Advent of Code Day 6, 7 and 8
Day 6 - Lanternfish
Did the first part via an Array, because I was expecting some GoL stuff in Part 2. There wasn't and the Array-based solution would take forever for part 2. So after a bit of thinking (and (for once) not looking at reddit for ideas) I realized that the position of each fish is irrelevant, and we just need to count the fish.
Counting fish is faster than fish-herding them in an array
So part 2 is converted to a hash (where the keys are the generation of the fish, and the value the number of fishes at that generation), and a very simple loop to move the fish around. I had a small problem while figuring out when to add fish vs just set them, but the finished code is quite clear to read.
Cleanup
Sometimes I later like to come back to the code and clean it up a bit more (and maybe make it a bit smarter). While doing so I realized that I don't need a hash, I can use the fish generation as the index of an array.
my @fish = map { 0 } ( 0 .. 8 );
for ( split( ',', <> ) ) {
$fish[ $_ ]++;
}Read in the list of fish and store them in an array indexed by the generation. The first line inits the array with 0s to prevent undefined warnings.
for my $day ( 1 .. 256 ) {
my $born = 0;
for my $gen ( 0 .. 8 ) {
if ( $gen 0 ) {
$born = $fish[$gen];
}
else {
$fish[ $gen - 1 ] = $fish[$gen];
}
}
$fish[6] += $fish[8] = $born;
say "$day: ".sum(@fish) if ( $day 80 || $day == 256 );
}Now for each of the days we go through all the generations, and move them one generation down ($fish[ $gen - 1 ] = $fish[$gen]). But the fish of generation 0 move to generation 6, and spawn the same number ($born) in generation 8. To calculate the sum of the fish i use List::Util's sum, but only for day 80 (part 1) and day 256 (part 2). My stupid array-based solution takes nearly a second for the first part, and probably forever for the second part; but the smarter solution takes only a few milliseconds for both parts.
Day 7 - The Treachery of Whales
For the first part I had a mathy gut feeling that the solution has to be related with the median of the values, so I hacked up a solution (using CPAN module Statistics::Basic for the statistics stuff), which worked for the test data. Tried the proper input and got a star!
So I assumed that part 2 will need mean. Tried it on the test-data, didn't work because the mean was a float, which I truncated to int. So I tried rounding it up, now it worked with test, but not with live data. Instead of thinking a tiny bit more, I thought that a brute force approach will also work and just calculated the fuel for all possible positions, which worked fast enough.
While brushing teeth (it's morning here..) I realized that I should also have tried the rounded down mean, so I did that, and got the proper result (much faster..). Of course I now knew that the result was in fact correct, but I don't have enough mathy gut feelings to prove that. Then I also used Gauss' sum formula for the fuel consumption. When I was coding the fuel sum I knew there was a smarter solution, but again the computer was fast enough for me to not use my brain (not sure I like this trend..)
Here's the cleaned up solution:
use Statistics::Basic qw(:all);
my @crabs = split( ',', <> );
my $mean = mean(@crabs);Read in the data and calculate the mean
my $res=0;
for my $cand ( int($mean), sprintf( '%.0f', $mean ) ) {
my $fuel;
for my $c (@crabs) {
my $diff = abs( $c - $cand );
$fuel += $diff * ( $diff + 1 ) / 2;
}
$res = !$res ? $fuel : $fuel < $res ? $fuel : $res;
}
say $res;Take the rounded down and rounded up mean, and for each go through all the crabs. Get the distance it has to travel, and use Gauss to calculate the fuel consumption. Then use the barley readable line $res = !$res ? $fuel : $fuel < $res ? $fuel : $res; to figure out which of the two candidates uses less fuel.
My favorite task this year so far :-)
Day 8 - Seven Segment Search
The first part was ridiculously easily especially considering the absurd long and complex explanation of the task. Just go through the second list of words and count those with the correct length:
my $hit;
for (<>) {
chomp;
my ( $first, $second ) = split / \| /;
for my $read ( split / /, $second ) {
my $l = length($read);
$hit++ if ( $l 2 || $l 3 || $l 4 || $l 7 );
}
}
say $hit;And now to something complex
It was clear that a few numbers are based on the length of the input (we did learn something in part 1!). To figure out the rest, I grabbed some of the best dev tools, pen & paper, and draw the missing numbers, and which lines are needed to get them. I soon realized that, from the numbers using 5 lines, only the 3 overlaps completely with the 1. This means that I need not figure out the exact position of each line, just which ones overlap. After a bit more drawing and thinking I found ways to identify the other numbers:
my $l = length($read);
my $cand = [ split( //, $read ) ];
if ( my $num = $direct{$l} ) {
$res[$num] = $cand;
}
elsif ( $l 5 ) {
if ( List::Compare->new( $cand, $res[1] )->get_intersection 2 ) {
$res[3] = $cand;
}
elsif ( List::Compare->new( $cand, $res[4] )->get_intersection 3 ) {
$res[5] = $cand;
}
else {
$res[2] = $cand;
}
}
elsif ( $l 6 ) {
if ( List::Compare->new( $cand, $res[1] )->get_intersection 1 ) {
$res[6] = $cand;
}
elsif ( List::Compare->new( $cand, $res[4] )->get_intersection 4 ) {
$res[9] = $cand;
}
else {
$res[0] = $cand;
}
}I was to lazy to come up with my own way to find the intersection of two arrays (see Abigale's post for a nice one), so I used List::Compare
The rest was simple: Map the letter combinations to their respective value:
my %decode;
for ( my $i = 0; $i < @res; $i++ ) {
$decode{ join( '', sort $res[$i]->@* ) } = $i;
}And finally go through the second set of readings, and convert them to a 4-digit number, and sum them all up:
my $output;
for my $read ( split / /, $second ) {
my $lookup = join( '', sort split( //, $read ) );
$output .= $decode{$lookup};
}
$sum += $output;Also a very nice task!