SHARE
TWEET

Untitled

a guest Oct 18th, 2019 75 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import random
  2.  
  3. def initialize(m, c, b):
  4.     initial_state = {'m': m, 'c': c, 'b': b}
  5.     return initial_state
  6.  
  7.  
  8. def ending_state(state):
  9.     if state['m'] == 0 and state['c'] == 0 and state['b'] == 0:
  10.         return True
  11.     return False
  12.  
  13.  
  14. def is_valid_state(state):
  15.     # verifica initializarea
  16.     if state['m'] < 0 or state['c'] < 0 or state['m'] > 3 or state['c'] > 3 or (state['b'] != 0 and state['b'] != 1):
  17.         return False
  18.     # verifica sa nu fie mai multi canibali decat misionari in portul original
  19.     if state['c'] > state['m'] and state['m'] > 0:
  20.         return False
  21.     # verifica sa nu fie mai multi canibali decat misionari in portul nou
  22.     if state['c'] < state['m'] and state['m'] < 3:
  23.         return False
  24.     return True
  25.  
  26.  
  27. def transition(state):
  28.     # minim 1 "om" maxim 2
  29.     if state['b'] == 1:
  30.         sign = -1
  31.         directie = "din portul original catre cel nou"
  32.     else:
  33.         sign = 1
  34.         directie = " din portul nou catre cel original"
  35.  
  36.     for m in range(3):
  37.         for c in range(3):
  38.             new_state = {'m': state['m']+sign*m,
  39.                          'c': state['c']+sign*c,
  40.                          'b': state['b']+sign*1}
  41.             if m+c >= 1 and m+c <= 2 and is_valid_state(new_state) == True:
  42.                 print "ia %d misionari si %d canibali %s " % (m, c, directie)
  43.                 return new_state
  44.  
  45.  
  46. def random_solution(state):
  47.     print "port original ( %d, %d, %d ) ------ port nou ( %d, %d, %d ) " % (
  48.         state['m'], state['c'], state['b'], 0, 0, 0)
  49.     nr = 0
  50.     while(ending_state(state) != True):
  51.         if state['b'] == 1:
  52.             sign = -1
  53.             directie = "din portul original catre cel nou"
  54.         else:
  55.             sign = 1
  56.             directie = " din portul nou catre cel original"
  57.         m = random.randrange(3)
  58.         c = random.randrange(3)
  59.         new_state = {'m': state['m']+sign*m,
  60.                      'c': state['c']+sign*c,
  61.                      'b': state['b']+sign*1}
  62.         nr += 1
  63.         if m+c >= 1 and m+c <= 2 and is_valid_state(new_state) == True:
  64.             print "ia %d misionari si %d canibali %s " % (m, c, directie)
  65.             state = new_state
  66.             print "port original ( %d, %d, %d ) ------ port nou ( %d, %d, %d ) " % (
  67.                 state['m'], state['c'], state['b'], 3-state['m'], 3-state['c'], state['b'])
  68.  
  69.     print "numarul de pasi:%d" % (nr)
  70.     return
  71.  
  72.  
  73. def check_state(state_list, new_state):
  74.     if new_state in state_list:
  75.         return False
  76.     return True
  77.  
  78.  
  79. def random_optimised_solution(state):
  80.     state_list = []
  81.     original_state = state
  82.     print "port original ( %d, %d, %d ) ------ port nou ( %d, %d, %d ) " % (
  83.         state['m'], state['c'], state['b'], 0, 0, 0)
  84.     nr = 0
  85.     tries = 0
  86.     state_list.append(state)
  87.     while(ending_state(state) != True):
  88.         if state['b'] == 1:
  89.             sign = -1
  90.             directie = "din portul original catre cel nou"
  91.         else:
  92.             sign = 1
  93.             directie = " din portul nou catre cel original"
  94.         m = random.randrange(3)
  95.         c = random.randrange(3)
  96.         new_state = {'m': state['m']+sign*m,
  97.                      'c': state['c']+sign*c,
  98.                      'b': state['b']+sign*1}
  99.         nr += 1
  100.         print nr
  101.         if nr > 100:
  102.             state = original_state
  103.             nr = 0
  104.             tries += 1
  105.             state_list = []
  106.  
  107.         if m+c >= 1 and m+c <= 2 and is_valid_state(new_state) == True and check_state(state_list, new_state):
  108.             print "ia %d misionari si %d canibali %s " % (m, c, directie)
  109.             state = new_state
  110.             print "port original ( %d, %d, %d ) ------ port nou ( %d, %d, %d ) " % (
  111.                 state['m'], state['c'], state['b'], 3-state['m'], 3-state['c'], state['b'])
  112.             state_list.append(state)
  113.  
  114.     print "numarul de pasi:%d si %d incercari" % (nr, tries)
  115.     return
  116.  
  117.  
  118. def DFS_solution(state, state_list):
  119.     ok=0
  120.         # generez de fiecare data chestia asta cu toate ca nu prea ajuta
  121.     posibilitati = []
  122.     for m in range(3):
  123.         for c in range(3):
  124.             if m+c >= 1 and m+c <= 2:
  125.                 posibilitati.append([m, c])
  126.    
  127.     for solutie in posibilitati:
  128.         if ok == 1:
  129.             return
  130.  
  131.         if state['b'] == 1:
  132.             sign = -1
  133.             directie = "din portul original catre cel nou"
  134.         else:
  135.             sign = 1
  136.             directie = " din portul nou catre cel original"
  137.  
  138.         m = solutie[0]
  139.         c = solutie[1]
  140.         new_state = {'m': state['m']+sign*m,
  141.                      'c': state['c']+sign*c,
  142.                      'b': state['b']+sign*1}
  143.         if is_valid_state(new_state) == True and check_state(state_list, new_state):
  144.             print "ia %d misionari si %d canibali %s " % (m, c, directie)
  145.             state = new_state
  146.             print "port original ( %d, %d, %d ) ------ port nou ( %d, %d, %d ) " % (
  147.                 state['m'], state['c'], state['b'], 3-state['m'], 3-state['c'], state['b'])
  148.             state_list.append(state)
  149.  
  150.             if ending_state(state) == True:
  151.                 ok = 1
  152.                 return
  153.             else:
  154.                 DFS_solution(state, state_list)
  155.  
  156.     return
  157.  
  158.  
  159. def BFS_solution(state, state_list):
  160.     posibilitati = []
  161.     for m in range(3):
  162.         for c in range(3):
  163.             if m+c >= 1 and m+c <= 2:
  164.                 posibilitati.append([m, c])
  165.     stiva = posibilitati
  166.  
  167.     while ending_state(state) != True:
  168.         for solutie in stiva:
  169.             if state['b'] == 1:
  170.                 sign = -1
  171.                 directie = "din portul original catre cel nou"
  172.             else:
  173.                 sign = 1
  174.                 directie = " din portul nou catre cel original"
  175.             m = solutie[0]
  176.             c = solutie[1]
  177.             new_state = {'m': state['m']+sign*m,
  178.                          'c': state['c']+sign*c,
  179.                          'b': state['b']+sign*1}
  180.             if is_valid_state(new_state) == True and check_state(state_list, new_state):
  181.                 print "ia %d misionari si %d canibali %s " % (m, c, directie)
  182.                 state = new_state
  183.                 print "port original ( %d, %d, %d ) ------ port nou ( %d, %d, %d ) " % (
  184.                     state['m'], state['c'], state['b'], 3-state['m'], 3-state['c'], state['b'])
  185.  
  186.     return
  187.  
  188.  
  189. def main():
  190.     state = initialize(3, 3, 1)
  191.     # random_solution(state)
  192.     print "Random Optimized"
  193.  
  194.     random_optimised_solution(state)
  195.     print "DFS"
  196.  
  197.     DFS_solution(state, [])
  198.     print "BFS"
  199.     BFS_solution(state, [])
  200.  
  201.     return 0
  202.  
  203.  
  204. if __name__ == "__main__":
  205.     main()
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