Last year, just for (masochistic) fun, I decided to attempt the Advent Of Code with Prolog, more specifically with Skryer Prolog. The objective was simple: expanding my brain, and figuring out if we can make an advanced AI superagent/overlord/Skynet thing. I succeeded at the first objective, the second objective keeps resisting.

Anyway.

Most of the solutions weren't that good to be implemented in Prolog, in comparison with similar solutions in other programming languages. Until Day 25. Day 25 was written as if someone wanted to showcase Prolog.

As the expedition finally reaches the extraction point, several large hot air balloons drift down to meet you. Crews quickly start unloading the equipment the balloons brought: many hot air balloon kits, some fuel tanks, and a fuel heating machine.

The fuel heating machine is a new addition to the process. When this mountain was a volcano, the ambient temperature was more reasonable; now, it's so cold that the fuel won't work at all without being warmed up first.

The Elves, seemingly in an attempt to make the new machine feel welcome, have already attached a pair of googly eyes and started calling it "Bob".

To heat the fuel, Bob needs to know the total amount of fuel that will be processed ahead of time so it can correctly calibrate heat output and flow rate. This amount is simply the sum of the fuel requirements of all of the hot air balloons, and those fuel requirements are even listed clearly on the side of each hot air balloon's burner.

Ok, that's too many words for "sum all these numbers".

You make a list of all of the fuel requirements (your puzzle input), but you don't recognize the number format either. For example:

1=-0-2

12111

2=0=

Oooh, this is the tricky part.

"Okay, our Special Numeral-Analogue Fuel Units - SNAFU for short - are sort of like normal numbers. You know how starting on the right, normal numbers have a ones place, a tens place, a hundreds place, and so on, where the digit in each place tells you how many of that value you have?"

"SNAFU works the same way, except it uses powers of five instead of ten. Starting from the right, you have a ones place, a fives place, a twenty-fives place, a one-hundred-and-twenty-fives place, and so on. It's that easy!"

You ask why some of the digits look like - or = instead of "digits".

"You know, I never did ask the engineers why they did that. Instead of using digits four through zero, the digits are 2, 1, 0, minus (written -), and double-minus (written =). Minus is worth -1, and double-minus is worth -2."

"So, because ten (in normal numbers) is two fives and no ones, in SNAFU it is written 20. Since eight (in normal numbers) is two fives minus two ones, it is written 2=."

So we have something that looks like a 5-based numeric system, except it's not 1 to 5, but -2 to 2. I have no idea how to do arithmetic with this thing, and the good part is that I don't have to. Let me show it.

Parsing SNAFU

Prolog DCGs is (almost) the king of parsing. Let's write a parser for SNAFU:

% We need a couple libraries, one for pure IO, the other for DCGs
:- use_module(library(pio)).
:- use_module(library(dcgs)).

% Let's do the parsing. First, let's parse a digit individually.
snafu_digit(2) --> "2".
snafu_digit(1) --> "1".
snafu_digit(0) --> "0".
snafu_digit(-1) --> "-".
snafu_digit(-2) --> "=".

% Digits don't come individually. They come as a string: a list of digits.
% How do we parse it? Well, an empty SNAFU string is just an empty string.
snafu_digits([]) --> [].
% And a non-empty SNAFU string is a SNAFU digit, followed by more SNAFU digits.
snafu_digits([D|Ds]) --> snafu_digit(D), snafu_digits(Ds).

% Finally, the file they send us is made out of a bunch of SNAFU digits, one on each line.
% So we make it into a list of lists of SNAFU digits.
% At the end of the file we find a single newline.
snafu_file([]) --> "\n".
% And, before the end of the file, we should find a SNAFU string made of digits, a new line
% and then more file contents.
snafu_file([X|Xs]) --> snafu_digits(X), "\n", snafu_file(Xs).

So far so good. All this does is parse a file like:

1=-0-2
12111
2=0=

Into a list of lists, by translating each individual "digit":

[
  [1, -2, -1, 0, -1, 2],
  [1, 2, 1, 1, 1],
  [2, -2, 0, -2]
]

This is nothing special other than we have a nicer (weirder?) syntax for writing parsers.

SNAFU to integers

But we are supposed to convert this SNAFU things into integers so as to be able to sum them. Let's do it using CPLz. CPLz is a library for Constraint Logic Programming over Integers, I/E define variables and specify ranges and constraints on them, then ask the system to find out values that satisfy all constraints. This is obviously overkill for what we want to do here, but trust me, all this overkill will become about-right-kill in a few minutes.

