From 1c24d2f5032a3181a6693084f763839e77eaca26 Mon Sep 17 00:00:00 2001 From: "Jan \"Yenya\" Kasprzak" Date: Sun, 16 Jan 2022 23:21:28 +0100 Subject: [PATCH] AoC 2017 days 11 to 15 --- 2017/21.pl | 43 ++++++++++++++++++++++++++++ 2017/22.pl | 51 +++++++++++++++++++++++++++++++++ 2017/23.pl | 27 ++++++++++++++++++ 2017/24.pl | 32 +++++++++++++++++++++ 2017/25.pl | 20 +++++++++++++ 2017/26.pl | 24 ++++++++++++++++ 2017/27.pl | 55 ++++++++++++++++++++++++++++++++++++ 2017/28.pl | 82 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2017/29.pl | 20 +++++++++++++ 2017/30.pl | 22 +++++++++++++++ 10 files changed, 376 insertions(+) create mode 100755 2017/21.pl create mode 100755 2017/22.pl create mode 100755 2017/23.pl create mode 100755 2017/24.pl create mode 100755 2017/25.pl create mode 100755 2017/26.pl create mode 100755 2017/27.pl create mode 100755 2017/28.pl create mode 100755 2017/29.pl create mode 100755 2017/30.pl diff --git a/2017/21.pl b/2017/21.pl new file mode 100755 index 0000000..9fc2bfe --- /dev/null +++ b/2017/21.pl @@ -0,0 +1,43 @@ +#!/usr/bin/perl + +use v5.30; +use strict; + +my ($x, $y) = (0, 0); + +my @path = split /[,\s]/, <>; + +# |/ +# o +# /| +# x y +for my $dir (@path) { + if ($dir eq 's') { + $y--; + } elsif ($dir eq 'n') { + $y++; + } elsif ($dir eq 'ne') { + $x++; + } elsif ($dir eq 'nw') { + $x--; + $y++; + } elsif ($dir eq 'se') { + $x++; + $y--; + } elsif ($dir eq 'sw') { + $x--; + } +} + +my $dist; +if ($x >= 0 && $y >= 0 || $x <= 0 && $y <= 0) { + $dist = abs($x + $y); +} elsif (abs($x) >= abs($y)) { + $dist = abs($x); +} else { + $dist = abs($y); +} + +say $dist; + + diff --git a/2017/22.pl b/2017/22.pl new file mode 100755 index 0000000..dcaa0da --- /dev/null +++ b/2017/22.pl @@ -0,0 +1,51 @@ +#!/usr/bin/perl + +use v5.30; +use strict; + +my ($x, $y) = (0, 0); + +my @path = split /[,\s]/, <>; + +# |/ +# o +# /| +# x y + +sub dist { + my ($x,$y) = @_; + my $dist; + if ($x >= 0 && $y >= 0 || $x <= 0 && $y <= 0) { + $dist = abs($x + $y); + } elsif (abs($x) >= abs($y)) { + $dist = abs($x); + } else { + $dist = abs($y); + } + return $dist; +} + +my $max; +for my $dir (@path) { + if ($dir eq 's') { + $y--; + } elsif ($dir eq 'n') { + $y++; + } elsif ($dir eq 'ne') { + $x++; + } elsif ($dir eq 'nw') { + $x--; + $y++; + } elsif ($dir eq 'se') { + $x++; + $y--; + } elsif ($dir eq 'sw') { + $x--; + } + my $d = dist($x,$y); + $max = $d if !$max || $max < $d; +} + +say $max; + + diff --git a/2017/23.pl b/2017/23.pl new file mode 100755 index 0000000..73a2e81 --- /dev/null +++ b/2017/23.pl @@ -0,0 +1,27 @@ +#!/usr/bin/perl + +use v5.30; +use strict; + +my %zero; +my %graph; +$; = ','; + +while (<>) { + chomp; + my ($src, @dsts) = /(\d+)/g; + $graph{$src} = [ @dsts ]; +} + + +sub walk { + my ($node) = @_; + + for my $neigh (@{ $graph{$node} }) { + next if $zero{$neigh}++; + walk($neigh); + } +} + +walk(0); +say scalar keys %zero; diff --git a/2017/24.pl b/2017/24.pl new file mode 100755 index 0000000..7b85e56 --- /dev/null +++ b/2017/24.pl @@ -0,0 +1,32 @@ +#!/usr/bin/perl + +use v5.30; +use strict; + +my %zero; +my %graph; +$; = ','; + +while (<>) { + chomp; + my ($src, @dsts) = /(\d+)/g; + $graph{$src} = [ @dsts ]; +} + + +sub walk { + my ($node) = @_; + + for my $neigh (@{ $graph{$node} }) { + next if $zero{$neigh}++; + walk($neigh); + } +} + +my $comp; +for my $node (keys %graph) { + next if $zero{$node}; + walk($node); + $comp++; +} +say $comp; diff --git a/2017/25.pl b/2017/25.pl new file mode 100755 index 0000000..37f5ce3 --- /dev/null +++ b/2017/25.pl @@ -0,0 +1,20 @@ +#!/usr/bin/perl + +use v5.30; +use strict; + +use List::Util qw(max); + +my %layers = map { /(\d+): (\d+)/ } <>; +my $max_l = max keys %layers; + +my $severity = 0; +for my $pos (0 .. $max_l) { + next if !defined $layers{$pos}; + next if $pos % (2 * $layers{$pos} - 2); + say "caught at $pos"; + $severity += $pos * $layers{$pos}; +} + +say $severity; + diff --git a/2017/26.pl b/2017/26.pl new file mode 100755 index 0000000..d3b6957 --- /dev/null +++ b/2017/26.pl @@ -0,0 +1,24 @@ +#!/usr/bin/perl + +use v5.30; +use strict; + +use List::Util qw(max); + +my %layers = map { /(\d+): (\d+)/ } <>; +my $max_l = max keys %layers; + +my $delay = -1; +DELAY: +while (1) { + $delay++; + for my $pos (0 .. $max_l) { + next if !defined $layers{$pos}; + next if ($pos+$delay) % (2 * $layers{$pos} - 2); + next DELAY; + } + last; +} + +say $delay; + diff --git a/2017/27.pl b/2017/27.pl new file mode 100755 index 0000000..dd0a244 --- /dev/null +++ b/2017/27.pl @@ -0,0 +1,55 @@ +#!/usr/bin/perl + +use v5.30; +use strict; + +my $in = 'stpzcrnm'; +# my $in = 'flqrgnkx'; + +sub knot { + my $line = shift; + my @l = map { ord } split //, $line; + push @l, 17, 31, 73, 47, 23; + + my $pos = 0; + my $skip = 0; + # my @nodes = (0 .. 4); + my @nodes = (0 .. 255); + my $n = @nodes; + + for (1 .. 64) { + for my $i (@l) { + my $end = $pos + $i; + my @to_rev; + # say "pos=$pos skip $skip i=$i ", join(',', @nodes); + if ($end > $n) { + push @to_rev, splice @nodes, $pos; + push @to_rev, splice @nodes, 0, $end - $n; + @to_rev = reverse @to_rev; + # say "to_rev = ", join(',', @to_rev); + unshift @nodes, splice @to_rev, @to_rev-($end-$n); + push @nodes, @to_rev; + } else { + push @to_rev, splice @nodes, $pos, $i; + splice @nodes, $pos, 0, reverse @to_rev; + } + $pos += $i + $skip++; + $pos -= $n while $pos >= $n; + } + } + + my $hash = ''; + while (my @s = splice (@nodes, 0, 16)) { + my $x = 0; + $x ^= $_ for @s; + $hash .= sprintf("%08b", $x); + } + return $hash; +} + +my $used = 0; +for my $row (0 .. 127) { + my $h = knot("$in-$row"); + $used++ for $h =~ /1/g; +} +say $used; diff --git a/2017/28.pl b/2017/28.pl new file mode 100755 index 0000000..0d742d6 --- /dev/null +++ b/2017/28.pl @@ -0,0 +1,82 @@ +#!/usr/bin/perl + +use v5.30; +use strict; + +my $in = 'stpzcrnm'; +# my $in = 'flqrgnkx'; + +sub knot { + my $line = shift; + my @l = map { ord } split //, $line; + push @l, 17, 31, 73, 47, 23; + + my $pos = 0; + my $skip = 0; + # my @nodes = (0 .. 4); + my @nodes = (0 .. 255); + my $n = @nodes; + + for (1 .. 64) { + for my $i (@l) { + my $end = $pos + $i; + my @to_rev; + # say "pos=$pos skip $skip i=$i ", join(',', @nodes); + if ($end > $n) { + push @to_rev, splice @nodes, $pos; + push @to_rev, splice @nodes, 0, $end - $n; + @to_rev = reverse @to_rev; + # say "to_rev = ", join(',', @to_rev); + unshift @nodes, splice @to_rev, @to_rev-($end-$n); + push @nodes, @to_rev; + } else { + push @to_rev, splice @nodes, $pos, $i; + splice @nodes, $pos, 0, reverse @to_rev; + } + $pos += $i + $skip++; + $pos -= $n while $pos >= $n; + } + } + + my $hash = ''; + while (my @s = splice (@nodes, 0, 16)) { + my $x = 0; + $x ^= $_ for @s; + $hash .= sprintf("%08b", $x); + } + return $hash; +} + +my @prev = (0) x 128; +my %regions; +my $nr = 1; +for my $row (0 .. 127) { + my $h = knot("$in-$row"); + my @line = split //, $h; + my @nl = (0) x 128; + for my $x (0 .. 127) { + next if $line[$x] == '0'; + + if ($prev[$x]) { + $nl[$x] = $prev[$x]; + } elsif ($x && $nl[$x-1]) { + $nl[$x] = $nl[$x-1]; + } else { + $nl[$x] = $nr; + $regions{$nr} = 1; + $nr++; + } + if ($x && $nl[$x-1] && $nl[$x-1] != $nl[$x]) { + my $old = $nl[$x-1]; + delete $regions{$old}; + for (0 .. 127) { + $nl[$_] = $nl[$x] if $nl[$_] == $old; + $prev[$_] = $nl[$x] if $prev[$_] == $old; + } + } + } + @prev = @nl; +} + +say scalar keys %regions; + diff --git a/2017/29.pl b/2017/29.pl new file mode 100755 index 0000000..fa9c3cc --- /dev/null +++ b/2017/29.pl @@ -0,0 +1,20 @@ +#!/usr/bin/perl + +use v5.30; +use strict; + +my @start = (883, 879); +# my @start = (65, 8921); +my @f = (16807, 48271); + +sub gen { + my ($i,$gen) = @_; + $start[$i] = $start[$i] * $f[$i] % 2147483647; + return $start[$i] & 0xFFFF; +} +my $matches = 0; +for (1 .. 40_000_000) { + $matches++ if gen(0, $_) == gen(1, $_); +} + +say $matches; diff --git a/2017/30.pl b/2017/30.pl new file mode 100755 index 0000000..8dfb269 --- /dev/null +++ b/2017/30.pl @@ -0,0 +1,22 @@ +#!/usr/bin/perl + +use v5.30; +use strict; + +my @start = (883, 879); +# my @start = (65, 8921); +my @f = (16807, 48271); + +sub gen { + my ($i,$gen) = @_; + do { + $start[$i] = $start[$i] * $f[$i] % 2147483647 + } while ($start[$i] % (1 << (2+$i)) != 0); + return $start[$i] & 0xFFFF; +} +my $matches = 0; +for (1 .. 5_000_000) { + $matches++ if gen(0, $_) == gen(1, $_); +} + +say $matches; -- 2.43.0