Advent of Code 2021 Day 8: Seven Segment Search

By Andreas Røssland

https://adventofcode.com/2021/day/8 https://github.com/roessland/advent-of-code

This was a tricky one. I would have saved a lot of time if I just read the problem properly instead of coding first, banging my head, then reading the problem properly.

The task was to descramble each display. For each display you get an input/output combo like this, where the data before the pipe is the input and the data after the pipe is the output.

be cfbegad cbdgef fgaecd cgeb fdcge agebfd fecdb fabcd edb |
fdgacbe cefdb cefbgd gcbe

What took me some time to realize is that the the input contains the signal combinations corresponding to every digit from 0-9, exactly once.

I represented each signal combination as a set, implemented as a byte. So be becomes 0b10010, since b is 0b10 and e is 0b10000.

type Signals uint8

func SetOf(str string) Signals {
	var set Signals
	for _, c := range str {
		set = set | (1 << (c - 'a'))
	}
	return set
}

func (set Signals) Len() int {
	return bits.OnesCount8(uint8(set))
}

Some example usage of this set implementation:

0b10 = SetOf("b")
0b11 = SetOf("ba")
0b101 = SetOf("c")|SetOf("a")
5 = SetOf("acdeg").Len()
2 = (SetOf("acdeg") & SetOf("acf")).Len()) 
6 = (SetOf("acdeg") | SetOf("acf")).Len()

Part 1 is trivial, and is just to count how many signal combos are either 1, 4, 7 or 8, since these are the digits that can be uniquely identified from the number of segments only. The remaining digits require more clever logic.

func part1(displays []Display) {
	n := 0
	for _, display := range displays {
		for _, signals := range display.Outputs {
			if signals.Len() == 2 || signals.Len() == 4 || signals.Len() == 3 || signals.Len() == 7  { // 1
				n++
			}
		}
	}
	fmt.Println("Part 1:", n)
}

For part 2 I figured out by trial and error that each signal combination can be mapped to a digit if you know the following:

  • How many segments are on?
  • How many segments does the intersection of this combo and 7 have?
  • How many segments does the union of this combo and 7 have?
  • How many segments does the intersection of this combo and 4 have?
i|i||i∩7||i∪7||i∩4|
06363
12
25262
353
44
55263
662
73
87
96364

Only the necessary criteria are listed. For example, if you have a signal combo with cardinality 4, you have found the number 4, and there is no need to check further. I found these numbers by analyzing the chart below.

  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

Now part 2 can be solved with a two pass process:

  1. Find 1, 4, 7, 8
  2. Find 0, 2, 3, 5, 6, 9 using the table above.
func part2(displays []Display) {
	totalOutput := 0
	for _, display := range displays {
		signalsFor := make(map[int]Signals)

		// First pass -- Get 1, 4, 7 since they are uniquely identified by
		// the number of segments only.
		for _, signals := range display.Inputs {
			if signals.Len() == 2 { // 1
				signalsFor[1] = signals
			} else if signals.Len() == 4 { // 4
				signalsFor[4] = signals
			} else if signals.Len() == 3 { // 7
				signalsFor[7] = signals
			} else if signals.Len() == 7 { // 8
				signalsFor[8] = signals
			}
		}

		// Second pass -- Moderately clever logic based on set operations.
		for _, signals := range display.Inputs {
			switch signals {
			case signalsFor[1], signalsFor[4], signalsFor[7], signalsFor[8]:
				continue
			}
			Len := signals.Len()
			and7 := (signalsFor[7] & signals).Len()
			or7 := (signalsFor[7] | signals).Len()
			and4 := (signalsFor[4] & signals).Len()

			if Len == 6 && and7 == 3 && or7 == 6 && and4 == 3 {
				signalsFor[0] = signals
			} else if Len == 5 && and7 == 2 && or7 == 6 && and4 == 2 {
				signalsFor[2] = signals
			} else if Len == 5 && and7 == 3  {
				signalsFor[3] = signals
			} else if Len == 5 && and7 == 2 && or7 == 6 && and4 == 3  {
				signalsFor[5] = signals
			} else if Len == 6 && and7 == 2 {
				signalsFor[6] = signals
			} else if Len == 6 && and7 == 3 && or7 == 6 && and4 == 4 {
				signalsFor[9] = signals
			}
		}

		// Decode output
		totalOutput += Decode(signalsFor, display.Outputs)
	}
	fmt.Println("Part 2:", totalOutput)
}

And finally, the boilerplate and I/O code. Go is pretty verbose. But readable, I hope.

package main

import (
	"bufio"
	"fmt"
	"log"
	"math/bits"
	"os"
	"strings"
)

type Display struct {
	Inputs  []Signals
	Outputs []Signals
}

func main() {
	patterns := ReadInput()
	part1(patterns)
	part2(patterns)
}

func part1(displays []Display) {
	n := 0
	for _, display := range displays {
		for _, signals := range display.Outputs {
			if signals.Len() == 2 || signals.Len() == 4 || signals.Len() == 3 || signals.Len() == 7  { // 1
				n++
			}
		}
	}
	fmt.Println("Part 1:", n)
}


func Decode(p map[int]Signals, signalsList []Signals) int {
	digitForSignals := make(map[Signals]int)
	for digit, signals := range p {
		digitForSignals[signals] = digit
	}

	out := 0
	for _, signals := range signalsList {
		out = out*10 + digitForSignals[signals]
	}
	return out
}


func ReadInput() []Display {
	f, err := os.Open("input.txt")
	if err != nil {
		log.Fatal(err)
	}
	scanner := bufio.NewScanner(f)
	var patterns []Display
	for scanner.Scan() {
		parts := strings.Split(scanner.Text(), " | ")
		pat := Display{}
		for _, signalsStr := range strings.Split(parts[0], " ") {
			pat.Inputs = append(pat.Inputs, SetOf(signalsStr))
		}
		for _, signalsStr := range strings.Split(parts[1], " ") {
			pat.Outputs = append(pat.Outputs, SetOf(signalsStr))
		}
		patterns = append(patterns, pat)
	}
	return patterns
}