Day 11

Section

defmodule Day11 do
  def parse(input, _relief_divider) do
    input
    |> String.split("\n\n", trim: true)
    |> Map.new(&parse_monkey/1)
  end

  defp parse_monkey(str) do
    [monkey, starting_items, operation, pred, on_true, on_false] =
      String.split(str, "\n", trim: true)

    "Monkey " <> monkey = monkey
    monkey = String.to_integer(String.trim_trailing(monkey, ":"))
    "Starting items: " <> starting_items = String.trim(starting_items)
    {starting_items, _} = Code.eval_string("[" <> starting_items <> "]")
    "Operation: new = " <> operation = String.trim(operation)

    {update, _} =
      Code.eval_string("""
      fn old ->
        #{operation}
      end
      """)

    "Test: divisible by " <> mod = String.trim(pred)
    mod = String.to_integer(mod)
    "If true: throw to monkey " <> true_monkey = String.trim(on_true)
    on_true = String.to_integer(true_monkey)
    "If false: throw to monkey " <> false_monkey = String.trim(on_false)
    on_false = String.to_integer(false_monkey)

    to_monkey = fn x ->
      if rem(x, mod) == 0 do
        on_true
      else
        on_false
      end
    end

    {monkey,
     %{
       items: starting_items,
       num_items: length(starting_items),
       update: update,
       to_monkey: to_monkey,
       remainder: mod
     }}
  end

  def part_1(input) do
    monkeys = parse(input, 3)

    {_, inspections} = run(20, monkeys, &amp;div(&amp;1, 3))

    inspections
    |> Map.values()
    |> Enum.sort(:desc)
    |> Enum.take(2)
    |> Enum.product()
  end

  defp run(max_rounds, monkeys, relief_fn) do
    n_monkeys = map_size(monkeys)
    inspections = Map.new(0..(n_monkeys - 1), &amp;{&amp;1, 0})

    for round <- 1..max_rounds,
        monkey <- 0..(n_monkeys - 1),
        reduce: {monkeys, inspections} do
      {monkeys, inspections} ->
        if monkey == 0 and rem(round, 100) == 0 do
          IO.puts("Round: #{round} [#{Time.utc_now()}]")
        end

        data = Map.fetch!(monkeys, monkey)

        items =
          data.items
          |> Enum.map(fn item ->
            new = item |> then(data.update) |> then(relief_fn)
            {new |> then(data.to_monkey), new}
          end)

        monkeys = Map.put(monkeys, monkey, %{data | items: [], num_items: 0})

        inspections = Map.update(inspections, monkey, 0, &amp;(&amp;1 + data.num_items))

        monkeys =
          items
          |> Enum.reduce(monkeys, fn {dest, new}, acc ->
            d = Map.fetch!(acc, dest)
            d = %{d | items: [d.items, new], num_items: d.num_items + 1}
            Map.put(acc, dest, d)
          end)
          |> Map.new(fn {k, v} ->
            {k, %{v | items: List.flatten(v.items)}}
          end)

        {monkeys, inspections}
    end
  end

  def part_2(input) do
    monkeys = parse(input, 1)

    # after _LOTS_ of debugging, turned out that the remainder of a big number
    # over a smaller divisor takes lots of time. This trick relies on the fact
    # that rem(rem(x, a * b * ...), a) == rem(x, a), so we can "modulate" the
    # number to a smaller value before taking the actual small remainder
    relief_mod = monkeys |> Map.values() |> get_in([Access.all(), :remainder]) |> Enum.product()

    {_, inspections} = run(10000, monkeys, &amp;rem(&amp;1, relief_mod))

    inspections
    |> Map.values()
    |> Enum.sort(:desc)
    |> Enum.take(2)
    |> Enum.product()
  end
end

test_input = """
Monkey 0:
  Starting items: 79, 98
  Operation: new = old * 19
  Test: divisible by 23
    If true: throw to monkey 2
    If false: throw to monkey 3

Monkey 1:
  Starting items: 54, 65, 75, 74
  Operation: new = old + 6
  Test: divisible by 19
    If true: throw to monkey 2
    If false: throw to monkey 0

Monkey 2:
  Starting items: 79, 60, 97
  Operation: new = old * old
  Test: divisible by 13
    If true: throw to monkey 1
    If false: throw to monkey 3

Monkey 3:
  Starting items: 74
  Operation: new = old + 3
  Test: divisible by 17
    If true: throw to monkey 0
    If false: throw to monkey 1
"""

parsed = Day11.parse(test_input, 3)

[19, 8, 9, 7] = Enum.with_index(Map.values(parsed), fn x, idx -> x.update.(idx + 1) end)
[3, 0, 3, 1] = Enum.with_index(Map.values(parsed), fn x, idx -> x.to_monkey.(idx + 1) end)

[2, 2, 1, 0] =
  Enum.zip_with([Map.values(parsed), [23, 19, 13, 17]], fn [x, input] -> x.to_monkey.(input) end)

parsed

Day11.part_1(test_input)

input = File.read!("day11_input.txt")

Day11.part_1(input)

Day11.part_2(test_input)

Day11.part_2(input)