SHARE
TWEET

Untitled

a guest Oct 23rd, 2019 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import copy
  2. import random
  3.  
  4. m = int(input('No. of missionaries: '))
  5. c = int(input('No. of cannibals: '))
  6. b = int(input('Boat capacity'))
  7. is_final = False
  8.  
  9.  
  10. def gen_state(b, b1, b2, m_load, c_load):
  11.     return {
  12.         'boat_pos': b,
  13.         'bank1': {
  14.             'c_count': b1['c_count'],
  15.             'm_count': b1['m_count']
  16.         },
  17.         'bank2': {
  18.             'c_count': b2['c_count'],
  19.             'm_count': b2['m_count']
  20.         },
  21.         'm_to_shift': m_load,
  22.         'c_to_shift': c_load
  23.     }
  24.  
  25.  
  26. initial_state = gen_state(1, {'c_count': c, 'm_count': m}, {
  27.                           'c_count': 0, 'm_count': 0}, 0, 0)
  28.  
  29.  
  30. def random_strategy(state) -> None:
  31.     global m, c, b, is_final, initial_state
  32.     turn = 0
  33.     previous_states = []
  34.     while not is_final:
  35.         turn += 1
  36.         if turn == 100:
  37.             state = copy.deepcopy(initial_state)
  38.             previous_states = []
  39.             turn = 0
  40.         # we pick the transition state
  41.         state['boat_pos'] = 1
  42.         copy_of_state = copy.deepcopy(state)
  43.         # we pick a random amount of missionaires and a random amount of cannibals
  44.         m_to_shift = random.randrange(0, state['bank1']['m_count']+1)
  45.         c_to_shift = random.randrange(0, state['bank1']['c_count']+1)
  46.         state['bank2']['m_count'] += m_to_shift
  47.         state['bank1']['m_count'] -= m_to_shift
  48.         state['bank2']['c_count'] += c_to_shift
  49.         state['bank1']['c_count'] -= c_to_shift
  50.         state['m_to_shift'] = m_to_shift
  51.         state['c_to_shift'] = c_to_shift
  52.         if not validate(state) or state in previous_states:
  53.             print(state)
  54.             print("Condition breached - reverting state")
  55.             state = copy.deepcopy(copy_of_state)
  56.             continue
  57.         else:
  58.             previous_states.append(state)
  59.             state['boat_pos'] = 2
  60.             print(state)
  61.             print("Correct transition")
  62.             state['m_to_shift'] = 0
  63.             state['c_to_shift'] = 0
  64.             if state['bank1']['m_count'] + state['bank1']['c_count'] == 0:
  65.                 is_final = True
  66.     if is_final:
  67.         print("Final state: ")
  68.         print(state)
  69.  
  70. def backtracking_strategy(state) -> None:
  71.     global m, c, b, is_final, initial_state
  72.     state_stack = []
  73.     turn = 0
  74.     while not is_final:
  75.         turn += 1
  76.         if turn == 100:
  77.             state = copy.deepcopy(initial_state)
  78.             state_stack = []
  79.         # we pick the transition state
  80.         state['boat_pos'] = 1
  81.         # we pick a random amount of missionaires and a random amount of cannibals
  82.         m_to_shift = random.randrange(0, state['bank1']['m_count']+1)
  83.         c_to_shift = random.randrange(0, state['bank1']['c_count']+1)
  84.         state['bank2']['m_count'] += m_to_shift
  85.         state['bank1']['m_count'] -= m_to_shift
  86.         state['bank2']['c_count'] += c_to_shift
  87.         state['bank1']['c_count'] -= c_to_shift
  88.         state['m_to_shift'] = m_to_shift
  89.         state['c_to_shift'] = c_to_shift
  90.         if not validate(state):
  91.             print(state)
  92.             print("Condition breached - reverting state")
  93.             if state_stack:
  94.                 state = copy.deepcopy(state_stack.pop())
  95.             else:
  96.                 state = copy.deepcopy(initial_state)
  97.             continue
  98.         else:
  99.             print(state)
  100.             print("Correct transition.")
  101.             state_stack.append(copy.deepcopy(state))
  102.             state['boat_pos'] = 2
  103.             state['m_to_shift'] = 0
  104.             state['c_to_shift'] = 0
  105.             if state['bank1']['m_count'] + state['bank1']['c_count'] == 0:
  106.                 is_final = True
  107.     if is_final:
  108.         print("Final state: ")
  109.         print(state)
  110.  
  111.  
  112. def validate(state) -> bool:
  113.     global b
  114.     if state['m_to_shift'] + state['c_to_shift'] > b:
  115.         return False
  116.     if state['bank1']['m_count'] < state['bank1']['c_count'] or state['bank2']['m_count'] < state['bank2']['c_count']:
  117.         return False
  118.     return True
  119.  
  120.  
  121. backtracking_strategy(initial_state)
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top