Advent of code 2023 day 8: Path finding in the desert - in pure Bash

Question

Part 1

In today's task, a network of paths is defined like this:

LLR

AAA = (BBB, BBB)
BBB = (AAA, ZZZ)
ZZZ = (ZZZ, ZZZ)

The first line LLR is instructions to follow to change position.

• When the current instruction is L, change position to the left value of the pair.
  • For example at position BBB the left value is AAA.
• When the current instruction is R, change position to the right value of the pair.
  • For example at position BBB the right value is ZZZ.
• The instructions loop around, so when reaching the last symbol, then start over from the first.

The task is to count the steps to reach from AAA to ZZZ. In the above example it takes 6 steps.

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

set -euo pipefail

solve_2023_day8_part1() {
  local instructions
  read -r instructions

  # Consume empty line.
  read -r

  local -A leftmap
  local -A rightmap
  local line pos left right

  while read -r line; do
    [[ $line =~ (...)\ =\ \((...),\ (...)\) ]]
    pos=${BASH_REMATCH[1]}
    left=${BASH_REMATCH[2]}
    right=${BASH_REMATCH[3]}

    leftmap[$pos]=$left
    rightmap[$pos]=$right
  done

  local i=0 steps=0
  pos="AAA"

  while [[ "$pos" != "ZZZ" ]]; do
    if [[ ${instructions:i:1} = "L" ]]; then
      pos=${leftmap[$pos]}
    else
      pos=${rightmap[$pos]}
    fi

    ((++steps))
    ((++i))
    ((i == ${#instructions})) && i=0
  done

  echo "$steps"
}

solve_2023_day8_part1

Part 2

For part 2, we are told that instead of just AAA, all positions that end with A are start positions, for example XXA would also be a start position. We are to move in parallel from all start positions, until all the positions end with Z at the same time.

After a few quick experiments it's easy to see that all start positions in the input arrive at positions ending with Z in regular cycles. Therefore, to determine the number of steps when all the positions end with Z at the same time, we can compute the least common multiple of all the individual cycle lengths.

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

set -euo pipefail

compute_gcd() {
  local a=$1
  local b=$2
  local temp

  while ((b > 0)); do
    ((temp = b))
    ((b = a % b))
    ((a = temp))
  done

  echo "$a"
}

compute_lcm() {
  local a=$1
  local b=$2
  local gcd

  gcd=$(compute_gcd "$a" "$b")
  echo $((a * b / gcd))
}

solve_2023_day8_part2() {
  local instructions
  read -r instructions

  # Consume empty line.
  read -r

  local -A leftmap
  local -A rightmap
  local line pos left right

  while read -r line; do
    [[ $line =~ (...)\ =\ \((...),\ (...)\) ]]
    pos=${BASH_REMATCH[1]}
    left=${BASH_REMATCH[2]}
    right=${BASH_REMATCH[3]}

    leftmap[$pos]=$left
    rightmap[$pos]=$right
  done

  local i steps lcm=1

  for pos in "${!leftmap[@]}"; do
    [[ "$pos" == ??A ]] || continue

    i=0
    steps=0

    while [[ "$pos" != ??Z ]]; do
      if [[ ${instructions:i:1} = "L" ]]; then
        pos=${leftmap[$pos]}
      else
        pos=${rightmap[$pos]}
      fi
      
      ((++steps))
      ((++i))
      ((i == ${#instructions})) && i=0
    done

    lcm=$(compute_lcm "$lcm" "$steps")
  done

  echo "$lcm"
}

solve_2023_day8_part2

Review request

I know 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. My main goals are:

• Compute the correct solution to the full input within seconds.
• Use idiomatic Bash.
• Easy to read and understand.

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?