Day11.livemd

Day 11: Monkey in the Middle

Mix.install([
  {:kino_aoc, git: "https://github.com/ljgago/kino_aoc"}
])

Data

{:ok, puzzle_input} = KinoAOC.download_puzzle("2022", "11", "")

defmodule Sanitizer do
  def sanitize(raw_input) do
    raw_input
    |> String.split("\n")
    |> Enum.reject(&(String.length(&1) == 0))
  end
end

Part 1

As you finally start making your way upriver, you realize your pack is much lighter than you remember. Just then, one of the items from your pack goes flying overhead. Monkeys are playing Keep Away with your missing things!

To get your stuff back, you need to be able to predict where the monkeys will throw your items. After some careful observation, you realize the monkeys operate based on how worried you are about each item.

You take some notes (your puzzle input) on the items each monkey currently has, how worried you are about those items, and how the monkey makes decisions based on your worry level. For example:

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

Each monkey has several attributes:

• Starting items lists your worry level for each item the monkey is currently holding in the order they will be inspected.
• Operation shows how your worry level changes as that monkey inspects an item. (An operation like new = old * 5 means that your worry level after the monkey inspected the item is five times whatever your worry level was before inspection.)
• Test shows how the monkey uses your worry level to decide where to throw an item next.
  • If true shows what happens with an item if the Test was true.
  • If false shows what happens with an item if the Test was false.

After each monkey inspects an item but before it tests your worry level, your relief that the monkey's inspection didn't damage the item causes your worry level to be divided by three and rounded down to the nearest integer.

The monkeys take turns inspecting and throwing items. On a single monkey's turn, it inspects and throws all of the items it is holding one at a time and in the order listed. Monkey 0 goes first, then monkey 1, and so on until each monkey has had one turn. The process of each monkey taking a single turn is called a round.

When a monkey throws an item to another monkey, the item goes on the end of the recipient monkey's list. A monkey that starts a round with no items could end up inspecting and throwing many items by the time its turn comes around. If a monkey is holding no items at the start of its turn, its turn ends.

In the above example, the first round proceeds as follows:

Monkey 0:
  Monkey inspects an item with a worry level of 79.
    Worry level is multiplied by 19 to 1501.
    Monkey gets bored with item. Worry level is divided by 3 to 500.
    Current worry level is not divisible by 23.
    Item with worry level 500 is thrown to monkey 3.
  Monkey inspects an item with a worry level of 98.
    Worry level is multiplied by 19 to 1862.
    Monkey gets bored with item. Worry level is divided by 3 to 620.
    Current worry level is not divisible by 23.
    Item with worry level 620 is thrown to monkey 3.
Monkey 1:
  Monkey inspects an item with a worry level of 54.
    Worry level increases by 6 to 60.
    Monkey gets bored with item. Worry level is divided by 3 to 20.
    Current worry level is not divisible by 19.
    Item with worry level 20 is thrown to monkey 0.
  Monkey inspects an item with a worry level of 65.
    Worry level increases by 6 to 71.
    Monkey gets bored with item. Worry level is divided by 3 to 23.
    Current worry level is not divisible by 19.
    Item with worry level 23 is thrown to monkey 0.
  Monkey inspects an item with a worry level of 75.
    Worry level increases by 6 to 81.
    Monkey gets bored with item. Worry level is divided by 3 to 27.
    Current worry level is not divisible by 19.
    Item with worry level 27 is thrown to monkey 0.
  Monkey inspects an item with a worry level of 74.
    Worry level increases by 6 to 80.
    Monkey gets bored with item. Worry level is divided by 3 to 26.
    Current worry level is not divisible by 19.
    Item with worry level 26 is thrown to monkey 0.
Monkey 2:
  Monkey inspects an item with a worry level of 79.
    Worry level is multiplied by itself to 6241.
    Monkey gets bored with item. Worry level is divided by 3 to 2080.
    Current worry level is divisible by 13.
    Item with worry level 2080 is thrown to monkey 1.
  Monkey inspects an item with a worry level of 60.
    Worry level is multiplied by itself to 3600.
    Monkey gets bored with item. Worry level is divided by 3 to 1200.
    Current worry level is not divisible by 13.
    Item with worry level 1200 is thrown to monkey 3.
  Monkey inspects an item with a worry level of 97.
    Worry level is multiplied by itself to 9409.
    Monkey gets bored with item. Worry level is divided by 3 to 3136.
    Current worry level is not divisible by 13.
    Item with worry level 3136 is thrown to monkey 3.
