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.  
  16.     noNewSolutionAdded = 1
  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.  
  47.                 noNewSolutionAdded = 0
  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.  
  70.                 noNewSolutionAdded = 0
  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.  
  94.                 noNewSolutionAdded = 0
  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.  
  117.                 noNewSolutionAdded = 0
  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.  
  141.                 noNewSolutionAdded = 0
  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.  
  165.                 noNewSolutionAdded = 0
  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.  
  181.                     noNewSolutionAdded = 0
  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.  
  192.                     noNewSolutionAdded = 0
  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.  
  203.                     noNewSolutionAdded = 0
  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.  
  214.                     noNewSolutionAdded = 0
  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.  
  225.                     noNewSolutionAdded = 0
  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.  
  236.                     noNewSolutionAdded = 0
  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. OK, I Understand
 
Top