2018/46.pl

   1 #!/usr/bin/perl -w
   2
   3 use v5.36;
   4 use strict;
   5
   6 my @bots = sort { $b->[3] <=> $a->[3] } map { [ /(-?\d+)/g ] } <>;
   7 # my @bots = map { [ /(-?\d+)/g ] } <>;
   8
   9 sub overlaps($bot1, $bot2) {
  10         abs($bot1->[0] - $bot2->[0])
  11         + abs($bot1->[1] - $bot2->[1])
  12         + abs($bot1->[2] - $bot2->[2]) <= $bot1->[3] + $bot2->[3];
  13 }
  14
  15 my @best;
  16
  17 sub walk($subset) {
  18         our $loop;
  19         our $min_sub = @$subset if !defined $min_sub || @$subset < $min_sub;
  20         if (++$loop % 10000 == 0) {
  21                 say "walk: best ", scalar @best,
  22                         ' min ', $min_sub;
  23                 $min_sub = undef;
  24                 die;
  25         }
  26         my $to_check = @bots - $subset->[-1];
  27         return if @$subset + $to_check < @best;
  28         CANDIDATE:
  29         for my $i ($subset->[-1] + 1 .. $#bots) {
  30                 for my $j (@$subset) {
  31                         next CANDIDATE if !overlaps($bots[$i], $bots[$j]);
  32                 }
  33                 walk([ @$subset, $i ]);
  34         }
  35
  36         if (@best < @$subset) {
  37                 @best = @$subset;
  38         }
  39 }
  40
  41 # eval { say "walk($_)"; walk([$_]) } for 0 .. $#bots;
  42 eval { walk([0]); };
  43
  44 @best = sort { $bots[$a]->[3] <=> $bots[$b]->[3] } @best;
  45 say "Best subset has ", scalar @best, " members";
  46 say "Smallest is ", join(',', @{ $bots[$best[0]] });
  47
  48 sub try_overlaps {
  49         for my $j (1 .. $#best) {
  50                 last return undef
  51                         if !overlaps($bots[$best[0]], $bots[$best[$j]]);
  52         }
  53         return 1;
  54 }
  55
  56 my $shrink;
  57 DIM:
  58 while (1) {
  59         say "Trying diameter $bots[$best[0]]->[3]";
  60         if (try_overlaps) {
  61                 last DIM if $bots[$best[0]]->[3] == 0;
  62                 $shrink = int($bots[$best[0]]->[3]/4);
  63                 $shrink = 1 if $shrink < 1;
  64                 $bots[$best[0]]->[3] -= $shrink;
  65                 next;
  66         }
  67         for my $dir ([-1, 0, 0], [1, 0, 0], [0, -1, 0], [0, 1, 0], [0, 0, -1], [0, 0, 1]) {
  68                 say "trying ", join(',', @$dir);
  69                 for (0 .. 2) {
  70                         $bots[$best[0]]->[$_] += $shrink*$dir->[$_];
  71                 }
  72                 next DIM if try_overlaps;
  73                 say "failed";
  74                 for (0 .. 2) {
  75                         $bots[$best[0]]->[$_] -= $shrink*$dir->[$_];
  76                 }
  77         }
  78         die "nothing matched. strange";
  79 }
  80 say "end: ", join(',', @{ $bots[$best[0]] });
  81 say $bots[$best[0]]->[0]
  82         + $bots[$best[0]]->[1]
  83         + $bots[$best[0]]->[2];
  84