Monkey 3:
  Monkey inspects an item with a worry level of 74.
    Worry level increases by 3 to 77.
    Monkey gets bored with item. Worry level is divided by 3 to 25.
    Current worry level is not divisible by 17.
    Item with worry level 25 is thrown to monkey 1.
  Monkey inspects an item with a worry level of 500.
    Worry level increases by 3 to 503.
    Monkey gets bored with item. Worry level is divided by 3 to 167.
    Current worry level is not divisible by 17.
    Item with worry level 167 is thrown to monkey 1.
  Monkey inspects an item with a worry level of 620.
    Worry level increases by 3 to 623.
    Monkey gets bored with item. Worry level is divided by 3 to 207.
    Current worry level is not divisible by 17.
    Item with worry level 207 is thrown to monkey 1.
  Monkey inspects an item with a worry level of 1200.
    Worry level increases by 3 to 1203.
    Monkey gets bored with item. Worry level is divided by 3 to 401.
    Current worry level is not divisible by 17.
    Item with worry level 401 is thrown to monkey 1.
  Monkey inspects an item with a worry level of 3136.
    Worry level increases by 3 to 3139.
    Monkey gets bored with item. Worry level is divided by 3 to 1046.
    Current worry level is not divisible by 17.
    Item with worry level 1046 is thrown to monkey 1.

After round 1, the monkeys are holding items with these worry levels:

Monkey 0: 20, 23, 27, 26
Monkey 1: 2080, 25, 167, 207, 401, 1046
Monkey 2: 
Monkey 3:

Monkeys 2 and 3 aren't holding any items at the end of the round; they both inspected items during the round and threw them all before the round ended.

This process continues for a few more rounds:

After round 2, the monkeys are holding items with these worry levels:
Monkey 0: 695, 10, 71, 135, 350
Monkey 1: 43, 49, 58, 55, 362
Monkey 2: 
Monkey 3: 

After round 3, the monkeys are holding items with these worry levels:
Monkey 0: 16, 18, 21, 20, 122
Monkey 1: 1468, 22, 150, 286, 739
Monkey 2: 
Monkey 3: 

After round 4, the monkeys are holding items with these worry levels:
Monkey 0: 491, 9, 52, 97, 248, 34
Monkey 1: 39, 45, 43, 258
Monkey 2: 
Monkey 3: 

After round 5, the monkeys are holding items with these worry levels:
Monkey 0: 15, 17, 16, 88, 1037
Monkey 1: 20, 110, 205, 524, 72
Monkey 2: 
Monkey 3: 

After round 6, the monkeys are holding items with these worry levels:
Monkey 0: 8, 70, 176, 26, 34
Monkey 1: 481, 32, 36, 186, 2190
Monkey 2: 
Monkey 3: 

After round 7, the monkeys are holding items with these worry levels:
Monkey 0: 162, 12, 14, 64, 732, 17
Monkey 1: 148, 372, 55, 72
Monkey 2: 
Monkey 3: 

After round 8, the monkeys are holding items with these worry levels:
Monkey 0: 51, 126, 20, 26, 136
Monkey 1: 343, 26, 30, 1546, 36
Monkey 2: 
Monkey 3: 

After round 9, the monkeys are holding items with these worry levels:
Monkey 0: 116, 10, 12, 517, 14
Monkey 1: 108, 267, 43, 55, 288
Monkey 2: 
Monkey 3: 

After round 10, the monkeys are holding items with these worry levels:
Monkey 0: 91, 16, 20, 98
Monkey 1: 481, 245, 22, 26, 1092, 30
Monkey 2: 
Monkey 3: 

...

