AoC2021 Day #12 Part #2

cave.lp

% undirected graph
edge(Y,X) :- edge(X,Y).

% hacky :(
% only needed to have dinstinct paths (otherwise there isn't any order leading to fewer models)
total(N*2) :- N=#count{X:edge(X,_)}.
% generate path for every edge
{ path(X,Y,Z) : Z=1..N } :- edge(X,Y), total(N).

visited("start",1).
visited(Y,N+1) :- visited(X,N), path(X,Y,N).

visited_twice(C) :- visited(C,M), visited(C,N), M!=N.
visited_thrice(C) :- visited(C,M), visited(C,N), visited(C,O), M!=N, N!=O, M!=O.

% no outgoing path from unvisited node
:- path(X,_,_), not path(_,X,_), X!="start".
% no incoming edge, if there is no outgoing
:- path(_,X,_), not path(X,_,_), X!="end".
:- path("start",X,N), path("start",Y,N), X!=Y.
:- path(X,"end",N), path(Y,"end",N), X!=Y.
% every path must have a start and an end
:- not path("start",_,1).
:- not path(_,"end",_).
% no outgoing edge from the end
:- path("end",_,_).
% no incoming edge towards start
:- path(_,"start",_).
% a small cave can be visited at most twice
:- small_cave(C), visited_thrice(C).
% only one cave may be visited twice
:- small_cave(A), small_cave(B), A!=B, visited_twice(A), visited_twice(B).

% can't have incoming from different nodes at the same time
:- path(A,B,N), path(X,Y,N), A!=X.
% can't have outgoing towards different nodes at the same time
:- path(A,B,N), path(X,Y,N), B!=Y.
% every path must have a direct predecessor
:- path(X,Y,N), N>1, not path(_,_,N-1).
% "end" must be the end
:- path(_,"end",M), path(_,X,N), N!="end", M<N.
% "start" must be the start
:- path("start",_,N), N>1.
% every startnode from a subsequent path must be the target node of a previous path
:- path(X,Y,N-1), path(Z,_,N), Z!=Y.

#show.