jkwchui

jkwchui

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

First Post! Switch mode

deadbeef

deadbeef

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

https://github.com/ed-flanagan/advent-of-code-solutions-elixir/blob/main/lib/advent/y2022/d11.ex

Most Liked

adamu

adamu

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

jkwchui

jkwchui

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.

stevensonmt

stevensonmt

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.

Last Post!

al2o3cr

al2o3cr

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.

Where Next?

Trending in Challenges Top

Other Trending Topics Top

JesseHerrick
Hey, I’m Jesse and I’m the main contributor behind Dexter, a full-featured, lightning-fast Elixir LSP optimized for large codebases. It s...
New
jimsynz
Beam Bots (or just BB for short) is a framework for building fault-tolerant robotics applications in Elixir using familiar OTP patterns. ...
New
Damirados
Hello everyone. After busy few months I am happy to announce v0.1.0 of Emerge &amp; Solve. They are GUI (Emerge) and State management (S...
New
ausimian
Emily is an Elixir library that runs Nx computations on Apple’s MLX. Install it as the default Nx backend and Nx, defn, Axon, Nx.Serving,...
New
type1fool
I just stumbled on a newly redesigned elixir-lang.org. :tada: It looks like @Software_Mansion did the work, and I think it is generally a...
New
akoutmos
@hugobarauna and I (Alex Koutmos) have been hard at work on writing a book on Nerves that takes you from simply blinking LEDs to building...
New

We're in Beta

About us Mission Statement