Last active
July 5, 2021 09:48
-
-
Save iczero/c83d00b94dee022a0cd3a002f196958b to your computer and use it in GitHub Desktop.
stupid api service
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import express from 'express'; | |
import createDebug from 'debug'; | |
import childProcess from 'child_process'; | |
// RANDOM BULLSHIT AS A SERVICE (RBaaS), brought to you by iczero | |
// IMAGINE BEING THE PERSON THAT WROTE THIS | |
// i have literally spent more time writing this than thinking about the problem | |
// Find the shortest path from n to 1 using the operations n = n/2, n = n + 1, n = n - 1. | |
// n can only be divided by 2 when it is even, and it is always an integer. | |
export enum Operation { | |
INCREMENT = '+1', | |
DECREMENT = '-1', | |
SHIFT_RIGHT = '/2' | |
} | |
export interface Step { | |
operation: Operation; | |
value: bigint; | |
} | |
// naive: round down odd numbers | |
export function strategy1(n: bigint): Step[] { | |
let steps: Step[] = []; | |
while (n > 1n) { | |
if (n % 2n) { | |
n -= 1n; | |
steps.push({ operation: Operation.DECREMENT, value: n }); | |
} else { | |
n /= 2n; | |
steps.push({ operation: Operation.SHIFT_RIGHT, value: n }); | |
} | |
} | |
return steps; | |
} | |
// yes, typescript is necessary. 100% completely necessary. | |
type Strategy = typeof strategy1; | |
// naive: round up odd numbers | |
export function strategy2(n: bigint): Step[] { | |
let steps: Step[] = []; | |
while (n > 1n) { | |
if (n % 2n) { | |
n += 1n; | |
steps.push({ operation: Operation.INCREMENT, value: n }); | |
} else { | |
n /= 2n; | |
steps.push({ operation: Operation.SHIFT_RIGHT, value: n }); | |
} | |
} | |
return steps; | |
} | |
// WHAT DO YOU DO WHEN THINGS TAKE TOO LONG? EAT ALL OF THE RAM, OF COURSE! | |
// trade off space to improve time complexity | |
export function memoize(strategy: Strategy): Strategy { | |
let debug = createDebug('memo'); | |
let memo = new Map<bigint, Step[]>(); | |
// no cheating! | |
let clearQueued = false; | |
return (n: bigint): Step[] => { | |
let result = memo.get(n); | |
if (!result) { | |
debug('caching', n); | |
result = strategy(n); | |
memo.set(n, result); | |
} | |
if (!clearQueued) { | |
debug('queueing clear for memoize cache'); | |
clearQueued = true; | |
queueMicrotask(() => { | |
debug('clearing memoize cache'); | |
memo.clear(); | |
clearQueued = false; | |
}); | |
} | |
return result; | |
}; | |
} | |
// brute force | |
export function strategy3NoMemo(n: bigint): Step[] { | |
let debug = createDebug('strategy3'); | |
let steps: Step[] = []; | |
while (n > 1n) { | |
if (n % 2n) { | |
let stepsInc = strategy3(n + 1n); | |
let stepsDec = strategy3(n - 1n); | |
debug('n = %d, %d steps for n + 1, %d steps for n - 1', | |
n, stepsInc.length, stepsDec.length); | |
if (stepsInc.length >= stepsDec.length) { | |
steps.push({ operation: Operation.DECREMENT, value: n - 1n }); | |
steps = steps.concat(stepsDec); | |
} else { | |
steps.push({ operation: Operation.INCREMENT, value: n + 1n }); | |
steps = steps.concat(stepsInc); | |
} | |
return steps; | |
} else { | |
n /= 2n; | |
steps.push({ operation: Operation.SHIFT_RIGHT, value: n }); | |
} | |
} | |
return steps; | |
} | |
export let strategy3 = memoize(strategy3NoMemo); | |
// Math.log2() for bigints, rounding down | |
export function poorMansLog2(n: bigint): bigint { | |
let count = 0n; | |
while (n /= 2n) count++; | |
return count; | |
} | |
// race to 2^n: round odd numbers towards nearest power of 2 (iczero) | |
export function strategy4(n: bigint): Step[] { | |
let debug = createDebug('strategy4'); | |
let steps: Step[] = []; | |
while (n > 1n) { | |
if (n % 2n) { | |
let power = poorMansLog2(n); | |
let lower = 2n ** power; | |
let upper = 2n ** (power + 1n); | |
let lowerDistance = n - lower; | |
let upperDistance = upper - n; | |
debug('n = %d, lower = %d (distance %d), upper = %d (distance %d)', | |
n, lower, lowerDistance, upper, upperDistance); | |
if (lowerDistance < upperDistance) { | |
// round to lower power of 2 | |
n -= 1n; | |
steps.push({ operation: Operation.DECREMENT, value: n }); | |
} else { | |
// round to upper power of 2 | |
n += 1n; | |
steps.push({ operation: Operation.INCREMENT, value: n }); | |
} | |
} else { | |
n /= 2n; | |
steps.push({ operation: Operation.SHIFT_RIGHT, value: n }); | |
} | |
} | |
return steps; | |
} | |
// count number of ones in a base-2 number | |
export function countOnes(n: bigint): number { | |
let count = 0; | |
while (n > 0) { | |
count += Number(n % 2n); | |
n /= 2n; | |
} | |
return count; | |
} | |
// most zeroes: round odd numbers towards the number with most zeroes in binary (iovoid) | |
export function strategy5(n: bigint): Step[] { | |
let debug = createDebug('strategy5'); | |
let steps: Step[] = []; | |
while (n > 1n) { | |
if (n % 2n) { | |
let onesInc = countOnes(n + 1n); | |
let onesDec = countOnes(n - 1n); | |
debug('n = %d, ones in n + 1 = %d, ones in n - 1 = %d', n, onesInc, onesDec); | |
if (onesInc < onesDec) { | |
// more zeroes in n + 1 | |
n += 1n; | |
steps.push({ operation: Operation.INCREMENT, value: n }); | |
} else { | |
n -= 1n; | |
steps.push({ operation: Operation.DECREMENT, value: n }); | |
} | |
} else { | |
n /= 2n; | |
steps.push({ operation: Operation.SHIFT_RIGHT, value: n }); | |
} | |
} | |
return steps; | |
} | |
export const ALL_STRATEGIES = new Map<number, Strategy>([ | |
[1, strategy1], [2, strategy2], [3, strategy3], [4, strategy4], [5, strategy5] | |
]); | |
export function testOne(strategy: Strategy, n: bigint): string { | |
let steps = strategy(n); | |
let verify = verifySteps(n, steps); | |
return [ | |
`test: ${n}, ${steps.length} steps, verify ${verify ? 'passed' : 'failed'}`, | |
' ' + steps.map(a => a.operation).join(' '), | |
' ' + steps.map(a => a.value).join(', ') | |
].join('\n'); | |
} | |
export function testAll(n: bigint): string { | |
let output = `test: ${n}`; | |
for (let [idx, strategy] of ALL_STRATEGIES.entries()) { | |
let steps = strategy(n); | |
let verify = verifySteps(n, steps); | |
output += '\n' + [ | |
`strategy ${idx}: ${steps.length} steps, verify ${verify ? 'passed' : 'failed'}`, | |
' ' + steps.map(a => a.operation).join(' '), | |
' ' + steps.map(a => a.value).join(', ') | |
].join('\n'); | |
} | |
return output; | |
} | |
export function performOperation(n: bigint, op: Operation): bigint { | |
switch (op) { | |
case Operation.DECREMENT: return n - 1n; | |
case Operation.INCREMENT: return n + 1n; | |
case Operation.SHIFT_RIGHT: return n / 2n; | |
} | |
} | |
export function verifySteps(n: bigint, steps: Step[]): boolean { | |
let debug = createDebug('verify'); | |
for (let step of steps) { | |
if (step.operation === Operation.SHIFT_RIGHT && (n % 2n)) { | |
debug('n = %d, verify failed, cannot SHIFT_RIGHT odd integer', n); | |
return false; | |
} | |
let expected = performOperation(n, step.operation); | |
if (expected !== step.value) { | |
debug('n = %d, verify failed, operation = %s, expected = %d, found = %d', | |
n, step.operation, expected, step.value); | |
return false; | |
} else { | |
debug('n = %d, operation = %s, expected = %d', n, step.operation, expected); | |
} | |
n = expected; | |
} | |
if (n !== 1n) { | |
debug('n = %d, final result is not 1', n); | |
return false; | |
} | |
return true; | |
} | |
// DID SOMEONE SAY GRAPH THEORY | |
export class Link { | |
constructor(public operation: Operation, public target: GraphNode) {} | |
} | |
export class GraphNode { | |
public incoming = new Set<Link>(); | |
public outgoing = new Set<Link>(); | |
constructor(public id: number) {} | |
} | |
export function graphify(max: number): GraphNode { | |
let nodeQueue = new Map<number, GraphNode>(); | |
let done = new Map<number, GraphNode>(); | |
let enqueue = (n: number): GraphNode | null => { | |
if (n > max || n < 1) return null; | |
let node = done.get(n); | |
if (node) return node; | |
node = nodeQueue.get(n); | |
if (node) return node; | |
let newNode = new GraphNode(n); | |
nodeQueue.set(n, newNode); | |
return newNode; | |
} | |
let root = enqueue(1)!; | |
while (nodeQueue.size) { | |
let current = nodeQueue.values().next().value; | |
nodeQueue.delete(current.id); | |
done.set(current.id, current); | |
let n = current.id; | |
let incNode = enqueue(n - 1); | |
if (incNode) { | |
incNode.outgoing.add(new Link(Operation.INCREMENT, current)); | |
current.incoming.add(new Link(Operation.INCREMENT, incNode)); | |
} | |
let decNode = enqueue(n + 1); | |
if (decNode) { | |
decNode.outgoing.add(new Link(Operation.DECREMENT, current)); | |
current.incoming.add(new Link(Operation.DECREMENT, decNode)); | |
} | |
let rsNode = enqueue(n * 2); | |
if (rsNode) { | |
rsNode.outgoing.add(new Link(Operation.SHIFT_RIGHT, current)); | |
current.incoming.add(new Link(Operation.SHIFT_RIGHT, rsNode)); | |
} | |
} | |
return root; | |
} | |
export function graphToAdjList(root: GraphNode): [Set<GraphNode>, [GraphNode, Operation, GraphNode][]] { | |
// outgoing links only! | |
let links: [GraphNode, Operation, GraphNode][] = []; | |
let seen = new Set<GraphNode>(); | |
let queue: GraphNode[] = []; | |
let enqueue = (node: GraphNode) => { | |
if (seen.has(node)) return; | |
queue.push(node); | |
} | |
enqueue(root); | |
while (queue.length) { | |
let current = queue.pop()!; | |
for (let link of current.outgoing) { | |
links.push([current, link.operation, link.target]); | |
enqueue(link.target); | |
} | |
seen.add(current); | |
} | |
return [seen, links]; | |
} | |
const OP_TO_COLOR = { | |
'+1': 'red', | |
'-1': 'green', | |
'/2': 'blue' | |
}; | |
export function toGraphviz(root: GraphNode): string { | |
let [nodes, links] = graphToAdjList(root); | |
let g = 'digraph {'; | |
let push = (s: string) => g += '\n ' + s; | |
for (let node of nodes) push(`"${node.id}" ;`); | |
for (let link of links) push(`"${link[0].id}" -> "${link[2].id}" [label = "${link[1]}", color = "${OP_TO_COLOR[link[1]]}"]`); | |
g += '\n}'; | |
return g; | |
} | |
// of course it needs to be web, what do you mean | |
export let router = express.Router(); | |
if (require.main === module) { | |
let app = express(); | |
app.listen(process.env.PORT || 5000); | |
app.use('/', router); | |
} | |
function ensurePositiveBigint(s: string): bigint | null { | |
let n; | |
try { | |
n = BigInt(s); | |
} catch (err) { | |
return null; | |
} | |
if (n <= 0) return null; | |
return n; | |
} | |
function ensurePositiveInteger(s: string): number | null { | |
let n = +s; | |
if (Number.isNaN(n)) return null; | |
if (n <= 0) return null; | |
if (Math.floor(n) !== n) return null; | |
return n; | |
} | |
router.get('/test/:n', (req, res) => { | |
let n = ensurePositiveBigint(req.params.n); | |
if (!n) { | |
res.type('text/plain').status(400).send('hoping that something is a number usually doesn\'t make it a number'); | |
return; | |
} | |
res.type('text/plain').send(testAll(n)); | |
}); | |
router.get('/test/:n/strategy/:snum', (req, res) => { | |
let n = ensurePositiveBigint(req.params.n); | |
if (!n) { | |
res.type('text/plain').status(400).send('help i lack stupid error messages'); | |
return; | |
} | |
let snum = ensurePositiveInteger(req.params.snum); | |
if (!snum) { | |
res.type('text/plain').status(400).send('definitely not a valid strategy'); | |
return; | |
} | |
let strategy = ALL_STRATEGIES.get(snum); | |
if (!strategy) { | |
res.type('text/plain').status(400).send('strategy does not exist, unfortunately'); | |
return; | |
} | |
res.type('text/plain').send(testOne(strategy, n)); | |
}); | |
// stolen from IoServ | |
router.get('/graph/:max/raw', (req, res) => { | |
let max = ensurePositiveInteger(req.params.max); | |
if (!max) { | |
res.type('text/plain').status(400).send('your parameter is bad and you should feel bad'); | |
return; | |
} | |
res.type('text/plain').send(toGraphviz(graphify(max))); | |
}); | |
router.get('/graph/:max/json', (req, res) => { | |
let max = ensurePositiveInteger(req.params.max); | |
if (!max) { | |
res.status(400).send({ error: 'does that look like a positive integer to you?' }); | |
return; | |
} | |
let graph = graphify(max); | |
let [nodes, links] = graphToAdjList(graph); | |
res.send({ | |
nodes: [...nodes].map(a => a.id), | |
links: links.map(([n1, op, n2]) => [n1.id, op, n2.id]) | |
}); | |
}); | |
const GRAPH_FORMATS = new Set(['svg', 'png', 'dot']); | |
const GRAPH_RENDERERS = new Set(['dot', 'neato', 'circo', 'fdp', 'twopi']); | |
router.get('/graph/:max', (req, res) => { | |
let max = ensurePositiveInteger(req.params.max); | |
if (!max) { | |
res.type('text/plain').status(400).send('you are drunk'); | |
return; | |
} | |
let format = req.query.format || 'svg'; | |
if (typeof format !== 'string') { | |
res.type('text/plain').status(400).send(`format must be a string`); | |
return; | |
} | |
let renderer = req.query.renderer || 'dot'; | |
if (typeof renderer !== 'string') { | |
res.type('text/plain').status(400).send(`renderer must be a string`); | |
return; | |
} | |
if (!GRAPH_FORMATS.has(format)) { | |
res.type('text/plain').status(400).send(`unknown format: ${format}`); | |
return; | |
} | |
if (!GRAPH_RENDERERS.has(renderer)) { | |
res.type('text/plain').status(400).send(`unknown renderer: ${renderer}`); | |
return; | |
} | |
if (format === 'dot') res.type('text/plain'); | |
else res.type(format); | |
let graphviz = childProcess.spawn('dot', ['-T' + format, '-Goverlap=prism', '-Gsplines=spline'], { | |
argv0: renderer, | |
stdio: ['pipe', 'pipe', 'pipe'] | |
}); | |
graphviz.stdin.write(toGraphviz(graphify(max))); | |
graphviz.stdin.end(); | |
graphviz.stderr.pipe(res, { end: false }); | |
graphviz.stdout.pipe(res); | |
// let killTimeout = setTimeout(() => graphviz.kill(), 300 * 1000); | |
// graphviz.on('exit', () => clearTimeout(killTimeout)); | |
res.on('close', () => graphviz.kill()); | |
}); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment