Advent of Code 2023 - Day 6

I expected a twist in part 2, but there wasn’t any. My solution:

https://github.com/bjorng/advent-of-code-2023/blob/main/day06/lib/day06.ex

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.

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

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

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.

Yes I figured out that the best distance would always be to hold for 0.5 * time, so I splitted my search here.

Ok so I googled a bit and that -4 seems to be inherent of this form of equation and not specific to those boats, which reassures me.

Reminds me a long time ago in high school but I guess I had already bailed out of mathematics

My beginner’s solution, Day 06.
I was considering binary search as well when coming up with an efficient solution.
But naive approach turned out to be fast enough.

defmodule Day06 do

  def part2(input) do
    parse(input, :part2)
    |> number_of_ways_you_can_beat_the_record
  end

  def part1(input) do
    parse(input)
    |> Enum.map(&number_of_ways_you_can_beat_the_record/1)
    |> Enum.product
  end

  def number_of_ways_you_can_beat_the_record({time, record}) do
    for n <- 1..time-1 do (time - n) * n end
  # |> Enum.count(fn x -> x > record end)
    |> Enum.count(&Kernel.>(&1,record))
  end

  def parse(raw_document, :part2) do
    raw_document
    |> String.replace(" ", "")
    |> parse
    |> List.first
    # {71530, 940200}
  end
  
  def parse(raw_document) do
    # "Time:      7  15   30
    #  Distance:  9  40  200" 
    raw_document
    |> String.split("\n")
    |> Enum.map(fn raw_line -> raw_line
          |> String.split(":")
          |> List.last
          |> String.split
          |> Enum.map(&String.to_integer/1)
       end)
    |> List.zip
    # [{7, 9}, {15, 40}, {30, 200}]
  end

end

Inspired by the solution of @lud , I just tried another approach with Newton’s approximation because I don’t want to deal with floating point numbers

Prep

# Newton's approximation of one of the solutions to the equation
#
#     (v ** 2) - (t * v) + s = 0
#
# Keep only the integer part.
approx = fn t, s, v ->
  v
  |> Stream.unfold(fn v ->
    y = v * v - t * v + s
    k = 2 * v - t
    dv = div(y, k)
    {v, v - dv}
  end)
  |> Stream.chunk_every(2, 1)
  |> Enum.find(&match?([a, a], &1))
  |> hd()
end

Part 2

t = ...  # The total time
s = ...  # The distance the last champion traveled

approx.(t, s, t) - approx.(t, s, 0) - 1

I also considered the last race (when function breaking points are integers), that why my floor and ceil methods are more complicated:

defmodule AdventOfCode.Day06 do
  def part1(input) do
    calculate(input, fn numbers -> Enum.map(numbers, &String.to_integer/1) end)
  end

  def part2(input) do
    calculate(input, fn numbers -> [Enum.join(numbers) |> String.to_integer()] end)
  end

  defp calculate(input, mapping_function) do
    input
    |> String.split("\n", trim: true)
    |> Enum.map(fn line ->
      [_ | numbers] = String.split(line, ~r/\s+/)
      mapping_function.(numbers)
    end)
    |> Enum.zip()
    |> Enum.map(&count_wins/1)
    |> Enum.product()
  end

  defp count_wins({time, distance}) do
    delta = :math.sqrt(time * time - 4 * distance)
    x1 = (time + delta) / 2
    x2 = (time - delta) / 2

    to_floor(x1) - to_ceil(x2) + 1
  end

  defp to_ceil(x) do
    truncated = trunc(x)
    if truncated == x, do: truncated + 1, else: ceil(x)
  end

  defp to_floor(x) do
    truncated = trunc(x)
    if truncated == x, do: truncated - 1, else: floor(x)
  end
end

I thought of that, too, but fortunately, my input doesn’t have that problem

Anyway, the Newton’s approximation approach should be fine in all cases.