After round 15, the monkeys are holding items with these worry levels:
Monkey 0: 83, 44, 8, 184, 9, 20, 26, 102
Monkey 1: 110, 36
Monkey 2: 
Monkey 3: 

...

After round 20, the monkeys are holding items with these worry levels:
Monkey 0: 10, 12, 14, 26, 34
Monkey 1: 245, 93, 53, 199, 115
Monkey 2: 
Monkey 3: 

Chasing all of the monkeys at once is impossible; you're going to have to focus on the two most active monkeys if you want any hope of getting your stuff back. Count the total number of times each monkey inspects items over 20 rounds:

Monkey 0 inspected items 101 times.
Monkey 1 inspected items 95 times.
Monkey 2 inspected items 7 times.
Monkey 3 inspected items 105 times.

In this example, the two most active monkeys inspected items 101 and 105 times. The level of monkey business in this situation can be found by multiplying these together: 10605.

Figure out which monkeys to chase by counting how many items they inspect over 20 rounds. What is the level of monkey business after 20 rounds of stuff-slinging simian shenanigans?

defmodule Monkey do
  defstruct [:items, :operation, :test, :true_target, :false_target, :inspection_count]

  def new(lines) do
    [
      "Monkey " <> _name,
      "  Starting items: " <> starting_items,
      "  Operation: new = " <> operation,
      "  Test: " <> test,
      "    If true: throw to monkey " <> if_true,
      "    If false: throw to monkey " <> if_false
    ] = lines

    new(parse_items(starting_items), operation, test, if_true, if_false)
  end

  def new(items, operation, test, true_target, false_target) do
    %__MODULE__{
      items: items,
      operation: operation,
      test: test,
      true_target: String.to_integer(true_target),
      false_target: String.to_integer(false_target),
      inspection_count: 0
    }
  end

  def parse_items(csv) do
    csv
    |> String.split(",")
    |> Enum.map(&String.trim/1)
    |> Enum.map(&String.to_integer/1)
  end

  def apply_operation(worry_level, "old * old") do
    worry_level * worry_level
    # |> IO.inspect(label: "Worry level is multiplied by itself to")
  end

  def apply_operation(worry_level, "old * " <> multiplier) do
    String.to_integer(multiplier) * worry_level
    # |> IO.inspect(label: "Worry level is multiplied by #{multiplier} to")
  end

  def apply_operation(worry_level, "old + old") do
    worry_level + worry_level
    # |> IO.inspect(label: "Worry level increases by itself to")
  end

  def apply_operation(worry_level, "old + " <> addition) do
    String.to_integer(addition) + worry_level
    # |> IO.inspect(label: "Worry level increases by #{addition} to")
  end

  def passes_test?(worry_level, "divisible by " <> divisor) do
    rem(worry_level, String.to_integer(divisor)) == 0
    # |> IO.inspect(label: "Current worry level is divisible by #{divisor}?")
  end

  def apply_relief(worry_level) do
    (worry_level / 3) |> trunc()
    # |> IO.inspect(label: "Monkey gets bored with item. Worry level is divided by 3 to")
  end

  def receive_item(%__MODULE__{items: items} = monkey, item) do
    %{monkey | items: items ++ [item]}
  end

  def to_throw_action(worry_level, %__MODULE__{
        test: test,
        true_target: true_target,
        false_target: false_target
      }) do
    case passes_test?(worry_level, test) do
      true ->
        # IO.inspect("Item with worry level #{worry_level} is thrown to monkey #{true_target}")
        {true_target, worry_level}

      false ->
        # IO.inspect("Item with worry level #{worry_level} is thrown to monkey #{false_target}")
        {false_target, worry_level}
    end
  end

  def inspect_next(%__MODULE__{inspection_count: inspection_count, items: []} = monkey, throws) do
    updated = %{monkey | inspection_count: inspection_count + Enum.count(throws)}
    {updated, throws}
  end

  def inspect_next(%__MODULE__{items: [head | tail], operation: operation} = monkey, throws) do
    # IO.inspect("Monkey inspects an item with a worry level of #{head}.")

    action =
      head
      |> apply_operation(operation)
      |> apply_relief()
      |> to_throw_action(monkey)

    %{monkey | items: tail}
    |> inspect_next(throws ++ [action])
  end
