Advent of Code 2022 - Day 11

Monkeys fitted squarely as GenServers in my head. My initial problem was using cast instead of call; I imagine impolite monkeys slinging bananas at each other as fast as they can. (At the end I’m still not sure whether this {:global, ".."}) naming strategy is idiomatic.)

For part 2, I hard-coded the @monkey_factor to assuage my worry level, and then it is otherwise exactly the same as part 1. There must be some less literal way of going about this, so I’m looking forward to seeing other solutions!

Main module

defmodule Day11Monkeys do
@moduledoc “”"
Documentation for Day11Monkeys.
“”"

  def part_2(input \\ "test") do
    notes =
      input
      |> load_notes()
      |> Enum.map(&parse_note/1)

    monkeys =
      for note <- notes do
        monkey_name = note[:monkey] |> Integer.to_string()
        {:ok, _pid} = Monkey.start_link(note, {:global, monkey_name})
        monkey_name
      end

    # simulate rounds
    for round <- 1..10_000 do
      IO.inspect "round #{round}"
      for monkey <- monkeys do
        for _item <- Monkey.get_items(monkey) do
          Monkey.inspect_item(monkey)
        end
      end
    end

    [top, second] =
      for monkey <- monkeys do
        Monkey.get_inspections(monkey)
      end
      |> Enum.sort(:desc)
      |> Enum.slice(0..1)

    top * second
  end

  def data_path(input), do:
    Path.expand "./priv/#{input}.txt"

  def load_notes(input) do
    input
    |> data_path()
    |> File.stream!()
    |> Stream.map(&String.trim/1)
    |> Enum.chunk_every(7)
    |> Enum.map(fn lines ->
        if lines |> Enum.at(-1) == "" do
          Enum.drop(lines, -1)
        else
          lines
        end
      end)
  end

  def parse_note(raw_note) do
    [
      "Monkey " <> monkey,
      "Starting items:" <> items,
      "Operation: new = old " <> operation,
      "Test: divisible by " <> test,
      "If true: throw to monkey " <> true_throw,
      "If false: throw to monkey " <> false_throw
    ] = raw_note

    %{
      monkey: monkey |> String.slice(0..-2) |> String.to_integer(),
      items: items
              |> String.split(",")
              |> Enum.map(fn item ->
                item |> String.trim() |> String.to_integer
              end),
      operation: to_function(operation),
      test_divisibility: test |> String.to_integer,
      throw_if_true: true_throw,
      throw_if_false: false_throw,
      inspections: 0
    }
  end

  def to_function("+" <> num_as_string) do
    number = num_as_string |> String.trim() |> String.to_integer()

    fn value -> (value + number) end
  end
  def to_function("* old") do
    fn value -> (value * value) end
  end
  def to_function("*" <> num_as_string) do
    number = num_as_string |> String.trim() |> String.to_integer()

    fn value -> (value * number) end
  end

end
Monkey GenServer
defmodule Monkey do
  use GenServer

  @monkey_factor 17 * 5 * 11 * 13 * 3 * 19 * 2 * 7
  # Sample monkey:
  # [
  #   %{
  #     items: [54, 65, 75, 74],
  #     monkey: 1,
  #     operation: #Function<3.79865354/1 in Day11Monkeys.to_function/1>,
  #     test_divisibility: 19,
  #     throw_if_false: 0,
  #     throw_if_true: 2
  #   }
  # ]

  # CLIENT
  def start_link(monkey, name \\ __MODULE__) do
    # you may want to register your server with `name: __MODULE__`
    # as a third argument to `start_link`
    GenServer.start_link(__MODULE__, monkey, name: name)
  end

  def get_state(server), do:
    GenServer.call({:global, server}, :state)

  def get_items(server), do:
    GenServer.call({:global, server}, :items)

  def get_inspections(server), do:
    GenServer.call({:global, server}, :inspections)

  def inspect_item(server), do:
    GenServer.call({:global, server}, :inspect_item, 200_000)

  def throw_to(server, item), do:
    GenServer.call({:global, server}, {:add_item_to_end, item})

  # SERVER
  @impl true
  def init(monkey) do
    {:ok, monkey}
  end

  @impl true
  def handle_call(:state, _from, state) do
    {:reply, state, state}
  end

  @impl true
  def handle_call(:items, _from, state) do
    items = Map.get(state, :items)
    {:reply, items, state}
  end

  @impl true
  def handle_call(:inspections, _from, state) do
    inspections = Map.get(state, :inspections)
    {:reply, inspections, state}
  end

  @impl true
  def handle_call(:inspect_item, _from, state) do
    %{
      monkey: monkey,
      items: items,
      operation: operation,
      test_divisibility: test_divisibility,
      throw_if_true: throw_if_true,
      throw_if_false: throw_if_false,
      inspections: inspections
    } = state
    [first | remainder] = items

    new_worry = first |> operation.() |> rem(@monkey_factor) # |> Kernel.div(3) # part 1

    IO.inspect new_worry

    if rem(new_worry, test_divisibility) == 0 do
      throw_to(throw_if_true, new_worry)
    else
      throw_to(throw_if_false, new_worry)
    end

    {
      :reply,
      "inspected",
      %{ state |
        items: remainder,
        inspections: inspections + 1
      }
    }
  end

  @impl true
  def handle_call({:add_item_to_end, item}, _from, state) do
    items = Map.get(state, :items)

    {
      :reply,
      "item thrown",
      %{ state |
        items: items ++ [item]
      }
    }
  end
