I'm trying to learn Prolog by solving Advent Of Code puzzles, and have ended up being stuck on a task that I think should be pretty simple. The puzzle in question is this one. The task requires me to find all program IDs (integers) that are connected to program ID 0. Connections are symmetric and transitive, so if there exists a connection between programs from different connected groups, all programs in the given groups are connected to each other.
My current situation is that I've sorted the integers in the puzzle into sublists that each represent the group that they belong to.
For example: [[0, 2], [1, 1], [2, 0, 3, 4], [3, 2, 4], [4, 2, 3, 6], [5, 6], [6, 4, 5]]
I need to get all the programs that are somehow connected to 0. In this example, that would be all programs except the program with ID 1.
So, the logic that I'm looking for is something that manages to check if a given integer exists in both the expanding group that contains 0 and the group that my recursive predicate connected is currently looking at. I realise that this method might end up ignoring new connections to groups that were looked at earlier in the recursion, but that is a separate problem.
Sorting the programs into the sublists like above is not a problem, so I'm omitting that part from what I have so far.
main(R) :-
Groups = [[0, 2], [1, 1], [2, 0, 3, 4], [3, 2, 4], [4, 2, 3, 6], [5, 6], [6, 4, 5]],
connected(Groups, [0], R).
connected([H|T], X, R) :-
member(Y, H), member(Y, X) -> flatten([H|X], X1), connected(T, X1, R) ; R = X.
The result I'm getting here is simply: [0,2,0]
The result that I expect is: [0,2,0,2,0,3,4,3,2,4,4,2,3,6,5,6,6,4,5]
I've realised that the element [1,1] may stop the recursion too early, so I've tried changing the last line above to the following:
member(Y, H), member(Y, X) -> flatten([H|X], X1), connected(T, X1, R) ; connected(T, X, R).
However, that simply causes main(R). to evaluate to false for some reason. Likewise, it returns false if I simply remove [1,1] from the groups without changing the last line.
I assume that I'm overlooking something quite simple, and would appreciate any input.
Assuming your Groups have the proper structure, you may keep a list of "unvisited" groups, and at each recursive step take an unvisited item and add its still-unvisited neighours.
i.e.:
main(R) :-
Groups = [[0, 2], [1, 1], [2, 0, 3, 4], [3, 2, 4], [4, 2, 3, 6], [5, 6], [6, 4, 5]],
connected([0], [], Groups, R).
connected([], _, _, []).
connected([P|Tail], Visited, Groups, [P|R]):-
select([P|Ps], Groups, NGroups), % Get the item's neighours
subtract(Ps, [P|Visited], NPs), % subtract from it the visited ones
union(Tail, NPs, NTail), % and add these neighours to the unvisited list
connected(NTail, [P|Visited], NGroups, R).
This will get the set of "connected" programs without duplicates:
?- main(R).
R = [0, 2, 3, 4, 6, 5]