hauleth

hauleth

Yes, it is the same, but because how the task works, there will be only one way to win each game, so the minimum will be at the same time the only way to win.

0
Post #21
al2o3cr

al2o3cr

Used the same linear algebra approach as other solutions here, though I chose to always keep things as integers until they were confirmed to be exactly divisible.

Also uses Regex.run to parse a whole problem at once.

defmodule TheClaw do
  @problem_format ~r/Button A: X\+(\d+), Y\+(\d+)\nButton B: X\+(\d+), Y\+(\d+)\nPrize: X=(\d+), Y=(\d+)/

  defstruct [:xa, :xb, :ya, :yb, :x0, :y0]

  def read(filename) do
    File.read!(filename)
    |> String.split("\n\n")
    |> Enum.map(&Regex.run(@problem_format, &1, capture: :all_but_first))
    |> Enum.map(fn vs -> Enum.map(vs, &String.to_integer/1) end)
    |> Enum.map(fn [xa, ya, xb, yb, x0, y0] ->
      %__MODULE__{xa: xa, xb: xb, ya: ya, yb: yb, x0: x0, y0: y0}
    end)
  end

  def offset(c, off) do
    %{c | x0: c.x0 + off, y0: c.y0 + off}
  end

  def solution(c) do
    discriminant = c.xb*c.ya - c.xa*c.yb
    {
      discriminant,
      c.y0*c.xb - c.x0*c.yb,
      c.x0*c.ya - c.y0*c.xa
    }
  end

  def possible?({d, na, nb}) do
    rem(na, d) == 0 and rem(nb, d) == 0
  end

  @cost_a 3
  @cost_b 1

  def cost({d, na, nb}) do
    div(na * @cost_a + nb * @cost_b, d)
  end
end

TheClaw.read("input.txt")
|> Enum.map(&TheClaw.offset(&1, 10000000000000))
|> Enum.map(&TheClaw.solution/1)
|> Enum.filter(&TheClaw.possible?/1)
|> Enum.map(&TheClaw.cost/1)
|> Enum.sum()
|> IO.inspect()
1
Post #22
jarlah

jarlah

dam! THANKS! It was just “off by one” issue .. removing greater than and using ===


  defp reached_target?(
         {presses_a, presses_b, _},
         {x_inc_a, y_inc_a},
         {x_inc_b, y_inc_b},
         {target_x, target_y}
       ) do
    current_x = presses_a * x_inc_a + presses_b * x_inc_b
    current_y = presses_a * y_inc_a + presses_b * y_inc_b
    current_x === target_x and current_y === target_y
  end

now i probably will need to go off into the linear algebra territory also …I just hate it when i cant use normal dynamic programming for part1

1
Post #23
billylanchantin

billylanchantin

Linear algebra tells us there is at most one solution to this system of equations (that it’s integer division doesn’t play into it). We can solve with a simple application of Cramer’s rule or any equivalent method.

LOC: 13

defmodule Aoc2024.Day13 do
  import Enum
  def part1(file), do: main(file, 0)
  def part2(file), do: main(file, 10_000_000_000_000)
  def main(f, z), do: f |> File.read!() |> String.split("\n\n") |> map(&p/1) |> sum_by(&s(&1, z))
  @r ~r/Button A: X\+(\d+), Y\+(\d+)\nButton B: X\+(\d+), Y\+(\d+)\nPrize: X=(\d+), Y=(\d+)/
  def p(s), do: Regex.scan(@r, s, capture: :all_but_first) |> hd |> map(&String.to_integer/1)

  def s([ax, ay, bx, by, px, py], z) do
    {d, x, y} = {ax * by - ay * bx, (px + z) * by - bx * (py + z), ax * (py + z) - (px + z) * ay}
    if d == 0 or rem(x, d) != 0 or rem(y, d) != 0, do: 0, else: 3 * div(x, d) + div(y, d)
  end
end
1
Post #24
billylanchantin

billylanchantin

Ah I see @hauleth beat me to this observation! An incident at work kept me from this puzzle until today.

0
Post #25
jarlah

jarlah

I solved part2 today with the use of linear algebra. But it was a blatant copy paste. I think this and maybe the previous day (12) marks the end of where i can use dynamic programming alone to solve the puzzles. Its a bit sad i had to resort to math, but hey advent of code cant just be Enum.reduce :smiley:

i solved myself some cognitive overhead by actually naming the variables to match what the function actually takes in .. still doesnt “make sense”, but its easier to following the x’s and y’s i guess ..

