Coding challenge

index.js

const crypto = require("crypto");
const memoize = require("fast-memoize");
const levenshtein = require("js-levenshtein");

const createInts = n => Array.from({ length: n }, (_, i) => i);

const trace = memoize(i =>
  crypto
    .createHash("sha1")
    .update(`${i}`)
    .digest("hex")
    .replace(/[0-9]/g, "")
);

const affinity = memoize((n, m) => levenshtein(trace(n), trace(m)));
const posdist = (arr, n, m) => Math.abs(arr.indexOf(n) - arr.indexOf(m));
const pairScore = (arr, n, m) => affinity(n, m) / posdist(arr, n, m);
const score = arr => {
  let sum = 0;
  for (let n = 0; n < arr.length; n += 1) {
    for (let m = n + 1; m < arr.length; m += 1) {
      const n1 = arr[n];
      const m1 = arr[m];

      if (posdist(arr, n1, m1) < 4) {
        sum += pairScore(arr, n1, m1);
      }
    }
  }
  return sum;
};

const ints = createInts(100);

let i = 0;
let len = 0;

const solve = (
  left,
  searchDepth,
  seq = [],
  depth = searchDepth,
  walking = false
) => {
  i++;
  if (seq.length > len) {
    console.log({ len, i });
    len++;
  }
  if (!left.length || depth === 0) {
    return [score(seq), seq];
  }

  const [s, maxSeq] = left.reduce(
    ([max, _seq], l, i) => {
      const [score, __seq] = solve(
        [...left.slice(0, i), ...left.slice(i + 1)],
        searchDepth,
        [...seq, l],
        depth - 1,
        true
      );
      if (score > max) {
        return [score, __seq];
      }

      return [max, _seq];
    },
    [-Infinity, null]
  );

  if (walking) {
    return [s, maxSeq];
  }

  const _seq = maxSeq.slice(0, seq.length + 1);
  const _left = left.filter(l => l !== _seq[_seq.length - 1]);

  return solve(_left, searchDepth, _seq);
};

const l = (...args) => console.log(JSON.stringify(args));

l(solve(ints, 3));