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!
Code
You can get the code from my locally-hosed Git repo, or from Gitlab.