2019/28.pl

   1 #!/usr/bin/perl -w
   2
   3 use v5.16;
   4 use Data::Dumper;
   5 use List::Util qw(any);
   6
   7 my %rules;
   8 while (<>) {
   9         chomp;
  10         my ($srcs, $dstcount, $dst) = /(.*) => (\d+) (\w+)/;
  11         my %srcs = reverse $srcs =~ /(\d+) (\w+)/g;
  12         $rules{$dst} = {
  13                 count => $dstcount,
  14                 srcs  => \%srcs,
  15         };
  16 }
  17
  18 use List::Util qw(first);
  19
  20 sub fuel_from_ore {
  21         my $fuel = shift;
  22
  23         my (%want, %have);
  24         $want{FUEL} = $fuel;
  25         while (my $w = first { $_ ne 'ORE' && $want{$_} } keys %want) {
  26                 my $r = $rules{$w};
  27                 my $rcount = int (($want{$w}+$r->{count}-1)/$r->{count});
  28                 # say "want $want{$w} of $w, rule has $r->{count}, need $rcount rules";
  29                 if ($rcount * $r->{count} > $want{$w}) {
  30                         $have{$w} = $rcount * $r->{count} - $want{$w};
  31                 }
  32                 delete $want{$w};
  33                 for my $src (keys %{ $r->{srcs} }) {
  34                         my $need = $r->{srcs}->{$src} * $rcount;
  35                         if ($have{$src}) {
  36                                 if ($need >= $have{$src}) {
  37                                         $need -= $have{$src};
  38                                         delete $have{$src};
  39                                 } else {
  40                                         $have{$src} -= $need;
  41                                         next;
  42                                 }
  43                         }
  44                         $want{$src} += $need;
  45                 }
  46                 # say "want: ", join(', ', map { "$want{$_} of $_" } keys %want);
  47                 # say "have: ", join(', ', map { "$have{$_} of $_" } keys %have);
  48                 # say "";
  49         }
  50         return $want{ORE};
  51 }
  52
  53 my $low = fuel_from_ore(1);
  54 say $low;
  55 my $high = $low;
  56
  57 my $max_ore = 1_000_000_000_000;
  58 $high *= 2 while fuel_from_ore($high) <= $max_ore;
  59
  60 my $now;
  61 do {
  62         $now = int(($high + $low) / 2);
  63         if (fuel_from_ore($now) <= $max_ore) {
  64                 $low = $now;
  65         } else {
  66                 $high = $now;
  67         }
  68 } while ($low + 1 < $high);
  69
  70 say $low;