5
\$\begingroup\$

Yesterday I thought was the last day of Advent Of Code 2023 that I do in Bash. I was wrong. I'm not even sure anymore that today will be the one. We'll just have to see tomorrow!

Part 1

To paraphrase the puzzle, given some input ("scratchcards") like this:

Card 1: 41 48 83 86 17 | 83 86  6 31 17  9 48 53
Card 2: 13 32 20 16 61 | 61 30 68 82 17 32 24 19
Card 3:  1 21 53 59 44 | 69 82 63 72 16 21 14  1
Card 4: 41 92 73 84 69 | 59 84 76 51 58  5 54 83
Card 5: 87 83 26 28 32 | 88 30 70 12 93 22 82 36
Card 6: 31 18 13 56 72 | 74 77 10 23 35 67 36 11

The task is:

  1. For each line, count the numbers on the right side that match numbers on the left side. These "winning numbers".
  2. Compute the sum of \$2^{count}\$.

That is, in the above example:

  • Card 1 has 4 winning numbers -- \$2^3\$ = 8
  • Card 2 has 2 winning numbers -- \$2^1\$ = 2
  • And so on...

The sum becomes 8 + 2 + 2 + 1 = 13.

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

set -euo pipefail

nums_to_lines() {
  local nums oldIFS
  nums=$1

  # Convert the space delimited values to an array.
  # Note: excess spaces are simply ignored.
  nums=($nums)

  # Print array values using newline as delimiter.
  oldIFS=$IFS
  IFS=$'\n'
  echo "${nums[*]}"
  IFS=$oldIFS
}

