Hi everyone,
I’ve been looking forward to the Advent of Code 2021 for a long time now, especially as I’ve decided to write my solutions for this year’s coming month of challenges in Prolog!
Last year, I was having such a fun (and busy) time around Christmas that I forgot to finish the final two days of challenges. Day 24 asks you to write a sort of implementation of Conway’s Game of Life, but with a twist: the grid uses hexagons, as opposed to squares! The rules, of course, for the hex-based grid are a little different—and I don’t know if they’re the rules of the ‘official’ Hexlife, but they work very well and seem to propagate vastly from a few squares.
Any black tile with zero or more than 2 black tiles immediately adjacent to it is flipped to white. Any white tile with exactly 2 black tiles immediately adjacent to it is flipped to black.
Part 2 of the challenge isn’t visible until you complete Part 1, but it basically explains the rules which you’ve just read. The requirements of the challenge are simple:
How many hexes are set to "black" after reading the initial data, and how many will be set to black after 100 iterations of the rules stated above?
I had a lot of fun working through the problem in Prolog, but it’s been a long time since I really used the language and my code could use a little bit of constructive criticism (I banged this out quite quickly, in keeping with the spirit of the competition, so it’s definitely a little “raw” in implementation!)
To run the program:
$ swipl -s hexes.pro input.txt
Loading file input.txt
Total hexes set to black: 411
?- iterate(100).
Points to consider:
-
I use SWI Prolog’s wonderful DCG system to read the grid data. I’m not too fussed about this part, but maybe there are more elegant ways to do it!
-
I’ve used the “cube-based” coordinate style, which you can read about on this wonderful little page. It uses three coordinate dimensions in a redundant way. It has the nice property is that the coordinates always sum to 0.
-
I’ve used a dynamic predicate to store which hexes are set to “black”, e.g.
set_hex(0, 0, 0).. The program impurelyassertzs andretractalls theset_hexes to turn them on and off, but at each iteration the state of the program can be interrogated in a logically pure fashion. -
Perhaps there is a better way to do this—would SWI’s database system be more effective, for example?
-
I use a logical predicate,
adj, whose arguments unify to 1) any hex and 2) any adjoining hex set to “black”. Thanks to the predicate system, I never had to state the dimensions of the grid. By usingclpfd, I was able to let this spontaneously generate sets of all hexes adjacent to currently set hexes, in that wonderful Prolog-y way that feels at times kind of magical. I’m sure there’s a way to make this happen more efficiently, though. I couldn’t do it at all withoutclpfd. -
The program is correct but SLOW. What have I done wrong that makes it so slow?
-
One thing I get really bothered by in Prolog is that I can’t use arithmetic when passing arguments. Instead, I have to assign intermediate variables and pass their results. Look at my
hexespredicate for an example of what I’m talking about. I wonder if there’s a way to get around this? -
There’s no GUI, nor any way to display the hexes even on the command line. I’d like to implement this as a way to continue my Prolog training.
And so, further ado, here’s the Hexlife source code. Thanks in advance for any advice!
% Hexlife in SWI-Prolog
% Solution to Day 24 of the Advent of Code challenges, 2020
% Parts 1 and 2 are included
:- initialization(main).
:- use_module(library(clpfd)).
:- dynamic set_hex/3.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Part 1 %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
hexes([0, 0, 0]) --> [].
hexes([Q, R, S]) -->
hex([Qd, Rd, Sd]),
hexes([Q1, R1, S1]),
{Q is Q1+Qd, R is R1+Rd, S is S1+Sd}.
% Horizontal axis (R stays the same)
hex([-1, 0, 1]) --> "w".
hex([1, 0, -1]) --> "e".
% NW-to-SE axis (Q stays the same)
hex([0, -1, 1]) --> "nw".
hex([0, 1, -1]) --> "se".
% NE-to-SW axis (S stays the same)
hex([1, -1, 0]) --> "ne".
hex([-1, 1, 0]) --> "sw".
flip_hex(Q, R, S) :-
( set_hex(Q, R, S)
-> retract(set_hex(Q, R, S))
; assertz(set_hex(Q, R, S))
).
main :-
current_prolog_flag(argv, [Filename|_]),
format("Loading file ~s~n", Filename),
open(Filename, read, Stream),
parse_file(Stream),
aggregate_all(count, set_hex(_, _, _), Count),
format("Total hexes set to black: ~d~n~n", Count).
main :-
halt(1).
parse_file(Stream) :-
at_end_of_stream(Stream).
parse_file(Stream) :-
\+ at_end_of_stream(Stream),
read_line_to_codes(Stream, Line),
phrase(hexes([Q, R, S]), Line),
flip_hex(Q, R, S),
parse_file(Stream).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Part 2 (calculations) %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
adj(Q, R, S, [Q2, R2, S]) :- Q2 #= Q+1, R2 #= R-1, set_hex(Q2, R2, S).
adj(Q, R, S, [Q2, R2, S]) :- Q2 #= Q-1, R2 #= R+1, set_hex(Q2, R2, S).
adj(Q, R, S, [Q2, R, S2]) :- Q2 #= Q+1, S2 #= S-1, set_hex(Q2, R, S2).
adj(Q, R, S, [Q2, R, S2]) :- Q2 #= Q-1, S2 #= S+1, set_hex(Q2, R, S2).
adj(Q, R, S, [Q, R2, S2]) :- R2 #= R+1, S2 #= S-1, set_hex(Q, R2, S2).
adj(Q, R, S, [Q, R2, S2]) :- R2 #= R-1, S2 #= S+1, set_hex(Q, R2, S2).
count_adjacents(Q, R, S, Ct) :-
aggregate_all(count, adj(Q, R, S, _), Ct).
hex_to_black(Q, R, S) :-
set_hex(Q, R, S),
Ct in 1..2,
count_adjacents(Q, R, S, Ct).
hex_to_black(Q, R, S) :-
adj(Q, R, S, _),
\+ set_hex(Q, R, S),
count_adjacents(Q, R, S, 2).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Interactivity %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
iterate :-
setof([Q, R, S], hex_to_black(Q, R, S), NewHexes),
retractall(set_hex(_, _, _)),
forall(member([Q, R, S], NewHexes),
assertz(set_hex(Q, R, S))),
display_hex_count.
iterate(N) :-
format("Iterating ~d times:~N", N),
forall(between(1, N, _),
iterate).
display_hex_count :-
findall([Q, R, S], set_hex(Q, R, S), Results),
length(Results, Ct),
format("There are currently ~d black hexes~n", Ct).