end

Ain’t pretty, but it works. I did look up a hint for the part 2 “trick”.

The first one I wasn’t able to solve.

I also used GenServers for part 1, where each “throw” was a message between processes. Quite nice :slight_smile:

Part 2 I have no idea.

Runing behind and I don’t much like the look of Day 12 either :face_with_peeking_eye:. I’m probably done for AoC for this year. Thanks for the fun everyone. :christmas_tree::star::man_elf:

Same. I got part 1 pretty easily but part 2 is just not happening. I actually don’t understand how the code from @jkwchui and @deadbeef are able to handle part 2 successfully. I did refactor my parsing based on @jkwchui’s post b/c I thought it was really clever.

defmodule Day11 do
  defmodule Input do
    def sample_data() do
      """
      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
      """
    end

    def load() do
      AocHelper.load(2022, 11)
    end

    def parse(input) do
      input
      |> String.split("\n\n", trim: true)
      |> Enum.map(fn lines ->
        lines
        |> String.split("\n", trim: true)
        |> Enum.map(&String.trim_leading(&1))
        |> build_monkey()
      end)
      |> :array.from_list()
    end

    defp build_monkey(monkey_text) do
      [
        <<"Monkey ", monkey, ":">>,
        "Starting items: " <> items,
        "Operation: new = old " <> operation,
        "Test: divisible by " <> test,
        "If true: throw to monkey " <> true_throw,
        "If false: throw to monkey " <> false_throw
      ] = monkey_text

      %{
        id: monkey - 48,
        items: parse_items(items),
        op: parse_op(operation),
        test: test |> String.to_integer(),
        pos: String.to_integer(true_throw),
        neg: String.to_integer(false_throw)
      }
    end

    defp parse_items(items) do
      items
      |> String.split(", ", trim: true)
      |> Enum.map(&String.to_integer(&1))
    end

    defp parse_op(<<"+ ", addend::binary>>) do
      try do
        fn n -> n + String.to_integer(addend) end
      rescue
        _ -> fn n -> n + n end
      end
    end

    defp parse_op(<<"* ", factor::binary>>) do
      try do
        factor = String.trim_leading(factor) |> String.to_integer()
        fn n -> n * factor end
      rescue
        _ -> fn n -> n * n end
      end
    end
  end

  defmodule Monkeys do
    def simulate_rounds(n, troop, counters, with_relief?) do
      for _round <- 1..n,
          reduce: troop do
        t ->
          for monkey <- 0..(:array.sparse_size(troop) - 1),
              reduce: t do
            barrel -> simulate_round(barrel, monkey, counters, with_relief?)
          end
      end

      # 1..n
      # |> Enum.reduce(troop, fn _, barrel ->
      #   simulate_round(barrel, 0, counters, with_relief?)
      # end)
    end

    def simulate_round(troop, monkey, counters, with_relief?) do
      if monkey >= :array.sparse_size(troop) do
        troop
      else
        {items_to_throw, monkey_after_throwing} =
          :array.get(monkey, troop)
          |> Map.get_and_update!(:items, fn curr -> {curr, []} end)

        troop = :array.set(monkey, monkey_after_throwing, troop)

        items_to_throw
        |> Task.async_stream(fn item ->
          :counters.add(counters, monkey + 1, 1)
          inspected_and_bored = monkey_after_throwing.op.(item) |> maybe_relief(with_relief?)

          dest =
            if rem(inspected_and_bored, monkey_after_throwing.test) == 0 do
              monkey_after_throwing.pos
            else
              monkey_after_throwing.neg
            end

          {inspected_and_bored, dest}
        end)
        |> Enum.reduce(troop, fn {:ok, {item, dest}}, barrel ->
          throw(item, dest, barrel)
        end)
      end
    end

    def simulate_round_by_item({{item, curr_monkey}, ops, rules}, counters) do
      new_worry = ops[curr_monkey].(item)
      :counters.add(counters, curr_monkey + 1, 1)
      {rule, pos, neg} = rules[curr_monkey]

      new_monkey =
        if rem(new_worry, rule) == 0 do
          pos
        else
          neg
        end

      new_item = {new_worry, new_monkey}

      if new_monkey > curr_monkey do
        simulate_round_by_item({new_item, ops, rules}, counters)
      else
        new_item
      end
    end

    defp throw(item, dest, troop) do
      {_, rcvd} =
        :array.get(dest, troop)
        |> Map.get_and_update!(:items, fn curr -> {curr, [item | curr]} end)

      :array.set(dest, rcvd, troop)
    end

    defp maybe_relief(item, false), do: item
    defp maybe_relief(item, true), do: div(item, 3)
  end

  defmodule Solve do
    def part1(troop) do
      counters = :counters.new(:array.sparse_size(troop), [])
      Monkeys.simulate_rounds(20, troop, counters, true)

      solve(troop, counters)
    end

    defp solve(troop, counters) do
      1..:array.sparse_size(troop)
      |> Enum.map(fn i -> :counters.get(counters, i) end)
      |> IO.inspect()
      |> Enum.sort(:desc)
      |> Enum.take(2)
      |> Enum.product()
    end

    def part2(troop, n) do
      counters = :counters.new(:array.sparse_size(troop), [])

      troop
      |> setup_for_part2()
      |> simulate(n, counters)

      solve(troop, counters)
    end

    def setup_for_part2(troop) do
      troop
      |> :array.to_list()
      |> Enum.reduce({[], %{}, %{}}, fn monkey, {items, ops, rules} ->
        id = monkey.id
        ops = Map.put(ops, id, monkey.op)
        rules = Map.put(rules, id, {monkey.test, monkey.pos, monkey.neg})
        items = [monkey.items |> Enum.zip(Stream.cycle([id])) | items]
        {items, ops, rules}
      end)
      |> flatten_items()
    end

    defp flatten_items({items, ops, rules}), do: {List.flatten(items), ops, rules}

    defp simulate({items, ops, rules}, rounds, counters) do
      items
      |> Task.async_stream(
        fn item ->
          1..rounds
          |> Enum.reduce(item, fn _, obj ->
            Monkeys.simulate_round_by_item({obj, ops, rules}, counters)
          end)
        end,
        timeout: :infinity,
        max_concurrency: 8
      )
      |> Stream.run()
    end
  end
