From: Jan "Yenya" Kasprzak Date: Thu, 24 Nov 2022 15:56:41 +0000 (+0100) Subject: Year 2018 X-Git-Url: https://www.fi.muni.cz/~kas/git//home/kas/public_html/git/?p=aoc.git;a=commitdiff_plain;h=eb440d6121be85da5c73a639795fb430e6fdb358 Year 2018 --- diff --git a/2018/01.pl b/2018/01.pl new file mode 100755 index 0000000..85b5f94 --- /dev/null +++ b/2018/01.pl @@ -0,0 +1,7 @@ +#!/usr/bin/perl -w + +use v5.30; +use strict; + +use List::Util qw(sum); +say sum <>; diff --git a/2018/02.pl b/2018/02.pl new file mode 100755 index 0000000..b90441f --- /dev/null +++ b/2018/02.pl @@ -0,0 +1,20 @@ +#!/usr/bin/perl -w + +use v5.30; +use strict; + +my %seen; +my $freq = 0; +chomp(my @changes = <>); +while (1) { + for my $x (@changes) { + $freq += $x; + if ($seen{$freq}++) { + say $freq; + exit 0; + } + } +} + + + diff --git a/2018/03.pl b/2018/03.pl new file mode 100755 index 0000000..793775f --- /dev/null +++ b/2018/03.pl @@ -0,0 +1,17 @@ +#!/usr/bin/perl -w + +use v5.30; +use strict; + +my ($two, $three); +while (<>) { + chomp; + my %h; + $h{$_}++ for split //; + $two++ if grep { $_ == 2 } values %h; + $three++ if grep { $_ == 3 } values %h; +} + +say $two * $three; + + diff --git a/2018/04.pl b/2018/04.pl new file mode 100755 index 0000000..dca4189 --- /dev/null +++ b/2018/04.pl @@ -0,0 +1,22 @@ +#!/usr/bin/perl -w + +use v5.30; +use strict; + +my %seen; +while (<>) { + chomp; + for my $i (0 .. length($_) - 1) { + my $x = $_; + substr($x, $i, 1) = '_'; + $seen{$x}++; + } +} + +for my $k (keys %seen) { + if ($seen{$k} == 2) { + $k =~ s/_//; + say $k; + } +} + diff --git a/2018/05.pl b/2018/05.pl new file mode 100755 index 0000000..5eadf3b --- /dev/null +++ b/2018/05.pl @@ -0,0 +1,21 @@ +#!/usr/bin/perl -w + +use v5.30; +use strict; + +my %map; +while (<>) { + chomp; + my ($id, $x, $y, $w, $h) = /(\d+)/g; + for my $dx (0 .. $w-1) { + for my $dy (0 .. $h-1) { + $map{$x+$dx,$y+$dy}++; + } + } +} + +my $sum; +for my $k (keys %map) { + $sum++ if $map{$k} > 1; +} +say $sum; diff --git a/2018/06.pl b/2018/06.pl new file mode 100755 index 0000000..8b921f3 --- /dev/null +++ b/2018/06.pl @@ -0,0 +1,24 @@ +#!/usr/bin/perl -w + +use v5.30; +use strict; + +my %map; +my %no; +while (<>) { + chomp; + my ($id, $x, $y, $w, $h) = /(\d+)/g; + my $o; + for my $dx (0 .. $w-1) { + for my $dy (0 .. $h-1) { + if (defined $map{$x+$dx,$y+$dy}) { + delete $no{$map{$x+$dx,$y+$dy}}; + $o++; + } + $map{$x+$dx,$y+$dy} = $id; + } + } + $no{$id} = 1 if !$o; +} + +say keys %no; diff --git a/2018/07.pl b/2018/07.pl new file mode 100755 index 0000000..d1ee816 --- /dev/null +++ b/2018/07.pl @@ -0,0 +1,45 @@ +#!/usr/bin/perl -w + +use v5.30; +use strict; + +my ($g, $sleep_m); +my (%sleep_g, %sleep_g_m); +for (sort <>) { + if (/#(\d+) begins/) { + $g = $1; + } elsif (/:(\d+)\] falls/) { + $sleep_m = $1; + } elsif (/:(\d+)\] wakes/) { + $sleep_g{$g} += $1 - $sleep_m; + for my $min ($sleep_m .. $1 - 1) { + $sleep_g_m{$g}{$min}++; + } + } +} + +my $max_g; +my $max_g_sleep; +for my $g (keys %sleep_g) { + if (!$max_g_sleep || $max_g_sleep < $sleep_g{$g}) { + $max_g = $g; + $max_g_sleep = $sleep_g{$g}; + } +} +my $max_min; +my $max_min_sleep; +for my $min (keys %{ $sleep_g_m{$max_g} }) { + my $n = $sleep_g_m{$max_g}{$min}; + if (!defined $max_min_sleep || $max_min_sleep < $n) { + $max_min = $min; + $max_min_sleep = $n; + } +} + +say $max_g * $max_min; + + + + + + diff --git a/2018/08.pl b/2018/08.pl new file mode 100755 index 0000000..d5446ff --- /dev/null +++ b/2018/08.pl @@ -0,0 +1,41 @@ +#!/usr/bin/perl -w + +use v5.30; +use strict; + +my ($g, $sleep_m); +my (%sleep_g, %sleep_g_m); +for (sort <>) { + if (/#(\d+) begins/) { + $g = $1; + } elsif (/:(\d+)\] falls/) { + $sleep_m = $1; + } elsif (/:(\d+)\] wakes/) { + $sleep_g{$g} += $1 - $sleep_m; + for my $min ($sleep_m .. $1 - 1) { + $sleep_g_m{$g}{$min}++; + } + } +} + +my $max_g; +my $max_min; +my $max_min_sleep; +for my $g (keys %sleep_g) { + for my $min (keys %{ $sleep_g_m{$g} }) { + my $n = $sleep_g_m{$g}{$min}; + if (!defined $max_min_sleep || $max_min_sleep < $n) { + $max_g = $g; + $max_min = $min; + $max_min_sleep = $n; + } + } +} + +say $max_g * $max_min; + + + + + + diff --git a/2018/09.pl b/2018/09.pl new file mode 100755 index 0000000..7abf1d8 --- /dev/null +++ b/2018/09.pl @@ -0,0 +1,13 @@ +#!/usr/bin/perl -w + +use v5.30; +use strict; + +chomp (my $data = <>); + +my $re = join('|', map { ("\l$_\u$_", "\u$_\l$_") } ('a' .. 'z')); + +1 while $data =~ s/$re//; + +say length $data; + diff --git a/2018/10.pl b/2018/10.pl new file mode 100755 index 0000000..d37215e --- /dev/null +++ b/2018/10.pl @@ -0,0 +1,19 @@ +#!/usr/bin/perl -w + +use v5.30; +use strict; + +chomp (my $data = <>); + +my $re = join('|', map { ("\l$_\u$_", "\u$_\l$_") } ('a' .. 'z')); + +my $min; +for my $c ('a' .. 'z') { + my $d1 = $data; + $d1 =~ s/$_//g for $c, "\u$c"; + 1 while $d1 =~ s/$re//; + $min = length $d1 if !$min || $min > length $d1; +} + +say $min; + diff --git a/2018/11.pl b/2018/11.pl new file mode 100755 index 0000000..0fe2b4e --- /dev/null +++ b/2018/11.pl @@ -0,0 +1,50 @@ +#!/usr/bin/perl -w + +use v5.30; +use strict; + +my @pts = map { [ /(\d+)/g ] } <>; + +my ($minx, $miny, $maxx, $maxy); +for my $pt (@pts) { + $minx = $pt->[0] if !defined $minx || $minx > $pt->[0]; + $maxx = $pt->[0] if !defined $maxx || $maxx < $pt->[0]; + $miny = $pt->[1] if !defined $miny || $miny > $pt->[1]; + $maxy = $pt->[1] if !defined $maxy || $maxy < $pt->[1]; +} + +my (%count, %inf); +for my $x ($minx .. $maxx) { +for my $y ($miny .. $maxy) { + my ($minpt, $mindist); + for my $i (0 .. $#pts) { + my $pt = $pts[$i]; + my $dist = abs($x-$pt->[0]) + abs($y-$pt->[1]); + if (!defined $mindist || $mindist > $dist) { + $minpt = $i; + $mindist = $dist; + } elsif (defined $mindist && $mindist == $dist) { + $minpt = undef; + } + } + next if !defined $minpt; + say "$x,$y closest to $minpt at $mindist"; + if ($y == $miny || $y == $maxy || $x == $minx || $x == $maxx) { + $inf{$minpt}++; + say "$minpt is infinite"; + } else { + $count{$minpt}++; + } +} } + +my $maxarea; +for my $i (0 .. $#pts) { + next if $inf{$i}; + $maxarea = $count{$i} if !$maxarea || $maxarea < $count{$i}; +} + +say $maxarea; + + + + diff --git a/2018/12.pl b/2018/12.pl new file mode 100755 index 0000000..dac4857 --- /dev/null +++ b/2018/12.pl @@ -0,0 +1,27 @@ +#!/usr/bin/perl -w + +use v5.30; +use strict; + +my @pts = map { [ /(\d+)/g ] } <>; + +my ($minx, $miny, $maxx, $maxy); +for my $pt (@pts) { + $minx = $pt->[0] if !defined $minx || $minx > $pt->[0]; + $maxx = $pt->[0] if !defined $maxx || $maxx < $pt->[0]; + $miny = $pt->[1] if !defined $miny || $miny > $pt->[1]; + $maxy = $pt->[1] if !defined $maxy || $maxy < $pt->[1]; +} + +my $count; +for my $x ($minx .. $maxx) { +for my $y ($miny .. $maxy) { + my $dist; + for my $i (0 .. $#pts) { + my $pt = $pts[$i]; + $dist += abs($x-$pt->[0]) + abs($y-$pt->[1]); + } + $count++ if $dist < 10000; +} } + +say $count; diff --git a/2018/13.pl b/2018/13.pl new file mode 100755 index 0000000..5e1e161 --- /dev/null +++ b/2018/13.pl @@ -0,0 +1,27 @@ +#!/usr/bin/perl -w + +use v5.30; +use strict; + +my %prereqs; +my %steps; +while (<>) { + my ($src, $dst) = /(\w) must be.* (\w) can/; + $prereqs{$dst}->{$src} = 1; + $steps{$src} = 1; + $steps{$dst} = 1; +} + +my $res = ''; +while (%steps) { + my @avail = sort grep { keys %{ $prereqs{$_} } == 0 } keys %steps; + my $finished = $avail[0]; + $res .= $finished; + delete $steps{$finished}; + for my $p (keys %prereqs) { + delete $prereqs{$p}->{$finished}; + } +} + +say $res; + diff --git a/2018/14.pl b/2018/14.pl new file mode 100755 index 0000000..41f45db --- /dev/null +++ b/2018/14.pl @@ -0,0 +1,29 @@ +#!/usr/bin/perl -w + +use v5.30; +use strict; + +my %prereqs; +my %steps; +while (<>) { + my ($src, $dst) = /(\w) must be.* (\w) can/; + $prereqs{$dst}->{$src} = 1; + $steps{$src} = ord($src)-ord('A')+61; + $steps{$dst} = ord($dst)-ord('A')+61; +} + +my $time = 0; +while (%steps) { + $time++; + my @avail = sort grep { keys %{ $prereqs{$_} } == 0 } keys %steps; + for my $step (splice @avail, 0, 5) { + next if --$steps{$step} > 0; + delete $steps{$step}; + for my $p (keys %prereqs) { + delete $prereqs{$p}->{$step}; + } + } +} + +say $time; + diff --git a/2018/15.pl b/2018/15.pl new file mode 100755 index 0000000..c606505 --- /dev/null +++ b/2018/15.pl @@ -0,0 +1,25 @@ +#!/usr/bin/perl -w + +use v5.30; +use strict; + +my @tree = split /\s+/, <>; + +use List::Util qw(sum); + +my $metasum = 0; +sub walk { + my $subnodes = shift @tree; + my $metadata = shift @tree; + say "walk $subnodes $metadata"; + while ($subnodes--) { + walk(); + } + while ($metadata--) { + $metasum += shift @tree; + } +} +walk(); +say $metasum; + + diff --git a/2018/16.pl b/2018/16.pl new file mode 100755 index 0000000..ab794e2 --- /dev/null +++ b/2018/16.pl @@ -0,0 +1,35 @@ +#!/usr/bin/perl -w + +use v5.30; +use strict; + +my @tree = split /\s+/, <>; + +use List::Util qw(sum); + +sub walk { + my $subnodes = shift @tree; + my $metadata = shift @tree; + my $sum = 0; + say "walk $subnodes $metadata"; + my $sn1 = $subnodes; + my @subvals; + while ($sn1--) { + push @subvals, walk(); + } + if ($subnodes) { + while ($metadata--) { + my $id = shift @tree; + $id--; + $sum += $subvals[$id] + if $id < @subvals; + } + } else { + while ($metadata--) { + $sum += shift @tree; + } + } + say "returning $sum"; + $sum; +} +say walk(); diff --git a/2018/17.pl b/2018/17.pl new file mode 100755 index 0000000..f278359 --- /dev/null +++ b/2018/17.pl @@ -0,0 +1,33 @@ +#!/usr/bin/perl -w + +use v5.30; +use strict; + +my ($players, $last) = @ARGV; + +my @l = (0); +my $cur = 0; + +my %score; +for (1 .. $last) { + my $player = $_ % $players; + if ($_ % 23 == 0) { + $score{$player} += $_; + $cur -= 7; + $cur += @l if $cur < 0; + my ($val) = splice @l, $cur, 1; + $score{$player} += $val; + } else { + my $dst = @l > 1 ? ($cur + 2) % @l : $cur + 1; + $dst = @l if $dst == 0; + splice @l, $dst, 0, $_; + $cur = $dst; + } + say $_ if $_ % 100000 == 0; + # say join(' ', $cur, @l); +} + +use List::Util qw(max); +say max values %score; + + diff --git a/2018/18.pl b/2018/18.pl new file mode 100755 index 0000000..e7c9e12 --- /dev/null +++ b/2018/18.pl @@ -0,0 +1,38 @@ +#!/usr/bin/perl -w + +use v5.30; +use strict; + +my ($players, $last) = @ARGV; + +my %prev = ( 0 => 0 ); +my %next = ( 0 => 0 ); +my $cur = 0; + +my %score; +for (1 .. $last) { + my $player = $_ % $players; + if ($_ % 23 == 0) { + $score{$player} += $_; + $cur = $prev{$cur} for 1 .. 7; + $score{$player} += $cur; + $next{$prev{$cur}} = $next{$cur}; + $prev{$next{$cur}} = $prev{$cur}; + $cur = $next{$cur}; + } else { + $cur = $next{$cur}; + my $n = $next{$cur}; + $next{$cur} = $_; + $prev{$_} = $cur; + $prev{$n} = $_; + $next{$_} = $n; + $cur = $_; + } + say $_ if $_ % 100000 == 0; + # say join(' ', $cur, @l); +} + +use List::Util qw(max); +say max values %score; + + diff --git a/2018/19.pl b/2018/19.pl new file mode 100755 index 0000000..6233d54 --- /dev/null +++ b/2018/19.pl @@ -0,0 +1,48 @@ +#!/usr/bin/perl -w + +use v5.30; +use strict; + +my @pts; +my @vel; +while (<>) { + my ($x, $y, $dx, $dy) = /(-?\d+)/g; + push @pts, [ $x, $y ]; + push @vel, [ $dx, $dy ]; +} + +$; = ','; +my $printed; + +while (1) { + my %map; + my ($minx, $miny, $maxx, $maxy); + for my $i (0 .. $#pts) { + my $pt = $pts[$i]; + my $ve = $vel[$i]; + $pt->[$_] += $ve->[$_] for 0 .. 1; + $maxx = $pt->[0] if !defined $maxx || $maxx < $pt->[0]; + $maxy = $pt->[1] if !defined $maxy || $maxy < $pt->[1]; + $minx = $pt->[0] if !defined $minx || $minx > $pt->[0]; + $miny = $pt->[1] if !defined $miny || $miny > $pt->[1]; + $map{$pt->[0],$pt->[1]}++; + } + my $dim = $maxx-$minx + $maxy-$miny; + if ($dim < 200) { + for my $y ($miny .. $maxy) { + for my $x ($minx .. $maxx) { + print $map{$x,$y} ? '#' : '.'; + } + print "\n"; + } + $printed = 1; + } elsif ($printed) { + last; + } + say "dim=$dim\n"; +} + + + + + diff --git a/2018/20.pl b/2018/20.pl new file mode 100755 index 0000000..1b5e0d9 --- /dev/null +++ b/2018/20.pl @@ -0,0 +1,51 @@ +#!/usr/bin/perl -w + +use v5.30; +use strict; + +my @pts; +my @vel; +while (<>) { + my ($x, $y, $dx, $dy) = /(-?\d+)/g; + push @pts, [ $x, $y ]; + push @vel, [ $dx, $dy ]; +} + +$; = ','; +my $printed; +my $count; + +while (1) { + my %map; + my ($minx, $miny, $maxx, $maxy); + for my $i (0 .. $#pts) { + my $pt = $pts[$i]; + my $ve = $vel[$i]; + $pt->[$_] += $ve->[$_] for 0 .. 1; + $maxx = $pt->[0] if !defined $maxx || $maxx < $pt->[0]; + $maxy = $pt->[1] if !defined $maxy || $maxy < $pt->[1]; + $minx = $pt->[0] if !defined $minx || $minx > $pt->[0]; + $miny = $pt->[1] if !defined $miny || $miny > $pt->[1]; + $map{$pt->[0],$pt->[1]}++; + } + $count++; + my $dim = $maxx-$minx + $maxy-$miny; + if ($dim < 150) { + say "count=$count :"; + for my $y ($miny .. $maxy) { + for my $x ($minx .. $maxx) { + print $map{$x,$y} ? '#' : '.'; + } + print "\n"; + } + $printed = 1; + } elsif ($printed) { + last; + } + say "dim=$dim\n"; +} + + + + + diff --git a/2018/21.pl b/2018/21.pl new file mode 100755 index 0000000..631f2f8 --- /dev/null +++ b/2018/21.pl @@ -0,0 +1,46 @@ +#!/usr/bin/perl -w + +use v5.30; +use strict; + +my $serial = shift @ARGV; + +my %cache; +sub power_at { + my ($x, $y) = @_; + return $cache{$x,$y} if defined $cache{$x,$y}; + + my $rack_id = $x + 10; + my $power = ($rack_id * $y + $serial) * $rack_id; + $power = "000" . $power; + $power =~ s/.*(.)..\z/$1/; + $power -= 5; + return $cache{$x,$y} = $power; +} + +my ($maxx, $maxy, $maxpwr); +for my $x (1 .. 300) { + for my $y (1 .. 300) { + my $sum; + for my $dx (0 .. 2) { + next if $x + $dx > 300; + for my $dy (0 .. 2) { + next if $y + $dy > 300; + $sum += power_at($x+$dx, $y+$dy); + } + } + if (!defined $maxpwr || $sum > $maxpwr) { + $maxpwr = $sum; + $maxx = $x; + $maxy = $y; + } + } +} + +say power_at(33,45); +say "$maxx,$maxy = $maxpwr"; + + + + + diff --git a/2018/22.pl b/2018/22.pl new file mode 100755 index 0000000..ba59374 --- /dev/null +++ b/2018/22.pl @@ -0,0 +1,68 @@ +#!/usr/bin/perl -w + +use v5.30; +use strict; + +my $serial = shift @ARGV; + +my %cache; +sub power_at { + my ($x, $y) = @_; + return $cache{$x,$y} if defined $cache{$x,$y}; + + my $rack_id = $x + 10; + my $power = ($rack_id * $y + $serial) * $rack_id; + $power = "000" . $power; + $power =~ s/.*(.)..\z/$1/; + $power -= 5; + return $cache{$x,$y} = $power; +} + +my %sq_cache; +my ($maxx, $maxy, $maxsize, $maxpwr); +sub square_at { + my ($x, $y, $sizex, $sizey) = @_; + + return $sq_cache{$x,$y,$sizex,$sizey} + if defined $sq_cache{$x,$y,$sizex,$sizey}; + + my $sum; + if ($sizex == 1 && $sizey == 1) { + $sum = power_at($x, $y); + } elsif ($sizex == 1) { + $sum = square_at($x, $y, $sizex, $sizey-1) + + power_at($x, $y+$sizey-1); + } elsif ($sizey == 1) { + $sum = square_at($x, $y, $sizex-1, $sizey) + + power_at($x+$sizex-1, $y); + } else { + $sum = square_at($x, $y, $sizex-1, $sizey-1) + + square_at($x+$sizex-1, $y, 1, $sizey-1) + + square_at($x, $y+$sizey-1, $sizex-1, 1) + + power_at($x+$sizex-1, $y+$sizey-1); + } + if ($sizex == $sizey && (!defined $maxpwr || $sum > $maxpwr)) { + $maxpwr = $sum; + $maxx = $x; + $maxy = $y; + $maxsize = $sizex; + } + $sq_cache{$x,$y,$sizex,$sizey} = $sum; +} + +for my $size (1 .. 300) { + for my $x (1 .. 301-$size) { + for my $y (1 .. 301-$size) { + my $sz = square_at($x, $y, $size, $size); + # say "$x,$y,$size = $sz"; + } + } + say "size $size, $maxx,$maxy,$maxsize = $maxpwr"; +} + +say "$maxx,$maxy,$maxsize = $maxpwr"; + + + + + diff --git a/2018/23.pl b/2018/23.pl new file mode 100755 index 0000000..e074064 --- /dev/null +++ b/2018/23.pl @@ -0,0 +1,44 @@ +#!/usr/bin/perl -w + +use v5.30; +use strict; + +chomp (my $state = <>); +$state =~ s/.*: //; + +scalar <>; + +my %rules; +while (<>) { + chomp; + my ($src, $dst) = split / => /; + $rules{$src} = $dst; +} + +my $off = 0; +for (1 .. 20) { + if ($state !~ /^\.\.\.\./) { + $state = '....' . $state; + $off -= 4; + say "adding 4"; + } + $state = $state . '....' if $state !~ /\.\.\.\.$/; + + my $nstate = $state; + $nstate =~ y/#/./; + + for my $p (2 .. length($state)-3) { + my $src = substr($state, $p-2, 5); + # die "no rule for $src" if !exists $rules{$src}; + substr($nstate, $p, 1) = $rules{$src} if defined $rules{$src}; + } + $state = $nstate; + say $state; +} + +my $sum; +while ($state =~ /#/g) { + say "at ", pos($state) + $off - 1; + $sum += pos($state) + $off - 1; +} +say $sum; diff --git a/2018/24.pl b/2018/24.pl new file mode 100755 index 0000000..697a587 --- /dev/null +++ b/2018/24.pl @@ -0,0 +1,59 @@ +#!/usr/bin/perl -w + +use v5.30; +use strict; + +chomp (my $state = <>); +$state =~ s/.*: //; + +scalar <>; + +my %rules; +while (<>) { + chomp; + my ($src, $dst) = split / => /; + $rules{$src} = $dst; +} + +my $off = 0; +my %seen; +my $gen = 0; +while (1) { + $gen++; + if ($state !~ /^\.\.\.\./) { + $state = '....' . $state; + $off -= 4; + } + $state = $state . '....' if $state !~ /\.\.\.\.$/; + while ($state =~ /^\.\.\.\.\./) { + $state =~ s/^.//; + $off++; + } + while ($state =~ /\.\.\.\.\.$/) { + $state =~ s/.$//; + } + + my $nstate = $state; + $nstate =~ y/#/./; + + for my $p (2 .. length($state)-3) { + my $src = substr($state, $p-2, 5); + # die "no rule for $src" if !exists $rules{$src}; + substr($nstate, $p, 1) = $rules{$src} if defined $rules{$src}; + } + $state = $nstate; + last if ($seen{$state}); + $seen{$state} = [ $gen, $off ]; + say $state; +} + +say "state $gen off $off"; +say $state; +say "is equal to ", $seen{$state}[0], ' ', $seen{$state}[1]; + +$off += (50000000000 - $gen) * ($off - $seen{$state}[1]); +my $sum; +while ($state =~ /#/g) { + $sum += pos($state) + $off - 1; +} +say $sum; diff --git a/2018/25.pl b/2018/25.pl new file mode 100755 index 0000000..57f36a1 --- /dev/null +++ b/2018/25.pl @@ -0,0 +1,72 @@ +#!/usr/bin/perl -w + +use v5.30; +use strict; + +$; = ','; +my @map = map { chomp; [ split // ] } <>; +my $xmax = $#{ $map[0] }; +my $ymax = $#map; + +my @carts; +for my $y (0 .. $ymax) { + for my $x (0 .. $xmax) { + my $p = $map[$y][$x]; + if ($p eq '^') { + $map[$y][$x] = '|'; + push @carts, [ $x, $y, 0, 0 ]; + } + if ($p eq '>') { + $map[$y][$x] = '-'; + push @carts, [ $x, $y, 1, 0 ]; + } + if ($p eq 'v') { + $map[$y][$x] = '|'; + push @carts, [ $x, $y, 2, 0 ]; + } + if ($p eq '<') { + $map[$y][$x] = '-'; + push @carts, [ $x, $y, 3, 0 ]; + } + } +} + +my %cartpos; +for my $c (@carts) { + my ($x, $y) = @$c; + $cartpos{$x,$y} = 1; +} +while (1) { + for my $c (@carts) { + my ($x, $y, $dir, $state) = @$c; + my $m = $map[$y][$x]; + if ($m eq '/') { + $dir =~ y/0123/1032/; + } elsif ($m eq '\\') { + $dir =~ y/0123/3210/; + } elsif ($m eq '+') { + if ($state == 0) { + $dir =~ y/0123/3012/; + } elsif ($state == 2) { + $dir =~ y/0123/1230/; + } + $state = 0 if ++$state > 2; + } + delete $cartpos{$x,$y}; + $y-- if $dir == 0; + $x++ if $dir == 1; + $y++ if $dir == 2; + $x-- if $dir == 3; + if ($cartpos{$x,$y}++) { + say "$x,$y"; + exit 0; + } + $c->[0] = $x; + $c->[1] = $y; + $c->[2] = $dir; + $c->[3] = $state; + } + @carts = sort { $a->[1] == $b->[1] + ? $a->[0] <=> $b->[0] + : $a->[1] <=> $b->[1] } @carts; +} diff --git a/2018/26.pl b/2018/26.pl new file mode 100755 index 0000000..e9cfa60 --- /dev/null +++ b/2018/26.pl @@ -0,0 +1,82 @@ +#!/usr/bin/perl -w + +use v5.30; +use strict; + +$; = ','; +my @map = map { chomp; [ split // ] } <>; +my $xmax = $#{ $map[0] }; +my $ymax = $#map; + +my @carts; +for my $y (0 .. $ymax) { + for my $x (0 .. $xmax) { + my $p = $map[$y][$x]; + if ($p eq '^') { + $map[$y][$x] = '|'; + push @carts, [ $x, $y, 0, 0 ]; + } + if ($p eq '>') { + $map[$y][$x] = '-'; + push @carts, [ $x, $y, 1, 0 ]; + } + if ($p eq 'v') { + $map[$y][$x] = '|'; + push @carts, [ $x, $y, 2, 0 ]; + } + if ($p eq '<') { + $map[$y][$x] = '-'; + push @carts, [ $x, $y, 3, 0 ]; + } + } +} + +my %cartpos; +for my $i (0 .. $#carts) { + my $c = $carts[$i]; + my ($x, $y) = @$c; + $cartpos{$x,$y} = $i; +} +while (1) { + for my $i (0 .. $#carts) { + my $c = $carts[$i]; + next if $c->[4]; + my ($x, $y, $dir, $state) = @$c; + my $m = $map[$y][$x]; + if ($m eq '/') { + $dir =~ y/0123/1032/; + } elsif ($m eq '\\') { + $dir =~ y/0123/3210/; + } elsif ($m eq '+') { + if ($state == 0) { + $dir =~ y/0123/3012/; + } elsif ($state == 2) { + $dir =~ y/0123/1230/; + } + $state = 0 if ++$state > 2; + } + delete $cartpos{$x,$y}; + $y-- if $dir == 0; + $x++ if $dir == 1; + $y++ if $dir == 2; + $x-- if $dir == 3; + if (defined $cartpos{$x,$y}) { + $c->[4] = 1; + $carts[$cartpos{$x,$y}]->[4] = 1; + delete $cartpos{$x,$y}; + } else { + $cartpos{$x,$y} = $i; + } + $c->[0] = $x; + $c->[1] = $y; + $c->[2] = $dir; + $c->[3] = $state; + } + @carts = sort { $a->[1] == $b->[1] + ? $a->[0] <=> $b->[0] + : $a->[1] <=> $b->[1] } grep { !defined $_->[4] } @carts; + if (@carts == 1) { + say $carts[0][0], ',', $carts[0][1]; + last; + } +} diff --git a/2018/27.pl b/2018/27.pl new file mode 100755 index 0000000..5ef9f36 --- /dev/null +++ b/2018/27.pl @@ -0,0 +1,23 @@ +#!/usr/bin/perl -w + +use v5.30; +use strict; + +my $iters = shift @ARGV; +$iters += 10; + +my @r = qw(3 7); +my @p = qw(0 1); + +while (@r < $iters) { + my $n = $r[$p[0]] + $r[$p[1]]; + push @r, split //, $n; + for (0 .. 1) { + $p[$_] += 1 + $r[$p[$_]]; + $p[$_] -= @r while $p[$_] >= @r; + } + # say join ' ', @p, @r; +} + +say join('', @r[-10 .. -1]) + diff --git a/2018/28.pl b/2018/28.pl new file mode 100755 index 0000000..d60cd89 --- /dev/null +++ b/2018/28.pl @@ -0,0 +1,27 @@ +#!/usr/bin/perl -w + +use v5.20; +use strict; + +my $input = shift @ARGV; + +my $r = '37'; +my @p = qw(0 1); + +my $l = length $input; +my $lr = length $r; +while (1) { + my @n = (substr($r, $p[0], 1), substr($r, $p[1], 1)); + $r .= $n[0]+$n[1]; + $lr = length $r; + for (0 .. 1) { + $p[$_] += 1 + $n[$_]; + $p[$_] -= $lr while $p[$_] >= $lr; + } + next if $lr < $l; + last if substr($r, -$l) eq $input; + last if substr($r, -$l-1, -1) eq $input; +} + +$r =~ s/$input.*//; +say length $r; diff --git a/2018/29.pl b/2018/29.pl new file mode 100755 index 0000000..6c30654 --- /dev/null +++ b/2018/29.pl @@ -0,0 +1,187 @@ +#!/usr/bin/perl -w + +use v5.36; +use strict; +use experimental 'multidimensional'; + +my @map = map { chomp; [ split // ] } <>; +my $xmax = $#{ $map[0] }; +my $ymax = $#map; + +my @units; +for my $y (0 .. $ymax) { + for my $x (0 .. $xmax) { + if ($map[$y][$x] eq 'G') { + push @units, [$x, $y, 'G', 200]; + } elsif ($map[$y][$x] eq 'E') { + push @units, [$x, $y, 'E', 200]; + } + } +} + +sub enemy_of($unit) { $unit->[2] eq 'G' ? 'E' : 'G' } + +my @neighbors = ([0, -1], [-1, 0], [1, 0], [0, 1]); + +sub reading_sort { + return sort { $a->[1] == $b->[1] ? $a->[0] <=> $b->[0] : $a->[1] <=> $b->[1] } @_; +} + +sub print_map { + for my $y (0 .. $ymax) { + for my $x (0 .. $xmax) { + print $map[$y][$x]; + } + print "\n"; + } + for my $unit (grep { $_->[3] } reading_sort(@units)) { + say "$unit->[2] at $unit->[0],$unit->[1] ($unit->[3])" + } +} + +sub neigh_squares($unit, $type) { + my @rv; + for my $n (@neighbors) { + my ($dx, $dy) = @$n; + $dx += $unit->[0]; + $dy += $unit->[1]; + if ($map[$dy][$dx] eq $type) { + push @rv, [ $dx, $dy ]; + } + } + return @rv; +} + +sub enemy_within_range($unit) { + return neigh_squares($unit, enemy_of($unit)); +} + +sub loc2unit($loc) { + for my $unit (@units) { + return $unit + if $unit->[0] == $loc->[0] && $unit->[1] == $loc->[1]; + } + die "Can't locate unit at ", join(',', @$loc); +} + +sub attack($unit, $enemies) { + say "Attacking unit: ", join(',', @$unit); + my $min_hp; + my @min_hp; + for my $enemy (@$enemies) { + say "Enemy: ", join(',', @$enemy); + my $enemy_unit = loc2unit($enemy); + if (!defined $min_hp || $min_hp > $enemy_unit->[3]) { + $min_hp = $enemy_unit->[3]; + @min_hp = (); + } + if ($min_hp == $enemy_unit->[3]) { + push @min_hp, $enemy_unit; + } + } + + @min_hp = reading_sort(@min_hp); + my $enemy = shift @min_hp; + say "attacking"; + $enemy->[3] -= 3; + if ($enemy->[3] <= 0) { + $enemy->[3] = 0; + $map[$enemy->[1]][$enemy->[0]] = '.'; + } + $enemy->[3] = 0 if $enemy->[3] < 0; + say "attacked ", join(',', @$enemy); +} + +sub dump_path($path) { + join(' ', map { "[$_->[0],$_->[1]]" } @$path); +} + +sub move($unit) { + my %target_sq; + for my $enemy (grep { $_->[2] ne $unit->[2] } @units) { + for my $sq (neigh_squares($enemy, '.')) { + if (!$target_sq{$sq->[0],$sq->[1]}++) { + # say "target square $sq->[0],$sq->[1]"; + } + } + } + + my @q = [ [ $unit->[0], $unit->[1] ] ]; + my %visited; + my $found_at_dist; + my @reachable; + while (@q) { + my $path = shift @q; + # say "walking path ", dump_path($path); + last if $found_at_dist && @$path > $found_at_dist; + for my $sq (neigh_squares($path->[-1], '.')) { + next if $visited{$sq->[0],$sq->[1]}++; + + if ($target_sq{$sq->[0],$sq->[1]}) { + $found_at_dist //= @$path; + my $path1 = [ @$path, [ @$sq ] ]; + # say "Found square $sq->[0],$sq->[1] through ", + # dump_path($path1); + push @reachable, [ @$sq, @{ $path1->[1] } ]; + } else { + push @q, [ @$path, [ @$sq ] ]; + } + } + } + + if (!@reachable) { + # say "no reachable squares"; + return; + } + + @reachable = reading_sort(@reachable); + my $target = $reachable[0]; + # say "moving to $target->[0],$target->[1] via $target->[2],$target->[3]"; + $map[$unit->[1]][$unit->[0]] = '.'; + $map[$unit->[1] = $target->[3]][$unit->[0] = $target->[2]] = $unit->[2]; +} + +sub unit_round($unit) { + return if !$unit->[3]; # are we alive? + # say "\nunit_round ", join(',', @$unit); + + my @enemies = enemy_within_range($unit); + if (!@enemies) { + move($unit); + @enemies = enemy_within_range($unit); + } + if (@enemies) { + attack($unit, \@enemies); + } +} + +my $round = 0; +my %total_hp; +ROUND: +while (1) { + say "After $round rounds:"; + print_map; + $round++; + @units = reading_sort(grep { $_->[3] } @units); + + for my $unit (@units) { + next if !$unit->[3]; + %total_hp = (); + for my $u (@units) { + $total_hp{$u->[2]} += $u->[3] + if $u->[3]; + } + if (keys %total_hp < 2) { + $round--; + last ROUND; + } + unit_round($unit); + } + +} + +say "After $round rounds:"; +print_map; + +say "ended after round $round with hp ", join('=>', %total_hp); +say $round * (%total_hp)[1]; diff --git a/2018/30.pl b/2018/30.pl new file mode 100755 index 0000000..61e60e5 --- /dev/null +++ b/2018/30.pl @@ -0,0 +1,208 @@ +#!/usr/bin/perl -w + +use v5.36; +use strict; +use experimental 'multidimensional'; + +my @input = <>; + +my (@map, $xmax, $ymax, @units); + +sub init_map { + @map = map { chomp; [ split // ] } @input; + $xmax = $#{ $map[0] }; + $ymax = $#map; + + @units = (); + for my $y (0 .. $ymax) { + for my $x (0 .. $xmax) { + if ($map[$y][$x] eq 'G') { + push @units, [$x, $y, 'G', 200]; + } elsif ($map[$y][$x] eq 'E') { + push @units, [$x, $y, 'E', 200]; + } + } + } +} + +init_map; + +sub enemy_of($unit) { $unit->[2] eq 'G' ? 'E' : 'G' } + +my @neighbors = ([0, -1], [-1, 0], [1, 0], [0, 1]); + +sub reading_sort { + return sort { $a->[1] == $b->[1] ? $a->[0] <=> $b->[0] : $a->[1] <=> $b->[1] } @_; +} + +sub print_map { + for my $y (0 .. $ymax) { + for my $x (0 .. $xmax) { + print $map[$y][$x]; + } + print "\n"; + } + for my $unit (grep { $_->[3] } reading_sort(@units)) { + say "$unit->[2] at $unit->[0],$unit->[1] ($unit->[3])" + } +} + +sub neigh_squares($unit, $type) { + my @rv; + for my $n (@neighbors) { + my ($dx, $dy) = @$n; + $dx += $unit->[0]; + $dy += $unit->[1]; + if ($map[$dy][$dx] eq $type) { + push @rv, [ $dx, $dy ]; + } + } + return @rv; +} + +sub enemy_within_range($unit) { + return neigh_squares($unit, enemy_of($unit)); +} + +sub loc2unit($loc) { + for my $unit (@units) { + return $unit + if $unit->[0] == $loc->[0] && $unit->[1] == $loc->[1]; + } + die "Can't locate unit at ", join(',', @$loc); +} + +sub attack($unit, $enemies, $power) { + say "Attacking unit: ", join(',', @$unit); + my $min_hp; + my @min_hp; + for my $enemy (@$enemies) { + say "Enemy: ", join(',', @$enemy); + my $enemy_unit = loc2unit($enemy); + if (!defined $min_hp || $min_hp > $enemy_unit->[3]) { + $min_hp = $enemy_unit->[3]; + @min_hp = (); + } + if ($min_hp == $enemy_unit->[3]) { + push @min_hp, $enemy_unit; + } + } + + @min_hp = reading_sort(@min_hp); + my $enemy = shift @min_hp; + say "attacking"; + $enemy->[3] -= $power; + if ($enemy->[3] <= 0) { + die if $enemy->[2] eq 'E'; + $enemy->[3] = 0; + $map[$enemy->[1]][$enemy->[0]] = '.'; + } + $enemy->[3] = 0 if $enemy->[3] < 0; + say "attacked ", join(',', @$enemy); +} + +sub dump_path($path) { + join(' ', map { "[$_->[0],$_->[1]]" } @$path); +} + +sub move($unit) { + my %target_sq; + for my $enemy (grep { $_->[2] ne $unit->[2] } @units) { + for my $sq (neigh_squares($enemy, '.')) { + if (!$target_sq{$sq->[0],$sq->[1]}++) { + # say "target square $sq->[0],$sq->[1]"; + } + } + } + + my @q = [ [ $unit->[0], $unit->[1] ] ]; + my %visited; + my $found_at_dist; + my @reachable; + while (@q) { + my $path = shift @q; + # say "walking path ", dump_path($path); + last if $found_at_dist && @$path > $found_at_dist; + for my $sq (neigh_squares($path->[-1], '.')) { + next if $visited{$sq->[0],$sq->[1]}++; + + if ($target_sq{$sq->[0],$sq->[1]}) { + $found_at_dist //= @$path; + my $path1 = [ @$path, [ @$sq ] ]; + # say "Found square $sq->[0],$sq->[1] through ", + # dump_path($path1); + push @reachable, [ @$sq, @{ $path1->[1] } ]; + } else { + push @q, [ @$path, [ @$sq ] ]; + } + } + } + + if (!@reachable) { + # say "no reachable squares"; + return; + } + + @reachable = reading_sort(@reachable); + my $target = $reachable[0]; + # say "moving to $target->[0],$target->[1] via $target->[2],$target->[3]"; + $map[$unit->[1]][$unit->[0]] = '.'; + $map[$unit->[1] = $target->[3]][$unit->[0] = $target->[2]] = $unit->[2]; +} + +sub unit_round($unit, $attack) { + return if !$unit->[3]; # are we alive? + # say "\nunit_round ", join(',', @$unit); + + my @enemies = enemy_within_range($unit); + if (!@enemies) { + move($unit); + @enemies = enemy_within_range($unit); + } + if (@enemies) { + attack($unit, \@enemies, $attack); + } +} + +sub battle($elf_hp) { + my $round = 0; + init_map; + say "elf_hp: $elf_hp ====================================="; + my %total_hp; + ROUND: + while (1) { + say "After $round rounds:"; + print_map; + $round++; + @units = reading_sort(grep { $_->[3] } @units); + + for my $unit (@units) { + next if !$unit->[3]; + %total_hp = (); + for my $u (@units) { + $total_hp{$u->[2]} += $u->[3] + if $u->[3]; + } + if (keys %total_hp < 2) { + $round--; + last ROUND; + } + eval { unit_round($unit, $unit->[2] eq 'E' ? $elf_hp : 3); }; + return 0 if $@; + } + + } + say "After $round rounds with hp $elf_hp:"; + print_map; + + say "elf_hp $elf_hp ended after round $round with hp ", join('=>', %total_hp); + say $round * (%total_hp)[1]; + return 1; +} + +my $elf_hp = 4; +$elf_hp++ while !battle($elf_hp); + +# There is a bug out there - on the real puzzle input it returned +# remaining hp lower by three, which means there had to be one less Goblin +# attack somewhere. diff --git a/2018/31.pl b/2018/31.pl new file mode 100755 index 0000000..86c46e4 --- /dev/null +++ b/2018/31.pl @@ -0,0 +1,55 @@ +#!/usr/bin/perl -w + +use v5.30; +use strict; + +local $/ = "\n\n"; + +my $total = 0; +while(<>) { + chomp; + last if !length; + + my @nums = /(\d+)/g; + my @before = @nums[0..3]; + my ($op, $a, $b, $c) = @nums[4..7]; + my @after = @nums[8..11]; + my $match = 0; + + # addr + $match++ if ($before[$a] + $before[$b] == $after[$c]); + # addi + $match++ if ($before[$a] + $b == $after[$c]); + # mulr + $match++ if ($before[$a] * $before[$b] == $after[$c]); + # muli + $match++ if ($before[$a] * $b == $after[$c]); + # bandr + $match++ if (($before[$a] & $before[$b]) == $after[$c]); + # bandi + $match++ if (($before[$a] & $b) == $after[$c]); + # borr + $match++ if (($before[$a] | $before[$b]) == $after[$c]); + # bori + $match++ if (($before[$a] | $b) == $after[$c]); + # setr + $match++ if ($before[$a] == $after[$c]); + # seti + $match++ if ($a == $after[$c]); + # gtir + $match++ if (($a > $before[$b] ? 1 : 0) == $after[$c]); + # gtri + $match++ if (($before[$a] > $b ? 1 : 0) == $after[$c]); + # gtrr + $match++ if (($before[$a] > $before[$b] ? 1 : 0) == $after[$c]); + # eqir + $match++ if (($a == $before[$b] ? 1 : 0) == $after[$c]); + # eqri + $match++ if (($before[$a] == $b ? 1 : 0) == $after[$c]); + # eqrr + $match++ if (($before[$a] == $before[$b] ? 1 : 0) == $after[$c]); + + $total++ if $match >= 3; +} + +say $total; diff --git a/2018/32.pl b/2018/32.pl new file mode 100755 index 0000000..6a1f2e4 --- /dev/null +++ b/2018/32.pl @@ -0,0 +1,127 @@ +#!/usr/bin/perl -w + +use v5.30; +use strict; + +local $/ = "\n\n"; + +my @is_op = (65535) x 16; + +my $total = 0; +while(<>) { + chomp; + last if !length; + + my @nums = /(\d+)/g; + my @before = @nums[0..3]; + my ($op, $a, $b, $c) = @nums[4..7]; + my @after = @nums[8..11]; + my $match = 0; + + print join(' ', @nums), "\n"; + # addr + $is_op[$op] &= ~(1 << 0) unless ($before[$a] + $before[$b] == $after[$c]); + # addi + $is_op[$op] &= ~(1 << 1) unless ($before[$a] + $b == $after[$c]); + # mulr + $is_op[$op] &= ~(1 << 2) unless ($before[$a] * $before[$b] == $after[$c]); + # muli + $is_op[$op] &= ~(1 << 3) unless ($before[$a] * $b == $after[$c]); + # bandr + $is_op[$op] &= ~(1 << 4) unless (($before[$a] & $before[$b]) == $after[$c]); + # bandi + $is_op[$op] &= ~(1 << 5) unless (($before[$a] & $b) == $after[$c]); + # borr + $is_op[$op] &= ~(1 << 6) unless (($before[$a] | $before[$b]) == $after[$c]); + # bori + $is_op[$op] &= ~(1 << 7) unless (($before[$a] | $b) == $after[$c]); + # setr + $is_op[$op] &= ~(1 << 8) unless ($before[$a] == $after[$c]); + # seti + $is_op[$op] &= ~(1 << 9) unless ($a == $after[$c]); + # gtir + $is_op[$op] &= ~(1 << 10) unless (($a > $before[$b] ? 1 : 0) == $after[$c]); + # gtri + $is_op[$op] &= ~(1 << 11) unless (($before[$a] > $b ? 1 : 0) == $after[$c]); + # gtrr + $is_op[$op] &= ~(1 << 12) unless (($before[$a] > $before[$b] ? 1 : 0) == $after[$c]); + # eqir + $is_op[$op] &= ~(1 << 13) unless (($a == $before[$b] ? 1 : 0) == $after[$c]); + # eqri + $is_op[$op] &= ~(1 << 14) unless (($before[$a] == $b ? 1 : 0) == $after[$c]); + # eqrr + $is_op[$op] &= ~(1 << 15) unless (($before[$a] == $before[$b] ? 1 : 0) == $after[$c]); + print join(' ', map { sprintf("%04x", $_) } @is_op), "\n"; +} + +my %is_2n = map { (1 << $_) => 1 } 0 .. 15; + +my %done_2n; +my $modified = 1; +while ($modified) { + say join(" ", map { sprintf("%04x", $_) } @is_op); + $modified = 0; + for my $try (0 .. 15) { + next if $done_2n{$try}; + next if !$is_2n{$is_op[$try]}; + print "Unique: $try: $is_op[$try]\n"; + $done_2n{$try} = 1; + $modified = 1; + for my $other (0 .. 15) { + next if $done_2n{$other}; + $is_op[$other] &= ~$is_op[$try]; + } + } +} + +my @op_trans; +for my $op (0 .. 15) { + for my $l (0 .. 15) { + next if (1 << $l) != $is_op[$op]; + print "$op => $l\n"; + $op_trans[$op] = $l; + } +} + +local $/ = "\n"; +my @regs = (0) x 4; +while (<>) { + my ($op, $a, $b, $c) = /(\d+)/g; + say "$op $a $b $c ", join(' ', @regs); + + # addr + $regs[$c] = $regs[$a] + $regs[$b] if $op_trans[$op] == 0; + # addi + $regs[$c] = $regs[$a] + $b if $op_trans[$op] == 1; + # mulr + $regs[$c] = $regs[$a] * $regs[$b] if $op_trans[$op] == 2; + # muli + $regs[$c] = $regs[$a] * $b if $op_trans[$op] == 3; + # bandr + $regs[$c] = ($regs[$a] & $regs[$b]) if $op_trans[$op] == 4; + # bandi + $regs[$c] = ($regs[$a] & $b) if $op_trans[$op] == 5; + # borr + $regs[$c] = ($regs[$a] | $regs[$b]) if $op_trans[$op] == 6; + # bori + $regs[$c] = ($regs[$a] | $b) if $op_trans[$op] == 7; + # setr + $regs[$c] = $regs[$a] if $op_trans[$op] == 8; + # seti + $regs[$c] = $a if $op_trans[$op] == 9; + # gtir + $regs[$c] = ($a > $regs[$b] ? 1 : 0) if $op_trans[$op] == 10; + # gtri + $regs[$c] = ($regs[$a] > $b ? 1 : 0) if $op_trans[$op] == 11; + # gtrr + $regs[$c] = ($regs[$a] > $regs[$b] ? 1 : 0) if $op_trans[$op] == 12; + # eqir + $regs[$c] = ($a == $regs[$b] ? 1 : 0) if $op_trans[$op] == 13; + # eqri + $regs[$c] = ($regs[$a] == $b ? 1 : 0) if $op_trans[$op] == 14; + # eqrr + $regs[$c] = ($regs[$a] == $regs[$b] ? 1 : 0) if $op_trans[$op] == 15; +} + +say $regs[0]; + diff --git a/2018/33.pl b/2018/33.pl new file mode 100755 index 0000000..60094a5 --- /dev/null +++ b/2018/33.pl @@ -0,0 +1,113 @@ +#!/usr/bin/perl -w + +use v5.30; +use strict; + +my %map; + +my ($ymin, $ymax, $xmin, $xmax); + +while (<>) { + chomp; + my ($c1n, $c1, $c2min, $c2max) = /\A(.)=(\d+), .=(\d+)\.\.(\d+)/; + + for my $c2 ($c2min .. $c2max) { + if ($c1n eq 'x') { + $map{$c1}{$c2} = '#'; + $ymin = $c2 if !defined $ymin || $ymin > $c2; + $ymax = $c2 if !defined $ymax || $ymax < $c2; + $xmin = $c1 if !defined $xmin || $xmin > $c1; + $xmax = $c1 if !defined $xmax || $xmax < $c1; + } else { + $map{$c2}{$c1} = '#'; + $ymin = $c1 if !defined $ymin || $ymin > $c1; + $ymax = $c1 if !defined $ymax || $ymax < $c1; + $xmin = $c2 if !defined $xmin || $xmin > $c2; + $xmax = $c2 if !defined $xmax || $xmax < $c2; + } + } +} +$xmin--; +$xmax++; + +say "y=$ymin .. $ymax"; + +my $iter = 0; +sub dump_map { + return if $iter++ % 1000; + my $total = 0; + for my $y (0 .. $ymax) { + for my $x ($xmin .. $xmax) { + print $map{$x}{$y} // ' '; + $total++ if defined $map{$x}{$y} + && $map{$x}{$y} =~ /[~0]/; + } + print "\n"; + } + say "total=$total"; + return $total; +} + +dump_map(); + +my $total = 0; + +sub explore { + my ($x, $y) = @_; + return 0 if $y > $ymax; + $map{$x}{$y} //= 0; + my $was_change; + while (1) { + $was_change = 0; + say "explore $x, $y"; + dump_map(); + my $xp = $x; + while ($map{$xp}{$y+1}) { + last if $map{$xp+1}{$y}; + $xp++; + $map{$xp}{$y} //= 0; + } + my $xm = $x; + while ($map{$xm}{$y+1}) { + last if $map{$xm-1}{$y}; + $xm--; + $map{$xm}{$y} //= 0; + } + + say "$xm .. $xp"; + if (!$map{$xp}{$y+1} && $y < $ymax) { + $map{$xp}{$y} //= 0; + if (!defined $map{$xp}{$y+1}) { + say "calling to $xp, $y+1"; + $was_change += explore($xp, $y+1); + } + } + + if (!$map{$xm}{$y+1} && $y < $ymax) { + $map{$xm}{$y} //= 0; + if (!defined $map{$xm}{$y+1}) { + say "calling to $xm, $y+1"; + $was_change += explore($xm, $y+1); + } + } + say "was_change = $was_change"; + + next if $was_change; + + if ($map{$xp+1}{$y} && $map{$xm-1}{$y}) { + for my $x0 ($xm .. $xp) { + $map{$x0}{$y} = '~'; + } + return 1; + } + last; + } + say "$x,$y returning $was_change"; + return $was_change; +} + +explore(500, $ymin); + +$iter = 0; +dump_map(); + diff --git a/2018/34.pl b/2018/34.pl new file mode 100755 index 0000000..264148e --- /dev/null +++ b/2018/34.pl @@ -0,0 +1,113 @@ +#!/usr/bin/perl -w + +use v5.30; +use strict; + +my %map; + +my ($ymin, $ymax, $xmin, $xmax); + +while (<>) { + chomp; + my ($c1n, $c1, $c2min, $c2max) = /\A(.)=(\d+), .=(\d+)\.\.(\d+)/; + + for my $c2 ($c2min .. $c2max) { + if ($c1n eq 'x') { + $map{$c1}{$c2} = '#'; + $ymin = $c2 if !defined $ymin || $ymin > $c2; + $ymax = $c2 if !defined $ymax || $ymax < $c2; + $xmin = $c1 if !defined $xmin || $xmin > $c1; + $xmax = $c1 if !defined $xmax || $xmax < $c1; + } else { + $map{$c2}{$c1} = '#'; + $ymin = $c1 if !defined $ymin || $ymin > $c1; + $ymax = $c1 if !defined $ymax || $ymax < $c1; + $xmin = $c2 if !defined $xmin || $xmin > $c2; + $xmax = $c2 if !defined $xmax || $xmax < $c2; + } + } +} +$xmin--; +$xmax++; + +say "y=$ymin .. $ymax"; + +my $iter = 0; +sub dump_map { + return if $iter++ % 1000; + my $total = 0; + for my $y (0 .. $ymax) { + for my $x ($xmin .. $xmax) { + print $map{$x}{$y} // ' '; + $total++ if defined $map{$x}{$y} + && $map{$x}{$y} =~ /[~]/; + } + print "\n"; + } + say "total=$total"; + return $total; +} + +dump_map(); + +my $total = 0; + +sub explore { + my ($x, $y) = @_; + return 0 if $y > $ymax; + $map{$x}{$y} //= 0; + my $was_change; + while (1) { + $was_change = 0; + say "explore $x, $y"; + dump_map(); + my $xp = $x; + while ($map{$xp}{$y+1}) { + last if $map{$xp+1}{$y}; + $xp++; + $map{$xp}{$y} //= 0; + } + my $xm = $x; + while ($map{$xm}{$y+1}) { + last if $map{$xm-1}{$y}; + $xm--; + $map{$xm}{$y} //= 0; + } + + say "$xm .. $xp"; + if (!$map{$xp}{$y+1} && $y < $ymax) { + $map{$xp}{$y} //= 0; + if (!defined $map{$xp}{$y+1}) { + say "calling to $xp, $y+1"; + $was_change += explore($xp, $y+1); + } + } + + if (!$map{$xm}{$y+1} && $y < $ymax) { + $map{$xm}{$y} //= 0; + if (!defined $map{$xm}{$y+1}) { + say "calling to $xm, $y+1"; + $was_change += explore($xm, $y+1); + } + } + say "was_change = $was_change"; + + next if $was_change; + + if ($map{$xp+1}{$y} && $map{$xm-1}{$y}) { + for my $x0 ($xm .. $xp) { + $map{$x0}{$y} = '~'; + } + return 1; + } + last; + } + say "$x,$y returning $was_change"; + return $was_change; +} + +explore(500, $ymin); + +$iter = 0; +dump_map(); + diff --git a/2018/35.pl b/2018/35.pl new file mode 100755 index 0000000..bf04ec7 --- /dev/null +++ b/2018/35.pl @@ -0,0 +1,47 @@ +#!/usr/bin/perl -w + +use v5.36; +use strict; +use experimental 'multidimensional'; + +my @map = map { chomp; [ split // ] } <>; + +my $rows = @map; +my $cols = @{ $map[0] }; + +my %total; +for (1..10) { + %total = (); + my @nmap; + for my $y (0 .. $rows-1) { + my @row; + for my $x (0 .. $cols-1) { + my %count = map { $_ => 0 } ('#', '|', '.'); + for my $neigh ([-1,-1], [0, -1], [1, -1], + [-1, 0], [1, 0], + [-1, 1], [0, 1], [1, 1]) { + my $nx = $x + $neigh->[0]; + my $ny = $y + $neigh->[1]; + next if $nx < 0 || $nx >= $cols + || $ny < 0 || $ny >= $cols; + $count{$map[$ny][$nx]}++; + } + my $self = $map[$y][$x]; + if ($self eq '.' && $count{'|'} >= 3) { + $self = '|'; + } elsif ($self eq '|' && $count{'#'} >= 3) { + $self = '#'; + } elsif ($self eq '#' && + ($count{'#'} == 0 || $count{'|'} == 0)) { + $self = '.'; + } + push @row, $self; + $total{$self}++; + } + push @nmap, \@row; + } + @map = @nmap; + say map { join('', @$_, "\n") } @map; +} + +say $total{"#"} * $total{'|'}; diff --git a/2018/36.pl b/2018/36.pl new file mode 100755 index 0000000..cf75ea0 --- /dev/null +++ b/2018/36.pl @@ -0,0 +1,59 @@ +#!/usr/bin/perl -w + +use v5.36; +use strict; +use experimental 'multidimensional'; + +my @map = map { chomp; [ split // ] } <>; + +my $rows = @map; +my $cols = @{ $map[0] }; +my $periods = 1000000000; + +my $gen = 0; +my %seen; +while ($gen++ < $periods) { + my %total; + my @nmap; + say "gen $gen"; + for my $y (0 .. $rows-1) { + my @row; + for my $x (0 .. $cols-1) { + my %count = map { $_ => 0 } ('#', '|', '.'); + for my $neigh ([-1,-1], [0, -1], [1, -1], + [-1, 0], [1, 0], + [-1, 1], [0, 1], [1, 1]) { + my $nx = $x + $neigh->[0]; + my $ny = $y + $neigh->[1]; + next if $nx < 0 || $nx >= $cols + || $ny < 0 || $ny >= $cols; + $count{$map[$ny][$nx]}++; + } + my $self = $map[$y][$x]; + if ($self eq '.' && $count{'|'} >= 3) { + $self = '|'; + } elsif ($self eq '|' && $count{'#'} >= 3) { + $self = '#'; + } elsif ($self eq '#' && + ($count{'#'} == 0 || $count{'|'} == 0)) { + $self = '.'; + } + push @row, $self; + $total{$self}++; + } + push @nmap, \@row; + } + @map = @nmap; + my $state = join('', map { join('', @$_, "\n") } @map); + + say $total{"#"} * $total{'|'}; + if (defined $seen{$state} && $gen < 500) { + say "at $gen: the same state seen at $seen{$state}"; + my $period = $gen - $seen{$state}; + say "period $period"; + $gen += $period * int(($periods-1-$gen)/$period); + say " => $gen"; + } + $seen{$state} = $gen; +} + diff --git a/2018/37.pl b/2018/37.pl new file mode 100755 index 0000000..1c334fa --- /dev/null +++ b/2018/37.pl @@ -0,0 +1,54 @@ +#!/usr/bin/perl -w + +use v5.30; +use strict; + +my @code; +my @regs = ((0) x 6); +my $ip_reg; + +while(<>) { + if (/\A#ip (\d+)/) { + $ip_reg = $1; + next; + } + chomp; + push @code, [ split /\s+/ ]; +} + +my $ip = 0; +while ($ip < @code) { + my ($op, $a, $b, $c) = @{ $code[$ip] }; + + $regs[$ip_reg] = $ip; + + if ($op eq 'addr') { + $regs[$c] = $regs[$a] + $regs[$b]; + } elsif ($op eq 'addi') { + $regs[$c] = $regs[$a] + $b; + } elsif ($op eq 'mulr') { + $regs[$c] = $regs[$a] * $regs[$b]; + } elsif ($op eq 'muli') { + $regs[$c] = $regs[$a] * $b; + } elsif ($op eq 'andr') { + $regs[$c] = $regs[$a] & $regs[$b]; + } elsif ($op eq 'andi') { + $regs[$c] = $regs[$a] & $b; + } elsif ($op eq 'orr') { + $regs[$c] = $regs[$a] | $regs[$b]; + } elsif ($op eq 'ori') { + $regs[$c] = $regs[$a] | $b; + } elsif ($op eq 'setr') { + $regs[$c] = $regs[$a]; + } elsif ($op eq 'seti') { + $regs[$c] = $a; + } elsif ($op eq 'gtrr') { + $regs[$c] = $regs[$a] > $regs[$b] ? 1 : 0; + } elsif ($op eq 'eqrr') { + $regs[$c] = $regs[$a] == $regs[$b] ? 1 : 0; + } + $ip = $regs[$ip_reg] + 1; +} + +say $regs[0]; + diff --git a/2018/38.pl b/2018/38.pl new file mode 100755 index 0000000..1e18937 --- /dev/null +++ b/2018/38.pl @@ -0,0 +1,60 @@ +#!/usr/bin/perl -w + +use v5.30; +use strict; + +my @code; +my @regs = (1, (0) x 5); +my $ip_reg; + +while() { + if (/\A#ip (\d+)/) { + $ip_reg = $1; + next; + } + chomp; + push @code, [ split /\s+/ ]; +} + +my $ip = 0; +while ($ip < @code) { + my ($op, $a, $b, $c) = @{ $code[$ip] }; + + $regs[$ip_reg] = $ip; + + if ($op eq 'addr') { + $regs[$c] = $regs[$a] + $regs[$b]; + } elsif ($op eq 'addi') { + $regs[$c] = $regs[$a] + $b; + } elsif ($op eq 'mulr') { + $regs[$c] = $regs[$a] * $regs[$b]; + } elsif ($op eq 'muli') { + $regs[$c] = $regs[$a] * $b; + } elsif ($op eq 'banr') { + $regs[$c] = $regs[$a] & $regs[$b]; + } elsif ($op eq 'bani') { + $regs[$c] = $regs[$a] & $b; + } elsif ($op eq 'borr') { + $regs[$c] = $regs[$a] | $regs[$b]; + } elsif ($op eq 'bori') { + $regs[$c] = $regs[$a] | $b; + } elsif ($op eq 'setr') { + $regs[$c] = $regs[$a]; + } elsif ($op eq 'seti') { + $regs[$c] = $a; + } elsif ($op eq 'gtrr') { + $regs[$c] = $regs[$a] > $regs[$b] ? 1 : 0; + } elsif ($op eq 'eqrr') { + $regs[$c] = $regs[$a] == $regs[$b] ? 1 : 0; + } elsif ($op eq 'nop') { + + } else { + die "Unknown op $ op at $ip"; + } + say join(' ', $ip, "\t", @{ $code[$ip] }, "\t", @regs); + # $regs[3] = $ARGV[0] if $ip == 35; + $ip = $regs[$ip_reg] + 1; +} + +say $regs[0]; + diff --git a/2018/39.pl b/2018/39.pl new file mode 100755 index 0000000..90db131 --- /dev/null +++ b/2018/39.pl @@ -0,0 +1,107 @@ +#!/usr/bin/perl -w + +use v5.36; +use strict; +use List::Util qw(max); +use feature 'multidimensional'; + +my (%hdoor, %vdoor); +my ($minx, $miny, $maxx, $maxy) = (0, 0, 0, 0); +my $was_change; +my $maxdist; +chomp (my $re = <>); + +$re =~ s/\A\^//; +$re =~ s/\$\z//; + +sub walk($positions, $re) { + my @npos; + my %seen; + for my $p (@$positions) { + next if $seen{$p->[0],$p->[1]}++; + push @npos, [ @$p ]; + } + + say "len=", length($re), " npos=", scalar @npos; + + my @rv; + + while (length $re) { + my ($first, $rest) = $re =~ /\A(.)(.*)\z/; + + if ($first =~ /[NSWE]/) { + for my $p (@npos) { + my ($x, $y) = @$p; + if ($first eq 'N') { $hdoor{$x,$y} = 1; $y--; } + elsif ($first eq 'S') { $y++; $hdoor{$x,$y} = 1; } + elsif ($first eq 'W') { $vdoor{$x,$y} = 1; $x--; } + elsif ($first eq 'E') { $x++; $vdoor{$x,$y} = 1; } + $p->[0] = $x; + $p->[1] = $y; + $minx = $x if $minx > $x; + $maxx = $x if $maxx < $x; + $miny = $y if $miny > $y; + $maxy = $y if $maxy < $y; + } + } elsif ($first eq '|') { + push @rv, @npos; + @npos = map { [ @$_ ] } @$positions; + } elsif ($first eq ')') { + push @rv, @npos; + return (\@rv, $rest); + } elsif ($first eq '(') { + my ($n, $re1) = walk(\@npos, $rest); + @npos = @$n; + $rest = $re1; + } + $re = $rest; + } + return (\@npos, ''); +} + +sub print_map { + for my $y ($miny .. $maxy+1) { + for my $x ($minx .. $maxx) { + print $hdoor{$x,$y} ? '#-' : '##'; + } + print "#\n"; + if ($y <= $maxy) { + for my $x ($minx .. $maxx) { + print $vdoor{$x,$y} ? '|.' : '#.'; + } + print "#\n"; + } + } +} + +walk([ [0, 0] ], $re); +print_map(); + +my @q = ([ 0, 0, 0 ]); +my %seen; +$seen{0,0} = 1; +my $max_dist = 0; + +while (@q) { + my $h = shift @q; + my ($x, $y, $dist) = @$h; + if (!$max_dist || $dist > $max_dist) { + $max_dist = $dist; + } + if ($hdoor{$x,$y} && !$seen{$x,$y-1}++) { + push @q, [$x, $y-1, $dist+1]; + } + if ($hdoor{$x,$y+1} && !$seen{$x,$y+1}++) { + push @q, [$x, $y+1, $dist+1]; + } + if ($vdoor{$x,$y} && !$seen{$x-1,$y}++) { + push @q, [$x-1, $y, $dist+1]; + } + if ($vdoor{$x+1,$y} && !$seen{$x+1,$y}++) { + push @q, [$x+1, $y, $dist+1]; + } +} + +say $max_dist; + + diff --git a/2018/40.pl b/2018/40.pl new file mode 100755 index 0000000..6a7e76c --- /dev/null +++ b/2018/40.pl @@ -0,0 +1,110 @@ +#!/usr/bin/perl -w + +use v5.36; +use strict; +use List::Util qw(max); +use feature 'multidimensional'; + +my (%hdoor, %vdoor); +my ($minx, $miny, $maxx, $maxy) = (0, 0, 0, 0); +my $was_change; +my $maxdist; +chomp (my $re = <>); + +$re =~ s/\A\^//; +$re =~ s/\$\z//; + +sub walk($positions, $re) { + my @npos; + my %seen; + for my $p (@$positions) { + next if $seen{$p->[0],$p->[1]}++; + push @npos, [ @$p ]; + } + + say "len=", length($re), " npos=", scalar @npos; + + my @rv; + + while (length $re) { + my ($first, $rest) = $re =~ /\A(.)(.*)\z/; + + if ($first =~ /[NSWE]/) { + for my $p (@npos) { + my ($x, $y) = @$p; + if ($first eq 'N') { $hdoor{$x,$y} = 1; $y--; } + elsif ($first eq 'S') { $y++; $hdoor{$x,$y} = 1; } + elsif ($first eq 'W') { $vdoor{$x,$y} = 1; $x--; } + elsif ($first eq 'E') { $x++; $vdoor{$x,$y} = 1; } + $p->[0] = $x; + $p->[1] = $y; + $minx = $x if $minx > $x; + $maxx = $x if $maxx < $x; + $miny = $y if $miny > $y; + $maxy = $y if $maxy < $y; + } + } elsif ($first eq '|') { + push @rv, @npos; + @npos = map { [ @$_ ] } @$positions; + } elsif ($first eq ')') { + push @rv, @npos; + return (\@rv, $rest); + } elsif ($first eq '(') { + my ($n, $re1) = walk(\@npos, $rest); + @npos = @$n; + $rest = $re1; + } + $re = $rest; + } + return (\@npos, ''); +} + +sub print_map { + for my $y ($miny .. $maxy+1) { + for my $x ($minx .. $maxx) { + print $hdoor{$x,$y} ? '#-' : '##'; + } + print "#\n"; + if ($y <= $maxy) { + for my $x ($minx .. $maxx) { + print $vdoor{$x,$y} ? '|.' : '#.'; + } + print "#\n"; + } + } +} + +walk([ [0, 0] ], $re); +print_map(); + +my @q = ([ 0, 0, 0 ]); +my %seen; +$seen{0,0} = 1; +my $max_dist = 0; +my $rooms = 0; + +while (@q) { + my $h = shift @q; + my ($x, $y, $dist) = @$h; + $rooms++ if $dist >= 1000; + + if (!$max_dist || $dist > $max_dist) { + $max_dist = $dist; + } + if ($hdoor{$x,$y} && !$seen{$x,$y-1}++) { + push @q, [$x, $y-1, $dist+1]; + } + if ($hdoor{$x,$y+1} && !$seen{$x,$y+1}++) { + push @q, [$x, $y+1, $dist+1]; + } + if ($vdoor{$x,$y} && !$seen{$x-1,$y}++) { + push @q, [$x-1, $y, $dist+1]; + } + if ($vdoor{$x+1,$y} && !$seen{$x+1,$y}++) { + push @q, [$x+1, $y, $dist+1]; + } +} + +say $max_dist; + +say $rooms; diff --git a/2018/41.pl b/2018/41.pl new file mode 100755 index 0000000..3fb1a71 --- /dev/null +++ b/2018/41.pl @@ -0,0 +1,94 @@ +#!/usr/bin/perl -w + +use v5.36; +use strict; + +my @code; +my @regs = ((0) x 6); +my $ip_reg; + +while() { + if (/\A#ip (\d+)/) { + $ip_reg = $1; + next; + } + chomp; + push @code, [ split /\s+/ ]; +} + +my $nmachines = shift @ARGV; +my @machines; +# push @machines, [ ($_, ((0) x 6)) ] for 0 .. $nmachines; +push @machines, [ (10961197, ((0) x 6)) ]; + +my %seen; + +sub one_step($regs) { + my $ip = $regs->[6]; + my ($op, $a, $b, $c) = @{ $code[$ip] }; + + $regs->[$ip_reg] = $ip; + + if ($op eq 'addr') { + $regs->[$c] = $regs->[$a] + $regs->[$b]; + } elsif ($op eq 'addi') { + $regs->[$c] = $regs->[$a] + $b; + } elsif ($op eq 'mulr') { + $regs->[$c] = $regs->[$a] * $regs->[$b]; + } elsif ($op eq 'muli') { + $regs->[$c] = $regs->[$a] * $b; + } elsif ($op eq 'banr') { + $regs->[$c] = $regs->[$a] & $regs->[$b]; + } elsif ($op eq 'bani') { + $regs->[$c] = $regs->[$a] & $b; + } elsif ($op eq 'borr') { + $regs->[$c] = $regs->[$a] | $regs->[$b]; + } elsif ($op eq 'bori') { + $regs->[$c] = $regs->[$a] | $b; + } elsif ($op eq 'setr') { + $regs->[$c] = $regs->[$a]; + } elsif ($op eq 'seti') { + $regs->[$c] = $a; + } elsif ($op eq 'gtrr') { + $regs->[$c] = $regs->[$a] > $regs->[$b] ? 1 : 0; + } elsif ($op eq 'gtir') { + $regs->[$c] = $a > $regs->[$b] ? 1 : 0; + } elsif ($op eq 'eqrr') { + $regs->[$c] = $regs->[$a] == $regs->[$b] ? 1 : 0; + } elsif ($op eq 'eqri') { + $regs->[$c] = $regs->[$a] == $b ? 1 : 0; + } elsif ($op eq 'nop') { + + } else { + die "Unknown op $ op at $ip"; + } + say join(' ', @{ $code[$ip] }, "\t", @$regs); + # $regs->[3] = $ARGV[0] if $ip == 35; + $regs->[6] = $regs->[$ip_reg] + 1; + +# if ($seen{join(',', @$regs)}++) { +# say "seen"; +# $regs->[6] = -1; +# return 0; +# } + if ($regs->[6] >= @code) { + say "halts"; + return 1; + } else { + return undef; + } +} + +my $step = 0; +while (1) { + say "step ", ++$step; + for my $m (0 .. $#machines) { + next if $machines[$m]->[6] == -1; + # say "machine $m"; + if (one_step($machines[$m])) { + say "Machine $m halts after ste $step"; + exit 0; + } + } +} + diff --git a/2018/42.pl b/2018/42.pl new file mode 100755 index 0000000..9a4f095 --- /dev/null +++ b/2018/42.pl @@ -0,0 +1,105 @@ +#!/usr/bin/perl -w + +use v5.36; +use strict; + +my @code; +my @regs = ((0) x 6); +my $ip_reg; + +while() { + if (/\A#ip (\d+)/) { + $ip_reg = $1; + next; + } + chomp; + push @code, [ split /\s+/ ]; +} + +my $nmachines = shift @ARGV; +my @machines; +# push @machines, [ ($_, ((0) x 6)) ] for 0 .. $nmachines; +push @machines, [ (10961198, ((0) x 6)) ]; + +my %seen; +my $prev_halting; + +sub one_step($regs) { + my $ip = $regs->[6]; + my ($op, $a, $b, $c) = @{ $code[$ip] }; + + $regs->[$ip_reg] = $ip; + + if ($op eq 'addr') { + $regs->[$c] = $regs->[$a] + $regs->[$b]; + } elsif ($op eq 'addi') { + $regs->[$c] = $regs->[$a] + $b; + } elsif ($op eq 'mulr') { + $regs->[$c] = $regs->[$a] * $regs->[$b]; + } elsif ($op eq 'muli') { + $regs->[$c] = $regs->[$a] * $b; + } elsif ($op eq 'banr') { + $regs->[$c] = $regs->[$a] & $regs->[$b]; + } elsif ($op eq 'bani') { + $regs->[$c] = $regs->[$a] & $b; + } elsif ($op eq 'borr') { + $regs->[$c] = $regs->[$a] | $regs->[$b]; + } elsif ($op eq 'bori') { + $regs->[$c] = $regs->[$a] | $b; + } elsif ($op eq 'setr') { + $regs->[$c] = $regs->[$a]; + } elsif ($op eq 'seti') { + $regs->[$c] = $a; + } elsif ($op eq 'gtrr') { + $regs->[$c] = $regs->[$a] > $regs->[$b] ? 1 : 0; + } elsif ($op eq 'gtir') { + $regs->[$c] = $a > $regs->[$b] ? 1 : 0; + } elsif ($op eq 'eqrr') { + $regs->[$c] = $regs->[$a] == $regs->[$b] ? 1 : 0; + } elsif ($op eq 'eqri') { + $regs->[$c] = $regs->[$a] == $b ? 1 : 0; + } elsif ($op eq 'nop') { + + } else { + die "Unknown op $ op at $ip"; + } + # say join(' ', @{ $code[$ip] }, "\t", @$regs); + # $regs->[3] = $ARGV[0] if $ip == 35; + $regs->[6] = $regs->[$ip_reg] + 1; + + if ($regs->[6] == 28) { + if ($seen{$regs->[4]}++) { + say "$regs->[4] already seen"; + return 1; + } + say "halts at $regs->[4]\t", sprintf("%08x", $regs->[4]); + $prev_halting = $regs->[4]; + } + +# if ($seen{join(',', @$regs)}++) { +# say "seen"; +# $regs->[6] = -1; +# return 0; +# } + if ($regs->[6] >= @code) { + say "halts"; + return 1; + } else { + return undef; + } +} + +my $step = 0; +while (1) { + ++$step; + # say "step ", ++$step; + for my $m (0 .. $#machines) { + next if $machines[$m]->[6] == -1; + # say "machine $m"; + if (one_step($machines[$m])) { + say "Machine $m halts after step $step prev $prev_halting"; + exit 0; + } + } +} + diff --git a/2018/43.pl b/2018/43.pl new file mode 100755 index 0000000..21407e0 --- /dev/null +++ b/2018/43.pl @@ -0,0 +1,38 @@ +#!/usr/bin/perl -w + +use v5.36; +use strict; +use feature 'multidimensional'; + +my $depth = 11739; +my ($tx, $ty) = (11,718); + +my %gi; +sub gi2el($gi) { ($gi + $depth) % 20183 } +my %el; + +my $sum = 0; +for my $n (1 .. $tx + $ty) { + my $y = 0; + my $x = $n; + for my $i (0 .. $n) { + if (($x == 0 && $y == 0) || ($x == $tx && $y == $ty)) { + $gi{$x,$y} = 0; + } elsif ($y == 0) { + $gi{$x,$y} = 16807*$x; + } elsif ($x == 0) { + $gi{$x,$y} = 48271*$y; + } else { + $gi{$x,$y} = $el{$x-1,$y} * $el{$x,$y-1}; + } + $el{$x,$y} = gi2el($gi{$x,$y}); + $sum += $el{$x,$y} % 3 + if $x <= $tx && $y <= $ty; + $y++; + $x--; + } +} + +say $sum; + + diff --git a/2018/44.pl b/2018/44.pl new file mode 100755 index 0000000..2b795c7 --- /dev/null +++ b/2018/44.pl @@ -0,0 +1,109 @@ +#!/usr/bin/perl -w + +use v5.36; +use strict; +use feature 'multidimensional'; + +my $depth = 11739; +my ($tx, $ty) = (11,718); + +my %gi; +sub gi2el($gi) { ($gi + $depth) % 20183 } +my %el; +my %type; + +sub can_use($x, $y, $gear) { + return 1 if + $type{$x,$y} == 0 && $gear + || $type{$x,$y} == 1 && ($gear == 0 || $gear == 2) + || $type{$x,$y} == 2 && ($gear == 0 || $gear == 1); + return 0; +} + +my $sum = 0; +for my $n (0 .. 6*($tx + $ty)) { + my $y = 0; + my $x = $n; + for my $i (0 .. $n) { + if (($x == 0 && $y == 0) || ($x == $tx && $y == $ty)) { + $gi{$x,$y} = 0; + } elsif ($y == 0) { + $gi{$x,$y} = 16807*$x; + } elsif ($x == 0) { + $gi{$x,$y} = 48271*$y; + } else { + $gi{$x,$y} = $el{$x-1,$y} * $el{$x,$y-1}; + } + $el{$x,$y} = gi2el($gi{$x,$y}); + $type{$x,$y} = $el{$x,$y} % 3; + $y++; + $x--; + } +} + +my @q = ([0, 0, 0, 1]); + +my %map; +$map{0,0,1} = 0; + +say "walking the graph"; +my $now = 0; +while (@q) { + my @current_minute; + while (@q && $q[0]->[0] <= $now) { + push @current_minute, shift @q; + } + say scalar(@current_minute), " states in $now"; + + for my $state (@current_minute) { + my ($time, $x, $y, $tool) = @$state; + say "state $x,$y,$tool"; + next if !defined $type{$x,$y}; + $map{$x,$y,$tool} = $now + if !defined $map{$x,$y,$tool} + || $map{$x,$y,$tool} > $now; + + if ($x == $tx && $y == $ty) { + say "Target reached at $now"; + exit 0; + } + $map{$x,$y,$tool} = $now if !defined $map{$x,$y,$tool} + || $map{$x,$y,$tool} > $now; + + if ($tool != 0 && can_use($x, $y, 0) + && (!defined $map{$x,$y,0} + || ($map{$x,$y,0} > $now+7))) { + push @q, [ $now+7, $x, $y, 0]; + $map{$x,$y,$0} = $now+7; + } + + if ($tool != 1 && can_use($x, $y, 1) + && (!defined $map{$x,$y,1} + || ($map{$x,$y,1} > $now+7))) { + push @q, [ $now+7, $x, $y, 1]; + $map{$x,$y,1} = $now+7; + } + + if ($tool != 2 && can_use($x, $y, 2) + && (!defined $map{$x,$y,2} + || ($map{$x,$y,2} > $now+7))) { + push @q, [ $now+7, $x, $y, 2]; + $map{$x,$y,2} = $now+7; + } + + for my $v ([-1, 0], [0, -1], [1, 0], [0, 1]) { + my ($dx, $dy) = @$v; + next if $x+$dx < 0 || $y+$dy < 0; + next if !can_use($x+$dx, $y+$dy, $tool); + next if defined $map{$x+$dx,$y+$dy,$tool} + && $map{$x+$dx,$y+$dy,$tool} <= $now+1; + unshift @q, [ $now+1, $x+$dx, $y+$dy, $tool ]; + $map{$x+$dx,$y+$dy,$tool} = $now+1; + } + } + $now++; +} + +say join(',', $map{$tx,$ty,0}, $map{$tx,$ty,1}, $map{$tx,$ty,2}); + + diff --git a/2018/45.pl b/2018/45.pl new file mode 100755 index 0000000..349b246 --- /dev/null +++ b/2018/45.pl @@ -0,0 +1,28 @@ +#!/usr/bin/perl -w + +use v5.34; +use strict; + +my @bots; +my $highest; +while (<>) { + my ($x, $y, $z, $r) = /(-?\d+)/g; + push @bots, [$x, $y, $z, $r]; + if (!$highest || $highest->[3] < $r) { + $highest = [$x, $y, $z, $r]; + } +} + +my ($x, $y, $z, $r) = @$highest; + +my $in_range; +for my $bot (@bots) { + $in_range++ if + abs($bot->[0] - $x) + + abs($bot->[1] - $y) + + abs($bot->[2] - $z) <= $r; +} + +say $in_range; + + diff --git a/2018/46.pl b/2018/46.pl new file mode 100755 index 0000000..a7ea97e --- /dev/null +++ b/2018/46.pl @@ -0,0 +1,84 @@ +#!/usr/bin/perl -w + +use v5.36; +use strict; + +my @bots = sort { $b->[3] <=> $a->[3] } map { [ /(-?\d+)/g ] } <>; +# my @bots = map { [ /(-?\d+)/g ] } <>; + +sub overlaps($bot1, $bot2) { + abs($bot1->[0] - $bot2->[0]) + + abs($bot1->[1] - $bot2->[1]) + + abs($bot1->[2] - $bot2->[2]) <= $bot1->[3] + $bot2->[3]; +} + +my @best; + +sub walk($subset) { + our $loop; + our $min_sub = @$subset if !defined $min_sub || @$subset < $min_sub; + if (++$loop % 10000 == 0) { + say "walk: best ", scalar @best, + ' min ', $min_sub; + $min_sub = undef; + die; + } + my $to_check = @bots - $subset->[-1]; + return if @$subset + $to_check < @best; + CANDIDATE: + for my $i ($subset->[-1] + 1 .. $#bots) { + for my $j (@$subset) { + next CANDIDATE if !overlaps($bots[$i], $bots[$j]); + } + walk([ @$subset, $i ]); + } + + if (@best < @$subset) { + @best = @$subset; + } +} + +# eval { say "walk($_)"; walk([$_]) } for 0 .. $#bots; +eval { walk([0]); }; + +@best = sort { $bots[$a]->[3] <=> $bots[$b]->[3] } @best; +say "Best subset has ", scalar @best, " members"; +say "Smallest is ", join(',', @{ $bots[$best[0]] }); + +sub try_overlaps { + for my $j (1 .. $#best) { + last return undef + if !overlaps($bots[$best[0]], $bots[$best[$j]]); + } + return 1; +} + +my $shrink; +DIM: +while (1) { + say "Trying diameter $bots[$best[0]]->[3]"; + if (try_overlaps) { + last DIM if $bots[$best[0]]->[3] == 0; + $shrink = int($bots[$best[0]]->[3]/4); + $shrink = 1 if $shrink < 1; + $bots[$best[0]]->[3] -= $shrink; + next; + } + for my $dir ([-1, 0, 0], [1, 0, 0], [0, -1, 0], [0, 1, 0], [0, 0, -1], [0, 0, 1]) { + say "trying ", join(',', @$dir); + for (0 .. 2) { + $bots[$best[0]]->[$_] += $shrink*$dir->[$_]; + } + next DIM if try_overlaps; + say "failed"; + for (0 .. 2) { + $bots[$best[0]]->[$_] -= $shrink*$dir->[$_]; + } + } + die "nothing matched. strange"; +} +say "end: ", join(',', @{ $bots[$best[0]] }); +say $bots[$best[0]]->[0] + + $bots[$best[0]]->[1] + + $bots[$best[0]]->[2]; + diff --git a/2018/47.pl b/2018/47.pl new file mode 100755 index 0000000..1e1e594 --- /dev/null +++ b/2018/47.pl @@ -0,0 +1,117 @@ +#!/usr/bin/perl -w + +use v5.36; +use strict; + +my @armies_txt; +{ local $/ = "\n\n"; chomp (@armies_txt = <>); } + +my @units = map { parse_army($_) } @armies_txt; +use Data::Dumper; +# print Dumper \@units; + +sub parse_army($text) { + my ($name, @rest) = split /\n/, $text; + $name =~ s/:\z//; + my $i = 0; + return ( map { parse_group($name, ++$i, $_) } + grep { length $_ } @rest ); +} + +sub parse_group($army, $id, $text) { + my %rv = ( army => $army, name => "$army group $id", text => $text ); + ($rv{units}) = $text =~ /\A(\d+) unit/; + ($rv{hp}) = $text =~ / (\d+) hit point/; + ($rv{hp}) = $text =~ / (\d+) hit point/; + ($rv{damage}, $rv{damage_type}) + = $text =~ /that does (\d+) (\w+) damage /; + ($rv{init}) = $text =~ /at initiative (\d+)\z/; + $rv{weak} = { + map { defined $_ ? ($_ => 1) : () } + $text =~ /weak to (\w+)(?:, (\w+))*/ + }; + $rv{immune} = { + map { defined $_ ? ($_ => 1) : () } + $text =~ /immune to (\w+)(?:, (\w+))*/ + }; + return \%rv; +} + +sub e_pwr($unit) { return $unit->{units} * $unit->{damage} }; + +sub damage_to($attacker, $defender) { + return 0 if $defender->{immune}->{$attacker->{damage_type}}; + my $power = e_pwr($attacker); + $power *= 2 if $defender->{weak}->{$attacker->{damage_type}}; + return $power; +} + +sub selection { + say ""; + my @rv; + my %attacked; + for my $unit (sort { + $b->{units}*$b->{damage} <=> $a->{units}*$a->{damage} + || $b->{init} <=> $a->{init} + } @units) { + next if !$unit->{units}; + for my $def (sort { + damage_to($unit, $b) <=> damage_to($unit, $a) + || e_pwr($b) <=> e_pwr($a) + || $b->{init} <=> $a->{init} + } + grep { + $_->{army} ne $unit->{army} + && $_->{units} + && !$attacked{$_->{name}} + } @units) { + my $d = damage_to($unit, $def); + next if !$d; + say $unit->{name}, ' => ', $def->{name}, ': ', $d; + $attacked{$def->{name}} = $unit->{name}; + push @rv, [ $unit, $def ]; + last; + } + } + return \@rv; +} + +sub attack($items) { + say ""; + for my $item (sort { $b->[0]->{init} <=> $a->[0]->{init} } @$items) { + my ($att, $def) = @$item; + next if !$att->{units}; + my $killed = int(damage_to($att, $def) / $def->{hp}); + $killed = $def->{units} if $killed > $def->{units}; + + say "$att->{name} attacks $def->{name} killing $killed units"; + $def->{units} -= $killed; + $def->{units} = 0 if $def->{units} < 0; + } +} + +my $round = 0; +while (1) { + say "round ", $round++; + my %alive; + my $sum; + for my $unit (@units) { + next if !$unit->{units}; + say "$unit->{name} contains $unit->{units} units"; + $sum += $unit->{units}; + $alive{$unit->{army}}++; + } + if (keys(%alive) < 2) { + say "sum=$sum"; + last; + } + attack(selection()); +} + +__END__ +Immune System: +889 units each with 3275 hit points (weak to bludgeoning, radiation; immune to cold) with an attack that does 36 bludgeoning damage at initiative 12 +94 units each with 1336 hit points (weak to radiation, cold) with an attack that does 127 bludgeoning damage at initiative 7 +1990 units each with 5438 hit points with an attack that does 25 slashing damage at initiative 20 + + diff --git a/2018/48.pl b/2018/48.pl new file mode 100755 index 0000000..6198516 --- /dev/null +++ b/2018/48.pl @@ -0,0 +1,135 @@ +#!/usr/bin/perl -w + +use v5.36; +use strict; + +my @armies_txt; +{ local $/ = "\n\n"; chomp (@armies_txt = <>); } + +my @units = map { parse_army($_) } @armies_txt; +use Data::Dumper; +print Dumper \@units; + +sub parse_army($text) { + my ($name, @rest) = split /\n/, $text; + $name =~ s/:\z//; + my $i = 0; + return ( map { parse_group($name, ++$i, $_) } + grep { length $_ } @rest ); +} + +sub parse_group($army, $id, $text) { + my %rv = ( army => $army, name => "$army group $id", text => $text ); + ($rv{units}) = $text =~ /\A(\d+) unit/; + ($rv{hp}) = $text =~ / (\d+) hit point/; + ($rv{damage}, $rv{damage_type}) + = $text =~ /that does (\d+) (\w+) damage /; + ($rv{init}) = $text =~ /at initiative (\d+)\z/; + my ($l) = $text =~ /weak to ([^;\)]+)[\);]/; + + $rv{weak} = { map { $_ => 1 } split(/, /, $l) } + if length $l; + ($l) = $text =~ /immune to ([^;\)]+)[\);]/; + $rv{immune} = { map { $_ => 1 } split(/, /, $l) } + if length $l; + $rv{orig_units} = $rv{units}; + $rv{orig_damage} = $rv{damage}; + return \%rv; +} + +sub e_pwr($unit) { return $unit->{units} * $unit->{damage} }; + +sub damage_to($attacker, $defender) { + return 0 if $defender->{immune}->{$attacker->{damage_type}}; + my $power = e_pwr($attacker); + $power *= 2 if $defender->{weak}->{$attacker->{damage_type}}; + return $power; +} + +sub selection { + say ""; + my @rv; + my %attacked; + for my $unit (sort { + $b->{units}*$b->{damage} <=> $a->{units}*$a->{damage} + || $b->{init} <=> $a->{init} + } @units) { + next if !$unit->{units}; + for my $def (sort { + damage_to($unit, $b) <=> damage_to($unit, $a) + || e_pwr($b) <=> e_pwr($a) + || $b->{init} <=> $a->{init} + } + grep { + $_->{army} ne $unit->{army} + && $_->{units} + && !$attacked{$_->{name}} + } @units) { + my $d = damage_to($unit, $def); + next if !$d; + say $unit->{name}, ' => ', $def->{name}, ': ', $d; + $attacked{$def->{name}} = $unit->{name}; + push @rv, [ $unit, $def ]; + last; + } + } + return \@rv; +} + +sub attack($items) { + say ""; + my $total_killed = 0; + for my $item (sort { $b->[0]->{init} <=> $a->[0]->{init} } @$items) { + my ($att, $def) = @$item; + next if !$att->{units}; + my $killed = int(damage_to($att, $def) / $def->{hp}); + $killed = $def->{units} if $killed > $def->{units}; + $total_killed += $killed; + + say "$att->{name} attacks $def->{name} killing $killed units"; + $def->{units} -= $killed; + $def->{units} = 0 if $def->{units} < 0; + } + return $total_killed; +} + +sub battle($boost) { + my $round = 0; + + for my $unit (@units) { + $unit->{units} = $unit->{orig_units}; + $unit->{damage} = $unit->{orig_damage}; + $unit->{damage} += $boost + if $unit->{army} eq 'Immune System'; + } + + say " ################## boost $boost ##################### "; + while (1) { + say "round ", $round++; + my %alive; + my $sum; + for my $unit (@units) { + next if !$unit->{units}; + say "$unit->{name} contains $unit->{units} units"; + $sum += $unit->{units}; + $alive{$unit->{army}}++; + } + if (keys(%alive) < 2) { + say "sum=$sum"; + return $alive{"Immune System"} ? 1 : 0; + } + return 0 if !attack(selection()); + } +} + +my $boost = 0; +1 while !battle($boost++); + +__END__ +Immune System: +889 units each with 3275 hit points (weak to bludgeoning, radiation; immune to cold) with an attack that does 36 bludgeoning damage at initiative 12 +94 units each with 1336 hit points (weak to radiation, cold) with an attack that does 127 bludgeoning damage at initiative 7 +1990 units each with 5438 hit points with an attack that does 25 slashing damage at initiative 20 + +Infection group 4 attacks Immune System group 9 killing 0 units +6523 diff --git a/2018/49.pl b/2018/49.pl new file mode 100755 index 0000000..0d0c595 --- /dev/null +++ b/2018/49.pl @@ -0,0 +1,42 @@ +#!/usr/bin/perl -w + +use v5.36; +use strict; +use List::Util qw(sum); +use experimental 'multidimensional'; + +my @points = map { chomp; [ split /,/ ] } <>; + +sub dist($p1, $p2) { my $sum; $sum+=abs($p1->[$_]-$p2->[$_]) for 0 .. 3; $sum }; + +my $n_const; +my %const_of; +for my $x (0 .. $#points) { + for my $y ($x .. $#points) { + next if dist($points[$x], $points[$y]) > 3; + say "dist($x,$y) = ", dist($points[$x], $points[$y]); + if (!defined $const_of{$x} && !defined $const_of{$y}) { + $const_of{$x} = $const_of{$y} = ++$n_const; + } elsif (!defined $const_of{$x}) { + $const_of{$x} = $const_of{$y}; + } elsif (!defined $const_of{$y}) { + $const_of{$y} = $const_of{$x}; + } elsif ($const_of{$x} != $const_of{$y}) { + # both different, join them + say "adding $const_of{$y} to $const_of{$x}"; + my $to_del = $const_of{$y}; + for my $p (0 .. $#points) { + $const_of{$p} = $const_of{$x} + if defined $const_of{$p} + && $const_of{$p} == $to_del; + } + } + say " $x in $const_of{$x}, $y in $const_of{$y}"; + } +} + +say "$_ in $const_of{$_}" for sort keys %const_of; +my %const_used = map { $_ => 1 } values %const_of; +say join(',', keys %const_used); +say scalar keys %const_used; + diff --git a/2018/get.sh b/2018/get.sh new file mode 100755 index 0000000..10ac59c --- /dev/null +++ b/2018/get.sh @@ -0,0 +1,29 @@ +#!/bin/bash + +DAY=`date +%d|sed 's/ //g'` +test -n "$1" && DAY="$1" +FILE="$((2*DAY - 1))in.txt" +COOKIE=`cat cookie` + +START="6:00:02" +MAXWAIT=300 +STARTSEC=`date -d "$START" "+%s"` +NOW=`date "+%s"` +WAITSEC=`expr $STARTSEC - $NOW` + +if [ $WAITSEC -gt 0 -a $WAITSEC -lt $MAXWAIT ] +then + echo "Waiting for $WAITSEC seconds till $START for getting $FILE ..." + sleep $WAITSEC +fi + +URL="https://adventofcode.com/2018/day/$DAY/input" +echo +echo "Downloading $URL to $FILE" +curl -s -b "$COOKIE" "$URL" --output "$FILE" +echo ======================================================================== +cat "$FILE" +echo ======================================================================== +echo "lines words chars" +wc "$FILE" +echo