Advent of Code 2020 - Day 13

Aetherus · December 13, 2020, 5:08am

Hello, guys. I’m back again, but only for the weekends, maybe.

This topic is about Day 13 of the Advent of Code 2020 .

Thanks to @egze, we have a private leaderboard:
https://adventofcode.com/2020/leaderboard/private/view/39276

The join code is:
39276-eeb74f9a

code-shoily · December 13, 2020, 6:57am

I am stuck at part 2 of this one, trying to use Chinese Remainder Theorem but for some reason getting the mods messed up, whether to go backwards or something like (v - idx)… ekh, I guess I’m just tired, will try tomorrow

Meanwhile, my not so sophisticated part 1:

defmodule AdventOfCode.Y2020.Day13 do
  @moduledoc """
  Problem Link: https://adventofcode.com/2020/day/13
  """
  use AdventOfCode.Helpers.InputReader, year: 2020, day: 13

  def run_1, do: input!() |> process() |> earliest_bus() |> result()
  def run_2, do: {:not_implemented, 2}

  def process(input \\ input!()) do
    [time, ids] = String.split(input, "\n", trim: true)

    {String.to_integer(time),
     ids |> String.split(",") |> Enum.reject(&(&1 == "x")) |> Enum.map(&String.to_integer/1)}
  end

  defp next_departure(id, time) do
    next_departure = (div(time, id) + 1) * id
    {id, next_departure, next_departure - time}
  end

  defp earliest_bus({time, ids}) do
    Enum.min_by(Enum.map(ids, &next_departure(&1, time)), &elem(&1, 2))
  end

  defp result({id, _, diff}), do: id * diff
end

Aetherus · December 13, 2020, 7:26am

I’m stuck at Part 2, too. Chinese Remainder Theorem looks interesting.

So far, my Part 1 code:

#!/usr/bin/env elixir

[departure, busses] = "day13.txt"
                      |> File.stream!()
                      |> Enum.map(&String.trim/1)

departure = String.to_integer(departure)

id = busses
     |> String.split(",")
     |> Stream.reject(& &1 == "x")
     |> Stream.map(&String.to_integer/1)
     |> Enum.min_by(& &1 - rem(departure, &1))

wait = id - rem(departure, id)

IO.puts(id * wait)

code-shoily · December 13, 2020, 7:43am

Ekh, I could not sleep without trying out Chinese Remainder Theorem. It works!!! Though I cheated. I did not have the energy to remember the details of algorithm and try to implement in Elixir, so I Rosetta Coded it and the Elixir version there was brute forced, so Nope. So I translated the Erlang version there into Elixir (which in turn was translated from OCaml) and Bam! it worked and performed well. Here’s my CRT:

github.com

code-shoily/advent_of_code/blob/master/lib/helpers/chinese_remainder.ex

defmodule AdventOfCode.Helpers.ChineseRemainder do
  def chinese_remainder(congruences) do
    {modulii, residues} = Enum.unzip(congruences)
    mod_pi = List.foldl(modulii, 1, &Kernel.*/2)
    crt_modulii = for m <- modulii, do: div(mod_pi, m)

    case calc_inverses(crt_modulii, modulii) do
      nil ->
        nil

      inverses ->
        solution =
          Enum.sum(
            for {a, b} <-
                  Enum.zip(crt_modulii, for({a, b} <- Enum.zip(residues, inverses), do: a * b)),
                do: a * b
          )

        mod(solution, mod_pi)
    end

This file has been truncated. show original

And the relevant bits of the main code:

defmodule Day13 do
  def run_2, do: input!() |> process_2() |> compute()
  def process_2(input \\ input!()) do
    input
    |> String.split("\n", trim: true)
    |> Enum.at(-1)
    |> String.split(",")
    |> Enum.with_index()
    |> Enum.reject(fn {x, _} -> x == "x" end)
    |> Enum.map(fn {x, y} -> {String.to_integer(x), y} end)
  end

  def compute(list) do
    list
    |> Enum.map(fn {v, idx} -> {v, v - idx} end)
    |> chinese_remainder()
  end
