Day 13: Claw Contraption

Mix.install([
  {:kino, "~> 0.14.0"}
])

Reading

• We’re in the Arcade on the claw machine
• There are two inputs:
  • A Button, costs 3 tokens to press
  • B Button, costs 1 token to press
  • button moves claw to the right (on x-axis) or forward (on y-axis)
• A machine has one price
  • to win it, the claw must be EXACTLY above it
  • initial claw position is always 0|0
• Input is the following:
  • How much does Button A move the crane
  • How much does Button B move the crane
  • Where exactly is the price
  • Empty line to mean a new machine with different config
• Output: The minimum number of tokens required to win all prizes
  • NOTE: Some machines can’t be won!
  • We can early-exit if a single Button must be pressed more than 100 times

Input

defmodule MachineConf do
  defstruct btn_a: {0,0}, btn_b: {0,0}, prize: {0,0}

  def new(), do: %__MODULE__{}

  def parse(conf, "Button A: " <> rest), do: %__MODULE__{conf | btn_a: parse_claw_change(rest)}
  def parse(conf, "Button B: " <> rest), do: %__MODULE__{conf | btn_b: parse_claw_change(rest)}
  def parse(conf, "Prize: " <> rest), do: %__MODULE__{conf | prize: parse_pos(rest)}
  def parse(_conf, "\n"), do: :done

  defp parse_claw_change(changes) do
    [_, x, _, y] = String.split(changes, ~w(+ ,))
    x = String.to_integer(x)
    y = y |> String.trim_trailing() |> String.to_integer()
    {x, y}
  end

  defp parse_pos(prize_pos) do
    [_, x, _, y] = String.split(prize_pos, ~w(= ,))
    x = String.to_integer(x)
    y = y |> String.trim_trailing() |> String.to_integer()
    {x, y}
  end
end

claw_machines =
  Kino.FS.file_path("day13_input.bin")
  |> File.stream!()
  |> Enum.reduce({[], MachineConf.new()}, fn line, {acc, conf} ->
    case MachineConf.parse(conf, line) do
      :done -> {[conf | acc], MachineConf.new()}
      conf -> {acc, conf}
    end
  end)
  |> then(fn {list, last} ->
    # The file doesn't end in an empty line, so we'll add the last (complete)
    # machine config to the list as well.
    [last | list]
  end)

examples = [
  # NOTE: using this syntax because the "MachineConf" struct is declared in this
  # same context and not available. It _can_ however be used in functions, like
  # `MachineConf.new()`.
  %{MachineConf.new() | btn_a: {94, 34}, btn_b: {22, 67}, prize: {8400, 5400}},
  %{MachineConf.new() | btn_a: {26, 66}, btn_b: {67, 21}, prize: {12748, 12176}},
  %{MachineConf.new() | btn_a: {17, 86}, btn_b: {84, 37}, prize: {7870, 6450}},
  %{MachineConf.new() | btn_a: {69, 23}, btn_b: {27, 71}, prize: {18641, 10279}}
]

:ok

Implementation

• The order of pressing the buttons does not matter
• Theoretically, the cheaper button could move you three times less than the expensive one - can’t just greedily press cheap to get close
  • From the input, most configs have one Button bring you right and the other bring forward

Idea

• recursive algorithm that starts at the modulo of the B button movement (cheaper one) of the goal
• start going “backwards” and try pressing the expensive button
• if we are gone back to the start position, it’s not solveable

defmodule CheapWinner do
  def solve(%MachineConf{} = config) do
    do_solve({0, 0}, 0, [:btn_b, :btn_a], config)
  end

  defp do_solve(_, _, [], _), do: :error
  defp do_solve(current_pos, cost, [btn | rest] = buttons, %MachineConf{prize: prize} = conf) do
    change = fetch_change(conf, btn)
    case press_button(current_pos, change, prize) do
      {:cont, new_pos} -> do_solve(new_pos, add_cost(cost, btn), buttons, conf)
      :found -> {:ok, add_cost(cost, btn)}
      :error -> do_solve(current_pos, cost, rest, conf)
    end
    |> then(fn
      :error -> do_solve(current_pos, cost, rest, conf)
      result -> result
    end)
  end

  defp fetch_change(config, button), do: Map.fetch!(config, button)
  
  defp add_cost(cost, :btn_a), do: cost + 3
  defp add_cost(cost, :btn_b), do: cost + 1

  defp press_button({x_pos, y_pos}, {x_change, y_change}, {x_prize, y_prize}) do
    case {x_pos + x_change, y_pos + y_change} do
      {x, y} when x < x_prize and y < y_prize -> {:cont, {x, y}}
      {x, y} when x == x_prize and y == y_prize -> :found
      _ -> :error
    end
  end
