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

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:

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