/* A stolen balsam in Picat. From Adrian Groza "Modelling Puzzles in First Order Logic" See https://www.researchgate.net/publication/374588335_Measuring_reasoning_capabilities_of_ChatGPT """ Puzzle 36. A stolen balsam Three men robbed a gentleman of a vase containing 24 ounces of balsam. While running away, they met in a forest a glass seller, from whom, in a great hurry, they purchased three vessels. On reaching a place of safety they wished to divide the booty, but they found that their vessels contained 5, 11, and 13 ounces respectively. How could they di- vide the balsam into equal portions? (puzzle 409 from Dudeney (2016)) """ There are three optimal plans with 6 steps (using best_plan_nondet to show all optimal solutions). Plan: Pour 11 liter from the 24 vessel to the 11 vessel: [13,0,11,0] Pour 5 liter from the 24 vessel to the 5 vessel: [8,0,11,5] Pour 5 liter from the 5 vessel to the 13 vessel: [8,5,11,0] Pour 8 liter from the 11 vessel to the 13 vessel: [8,13,3,0] Pour 5 liter from the 13 vessel to the 5 vessel: [8,8,3,5] Pour 5 liter from the 5 vessel to the 11 vessel: [8,8,8,0] len = 6 Plan: Pour 5 liter from the 24 vessel to the 5 vessel: [19,0,0,5] Pour 11 liter from the 24 vessel to the 11 vessel: [8,0,11,5] Pour 5 liter from the 5 vessel to the 13 vessel: [8,5,11,0] Pour 8 liter from the 11 vessel to the 13 vessel: [8,13,3,0] Pour 5 liter from the 13 vessel to the 5 vessel: [8,8,3,5] Pour 5 liter from the 5 vessel to the 11 vessel: [8,8,8,0] len = 6 Plan: Pour 5 liter from the 24 vessel to the 5 vessel: [19,0,0,5] Pour 5 liter from the 5 vessel to the 13 vessel: [19,5,0,0] Pour 11 liter from the 24 vessel to the 11 vessel: [8,5,11,0] Pour 8 liter from the 11 vessel to the 13 vessel: [8,13,3,0] Pour 5 liter from the 13 vessel to the 5 vessel: [8,8,3,5] Pour 5 liter from the 5 vessel to the 11 vessel: [8,8,8,0] len = 6 This planner model is more general than the standard 3 jugs problem, see for example: - water_jugs.pi, - water_jugs2.pi, - test_planner_water_jugs.pi For more examples how to use this planner model, see n_water_jugs.pi which also show how to model the traditional 3 jugs problem. This program was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import util. import planner. main => go. go ?=> Capacities = [24,13,11,5], Start = [24,0,0,0], Final = [8,8,8,0], cl_facts($[final_state(Final)]), best_plan_nondet([Start,Capacities],Plan,_Cost), print_plan(Plan), nl, fail, nl. go => true. /* Show some solutions using plan/4 with specific plan lengths. For example, here is a 10 step plan Plan: Pour 13 liter from the 24 vessel to the 13 vessel: [11,13,0,0] Pour 11 liter from the 24 vessel to the 11 vessel: [0,13,11,0] Pour 13 liter from the 13 vessel to the 24 vessel: [13,0,11,0] Pour 5 liter from the 24 vessel to the 5 vessel: [8,0,11,5] Pour 11 liter from the 11 vessel to the 24 vessel: [19,0,0,5] Pour 5 liter from the 5 vessel to the 13 vessel: [19,5,0,0] Pour 11 liter from the 24 vessel to the 11 vessel: [8,5,11,0] Pour 8 liter from the 11 vessel to the 13 vessel: [8,13,3,0] Pour 5 liter from the 13 vessel to the 5 vessel: [8,8,3,5] Pour 5 liter from the 5 vessel to the 11 vessel: [8,8,8,0] len = 10 Note: plan/4 is not non-deterministic so only one solution is found for each Max value. best_plan_nondet/n is the only non-deterministic plan solver in Picat. */ go2 ?=> Capacities = [24,13,11,5], Start = [24,0,0,0], Final = [8,8,8,0], cl_facts($[final_state(Final)]), member(Max,1..10), println(max=Max), plan([Start,Capacities],Max,Plan,_Cost), print_plan(Plan), fail, nl. go2 => true. /* Here is a (perhaps contrieved) variant of the stolen balsam puzzle: 6 thieves stole 60L of balsam and want to divide it so the first three thieves get the same amount and the last three thieves get the same amount. They bought vessels of sizes 30L, 25L, 19L, 11L, 9L, and 7L. How should the thieves divide the loot? Here is a plan of minimal 11 steps: Pour 19 liter from the 30 vessel to the 19 vessel: [41,0,19,0,0,0] Pour 9 liter from the 30 vessel to the 9 vessel: [32,0,19,0,9,0] Pour 19 liter from the 19 vessel to the 25 vessel: [32,19,0,0,9,0] Pour 19 liter from the 30 vessel to the 19 vessel: [13,19,19,0,9,0] Pour 6 liter from the 19 vessel to the 25 vessel: [13,25,13,0,9,0] Pour 7 liter from the 25 vessel to the 7 vessel: [13,18,13,0,9,7] Pour 7 liter from the 7 vessel to the 11 vessel: [13,18,13,7,9,0] Pour 7 liter from the 25 vessel to the 7 vessel: [13,11,13,7,9,7] Pour 9 liter from the 9 vessel to the 25 vessel: [13,20,13,7,0,7] Pour 7 liter from the 7 vessel to the 9 vessel: [13,20,13,7,7,0] Pour 7 liter from the 25 vessel to the 7 vessel: [13,13,13,7,7,7] len = 11 Side note: The longest plan is a huge plan of 113019 steps. This can be be shown by changing Cost = 1 to Cost = -1 in action/4. (Don't forget to change Cost back.) Another - and perhaps simpler - way is to use plan/3 instead. */ go3 ?=> % nolog, Capacities = [30,25,19,11,9,7], Start = [60,0,0,0,0,0], Final = [X,X,X,Y,Y,Y], cl_facts($[final_state(Final)]), % best_plan_nondet([Start,Capacities],Plan,_Cost), best_plan([Start,Capacities],Plan,Cost), % plan([Start,Capacities],Plan,Cost), % longest plan print_plan(Plan), println(cost=Cost), % fail, nl. go3 => true. % % Print a plan % print_plan(Plan) => println("Plan:"), foreach([pour,AF,liter,from,From,to,To,new = New] in Plan) printf("Pour %2d liter from the %2d vessel to the %2d vessel: %w\n",AF,From,To,New) end, println(len=Plan.len), nl. final([From|_]) :- final_state(From). table action([From,Capacities],To,Move,Cost) :- Len = From.len, select(F,1..Len,Rest), % Select From vessel select(T,Rest,_), % Select To vessel AmountF = From[F], AmountF > 0, CapT = Capacities[T], AmountT = From[T], % We must % - either fill the To vessel completely or % - fill everything from the From vessel AF = min(AmountF,CapT-AmountT), % pour AF ounces from vessel F to vessel T AF > 0, % We must do some pouring % Checks: AmountF - AF >= 0, AmountT + AF <= CapT, New = copy_term(From), New[F] := From[F]-AF, New[T] := From[T]+AF, sum(New) == sum(From), To = [New,Capacities], Move = [pour,AF,liter,from,Capacities[F],to,Capacities[T],new=New], Cost = 1.