• API
• FAQ
• Tools
• Archive
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.
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.         },
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.
Not a member of Pastebin yet?