end

Enum.reduce(claw_machines, 0, fn machine, total ->
  case CheapWinner.solve(machine) do
    {:ok, cost} -> total + cost
    :error -> total
  end
end)

Part 2

The prize coordinates are moved by 10000000000000 units each

• This makes the solution above take too long to complete.
• The early exit condition of “less than 100 presses per button” has now been removed
• Running the part 1 solution for a single new machine takes too long

Idea

• From looking at the part 1 example 80*94 + 40*22 = 8400 we can write this with variables as 94a + 22b = 8400 -> This is a linear equation
• And thats where my rust math left me behind. Fortunatly, I found David Brownmans solution writeup which helped me make sense of the math.

We have two linear equations for each point, where we use a as the number of times we press the A-Button and b for the number of times we press the B-Button.

• The first example is $$a = (94|34)$$ and $$b = (22,67)$$ with the prize at $$(8400|5400)$$
• We can create two linear equations from this, one for each axis:
  • X-axis: $$94a + 22b = 8400$$
  • Y-axis: $$34a + 67b = 5400$$

Find A

• To solve an equation with two unknowns, we must “get rid of” (replace) one of the unknowns
  • We can do this by subtracting one equation from the other
  • This allows us to remove two variables if they have the same factor
  • We must change both linear equations…
• To get the same factor for b on both sides, we’ll multiply…
  • the x-axis equation with the y factor 67: $$(67 94a) + (67 22b) = 67 * 8400$$
  • the y-axis equation with the x factor 22: $$(22 34a) + (22 67b) = 22 * 5400$$
• If we now subtract both equations from each other, we get:
  • $$(67 94a + 67 22b) - (2234a + 2267b) = (678400) - (225400)$$
  • Our b now has the same factor on both sides of the subtraction (just ordered differently)
  • We can remove both of them: $$6794a - 2234a = (678400) - (225400)$$
• At this point we can solve for a:
  • Write the above with explicit brackets: $$(6794)a - (2234)a = (678400) - (225400)$$
  • Combine both factors: $$(6794 - 2234)a = (678400) - (22*5400)$$
  • Divide both sides by the factors: $$a = \frac{(678400) - (225400)}{(6794) - (2234)}$$
  • Result: $$a = 80$$
• We can now calculate the above formula with Integers to get a value for a

Find B

• We can use the original linear equation for the Y-axis and insert the previously calculated a value: $$34*80+67b = 5400$$
• Again we’ll divide both sides by the factor: $$\frac{34*80}{67} +b = \frac{5400}{67}$$
• Now subtract the fraction from both sides: $$b = \frac{5400-34*80}{67}$$
  • Result: $$b = 40$$
• Again we can calcualte the above with Integers to get our b value in-code

Hit test

The solution from the blog uses Pythons IsInteger() method to test if the equations results are whole numbers. If they are not whole numbers, the machien isn’t solvable since we can’t press a button partially.

In Elixir, there is no such method (that I could find), so instead we just multiply the result for each button with the axis changes and see if that is exaclty the prizes position.

defmodule UnitCorrectCheapWinner do
  @unit_factor 10_000_000_000_000  
  
  def solve(%MachineConf{prize: {prize_x, prize_y}, btn_a: {ax, ay}, btn_b: {bx, by}}) do
    {px, py} = {prize_x + @unit_factor, prize_y + @unit_factor}

    # Use `div` for Integer division
    a_presses = div((by * px) - (bx * py), (by * ax) - (bx * ay))
    b_presses = div(py - (ay * a_presses), by)

    # Verify we hit the target. If not, the equation above gives a comma result
    # but we can't press "half a button", so the machine isn't solvable
    hit_x = a_presses * ax + b_presses * bx == px
    hit_y = a_presses * ay + b_presses * by == py
    
    if hit_x and hit_y do
      {:ok, a_presses * 3 + b_presses}
    else
      :error # not solvable
    end
  end
end

Enum.reduce(claw_machines, 0, fn machine, total ->
  case UnitCorrectCheapWinner.solve(machine) do
    {:ok, cost} -> total + cost
    _ -> total
  end
end)

I had to look for help on this one, my Math just isn’t strong enough to solve this on my own. Once I understood what to do I did the calculations myself on paper. The “Idea” discription above is in my own words.

I like to think that I didn’t just steel the solution but applied some of my own brain.