2
\$\begingroup\$

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?

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

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.