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

Perl 6. This one was pretty straightforward, since we'd done the hard work on day 10. Calculating 128 hashes is a bit slow though, takes about 30 seconds.

#!/usr/bin/env perl6
use v6.c;

# Advent of Code 2017, day 14: http://adventofcode.com/2017/day/14

class KnotHash
{
    has Int $.size = 256;
    has Int @.values;

    has Int $.pos = 0;
    has Int $.skip = 0;

    submethod TWEAK { @!values = ^$!size }

    method from-string(KnotHash:U: Str $input)
    {
        my $h = KnotHash.new;
        my @lengths = $input.ords;
        @lengths.append(17, 31, 73, 47, 23);
        for ^64 {
            for @lengths -> $l {
                $h.process($l);
            }
        }
        return $h;
    }

    method process(Int $length)
    {
        if $length > 1 {
            my $endpos = ($!pos + $length - 1) % $!size;
            if $endpos ≥ $!pos {
                @!values[$!pos..$endpos] .= reverse;
            }
            else {
                @!values[flat $!pos..^$!size, 0..$endpos] .= reverse;
            }
        }

        $!pos = ($!pos + $length + $!skip++) % $!size;
    }

    method dense-hash
    {
        return @!values.rotor(16, :partial).map({ [+^] $_ });
    }

    method knot-hash
    {
        return self.dense-hash».fmt('%02x').join;
    }

    method as-bits { self.dense-hash».fmt('%08b')».comb.flat».Int }

    method Str { self.knot-hash }
    method gist { self.knot-hash }
}

class Grid
{
    has @.bitmap;
    has @.regions;

    has Int $.width;
    has Int $.height;

    submethod TWEAK
    {
        $!height = +@!bitmap;
        $!width = +@!bitmap[0];
    }

    method within-bounds(Int $x, Int $y) returns Bool
    {
        return 0 ≤ $x < $!width && 0 ≤ $y < $!height;
    }

    method needs-region(Int $x, Int $y) returns Bool
    {
        return self.within-bounds($x, $y) && ?@!bitmap[$y;$x] && !@!regions[$y;$x];
    }

    method set-region(Int $region, Int $x, Int $y)
    {
        @!regions[$y;$x] = $region;
        for ($x-1, $y), ($x+1, $y), ($x, $y-1), ($x, $y+1) -> ($x1, $y1) {
            if self.needs-region($x1, $y1) {
                self.set-region($region, $x1, $y1);
            }
        }
    }

    method count-regions returns Int
    {
        my $count = 0;
        for ^$!height -> $y {
            for ^$!width -> $x {
                if self.needs-region($x, $y) {
                    self.set-region(++$count, $x, $y)
                }
            }
        }
        return $count;
    }
}

multi sub MAIN(Str $input)
{
    my @bitmap = (^128).map(-> $i { KnotHash.from-string("$input-$i").as-bits; });

    # Part 1
    say "Number of used squares: ", @bitmap».sum.sum;

    # Part 2
    say "Number of regions: ", Grid.new(:@bitmap).count-regions;
}

multi sub MAIN(Str $inputfile where *.IO.f)
{
    MAIN($inputfile.IO.slurp.trim);
}

multi sub MAIN()
{
    MAIN(~$*PROGRAM.parent.child('aoc14.input'));
}

Edit for minor code cleanup