Advent of Code 2021 Day 8

10 Dec 2021 . category: . Comments

This marks the second year that I’ve done Advent of Code. Now and then, I’d like to write about my experience with a given day’s puzzle. Advent of Code is free, it’s fun, and you probably already know someone who’s doing it. Check it out!

Day 8 finds us having a bit of trouble with some seven-segment displays,

The problem is that the signals which control the segments have been mixed up on each display. The submarine is still trying to display numbers by producing output on signal wires a through g, but those wires are connected to segments randomly. Worse, the wire/segment connections are mixed up separately for each four-digit display!

So, our puzzle input has the following for each display:

• the ten signal combinations used to represent digits 4-9
• 4 signal combinations describing a 4-digit number.

Part 1: Find the Unique Digits

Part 1 asks us to count the number of times the digits 1, 4, 7, and 8 appear in the displays. To begin, let’s group the digits 0 through 9 by the number of segments we’ll need to represent them.

  0:      1:      2:      3:      4:
 aaaa    ....    aaaa    aaaa    ....
b    c  .    c  .    c  .    c  b    c
b    c  .    c  .    c  .    c  b    c
 ....    ....    dddd    dddd    dddd
e    f  .    f  e    .  .    f  .    f
e    f  .    f  e    .  .    f  .    f
 gggg    ....    gggg    gggg    ....

  5:      6:      7:      8:      9:
 aaaa    aaaa    aaaa    aaaa    aaaa
b    .  b    .  .    c  b    c  b    c
b    .  b    .  .    c  b    c  b    c
 dddd    dddd    ....    dddd    dddd
.    f  e    f  .    f  e    f  .    f
.    f  e    f  .    f  e    f  .    f
 gggg    gggg    ....    gggg    gggg

• 2 segments: 1
• 3 segments: 7
• 4 segments: 4
• 5 segments: 2, 3, 5
• 6 segments: 0, 6, 9
• 7 segments: 8

So, for part 1, we could literally just count the length of the signal combination and determine if it’s 1, 7, 4, or 8. The following isn’t my solution, but it does get the right answer for part 1.

func part1(input []string) int {
  acc := 0
  for _, s := range input {
    parts := strings.Split(s, " | ")
    for _, digit := range strings.Fields(parts[1]) {
      if segs := len(digit); (segs >= 2 && segs <= 4) || segs == 7 {
        acc++
      }
    }
  }
  return acc
}

Easy, right? It’s about to get a bit harder. Part 2 asks us to map the 10 signal combinations into the digits 0-9 and and decode the display value. Now, which segments are lit suddenly becomes more important. I’ve got two problems that I need to solve:

• How do I easily compare two signal combinations to know they’re the same?
• How can I determine the remaining signals?

Part 2: Bitvectors and Bitmasking

One of the big challenges in this problem is that the signal combination can be in any order! As a example, the following combinations are equivalent:

bcdf fdcb fbdc fcdb

I need a way to quickly determine what makes them equivalent. This is where a bitvector really comes in handy. Let’s imagine I have a 7-bit number, where each bit corresponds to the signals a thru g. I could then represent all the above signals like so:

0101110
-------
gfedcba

All 4 forms of the signal combination produce the same bitvector: 46 (0101110 in binary). Using this pattern, I can quickly establish bitvectors for digits 1, 7, 4, and 8. Here’s how we could determine the bitvector for a given string:

func toBitvector(s string) uint {
	val := uint(0)
	for _, c := range s {
		val = val | 1<<(c-'a')
	}
	return val
}

At this point, you might be wondering: Vishal, couldn’t you just sort the strings and see that they’re all anagrams? Well, yes, but the next task is going to make bitvectors a little more essential. Let’s take a look at the number 3 for a moment.

  3:  
 aaaa 
.    c
.    c
 dddd 
.    f
.    f
 gggg 

Given that I know the bitvectors for some of the digits, can I figure out if a given signal combination is a 3? Well, let’s look at all of the 5-segment numbers.

  3:       2:     5:  
 aaaa    aaaa    aaaa 
.    c  .    c  b    .
.    c  .    c  b    .
 dddd    dddd    dddd 
.    f  e    .  .    f
.    f  e    .  .    f
 gggg    gggg    gggg 

Hm. Only the number 3 has segments c and f lit. I do know the bitvector for those segments, it’s the 1 digit. By using bitwise operations, I can use the bitvector for the 1 digit to test if this unknown bitvector is the 3 digit. To lllustrate this, let’s take the intersection of the 1 digit with each of the numbers above. That is, let’s show which segments are lit in both the 1 digit and each of 2, 3, and 5:

1 & 3:   1 & 2:  1 & 5:  
 ....    ....    .... 
.    c  .    c  .    .
.    c  .    c  .    .
 ....    ....    .... 
.    f  .    .  .    f
.    f  .    .  .    f
 ....    ....    .... 

Only the 3 digit fully overlaps with the 1 digit. So, even though we don’t know how the signals correspond to the segments, we do know that a 5-segment signal is definitively for the 3 digit if a bitwise AND operation with the 1 digit bitvector yields the 1 digit bitvector. In a similar manner, we can use the known digits as bitmasks to uncover the rest of the signals. The table below shows how we can do this.

"mystery" bitvector given as bv
5-segment signals:
3 -> bv & bitvector[1] == bitvector[1]
2 -> bv &^ bitvector[4] has 3 bits set
5 -> not 3 or 2

6-segment signals:
9 -> bv & bitvector[4] == bitvector[4]
0 -> bv & bitvector[1] == bitvector[1]
6 -> not 9 or 0

The only funky one in the bunch is the 2 digit. It uses the complement of the bitvector for the 4 digit, meaning that it uses all 3 segments that the 4 digit doesn’t.

With this approach, we can build up a hash table of bitvector to digit and decode our solution!

You can see my solution here.

Takeaways

One of the big challenges with this problem is anagram detection. That is, determining if a pair of strings have all the same characters. While you could sort the strings or use a counting sort, using a bitvector works here because we know that each string has no more than one of each character. Choosing a bitvector also makes sense because it lets us deduce signals using bitwise operations. This lets us look at the intersection of digits to make a determination on which digit is which.

Thankfully, I didn’t need to worry about a ton of defensive coding here! I could rely on the input to be properly formed without worrying about invalid signal combinations like aabc. This is a pattern with Advent of Code – the inputs are friendly and tend to not expose corner cases, for better or worse.

Vishal Kotcherlakota is a reformed sysadmin, who writes code and will talk incessantly about DevOps to anyone who will listen. All views expressed here are his and not those of his employers.