solve_2023_day4_part1() {
  local left right count sum

  sum=0
  # Read the left and right parts, delimited by '|' 
  while IFS='|' read left right; do
    # Strip the "Card N:" prefix from left.
    left=${left#*: }

    # Count the exact matches of numbers in the right among in the left.
    # Warning: running a program (grep) in a loop is inefficient.
    # When this becomes a performance bottleneck, this is easy enough
    # to implement in pure Bash.
    count=$(grep -xFcf <(nums_to_lines "$right") <(nums_to_lines "$left")) || continue

    # Compute power of 2 and add to sum.
    ((sum += 1 << (count - 1)))
  done

  echo "$sum"
}

solve_2023_day4_part1

Part 2

To paraphrase the change in part 2... no that would be too hard to paraphrase! So here's the description verbatim!

Copies of scratchcards are scored like normal scratchcards and have the same card number as the card they copied. So, if you win a copy of card 10 and it has 5 matching numbers, it would then win a copy of the same cards that the original card 10 won: cards 11, 12, 13, 14, and 15. This process repeats until none of the copies cause you to win any more cards. (Cards will never make you copy a card past the end of the table.)

This time, the above example goes differently:

Card 1: 41 48 83 86 17 | 83 86  6 31 17  9 48 53
Card 2: 13 32 20 16 61 | 61 30 68 82 17 32 24 19
Card 3:  1 21 53 59 44 | 69 82 63 72 16 21 14  1
Card 4: 41 92 73 84 69 | 59 84 76 51 58  5 54 83
Card 5: 87 83 26 28 32 | 88 30 70 12 93 22 82 36
Card 6: 31 18 13 56 72 | 74 77 10 23 35 67 36 11
  • Card 1 has four matching numbers, so you win one copy each of the next four cards: cards 2, 3, 4, and 5.
  • Your original card 2 has two matching numbers, so you win one copy each of cards 3 and 4.
  • Your copy of card 2 also wins one copy each of cards 3 and 4.
  • Your four instances of card 3 (one original and three copies) have two matching numbers, so you win four copies each of cards 4 and 5.
  • Your eight instances of card 4 (one original and seven copies) have one matching number, so you win eight copies of card 5.
  • Your fourteen instances of card 5 (one original and thirteen copies) have no matching numbers and win no more cards.
  • Your one instance of card 6 (one original) has no matching numbers and wins no more cards.

Once all of the originals and copies have been processed, you end up with 1 instance of card 1, 2 instances of card 2, 4 instances of card 3, 8 instances of card 4, 14 instances of card 5, and 1 instance of card 6. In total, this example pile of scratchcards causes you to ultimately have 30 scratchcards!

Process all of the original and copied scratchcards until no more scratchcards are won. Including the original set of scratchcards, how many total scratchcards do you end up with?

See what I mean? That's a mouthful!

# (omitted: boilerplate header and shared nums_to_lines function from part 1)

solve_2023_day4_part2() {
  local counts index left right count nextIndex sum

  # Storage to track the card counts at indexes.
  counts=()
  index=0

  sum=0
  # Read the left and right parts, delimited by '|' 
  while IFS='|' read left right; do
    # Initialize or increment counter.
    if [[ ${counts[$index]+x} ]]; then
      ((++counts[index]))
    else
      ((counts[index] = 1))
    fi

    # Strip the "Card N:" prefix from left.
    left=${left#*: }

    # Count the exact matches of numbers in the right among in the left.
    # Warning: running a program (grep) in a loop is inefficient.
    # When this becomes a performance bottleneck, this is easy enough
    # to implement in pure Bash.
    count=$(grep -xFcf <(nums_to_lines "$right") <(nums_to_lines "$left")) || true
    ((sum += counts[index]))

    # Update the count of subsequent cards.
    # Warning: there may be wasted storage and CPU here for indexes beyond
    # the number of cards. Ignoring that for now until it becomes a problem.
    for ((nextIndex = index + 1; nextIndex < index + 1 + count; ++nextIndex)); do
      if [[ ${counts[$nextIndex]+x} ]]; then
        ((counts[nextIndex] += counts[index]))
      else
        ((counts[nextIndex] = counts[index]))
      fi
    done

    ((++index))
  done

  echo "$sum"
}

solve_2023_day4_part2

Review request

I do realize this is a bit whimsical, and Bash is not a great choice to solve algorithmic puzzles. The solver is intended as a one-off, and not for reuse.

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?

The Devil's advocate

I'll be the first to say that the grep sticks out like a sore thumb. It's a major performance hit with multiple subprocesses for each line of input, for something that can be easily written in native Bash. I didn't bother to optimize that part because:

  1. This is fast enough for its purpose, at less than 1 second on my laptop.
  2. I have no plans for future extensions of this script.
  3. I thought this is a nice demonstration of things you can do with grep, and a more interesting solution than my Bash implementation would be.
\$\endgroup\$
1

2 Answers 2

3
\$\begingroup\$

one word per line

In nums_to_lines, these six lines follow a very clear pattern. But it seems a bit long. I tend to use echo ${nums} | fmt -w1 when numpy's nums.T transpose operator is not available.

I do like the conservative set.


matching

grep -xFcf  <(nums_to_lines "$right")  < /tmp/winning-numbers.txt

For clarity, maybe start with grep -c? The -x and -F are closely related to each other, and related to the following -f, essentially producing this for that first example card:

grep -c '^(83|86|6|31|17|9|48|53)$'  < /tmp/winning-numbers.txt

There are many ways to skin this cat. I thought for sure I would see sort -n invocations, followed by comm -12, as the most natural way to compute set intersection in a bash pipeline.


no fork

    # Strip the "Card N:" prefix from left.
    left=${left#*: }

Thank you very much for that comment. It is not merely helpful; it is essential. Else I would have no idea what that expression had computed. (Recommend you elide the final SPACE after the : colon.)

The trouble with bash line noise is that it's so difficult to consult the bash docs to find what an expression means. Grep reports thirty matches for # hash, twice that for * star, and twice again for : colon. We have accreted one feature after another for more than half a century, and at some point the edifice sags under its own weight.

IMHO, echo $left | sed 's/^Card [0-9]*: //' would more clearly express Author's Intent, without need of a comment. But maybe that just comes from using regexes so often in lots of contexts, some of them involving a bash command line.

    # Compute power of 2 and add to sum.
    ((sum += 1 << (count - 1)))

Again, I thank you for the helpful comment. Not quite as essential, but still helpful.

And I'm surprised that the swiss army knife named bash lacks exponentiation. Guess we didn't like the bc ^ power operator?

It would cost a fork(). And would save on clarity.


default dict

I confess I'm a bit spoiled by python's standard library. We see this pattern pop up in any language that offers a HashMap, which is to say, in every language.

      if [[ ${counts[$nextIndex]+x} ]]; then
        ((counts[nextIndex] += counts[index]))
      else
        ((counts[nextIndex] = counts[index]))
      fi

This is perfectly lovely as-is.

I ask one and all: Is there some bash idiom for expressing this more compactly? (Specifically, for incrementing a possibly non-existent entry as though it already held a 0.)

\$\endgroup\$
2
  • \$\begingroup\$ I don't think sort -n + comm -12 is "the most natural way" to compute set intersection in a bash pipeline. It's a way. As for navigating man bash, yes it helps to know the proper terms for some constructs, in this example "Parameter Expansion". Other than that, I find it fantastic docs, almost everything is there. As for default dict, I learned a neat trick from Choroba, see my answer. \$\endgroup\$
    – janos
    Dec 5, 2023 at 5:29
  • \$\begingroup\$ Ooohhh, I like it. I use e.g. first_param=${1:-default_value} all the time, but it hadn't occurred to me to use it in this context. Nice. // As far as "natural" goes, I shy away from quadratic solutions if I can get O(N log N) plus 2-way merge to accomplish the same task. Sometimes an RDBMS is doing the heavy lifting for that, but not always. It's just how I think about the data flow. And then I look for a matching tool. \$\endgroup\$
    – J_H
    Dec 5, 2023 at 6:26
3
\$\begingroup\$

Got a tip from @choroba's alternative solution.

To conditionally initialize or update an entry in a map, instead of:

if [[ ${counts[$nextIndex]+x} ]]; then
  ((counts[nextIndex] += counts[index]))
else
  ((counts[nextIndex] = counts[index]))
fi

A simpler idiom is using Default Values syntax ${parameter:-word} of Parameter Expansion:

((counts[$nextIndex] = ${counts[$nextIndex]:-0} + counts[index]))

This is applicable at two places in the solution for Part 2, making the code simpler and more compact.

This is compatible with set -u (no errors raised for referencing an undefined value).

\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.