Advent of code 2023 day 6: Count ways to win boat race - in pure Bash

Question

Part 1

To paraphrase the puzzle, given the times and record distances of boat races like this:

Time:      7  15   30
Distance:  9  40  200

That is, the first runs for 7 milliseconds, and the record distance so far is 9 millimeters. The way a race takes place is you hold your boat for \$t\$ milliseconds, and after release it will travel \$t\$ millimeters in every millisecond. The goal in each race is to travel further than the previous record within the given time. The answer to the puzzle is the product of the number of ways to win each race, in the above example 4 * 8 * 9 = 288.

#!/usr/bin/env bash
#
# Solver for https://adventofcode.com/2023/day/6 part 1
# Redirect the input file to this script, for example day6part1.sh < path/to/input.txt
#

set -euo pipefail

solve_2023_day6_part1() {
  # Read times and convert to an array.
  local times
  read -r _ times
  # Disable warning, we specifically want word splitting now.
  # shellcheck disable=SC2206
  times=($times)

  # Read distances and convert to an array.
  local distances
  read -r _ distances
  # Disable warning, we specifically want word splitting now.
  # shellcheck disable=SC2206
  distances=($distances)

  # Note that the distance function is quadratic, and symmetric around the middle.
  # Count the ways until we reach the distance, and derive the total possible ways from that.
  local max_time min_distance
  local answer i t distance ways
  answer=1
  for ((i = 0; i < ${#times[@]}; ++i)); do
    max_time=${times[i]}
    min_distance=${distances[i]}
    for ((t = 1; t < max_time; ++t)); do
      ((distance = t * (max_time - t)))
      ((min_distance < distance)) && break
    done
    ((ways = max_time - 2 * (t - 1) - 1))
    ((answer *= ways))
  done

  echo "$answer"
}

solve_2023_day6_part1

Part 2

In part 2, it turns out that there really is just one race to beat, for which we get the parameters by removing the spaces from the input. In the above example the time is 71530 and the distance is 940200, and there are 71503 ways to do it.

This change makes the input significantly larger. Although the solution for part 1 would still work just by adapting to the new input format (or by simply modifying the input by hand and no code change), it would be very slow, so I added a binary search to speed it up significantly.

#!/usr/bin/env bash
#
# Solver for https://adventofcode.com/2023/day/6 part 2
# Redirect the input file to this script, for example day6part2.sh < path/to/input.txt
#

set -euo pipefail

solve_2023_day6_part2() {
  # Parse the max time of the single race, stripping excess spaces.
  local max_time
  read -r _ max_time
  max_time=${max_time// /}

  # Parse the minimum distance parameter we have to reach, stripping excess spaces.
  local min_distance
  read -r _ min_distance
  min_distance=${min_distance// /}

  # Find the minimum time we need to the target distance using binary search.
  # Note that the distance function is quadratic, and symmetric around the middle.
  local min_wait
  left=1
  ((right = max_time / 2 + max_time % 2))
  while ((left < right)); do
    ((mid = left + (right - left) / 2))
    ((distance = (max_time - mid) * mid))
    if ((distance <= min_distance)); then
      ((left = mid + 1))
    else
      ((right = mid))
    fi
  done
  min_wait=$left

  echo "$((1 + max_time - 2 * min_wait))"
}

solve_2023_day6_part2

Review request

I do realize this is a bit whimsical, and Bash is a poor choice to solve algorithmic puzzles. Also, this code is intended as a one-off, and not for reuse. I'm solving in Bash because, and as long as, it gives me joy. I won't make promises about how far I'm willing to stick to pure Bash, it will depend on the day and my mood. The main principles I do intend to stick to are:

• The program must produce the correct solution to the full input within seconds.
• The program must use idiomatic Bash.

Do you see any patterns here that you would replace with better patterns?

Do you see a simpler way to solve any part of the puzzle with Bash and common shell tools?

What would you do differently?