diff options
| author | Elizabeth Alexander Hunt <me@liz.coffee> | 2026-07-02 11:55:17 -0700 |
|---|---|---|
| committer | Elizabeth Alexander Hunt <me@liz.coffee> | 2026-07-02 11:55:17 -0700 |
| commit | 6bf4b90c90f15f4ab60833bddf5b5756d1a6b1f6 (patch) | |
| tree | ed97e39ec77c5231ffd2c394493e68d00ddac5a4 /Homework/cs4700/prolog/castle.pl | |
| download | misc-undergrad-main.tar.gz misc-undergrad-main.zip | |
Diffstat (limited to 'Homework/cs4700/prolog/castle.pl')
| -rw-r--r-- | Homework/cs4700/prolog/castle.pl | 97 |
1 files changed, 97 insertions, 0 deletions
diff --git a/Homework/cs4700/prolog/castle.pl b/Homework/cs4700/prolog/castle.pl new file mode 100644 index 0000000..2fa5608 --- /dev/null +++ b/Homework/cs4700/prolog/castle.pl @@ -0,0 +1,97 @@ +% First castle for testing
+% The castle is a set of room facts of the form
+% room(Castle, FromRoom, ToRoom, cost).
+room(dunstanburgh, enter, foyer, 1).
+room(dunstanburgh, foyer, livingRoom, 1).
+room(dunstanburgh, foyer, hall, 2).
+room(dunstanburgh, hall, kitchen, 4).
+room(dunstanburgh, hall, garage, 3).
+room(dunstanburgh, kitchen, exit, 1).
+
+% Second castle for testing
+room(windsor, enter, foyer, 1).
+room(windsor, foyer, hall, 2).
+room(windsor, foyer, dungeon, 1).
+room(windsor, hall, throne, 1).
+room(windsor, hall, stairs, 4).
+room(windsor, stairs, dungeon, 3).
+room(windsor, throne, stairs, 1).
+room(windsor, dungeon, escape, 5).
+room(windsor, escape, exit, 1).
+
+% Third castle for testing
+room(alnwick, enter, foyer, 1).
+room(alnwick, foyer, hall, 2).
+room(alnwick, hall, throne, 1).
+room(alnwick, hall, stairs, 4).
+room(alnwick, stairs, dungeon, 3).
+room(alnwick, dungeon, foundry, 5).
+room(alnwick, foyer, passage, 1).
+room(alnwick, passage, foundry, 1).
+room(alnwick, foundry, exit, 4).
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%helper code that generates permutations
+%https://stackoverflow.com/questions/9134380/how-to-access-list-permutations-in-prolog
+takeout(X,[X|R],R).
+takeout(X,[F |R],[F|S]) :-
+ takeout(X,R,S).
+
+perm([X|Y],Z) :-
+ perm(Y,W),
+ takeout(X,Z,W).
+perm([],[]).
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%printList(list)
+% print each element of list on a new line
+printList([]).
+printList([X | XS]) :-
+ print(X),
+ nl,
+ printList(XS).
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%reachable(Castle, AtRoom, GoalRoom, Path, Cost).
+% reachable in Castle at AtRoom is true if there exists a path to GoalRoom
+% has book keeping to keep track of the path followed and it's cost
+reachable(_, Room, Room, [], 0).
+
+reachable(Castle, AtRoom, GoalRoom, [AtRoom | NextPath], Cost):-
+ room(Castle, AtRoom, NextRoom, ThisCost),
+ reachable(Castle, NextRoom, GoalRoom, NextPath, NextCost),
+ Cost is NextCost + ThisCost.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%tour(Castle, AtRoom, Rooms, Tour)
+% tour in Castle is true if there exists a tour from AtRoom that visits
+% each room in Rooms in order and then exits the castle
+% has book keeping to collect the paths to each room in Rooms
+
+tour(Castle, AtRoom, [], Path):-
+ reachable(Castle, AtRoom, exit, Path, _).
+
+tour(Castle, AtRoom, [VisitRoom | RestRooms], [Path | RestTour]):-
+ reachable(Castle, AtRoom, VisitRoom, Path, _),
+ tour(Castle, VisitRoom, RestRooms, RestTour).
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%solveRooms(Castle, Rooms).
+% solve Rooms is true if there exists a tour that includes the rooms
+% in any order
+solveRooms(Castle, Rooms):-
+ perm(Rooms, PermutedRooms),
+ tour(Castle, enter, PermutedRooms, Path),
+ flatten(Path, FlattenedPath),
+ printList(FlattenedPath).
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%solveRoomsWithinCost(Castle, Cost)
+% Attempts to find a tour from enter to exit
+% within Cost, and if found, prints it!
+solveRoomsWithinCost(Castle, Cost):-
+ reachable(Castle, enter, exit, Path, TourCost),
+ Cost >= TourCost,
+ flatten(Path, FlattenedPath),
+ format("Total Cost is ~a out of limit ~a~n", [TourCost, Cost]),
+ printList(FlattenedPath).
|