hunting.lp

% solution for https://puzzlehunt.club.cc.cmu.edu/puzzle/15011/

#script (python)
from clingo import Function
from collections import defaultdict
import operator
from colored import bg, attr

MAP = """
..B#.~....
.~~.~..#..
#..~~~..~.
.~~....~..
~~.@~..~.#
.~~~~~..~.
...~~.~...
...~~~.~B.
.~.B.B.~..
~~..~...~~
..B#......
""".strip().split("\n")

def symbol(c):
    for i in range(11):
        for j in range(10):
            if MAP[i][j] == c.string:
                yield Function('n', [i, j])

def parse_n(n):
    return (n.arguments[0].number, n.arguments[1].number)

def nsub(a, b):
    return tuple(map(operator.sub, a, b))

DIRS = {
  'e': (0, 1),
  'w': (0, -1),
  's': (1, 0),
  'n': (-1, 0)
}

RENDER = {
  'nesw': "┼",
  'ne': "└",
  'ns': "│",
  'nw': "┘",
  'es': "┌",
  'ew': "─",
  'sw': "┐",
}

COLORS = {
  '~': 'cyan',
  '@': 'yellow',
  '#': 'green',
  'B': 'black',
}

def main(ctl):
    ctl.ground([("base", [])])
    with ctl.solve(yield_=True) as h:
        for m in h:
            print()
            paths = defaultdict(set)
            terms = m.symbols(atoms=True)
            for t in sorted(terms):
                # print(t)
                if t.name == 'path':
                    n1, n, n2 = map(parse_n, t.arguments)
                    paths[n].add(nsub(n1, n))
                    paths[n].add(nsub(n2, n))
            for i in range(11):
                for j in range(10):
                    s = paths.get((i, j))
                    if s is not None:
                        dacc = ""
                        for d in "nesw":
                            if DIRS[d] in s:
                                dacc += d
                        render = RENDER.get(dacc, '?')
                    else:
                        render = ' '
                    color = COLORS.get(MAP[i][j])
                    if color is not None:
                        print(bg(color), end='')
                    print(render, end='')
                    if MAP[i][j] in '~@#B':
                        print(attr(0), end='')
                print()
#end.

row(0..10).
col(0..9).
node(n(I, J)) :- row(I), col(J).

ice(N)      :- N = @symbol("~").
tree(N)     :- N = @symbol("#").
buffalo(N)  :- N = @symbol("B").
start(N)    :- N = @symbol("@").

obstacle(N) :- tree(N).
obstacle(N) :- buffalo(N).

delta(0,1).
delta(1,0).

% Directed graph.  Actually the direction here doesn't
% really matter, we just don't want to double-count edges.
edge(e(N1, N2)) :-
    node(N1), node(N2),
    N1 = n(I1, J1),
    N2 = n(I2, J2),
    delta(I2-I1, J2-J1).

% test cases
:- not edge(e(n(0,0),n(1,0))).
:- not edge(e(n(0,0),n(0,1))).

% manually input logs
log(e(n(3,3), n(4,3))).
log(e(n(7,2), n(8,2))).
log(e(n(9,5), n(9,6))).

% make sure you did directedness correctly on log input
:- log(E), not edge(E).

% Traditionally, you think of a path as going from node to node.
% But it's possible to cross over a node twice, which means
% that just knowing what node you are on isn't enough to tell
% you where you are on a path (you could have come from the left,
% or from above.)  So we're going to consider patches in chunks
% of three nodes: where you came from, where you are, and where
% you are going.

% short for line graph edge. N1 < N2 to symmetry break.
ledge(N1, N, N2) :-
    N1 < N2,
    edge(e(N1, N; N, N1)),
    edge(e(N2, N; N, N2)).

% postulate that each edge may participate in the path, DIRECTIONALLY
{ path(N1, N, N2) : node(N2), ledge(N1, N, N2; N2, N, N1) } <= 1 :- node(N1), node(N).

% some basic coherence conditions on paths
:- path(N1, N, N2), path(N3, N, N1).  % cannot enter and exit through same side
:- path(N1, N, N2), path(N1, N, N3), N2 != N3.  % cannot split path
:- path(N1, N, N3), path(N2, N, N3), N1 != N2.  % cannot join path

% path must be connected
:- path(N1, N, N2), { path(N, N2, N3) } = 0.
:- path(N1, N, N2), { path(N3, N1, N) } = 0.

% walk along the path starting from start, recording all locations we reached
reached(n(I, J), n(I, J+1)) :- start(n(I, J)).
reached(N, N2) :- path(N1, N, N2), reached(N1, N).
reached(N) :- reached(N, N2).  % simplify

% must reach every non-obstacle node
:- node(N), not obstacle(N), not reached(N).

% must skip obstacles
:- node(N), obstacle(N), reached(N).

% if on ice, must keep going the direction you came from
:- ice(N), path(n(I1, J1), N, n(I2, J2)), I1 != I2, J1 != J2.

% crossing logs not allowed
:- log(e(N1, N2)), node(N3), path(N1, N2, N3; N2, N1, N3).

% crossings must be on ice
:- not ice(N), path(N1, N, N2), path(N3, N, N4), N3 != N1, N4 != N2.

#show.