"Hexlife" in SWI Prolog — critique very much welcome!

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 impurely assertzs and retractalls the set_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 using clpfd, 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 without clpfd.

  • 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 hexes predicate 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).
2 Likes

Two things I might try if this were my problem.

  1. concurrent_forall/3 (ref)
  2. arg/3 - For a practical and simple usage of arg/3 see dynamic array (code) (ref)
1 Like

Awesome!

… Here we go, down the rabbit hole of multithreaded Prolog :laughing:

Reply to self:

I’ve cut the time to run iterate(50) from roughly 4.7s to 1.9s — by creating two seperate predicates in place of adj, depending on mode.

I worked through a Mercury tutorial today which really helped me to understand these concepts, and how to streamline execution with them. Whew! That was a lot of fun. More to come…

EDIT: Tabling takes it to 0.63s consistently. I tried concurrency but it was faster with it off! profile/1 is a godsend.

2 Likes

Why not use the built in profile/1 predicate to isolate the bottlenecks?

Why not use the built in profile/1 predicate to isolate the bottlenecks?

Thanks for the tip! I’ve done that.

I thought it would be a lot to learn, but to my surprise it turned out to be one of the easiest, most helpful profiling tools I’ve used in any language. SWI-Prolog manages to exceed my expectations every time!

Thanks to this, I’ve reduced iterate(50) from 25 million inferences to 2.5 million inferences.

I’d still like to get some stylistic advice, or pointers to any libraries that could be helpful. The concurrency predicates, which EricGT recommended, were a revelation!

The way I currenlty learn the most about coding with SWI-Prolog is by text searching many downloaded trusted repositories from GitHub (ref) with NotePad++ and then look at the code. If the code is in the ball park of what I need I look at it in more detail. If I don’t understand something I use the individual predicates in examples until the predicate is my friend. Sometimes this takes a few hours and sometimes it takes months. dif/2 is one I am currently trying to make a friend.

Often this leads to other code or ways of doing things and my code just keeps getting better. The most interesting fact of all of this is that my code no longer looks anything like what I learned in my university class many decades ago, it looks a lot more like the code for SWI-Prolog.

Current list (Click triangle to expand)
bench-master
contrib-protobufs-master
docker-swipl-linux-ci-master
packages-bdb-master
packages-chr-master
packages-clib-master
packages-cppproxy-master
packages-http-master
packages-inclpr-master
packages-jpl-master
packages-ltx2htm-master
packages-odbc-master
packages-pcre-master
packages-pengines-master
packages-pldoc-master
packages-RDF-master
packages-real-master
packages-semweb-master
packages-sgml-master
packages-ssl-master
packages-utf8proc-master
packages-xpce-master
packages-yaml-master
packages-zlib-master
pengines-master
plweb-blog-master
plweb-examples-master
plweb-master
plweb-www-master
rclswi-master
sCASP-swipl
swipl-devel-master
swipl-master
swipl-server-js-client-master
swish-master
webstat-master

EDIT

Sometimes there is not enough hits in the current set of repositories. In such cases searching GitHub directly against all repositories, then selecting just those with Prolog code generates new sources of information. This was done recently for http_reply_from_files/3 as there were not enough simple examples from the list above.

1 Like