In this article I revisit the problem Seven Segment Search of Day 8 in the Advent of Code 2021 puzzle series. I implement a declarative solution in Clojure using the logic programming library core.logic.
Puzzle
The problem of Day 8 was about decoding the digits of a broken sevensegment display. We can measure the signals on the wires powering the display’s segments, but we don’t know which wire is connected to which segment. The puzzle input is a sequence of activation signals of the display as it renders the digits from 0 to 9 in some random order:
"be" "cfbegad" "cbdgef" "fgaecd" "cgeb" "fdcge" "agebfd"
"fecdb" "fabcd" "edb"
The goal of the puzzle is to decode these signal patterns to understand which digit the display renders.
For example, the first signal pattern "be"
must be the digit 1
because this
is the only digit that is rendered using two segments. But we don’t know which
segment the signals b
and e
are connected. By looking at the digit 1
there are two possibilities:
.... ....
. b . e
. b . e
.... ....
. e . b
. e . b
.... ....
In fact, the digits 1
, 4
, 7
and 8
each use a unique number of segments:
2, 4, 3 and 7, respectively, so these are easy to identify. To find the other
digits we need to collect more information.
For example, the digits 2
, 3
and 5
are each contain five active segments.
From this group we can find the digit 3
by exploiting that the rendering of
the digit 3
doesn’t change with the digit 1
superimposed. In other words,
the activation signals of the digit 3
and 1
only differ in one segment.
Imperative solution
Exploiting the similarities between the digit representations you can come up with your own algorithm to unambiguously identify all digits. My implementation in Clojure looks like this:
(defn decode [patterns]
(let [length (groupby count patterns)
; Unambiguous digits
[one] (get length 2)
[four] (get length 4)
[seven] (get length 3)
[eight] (get length 7)
; Candiates for 2,3,5 and 0,6,9
c235 (get length 5)
c069 (get length 6)
; Find the rest using similar digits
three (findwithmask one c235)
nine (findwithmask three c069)
zero (findwithmask seven (remove #{nine} c069))
five (findwithmask nine nine (remove #{three} c235))
[six] (remove #{zero nine} c069)
[two] (remove #{three five} c235)]
{zero 0 one 1 two 2 three 3 four 4
five 5 six 6 seven 7 eight 8 nine 9}))
The function decode
takes the signal patterns as input and returns a map from
signal pattern to digit value. The function findwithmask
implements the
insight about the similarity of the digits. You can read the entire code of my
solution here.
Clojure may not be your language of choice, but in any other mainstream
language the solution would be similar in spirit: a few function calls, set and
sequence operations. Each operation is trivial but the decode
function is
hard to understand even for a person familiar with the problem statement. This
implementation is imperative, each line prescribing what to do and the order of
operations is critical.
In the next section I show a declarative solution where we only state the problem and let the computer figure out how to solve it.
Declarative solution
In this section we reimplement the decode
function using the logic
programming library core.logic. A logic program is an expression
of constraints upon a set of logic variables. We hand this expression to a
solver, in our case core.logic, which returns all the possible values of the
logic variables that satisfy the constraints. The core.logic
Primer explains in detail how the solver works.
Let’s see the declarative version of the pattern decoder in Clojure core.logic:
(defn decodelogic [patterns]
(let [length (groupby count patterns)]
(first (run 1 [q] ; ❶
(fresh [zero one two three four five six seven eight nine]
; ❷
(== q {zero 0 one 1 two 2 three 3 four 4
five 5 six 6 seven 7 eight 8 nine 9})
; ❸
(== [one] (length 2))
(== [four] (length 4))
(== [seven] (length 3))
(== [eight] (length 7))
; ❹
(permuteo (length 5) [two three five])
(permuteo (length 6) [zero six nine])
; ❺
(overlay one three three)
(overlay one nine nine)
(overlay one zero zero)
(overlay one five nine)
; ❻
(permuteo patterns [zero one two three four
five six seven eight nine]))))))
After a standard function definition and a letbinding the body of
decodelogic
is a set of constraints derived from our original problem statement:

Run the solver and ask for exactly solution. Our problem has a unique solution, but in other applications you may be interested in many solutions that satisfy the constraints.
q
, the second argument of run, refers to the final solution. 
Search the solution
q
in the shape of a map from pattern to digit value. This is the same structure we used in the previous section. 
Identify the “easy” digits, those with unambiguous number of active segments.

The 5 and 6 character long signal patterns are the permutations of the sequences
[2, 3, 5]
and[0, 6, 9]
, respectively. 
Overlay rules: for example the digit 1 and 3 yields 3 when on top of each other.

The sequence of activation patterns is a permutation of the digits.
decodelogic
encodes only the rules of the puzzle without any details of the
program’s execution. In fact, you can rearrange the constraints arbitrarily,
the logic expression evaluates to the same result.
The order of the constraints, however, affects the solver’s performance: I found that stating more specific constraints first makes the solver explore the possible states faster.
The beauty of the declarative solution comes with a price, at least in my
implementation: decodelogic
takes approximately six seconds to run where
decode
completes within a millisecond. This was my first logic program I’ve
ever written in Clojure core.logic so I guess this is fine.
The source code of the implementation is available here.
Summary
I implemented an Advent of Code puzzle as a logic expression in Clojure. A logic program is about the what instead of the how: stating the problem is easier, but reasoning about the program’s performance is harder than compared to an imperative implementation.
You can read about my experience of the 2021 Advent of Code here and this repository contains all my solutions.