stupid api service

oneify.ts

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());
});