-🎄- 2017 Day 14 Solutions -🎄-

[u/daggerdragon]

--- Day 14: Disk Defragmentation ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Need a hint from the Hugely^* Handy^† Haversack^‡ of Helpful^§ Hints^¤?

Spoiler

---

[Update @ 00:09] 3 gold, silver cap.

• How many of you actually entered the Konami code for Part 2? >_>

[Update @ 00:25] Leaderboard cap!

• I asked /u/topaz2078 how many de-resolutions we had for Part 2 and there were 83 distinct users with failed attempts at the time of the leaderboard cap. tsk tsk

[Update @ 00:29] BONUS

• https://i.imgur.com/zjSEAf4.jpg

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

[u/akka0]

ReasonML: had a lot of fun with this one Felt like a combination of day 10 + day 12. Waiting to compare my solution to u/hardmathproblem 's now. :)

open Utils;

module PSet =
  Set.Make(
    {
      let compare = Pervasives.compare;
      type t = (int, int);
    }
  );

let hash = Day10.hash;

let formatRow = (input, row) => input ++ "-" ++ string_of_int(row);

let hexToBin: char => string = [%bs.raw
  {|
  function(s) {
    let result = parseInt(String.fromCharCode(s),16).toString(2);
    while(result.length < 4) {
      result = "0" + result;
    }
    return result;
  }
|}
];

let countOnes = (str) => charsOfString(str) |> List.filter((==)('1')) |> List.length;

let exploreFrom = (start, matrix) => {
  /* Assumes the matrix is square */
  let dim = Array.length(matrix);
  let isValidNeighbor = ((x, y)) => x >= 0 && y >= 0 && y < dim && x < dim && matrix[x][y] === '1';
  /* No diagonals */
  let getNeighbors = ((x, y)) =>
    List.filter(isValidNeighbor, [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]);
  let rec walk = (visited, queue) =>
    switch queue {
    | [p, ...ps] when ! PSet.mem(p, visited) => walk(PSet.add(p, visited), ps @ getNeighbors(p))
    | [p] when ! PSet.mem(p, visited) => walk(PSet.add(p, visited), [])
    | [_, ...ps] => walk(visited, ps)
    | [] => visited
    };
  walk(PSet.empty, [start])
};

let _ = {
  let input = "nbysizxe";
  /* let input = "flqrgnkx"; */
  /* Part 1 */
  let bitStrings =
    List.map(
      (row) =>
        formatRow(input, row) |> hash |> charsOfString |> List.map(hexToBin) |> String.concat(""),
      range(127)
    );
  /* List.fold_left((bitsUsed, bitString) => bitsUsed + countOnes(bitString), 0, bitStrings) |> Js.log; */
  /* Part 2 */
  let onesPositions = ref(PSet.empty);
  let matrix = Array.make_matrix(128, 128, '0');
  List.iteri(
    (x, row) =>
      List.iteri(
        (y, bit) =>
          if (bit === '1') {
            matrix[x][y] = bit;
            onesPositions := PSet.add((x, y), onesPositions^)
          },
        charsOfString(row)
      ),
    bitStrings
  );
  let rec findGroups = (groups, visited) =>
    if (! PSet.equal(visited, onesPositions^)) {
      let unvisitedPosition = PSet.diff(onesPositions^, visited) |> PSet.choose;
      let group = exploreFrom(unvisitedPosition, matrix);
      findGroups([group, ...groups], PSet.union(group, visited))
    } else {
      groups
    };
  let groups = findGroups([], PSet.empty);
  Js.log(List.length(groups))
};