Skip to main content

Day 8: Seven Segment Search

by @bishabosha

Puzzle description​

https://adventofcode.com/2021/day/8

Solution of Part 1​

Modelling the Domain​

First we will model our problem so that we can parse the input into our model.

Let's look at the representation of display digits from the problem: we see that there are a fixed number of possible digits for a display, and that each digit is made by activating some segments, where there are a fixed number of possible segments:

  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

Segment​

As there are a fixed range of possible display segments: a, b, c, d, e, f, g, we will model them with an enumeration.

An enumeration is used to define a type consisting of a set of named values. Read the official documentation for more details.

Our enumeration Segment looks like the following:

enum Segment:
  case A, B, C, D, E, F, G

Digit​

Next, we will model the possible digits of a display. Again, there are a fixed number of them so we will use an enumeration.

A digit is made by lighting a number of segments, so we will associate each digit with the segments required to light it, we can do this by adding a parameter to Digit:

enum Digit(val segments: Segment*):
  case Zero extends Digit(A, B, C, E, F, G)
  case One extends Digit(C, F)
  case Two extends Digit(A, C, D, E, G)
  case Three extends Digit(A, C, D, F, G)
  case Four extends Digit(B, C, D, F)
  case Five extends Digit(A, B, D, F, G)
  case Six extends Digit(A, B, D, E, F, G)
  case Seven extends Digit(A, C, F)
  case Eight extends Digit(A, B, C, D, E, F, G)
  case Nine extends Digit(A, B, C, D, F, G)

In the above case One extends Digit(C, F) defines a Digit: One which has segments C and F.

Segment Strings, aka Segments​

In the input we see many sequences of strings, such as "fdcagb", which we will call segment strings. We can think of a segment string as a set of characters that represent the segments lit in a single digit of a display. These segments are not necessarily the correct configuration for viewing by humans.

We will model a segment string in Scala by values of type Set[Segment], which we will simplify with a type alias Segments, defined in the companion object of Segment:

object Segment:
  type Segments = Set[Segment]

Finding A Unique Digit from Segments​

The problem asks us to find segment strings that correspond to the digits with a unique number of segments.

If we group the digits by the number of segments they have, we can see the following picture:

No. SegmentsDigits
2{ One }
3{ Seven }
4{ Four }
5{ Two , Three , Five }
6{ Zero , Six , Nine }
7{ Eight }

We can build the table above with the following code:

val bySizeLookup: Map[Int, Seq[Digit]] =
  Digit.values.toIndexedSeq.groupBy(_.segments.size)

In the above, we can access all Digit values with the built in values method of the companion, here we have converted it to a Seq for convenience.

However we are only interested in the entries where the segment count is linked to a single digit. We can remove the entries with more than one digit, and map each key to a single digit with a collect call:

val uniqueLookup: Map[Int, Digit] =
  bySizeLookup.collect { case k -> Seq(d) => k -> d }

You can think of the above as "keep all entries where k is mapped to a singleton sequence, and map k instead to that single element d."

The content of uniqueLookup looks like the following:

Map(2 -> One, 3 -> Seven, 4 -> Four, 7 -> Eight)

For our problem, we need to lookup a Digit from a segment string, which we will implement in the companion of Digit, with a method lookupUnique. The method takes a segment string (of type Segments), and returns an Option[Digit].

To implement this, we call get on uniqueLookup with the size of the segment string, which returns an Option[Digit], depending on whether the key was present.

Here is the final companion of Digit (where uniqueLookup inlines the definition of bySizeLookup):

object Digit:

  val index: IndexedSeq[Digit] = values.toIndexedSeq

  private val uniqueLookup: Map[Int, Digit] =
    index.groupBy(_.segments.size).collect { case k -> Seq(d) => k -> d }

  def lookupUnique(segments: Segments): Option[Digit] =
    uniqueLookup.get(segments.size)

Parsing the input​

Parsing Segments​

We will parse each segment string into Segments aka a Set[Segment].

First, we add a char field to our Segment enum: its computed by making the first character of toString lower-case:

enum Segment:
  case A, B, C, D, E, F, G

  val char = toString.head.toLower

Next within Segment's companion object we define:

  • a reverse map fromChar, which can lookup any Segment with a matching char field.
  • a method parseSegments which takes a segment string (typed as String) and converts it to a Set[Segment], by looking up the corresponding Segment of each character of the string, using fromChar.

The final companion object to Segment can be seen below:

object Segment:
  type Segments = Set[Segment]

  val fromChar: Map[Char, Segment] = values.map(s => s.char -> s).toMap

  def parseSegments(s: String): Segments =
    s.map(fromChar).toSet
info