haha just found the spoiler functionality :stuck_out_tongue: would be REALLY nice actually to avoid scrolling past posts to not get the answer thrown into your face :smiley: haha ..

def solve_machine({{aX, aY}, {bX, bY}, {tX, tY}}) do
x = (bY * tX - bX * tY) / (aX * bY - bX * aY)
y = (aX * tY - aY * tX) / (aX * bY - bX * aY)

if floor(x) == x and floor(y) == y do
  [trunc(x), trunc(y)]
end

end

0
Post #26
mwilsoncoding

mwilsoncoding

I feel like I just took a college class. It’s been years since I visited linear algebra, but I’m gonna get a book on it cuz this was fun.

3-blue,1-brown’s series on linear algebra explains things in a visual way that makes a lot of sense. Not sure I understood it back in college as well as I had to for solving this problem. Didn’t help that we were forced to do pen/paper solutions. Kept me from seeing “the joy of linear algebra,” so to speak.

I noted down my thoughts as I wrestled with the concepts. If anyone would like to correct or add to my understanding, I’m all ears.

defmodule Day13.Part2 do
  @moduledoc """
  This puzzle will be solved easier if I understand linear algebra.

  After speed-running 3-blue-1-brown's series on the essence of linear algebra
  (up to Cramer's rule) and wrestling with the concepts, here's what I've come up with
  """

  @a_cost 3
  @b_cost 1
  @adjustment 10_000_000_000_000

  defp parse_machine_args(machine_args) when is_list(machine_args) do
    machine_args
    |> Enum.reduce(
      %{},
      fn arg, machine ->
        {key, value} = parse_arg(arg)
        machine |> Map.put(key, value)
      end
    )
  end

  defp parse_arg("Button A: " <> a_vector), do: {:a, parse_point(a_vector)}
  defp parse_arg("Button B: " <> b_vector), do: {:b, parse_point(b_vector)}

  defp parse_arg("Prize: " <> point) do
    {p_x, p_y} = parse_point(point)
    {:prize, {p_x + @adjustment, p_y + @adjustment}}
  end

  defp parse_point("X" <> rest) do
    ~r/\d+/
    |> Regex.scan(rest)
    |> List.flatten()
    |> Enum.map(&String.to_integer/1)
    |> List.to_tuple()
  end

  defp parse(str) do
    str
    |> String.split("\n")
    |> Stream.chunk_by(&(&1 == ""))
    |> Stream.filter(&(&1 != [""]))
    |> Enum.map(&parse_machine_args/1)
  end

  defp determinant_2d([[a, b], [c, d]]) do
    a * d - b * c
  end

  defp min_cost(%{a: {a_x, a_y}, b: {b_x, b_y}, prize: {c_1, c_2}} = _machine) do
    # a_xx + b_xy = c_1 <- how many xs from button A + how many xs from button b to reach c_1?
    # a_yx + b_yy = c_2 <- how many ys from button A + how many ys from button b to reach c_2?

    # 2x2 Square Matrix
    #  _        _  _ _     _   _
    # | a_x  b_x || x |   | c_1 |
    # | a_y  b_y || y | = | c_2 |
    #  -        -  - -     -   -

    # Target vector
    #
    # [c_1 c_2]
    #
    # This 1x2 matrix of constants can be seen as a vector.

    # target_vector = [c_1, c_2]

    # Free-variable vector
    #
    # [x y]
    #
    # This 1x2 matrix of free-variables can be seen as a vector.

    # Variable Transform
    #
    # a_x b_x
    # a_y b_y
    #
    # The variable transform is the matrix of constants that is multiplied by the
    # free-variable vector in the matrix-multiplication representation of the linear system.

    variable_transform = [[a_x, b_x], [a_y, b_y]]

    # Columns
    #
    # A = [a_x a_y] = i-hat
    # B = [b_x b_y] = j-hat
    #
    # Each column corresponds to the vector described by pressing a given button.

    # Basis Vectors
    #
    # Typically i-hat and j-hat in 2-d vector space. These represent the initial state of
    # vector space to which you would like to apply transformations.

    # The Determinant
    #
    # The determinant is a function of a square matrix that tells us a scalar value. This
    # value is equivalent to the area of the unit square once transformed by the matrix,
    # in relation to some basis vectors. This scalar can be used to determine the scale of
    # one matrix/transform in proportion to another.

    # Carmine's Rule
    #
    # Used to evaluate the constituent variables of a linear system when said linear system
    # is representable by a square matrix. The square nature of the matrix means that each
    # linear equation represents a vector orthogonal to the other n-1 linear equations in
    # n-dimensional space.

    # When dealing with such a linear system, we can find the values of its constituent
    # variables one-at-a-time by finding a ratio of determinants.

    # For each n-th variable, the denominator is the determinant of the variable transform.

    # For each n-th variable, the numerator is the determinant of the target transform.
    # A target transform is the matrix formed by taking the variable transform and replacing
    # the n-th column's constants (the vector described by pressing that column's button)
    # with the constants from the target vector. I.e. we replace the vector described by
    # [n_x n_y] with [c_1 c_2].

    target_transform_x = [[c_1, b_x], [c_2, b_y]]

    target_transform_y = [[a_x, c_1], [a_y, c_2]]

    # x = determinant(target_transform_x)/determinant(variable_transform)
    # y = determinant(target_transform_y)/determinant(variable_transform)

    # x = by how much do I have to multiply the determinant of the variable transform to reach the determinant of the target x (i-hat) transform?
    # y = by how much do I have to multiply the determinant of the variable transform to reach the determinant of the target y (j-hat) transform?

    target_determinant_x = determinant_2d(target_transform_x)
    target_determinant_y = determinant_2d(target_transform_y)
    variable_determinant = determinant_2d(variable_transform)

    # For this puzzle, we want to find all integer solutions for x and y, since a button can't be partially pressed.

    # If all target determinants are evenly divisible by the variable determinant, we've found an integer solution to the linear system.

    # For that reason, we can filter by rem(target_determinant / variable_determinant) == 0 for all target_determinants

    # Cases where determinant(variable_transform) is 0 can't be divided, so skip those machines. Visually,
    # this would mean that the vector space described by the variable transform already squeezes down to a line or dot (starts out ortholinear?).

    if variable_determinant != 0 and
         rem(target_determinant_x, variable_determinant) == 0 and
         rem(target_determinant_y, variable_determinant) == 0 do
      # In the case we've found an integer solution to the linear equation, we've found how many button presses of A and B we need.
      # Multiply each by its cost and report their sum to be added to the overarching accumulator
      div(target_determinant_x, variable_determinant) * @a_cost +
        div(target_determinant_y, variable_determinant) * @b_cost
    else
      # Add nothing to the accumulator
      0
    end
  end

  defp score_min_costs(machines) do
    machines
    |> Task.async_stream(&min_cost/1)
    |> Enum.reduce(0, fn {:ok, min_cost}, acc ->
      acc + min_cost
    end)
  end

  def solve() do
    File.read!("lib/advent_of_code/year/2024/day/13/input.txt")
    |> parse()
    |> score_min_costs()
    |> IO.puts()
  end
