Advent of code (Discussion)

[rausm]

Thanks for the reminder (I usually remember there was AoC during the first quartal of the following year ).

Yesterday I solved firts three days, and I hope i did better work then Alicia (no offense intended, but I don’t find them readable; very low-level, verbose approach, interation manually woven into the predicates, I’d have hard time trying to understand what the code does).

Of course, I’m no Prolog guru (and tastes may vary), so anyone interested, please, send comments / improvements, and help me make them the best possible examples of elegant Prolog code.

Enjoy.

EDIT: Perhaps including the repo link isn’t such a bad idea, lol:

rausm/adventofcode_2019_prolog

[EricGT]

For those like me wondering what is Advent of Code (about)

Advent of Code is an Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like. People use them as a speed contest, interview prep, company training, university coursework, practice problems, or to challenge each other.

You don’t need a computer science background to participate - just a little programming knowledge and some problem solving skills will get you pretty far. Nor do you need a fancy computer; every problem has a solution that completes in at most 15 seconds on ten-year-old hardware.

[Boris]

Good work.

I recently realized that reading files/streams in Prolog has gotten suprisingly easy using a combination of three things:

• phrase_from_file/2;
• library(dcg/basics);
• sequence//3 and sequence//5 from library(dcg/high_order).

The easy things become a proper one-liner, the difficult things are easy. Even for the easiest input, if you use read_string/3 and split_string/5, you have, at least, something like:

setup_call_cleanup(open(Filename, r, In),
    read_string(In, _, Str),
    close(In)),
split_string(Str, ",", "\n", Elements),
maplist(number_string, Ns, Elements)

Of course you can put this is a predicate and so on, but still, it is code you need to write. This is now for a single line of integers separated by commas (note I didn’t want to paste the file content into my Prolog code!).

Here it is with the combination of three things:

phrase_from_file(sequence("", integer, ",", "\n", Ns), Filename)

You can of course define your own DCGs to use in place of integer//1 that I used in this example.

[rausm]

Thanks for the tips, I’m already familiar with DCGs (and phrase_from_file, setup_call_cleanup, …) and was waiting for something that warranted their use to “introduce” them.

split_string(Str, ",", "\n", Elements)

isn’t useful here, since the line separator is pretty important (each line is different “wire”). But of course, with DCGs it’s simple to state something like “newline-separated parts, that are comma-separated lists; ?perhaps followed by optional newline(s)?”

In the meantime, multi-line string literals & string-splitting are “quick & dirty” shortcuts (that work wonders for simpler cases: you need it fast, you won’t run it that often - or perhaps only once, bang & done

Funny story about “the power of string-splitting”: On programming reddit, C++ wanna-be’s are comparing their code for some previous AoC task . One states, that his code takes a minute to run, the second one pulls out his “regex compiled at compile-time, which parses the [pretty small] text-file in 13 seconds”.

I literally burst out laughing, because my python code, using simple string splitting, was done in less then 0.2 seconds (lines, split by spaces, pick parts at fixed offsets, some simple computation, done). The best optimization for them would be (besides better regexes) to at least split the file into lines and then use their “woderful” regex (that wasn’t very specific, and had to do a lot of backtracking) to parse that.

EDIT: and your split_string call needs a little tweak (also split on new-line, otherwise the \n would glue two parts together and wouldn’t get stripped:

?- split_string("1,2,3\n4,5,6", ",", "\n", Elements).
Elements = ["1", "2", "3\n4", "5", "6"].

?- split_string("1,2,3\n4,5,6", ",\n", "\n", Elements).
Elements = ["1", "2", "3", "4", "5", "6"].

[Boris]

OK, I was thinking something like this. (It is a very small module but it is then easier for you to test maybe).

:- module(wire, [wire//1]).
:- use_module(library(dcg/basics)).
:- use_module(library(dcg/high_order)).

wire(W) -->
    sequence("", segment, ",", "\n", W).

segment(v(D, Steps)) -->
    direction(D),
    integer(Steps).

direction(up) --> "U".
direction(down) --> "D".
direction(left) --> "L".
direction(right) --> "R".

and then you can use it like this:

?- use_module(wire).
true.

?- setup_call_cleanup(open('d03-example.input', read, In), read_string(In, _, Str), close(In)).
In = <stream>(0x55e859d5ac90),
Str = "R98,U47,R26,D63,R33,U87,L62,D20,R33,U53,R51\nU98,R91,D20,R16,D67,R40,U7,R15,U6,R7\n".

?- phrase_from_file(( wire(W1), wire(W2) ), 'd03-example.input').
W1 = [v(right, 98), v(up, 47), v(right, 26), v(down, 63), v(right, 33), v(up, 87), v(left, 62), v(down, 20), v(right, 33), v(up, 53), v(right, 51)],
W2 = [v(up, 98), v(right, 91), v(down, 20), v(right, 16), v(down, 67), v(right, 40), v(up, 7), v(right, 15), v(up, 6), v(right, 7)].

But of course it is all matter of taste at the end.

[anniepoo]

totally OT, but HI Boris - forgot you’re more or less on my time zone now!
Maybe I’ll make a trip that direction and we can meet up without being completely dead tired some time!

[rausm]

Wut ? DCGs are conciser even in such a trivial case ? I used them only for more complicated things such as simplified JSON parser (Advent 2015 ) or for parsing the more complex inputs (and they were super-sweet), but I never realized how well they will work even for the simpler cases (especially since one can nicely tie “type-conversions” or whatever into them - if appropriate)

Ok, “eff” string splitting (at least in Prolog ;-), I’m gonna try considering them first.

And I’m gona re-write at least day 3, with phrase for the time being. I already have AoC 2015 (and a few days from other years) in prolog, with a “read input - feed it into the solver for specified day, time the solving, check results, display it all” harness, but I wanna upgrade it into XPCE browser / launcher, so for now I’ll probably leave the input hardcoded.

[anniepoo]

I’ve only used the regex libs once in SWI-Prolog. I use DCGs for simple stuff instead - DCGs are just clearer.

The one time I used regexes was to validate a form field, so it was app dev configurable and the JS on client and Prolog on server agreed what was valid.