end

defmodule Day11Part1 do
  def run(input, rounds) do
    input
    |> setup()
    |> play(rounds)
    |> monkey_business_level(2)
  end

  def setup(input) do
    input
    |> Sanitizer.sanitize()
    |> Enum.reject(&(String.length(&1) == 0))
    |> Enum.chunk_every(6)
    |> Enum.map(&Monkey.new/1)
    |> Enum.with_index(fn element, index -> {index, element} end)
    |> Enum.into(%{})
  end

  def play(initial_state, rounds) do
    Enum.reduce(0..(rounds - 1), initial_state, fn _index, state ->
      play_round(state)
    end)
  end

  def monkey_business_level(state, number) do
    state
    |> Map.values()
    |> Enum.sort_by(& &1.inspection_count, :desc)
    |> Enum.take(number)
    |> Enum.map(& &1.inspection_count)
    |> Enum.product()
  end

  def play_round(initial_state) do
    monkeys = Map.values(initial_state)

    monkeys
    |> Enum.with_index()
    |> Enum.reduce(initial_state, fn {_monkey, index}, state ->
      # IO.inspect("Monkey #{index}")
      {monkey, throws} =
        state
        |> Map.get(index)
        |> Monkey.inspect_next([])

      state
      |> Map.put(index, monkey)
      |> apply_throws(throws)
    end)
  end

  def apply_throws(initial_state, throws) do
    # IO.inspect("apply_throws " <> initial_state <> " throws " <> throws)
    throws
    |> Enum.reduce(initial_state, fn {monkey_id, worry_level}, state ->
      Map.get_and_update!(state, monkey_id, fn monkey ->
        {monkey, Monkey.receive_item(monkey, worry_level)}
      end)
      |> elem(1)
    end)
  end
end

Part 1 Tests

ExUnit.start(autorun: false)

defmodule Day11Part1Test do
  use ExUnit.Case, async: true

  @setup """
  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
  """

  test "works with sample input" do
    state = Day11Part1.setup(@setup) |> Day11Part1.play(1)
    assert [20, 23, 27, 26] == Map.get(state, 0).items
    assert [2080, 25, 167, 207, 401, 1046] == Map.get(state, 1).items
    assert [] == Map.get(state, 2).items
    assert [] == Map.get(state, 3).items
  end

  test "inspection count after 20 rounds" do
    state = Day11Part1.setup(@setup) |> Day11Part1.play(20)
    assert 101 == Map.get(state, 0).inspection_count
    assert 95 == Map.get(state, 1).inspection_count
    assert 7 == Map.get(state, 2).inspection_count
    assert 105 == Map.get(state, 3).inspection_count
  end

  test "monkey level" do
    state = Day11Part1.setup(@setup) |> Day11Part1.play(20)
    assert 10605 == Day11Part1.monkey_business_level(state, 2)
  end
end

ExUnit.run()

Day11Part1.run(puzzle_input, 20)

Part 2

