I recently came across a simple but interesting puzzle called “I Love Computers” and decided to find a declarative solution using Prolog.

Puzzle

The puzzle’s input is a sequence of integer-string pairs, one per line. Take the following as the example input; it contains a secret message. The solver must output the three words “I love computers.”

3 love
6 computers
2 dogs
4 cats
1 I
5 you

See these as a pyramid where \(1\) goes to the apex of the pyramid at the top; \(2\) and \(3\) make up the second row; \(4..6\) become the third row and so on. The secret derives from the last word found on each row.

The solver begins by parsing the given file as pairs of whitespace-delimited numbers and strings, one per line. Finding the hidden message begins by sorting the pairs by their ‘priority number’ in ascending order. It then strips off the sort keys, leaving only the strings in “pyramid” order. The solver then uses an accumulator function to span each row according to the expanding length of each row and chooses the last element within the row as the decoded result.

Solver

Many different solutions exist, of course. My declaratively-based version of the solver uses three predicates:

one predicate to parse numbers and strings;
one predicate to construct a pyramid;
and a final predicate to find the solution by using the previous two predicates and some glue logic.

Text Input to Number-String Pairs

The grammar in logic for each line of the input file finds a number followed by whitespaces and then a string up to the end of the line of text. In Definite-Clause Grammar terms, each line unifies as follows. Note that string_without//2 finds a list of Unicode character codes so requires a codes-to-string conversion.

pair(Number-String) -->
    number(Number), blanks, string_without("\n", Codes), "\n",
    { string_codes(String, Codes)
    }.

Hence,

once(phrase_from_file(sequence(pair, Pairs0), File, [])).

will unify with a list of \(Number\)-\(String\) pairs at \(Pairs_0\). Sorting and mapping will find the \(String\) terms in their order, i.e.

once(phrase_from_file(sequence(pair, Pairs0), File, [])),
sort(Pairs0, Pairs),
maplist(arg(2), Pairs, Strings).

will unify the \(String\) terms from the input file in their ascending priority order.

Spanning the Pyramid

Straightforward thus far. Next, address the pyramid. Each pyramid row has a length starting at \(1\) and grows by \(1\) until none are left. A tail-recursive accumulator can find the last strings in all such rows as follows.

lasts([], _, []) :- !.
lasts(Pairs, N, [Last|T]) :-
    length(Row, N),
    append(Row, Pairs_, Pairs),
    last(Row, Last),
    succ(N, N1),
    lasts(Pairs_, N1, T).

The first clause length(Row, N) first declares that a \(Row\) exists of length \(N\). It does not know what the elements of the row are initially. They could be anything at all. It then declares that the unknown \(Row\) belongs to the beginning of the given \(Pairs\) followed by some remaining unknown pairs at \(Pairs'\)—using underscore for ‘prime’. The \(Last\) element of each \(Row\) belongs at the head of the new list of ‘last’ elements. The succ/2 clause finds the length of the next row before tail-recursion on the remaining pairs.

Failure is one important feature of this logical declaration. It will fail entirely if the input does not correctly form a pyramid. It requires no unnecessary counting or checking as when imperatively programming. The recursive declarations logically imply the necessary pyramid consistency checking. The predicate expresses the “rule” for a pyramid.

All Together

Combining the pieces gives the following.

i_love_computers(File) :-
    once(phrase_from_file(sequence(pair, Pairs0), File, [])),
    sort(Pairs0, Pairs),
    maplist(arg(2), Pairs, Strings),
    lasts(Strings, 1, Lasts),
    atomics_to_string(Lasts, ' ', Answer),
    writeln(Answer).

Asking i_love_computers('i_love_computers.txt') correctly writes:

i love computers

Conclusion

The declarative approach makes the solution simple. It differs from imperative solutions. The solution only declares what is true and the solution falls out. Nice.