Today’s puzzle is all about quadratic equation.

If the total time of a game is t, the speed of the boat (i.e. the time holding that button) is v, the distance the boat traveled is s, then the equation is

v * (t - v) = s

which can be normalized to

(v ** 2) - (t * v) + s = 0 

All the speeds that result in better distance are between the two solutions of v of that equation.

Aaaah. I wish I knew maths …

I hesitate to post my solution because it is so much more complex, but anyway.

Part 2 was around 4 seconds with the algorithm of part 1 so I used a binary search to find the two bounds:

defmodule AdventOfCode.Y23.Day6 do
  alias AoC.Input, warn: false

  def read_file(file, _part) do
    file |> Input.stream!(trim: true) |> Enum.take(2)
  end

  def parse_input([times, distances], :part_one) do
    times = int_list_no_header(times)
    distances = int_list_no_header(distances)
    Enum.zip(times, distances)
  end

  def parse_input(["Time: " <> times, "Distance: " <> distances], _) do
    {single_int(times), single_int(distances)}
  end

  defp int_list_no_header(string) do
    string
    |> String.split(" ", trim: true)
    |> Enum.drop(1)
    |> Enum.map(&String.to_integer/1)
  end

  defp single_int(string) do
    string
    |> String.split(" ", trim: true)
    |> Enum.join()
    |> String.to_integer()
  end

  def part_one(problem) do
    problem
    |> Enum.map(&count_wins/1)
    |> Enum.product()
  end

  defp count_wins({time, best}) do
    0..time
    |> Enum.map(&hold_time_to_distance(&1, time))
    |> Enum.filter(&(&1 > best))
    |> length()
  end

  defp hold_time_to_distance(hold = speed, time) do
    duration = time - hold
    _distance = speed * duration
  end

  def part_two({time, distance_record}) do
    half = trunc(time / 2)
    left = binary_search(&find_left_bound(&1, time, distance_record), 1, half)
    right = binary_search(&find_right_bound(&1, time, distance_record), half, time)
    right - left + 1
  end

  defp find_left_bound(hold, time, record) do
    left = hold_time_to_distance(hold - 1, time)
    right = hold_time_to_distance(hold, time)

    case {left, right} do
      {d1, d2} when d1 < record and d2 > record -> :eq
      {_d1, d2} when d2 < record -> :lt
      {d1, _d2} when d1 > record -> :gt
    end
  end

  defp find_right_bound(hold, time, record) do
    left = hold_time_to_distance(hold, time)
    right = hold_time_to_distance(hold + 1, time)

    case {left, right} do
      {d1, d2} when d1 > record and d2 < record -> :eq
      {_d1, d2} when d2 > record -> :lt
      {d1, _d2} when d1 < record -> :gt
    end
  end

  def binary_search(ask, min, max) do
    n = div(min + max, 2)

    case ask.(n) do
      # n is lower than the answer
      :lt -> binary_search(ask, n + 1, max)
      # n is greater than the answer
      :gt -> binary_search(ask, min, n - 1)
      :eq -> n
    end
  end
end

And it takes less than 100µs for part 2 which is really nice.

But still, I would like to understand your maths

This is due to compiled versus interpreted code.

In this case, wrapping this within a module inside livebook/IEx will compile the code and run in ~1s, while just running the code directly in interpreted mode (uses :erl_eval under the hood) will be slow when you have many iterations.

defmodule MyCell do
  def run do
    for r <- 1..46828479, r * (46828479 - r) > 347152214061471 do 1 end |> Enum.count()
  end
end

MyCell.run()

Part 1

puzzle_input
|> String.split("\n")
|> Stream.map(&String.split/1)
|> Stream.map(&tl/1)
|> Stream.map(&Enum.map(&1, fn s -> String.to_integer(s) end))
|> Enum.zip()
|> Enum.map(fn {t, s} ->
  delta = :math.sqrt(t * t - 4 * s)
  v1 = ceil((t - delta) / 2)
  v2 = floor((t + delta) / 2)
  v2 - v1 + 1
end)
|> Enum.product()

Part 2

[t, s] =
  puzzle_input
  |> String.split("\n")
  |> Enum.map(fn line ->
    ~r/\d/
    |> Regex.scan(line)
    |> List.flatten()
    |> Enum.join()
    |> String.to_integer()
  end)

delta = :math.sqrt(t * t - 4 * s)
v1 = ceil((t - delta) / 2)
v2 = floor((t + delta) / 2)
v2 - v1 + 1

Your binary search part is brilliant. I know the optimal time of holding the button is just time / 2, so I could have just used your strategy.

About the math in my solution, first see this image that corresponds to the first game in Part 1 (total time = 7)

image1965×1356 91.6 KB

The horizontal axis is the speed (i.e. time of holding the button), and the vertical axis is how far the boat can travel.

The red line shows the relationship between the speed and the distance the boat can travel.

The green line is the distance that the last winner traveled.

To beat the last winner, my speed needs to be between the two cross points (the two black points) of the red line and the green line.

The rest is just to google how to solve a quadratic equation.