Movie Seating

movie-seating.js

// @ts-check

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

const traceHashMap = {};

const trace = n => {
  const hash = crypto.createHash("sha1");
  hash.update(n.toString());
  const str = hash.digest("hex");
  return str
    .split("")
    .reduce((acc, char) => (parseInt(char) + 1 ? acc : acc + char), "");
};

for (let i = 0; i < 100; i++) {
  traceHashMap[i] = trace(i);
}

const affinity = (n, m) => levenshtein.get(traceHashMap[n], traceHashMap[m]);

const posdist = (n, m, arr) => Math.abs(arr.indexOf(n) - arr.indexOf(m));

const pairScore = (n, m, arr) => affinity(n, m) / posdist(n, m, arr);

const score = arr =>
  arr.reduce(
    (nacc, n) =>
      nacc +
      arr.reduce((macc, m) => {
        if (n >= m || n === m) {
          return macc;
        }
        return posdist(n, m, arr) <= 3 ? macc + pairScore(n, m, arr) : macc;
      }, 0),
    0
  );

const imperativeScore = arr => {
  let iScore = 0;
  for (let n = 0; n < arr.length; n++) {
    for (let m = 0; m < arr.length; m++) {
      iScore = iScore + getScore(n, m, arr);
    }
  }
  return iScore;
};

const getScore = (n, m, arr) => {
  return n < m && n !== m && posdist(n, m, arr) <= 3 ? pairScore(n, m, arr) : 0;
};

const getRandomArr = n => {
  const reference = new Array(n);
  const result = [];
  for (let i = 0; i < n; i++) {
    reference[i] = i + 1;
  }
  for (let i = 1; i <= n; i++) {
    const index = Math.floor(Math.random() * reference.length);
    result.push(reference.splice(index, 1)[0]);
  }
  return result;
};

const getSequence = n => {
  const result = new Array(n);
  for (let i = 0; i < n; i++) {
    result[i] = i;
  }
  return result;
};

const createOptimisedArray = (length, seed, n) => {
  // For the given seed, compute the next n best fits in the chain
  const result = new Array(length);
  result[0] = seed;
  const reference = getSequence(length);
  console.log(reference);
  return;
  for (let i = 1; i < length; i++) {
    const { score, index } = getNextBestScore(result[i - 1], result, reference);
    console.log(reference, index);
    result[i] = reference[index];
    reference.splice(reference.indexOf(index), 1);
  }
  return result;
};

const getNextBestScore = (n, currentArr, remainingArr) => {
  let index = 0;
  let max = 0;
  for (let i = 0; i < remainingArr.length; i++) {
    console.log(
      "getScore",
      n,
      remainingArr[i],
      JSON.stringify([...currentArr, remainingArr[i]])
    );
    const score = getScore(n, remainingArr[i], [
      ...currentArr,
      remainingArr[i]
    ]);
    // console.log("score", score);
    if (score > max) {
      max = score;
      index = i;
    }
  }
  return { score: max, index };
};

let max = 0;
let comps = 0;
let time = Date.now();
// while (true) {
//   const testArr = getRandomArr(100);
//   const arrScore = imperativeScore(testArr);
//   if (arrScore > max) {
//     console.log("New result", arrScore, JSON.stringify(testArr));
//     console.log("Computations", comps);
//     console.log("C/sec", comps / ((Date.now() - time) / 1000));
//     max = arrScore;
//   }
//   comps++;
// }
const ex = createOptimisedArray(100, 0);
console.log(ex);
console.log(imperativeScore(ex), JSON.stringify(ex));