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

Question

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
 while read -r line; do
 # 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
 ((sum += heads[i])) || true
 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?

• Billal BEGUERADJ: Janos asked tons of questions about this subject recently. Not sure why he is excited by awk, bash ..., suddenly :)

Answer 1

I like this set of options:

set -euo pipefail

It's good to see the implication that we have tested for common errors here:

 while read -r line; do
 # Disable warning, we specifically want word splitting now.
 # shellcheck disable=SC2206
 nums=($line)
 heads=("${nums[0]}")

A better alternative might be readarray:

 while
 read -r line &&
 readarray -t -d ' ' nums <<<"$line" &&
 [ "${nums[*]}" ]
 do

We can reduce the scope of some of the variables:

 local sum=0 line nums
 while
 read -r line &&
 readarray -t -d ' ' nums <<<"$line" &&
 [ "${nums[*]}" ]
 do
 local new_nums i
 local -A diffs
 while true; do

Instead of while true with a break, we can invert and move the test:

 while
 ((sum += nums[-1]))
 local -A diffs
 for ((i = 1; i < ${#nums[@]}; i++)); do
 new_nums+=($((nums[i] - nums[i-1])))
 diffs[${new_nums[-1]}]=1
 done
 ((${#diffs[@]} == 1))
 do
 nums=("${new_nums[@]}")
 done

---

I'd be inclined to restructure into functions than can work with "$@" rather than needing multiple named arrays. The simplest is to use a recursive function to find the successor value to a row by adding the successor value from the next row:

next_int() {
 [ $# -gt 0 ] || return
 local -a next_row
 while [ $# -gt 1 ]
 do
 next_row+=($((2ドル - 1ドル)))
 shift
 done
 echo $(($(next_int "${next_row[@]}") + 1ドル))
}

We then just call this function for each line:

solve_2023_day9_part1() {
 local -i sum=0
 local line
 local -a nums
 while
 read -r line &&
 readarray -t -d ' ' nums <<<"$line" &&
 [ "${nums[*]}" ]
 do
 sum+=$(next_int "${nums[@]}")
 done
 echo "$sum"
}

That means that the Part 2 solution becomes very similar - we just need the recursive function to subtract the next row's result from the first element:

prev_int() {
 [ $# -gt 0 ] || return
 local -a next_row
 local -i first=1ドル n
 while [ $# -gt 1 ]
 do
 next_row+=($((2ドル - 1ドル)))
 shift
 done
 n=$(prev_int "${next_row[@]}")
 echo $((first - n))
}

And the outer function only needs minimal change to call prev_int rather than next_int:

solve_2023_day9_part2() {
 local -i sum=0
 local line
 local -a nums
 while
 read -r line &&
 readarray -t -d ' ' nums <<<"$line" &&
 [ "${nums[*]}" ]
 do
 sum+=$(prev_int "${nums[@]}")
 done
 echo "$sum"
}