Please note that in parseSegments I am assuming that fromChar will contain each character of the input string s, which is only safe with correct input. With invalid input it will throw NoSuchElementException.

To be more explicit with error handling, we could wrap parseSegments with a Try.

Parsing the input file​

For part 1 we only need to read the four digit display section of each line, we can parse this from a line with the following function getDisplay:

def getDisplay(line: String): String = line.split('|')(1).trim

Above, we call line.split('|'), which will make an Array of the two halves of the line: before and after |. We are only interested in the second half, so we access the element at index 1, and then call trim to remove leading/terminating spaces.

After using getDisplay we will have a string display, e.g. "fdgacbe cefdb cefbgd gcbe". Next we call display.split(' '), to get a sequence of segment strings, e.g. Array("fdgacbe", "cefdb", "cefbgd", "gcbe").

Computing the Solution​

Finally we want to lookup a possible unique digit for each segment string.

We will create a helper function parseUniqueDigit which first parses a segment string as Segments and then looks up a unique Digit:

def parseUniqueDigit(s: String): Option[Digit] =
  Digit.lookupUnique(Segment.parseSegments(s))

Then, to compute the final result we will proceed as follows, for each line get the display output display, then for each display find each encoded digit segments, for each encoded digit lookup a possible digit that uniquely matches. Then get the size of the resulting unique digits:

// `input` is the input file as a String
val uniqueDigits: Iterator[Digit] =
  for
    display <- input.linesIterator.map(getDisplay)
    segments <- display.split(" ")
    uniqueDigit <- parseUniqueDigit(segments)
  yield
    uniqueDigit

uniqueDigits.size

Final Code​

The final code for part one is as follows:

import Segment.*

enum Segment:
  case A, B, C, D, E, F, G

  val char = toString.head.toLower

object Segment:
  type Segments = Set[Segment]

  val fromChar: Map[Char, Segment] = values.map(s => s.char -> s).toMap

  def parseSegments(s: String): Segments =
    s.map(fromChar).toSet

end Segment

enum Digit(val segments: Segment*):
  case Zero extends Digit(A, B, C, E, F, G)
  case One extends Digit(C, F)
  case Two extends Digit(A, C, D, E, G)
  case Three extends Digit(A, C, D, F, G)
  case Four extends Digit(B, C, D, F)
  case Five extends Digit(A, B, D, F, G)
  case Six extends Digit(A, B, D, E, F, G)
  case Seven extends Digit(A, C, F)
  case Eight extends Digit(A, B, C, D, E, F, G)
  case Nine extends Digit(A, B, C, D, F, G)

object Digit:

  val index: IndexedSeq[Digit] = values.toIndexedSeq

  private val uniqueLookup: Map[Int, Digit] =
    index.groupBy(_.segments.size).collect { case k -> Seq(d) => k -> d }

  def lookupUnique(segments: Segments): Option[Digit] =
    uniqueLookup.get(segments.size)

end Digit

def part1(input: String): Int =

  def getDisplay(line: String): String = line.split('|')(1).trim

  def parseUniqueDigit(s: String): Option[Digit] =
    Digit.lookupUnique(Segment.parseSegments(s))

  val uniqueDigits: Iterator[Digit] =
    for
      display <- input.linesIterator.map(getDisplay)
      segments <- display.split(" ")
      uniqueDigit <- parseUniqueDigit(segments)
    yield
      uniqueDigit

  uniqueDigits.size
end part1

Solution of Part 2​

Modelling the Domain​

For part 2 we can reuse all data structures from part 1.

Cryptography and Decoding​

In part 2 we are asked to decode each four digit display to an integer number. The problem is that each display is wired incorrectly, so while the signals to the display are for a correct digit, the observable output is different.

We know that the configuration of wires is stable, so for each display we are given a list of the 10 possible visible output signals of the display (one for each digit).

This problem is identical to a substitution cipher, where the encoded alphabet is the mismatch of wires to segments, and words are output signals (aka encoded digits). We can rediscover the original alphabet by recognising words (aka finding how each digit has been encoded).

To solve the problem, we will take the list of 10 unique output signals (the 10 possible digits) and produce a dictionary of these associated to their decoded forms (aka a map of type Map[Segments, Digits]).

Discovering the Encoded Digits​

In part 1 we discovered how to identify One, Four, Seven and Eight from encoded digits because their encoded forms one, four, seven and eight are composed of a unique number of segments. After finding those digits, we are left with six more digits to discover:

  • those with 5 segments: { two , three , five }
  • those with 6 segments: { zero , six , nine }

To help us, lets look again at the valid configurations of segments for digits:

  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

You might notice that some of the digits fit within another. For example, One overlaps with all of Zero, Three, Four, Seven, Eight, and Nine.

