# Advent of code 2023 day 9: Sequence extrapolation - in pure Bash

### Part 1

Today's task involves extrapolating the next value in sequences, given in this format:

0 3 6 9 12 15
1 3 6 10 15 21
10 13 16 21 30 45

The task is to extrapolate the next value of the sequences, by computing the difference between adjacent elements, and iterating on the resulting sequence until all the items are identical. Going with the last example, the sequences computed from the differences would be:

10  13  16  21  30  45  68
3   3   5   9  15  23
0   2   4   6   8
2   2   2   2
0   0   0

The task is to sum the extrapolated next value of the input sequences, in the above example 18 + 28 + 68 = 114.

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

set -euo pipefail

solve_2023_day9_part1() {
local sum=0 line nums new_nums i
local -A diffs

# Disable warning, we specifically want word splitting now.
# shellcheck disable=SC2206
nums=($line) while true; do ((sum += nums[-1])) new_nums=() diffs=() for ((i = 1; i <${#nums[@]}; i++)); do
new_nums+=($((nums[i] - nums[i-1]))) diffs[${new_nums[-1]}]=1
done
((${#diffs[@]} != 1)) || break nums=("${new_nums[@]}")
done
((sum += new_nums[-1]))
done

echo "$sum" } solve_2023_day9_part1 ### Part 2 Part 2 is a minor twist on part 1: apply the extrapolation logic in reverse to compute the preceding values, and sum those. In the above example this would be -3 + 0 + 5 = 2. #!/usr/bin/env bash # # Solver for https://adventofcode.com/2023/day/9 part 2 # Redirect the input file to this script, for example day9part2.sh < path/to/input.txt # set -euo pipefail solve_2023_day9_part2() { local sum=0 line nums new_nums i heads local -A diffs while read -r line; do # Disable warning, we specifically want word splitting now. # shellcheck disable=SC2206 nums=($line)
heads=("${nums[0]}") while true; do new_nums=() diffs=() for ((i = 1; i <${#nums[@]}; i++)); do
new_nums+=($((nums[i] - nums[i-1]))) diffs[${new_nums[-1]}]=1
done
heads+=("${new_nums[0]}") ((${#diffs[@]} != 1)) || break
nums=("${new_nums[@]}") done for ((i = 0; i <${#heads[@]}; i += 2)); do
done
for ((i = 1; i < ${#heads[@]}; i += 2)); do ((sum -= heads[i])) || true done done echo "$sum"
}

solve_2023_day9_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?

• Janos asked tons of questions about this subject recently. Not sure why he is excited by awk, bash ..., suddenly :) Commented Dec 11, 2023 at 10:29