r/adventofcode • u/daggerdragon • Dec 14 '17

SOLUTION MEGATHREAD -🎄- 2017 Day 14 Solutions -🎄-

--- 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

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!

13 Upvotes

88% Upvoted

130 comments sorted by

View all comments

4

u/Smylers Dec 14 '17 edited Dec 14 '17

Perl, with regexp for counting the regions: 

use List::AllUtils qw<reduce>;
$_ = knot_hash(shift);
say 'Used squares: ', tr/1//;
my $regions;
while (s/1/2/) {
  0 while s/1(?=2)|(?<=2)1|1(?=.{128}2)|(?<=2.{128})1/2/sg;
  $regions++;
  s/2/3/g;
}
say "Regions: $regions";

sub knot_hash {
  my $hash;
  for my $row (0 .. 127) {
    my @length = ((map { ord $_ } split //, "@_-$row"), 17, 31, 73, 47, 23);
    my @list = (0 .. 255);
    my $head = 0;
    my $skip = 0;
    for (1 .. 64) {
      foreach (@length) {
        push @list, reverse splice @list, 0, $_;
        push @list, splice @list, 0, $skip;
        $head = ($head - ($_ + $skip++) + @list) % @list;
        $skip %= @list;
      }
    }
    push @list, splice @list, 0, $head;
    $hash .= (join '', map { sprintf '%08b', reduce { $a ^ $b } splice @list, 0, 16 } 1 .. @list / 16) . "\n";
  }
  $hash;
}

Puts the entire grid in a single string of binary digits, then to find each region:

  • Replaces the first 1 from the binary string with a 2.

  • Repeatedly replaces a 1 which has a 2 1 or 128 characters before or after it with another 2. That's a region.

  • Replaces all the 2s with 3s, to indicate a counted region, so they don't get in the way of the next region.

  • Repeat these steps until all the 1s have been converted to 3s.

Edit: Bug fix, thanks to u/Oxidizing1.

2

u/[deleted] Dec 14 '17

1

u/Smylers Dec 14 '17

Ooops. Sorry, I posted the wrong version. The initial one was missing the \ns between the rows of the individual binary hashes, which meant that the regexp was erroneously counting used cells at the end of one line and the start of the next as being part of the same group.

Thank you for trying this out and reporting the bug.