AoC Day 13 – Shuttle Search

This is a solution to Advent of Code 2020 day 13, written in Raku.

https://adventofcode.com/2020/day/13

Part One

What is the ID of the earliest bus you can take to the airport multiplied by the number of minutes you'll need to wait for that bus?

Raku

Part one can be solved by using a bit of div and multiplication to work out the next time after $earliest that each bus will run. Then it's just a case of sorting these future times and picking the first.

  my @input = '13-input.txt'.IO.lines;
  my $earliest = +@input.shift;
  my @bus-ids = @input.shift.split(',').grep(* ne 'x').map(*.Int);

  my %futures = @bus-ids.map(-> $id { $id => ($earliest div $id) * $id + $id });
  my @times = %futures.pairs.sort({ $^a.value leg $^b.value });

  my $id = @times[0].key;
  my $diff = @times[0].value - $earliest;

  say "{$id} * {$diff} = {$id * $diff}";
647 * 6 = 3882

What is the earliest timestamp such that all of the listed bus IDs depart at offsets matching their positions in the list?

Raku

Part two left me fairly stumped because I knew that a brute-force search would likely run too long. It took a lot of clues from the reddit discussion for this problem to home in on a solution.

0rac1e has the most concise solution for Raku that I have seen:

https://www.reddit.com/r/adventofcode/comments/kc4njx/2020_day_13_solutions/gfvy1u0?utm_source=share&utm_medium=web2x&context=3

  # my @bus-ids = '7,13,x,x,59,x,31,19'.split(',');

  my @input = '13-input.txt'.IO.lines;
  @input.shift;
  my @bus-ids = @input.shift.split(',');

  my @buses = do for ^@bus-ids.elems -> $i {
      [@bus-ids[$i], (@bus-ids[$i] - $i) % @bus-ids[$i] ] if @bus-ids[$i] ne 'x'
  }

  say @buses;

  my $result = 0;
  my $increment = 1;

  for @buses -> $bus {
      while $result % $bus[0] != $bus[1] {
          $result += $increment;
      }
      $increment *= $bus[0];
      say $result;
  }
[[23 0] [41 28] [647 624] [13 11] [19 15] [29 6] [557 503] [37 14] [17 14]]
0
69
535693
4806540
4806540
1361105523
700608581203
56688479899556
867295486378319
raku 
comments powered by Disqus