Disk Defragmentation - Advent of Code - 20171214

ac20171214.js

let knotHashRounds = function(lengths) {
  let salt = [17, 31, 73, 47, 23];

  let skip = 0;
  let currentPosition = 0;
  let numbers = new Array(256).fill(0).map((v, i) => i);

  let knotHash = function(input, lengths) {
    let numbers = input.slice();
    lengths.forEach((v, i) => {
      let length = [...numbers, ...numbers]
        .slice(currentPosition, currentPosition + v)
        .reverse();
      length.forEach((v, i) => {
        numbers[(currentPosition + i) % numbers.length] = v;
      });
      currentPosition = (currentPosition + v + skip++) % numbers.length;
    });

    return numbers;
  };

  lengths = lengths
    .split('')
    .map(v => v.charCodeAt())
    .concat(salt);

  for (let i = 0; i < 64; i++) {
    numbers = knotHash(numbers, lengths);
  }

  let denseHash = numbers.reduce((acc, v, i) => {
    let index = Math.floor(i / 16);
    acc[index] = acc[index] ^ v;
    return acc;
  }, new Array(16).fill(0));
  denseHash = denseHash.map(v => ('0' + v.toString(16)).substr(-2)).join('');

  return denseHash;
};

let hex2bin = function(hex) {
  return hex
    .split('')
    .map(v => parseInt(v, 16))
    .map(v => {
      return ('0000' + v.toString(2))
        .substr(-4)
        .split('')
        .map(v => parseInt(v));
    })
    .reduce((acc, v, i) => acc.concat(v), []);
};

let diskLayout = function(key) {
  return new Array(128)
    .fill(0)
    .map((v, i) => `${test}-${i}`)
    .map(v => knotHashRounds(v))
    .map(hex2bin);
};

let diskUsage = function(disk) {
  return disk
    .map(v => v.filter(bit => bit))
    .reduce((acc, v, i) => acc + v.length, 0);
};

let findDiskGroups = function(disk) {
  let removeGroup = function(x_orig, y_orig) {
    let c = (x, y) =>
      x < 0 || y < 0 || x >= disk.length || y >= disk[0].length
        ? 0
        : disk[x][y];

    disk[x_orig][y_orig] = 0;
    let adjacent = [[-1, 0], [1, 0], [0, -1], [0, 1]].map(v => [
      v[0] + x_orig,
      v[1] + y_orig
    ]);

    adjacent.forEach(([x, y]) => {
      if (c(x, y) == 1) {
        removeGroup(x, y);
      }
    });
  };

  let groupCount = 0;
  disk.forEach((row, x) => {
    row.forEach((column, y) => {
      if (column == 1) {
        groupCount++;
        removeGroup(x, y);
      }
    });
  });
  return groupCount;
};

let test = 'ugkiagan';
let result;

let disk = diskLayout(test);

// 8292
result = diskUsage(disk);
console.log(result);

// 1069
result = findDiskGroups(disk);
console.log(result);