<div class="notebook"> <div class="nb-cell markdown" name="md1"> # Train Consist This notebook is an accompaniment to the Playing with Prolog video "Train Consists". Different cars in a passenger train have different functions. There are sleeper cars with beds, a diner to feed the passengers, and so on. Each car has some restrictions (constraints) about where it must be in the train. For example, no one is allowed in the baggage car, so it can't be placed where it would block passengers from getting to the diner. </div> <div class="nb-cell html" name="htm1"> <iframe src="https://www.youtube.com/embed/KckDVWysAes" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen="" width="1211" height="681" frameborder="0"></iframe> </div> <div class="nb-cell markdown" name="md2"> # Consist First make sure we have a ground list of cars. We then make a list of unbound variables `Order`, a list of the car's positions. So if we had cars `[diner, sleeper, observation]` and we wanted to order them `[sleeper, diner, observation]` `Order` would be `[2, 1, 3]` We put constraints on `Order`, and then label to get a solution. Finally, we turn `Order` and `Cars` into an ordered list of cars. </div> <div class="nb-cell program" data-background="true" name="p1"> :- use_module(library(clpfd)). %! consist(+Cars:list, -Ordered:list) is nondet % % @arg Cars a bag of cars as a list % @arg Ordered a valid ordering of the cars as a list % % for simplicity the engine's assumed. % consist(Cars, Ordered) :- % for sanity, make sure Cars is a ground list % of cars is_list(Cars), ground(Cars), maplist(car_type, Cars), % we'll need the train length for many things length(Cars, Len), % create a list of the train positions % 1 based length(Order, Len), Order ins 1..Len, all_different(Order), % add the constraints constrain_positions(Cars, Order), % minimize distance to diner % we constrain Dist to be distance to diner diner_dist(Cars, Order, Dist), % label the cars labeling([min(Dist), ff], [Dist| Order]), % get a simple list of cars for the user pairs_keys_values(Pairs, Order, Cars), keysort(Pairs, OrderedPairs), pairs_keys_values(OrderedPairs, _, Ordered). </div> <div class="nb-cell markdown" name="md3"> # `constrain_positions` `constrain_positions` applies the constraints to the order. We get the length, then make up two variables `MinWalk` and `MaxWalk` to define the area of the train the passengers can move around in. Then we apply the constraints for each individual car. </div> <div class="nb-cell program" data-background="true" name="p2"> constrain_positions(Cars, Order) :- length(Cars, Len), % min and max car # passengers can reach [MinWalk, MaxWalk] ins 1..Len, MinWalk #=< MaxWalk, maplist(a_car(Len, MinWalk, MaxWalk), Cars, Order). </div> <div class="nb-cell markdown" name="md4"> # Individual Constraints We apply constraints for each car based on it's type. </div> <div class="nb-cell program" data-background="true" name="p3"> % the observation must be at the end, and we must % be able to walk to it a_car(Len, _MinWalk, Len, observation, Len). % the baggage and RPO cars must be outside the walk area a_car(_Len, MinWalk, MaxWalk, rpo, Order) :- Order #> MaxWalk #\/ Order #< MinWalk. a_car(_Len, MinWalk, MaxWalk, baggage, Order) :- Order #> MaxWalk #\/ Order #< MinWalk. % other cars must be walkable a_car(_Len, MinWalk, MaxWalk, Car, Order) :- member(Car, [sleeper, chair, diner, lounge, dome]), Order #>= MinWalk, Order #=< MaxWalk. </div> <div class="nb-cell markdown" name="md5"> # car_type Define the car types </div> <div class="nb-cell program" data-background="true" name="p4"> car_type(X) :- member(X, [rpo, baggage, sleeper, chair, diner, lounge, dome, observation]). </div> <div class="nb-cell markdown" name="md6"> # diner_dist/3 Define the walk distance penalty for placing cars in relation to the diner. </div> <div class="nb-cell program" data-background="true" name="p5"> diner_dist(Cars, _, 0) :- \+ memberchk(diner, Cars). % no diner! diner_dist(Cars, Order, Dist) :- nth1(DinerIndex, Cars, diner), % diner location in Cars nth1(DinerIndex, Order, DinerLoc), % unbound diner location diner_dist(Cars, Order, DinerLoc, 0, Dist). </div> <div class="nb-cell markdown" name="md7"> # diner_dist/5 A famulus for diner_dist/3 that scores the total walk distance. We pass the distance so far and the diner's location as well as the arguments to diner_dist/3 </div> <div class="nb-cell program" data-background="true" name="p6"> diner_dist([], _, _, Dist, Dist). diner_dist([Car | T], [Order|OT], DinerLoc, SoFar, Dist) :- member(Car, [sleeper, chair]), NewSoFar #= SoFar + abs(DinerLoc - Order), diner_dist(T, OT, DinerLoc, NewSoFar, Dist). % these cars don't count diner_dist([Car | T], [_|OT], DinerLoc, SoFar, Dist) :- member(Car, [rpo, baggage, diner, lounge, dome, observation]), diner_dist(T, OT, DinerLoc, SoFar, Dist). </div> <div class="nb-cell markdown" name="md8"> And we're ready to try it out. </div> <div class="nb-cell query" data-tabled="true" name="q1"> consist([baggage, observation, diner, sleeper, sleeper], X). </div> <div class="nb-cell query" data-tabled="true" name="q2"> consist([baggage, rpo, rpo, chair, chair], X). </div> <div class="nb-cell markdown" name="md9"> Some consists are impossible </div> <div class="nb-cell query" data-tabled="true" name="q3"> consist([observation, dome, observation], X). </div> <div class="nb-cell markdown" name="md10"> In case you want to fiddle locally, here's the whole program as a single block </div> <div class="nb-cell program" name="p7"> :- module(consist, [ consist/2 ]). /** <module> Tool for arranging train consists * */ :- use_module(library(clpfd)). %! consist(+Cars:list, -Ordered:list) is nondet % % @arg Cars a bag of cars as a list % @arg Ordered a valid ordering of the cars as a list % % for simplicity the engine's assumed. % consist(Cars, Ordered) :- % for sanity, make sure Cars is a ground list % of cars is_list(Cars), ground(Cars), maplist(car_type, Cars), % we'll need the train length for many things length(Cars, Len), % create a list of the train positions % 1 based length(Order, Len), Order ins 1..Len, all_different(Order), % add the constraints constrain_positions(Cars, Order), % minimize distance to diner % we constrain Dist to be distance to diner diner_dist(Cars, Order, Dist), % label the cars labeling([min(Dist), ff], [Dist| Order]), pairs_keys_values(Pairs, Order, Cars), keysort(Pairs, OrderedPairs), pairs_keys_values(OrderedPairs, _, Ordered). constrain_positions(Cars, Order) :- length(Cars, Len), % min and max car # passengers can reach [MinWalk, MaxWalk] ins 1..Len, MinWalk #=< MaxWalk, maplist(a_car(Len, MinWalk, MaxWalk), Cars, Order). % the observation must be at the end, and we must % be able to walk to it a_car(Len, _MinWalk, Len, observation, Len). % the baggage and RPO cars must be outside the walk area a_car(_Len, MinWalk, MaxWalk, rpo, Order) :- Order #> MaxWalk #\/ Order #< MinWalk. a_car(_Len, MinWalk, MaxWalk, baggage, Order) :- Order #> MaxWalk #\/ Order #< MinWalk. % other cars must be walkable a_car(_Len, MinWalk, MaxWalk, Car, Order) :- member(Car, [sleeper, chair, diner, lounge, dome]), Order #>= MinWalk, Order #=< MaxWalk. car_type(X) :- member(X, [rpo, baggage, sleeper, chair, diner, lounge, dome, observation]). diner_dist(Cars, _, 0) :- \+ memberchk(diner, Cars). % no diner! diner_dist(Cars, Order, Dist) :- nth1(DinerIndex, Cars, diner), % diner location in Cars nth1(DinerIndex, Order, DinerLoc), % unbound diner location diner_dist(Cars, Order, DinerLoc, 0, Dist). diner_dist([], _, _, Dist, Dist). diner_dist([Car | T], [Order|OT], DinerLoc, SoFar, Dist) :- member(Car, [sleeper, chair]), NewSoFar #= SoFar + abs(DinerLoc - Order), diner_dist(T, OT, DinerLoc, NewSoFar, Dist). % these cars don't count diner_dist([Car | T], [_|OT], DinerLoc, SoFar, Dist) :- member(Car, [rpo, baggage, diner, lounge, dome, observation]), diner_dist(T, OT, DinerLoc, SoFar, Dist). </div> </div>