## DEV Community is a community of 782,260 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Neil Gall

Posted on

# Advent of Code 2021 Day 4

It's a rainy Saturday and a nice logic puzzle so I went for Prolog. I'm specifically using Scryer Prolog for its nice DCG library which makes parsing the input text a breeze.

The bit in part 2 that caught me out was that multiple boards can win at the same time, so capturing all the scores and dropping the winning boards took a bit of work.

``````:- use_module(library(charsio)).
:- use_module(library(dcgs)).
:- use_module(library(lists)).
:- use_module(library(pio)).
:- use_module(library(reif)).

%% parsing

digit(D) --> [D], { char_type(D, decimal_digit) }.

digits([D|Ds]) --> digit(D), digits(Ds), !.
digits([D])    --> digit(D).

number(N) --> digits(Ds), { number_chars(N, Ds) }.

draw([N|Ns]) --> number(N), ",", draw(Ns), !.
draw([N])    --> number(N).

board([R|Rs]) --> row(R), "\n", board(Rs), !.
board([R])    --> row(R).

row([N|Ns]) --> whitespace, number(N), row(Ns), !.
row([N])    --> whitespace, number(N).

whitespace --> "  ", !; " ", !; "", !.

boards([B|Bs]) --> board(B), "\n\n", boards(Bs), !.
boards([B])    --> board(B).

input(Draw, Boards) --> draw(Draw), "\n\n", boards(Boards), "\n".

load(File, Draw, Boards) :-
phrase_from_file(input(Draw, Boards), File).

%% model

match_row(_, [], []).
match_row(N, [N|Xs], [x|Xs]) :- !.
match_row(N, [X|Xs], [X|Ys]) :- match_row(N, Xs, Ys).

match_board(_, [], []).
match_board(N, [X|Xs], [Y|Ys]) :-
match_row(N, X, Y), match_board(N, Xs, Ys), !.

match_boards(_, [], []).
match_boards(N, [X|Xs], [Y|Ys]) :-
match_board(N, X, Y), match_boards(N, Xs, Ys), !.

winning_row([x]).
winning_row([x|Xs]) :- winning_row(Xs), !.

winning_board_([R])    :- winning_row(R).
winning_board_([R|Rs]) :- winning_row(R); winning_board_(Rs), !.

winning_board(B, true) :-
winning_board_(B);
transpose(B, B2), winning_board_(B2).

winning_board(_, false).

score_row([], 0).
score_row([x|Xs], S) :- score_row(Xs, S), !.
score_row([X|Xs], S) :- score_row(Xs, S2), S is X + S2.

score_board([R], S) :- score_row(R, S), !.
score_board([R|Rs], S) :-
score_row(R, S1),
score_board(Rs, S2),
S is S1 + S2.

%% game

win_score(Draw, Win, Score) :-
score_board(Win, S),
Score is Draw * S.

wins(Draw, Boards, BoardsLeft, Scores) :-
tfilter(winning_board, Boards, Wins),
maplist(win_score(Draw), Wins, Scores),
foldl(select, Wins, Boards, BoardsLeft).

game([D|Ds], Boards, Scores) :-
match_boards(D, Boards, NextBoards),
wins(D, NextBoards, BoardsLeft, WinScores),
game(Ds, BoardsLeft, MoreScores),
append(WinScores, MoreScores, Scores).

game([], _, []).

%% problems

part1(Draw, Boards, Score) :-
game(Draw, Boards, [Score|_]), !.

part2(Draw, Boards, LastScore) :-
game(Draw, Boards, Scores),
reverse(Scores, [LastScore|_]), !.

%% tests

test_part1 :-
part1(Draw, Boards, Score),
Score is 4512.

test_part2 :-
part2(Draw, Boards, Score),
Score is 1924.

main :-
test_part1,
test_part2,