We can formalise this by saying the set of segments for One is a subset of the segments for each of those other digits.

If we are trying to identify the encoded digits zero, three and nine however, we can't use one to identify them without some extra steps, as one is a subset of all of those encoded digits.

To help us, we can instead use the number of segments in each encoded digit: zero and nine both have 6 segments, but three has 5 segments. We can then conclude that out of the encoded digits with 5 segments, three can be discovered by finding the unique element where one is a subset.

Once we have discovered three, that leaves only { two , five } to discover out of those with 5 segments.

We can continue in this fashion to discover all the remaining encoded digits, formalised in this table below:

StepEncoded DigitRule
0onethe encoded digit with the same number of segments as One
0fourthe encoded digit with the same number of segments as Four
0seventhe encoded digit with the same number of segments as Seven
0eightthe encoded digit with the same number of segments as Eight
1threeunique encoded digit from { two , three , five } where one is a subset
2nineunique encoded digit from { zero , six , nine } where three is a subset
3zerounique encoded digit from { zero , six } where seven is a subset
3fiveunique encoded digit from { two , five } where (four \ one) is a subset
4tworemaining encoded digit from { two }
4sixremaining encoded digit from { six }
info

In the above table (four \ one) means the set difference, i.e. the set of segments formed from removing segments of one from segments of four.

Once we have discovered all the encoded digits, we build a dictionary by associating each encoded digit to the original digit.

Creating Our Subsitution Map​

We will implement our discovery rules with a few helpers.

The Encoded Digits​

First, we will refer to our list of 10 encoded digits by the value cipher, of type Seq[Segments].

Unique Encoded Digits Map​

We will build a map uniques from Digit to the encoded digits with unique segments size, reusing lookupUnique from part 1:

val uniques: Map[Digit, Segments] =
  Map.from(
    for
      segments <- cipher
      digit <- Digit.lookupUnique(segments)
    yield
      digit -> segments
  )

Above, we apply Map.from to a sequence of key value pairs (formed by a -> b). The values are formed by taking each encoded digit, passing it to lookupUnique, and if the encoded digit corresponds to a unique digit, then pair the valid digit with the encoded digit.

Lookup Encoded Digit by a Subset of Segments​

Next we need to be able to use a set of segments to select a unique encoded digit from a list, and return the remaining encoded digits.

We will do this by creating a function lookup which takes a list of encoded digits (section) and a discriminator segment set (withSegments). It produces a pair where the left element is the selected encoded digit, and the right element is the remaining encoded digits:

def lookup(section: Seq[Segments], withSegments: Segments): (Segments, Seq[Segments]) =
  val (Seq(uniqueMatch), remaining) = section.partition(withSegments.subsetOf)
  (uniqueMatch, remaining)

Above we call section.partition(withSegments.subsetOf) to create a pair of lists, the left is encoded digits of section that withSegments is a subset of, and the right are encoded digits where it is not. We expect to find only one unique match for withSegments, so we also assert that a singleton list is returned on the left.

5 and 6 Segment Sections​

We will create sections of encoded digits of size 5 and size 6:

val ofSizeFive = cipher.filter(encoded => encoded.sizeIs == 5)
val ofSizeSix = cipher.filter(encoded => encoded.sizeIs == 6)

Decoding the Encoded Digits​

We can now proceed to implement our rules and discover each encoded digit:

import Digit.*

val one = uniques(One)
val four = uniques(Four)
val seven = uniques(Seven)
val eight = uniques(Eight)
val (three, remainingFives) = lookup(ofSizeFive, withSegments = one)
val (nine, remainingSixes) = lookup(ofSizeSix, withSegments = three)
val (zero, Seq(six)) = lookup(remainingSixes, withSegments = seven)
val (five, Seq(two)) = lookup(remainingFives, withSegments = four &~ one)

In Scala &~ is the set difference operator. We also lookup (zero and six) and (five and two) in one step, as we know that six and two are the only possible elements of the remaining lists.

We also create new lists, (i.e. remainingFives and remainingSixes) instead of reusing the originals (ofSizeFive, ofSizeSix) because we cannot remove elements from lists after their creation.

Mapping from Encoded Digits to Digits​

We can now map from the encoded digits to the original digits by associating each encoded digit with the original:

val decode: Map[Segments, Digit] =
  Seq(zero, one, two, three, four, five, six, seven, eight, nine)
    .zip(Digit.index)
    .toMap

In the above, we create a map by first putting the encoded digits in order, we then zip with Digit.index, creating a list of key-value pairs of encoded digit to Digit. Finally we can call .toMap which creates a lookup table from the list of pairs.

Recall that Seq(1, 2, 3).zip(Seq('a', 'b', 'c')) results in Seq((1, 'a'), (2, 'b'), (3, 'c')). So we can use zip with Digit.index because it is an ordered sequence of Digit.

