Year 2018

[aoc.git] / 2018 / 46.pl

diff --git a/2018/46.pl b/2018/46.pl
new file mode 100755 (executable)
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];
+