aoc2023/day19.pl

85 lines
2.5 KiB
Perl
Raw Permalink Normal View History

:- use_module(library(dcg/basics)).
:- use_module(library(dcg/high_order)).
file(W, I) --> sequence(workflow, W), blanks, sequence(item, I).
workflow(w(L,I)) --> name(L), "{", sequence(instruction, ",", I), "}", blanks.
name(N) --> sequence(alpha_to_lower, Cs), {Cs \= [], atom_codes(N, Cs)}.
instruction(accept) --> "A", !.
instruction(reject) --> "R", !.
instruction(goto(X)) --> name(X).
instruction(if(A, R, N, T)) -->
attr(A), relation(R), number(N), ":", instruction(T).
% e.g. if(x, >, 420, goto(label)) or if(x, >, 420, accept)
attr(A) --> oneof([x,m,a,s], A).
relation(R) --> oneof([<,>], R).
oneof(Xs, X) --> {member(X, Xs)}, atom(X).
item(i(X, M, A, S)) -->
"{", field(x, X), ",", field(m, M), ",", field(a, A), ",", field(s, S), "}",
blanks.
field(L, X) --> atom(L), "=", number(X).
field(i(X,_,_,_), x, X).
field(i(_,M,_,_), m, M).
field(i(_,_,A,_), a, A).
field(i(_,_,_,S), s, S).
goto([w(L, W)|_], L, W) :- !.
goto([_ |Ws], L, W) :- goto(Ws, L, W).
run(_, [accept|_], _, accept) :- !.
run(_, [reject|_], _, reject) :- !.
run(Ws, [goto(L)|_], I, Res) :-
goto(Ws, L, W),
run(Ws, W, I, Res).
run(Ws, [if(F, R, N, T)|W], I, Res) :-
field(I, F, Val),
compare(R0, Val, N),
(R = R0 -> run(Ws, [T|W], I, Res) ; run(Ws, W, I, Res)).
score(_, reject, 0).
score(i(X,M,A,S), accept, T) :- T is X + M + A + S.
total(Is, Rs, T) :- maplist(score, Is, Rs, Ts), foldl(plus, Ts, 0, T).
part1(File) :-
once(phrase_from_file(file(Ws, Is), File)),
maplist(run(Ws, [goto(in)]), Is, Rs),
total(Is, Rs, T),
writeln(T), !.
:- use_module(library(clpfd)).
run2(Ws, [goto(L)|_], I) :- goto(Ws, L, W), run2(Ws, W, I).
run2(Ws, [if(F, R, N, T)|_], I) :- yes(F, R, N, I), run2(Ws, [T], I).
run2(Ws, [if(F, R, N, _)|W], I) :- no(F, R, N, I), run2(Ws, W, I).
run2(_, [accept|_], i(X,M,A,S)) :-
X in 1..4000, M in 1..4000, A in 1..4000, S in 1..4000.
yes(F, R, N, I) :- field(I, F, Val), constrain(yes, R, Val, N).
no(F, R, N, I) :- field(I, F, Val), constrain(no, R, Val, N).
constrain(yes, <, X, Y) :- X #< Y.
constrain(yes, >, X, Y) :- X #> Y.
constrain(no, <, X, Y) :- X #>= Y.
constrain(no, >, X, Y) :- X #=< Y.
comb_size(i(X,M,A,S), Size) :-
fd_size(X, XN), fd_size(M, MN), fd_size(A, AN), fd_size(S, SN),
Size is XN * MN * AN * SN.
part2(File) :-
once(phrase_from_file(file(Ws, _), File)),
findall(I, run2(Ws, [goto(in)], I), Is),
maplist(comb_size, Is, Ns),
foldl(plus, Ns, 0, N),
writeln(N).
% vim: set ft=prolog :