/* N water jugs model in Picat. This is a generalization of water_jugs.pi and water_jugs2.pi and is taken from a_stolen_balsam.pi Compared to the traditional 2 jugs problem, this model can take any number of jugs, not just 2. It comes with some costs: - it can be a little slower for 2 jugs problems than the dedicated 2 jugs solver in water_jugs2.pi - it requires an extra jug that represents the "infinite" amount of water (though it must have some integer value) as well as a "ground" jug to which water can be poured to the "ground". This version can also model the variant of water jug problem that is represented in a_stolen_balsam.pi in which there are an exact amount of water to distribute. 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. % % This is the problem from a_stolen_balsam.pi % 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 way to encode a standard 3 jugs puzzle. Note that there must be an extra jug for an endless supply of water and for emptying a jug. This is the first vessel/jug in the lists (here with a capacity of 20). This is the Die Hard version: Jugs are of sizes 5L and 3L and the object is to measure 4L, i.e [5,3] -> [4,0]. This is the unique solution: Plan: Pour 5 liter from the 20 vessel to the 5 vessel: [15,5,0] Pour 3 liter from the 5 vessel to the 3 vessel: [15,2,3] Pour 3 liter from the 3 vessel to the 20 vessel: [18,2,0] Pour 2 liter from the 5 vessel to the 3 vessel: [18,0,2] Pour 5 liter from the 20 vessel to the 5 vessel: [13,5,2] Pour 1 liter from the 5 vessel to the 3 vessel: [13,4,3] Pour 3 liter from the 3 vessel to the 20 vessel: [16,4,0] len = 7 Compare with the result from water_jugs2.pi (go5/0) [fill,x,from,ground,[5,0]] [fill,y,from,x,with,3,[2,3]] [empty,y,[2,0]] [fill,y,from,x,with,2,[0,2]] [fill,x,from,ground,[5,2]] [fill,y,from,x,with,1,[4,3]] [empty,y,[4,0]] len = 7 */ go3 ?=> Capacities = [20,5,3], Start = [20,0,0], Final = [_,4,0], cl_facts($[final_state(Final)]), best_plan_nondet([Start,Capacities],Plan,_Cost), print_plan(Plan), fail, nl. go3 => true. /* However, the generality has its price: it's a little slower than the specific 3 jugs problem. Consider for example the harder version [968,283] -> [2,0] which has 946 steps. Time for: - go4/0: 0.6s - water_jugs2.pi go11/0: 0.111s */ go4 ?=> nolog, Capacities = [10000,968,283], Start = [10000,0,0], Final = [_,2,0], cl_facts($[final_state(Final)]), best_plan_nondet([Start,Capacities],Plan,_Cost), print_plan(Plan), % fail, nl. go4 => 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. */ go5 ?=> % 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. go5 => true. /* This is the solution for Puzzle 138. At the brook from Adrian Groza "Modelling Puzzles in First Order Logic"" """ A man goes to the brook with two measures of 15 pints and 16 pints. How is he to measure exactly 8 pints of water, in the fewest possible transactions? Filling or empty- ing a vessel or pouring any quantity from one vessel to another counts as a transaction. (puzzle 403 from Dudeney (2016)) """ Note: Groza shows a 28 step solution. Here is a 28 step solution: Pour 15 liter from the 1000 vessel to the 15 vessel: [985,0,15] Pour 15 liter from the 15 vessel to the 16 vessel: [985,15,0] Pour 15 liter from the 1000 vessel to the 15 vessel: [970,15,15] Pour 1 liter from the 15 vessel to the 16 vessel: [970,16,14] Pour 16 liter from the 16 vessel to the 1000 vessel: [986,0,14] Pour 14 liter from the 15 vessel to the 16 vessel: [986,14,0] Pour 15 liter from the 1000 vessel to the 15 vessel: [971,14,15] Pour 2 liter from the 15 vessel to the 16 vessel: [971,16,13] Pour 16 liter from the 16 vessel to the 1000 vessel: [987,0,13] Pour 13 liter from the 15 vessel to the 16 vessel: [987,13,0] Pour 15 liter from the 1000 vessel to the 15 vessel: [972,13,15] Pour 3 liter from the 15 vessel to the 16 vessel: [972,16,12] Pour 16 liter from the 16 vessel to the 1000 vessel: [988,0,12] Pour 12 liter from the 15 vessel to the 16 vessel: [988,12,0] Pour 15 liter from the 1000 vessel to the 15 vessel: [973,12,15] Pour 4 liter from the 15 vessel to the 16 vessel: [973,16,11] Pour 16 liter from the 16 vessel to the 1000 vessel: [989,0,11] Pour 11 liter from the 15 vessel to the 16 vessel: [989,11,0] Pour 15 liter from the 1000 vessel to the 15 vessel: [974,11,15] Pour 5 liter from the 15 vessel to the 16 vessel: [974,16,10] Pour 16 liter from the 16 vessel to the 1000 vessel: [990,0,10] Pour 10 liter from the 15 vessel to the 16 vessel: [990,10,0] Pour 15 liter from the 1000 vessel to the 15 vessel: [975,10,15] Pour 6 liter from the 15 vessel to the 16 vessel: [975,16,9] Pour 16 liter from the 16 vessel to the 1000 vessel: [991,0,9] Pour 9 liter from the 15 vessel to the 16 vessel: [991,9,0] Pour 15 liter from the 1000 vessel to the 15 vessel: [976,9,15] Pour 7 liter from the 15 vessel to the 16 vessel: [976,16,8] len = 28 */ go6 ?=> nolog, Capacities = [100,16,15], Start = [100,0,0], Final = [_,_,8], 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. go6 => true. /* https://medium.com/the-pub/can-you-crack-this-microsoft-interview-puzzle-e92fa5227dd2 """ Imagine you have three containers: - Container A can hold 3 liters of oil. - Container B can hold 5 liters of oil. - Container C can hold 8 liters of oil (currently full). Your task is to split the 8 liters of oil into two equal parts, with exactly 4 liters in Container B and 4 liters in Container C. """ Here is the unique solutions (first found by hand) Plan: Pour 5 liter from the 8 vessel to the 5 vessel: [0,5,3] Pour 3 liter from the 5 vessel to the 3 vessel: [3,2,3] Pour 3 liter from the 3 vessel to the 8 vessel: [0,2,6] Pour 2 liter from the 5 vessel to the 3 vessel: [2,0,6] Pour 5 liter from the 8 vessel to the 5 vessel: [2,5,1] Pour 1 liter from the 5 vessel to the 3 vessel: [3,4,1] Pour 3 liter from the 3 vessel to the 8 vessel: [0,4,4] len = 7 cost = 7 */ go7 ?=> nolog, Capacities = [3,5,8], Start = [0,0,8], Final = [_,4,4], 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. go7 => true. /* From https://medium.com/puzzle-sphere/the-greatest-common-divisor-math-rule-behind-water-jug-puzzle-88cca03733bf Measure 1..9 using a 4 gallon jug and a 9-gallon jug """ Using the Euclidean algorithm: gcd(4,9) = 1 Since the GCD is 1, we can express any positive integer as a combination of 4 and 9. This guarantees that we can measure all values from 1 gallon to 9 gallons using a sequence of filling, emptying, and transferring operations. If the GCD had been greater than 1 (e.g., if we had jugs of 6G and 9G where gcd⁡(6,9)=3, then we could only measure multiples of 3 (like 3G, 6G, 9G), but not all values from 1 to 9. """ */ go8 ?=> % nolog, A = 4, B = 9, Cap = A+B, println([a=A,b=B,cap=Cap]), Capacities = [Cap,A,B], Start = [Cap,0,0], member(N,1..max(A,B)), println(n=N), Final = [_,0,N], cl_facts($[final_state(Final)]), % best_plan_nondet([Start,Capacities],Plan,Cost), % best_plan([Start,Capacities],Plan,Cost), % best_plan_bb([Start,Capacities],Plan,Cost), best_plan_unbounded([Start,Capacities],Plan,Cost), % plan([Start,Capacities],Plan,Cost), % longest plan print_plan(Plan), println(cost=Cost), nl, fail, nl. go8 => true. /* All combinations for jugs sizes A,B in 2..19 (with gcd(A,B) = 1), and generating all amounts from 1..max(A,B). (Cf go8/0) Here are all pairs A,B (2..9) such that A<=B and gcd(A,B) == 1: Picat> X = [[A,B] : A in 2..19, B in A..19, gcd(A,B) == 1] X = [[2,3],[2,5],[2,7],[2,9],[2,11],[2,13],[2,15],[2,17],[2,19],[3,4],[3,5],[3,7],[3,8],[3,10],[3,11],[3,13],[3,14],[3,16],[3,17],[3,19],[4,5],[4,7],[4,9],[4,11],[4,13],[4,15],[4,17],[4,19],[5,6],[5,7],[5,8],[5,9],[5,11],[5,12],[5,13],[5,14],[5,16],[5,17],[5,18],[5,19],[6,7],[6,11],[6,13],[6,17],[6,19],[7,8],[7,9],[7,10],[7,11],[7,12],[7,13],[7,15],[7,16],[7,17],[7,18],[7,19],[8,9],[8,11],[8,13],[8,15],[8,17],[8,19],[9,10],[9,11],[9,13],[9,14],[9,16],[9,17],[9,19],[10,11],[10,13],[10,17],[10,19],[11,12],[11,13],[11,14],[11,15],[11,16],[11,17],[11,18],[11,19],[12,13],[12,17],[12,19],[13,14],[13,15],[13,16],[13,17],[13,18],[13,19],[14,15],[14,17],[14,19],[15,16],[15,17],[15,19],[16,17],[16,19],[17,18],[17,19],[18,19]] */ go9 ?=> % nolog, Map = get_global_map(), Max = 19, member(A,2..Max), member(B,A..Max), gcd(A,B) == 1, println("**************************************'"), Cap = A+B, println([a=A,b=B,cap=Cap]), Capacities = [Cap,A,B], Start = [Cap,0,0], member(N,1..max(A,B)), println(n=N), Final = [_,0,N], cl_facts($[final_state(Final)]), % best_plan_nondet([Start,Capacities],Plan,Cost), % best_plan([Start,Capacities],Plan,Cost), % best_plan_bb([Start,Capacities],Plan,Cost), best_plan_unbounded([Start,Capacities],Plan,Cost), % plan([Start,Capacities],Plan,Cost), % longest plan print_plan(Plan), println(cost=Cost), nl, Map.put([A,B],Map.get([A,B],[])++[Cost]), fail, nl. % Print the number of steps for each combinations of [A,B] go9 => /* foreach(V in get_global_map().to_list.sort) println(V) end, nl. */ 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.