• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Jun 25th, 2019 53 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #Create list of visited solutions
2.     listPrevSolutions = []
3.     #Create correspnding list of number of steps to reach solution
4.     listTotalSteps = []
5.
6.     list_index_steps = []
7.
8.     def MoveWater (jugMax,
9.                     jugState,
10.                     targetVol,
11.                     runningTotal,
12.                     previousSteps,
13.                     listLength):
14.         global list_index_steps
15.
17.     listPosition = listLength
18.
19.     jugA_max = jugMax[0]
20.     jugB_max = jugMax[1]
21.     jugC_max = jugMax [2]
22.
23.     jugA_state = jugState[0]
24.     jugB_state = jugState[1]
25.     jugC_state = jugState[2]
26.
27.     if jugA_state == targetVol or jugB_state == targetVol or jugC_state == targetVol:
28.         print ("Target achieved in 1 step. Fill up a fucking jug")
29.         return True
30.
31.     #Move 1: move from A into B (if room) AND (if not state doesn't exist)
32.     if jugA_state !=0:
33.         if jugB_state < jugB_max:
34.             #Empty A into B if room
35.             if jugB_state + jugA_state <= jugB_max:
36.                 new_jugA_state, new_jugB_state = 0, jugB_state + jugA_state
37.             else: #Empty as much of A into B
38.                 new_jugA_state, new_jugB_state = (jugA_state - (jugB_max-jugB_state)), jugB_max
39.
40.             new_jugC_state = jugC_state
41.             if [new_jugA_state,new_jugB_state,new_jugC_state] not in listPrevSolutions:
42.                 listPrevSolutions.append([new_jugA_state,new_jugB_state,new_jugC_state])
43.                 listTotalSteps.append(runningTotal+1)
44.                 list_index_steps.append(previousSteps + [listPosition])
45.                 listPosition +=1
46.
48.
49.             if new_jugA_state == targetVol or new_jugB_state == targetVol or new_jugC_state == targetVol:
50.                 print (targetVol,"ml reached in", runningTotal+1,"steps")
51.                 print (print_Steps_Taken(previousSteps + [listPosition-1]))
52.                 return True
53.
54.     #Move 2: move from A into C (if room) AND (if not state doesn't exist)
55.     if jugA_state !=0:
56.         if jugC_state < jugC_max:
57.             #Empty A into C if room
58.             if jugC_state + jugA_state <= jugC_max:
59.                 new_jugA_state, new_jugC_state = 0, jugC_state+ jugA_state
60.             else: #Empty as much of A into C
61.                 new_jugA_state, new_jugC_state = (jugA_state - (jugC_max-jugC_state)), jugC_max
62.
63.             new_jugB_state = jugB_state
64.             if [new_jugA_state,new_jugB_state,new_jugC_state] not in listPrevSolutions:
65.                 listPrevSolutions.append([new_jugA_state,new_jugB_state,new_jugC_state])
66.                 listTotalSteps.append(runningTotal+1)
67.                 list_index_steps.append(previousSteps + [listPosition])
68.                 listPosition +=1
69.
71.
72.             if new_jugA_state == targetVol or new_jugB_state == targetVol or new_jugC_state == targetVol:
73.                 print (targetVol,"ml reached in", runningTotal+1,"steps")
74.                 print (print_Steps_Taken(previousSteps + [listPosition-1]))
75.                 return True
76.
77.     #Move 3: move from B into A (if room) AND (if not state doesn't exist)
78.     if jugB_state !=0:
79.         if jugA_state < jugA_max:
80.             #Empty B into A if room
81.             if jugA_state + jugB_state <= jugA_max:
82.                 new_jugB_state, new_jugA_state = 0, jugA_state + jugB_state
83.             else: #Empty as much of B into A
84.                 totalToMove = jugA_max - jugA_state
85.                 new_jugA_state, new_jugB_state = jugA_max, jugB_state - totalToMove
86.
87.             new_jugC_state = jugC_state
88.             if [new_jugA_state,new_jugB_state,new_jugC_state] not in listPrevSolutions:
89.                 listPrevSolutions.append([new_jugA_state,new_jugB_state,new_jugC_state])
90.                 listTotalSteps.append(runningTotal+1)
91.                 list_index_steps.append(previousSteps + [listPosition])
92.                 listPosition +=1
93.
95.
96.             if new_jugA_state == targetVol or new_jugB_state == targetVol or new_jugC_state == targetVol:
97.                 print (targetVol,"ml reached in", runningTotal+1,"steps")
98.                 print (print_Steps_Taken(previousSteps + [listPosition-1]))
99.                 return True
100.
101.     #Move 4: move from B into C (if room) AND (if not state doesn't exist)
102.     if jugB_state !=0:
103.         if jugC_state < jugC_max:
104.             #Empty B into C if room
105.             if jugC_state + jugB_state <= jugC_max:
106.                 new_jugB_state, new_jugC_state = 0, jugC_state + jugB_state
107.             else: #Empty as much of B into C
108.                 new_jugB_state, new_jugC_state = (jugB_state - jugC_max), jugC_max
109.
110.             new_jugA_state = jugA_state
111.             if [new_jugA_state,new_jugB_state,new_jugC_state] not in listPrevSolutions:
112.                 listPrevSolutions.append([new_jugA_state,new_jugB_state,new_jugC_state])
113.                 listTotalSteps.append(runningTotal+1)
114.                 list_index_steps.append(previousSteps + [listPosition])
115.                 listPosition +=1
116.
118.
119.             if new_jugA_state == targetVol or new_jugB_state == targetVol or new_jugC_state == targetVol:
120.                 print (targetVol,"ml reached in", runningTotal+1,"steps")
121.                 print (print_Steps_Taken(previousSteps + [listPosition-1]))
122.                 return True
123.
124.     #Move 5: move from C into B (if room) AND (if not state doesn't exist)
125.     if jugC_state !=0:
126.         if jugB_state < jugB_max:
127.             #Empty C into B if room
128.             if jugC_state + jugB_state <= jugB_max:
129.                 new_jugC_state, new_jugB_state = 0, jugB_state + jugC_state
130.             else: #Empty as much of C into B
131.                 totalToMove = jugB_max - jugB_state
132.                 new_jugB_state, new_jugC_state = jugB_max, jugC_state - totalToMove
133.
134.             new_jugA_state = jugA_state
135.             if [new_jugA_state,new_jugB_state,new_jugC_state] not in listPrevSolutions:
136.                 listPrevSolutions.append([new_jugA_state,new_jugB_state,new_jugC_state])
137.                 listTotalSteps.append(runningTotal+1)
138.                 list_index_steps.append(previousSteps + [listPosition])
139.                 listPosition +=1
140.
142.
143.             if new_jugA_state == targetVol or new_jugB_state == targetVol or new_jugC_state == targetVol:
144.                 print (targetVol,"ml reached in", runningTotal+1,"steps")
145.                 print (print_Steps_Taken(previousSteps + [listPosition-1]))
146.                 return True
147.
148.     #Move 6: move from C into A (if room) AND (if not state doesn't exist)
149.     if jugC_state !=0:
150.         if jugA_state < jugA_max:
151.             #Empty C into A if room
152.             if jugA_state + jugC_state <= jugA_max:
153.                 new_jugC_state, new_jugA_state = 0, jugA_state + jugC_state
154.             else: #Empty as much of C into A
155.                 totalToMove = jugA_max - jugA_state
156.                 new_jugA_state, new_jugC_state = jugA_max, jugC_state - totalToMove
157.
158.             new_jugB_state = jugB_state
159.             if [new_jugA_state,new_jugB_state,new_jugC_state] not in listPrevSolutions:
160.                 listPrevSolutions.append([new_jugA_state,new_jugB_state,new_jugC_state])
161.                 listTotalSteps.append(runningTotal+1)
162.                 list_index_steps.append(previousSteps + [listPosition])
163.                 listPosition +=1
164.
166.
167.             if new_jugA_state == targetVol or new_jugB_state == targetVol or new_jugC_state == targetVol:
168.                 print (targetVol,"ml reached in", runningTotal+1,"steps")
169.                 print (print_Steps_Taken(previousSteps + [listPosition-1]))
170.                 return True
171.
172.     #Move 7 - Empty A
173.     if jugA_state != 0:
174.         if jugB_state != 0 or jugC_state !=0:
175.             if [0,jugB_state,jugC_state] not in listPrevSolutions:
176.                     listPrevSolutions.append([0,jugB_state,jugC_state])
177.                     listTotalSteps.append(runningTotal+1)
178.                     list_index_steps.append(previousSteps + [listPosition])
179.                     listPosition +=1
180.
182.
183.     #Move 8 - Empty B
184.     if jugB_state != 0:
185.         if jugA_state != 0 or jugC_state !=0:
186.             if [jugA_state,0,jugC_state] not in listPrevSolutions:
187.                     listPrevSolutions.append([jugA_state,0,jugC_state])
188.                     listTotalSteps.append(runningTotal+1)
189.                     list_index_steps.append(previousSteps + [listPosition])
190.                     listPosition +=1
191.
193.
194.     #Move 9 - Empty C
195.     if jugC_state != 0:
196.         if jugB_state != 0 or jugA_state !=0:
197.             if [jugA_state,jugB_state,0] not in listPrevSolutions:
198.                     listPrevSolutions.append([jugA_state,jugB_state,0])
199.                     listTotalSteps.append(runningTotal+1)
200.                     list_index_steps.append(previousSteps + [listPosition])
201.                     listPosition +=1
202.
204.
205.     #Move 10 - Fill A
206.     if jugA_state!=jugA_max:
207.         if jugB_state != jugB_max or jugC_state!=jugC_max:
208.             if [jugA_max,jugB_state,jugC_state] not in listPrevSolutions:
209.                     listPrevSolutions.append([jugA_max,jugB_state,jugC_state])
210.                     listTotalSteps.append(runningTotal+1)
211.                     list_index_steps.append(previousSteps + [listPosition])
212.                     listPosition +=1
213.
215.
216.     #Move 11 - Fill B
217.     if jugB_state!=jugB_max:
218.         if jugA_state!=jugA_max or jugC_state!=jugC_max:
219.                 if [jugA_state,jugB_max,jugC_state] not in listPrevSolutions:
220.                     listPrevSolutions.append([jugA_state,jugB_max,jugC_state])
221.                     listTotalSteps.append(runningTotal+1)
222.                     list_index_steps.append(previousSteps + [listPosition])
223.                     listPosition +=1
224.
226.
227.     #Move 12 - Fill C
228.     if jugC_state!=jugC_max:
229.         if jugA_state != jugA_max or jugB_state!=jugB_max:
230.                 if [jugA_state,jugB_state,jugC_max] not in listPrevSolutions:
231.                     listPrevSolutions.append([jugA_state,jugB_state,jugC_max])
232.                     listTotalSteps.append(runningTotal+1)
233.                     list_index_steps.append(previousSteps + [listPosition])
234.                     listPosition +=1
235.
237.
238.     if noNewSolutionAdded == 1 and listPrevSolutions.index(jugState) == len(listPrevSolutions) - 1:
239.         print ("No new possible solutions")
240.         return True
241.
242.     return False
243.
244. def print_Steps_Taken(previousSteps):
245.     solution = []
246.     for index in previousSteps:
247.         solution += [listPrevSolutions[index]]
248.     return solution
249.
250.
251. def setjugVolumes():
252.     #Set jug sizes (a,b,c) and target volume (d)
253.     a = int(input("Please enter volume of largest jug: "))
254.     b = int(input("Please enter volume of second largest jug: "))
255.     c = int(input("Please enter volume of third largest jug: "))
256.     jugsMax = [a,b,c]
257.     targetVol = int(input("Please enter target volume: "))
258.     return jugsMax, targetVol
259.
260. def possibleStartStates():
261.     #Set jug states
262.     # (full, empty, empty), (full, full empty),
263.     #(empty, full, empty), (empty, full, full),
264.     #(empty, empty, full) ,(full, empty, full),
265.     startStates = [
266.         [5,0,0], [5,3,0],
267.         [0,3,0], [0, 3,1],
268.         [0,0,1], [5,0,1]]
269.     return startStates
270.
271. if __name__ == "__main__":
272.     jugMax, targetVol = setjugVolumes()
273.     #Get all possible start states - add featur later and run for loop for ALL possible
274.     #...states. Add this feature later
275.     jugA_max = jugMax[0]
276.     jugB_max = jugMax[1]
277.     jugC_Max = jugMax[2]
278.
279.     #Add first state to list with runningTotal
280.     listPrevSolutions.append([jugA_max, 0,0])
281.     listTotalSteps.append(1)
282.
283.     listPrevSolutions.append([0, jugB_max,0])
284.     listTotalSteps.append(1)
285.
286.     listPrevSolutions.append([0, 0,jugC_Max])
287.     listTotalSteps.append(1)
288.
289.     listPrevSolutions.append([jugA_max, jugB_max,0])
290.     listTotalSteps.append(2)
291.
292.     listPrevSolutions.append([jugA_max, 0,jugC_Max])
293.     listTotalSteps.append(2)
294.
295.     listPrevSolutions.append([0, jugB_max,jugC_Max])
296.     listTotalSteps.append(2)
297.
298.     list_index_steps.append ([0])
299.     list_index_steps.append ([1])
300.     list_index_steps.append ([2])
301.     list_index_steps.append ([3])
302.     list_index_steps.append ([4])
303.     list_index_steps.append ([5])
304.
305.
306.     #Now run the function
307.
308.     counter = 0
309.     for item in listPrevSolutions:
310.         jugState = item
311.         runningTotal = listTotalSteps[counter]
312.         previousSteps = list_index_steps[counter]
313.         listLength = len(listPrevSolutions)
314.         x = MoveWater(jugMax,
315.                     jugState,
316.                     targetVol,
317.                     runningTotal,
318.                     previousSteps,
319.                     listLength)
320.         counter +=1
321.         if x == True:
322.             break
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top