end

I think if I change part 2 to something like

 1..n
    |> Enum.reduce(items, fn _, acc ->
      IO.inspect(acc)

      acc
      |> Task.async_stream(
        fn {val, id} ->
          simulate_round_by_item({{val, id}, counters, ops}, rules)
        end,
        max_concurrency: 8
      )
      |> Enum.map(&elem(&1, 1))
      |> Enum.to_list()
    end)

the concurrency effect might actually be useful. Not able to try it right now though. Day 12 part 1 I think I know how to solve but those weighted graph type problems always take me forever.

No style awards for this one :sweat_smile: ~100ms without any GenServers. I spotted that all “divisible by x” were prime numbers and figured that was part of the trick for part 2.

How long time does it take to compute part 2?

@kwando Why does that LCM trick work in your run_round/2 function new_wl = rem(wl, factor)? And how does it speed things up?

The only thing that makes it slow is that the numbers will be ridiculously large pretty quick, which means we will be using huge bignums instead of integers.

Yeah, I tried to brute force it and it took few seconds to get to round 600, then minutes to get to round 800 and I don’t think I ever saw it go beyond round 900 before I gave up (having had breakfast in between). Using only the remainder make the 10k complete in seconds. I would’ve never figured that out without looking at others’ solutions though. It still kinda blows my mind that applying operations on the remained instead of the whole number somehow yield the same results (given multiplication and additions all the same).

