Day 13 - Advent of Code 2020

# Mix.install([:kino, :benchee])

Links

• Advent of Code (AoC)
• AoC Puzzle Input
• tylerj GitHub - Code
• tylerj GitHub - Livebook

Prompt

— Day 13: Shuttle Search —

Your ferry can make it safely to a nearby port, but it won’t get much further. When you call to book another ship, you discover that no ships embark from that port to your vacation island. You’ll need to get from the port to the nearest airport.

Fortunately, a shuttle bus service is available to bring you from the sea port to the airport! Each bus has an ID number that also indicates how often the bus leaves for the airport.

Bus schedules are defined based on a timestamp that measures the number of minutes since some fixed reference point in the past. At timestamp 0, every bus simultaneously departed from the sea port. After that, each bus travels to the airport, then various other locations, and finally returns to the sea port to repeat its journey forever.

The time this loop takes a particular bus is also its ID number: the bus with ID 5 departs from the sea port at timestamps 0, 5, 10, 15, and so on. The bus with ID 11 departs at 0, 11, 22, 33, and so on. If you are there when the bus departs, you can ride that bus to the airport!

Your notes (your puzzle input) consist of two lines. The first line is your estimate of the earliest timestamp you could depart on a bus. The second line lists the bus IDs that are in service according to the shuttle company; entries that show x must be out of service, so you decide to ignore them.

To save time once you arrive, your goal is to figure out the earliest bus you can take to the airport. (There will be exactly one such bus.)

For example, suppose you have the following notes:

939
7,13,x,x,59,x,31,19

Here, the earliest timestamp you could depart is 939, and the bus IDs in service are 7, 13, 59, 31, and 19. Near timestamp 939, these bus IDs depart at the times marked D:

time   bus 7   bus 13  bus 59  bus 31  bus 19
929      .       .       .       .       .
930      .       .       .       D       .
931      D       .       .       .       D
932      .       .       .       .       .
933      .       .       .       .       .
934      .       .       .       .       .
935      .       .       .       .       .
936      .       D       .       .       .
937      .       .       .       .       .
938      D       .       .       .       .
939      .       .       .       .       .
940      .       .       .       .       .
941      .       .       .       .       .
942      .       .       .       .       .
943      .       .       .       .       .
944      .       .       D       .       .
945      D       .       .       .       .
946      .       .       .       .       .
947      .       .       .       .       .
948      .       .       .       .       .
949      .       D       .       .       .

The earliest bus you could take is bus ID 59. It doesn’t depart until timestamp 944, so you would need to wait 944 - 939 = 5 minutes before it departs. Multiplying the bus ID by the number of minutes you’d need to wait gives 295.

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?

To begin, get your puzzle input.

— Part Two —

The shuttle company is running a contest: one gold coin for anyone that can find the earliest timestamp such that the first bus ID departs at that time and each subsequent listed bus ID departs at that subsequent minute. (The first line in your input is no longer relevant.)

For example, suppose you have the same list of bus IDs as above:

7,13,x,x,59,x,31,19

An x in the schedule means there are no constraints on what bus IDs must depart at that time.

This means you are looking for the earliest timestamp (called t) such that:

• Bus ID 7 departs at timestamp t.
• Bus ID 13 departs one minute after timestamp t.
• There are no requirements or restrictions on departures at two or three minutes after timestamp t.
• Bus ID 59 departs four minutes after timestamp t. There are no requirements or restrictions on departures at five minutes after timestamp t.
• Bus ID 31 departs six minutes after timestamp t.
• Bus ID 19 departs seven minutes after timestamp t.

The only bus departures that matter are the listed bus IDs at their specific offsets from t. Those bus IDs can depart at other times, and other bus IDs can depart at those times. For example, in the list above, because bus ID 19 must depart seven minutes after the timestamp at which bus ID 7 departs, bus ID 7 will always also be departing with bus ID 19 at seven minutes after timestamp t.

In this example, the earliest timestamp at which this occurs is 1068781:

time     bus 7   bus 13  bus 59  bus 31  bus 19
1068773    .       .       .       .       .
1068774    D       .       .       .       .
1068775    .       .       .       .       .
1068776    .       .       .       .       .
1068777    .       .       .       .       .
1068778    .       .       .       .       .
1068779    .       .       .       .       .
1068780    .       .       .       .       .
1068781    D       .       .       .       .
1068782    .       D       .       .       .
1068783    .       .       .       .       .
1068784    .       .       .       .       .
1068785    .       .       D       .       .
1068786    .       .       .       .       .
1068787    .       .       .       D       .
1068788    D       .       .       .       D
1068789    .       .       .       .       .
1068790    .       .       .       .       .
1068791    .       .       .       .       .
1068792    .       .       .       .       .
1068793    .       .       .       .       .
1068794    .       .       .       .       .
1068795    D       D       .       .       .
1068796    .       .       .       .       .
1068797    .       .       .       .       .

In the above example, bus ID 7 departs at timestamp 1068788 (seven minutes after t). This is fine; the only requirement on that minute is that bus ID 19 departs then, and it does.

Here are some other examples:

• The earliest timestamp that matches the list 17,x,13,19 is 3417.
• 67,7,59,61 first occurs at timestamp 754018.
• 67,x,7,59,61 first occurs at timestamp 779210.
• 67,7,x,59,61 first occurs at timestamp 1261476.
• 1789,37,47,1889 first occurs at timestamp 1202161486.