Putting it all Together​

We can then put all the parts for decoding the digits into one function substitutions (seen in the final code), with a single argument cipher (the list of 10 encoded digits) and returning the decode map.

Parsing the Input​

To parse the inputs this time, we will split each line by |, and then convert each half of the line to a sequence of segment strings by splitting each half on ' ':

def parseSegmentsSeq(segments: String): Seq[Segments] =
  segments.trim.split(" ").toSeq.map(Segment.parseSegments)

def splitParts(line: String): (Seq[Segments], Seq[Segments]) =
  val Array(cipher, plaintext) = line.split('|').map(parseSegmentsSeq)
  (cipher, plaintext)

Computing the Solution​

Decoding Each Display​

To decode each display, first we parse the input into our problems, i.e. a sequence of pairs where the left element is the 10 encoded digits cipher, and the right element is the display of 4 encoded digits plaintext.

Then for each problem, we can then create the substitution map by applying substitutions to cipher, then we can use the substitution map on each encoded digit of plaintext to convert it to a Digit.

We are then left with solutions, which is a list of decoded displays, where each display is a Seq[Digit].

val problems = input.linesIterator.map(splitParts)

val solutions = problems.map((cipher, plaintext) =>
  plaintext.map(substitutions(cipher))
)

Converting Seq[Digit] to Int​

The problem wants us to sum the total of all digit displays after decoding. Each display has 4 digits, so after decoding the digits we will have a sequence of 4 Digit.

To convert a sequence of Digit to an integer value, we can convert each digit to its corresponding integer representation by calling .ordinal, and then we can accumulate a sum by (from the left), multiplying the current total by 10 for each new digit, and then adding the current digit:

def digitsToInt(digits: Seq[Digit]): Int =
  digits.foldLeft(0)((acc, d) => acc * 10 + d.ordinal)

Final Result​

Finally, we use our digitsToInt function to convert each solution to an integer value, and sum the result:

solutions.map(digitsToInt).sum

Final Code​

The final code for part 2 can be appended to the code of part 1:

import Digit.*

def part2(input: String): Int =

  def parseSegmentsSeq(segments: String): Seq[Segments] =
    segments.trim.split(" ").toSeq.map(Segment.parseSegments)

  def splitParts(line: String): (Seq[Segments], Seq[Segments]) =
    val Array(cipher, plaintext) = line.split('|').map(parseSegmentsSeq)
    (cipher, plaintext)

  def digitsToInt(digits: Seq[Digit]): Int =
    digits.foldLeft(0)((acc, d) => acc * 10 + d.ordinal)

  val problems = input.linesIterator.map(splitParts)

  val solutions = problems.map((cipher, plaintext) =>
    plaintext.map(substitutions(cipher))
  )

  solutions.map(digitsToInt).sum

end part2

def substitutions(cipher: Seq[Segments]): Map[Segments, Digit] =

  def lookup(section: Seq[Segments], withSegments: Segments): (Segments, Seq[Segments]) =
    val (Seq(uniqueMatch), remaining) = section.partition(withSegments.subsetOf)
    (uniqueMatch, remaining)

  val uniques: Map[Digit, Segments] =
    Map.from(
      for
        segments <- cipher
        digit <- Digit.lookupUnique(segments)
      yield
        digit -> segments
    )

  val ofSizeFive = cipher.filter(_.sizeIs == 5)
  val ofSizeSix = cipher.filter(_.sizeIs == 6)

  val one = uniques(One)
  val four = uniques(Four)
  val seven = uniques(Seven)
  val eight = uniques(Eight)
  val (three, remainingFives) = lookup(ofSizeFive, withSegments = one)
  val (nine, remainingSixes) = lookup(ofSizeSix, withSegments = three)
  val (zero, Seq(six)) = lookup(remainingSixes, withSegments = seven)
  val (five, Seq(two)) = lookup(remainingFives, withSegments = four &~ one)

  val decode: Map[Segments, Digit] =
    Seq(zero, one, two, three, four, five, six, seven, eight, nine)
      .zip(Digit.index)
      .toMap

  decode
end substitutions

Run it locally​

You can get this solution locally by cloning the scalacenter/scala-advent-of-code repository.

$ git clone https://github.com/scalacenter/scala-advent-of-code
$ cd scala-advent-of-code

You can run it with scala-cli.

$ scala-cli 2021 -M day8.part1
The solution is 521

$ scala-cli 2021 -M day8.part2
The solution is 1016804

You can replace the content of the input/day8 file with your own input from adventofcode.com to get your own solution.

Solutions from the community​

Share your solution to the Scala community by editing this page.