/* Connected components in Picat. This is from my Advent of Code 2024 day 12 program (part 1): http://hakank.org/advent-of-code-2024/12_part1.pi The examples below are for matrices, i.e. with [I,J] coordinates, but any nodes would do. This program was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import util. main => go. go ?=> data(D,Adj,Rows,Cols), println(d=D), Nodes = Adj.keys.sort, T = new_array(Rows,Cols), CC = connected_components(Nodes,Adj), Id = 1, foreach(C in CC) println(component=C), foreach([A,B] in C) T[A,B] := Id end, Id := Id + 1 end, foreach(I in 1..Rows) foreach(J in 1..Cols) printf("%3w",T[I,J]) end, nl end, nl, fail, nl. go => true. % All neigbours neibs(M,Rows,Cols,I,J) = [M[I+A,J+B] : A in -1..1, B in -1..1, abs(A+B) == 1, % just left/right/up/down I+A >= 1, I+A <= Rows, J+B >= 1, J+B <= Cols]. % All neighours with the same character as M[I,J] neibs2(M,Rows,Cols,I,J,C) = [[I+A,J+B] : A in -1..1, B in -1..1, abs(A+B) == 1, % just left/right/up/down I+A >= 1, I+A <= Rows, J+B >= 1, J+B <= Cols, M[I+A,J+B] == C]. % % Connected components % Ported from % https://www.geeksforgeeks.org/connected-components-in-an-undirected-graph/ dfs(Adj,Temp0,V, Visited,Temp) => Temp1 = copy_term(Temp0), Visited.put(V,true), Temp1 := Temp1 ++ [V], foreach([A,B] in Adj.get(V)) if not Visited.has_key([A,B]) then dfs(Adj,Temp1,[A,B],Visited,Temp2), Temp1 := Temp2 end end, Temp=Temp1. connected_components(Nodes,Adj) = CC => Visited = new_map(), CC = [], foreach([A,B] in Nodes) if not Visited.has_key([A,B]) then Temp = [], dfs(Adj,Temp, [A,B], Visited,Temp2), CC := CC ++ [Temp2] end end. % AoC 2024, day 12, part 1, example 1 data(1,Adj,Rows,Cols) :- Rows = 4, Cols = 4, Adj = new_map([ [1,1]=[[1,2],[1,1]], [1,2]=[[1,1],[1,3],[1,2]], [1,3]=[[1,2],[1,4],[1,3]], [1,4]=[[1,3],[1,4]], [2,1]=[[2,2],[3,1],[2,1]], [2,2]=[[2,1],[3,2],[2,2]], [3,1]=[[2,1],[3,2],[3,1]], [3,2]=[[2,2],[3,1],[3,2]], [2,3]=[[3,3],[2,3]], [3,3]=[[2,3],[3,4],[3,3]], [3,4]=[[3,3],[4,4],[3,4]], [4,4]=[[3,4],[4,4]], [2,4]=[[2,4]], [4,1]=[[4,2],[4,1]], [4,2]=[[4,1],[4,3],[4,2]], [4,3]=[[4,2],[4,3]] ]). % AoC 2024, day 12, part 1, example 2 data(2,Adj,Rows,Cols) :- Rows = 5, Cols = 5, Adj = new_map([ [1,1]=[[1,2],[2,1],[1,1]], [1,2]=[[1,1],[1,3],[1,2]], [1,3]=[[1,2],[1,4],[2,3],[1,3]], [1,4]=[[1,3],[1,5],[1,4]], [1,5]=[[1,4],[2,5],[1,5]], [2,1]=[[1,1],[3,1],[2,1]], [2,3]=[[1,3],[3,3],[2,3]], [2,5]=[[1,5],[3,5],[2,5]], [3,1]=[[2,1],[3,2],[4,1],[3,1]], [3,2]=[[3,1],[3,3],[3,2]], [3,3]=[[2,3],[3,2],[3,4],[4,3],[3,3]], [3,4]=[[3,3],[3,5],[3,4]], [3,5]=[[2,5],[3,4],[4,5],[3,5]], [4,1]=[[3,1],[5,1],[4,1]], [4,3]=[[3,3],[5,3],[4,3]], [4,5]=[[3,5],[5,5],[4,5]], [5,1]=[[4,1],[5,2],[5,1]], [5,2]=[[5,1],[5,3],[5,2]], [5,3]=[[4,3],[5,2],[5,4],[5,3]], [5,4]=[[5,3],[5,5],[5,4]], [5,5]=[[4,5],[5,4],[5,5]], [2,2]=[[2,2]], [2,4]=[[2,4]], [4,2]=[[4,2]], [4,4]=[[4,4]] ]). % AoC 2024, day 12, part 1, example 2 data(3,Adj,Rows,Cols) :- Rows = 10, Cols = 10, Adj = new_map([ [1,7]=[[1,8],[2,7],[1,7]], [1,8]=[[1,7],[2,8],[1,8]], [2,7]=[[1,7],[2,8],[3,7],[2,7]], [2,8]=[[1,8],[2,7],[2,9],[2,8]], [2,9]=[[2,8],[2,9]], [3,6]=[[3,7],[4,6],[3,6]], [3,7]=[[2,7],[3,6],[3,7]], [4,4]=[[4,5],[4,4]], [4,5]=[[4,4],[4,6],[5,5],[4,5]], [4,6]=[[3,6],[4,5],[4,6]], [5,5]=[[4,5],[6,5],[5,5]], [5,8]=[[5,8]], [6,5]=[[5,5],[6,6],[6,5]], [6,6]=[[6,5],[7,6],[6,6]], [7,6]=[[6,6],[7,6]], [5,10]=[[6,10],[5,10]], [6,9]=[[6,10],[7,9],[6,9]], [6,10]=[[5,10],[6,9],[7,10],[6,10]], [7,9]=[[6,9],[7,10],[8,9],[7,9]], [7,10]=[[6,10],[7,9],[8,10],[7,10]], [8,9]=[[7,9],[8,10],[9,9],[8,9]], [8,10]=[[7,10],[8,9],[9,10],[8,10]], [9,8]=[[9,9],[10,8],[9,8]], [9,9]=[[8,9],[9,8],[9,10],[10,9],[9,9]], [9,10]=[[8,10],[9,9],[10,10],[9,10]], [10,8]=[[9,8],[10,9],[10,8]], [10,9]=[[9,9],[10,8],[10,10],[10,9]], [10,10]=[[9,10],[10,9],[10,10]], [1,9]=[[1,10],[1,9]], [1,10]=[[1,9],[2,10],[1,10]], [2,10]=[[1,10],[3,10],[2,10]], [3,8]=[[3,9],[4,8],[3,8]], [3,9]=[[3,8],[3,10],[4,9],[3,9]], [3,10]=[[2,10],[3,9],[4,10],[3,10]], [4,8]=[[3,8],[4,9],[4,8]], [4,9]=[[3,9],[4,8],[4,10],[5,9],[4,9]], [4,10]=[[3,10],[4,9],[4,10]], [5,9]=[[4,9],[5,9]], [1,5]=[[1,6],[2,5],[1,5]], [1,6]=[[1,5],[2,6],[1,6]], [2,5]=[[1,5],[2,6],[2,5]], [2,6]=[[1,6],[2,5],[2,6]], [6,3]=[[7,3],[6,3]], [7,3]=[[6,3],[7,4],[8,3],[7,3]], [7,4]=[[7,3],[7,5],[8,4],[7,4]], [7,5]=[[7,4],[8,5],[7,5]], [8,2]=[[8,3],[9,2],[8,2]], [8,3]=[[7,3],[8,2],[8,4],[9,3],[8,3]], [8,4]=[[7,4],[8,3],[8,5],[9,4],[8,4]], [8,5]=[[7,5],[8,4],[8,6],[8,5]], [8,6]=[[8,5],[9,6],[8,6]], [9,2]=[[8,2],[9,3],[9,2]], [9,3]=[[8,3],[9,2],[9,4],[9,3]], [9,4]=[[8,4],[9,3],[10,4],[9,4]], [9,6]=[[8,6],[9,6]], [10,4]=[[9,4],[10,4]], [4,7]=[[5,7],[4,7]], [5,6]=[[5,7],[5,6]], [5,7]=[[4,7],[5,6],[6,7],[5,7]], [6,7]=[[5,7],[6,8],[7,7],[6,7]], [6,8]=[[6,7],[7,8],[6,8]], [7,7]=[[6,7],[7,8],[8,7],[7,7]], [7,8]=[[6,8],[7,7],[8,8],[7,8]], [8,7]=[[7,7],[8,8],[9,7],[8,7]], [8,8]=[[7,8],[8,7],[8,8]], [9,7]=[[8,7],[10,7],[9,7]], [10,7]=[[9,7],[10,7]], [8,1]=[[9,1],[8,1]], [9,1]=[[8,1],[10,1],[9,1]], [10,1]=[[9,1],[10,2],[10,1]], [10,2]=[[10,1],[10,3],[10,2]], [10,3]=[[10,2],[10,3]], [1,1]=[[1,2],[2,1],[1,1]], [1,2]=[[1,1],[1,3],[2,2],[1,2]], [1,3]=[[1,2],[1,4],[2,3],[1,3]], [1,4]=[[1,3],[2,4],[1,4]], [2,1]=[[1,1],[2,2],[2,1]], [2,2]=[[1,2],[2,1],[2,3],[2,2]], [2,3]=[[1,3],[2,2],[2,4],[3,3],[2,3]], [2,4]=[[1,4],[2,3],[3,4],[2,4]], [3,3]=[[2,3],[3,4],[4,3],[3,3]], [3,4]=[[2,4],[3,3],[3,5],[3,4]], [3,5]=[[3,4],[3,5]], [4,3]=[[3,3],[4,3]], [9,5]=[[10,5],[9,5]], [10,5]=[[9,5],[10,6],[10,5]], [10,6]=[[10,5],[10,6]], [3,1]=[[3,2],[4,1],[3,1]], [3,2]=[[3,1],[4,2],[3,2]], [4,1]=[[3,1],[4,2],[5,1],[4,1]], [4,2]=[[3,2],[4,1],[5,2],[4,2]], [5,1]=[[4,1],[5,2],[6,1],[5,1]], [5,2]=[[4,2],[5,1],[5,3],[6,2],[5,2]], [5,3]=[[5,2],[5,4],[5,3]], [5,4]=[[5,3],[6,4],[5,4]], [6,1]=[[5,1],[6,2],[7,1],[6,1]], [6,2]=[[5,2],[6,1],[7,2],[6,2]], [6,4]=[[5,4],[6,4]], [7,1]=[[6,1],[7,2],[7,1]], [7,2]=[[6,2],[7,1],[7,2]] ]).