However, with so many bus IDs in your list, surely the actual earliest timestamp will be larger than 100000000000000!

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

Although it hasn’t changed, you can still get your puzzle input.

Input

input = Kino.Input.textarea("Please paste your input file:")

input = input |> Kino.Input.read()
input = AdventOfCode.Input.get!(13, 2020)

"1001287\n13,x,x,x,x,x,x,37,x,x,x,x,x,461,x,x,x,x,x,x,x,x,x,x,x,x,x,17,x,x,x,x,19,x,x,x,x,x,x,x,x,x,29,x,739,x,x,x,x,x,x,x,x,x,41,x,x,x,x,x,x,x,x,x,x,x,x,23\n"

Solution

defmodule Day13 do
  defdelegate parse(input), to: __MODULE__.Input

  def part1(input) do
    {start_time, buses} = parse(input)

    {id, departure} =
      buses
      |> Enum.reject(&(&1 == "x"))
      |> Enum.map(fn id ->
        {id, (div(start_time, id) + 1) * id}
      end)
      |> Enum.min_by(fn {_, departure} -> departure end)

    id * (departure - start_time)
  end

  def part2(input) do
    input
    |> parse()
    |> elem(1)
    |> Enum.with_index()
    |> Enum.filter(fn {x, _} -> x != "x" end)
    |> then(fn [{bus_id, 0} | tail] ->
      solve(bus_id, bus_id, tail)
    end)
  end

  def solve(ts, _, []), do: ts

  def solve(ts, jump, [{b, i} | tail]) when rem(ts + i, b) == 0 do
    solve(ts, jump * b, tail)
  end

  def solve(ts, jump, list) do
    solve(ts + jump, jump, list)
  end

  defmodule Input do
    def parse(input) when is_binary(input) do
      with [a, b] <- String.split(input, "\n", trim: true) do
        {String.to_integer(a), parse_line(b)}
      end
    end

    def parse_line(line) do
      line
      |> String.split(",", trim: true)
      |> Enum.map(fn
        "x" -> "x"
        y -> String.to_integer(y)
      end)
    end
  end
end

{:module, Day13, <<70, 79, 82, 49, 0, 0, 14, ...>>,
 {:module, Day13.Input, <<70, 79, 82, ...>>, {:parse_line, 1}}}

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?

Your puzzle answer was 2305.

Day13.part1(input)

2305

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

Your puzzle answer was 552612234243498.

Day13.part2(input)

552612234243498

Both parts of this puzzle are complete! They provide two gold stars: **

At this point, you should return to your Advent calendar and try another puzzle.

If you still want to see it, you can get your puzzle input.

Tests

ExUnit.start(auto_run: false)

defmodule Day13Test do
  use ExUnit.Case, async: false

  setup_all do
    [
      input: "939\n7,13,x,x,59,x,31,19"
    ]
  end

  describe "part1/1" do
    test "returns expected value", %{input: input} do
      assert Day13.part1(input) == 295
    end
  end

  describe "part2/1" do
    test "returns expected value", %{input: input} do
      assert Day13.part2(input) == 1_068_781
    end
  end
end

ExUnit.run()

..
Finished in 0.00 seconds (0.00s async, 0.00s sync)
2 tests, 0 failures

Randomized with seed 467860

%{total: 2, failures: 0, excluded: 0, skipped: 0}

Benchmarking

# https://github.com/bencheeorg/benchee
Benchee.run(
  %{
    "Part 1" => fn -> Day13.part1(input) end,
    "Part 2" => fn -> Day13.part2(input) end
  },
  memory_time: 2,
  reduction_time: 2
)

nil

Warning: the benchmark Part 1 is using an evaluated function.
  Evaluated functions perform slower than compiled functions.
  You can move the Benchee caller to a function in a module and invoke `Mod.fun()` instead.
  Alternatively, you can move the benchmark into a benchmark.exs file and run mix run benchmark.exs

Warning: the benchmark Part 2 is using an evaluated function.
  Evaluated functions perform slower than compiled functions.
  You can move the Benchee caller to a function in a module and invoke `Mod.fun()` instead.
  Alternatively, you can move the benchmark into a benchmark.exs file and run mix run benchmark.exs

Operating System: macOS
CPU Information: Apple M1 Pro
Number of Available Cores: 10
Available memory: 32 GB
Elixir 1.15.6
Erlang 26.1

Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 2 s
reduction time: 2 s
parallel: 1
inputs: none specified
Estimated total run time: 22 s

Benchmarking Part 1 ...
Benchmarking Part 2 ...

Name             ips        average  deviation         median         99th %
Part 1      263.15 K        3.80 μs   ±256.87%        3.67 μs        4.67 μs
Part 2      175.96 K        5.68 μs   ±110.72%        5.54 μs        7.29 μs

Comparison: 
Part 1      263.15 K
Part 2      175.96 K - 1.50x slower +1.88 μs

Memory usage statistics:

Name      Memory usage
Part 1         2.31 KB
Part 2         4.42 KB - 1.91x memory usage +2.11 KB

**All measurements for memory usage were the same**

Reduction count statistics:

Name   Reduction count
Part 1          0.76 K
Part 2          1.31 K - 1.73x reduction count +0.56 K

**All measurements for reduction count were the same**

nil