AoC 2017: Day 10

This is the 10th post in my ongoing series about Advent of Code 2017. I’m going to describe my solutions implemented in JS (ES6+) and Node.js.

TL;DR: this is a very straightforward problem.

The problem description is here: http://adventofcode.com/2017/day/10, and the input can be found here: http://adventofcode.com/2017/day/10/input.

Part One

The problem is entirely about implementing the specific, well-defined algorithm, so let’s just quickly go over the code.

const { readFile, parseInt } = require("../lib");
const ls = readFile("./input")
  .split(",")
  .map(parseInt);

Just get the input.

const L = 256;
const a = Array.from({ length: L }, (_, i) => i);

Oh, these lines are interesting. We’re using the new https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/from function to build an array using the generator. The first argument is anything array-like, so we pass an object to define the array length. The second is a function behaving the same as you would pass to the Array.prototype.map method.

let i = 0;
let skip = 0;

The app state.

const read = l => {
  let max = i + l;
  const r = a.slice(i, max);
  if (max < L) {
    return r;
  }
  max -= L;
  return r.concat(a.slice(0, max));
};

const write = b => {
  let k = i;
  for (const el of b) {
    a[k] = el;
    k++;
    if (k >= L) {
      k -= L;
    }
  }
};

const revert = l => {
  write(read(l).reverse());
};

The basic operations, defined in the problem definition. The first one reads a slice of an array, of length l, wrapping around the end of the array if needed. The second makes the in-place mutations circularly writing a slice b from the index i. Finally, the last method puts everything together implementing a single hashing step defined by the length l.

for (const l of ls) {
  revert(l);
  i = (i + l + skip) % L;
  skip++;
}

console.log(a[0] * a[1]);

Now we follow the rest of the algo, consequently hashing for each l from the input.

The full code:

emirotin/advent2017

Part Two

The bigger part of this file is the same as before, so let’s only check the pieces that have changed.

const SUFFIX = [17, 31, 73, 47, 23];

const ls = readFile("./input")
  .split("")
  .map(c => c.charCodeAt(0))
  .concat(SUFFIX);

Here we treat the same input differently, as chars that define numbers corresponding to their ASCII codes, and add the predefined suffix, per problem definition.

const runRound = () => {
  for (const l of ls) {
    revert(l);
    i = (i + l + skip) % L;
    skip++;
  }
};

for (let j = 0; j < 64; j++) {
  runRound();
}

Here we’ve moved the single hashing round into a method (it’s still mutating the same global a instance). And run this method 64 times in a loop. This computes the sparse hash.

const xor = a => a.reduce((x, y) => x ^ y, 0);

const denseHash = new Array(16);
for (let j = 0; j < 16; j++) {
  denseHash[j] = xor(a.slice(j * 16, (j + 1) * 16));
}

Here we define an array xor method, similar to how we’ve implemented the sum method in several problems before. Then we use it to xor numbers in subsequent groups of 16 to compute the dense hash.

const toHex = n => {
  const h = n.toString(16);
  if (h.length < 2) {
    return "0" + h;
  }
  return h;
};

console.log(denseHash.map(toHex).join(""));

Finally, we compute the string representation of the dense hash by defining a helper method to stringify the number between 0 and 255 and left-pad it with zero if needed.

Full code:

emirotin/advent2017

Bonus: Clojure

emirotin/advent2017