It seems like the X register controls the horizontal position of a sprite. Specifically, the sprite is 3 pixels wide, and the X register sets the horizontal position of the middle of that sprite. (In this system, there is no such thing as "vertical position": if the sprite's horizontal position puts its pixels where the CRT is currently drawing, then those pixels will be drawn.)

You count the pixels on the CRT: 40 wide and 6 high. This CRT screen draws the top row of pixels left-to-right, then the row below that, and so on. The left-most pixel in each row is in position 0, and the right-most pixel in each row is in position 39.

Like the CPU, the CRT is tied closely to the clock circuit: the CRT draws a single pixel during each cycle. Representing each pixel of the screen as a #, here are the cycles during which the first and last pixel in each row are drawn:

Cycle   1 -> ######################################## <- Cycle  40
Cycle  41 -> ######################################## <- Cycle  80
Cycle  81 -> ######################################## <- Cycle 120
Cycle 121 -> ######################################## <- Cycle 160
Cycle 161 -> ######################################## <- Cycle 200
Cycle 201 -> ######################################## <- Cycle 240

So, by carefully timing the CPU instructions and the CRT drawing operations, you should be able to determine whether the sprite is visible the instant each pixel is drawn. If the sprite is positioned such that one of its three pixels is the pixel currently being drawn, the screen produces a lit pixel (#); otherwise, the screen leaves the pixel dark (.).

The first few pixels from the larger example above are drawn as follows:

Sprite position: ###.....................................

Start cycle   1: begin executing addx 15
During cycle  1: CRT draws pixel in position 0
Current CRT row: #

During cycle  2: CRT draws pixel in position 1
Current CRT row: ##
End of cycle  2: finish executing addx 15 (Register X is now 16)
Sprite position: ...............###......................

Start cycle   3: begin executing addx -11
During cycle  3: CRT draws pixel in position 2
Current CRT row: ##.

During cycle  4: CRT draws pixel in position 3
Current CRT row: ##..
End of cycle  4: finish executing addx -11 (Register X is now 5)
Sprite position: ....###.................................

Start cycle   5: begin executing addx 6
During cycle  5: CRT draws pixel in position 4
Current CRT row: ##..#

During cycle  6: CRT draws pixel in position 5
Current CRT row: ##..##
End of cycle  6: finish executing addx 6 (Register X is now 11)
Sprite position: ..........###...........................

Start cycle   7: begin executing addx -3
During cycle  7: CRT draws pixel in position 6
Current CRT row: ##..##.

During cycle  8: CRT draws pixel in position 7
Current CRT row: ##..##..
End of cycle  8: finish executing addx -3 (Register X is now 8)
Sprite position: .......###..............................

Start cycle   9: begin executing addx 5
During cycle  9: CRT draws pixel in position 8
Current CRT row: ##..##..#

During cycle 10: CRT draws pixel in position 9
Current CRT row: ##..##..##
End of cycle 10: finish executing addx 5 (Register X is now 13)
Sprite position: ............###.........................

Start cycle  11: begin executing addx -1
During cycle 11: CRT draws pixel in position 10
Current CRT row: ##..##..##.

During cycle 12: CRT draws pixel in position 11
Current CRT row: ##..##..##..
End of cycle 12: finish executing addx -1 (Register X is now 12)
Sprite position: ...........###..........................

Start cycle  13: begin executing addx -8
During cycle 13: CRT draws pixel in position 12
Current CRT row: ##..##..##..#

During cycle 14: CRT draws pixel in position 13
Current CRT row: ##..##..##..##
End of cycle 14: finish executing addx -8 (Register X is now 4)
Sprite position: ...###..................................

Start cycle  15: begin executing addx 13
During cycle 15: CRT draws pixel in position 14
Current CRT row: ##..##..##..##.

During cycle 16: CRT draws pixel in position 15
Current CRT row: ##..##..##..##..
End of cycle 16: finish executing addx 13 (Register X is now 17)
Sprite position: ................###.....................

Start cycle  17: begin executing addx 4
During cycle 17: CRT draws pixel in position 16
Current CRT row: ##..##..##..##..#

During cycle 18: CRT draws pixel in position 17
Current CRT row: ##..##..##..##..##
End of cycle 18: finish executing addx 4 (Register X is now 21)
Sprite position: ....................###.................

Start cycle  19: begin executing noop
During cycle 19: CRT draws pixel in position 18
Current CRT row: ##..##..##..##..##.
End of cycle 19: finish executing noop

Start cycle  20: begin executing addx -1
During cycle 20: CRT draws pixel in position 19
Current CRT row: ##..##..##..##..##..

During cycle 21: CRT draws pixel in position 20
Current CRT row: ##..##..##..##..##..#
End of cycle 21: finish executing addx -1 (Register X is now 20)
Sprite position: ...................###..................

Allowing the program to run to completion causes the CRT to produce the following image:

##..##..##..##..##..##..##..##..##..##..
###...###...###...###...###...###...###.
####....####....####....####....####....
#####.....#####.....#####.....#####.....
######......######......######......####
#######.......#######.......#######.....

Render the image given by your program. What eight capital letters appear on your CRT?

Day10Part2.run(puzzle_input) |> IO.puts()