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

### 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

# Consume empty line.

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

[[ $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?