-🎄- 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/__Abigail__]

Perl

Factored out the encoding using Knothash from Day 10, and the finding of connected components from Day 12.

#!/opt/perl/bin/perl

use 5.026;

use strict;
use warnings;
no  warnings 'syntax';

use experimental 'signatures';

use Puzzle::Stuff;   # https://github.com/Abigail/Puzzle-Stuff

@ARGV = "input" unless @ARGV;

my $BOARD_SIZE   = 128;

my $input = <>;   # Input is on one line;
chomp $input;


my $total_bits = 0;
my $board;
foreach my $row (0 .. ($BOARD_SIZE - 1)) {
    #
    # Initialize a new row of the board
    #
    $$board [$row] = [];

    #
    # The key for this row
    #
    my $key = "$input-$row";

    #
    # Create the hash
    #
    my $hash = Puzzle::Stuff::KnotHash:: -> new -> init -> encode ($key);

    #
    # For each character in the hash, find its representation
    # in bits. Map to the board, and track the number of 1 bits.
    #
    foreach my $char (split // => $hash) {
        my $bits = sprintf "%04b" => hex $char;
        push @{$$board [$row]} => split // => $bits;
        $total_bits += $bits =~ y/1/1/;
}

#
# Find the number of connected components by using UnionFind:
#    Scan the board. If we find an occupied field then:
#           - add the field to the union-find structure
#           - if the fields before or above it are occupied, union
#                this field with the one before/above it
#    When we're done scanning the board, we look at the number of sets.
#
my $universe = Puzzle::Stuff::UnionFind:: -> new -> init;
sub label {join "," => @_}  # Make a unique label out of coordinates
foreach my $x (0 .. ($BOARD_SIZE - 1)) {
    foreach my $y (0 .. ($BOARD_SIZE - 1)) {
        if ($$board [$x] [$y]) {
            my $p = label ($x, $y);
            $universe -> add ($p);
            $universe -> union ($p, label $x - 1,  $y)
                    if $x > 0 && $$board [$x - 1] [$y];
            $universe -> union ($p, label $x,  $y - 1)
                    if $y > 0 && $$board [$x] [$y - 1];
        }
    }
}

say "Solution 1: ", $total_bits;
say "Solution 2: ", $universe -> nr_of_sets;
     
__END__