% snafu_value: converts between SNAFU and integers
% If my SNAFU string is empty, that is the number 0.
snafu_value([], 0).
% If my SNAFU string is non-empty, we take the last digit, and add it
% to the result of everything-but-the-last-digit converted, and multiplied by 5.
snafu_value(Digits, Value) :-
  % Separate the last digit and the prefix
  append(Prefix, [Digit], Digits),
  % The result is this last digit + the value of the prefix
  Value #= Digit + 5 * PrefixValue,
  % Finally, we obtain the value of the prefix by recursive call
  snafu_value(Prefix, PrefixValue).

So far so good. We are doing the old "123 is 3 * 10^0 + 2 * 10^1 + 1 * 10^2", except instead of 10 we do 5, and we transform it so that it looks like "123 is 3 + 10 * (2 + 10 * (1))".

With this in place, it's not hard to parse the file, get the SNAFU digits, convert them, then add them. Easy peasy.

solution1(X) :-
  % Parse the file
  phrase_from_file(snafu_file(D), '25.input'),
  % Convert the list of lists into a list of numbers
  maplist(snafu_value, D, Values),
  % Sum the list of numbers
  sum_list(Values, Total),
  ??? What now ???
  .

We haven't done anything groundbreaking, we haven't shown any of that magical AI stuff. All we have done so far is basic maths with fancy syntax. And we haven't done the hard part yet.

But you are supposed to give back the sum in SNAFU format!

That's the tricky part. I have no idea how to do it, but here is where Prolog AI Skynet magic stuff will do it.

We have been very careful to use "reversible" predicates so far, and that's going to do the trick. Let's try using snafu_value backwards. We say the end value, and ask for the SNAFU digits that would generate it:

?- snafu_value(X, 1234).
  X = [1234]

Ooh, silly goose! Yes, 1234 is 1234 * 5^0, but 1234 is not a valid digit in SNAFU land! Let's do some tweaking:

% snafu_value: converts between SNAFU and integers
% If my SNAFU string is empty, that is the number 0.
snafu_value([], 0).
% If my SNAFU string is non-empty, we take the last digit, and add it
% to the result of everything-but-the-last-digit converted, and multiplied by 5.
snafu_value(Digits, Value) :-
  % Separate the last digit and the prefix
  append(Prefix, [Digit], Digits),
  % But a digit must be between -2 and 2 (inclusive), you silly goose!
  Digit #>= -2,
  Digit #=< 2,
  % The result is this last digit + the value of the prefix
  Value #= Digit + 5 * PrefixValue,
  % Finally, we obtain the value of the prefix by recursive call
  snafu_value(Prefix, PrefixValue).

Let's try again:

?- snafu_value(X, 1234).
   X = [2,0,-1,2,-1]

That's so much nicer. CPLz is doing its thing. We set the value, and CPLz figures out the SNAFU digits for that value. I don't know how it works, but it works.

We are just one step before having our solution. Let's translate the final step: SNAFU digits into equals and minus and that stuff. I'm going to also use snafu_digits in reverse, because it's a DCG, and DCGs can be used in reverse. Set the expected value, ask for what string gets converted into that expected value.

?- snafu_value(X, 1234), phrase(snafu_digits(X), Result).
   X = [2,0,-1,2,-1], Result = "20-2-"

1234 is two-zero-dash-two-dash. That looks good. Let's plug it into the solution:

solution1(X) :-
  % Parse the file
  phrase_from_file(snafu_file(D), '25.input'),
  % Convert the list of lists into a list of numbers
  maplist(snafu_value, D, Values),
  % Sum the list of numbers
  sum_list(Values, Total),
  % Make the total back to SNAFU digits
  snafu_value(X1, Total),
  % Convert the SNAFU digits to a SNAFU string with equals and dashes
  phrase(snafu_digits(X1), X).

And this works, and earns me a star in the Advent of Code 2022.

Do you know why people were so hyped on AI in the 80s?

The Prolog solution to this riddle fits in half of a screen of code. And most of it is boring parser code. And took my Prolog-amateur brain less than an hour. And I still don't know how to do base-5-but-with-minus-two or whatever is the technical name for SNAFU. But I don't have. Prolog thinks for me. Prolog smart, me dumb.

Now you know why people were so hyped on AI in the 80s.