Advent of Code 2021 day 8

    Unlike day 6, the day 8 puzzle was one where brute force beat cleverness. Rather than trying to be clever, the problem was small enough that brute force could handle it in a small enough time.

    (I'm ignoring part 1. It was a test of reading and parsing the input, counting strings with the required lengths.)

    If there are seven segments in the display and seven letters that could be assigned to them, there are 7! = 5040 different ways they could be allocated. With 2000 rows in the input, that's only 10 million allocations to try, which isn't a great deal.

    The key data structure is an Encoding, a Map from letters to the Segments they encode. Given an encoding and a list of encoded digits (the first part of each input line), I judge the encoding as valid if all the encoded digits represent actual seven-segment digits.

    Note that this isn't true in general: it could be that there is more than one valid encoding, for instance if there are only some digits given, or the seven-segment display uses additional characters such that the set has some kind of symmetry (for instance, if we only have the digits 0, 2, 5, and 8, we can't distinguish between 180⁰ rotations of the display).

    Some data types to represent things. digitSegments shows the segments used in each digit.

    data Display = Display [String] [String] -- patterns, output
      deriving (Eq, Show)
    data Segment = Seg1 | Seg2 | Seg3 | Seg4 | Seg5 | Seg6 | Seg7  
      deriving (Eq, Ord, Show, Enum, Bounded)
    type Encoding = M.Map Char Segment
    type DigitSegments = M.Map (S.Set Segment) Char
    -- some constants
    segmentNames :: [Char]
    segmentNames = "abcdefg"
    segments :: [Segment]
    segments = [Seg1 .. Seg7]
    digitSegments :: DigitSegments
    digitSegments = M.fromList
      [ (S.fromList [Seg1, Seg2, Seg3, Seg5, Seg6, Seg7], '0')
      , (S.fromList [Seg3, Seg6], '1')
      , (S.fromList [Seg1, Seg3, Seg4, Seg5, Seg7], '2')
      , (S.fromList [Seg1, Seg3, Seg4, Seg6, Seg7], '3')
      , (S.fromList [Seg2, Seg3, Seg4, Seg6], '4')
      , (S.fromList [Seg1, Seg2, Seg4, Seg6, Seg7], '5')
      , (S.fromList [Seg1, Seg2, Seg4, Seg5, Seg6, Seg7], '6')
      , (S.fromList [Seg1, Seg3, Seg6], '7')
      , (S.fromList [Seg1, Seg2, Seg3, Seg4, Seg5, Seg6, Seg7], '8')
      , (S.fromList [Seg1, Seg2, Seg3, Seg4, Seg6, Seg7], '9')

    allocate creates a valid encoding by making all possible encodings (by finding all permutations of segments, then creating an encoding that maps the names to that order of segments), then filtering out the invalid ones.

    allocate :: Display -> Encoding
    allocate (Display examples _) = head $ validEncodings
      where allEncodings = map (\segs -> M.fromList $ zip segmentNames segs) 
                                $ permutations segments
            validEncodings = filter (isValidEncoding examples) allEncodings

    An encoding is valid if every example given, when it gets converted to segments, gives a known digit.

    isValidEncoding :: [[Char]] -> Encoding -> Bool
    isValidEncoding examples encoding = 
      all (\e -> M.member e digitSegments) exampleSegments
      where exampleSegments = map (segmentsOfSignal encoding) examples
    segmentsOfSignal :: Encoding -> [Char] -> S.Set Segment
    segmentsOfSignal encoding signal = S.fromList $ map (encoding ! ) signal

    Once I have an encoding, finding the displayed number is a case of looking up the encoded digits (as Chars) then reading them into the code.

    decodeOneDisplay :: Display -> Int
    decodeOneDisplay display = findCode allocation display
      where allocation = allocate display
    findDigit :: Encoding -> [Char] -> Char
    findDigit encoding code = digitSegments ! (segmentsOfSignal encoding code)
    findDigits :: Encoding -> [[Char]] -> [Char]
    findDigits encoding codes = map (findDigit encoding) codes
    findCode :: Encoding -> Display -> Int
    findCode encoding (Display _ codes) = read $ findDigits encoding codes

    This runs much slower than the longwinded version that deduces the encoding directly, but it's much easier to code up!


    You can get the code from my locally-hosed Git repo, or from Gitlab.

    Neil Smith

    Read more posts by this author.