Powered by AppSignal & Oban Pro
Would you like to see your link here? Contact us

Day 13: Claw Contraption

day13.livemd

Day 13: Claw Contraption

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

Input

input = Kino.Input.textarea("Please, paste your input:")
defmodule Day13Shared do
  def parse(input) do
    input
    |> Kino.Input.read()
    |> String.split("\n\n")
    |> Enum.map(&parse_machine/1)
  end

  defp parse_machine(rules) do
    [a_rules, b_rules, prize_at] = String.split(rules, "\n")

    [ax, ay] = parse_rule(a_rules, ~r/X\+(\d+), Y\+(\d+)$/)
    [bx, by] = parse_rule(b_rules, ~r/X\+(\d+), Y\+(\d+)$/)
    [px, py] = parse_rule(prize_at, ~r/X=(\d+), Y=(\d+)$/)

    %{a: {ax, ay}, b: {bx, by}, goal: {px, py}}
  end

  defp parse_rule(rules, regex),
    do: Regex.run(regex, rules, capture: :all_but_first) |> Enum.map(&String.to_integer/1)
end

Day13Shared.parse(input)

Part 1

defmodule Day13Part1 do
  def process(machines) do
    Enum.map(machines, fn %{a: {axd, ayd}, b: {bxd, byd}, goal: {gx, gy}} ->
      Enum.reduce(1..100, [], fn step_a, winning_combinations ->
        {ax, ay} = {axd * step_a, ayd * step_a}

        steps_b =
          1..100
          |> Enum.map(fn step_b -> {step_b, bxd * step_b, byd * step_b} end)
          |> Enum.filter(fn {_, bx, by} -> ax + bx == gx and ay + by == gy end)
          |> Enum.map(&elem(&1, 0))

        if steps_b == [] do
          winning_combinations
        else
          [{step_a, hd(steps_b)}]
        end
      end)
    end)
    |> List.flatten()
    |> Enum.reduce(0, fn {a_pushes, b_pushes}, tokens_spent ->
      tokens_spent + (a_pushes * 3 + b_pushes * 1)
    end)
  end
end

input |> Day13Shared.parse() |> Day13Part1.process()

# 31065 is the right answer

Part 2

defmodule EquationSolver do
  @doc """
  Solves a system of linear equations using matrix operations.

  ## Parameters
  - matrix_a: Coefficient matrix
  - matrix_b: Constant terms matrix

  ## Returns
  A tuple with the solutions for variables A and B
  """
  def solve_linear_system(matrix_a, matrix_b) do
    # Convert matrices to lists of lists for easier manipulation
    a_rows = Enum.map(matrix_a, &Enum.map(&1, fn x -> x end))
    b_rows = Enum.map(matrix_b, fn [x] -> x end)

    # Calculate determinant of the coefficient matrix
    det_a = calculate_determinant(a_rows)

    # Calculate determinants for each variable
    solutions =
      a_rows
      |> Enum.with_index()
      |> Enum.map(fn {_, index} ->
        replace_column(a_rows, b_rows, index)
        |> calculate_determinant()
        |> Kernel./(det_a)
      end)

    # Return the solutions as a tuple
    List.to_tuple(solutions)
  end

  @doc """
  Calculates the determinant of a 2x2 matrix.

  ## Parameters
  - matrix: 2x2 matrix represented as a list of lists

  ## Returns
  The determinant of the matrix
  """
  defp calculate_determinant([[a, b], [c, d]]) do
    a * d - b * c
  end

  @doc """
  Replaces a column in the matrix with the constant terms.

  ## Parameters
  - matrix: Original coefficient matrix
  - constants: Constant terms
  - column_index: Index of the column to replace

  ## Returns
  A new matrix with the specified column replaced
  """
  defp replace_column(matrix, constants, column_index) do
    matrix
    |> Enum.with_index()
    |> Enum.map(fn {row, row_index} ->
      List.replace_at(row, column_index, Enum.at(constants, row_index))
    end)
  end
end

defmodule Day13Part2 do
  def process(machines) do
    machines
    |> Enum.map(&update_the_goal/1)
    |> Enum.map(fn %{a: {axd, ayd}, b: {bxd, byd}, goal: {gx, gy}} ->
      IO.inspect([
        "#{axd}·A + #{bxd}·B = #{gx}",
        "#{ayd}·A + #{byd}·B = #{gy}"
      ])

      matrix_a = [
        [axd, bxd],
        [ayd, byd]
      ]

      matrix_b = [
        [gx],
        [gy]
      ]

      EquationSolver.solve_linear_system(matrix_a, matrix_b)
    end)
    |> Enum.filter(fn {a_pushes, b_pushes} ->
      Float.round(a_pushes) == a_pushes and Float.round(b_pushes) == b_pushes
    end)
    |> List.flatten()
    |> Enum.reduce(0, fn {a_pushes, b_pushes}, tokens_spent ->
      tokens_spent + (a_pushes * 3 + b_pushes * 1)
    end)
  end

  def update_the_goal(%{goal: {x, y}} = machine) do
    extra = 10_000_000_000_000
    
    %{machine | goal: {x + extra, y + extra}}
  end
end

input |> Day13Shared.parse() |> Day13Part2.process()

# 93866170395343 is the right answer