1 Like

That makes sense. I wonder if something like u128 integers in Rust bypasses this issue. I might try to use Rustler to make a nif that wraps u128 just to see.

A bit off-topic, but for Day 12, Paul Schoenfelder’s libgraph make it easy to generate a directed graph / do path-finding.

Day 12 spoiler

The edges does not need to be weighted, but they do need to be directed. I misread the prompt and took a looong time to figure out what happened. You are forbidden to climb more than one level, but it is permissible to jump off a cliff.

3 Likes

Wiw, thats useful! Thanks for sharing! :slight_smile:

I should take this as an opportunity to learn something and look up the underlying math.

It might be useful when doing AoC next year :slightly_smiling_face:

I cheated a little bit in parsing the “Operation” part:

@spec parse_op(String.t) :: (non_neg_integer -> non_neg_integer)
defp parse_op("new = " <> body) do
  Code.eval_string("fn old -> #{body} end") |> elem(0)
end

For example,

parse_op("new = old * old")

returns a unary function

fn old -> old * old end
1 Like

And in part 2, instead of |> div(3), I did |> rem(Enum.product(all_numbers_in_Test)), and it works quite well. Well, theoretically it should be the LCM of those numbers, but since all those numbers are prime numbers, I just multiply them up to get the LCM.

1 Like

Yeah, adding that LCM step made part 2 work for me. I think this is an issue where being told the result was overflowing the integer type instead of silently moving to a BigNum (or whaterver Erlang does under the hood) would have clued me in to what the problem was a lot sooner.
I tried changing lists to Erlang arrays to make it faster. I tried using Erlang counters to make it faster after watching @ityonemo’s Advent of Elixir youtube video on counters. I tried making each round use concurrent threads for each item to reduce the time each round would take. None of that helped. It was all this simple math trick to keep from overflowing the integer type.

3 Likes

It’s just occurred to me that the monkies are prime, making them… prime apes.

4 Likes

When one codes both Erlang and Elixir on the same night.

2 Likes

The way I eventually wrapped my head around the trick on part 2 (after looking up the solution :cry: ) was to think of the values like a clock. The “test” makes more sense to me in terms of a question like ‘is it 0800?’ after x hours have passed, where x is not material, only if it is 8 (the remainder). So every time you go around the clock you can discard what is divisible and just keep the rest. But since in this case each monkey has its own “clock”, you need to preserve the “real” values until you get to the LCM (if you had one american and one EU monkey, then they would have to use the 24 hour clock to account for values the american wouldn’t need to otherwise care about, strictly speaking).

I “cheated” a lot on parsing the input and translated the input files into structs manually. :stuck_out_tongue:

For part 2 the straightforward approach quickly runs out of steam since the numbers involved become ENORMOUS and slow to work with.

As other folks noticed, all of the monkeys are checking the remainder with different prime numbers (“pairwise coprime numbers” if you want to be specific). There’s a number theory trick for representing gigantic numbers that we only care about remainders of with a bunch of pairwise coprime numbers: a residue number system!

TL;DR a residue number system extends @tfwright’s “clock” analogy by having separate “clocks” for each prime number we care about (the moduli). Some operations are straightforward in this system:

  • addition: add the corresponding “clocks” for the two inputs and take the remainder (“wrap around the clock”)
  • subtraction: subtract the corresponding “clocks” and take the remainder
  • multiplication by a normal integer: multiply each “clock” and take the remainder
  • check for divisibility by one of the moduli: check to see if the corresponding “clock” is at zero

Division is “problematic” according to Wikipedia, but thankfully this problem doesn’t need it.

When all of the “clocks” roll over together, then the resulting residue number is zero again. The largest representable number is one less than the product of all the moduli - the “monkey factor” that appears in several other solutions. For this problem, that factor is still reasonable but for a “production” application of residue numbers the moduli might be a bunch of primes just below 2**31 - 1. In that case each “clock” fits neatly into a 32-bit signed integer, versus a single giant clock value that might not even fit in a u128.

My solution uses maps (keys are moduli, values are “clocks”) to avoid having to pass the moduli around separately everywhere, but using a tuple would be more efficient. See the Residue module in part2.exs for details.

1 Like