3 :- initialization
(main
).
4 :- dynamic neighbours
/2.
8 build_neighbours
(Rooms
).
12 open('08-rooms.txt', read, In
),
19 read_line_to_codes
(In
, H
),
28 string_codes
('abcdefghijklmnopqrstuvwxyz', A
).
30 adjacent
(Word
, Adjacents
):-
32 adjacent
(N
, Word
, Adjacents
).
34 adjacent
(N
, Word
, SAdjacents
):-
35 (N
= 0 -> Adjacents
= []
37 swap_char
(N
, Word
, NWords
),
39 adjacent
(N1
, Word
, RAdjacents
),
40 append
(NWords
, RAdjacents
, Adjacents
)),
41 list_to_ord_set
(Adjacents
, SAdjacents
).
43 swap_char
(N
, Word
, Swapped
):-
47 nth1
(N
, Word
, L
, Rest
),
52 build_neighbours
(Words
):-
53 build_neighbours
(Words
, Words
).
55 build_neighbours
([], _
).
56 build_neighbours
([Word
|Words
], Dictionary
):-
57 adjacent
(Word
, Adjacents
),
58 intersection
(Adjacents
, Dictionary
, Neighbours
),
59 string_codes
(SWord
, Word
),
60 maplist
(string_codes
, SNeighbours
, Neighbours
),
61 assertz
((neighbours
(SWord
, SNeighbours
):-!)), % Need the cut to keep lookup deterministic
in this dynamic predicate
62 build_neighbours
(Words
, Dictionary
).
67 extend
([W
|Chain
], Closed
, Extended
):-
69 ord_subtract
(Ns
, Closed
, Successors
),
70 extend_chain
(Successors
, [W
|Chain
], Extended
).
72 extend_chain
([], _
, []).
73 extend_chain
([N
|Ns
], Chain
, [[N
|Chain
]|Extended
]):-
74 extend_chain
(Ns
, Chain
, Extended
).
78 distance
([C
|Cs
], [O
|Os
], N
):-
80 -> distance
(Cs
, Os
, N
)
81 ; distance
(Cs
, Os
, N1
),
84 estimated_costed
([W
|C
], Goal
, N
-[W
|C
]):-
87 distance
(Cs
, Goal
, N2
),
90 estimated_costed_all
([], _
, []).
91 estimated_costed_all
([C
|Cs
], Goal
, [A
|As
]):-
92 estimated_costed
(C
, Goal
, A
),
93 estimated_costed_all
(Cs
, Goal
, As
).
96 astar
(Start
, SGoal
, Path
):-
97 string_codes
(SGoal
, Goal
),
98 estimated_costed
([Start
], Goal
, Costed
),
99 astar
([Costed
], SGoal
, Goal
, [], Path
).
102 astar
([_
-Current
|Agenda0
], SGoal
, Goal
, Closed0
, FoundPath
):-
103 %% write_ln
([N
-Current
, SGoal
, Goal
]),
106 -> FoundPath
= Current
107 ; [Word
|_
] = Current
,
108 ord_add_element
(Closed0
, Word
, Closed
),
109 extend
(Current
, Closed
, Extended
),
110 estimated_costed_all
(Extended
, Goal
, ExtraAgenda
),
111 append
(ExtraAgenda
, Agenda0
, Agenda1
),
112 keysort
(Agenda1
, Agenda
),
113 astar
(Agenda
, SGoal
, Goal
, Closed
, FoundPath
)
117 reachable
(Word
, Steps
, N
):-
118 reachable
(Steps
, [Word
], [Word
], Reachable
),
119 length(Reachable
, ReachableN
),
123 reachable
(N
, Found0
, Boundary0
, Reachable
):-
125 -> Reachable
= Found0
126 ; maplist
(neighbours
, Boundary0
, FoundL
),
127 flatten
(FoundL
, Found1
),
128 list_to_ord_set
(Found1
, Boundary1
),
129 ord_subtract
(Boundary1
, Found0
, Boundary
),
130 ord_union
(Found0
, Boundary
, Found
),
132 reachable
(N1
, Found
, Boundary
, Reachable
)
137 time(astar
("coax", "stay", P
)),
139 time(reachable
("coax", 10, Part2
)),
141 writef
('Part 1: %w steps from coax to stay\n', [Part1
]),
142 writef
('Part 2: %w rooms reacable in 10 steps from coax\n', [Part2
]).