AoC2021 Day #12 Part #1

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+1) :- 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).

% 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",_).
% no doubly visiting small caves
:- small_cave(C), visited(C,M), visited(C,N), M!=N.

% 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.