This is a part of my ongoing challenge of solving every Advent of Code puzzle in a different language.

The challenge we're tackling today is available here.

Secure Container

This time we’re given some conditions for what a valid password looks like, and then given the task of finding how many possible correct passwords are there. The rules are:

1. It has to be in a certain range
2. It has to have at least two same adjacent digits
3. It can never decrease through its digits: every next digit has to be equal or larger than the previous.

The Language

As soon as I understood that the challenge was going to be about rules and sets of things that comply with those rules, I knew which language to choose. Prolog! To be more specific, I’m using the SWI-prolog implementation of the prolog language.

Prolog is a logic programming language, which is one of the less popular programming paradigms in the industry. It’s similar to functional programming, as you don’t declare how to compute values but rather what those values should look like, and the language takes care of the rest. While it might not be very popular as a general-purpose language, it has specific domains in which it shines. This task, I feel, is one of them.

The Solution: Part 1

Let’s take a look at the code and then dissect it thoroughly.

count_valid_passwords(Low, High, Count) :-
  findall(Password, valid_password(Low, High, Password), PossiblePasswords),
  sort(PossiblePasswords, Results),
  length(Results, Count).
  
valid_password(Low, High, Value) :-
  between(Low, High, Value),
  number_codes(Value, Digits),
  has_two_adjacent_symbols(Digits),
  symbols_never_decrease(Digits).

has_two_adjacent_symbols([H, H | _]).
has_two_adjacent_symbols([_ | T]) :-
  has_two_adjacent_symbols(T).

symbols_never_decrease([]).
symbols_never_decrease([_]).
symbols_never_decrease([H, N | T]) :-
  N >= H,
  symbols_never_decrease([N | T]).

Prolog is made out of rules and facts, upon which you can run a query. Essentially, when writing software in prolog, you explain what sort of rules apply to the world, then you ask it about something, and based on the rules, prolog figures out the answer. Let’s take a look at some of these rules now.

symbols_never_decrease([]).
symbols_never_decrease([_]).
symbols_never_decrease([H, N | T]) :-
  N >= H,
  symbols_never_decrease([N | T]).

The symbols_never_decrease rule declares that for a list, every next symbol will be equal to or greater than the previous. Let’s see how it works.

You can see that we define the rule three times. Two out of those three, we’re defining facts. The first fact is that symbols do not decrease for an empty list. The second fact is that symbols do not decrease for a list with just one element in it. Notice that the choice of symbol inside the bracket is arbitrary, but an _ is used by convention if the variable will not be used. In prolog, variables start with capital letters, except for being able to also use the underscore.

Next, we have an actual rule. This rule pattern matches further on the list given, takes its first two elements (H and N) and the rest of the list (T for “tail”). We see a new symbol here: :- denotes a rule. The first clause in the rule is that N >= H, or that the second element we destructured earlier is equal to or larger than the first element. The , after the clause denotes an AND, or that the next clause in sequence also has to evaluate to true. This next clause is just asserting that the list, starting from the current second element N, also never decreases. Notice that we constructed a new list by putting the N together with T again. Essentially, we’re proving that the list’s symbols never decrease using mathematical induction.

That’s it for the symbols_never_decrease rule. Given a list, it will check if its elements never decrease.

has_two_adjacent_symbols is even more elegant. In its first fact, we again destructure the first two elements of the list, this time discarding the tail (by assigning it to underscore). Notice, however, that we use the same symbol for both elements. This means that for the rule to match (or “unify”, as prolog calls it), the first two symbols in the list have to be the same symbol.

Now the second line builds a rule which just asserts that discarding the first element of the list, the rest still has two adjacent symbols in it somewhere. Again we’re essentially using mathematical induction here. When this rule is given a list to check, it will only match on the first fact if the first two symbols are the same (and thus, there are two adjacent symbols), otherwise, it’ll try again with the rest of the list. If we don’t match with a rule by the time of running out of the list, it will say that this rule didn’t match, which means we didn’t have two adjacent characters.

valid_password is a bit more interesting. We have three variables here that we don’t pattern match on. First, we assert that the Value given must be between High and Low. Then, we do something interesting. We assert that for a given Value, its digits (in ASCII encoding) are stored in Digits. We haven’t provided prolog a value for Digits, though. This means that since it has enough information, it’ll find out what the value of Digits is by itself. This is what makes prolog powerful. We describe rules and what information we have, then ask for info, it figures out all the rest. We’ll use this power again later. Next, we check our own rules to see that the value complies.

We can use valid_password to check that a password is valid for a given range. However, using the power of prolog, we can do much more. If we give a range but don’t provide a password, it’ll just give us a valid password for that range.

We exploit this in the first function, count_valid_passwords, where we use this mechanic to find all valid passwords for the given range. Then we use the fact that sort removes duplicates and we find the length of the results using the mechanic illustrated before. Then we can query count_valid_passwords, and by not providing info in Count, it fills Count for us. Magical.

The Solution: Part 2

In this part, we had to only change the rule of adjacency. This time, instead of looking for at least two equal adjacent digits, we have to look for exactly two equal adjacent digits.

I’ll be honest – I got lazy here. Let’s take a look.

count_valid_passwords(Low, High, Count) :-
  findall(Password, valid_password(Low, High, Password), PossiblePasswords),
  sort(PossiblePasswords, Results),
  length(Results, Count).
  
valid_password(Low, High, Value) :-
  between(Low, High, Value),
  number_codes(Value, Digits),
  has_exactly_two_adjacent_symbols(Digits),
  symbols_never_decrease(Digits).

has_exactly_two_adjacent_symbols([A, A, C, _, _, _]) :-
  dif(A, C).
has_exactly_two_adjacent_symbols([A, B, B, D, _, _]) :-
  dif(A, B),
  dif(B, D).
has_exactly_two_adjacent_symbols([_, B, C, C, E, _]) :-
  dif(B, C),
  dif(C, E).
has_exactly_two_adjacent_symbols([_, _, C, D, D, F]) :-
  dif(C, D),
  dif(D, F).
has_exactly_two_adjacent_symbols([_, _, _, D, E, E]) :-
  dif(D, E).

symbols_never_decrease([]).
symbols_never_decrease([_]).
symbols_never_decrease([H, N | T]) :-
  N >= H,
  symbols_never_decrease([N | T]).

I’m exploiting the rule that the password is six digits long in this solution. I’m manually matching on every legal case of exactly two adjacency, and checking that the adjacent elements to those are different (using dif) to the two adjacent elements.

Retro

I had a lot of fun here, and hope that this has illustrated, if even a little bit, the unique power of prolog. I took a course on logic programming when I was an undergrad, and at first, had a strong dislike for it. The final task in that class was to build an AI for checkers using prolog, where different students’ AIs would be pitted against each other. Halfway through the task, prolog finally clicked for me, and I realized the class was worth it. I was describing what checkers looks like, and prolog took care of solving it for me. If you give prolog a shot, I hope you find that moment it clicks.

If you want to look at the code in full, I’m putting all of the Advent of Code solutions on GitHub.