end

Also I realized, my “read Erlang, write Elixir” speed is more than I thought it would be, it’s almost typing speed level

Aetherus · December 13, 2020, 8:33am

I Wiki’ed the Chinese Remainder Theorem and hand-coded the sieving approach. It worked on the example input, but was deadly slow on the true input. I guess I’ll go the Rosetta way, too.

#!/usr/bin/env elixir

defmodule ChineseRemainderTheorem do
  def sieve({x1, n1}, {a2, n2}) do
    x2 = x1
         |> Stream.unfold(fn x -> {x, x + n1} end)
         |> Enum.find(fn x -> rem(x, n2) == a2 end)
    {x2, n1 * n2}
  end
end


ids_and_rems = "day13.txt"
               |> File.stream!()
               |> Stream.map(&String.trim/1)
               |> Enum.take(2)
               |> List.last()
               |> String.split(",")
               |> Stream.with_index()
               |> Stream.reject(&elem(&1, 0) == "x")
               |> Stream.map(fn{id, i} -> {String.to_integer(id), i} end)
               |> Enum.map(fn{id, i}->{rem(id - i, id), id} end)
               |> Enum.sort_by(&elem(&1, 0))
               |> Enum.reverse()

ids_and_rems
|> Enum.reduce(&ChineseRemainderTheorem.sieve(&2, &1))
|> IO.inspect()

UPDATE

I implemented the same sieving approach in Ruby, and it finished in 0.15s. I wonder why Elixir is so much slower than Ruby.

Here’s the Ruby code:

#!/usr/bin/env ruby
ids_and_rems = File.readlines('day13.txt')[1]
  .split(',')
  .each_with_index
  .reject{|id, i| id == 'x'}
  .map{|id, i| [id.to_i, i]}
  .map{|id, i| [(id - i) % id, id]}
  .sort_by(&:first)
  .reverse

def sieve(pair1, pair2)
  x1, n1 = pair1
  a2, n2 = pair2
  x = x1
  x2 = loop do
    break x if x % n2 == a2
    x += n1
  end
  [x2, n1 * n2]
end

p ids_and_rems.reduce(&method(:sieve))

voltone · December 13, 2020, 9:13am

My part 2 runs in 64µs:

  def next_sequence(busses) do
    busses
    |> Enum.with_index()
    |> Enum.reduce({0, 1}, &add_to_sequence/2)
    |> elem(0)
  end

  defp add_to_sequence({"x", _index}, state), do: state
  defp add_to_sequence({bus, index}, {t, step}) do
    if Integer.mod(t + index, bus) == 0 do
      {t, lcm(step, bus)}
    else
      add_to_sequence({bus, index}, {t + step, step})
    end
  end

  defp lcm(a, b) do
    div(a * b, Integer.gcd(a, b))
  end

cblavier · December 13, 2020, 10:55am

Really clever. I was playing with lcm but could not figure out how

Damirados · December 13, 2020, 11:23am

Took me hours and few papers to figure out LCM should raise period of steps, not sleeping for more than 30 hours didn’t help either.

github.com

Damirados/AoC/blob/master/lib/Y2020/event13.ex

defmodule Y2020.Event13 do
  def run do
    IO.puts("Test part1: #{part1("input/Y2020/event13/test.txt")}")
    IO.puts("Puzzle part1: #{part1("input/Y2020/event13/puzzle.txt")}")
    IO.puts("Test part2: #{part2("input/Y2020/event13/test.txt", 0)}")
    IO.puts("Puzzle part2: #{part2("input/Y2020/event13/puzzle.txt", 170_000_000_000_000)}")
  end

  def part1(path), do: find_earliest_id(get_input(path))
  def part2(path, start_point), do: find_cascading_ts(get_input(path) |> elem(1), start_point)

  def get_input(path) do
    input_stream = File.stream!(path)
    ts = Enum.take(input_stream, 1) |> List.first() |> String.trim() |> String.to_integer()

    ids =
      input_stream
      |> Stream.drop(1)
      |> Enum.take(1)
      |> List.first()