end
0
Post #27
cblavier

cblavier

Here is my solution for Parts 1 & 2 using the equation-solving approach.
I didn’t enjoy this challenge very much, I prefer more algorithmic ones (and I struggled a bit at simplifying my equation :sweat_smile: )

My code (more parsing than solving)

defmodule Advent.Y2024.Day13 do
  defmodule Machine do
    defstruct [:x, :y, :a, :b, :x1, :x2, :y1, :y2, :prize]
  end

  def run(puzzle) do
    puzzle
    |> parse()
    |> Enum.map(&solve/1)
    |> Enum.map(& &1.prize)
    |> Enum.sum()
  end

  def parse(puzzle, error \\ 0) do
    puzzle
    |> String.split("\n\n")
    |> Enum.map(fn machine ->
      [a_btn, b_btn, prize] = String.split(machine, "\n")
      [[_, x1, y1]] = Regex.scan(~r/Button A: X\+(\d+), Y\+(\d+)/, a_btn)
      [[_, x2, y2]] = Regex.scan(~r/Button B: X\+(\d+), Y\+(\d+)/, b_btn)
      [[_, x, y]] = Regex.scan(~r/Prize: X=(\d+), Y=(\d+)/, prize)

      %Machine{
        x: String.to_integer(x) + error,
        y: String.to_integer(y) + error,
        x1: String.to_integer(x1),
        x2: String.to_integer(x2),
        y1: String.to_integer(y1),
        y2: String.to_integer(y2)
      }
    end)
  end

  def solve(m = %Machine{x: x, y: y, x1: x1, x2: x2, y1: y1, y2: y2}) do
    a = (y - y2 / x2 * x) / (y1 - y2 * x1 / x2)
    b = (x - a * x1) / x2

    if Float.round(a, 3) == round(a) and Float.round(b, 3) == round(b) do
      %Machine{m | a: round(a), b: round(b), prize: round(3 * a + b)}
    else
      %Machine{m | prize: 0}
    end
  end
