fub

The Advent of Code is a yearly recurring event in which puzzles are given which the players must solve with a computer program. It reminds me of the ACM Scholastic Programming Contest, but there is no ‘run environment’ and no judge. There is a leaderboard I think, but I’m not bothering with that — it’s a fun puzzle activity, not much more for me.

The first puzzle can be found on the AoC website, and I thought it would be fun to solve the problem in Prolog. Prolog remains my favourite for its expressiveness and the way it takes care of all kinds of mundane bookkeeping. In Prolog, you express what is true, and leave it to the machine to solve a question based on that — each Prolog program is like a zen koan. It is not the language to Get Shit Done, that’s mostly PHP, Java and C# these days. But you just can’t beat Prolog as an expression of beauty and truth.

So a little puzzle? That is very well suited for using Prolog! It’s been a (long) while since I programmed in Prolog, and I had to look up the exact syntax of a few of the built-in predicates, but I am pretty pleased with the result! Code under the cut.

Here’s my code (with the comments bolded for readability — my blog style is not really suited for sharing source code):

% This is our database with facts.

snack(elf1, 1000).

snack(elf1, 2000).

snack(elf1, 3000).

snack(elf2, 4000).

snack(elf3, 5000).

snack(elf3, 6000).

snack(elf4, 7000).

snack(elf4, 8000).

snack(elf4, 9000).

snack(elf5, 10000).

% An elf is in the expedition if it carries at least one snack.

elf_in_expedition(Elf) :- snack(Elf, _).

% The list of elves is the set of elves in the expedition.

elflist(ElfList) :- setof(Elf, elf_in_expedition(Elf), ElfList).

% sum_calories/2 takes a list as input and sums the numbers in the list and returns that as the second argument.

% Sum of an empty list is 0.

sum_calories([], 0).

% The sum of a list is the sum of the rest of the list plus the head of the list.

sum_calories([X|Rest], Result) :- sum_calories(Rest, RestResult), Result is X + RestResult.

% To find the total number of calories an elf is carrying, make a list of the calories of all the snacks the elf is carrying, and calculate the sum of that list.

total_calories(Elf, TotalCalories) :- findall(Calories, snack(Elf, Calories), CalorieList), sum_calories(CalorieList, TotalCalories).



% max_calories/2 returns the elf who is carrying the most calories and how much calories it is carrying. To do so, it first constructs the list of elves with snacks and calls max_calories/3.

max_calories(Elf, MaxCalories) :- elflist(ElfList), max_calories(Elf, MaxCalories, ElfList).

% If there are no elves in the list, then the total number of calories is 0 and there is ‘no elf’.

max_calories(no_elf, 0, []).

% The elf at the head of the list is the elf carrying the most calories if the total calories it is carrying is higher than the number of calories the elf with the highest number of calories in the rest of the list is carrying.

max_calories(Elf, ElfCalories, [Elf|RestElves]) :- total_calories(Elf, ElfCalories), max_calories(_, RestMaxCalories, RestElves), ElfCalories > RestMaxCalories.

% If the number of calories the elf at the head of the list is carrying, is lower (or equal) to the number of calories the elf with the highest number of calories in the rest of the list is carrying, then that elf is the elf with the highest number of calories in this list.

max_calories(RestMaxElf, RestMaxCalories, [Elf|RestElves]) :- total_calories(Elf, ElfCalories), max_calories(RestMaxElf, RestMaxCalories, RestElves), ElfCalories =< RestMaxCalories.

Running this with the fee GNU Prolog interpreter yields the result:

| ?- max_calories(Elf, MaxCalories).

Elf = elf4
MaxCalories = 24000

That was a fun thing to do in an evening. Will I do others? Probably not.