This file has been truncated. show original

kwando · December 13, 2020, 1:41pm

Beautiful!

Papey · December 13, 2020, 1:49pm

Here is my naive part 2, it’s a brute force that gets the job done really fast

  def run2(test \\ false) do
    [_, buses] =
      get_input("D13", test)
      |> split_input()

    {schedule, _} =
      String.split(buses, ",")
      |> Enum.reduce({%{}, 0}, fn v, {schedule, count} ->
        if v == "x" do
          {schedule, count + 1}
        else
          {Map.put(schedule, String.to_integer(v), count), count + 1}
        end
      end)

    Enum.reduce(schedule, {1, 1}, fn {l, t}, {min, product} ->
      [res] =
        Stream.iterate(min, &(&1 + product))
        |> Stream.drop_while(fn v ->
          rem(v + t, l) != 0
        end)
        |> Enum.take(1)

      {res, product * l}
    end)
  end

:timer.tc(fn -> AOC.D13.run2() end)
{1049, {_, _}}

I use the fact that, since they are all prime numbers,

CGD(p, q) = 1, then if a = 0 [p] and a = 0 [q], then a = 0 [pq]

And i’m searching for a = 0 [l0…ln]

LostKobrakai · December 13, 2020, 2:40pm

This is genius. I’m not sure how I would ever have come to something like that. I knew lcm would be somehow needed but the offsets blew anything I could think of out of the window. I’ve inlined the actual calculation I adapted from yours, so it’s no longer manually recursive and hopefully a bit simpler in what happens:

    String.split(list, ",", trim: true)
    |> Enum.with_index()
    |> Enum.reject(fn {id, _} -> id == "x" end)
    |> Enum.reduce({0, 1}, fn {bus, index}, {t, step} ->
      bus = String.to_integer(bus)

      t =
        Stream.unfold(t, fn t -> {t, t + step} end)
        |> Stream.filter(fn t -> rem(t + index, bus) == 0 end)
        |> Enum.at(0)

      {t, lcm(step, bus)}
    end)
    |> elem(0)
  end

stevensonmt · December 13, 2020, 5:39pm

I too knew LCM was part of the key but was not able to figure out how to utilize it correctly. It doesn’t make any appreciable difference, but I made use of the hint that the answer would be at least 100_000_000_000_000 to start counting from 100000000000000 + rem(100000000000000, first_bus).

defmodule Day13 do
  @moduledoc false

  @input "1001287
  13,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"

  def process() do
    @input
    |> String.split("\n", parts: 2, trim: true)
    |> Enum.with_index()
    |> Enum.reduce({}, fn {sub, ndx}, acc ->
      case ndx do
        0 ->
          Tuple.append(acc, String.to_integer(sub))

        _ ->
          Tuple.append(
            acc,
            sub
            |> String.trim_leading()
            |> String.split(",")
            |> Enum.filter(&Kernel.!=("x", &1))
            |> Enum.map(&String.to_integer(&1))
          )
      end
    end)
  end

  def shortest_wait(timestamp, bus_list) do
    {bus, wait} =
      bus_list
      |> Enum.map(fn x -> {x, x - rem(timestamp, x)} end)
      |> Enum.min_by(fn {_x, wait} -> wait end)

    bus * wait
  end

  def part_1 do
    {timestamp, bus_list} = process()
    shortest_wait(timestamp, bus_list)
  end

  def process_2 do
    @input
    |> String.split("\n", parts: 2, trim: true)
    |> List.last()
    |> String.trim_leading()
    |> String.split(",")
    |> Enum.with_index()
    |> Enum.reject(fn {c, _ndx} -> c == "x" end)
    |> Enum.map(fn {c, ndx} -> {ndx, String.to_integer(c)} end)
  end

  def timestamp_search([{_ndx, first_bus} | _rest] = buses) do
    min_time = 100_000_000_000_000 + rem(100_000_000_000, first_bus)
    timestamp_search(buses, {min_time, 1})
  end

  def timestamp_search([], {timestamp, _}) do
    timestamp
  end

  def timestamp_search([{ndx, bus} | rest] = buses, {timestamp, step}) do
    if valid_timestamp?(timestamp, bus, ndx) do
      timestamp_search(rest, {timestamp, Day13.MathHelpers.lcm(step, bus)})
    else
      timestamp_search(buses, {timestamp + step, step})
    end
  end

  def valid_timestamp?(timestamp, bus, ndx) do
    rem(timestamp + ndx, bus) == 0
  end

  def part_2 do
    process_2()
    |> timestamp_search()
  end

  defmodule MathHelpers do
    @moduledoc false
    def gcd(a, 0), do: a
    def gcd(0, b), do: b
    def gcd(a, b), do: gcd(b, rem(a, b))

    def lcm(0, 0), do: 0
    def lcm(a, b), do: div(a * b, gcd(a, b))
  end
