% 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).