Skip to content

Instantly share code, notes, and snippets.

View qntm's full-sized avatar

qntm qntm

View GitHub Profile
@qntm
qntm / held-karm-wasm.js
Last active November 13, 2024 23:24
Parallel JavaScript and WASM implementations of the Held–Karp algorithm for solving the travelling salesman problem
// The non-performance-intensive parts of this implementation can remain JavaScript.
import fs from 'node:fs/promises'
const BYTES_PER_INT32 = 4
const BYTES_PER_FLOAT64 = 8
const BYTES_PER_PAGE = 65_536
const wasmBuffer = await fs.readFile('./held-karp.wasm')
@qntm
qntm / xact.js
Last active December 10, 2021 19:32
Get all the decimal digits of any JavaScript float
const SIGN_BITS = 1n
const EXPONENT_BITS = 11n
const MANTISSA_BITS = 52n
const BIAS = 1023n
export const stringify = value => {
if (typeof value !== 'number') {
throw Error('Not a number')
}
@qntm
qntm / gilded_rose.js
Last active November 15, 2021 19:22
My Gilded Rose entry
class Item {
constructor (name, sellIn, quality) {
this.name = name
this.sellIn = sellIn
this.quality = quality
}
}
class Shop {
constructor (items = []) {
@qntm
qntm / isPowerOfTwo.js
Last active December 8, 2021 00:32
Determine whether a JavaScript value is a power of two (non-broken edition)
// Exports a function which determines whether a JavaScript value is a power of
// two or not. Unlike the npm package `is-power-of-two`, this actually returns
// the correct answer in all cases.
const countSetBits = i => {
// Based on <https://stackoverflow.com/a/109025/792705> but with some of the
// performance optimisations reverted for the sake of improved legibility.
i = (i & 0b01010101010101010101010101010101) + ((i & 0b10101010101010101010101010101010) >>> 1)
i = (i & 0b00110011001100110011001100110011) + ((i & 0b11001100110011001100110011001100) >>> 2)
i = (i & 0b00001111000011110000111100001111) + ((i & 0b11110000111100001111000011110000) >>> 4)
@qntm
qntm / trend.js
Last active August 1, 2020 16:06
Parsing highly ambiguous Twitter trend strings
const { UNICODE, seq } = require('green-parse')
const trend = UNICODE.plus().map(chars => chars.join(''))
// match e.g. "trend1, trend2, trend3" and return ["trend1", "trend2", "trend3"]
const trends = trend.plus(', ')
// match e.g. "trend1, trend2 and trend3" and return ["trend1", "trend2", "trend3"]
const trendsAndTrend = seq([trends, ' and ', trend])
.map(([trends, and, trend]) => [...trends, trend])
@qntm
qntm / defeat-appscan-heuristics.js
Last active August 1, 2020 16:07
Defeating AppScan false positives in JavaScript
// AppScan may flag up a call like this as "Insecure Use of Document.Write"
// because it isn't intelligent enough to know that this a call to a totally
// unrelated method also named `write`
const diffBuffer = PNG.sync.write(diffPng)
// Replace with:
// eslint-disable-next-line no-useless-call
const diffBuffer = PNG.sync.write.call(PNG.sync, diffPng)
///////////////////////////////
@qntm
qntm / everyfloat.js
Last active October 16, 2022 00:44
Get in, loser, we're iterating over every 64-bit float
const nextafter = require('nextafter')
for (let i = -Infinity; i !== Infinity; i = nextafter(i, Infinity)) {
console.log(i)
}
// Whoops, forgot a few the first time I ran this
console.log(Infinity)
console.log(NaN)
@qntm
qntm / high-water-mark-roman.js
Last active January 18, 2020 19:02
What is the smallest number which, when expressed in Roman numerals, won't fit in a 280-character Tweet?
// <https://twitter.com/Revolvolutionry/status/1165616879009816576>
// <https://oeis.org/A036746>
const { arabicToRoman, romanToArabic } = require('big-roman')
// The entry at index `i` in this array is the smallest Roman numeral
// of length `i`
const results = ['']
const stopAt = 281
let powerOfTen = 0
@qntm
qntm / roman.js
Last active June 17, 2019 19:50
An extremely spare Roman numerals converter
// No bounds/type checking
// No support for the overbar extension for numbers past 3999
const banks = [
['', 'I', 'II', 'III', 'IV', 'V', 'VI', 'VII', 'VIII', 'IX'],
['', 'X', 'XX', 'XXX', 'XL', 'L', 'LX', 'LXX', 'LXXX', 'XC'],
['', 'C', 'CC', 'CCC', 'CD', 'D', 'DC', 'DCC', 'DCCC', 'CM'],
['', 'M', 'MM', 'MMM']
]
@qntm
qntm / quine.js
Last active October 16, 2023 12:50
There are others like it, but this one is quine
(s => console.log(`${s}\n(${JSON.stringify(s)})\n`))
("(s => console.log(`${s}\\n(${JSON.stringify(s)})\\n`))")