end

faried · December 13, 2020, 5:54pm

It could use some cleanup…

defmodule Day13 do
  def readinput() do
    [start, busdata] =
      File.read!("13.input.txt")
      |> String.split("\n", trim: true)

    [String.to_integer(start), String.split(busdata, ",")]
  end

  def part1([start, buses] \\ readinput()) do
    buses =
      buses
      |> Enum.filter(&(&1 != "x"))
      |> Enum.map(&String.to_integer/1)

    bus =
      Enum.map(buses, fn bus -> {bus, bus - rem(start, bus)} end)
      |> Enum.min(fn {_b1, t1}, {_b2, t2} -> t1 < t2 end)

    elem(bus, 0) * elem(bus, 1)
  end

  def part2([_, buses] \\ readinput()) do
    buses =
      buses
      |> Enum.map(fn b -> if b != "x", do: String.to_integer(b), else: "x" end)
      |> Enum.with_index()
      |> Enum.filter(fn {b, _} -> b != "x" end)

    first =
      buses
      |> List.first()
      |> elem(0)

    loop(buses, first)
  end

  def loop(buses, time) do
    mods =
      buses
      |> Enum.map(fn {b, offset} -> rem(time + offset, b) end)

    if Enum.all?(mods, &(&1 == 0)) do
      time
    else
      # does too much work
      step =
        mods
        |> Enum.with_index()
        # find indexes in mod list where the mod was 0
        |> Enum.filter(fn {v, _i} -> v == 0 end)
        # use the indexes to find the bus times that resulted in mod 0
        |> Enum.map(fn {_v, i} -> Enum.at(buses, i) |> elem(0) end)
        |> Enum.reduce(1, &Kernel.*/2)

      loop(buses, time + step)
    end
  end
end

mruoss · December 13, 2020, 6:44pm

I noticed the bus ids all being primes so lcm(x,y) == x*y. So basically I search through the remaining list of buses by incrementing the timestamp by a certain value, starting with the first bus’ id. Whenever one of the remaining buses fulfills the requirement, I multiply the incrementor by that bus’ id.
Finds the timesramp very quickly.

github.com

mruoss/advent_of_code_2020/blob/master/lib/aoc_2020/day13/solver.ex

defmodule AOC2020.Day13.Solver do

  def solve(input, :first) do
    {ts, bus_ids} = parse(input)

    {bus, minutes} = bus_ids
    |> Enum.map(fn {bus_id, _} -> {bus_id, bus_id - rem(ts, bus_id)} end)
    |> Enum.min(fn {_, x}, {_, y} -> x <= y end)

    bus * minutes
  end

  def solve(input, :second) do
    {_,  [{first_bus, _} | rest]} = parse(input)
    find_sequence(rest, first_bus, first_bus)
  end

  defp find_sequence(bus_ids, current, inc) do
    case Enum.find(bus_ids, fn {bus_id, shift} -> rem(current + shift, bus_id) == 0 end) do
      nil -> find_sequence(bus_ids, current + inc, inc)

This file has been truncated. show original

adamu · December 13, 2020, 11:57pm