end
0
Post #28
lkuty

lkuty 

#!/usr/bin/env elixir

# AoC 2024. day 13.

Mix.install([
  {:nx, "~> 0.9.2"}
])

to_i = &String.to_integer/1

###########################################################
# Part 1

start = System.monotonic_time(:microsecond)
File.stream!("../day13.txt")
|> Stream.map(fn line -> Regex.run(~r/^(?:Button (A|B): X\+(\d+), Y\+(\d+))|(?:Prize: X=(\d+), Y=(\d+)$)/, line, capture: :all_but_first) end)
|> Enum.reduce({[], %{}}, fn
  nil, {lst, curr} -> {[curr | lst], %{}}
  ["", "", "", n1, n2], {lst, curr} -> {lst, Map.put(curr, :prize, {to_i.(n1), to_i.(n2)})}
  [what, n1, n2], {lst, curr} -> {lst, Map.put(curr, String.to_atom(String.downcase(what)), {to_i.(n1), to_i.(n2)})}
end)
|> then(fn {lst, curr} -> Enum.map([curr | lst], fn %{a: {ax,ay}, b: {bx,by}, prize: {x,y}} ->
    Nx.LinAlg.solve(Nx.tensor([[ax, bx], [ay, by]], type: {:f, 64}), Nx.tensor([x, y], type: {:f, 64}))
    |> Nx.round()
    |> Nx.as_type(:s64)
    |> Nx.to_list()
    |> then(fn [a,b] ->
      if a*ax+b*bx==x && a*ay+b*by==y do
        [a,b]
      else
        [-1,-1]
      end
    end)
  end) end)
|> Enum.filter(fn [a,b] -> a >= 0 && b >= 0 && a <= 100 && b <= 100 end)
|> Enum.map(fn [a,b] -> a*3+b end)
|> Enum.sum()
|> IO.inspect(label: "Part 1")
elapsed = System.monotonic_time(:microsecond) - start
IO.puts "Job done in #{elapsed} µs"

###########################################################
# Part 2

start = System.monotonic_time(:microsecond)
File.stream!("../day13.txt")
|> Stream.map(fn line -> Regex.run(~r/^(?:Button (A|B): X\+(\d+), Y\+(\d+))|(?:Prize: X=(\d+), Y=(\d+)$)/, line, capture: :all_but_first) end)
|> Enum.reduce({[], %{}}, fn
  nil, {lst, curr} -> {[curr | lst], %{}}
  ["", "", "", n1, n2], {lst, curr} -> {lst, Map.put(curr, :prize, {to_i.(n1)+10000000000000, to_i.(n2)+10000000000000})}
  [what, n1, n2], {lst, curr} -> {lst, Map.put(curr, String.to_atom(String.downcase(what)), {to_i.(n1), to_i.(n2)})}
end)
|> then(fn {lst, curr} -> Enum.map([curr | lst], fn %{a: {ax,ay}, b: {bx,by}, prize: {x,y}} ->
    Nx.LinAlg.solve(Nx.tensor([[ax, bx], [ay, by]], type: {:f, 64}), Nx.tensor([x, y], type: {:f, 64}))
    |> Nx.round()
    |> Nx.as_type(:s64)
    |> Nx.to_list()
    |> then(fn [a,b] ->
      if a*ax+b*bx==x && a*ay+b*by==y do
        [a,b]
      else
        [-1,-1]
      end
    end)
  end) end)
|> Enum.filter(fn [a,b] -> a >= 0 && b >= 0 end)
|> Enum.map(fn [a,b] -> a*3+b end)
|> Enum.sum()
|> IO.inspect(label: "Part 2")
elapsed = System.monotonic_time(:microsecond) - start
IO.puts "Job done in #{elapsed} µs"
0
Post #29
ken-kost

ken-kost

Man that’s elegant. I tried similar but with float operations and conditions and such… complications and of course it didn’t work out for part 2; although I got correct results for part 1 input data. :confused:
Anyway, I’ll try to sear this into my memory:

Solve the following equation system for integers (with integers)

1
Post #30