Question on Path Constraint

[David Silverman]

I am trying to solve Advent of Code 2017 day 12. Part 1 asks for all vertices connected by a path to vertex 0. I realize that I could write this as a recursive search, but I am trying to understand global constraints and wondered if I could use path. 

Here's the example graph, which is "test.txt".

0 <-> 2
1 <-> 1
2 <-> 0, 3, 4
3 <-> 2, 4
4 <-> 2, 3, 6
5 <-> 6
6 <-> 4, 5
7 <-> 8
8 <-> 7

In the example, 0 has a path to [2,3,4,5,6].

Here's my code:

import util.
import cp.

main =>
    Data = read_file_lines("test.txt").map(split).map(parse),
    N = Data.len,
    println(n=N),
    B = new_array(N),
    B :: 0..1,
    Vs = [{Data[I,1],B[I]} : I in 1..N],
    Es = [{V,V2,_} : D in Data, V = D[1], V2 in D[2]],
    writeln(vs=Vs),
    writeln(es=Es),
    go(Vs,Es,B,N).


go(Vs,Es,B,N) =>
    Dest :: 1..N,
    Vlist = [V[1] : V in Vs],
    member(Dest,Vlist), % without this, error ground_expected for path
    path(Vs,Es,0,Dest),
    % path(Vs,Es,0,5), % hardcoded gives the correct answer vlistOK = [0,2,3,4,5,6]
    Cliq #= sum([1 : V in Vs,V[2] #= 1]), 
    solve([$max(Cliq)],[B,Es,Vs]), % this isn't maximizing Cliq
    println(vs=Vs),
    println(es=Es),
    VlistOK = [V[1] : V in Vs, V[2] = 1],
    println([vlistOK=VlistOK,vlistlen=VlistOK.len]),
    println(cliq=Cliq).

parse([V,_|Es]) = [V.to_int,Es.map(parse_es)].
parse_es(S) = S2.to_int => S2 = delete(S,',').

Here's the output:

n = 9
vs = [{0,_03628},{1,_035d8},{2,_03588},{3,_03538},{4,_034e8},{5,_03498},{6,_03448},{7,_033f8},{8,_033a8}]
es = [{0,2,_3818},{1,1,_3848},{2,0,_3878},{2,3,_38a8},{2,4,_38d8},{3,2,_3908},{3,4,_3938},{4,2,_3968},{4,3,_3998},{4,6,_39c8},{5,6,_39f8},{6,4,_3a28},{6,5,_3a58},{7,8,_3a88},{8,7,_3ab8}]
vs = [{0,1},{1,0},{2,1},{3,0},{4,0},{5,0},{6,0},{7,0},{8,0}]
es = [{0,2,1},{1,1,0},{2,0,1},{2,3,0},{2,4,0},{3,2,0},{3,4,0},{4,2,0},{4,3,0},{4,6,0},{5,6,0},{6,4,0},{6,5,0},{7,8,0},{8,7,0}]
[vlistOK = [0,2],vlistlen = 2]
cliq = 2

If I hardcode the answer with path(Vs,Es,0,5), I get this output:

vs = [{0,1},{1,0},{2,1},{3,1},{4,1},{5,1},{6,1},{7,0},{8,0}]
es = [{0,2,1},{1,1,0},{2,0,1},{2,3,1},{2,4,0},{3,2,1},{3,4,1},{4,2,0},{4,3,1},{4,6,1},{5,6,1},{6,4,1},{6,5,1},{7,8,0},{8,7,0}]
[vlistOK = [0,2,3,4,5,6],vlistlen = 6]
cliq = 6

What am I doing wrong or misunderstanding?

[Neng-Fa Zhou]

I don't think the path constraint is a good pick for this problem. A typical graph traversal algorithm will do for this problem. Here is my program that uses this algorithm:

https://github.com/nfzhou/aoc/blob/main/aoc_17_12_part1.pi

If you'd like to try constraints, then scc could be used. Here is my version using scc for the same problem:

https://github.com/nfzhou/aoc/blob/main/aoc_17_12_part1_sat.pi

This one takes 3.8s while the graph traversal algorithm only takes 0.01s.

Cheers,

NF

[David Silverman]

This is incredibly helpful! I see how you added the required vertex of 0 into the Vs list. I had thought scc would be the right constraint, but misunderstood that it would require every vertex to be connected to every other vertex directly. I also found your use of append for parsing very illuminating. Wonderful stuff!

I also ended up using a recursive traversal myself, but it wasn't as neatly coded as yours. The base case with true was also very instructive. So much information in such a small piece of code. Thank you.