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
Trending in Challenges
Other Trending Topics
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
Beam Bots (or just BB for short) is a framework for building fault-tolerant robotics applications in Elixir using familiar OTP patterns. ...
New
Hello everyone. After busy few months I am happy to announce v0.1.0 of Emerge & Solve.
They are GUI (Emerge) and State management (S...
New
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
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
@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
Categories:
Sub Categories:
Forums
Popular Tags
- #ecto
- #liveview
- #troubleshooting
- #learning-elixir
- #deployment
- #library
- #erlang
- #testing
- #genserver
- #mix
- #absinthe
- #remote-other
- #otp
- #plug
- #how-to-question
- #macros
- #postgres
- #channels
- #elixirconf
- #exunit
- #discussion
- #code-sync
- #javascript
- #podcasts
- #onsite
- #dialyzer
- #docker
- #authentication
- #umbrella
- #full-time-contract
- #podcasts-by-brainlid
- #ecto-query
- #elixir-ls
- #phoenix_html
- #iex
- #blog-post
- #graphql
- #genstage
- #ai
- #elixirconf-us
- #websockets
- #supervisor
- #advent-of-code
- #distillery
- #processes
- #api
- #forms
- #metaprogramming
- #performance
- #security










First Post!
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
It’s just occurred to me that the monkies are prime, making them… prime apes.
jkwchui
A bit off-topic, but for Day 12, Paul Schoenfelder’s
libgraphmake 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
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
I “cheated” a lot on parsing the input and translated the input files into structs manually.
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:
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 au128.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
Residuemodule inpart2.exsfor details.