Another tough one. I couldn’t solve it and decided not to dwell more than a day on each question. Turns out not having the star bothers me though . Chinese remainder theory, eh? Will have to come back to this one after doing some reading (and avoid peeking at the answers above).

ricardo-h · December 14, 2020, 2:15am

part1 - O(n)

part2 - brute force with step by max_bus_id didnt print any result after ~1 hr - chinese remainder theorem (this is new for me) works only with prime numbers but the statement does not guarantee that bus-IDs will always be prime

part 1

defmodule Advent.Day13 do

  def start(file \\ "/tmp/input.txt"), do: File.read!(file) |> String.split(["\n", ","], trim: true) |> find_bus() |> elem(2)

  def find_bus([time|lst_bus_id]), do: Enum.reduce(lst_bus_id, {String.to_integer(time), -1, 0}, &calculate_time/2)

  defp calculate_time("x", acc), do: acc
  defp calculate_time(id, acc) when is_binary(id), do: calculate_time(String.to_integer(id), acc)
  defp calculate_time(id, acc), do: calculate_time(id, acc, (id - rem(elem(acc, 0), id)))
  defp calculate_time(id, {time, min_wait_time, _best_result}, m) when m < min_wait_time or min_wait_time < 0, do: {time, m, id * m}
  defp calculate_time(_, acc, _), do: acc

end

adamu · December 15, 2020, 4:26pm

Gave up and used this after my brute force still didn’t complete after two hours. Now to just understand it…

Thanks for sharing

voltone · December 15, 2020, 4:46pm

It starts off with zero busses, meaning t=0 is a valid solution, and the ‘step’ to get to the next valid solution is 1. That’s why the initial accumulator is {0, 1}.

Then it adds one bus at a time: it checks if the new bus leaves at required number of minutes after the current candidate t:

If yes, it determines the new step value (the LCM of the previous step value and the current bus interval); it then moves on to the next bus.
If no, it moves t to the next time when all the previous busses line up and tries again

davearonson · December 17, 2020, 6:17pm

Part 2 was a real bear (especially before I twigged that some indices were greater than the bus line id!) until I hit on the “sieving” idea with increasing jumps, and then it became crystal clear, as the below find_ordered_timestamp:

defmodule Day13 do
  @input  """
          1000001
          29,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,41,x,x,x,x,x,x,x,x,x,577,x,x,x,x,x,x,x,x,x,x,x,x,13,17,x,x,x,x,19,x,x,x,23,x,x,x,x,x,x,x,601,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,37
          """
          |> String.trim
          |> String.split("\n")

  def part1() do
    [min_depart_str, ids_str] = @input
    min_depart = String.to_integer(min_depart_str)
    ids =
      ids_str
      |> String.split(",")
      |> Enum.reject(fn(x) -> x == "x" end)
      |> Enum.map(&String.to_integer/1)
    {best_wait, best_id} =
      ids
      |> Enum.map(&(&1 - rem(min_depart, &1)))
      |> Enum.zip(ids)
      |> Enum.min_by(fn({wait,_id}) -> wait end)
    best_wait * best_id
  end

  def part2() do
    pairs =
      @input
      |> List.last
      |> String.split(",")
      |> Enum.map(&(if &1 == "x", do: &1, else: String.to_integer(&1)))
      |> Enum.with_index
      |> Enum.reject(fn(item) -> elem(item, 0) == "x" end)
      |> Enum.sort
      |> Enum.reverse
    # set up the first one for instant success
    {line, index} = hd(pairs)
    find_ordered_timestamp(pairs, 1, line - index)
  end

  defp find_ordered_timestamp(pairs = [{line,index}|rest], jump, candidate) do
    if rem(candidate + index, line) == 0 do
      # try SAME candidate again Just In Case it also works for next line
      find_ordered_timestamp(rest, jump * line, candidate)
    else
      find_ordered_timestamp(pairs, jump, candidate + jump)
    end
  end
  defp find_ordered_timestamp([], _, candidate), do: candidate
end