(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
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
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!