Day 7: Bridge Repair

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

Reading

• We’re doing calibrations for a rope bridge
• Looking fro the right operators to some equations
• Input Equations without any operators
• Equations are always evaluated left-to-right - NOT according to operator precedence
• Possbile operators are + and *
• The equation holds if it results in the value before the colon
• Result Sum of all equation results that can be made to work with any operators

Input

equations =
  Kino.FS.file_path("day7_input.bin")
  |> File.stream!()
  |> Enum.map(fn line ->
    [result, numbers] = String.split(line, ":")
    numbers = numbers
      |> String.split()
      |> Enum.map(fn num -> num |> String.trim() |> String.to_integer() end)
    {String.to_integer(result), numbers}
  end)

Implementation

• With the parsed input from above we can basically just test all combinations
• We can write a generator that generates a set of operators for the length of the list of values:
  • + +
  • * +
  • + *
  • * *
• This grows exponentially, so it might be slow if we do it brute-force

Recursive stepping solution

While implementing the above idea, I thought about the following better solution:

• All numbers in my Input are positive
• Adding two positive numbers makes the result bigger
• Multiplying two positive numbers makes the result much bigger
• Idea:
  1. Multiply both numbers
  2. If this is less than the final result, move on to next number
  3. If it’s more than the final result, add them instead
  4. If this is less than the final result, move on to next number
  5. Else go back one step and try the other operator
• This way, we go big early (using multiplications) and gradually make things smaller when needed
• This does fewer computations than generating all possible combinations and evaluating each

defmodule Evaluator do
  @operands [:mul, :add]

  def is_possibly_true?({result, [first | rest]}) do
    do_calc(result, rest, first, @operands)
    |> case do
      :ok -> true
      _ -> false
    end
  end

  defp do_calc(target, [number | rest] = numbers, current, [operand | fallback]) do
    case eval(current, number, operand) do
      result when result > target -> do_calc(target, numbers, current, fallback)
      result -> do_calc(target, rest, result, @operands)
    end
    |> then(fn
      :ok -> :ok
      :step_back -> do_calc(target, numbers, current, fallback)
    end)
  end

  defp do_calc(_target, _numbers, _current, []) do
    # No more operators to try, need to step back
    :step_back
  end

  defp do_calc(target, [], current, _operators) when target == current, do: :ok
  defp do_calc(_target, [], _current, _operators), do: :step_back

  defp eval(a, b, :mul), do: a * b
  defp eval(a, b, :add), do: a + b
end

total_calibration_result = equations
  |> Enum.reduce(0, fn {value, _numbers} = equation, count ->
    if Evaluator.is_possibly_true?(equation), do: count + value, else: count
  end)

Part 2

• We have a new concat operator which combines two digits: 1 || 2 = 12
• Everything is still evaluated left-to-right, as before
• Output is again the sum of all possible equations results
• This number must obviously be higher thant the previous one

Idea

I can probably just extend my code above to also include the new operator and use the exact same rules.

The only interesting question is should there be a new order of operators? I’m gonna append it for now and see…

defmodule EvaluatorV2 do
  @operands [:mul, :add, :concat]

  def is_possibly_true?({result, [first | rest]}) do
    do_calc(result, rest, first, @operands)
    |> case do
      :ok -> true
      _ -> false
    end
  end

  defp do_calc(target, [number | rest] = numbers, current, [operand | fallback]) do
    case eval(current, number, operand) do
      result when result > target -> do_calc(target, numbers, current, fallback)
      result -> do_calc(target, rest, result, @operands)
    end
    |> then(fn
      :ok -> :ok
      :step_back -> do_calc(target, numbers, current, fallback)
    end)
  end

  defp do_calc(_target, _numbers, _current, []) do
    # No more operators to try, need to step back
    :step_back
  end

  defp do_calc(target, [], current, _operators) when target == current, do: :ok
  defp do_calc(_target, [], _current, _operators), do: :step_back

  defp eval(a, b, :mul), do: a * b
  defp eval(a, b, :add), do: a + b
  defp eval(a, b, :concat) do
    to_string(a) <> to_string(b)
    |> String.to_integer()
  end
end

p2_total_calibration_result = equations
  |> Enum.reduce(0, fn {value, _numbers} = equation, count ->
    if EvaluatorV2.is_possibly_true?(equation), do: count + value, else: count
  end)