RoboRackers™ - Riddle by FiveThirtyEight - Solved with JavaScript

The FiveThirtyEight riddle RoboRackers™ is stated as follows.

      0        <-- Template
     1 0
    0 8 1      0 = Solids
   1 0 1 0     1 = Striped
  0 1 1 0 1    8 = Eightball

You own a start-up, RoboRackers™, that makes robots that can rack pool balls. To operate the robot, you give it a template, such as the one shown below. The template only recognizes the differences among stripes, solids and the eight ball. None of the other numbers matters.

First, the robot randomly corrals all of the balls into the wooden triangle. From there, the robot can either swap the location of two balls or rotate the entire rack 120 degrees in either direction. The robot continues performing these operations until the balls’ formation matches the template, and it always uses the fewest number of operations possible to do so.

Using the template given above — a correct rack for a standard game of eight-ball — what is the maximum number of operations the robot would perform? What starting position would yield this? How about the average number of operations?

FiveThirtyEight, The Robot Invasion Has Come For Our Pool Halls

// [X]  1. Generate all possible start formations.
// [X]  2. Count template and start formation differences.
//         Operations = Rotations + ⌈differences /2⌉
// [X]  3. Find start formation that needs most operations.
// [X]  4. Calculate average operations / start formation.

// The template is used both as target formation and source.
const template = [
  0,
  1, 0,
  0, 8, 1,
  1, 0, 1, 0,
  0, 1, 1, 0, 1
];

// Rack rotation functions
const rotateLeft = r => [r[14], r[9], r[13], r[5], r[8], r[12], r[2], r[4], r[7], r[11], r[0], r[1], r[3], r[6], r[10]];
const rotateRight = r => [r[10], r[11], r[6], r[12], r[7], r[3], r[13], r[8], r[4], r[1], r[14], r[9], r[5], r[2], r[0]];

// Create two extra rotated templates.
// (instead of rotating every permutation)
const templates = [
  {template, rotations: 0},
  {template: rotateLeft(template), rotations: 1},
  {template: rotateRight(template), rotations: 1}
];

// Use a next lexicographical permutation algorithm to
// generate all possible start formations.
function* generatePermutations(array) {
  // Nayuki has an amazing explanation this algo.
  // https://www.nayuki.io/page/next-lexicographical-permutation-algorithm

  let next = Array.from(array).sort();

  const nextPermutation = (array) => {

    // Reverse array to make identifying pivot
    // and successor easier.
    const reversedArray = [...array].reverse();

    // Find longest non-increasing suffix.
    const i = reversedArray.findIndex((item, index, collection) =>
        collection[index] < collection[index - 1]);

    // Exit if we are at the last permutation.
    if (i <= 0) {
      return false;
    }

    // Identify pivot.
    const pivot = reversedArray[i];

    // Find rightmost successor to pivot the suffix.
    const j = reversedArray.findIndex(item => item > pivot);

    // Identify successor and swap places.
    reversedArray[i] = reversedArray[j];
    reversedArray[j] = pivot;

    // Reverse suffix.
    const prefix = reversedArray.splice(i);
    return [...prefix.reverse(), ...reversedArray];

  };

  do {
    yield next;
    next = nextPermutation(next);
  } while (next);

}

const permutations = Array.from(generatePermutations(template));
console.log(`There are ${permutations.length} unique start formations.`);
// > There are 51480 unique start formations.


const getDifferences = (a, b) => a.reduce((memo, _, i) => {
  return memo + (b[i] !== a[i] ? 1 : 0);
}, 0);

const data = permutations.map(state => {
  // Minimum required operations is rotations + number of differences
  // between the state and the template divided by 2.
  const operations = templates.map(item =>
      Math.ceil(getDifferences(item.template, state) / 2) + item.rotations);

  return {
    // ...and it always uses the fewest number of operations possible to do so...
    operations: Math.min.apply(Math, operations),
    state
  }

});

const sorted = data.sort((a, b) => b.operations - a.operations);
const worst = sorted[0];

console.log(`Maxium required operations is ${worst.operations}.`);
// > Maxium required operations is 6.

console.log(`One of the worst starting states is ${worst.state}.`);
// > One of the worst starting states is 0,0,1,1,1,0,1,1,0,0,8,0,0,1,1.

const getAverage = (arr, key) => arr.reduce((memo, item) => memo + item[key], 0) / arr.length;
const average = getAverage(data, 'operations');

console.log(`There average required operations is ${average}.`);
// > There average required operations is 4.016860916860917.

Keywords