Advent of Code 2020 - Day 13

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

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)

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:

https://github.com/code-shoily/advent_of_code/blob/master/lib/helpers/chinese_remainder.ex

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

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))

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

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

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.

https://github.com/Damirados/AoC/blob/master/lib/Y2020/event13.ex

Beautiful!

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]

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