forked from idlv75/dragons-and-princesses
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathtest.py
118 lines (93 loc) · 4.21 KB
/
test.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#!/usr/bin/python3
import sys, itertools
from itertools import repeat
import yaml
import io
global max_size, result
max_size = 0
### reslut is a list of lists:
### in each index [i] in result we'll have the following information:
###[coins, [positions of the dragons]].
### for example: if in result[2] we have [ [12,[1,4]], [7,[1,3]], [15, [4,3]] ]
### the meaning of that is that we have an options to kill 2 dragons
### if we'll chose to kill the dragons in 1,4 we'll get 12 coins
### if we'll chose kill the dragons in 1,3 we'll get 7 coins
### if we'll chose to kill the dragons in 3,4 we'll get 15 coins
### this is a recursive function.
### in this function we'll be able to calculate all of the options that the knight has
### if he will choose to kill the dragon that he met now or not
def dragon(coins, position, idx):
if idx == 1:
### results[1] - we decided to kill only 1 dragon
### therefore we'll put the coins that we'll get if we'll kill this specific dragon as the 'coins' , and the position of the dragon
result[1].append([coins, [position]])
else:
### recursive call - to make sure we'll cover all of the options
dragon(coins, position, idx - 1)
### go over all of the options that we have now (idx).
### check what will happen if we'll do them and also will kill the new dragon that we just met
for (options) in result[idx - 1:idx]:
for op in options:
### if we can see the position of the dragon in this option
### don't calculate it since we can be in any position only 1 time
if position not in op[1]:
result[idx].append([int(coins) + op[0], op[1] + [position]])
def princess(value):
### remove all of the options that will cause the knight to take the wrong princess
global result
for i in range(value, max_size - 1):
result[i].clear()
def final(num_of_needed_kiled_dragon):
### let's assume that we can't get the wanted princess... unless we'll find that we can :)
final = [-1]
### check only for the relevant options (which mean from the number of the dragons that we have to kill to get the princess and forward)
for idx, options in reversed(list(enumerate(result[num_of_needed_kiled_dragon:max_size - 1]))):
if options != []:
for x in options:
### if we found a better solution.
if x[0] > final[0]:
final = x
### if we have more than 1 option - push only the postions of the dragons
elif x[0] == final[0]:
final.append(x[1])
if -1 in final:
print(-1)
return
else:
for i in range(1, len(final)):
print(final[0])
print(len(final[i]))
[print((j + 1), end=' ') for j in final[i]]
print()
def starting(steps):
global result
num_of_needed_kiled_dragon = int(steps[-1].replace('p ', ''))
### if the last princess need more dragons than what we can have ever- don't waste time and return that we can't do it.
if num_of_needed_kiled_dragon > max_size - 1:
print(-1)
return
### the list of the options.
result = [[] for i in repeat(None, max_size - 1)]
### go over the steps without the last position in which we have the wanted princess
for idx, step in enumerate(steps[0:max_size-1]):
if 'd ' in step:
dragon(int(step.replace('d ', '')), idx + 1, idx + 1)
elif 'p ' in step:
princess(int(step.replace('p ', '')))
else:
raise Exception('wrong option ' + step + ' in the index ' + str(idx) + '\nmaybe you forgot the space?')
final(num_of_needed_kiled_dragon)
def check_file(file):
if not (os.path.exists(file)):
raise Exception('could not find path/file ' + file)
if __name__ == '__main__':
try:
# for personal debugging:
# steps = [7, 'd 10', 'd 10', 'p 2','d 1', 'd 1','p 4']
# steps = [7, 'd 10', 'd 10', 'p 2','d 1', 'd 1','p 2']
with open('input.yaml', 'r') as stream:
steps = yaml.safe_load(stream)
max_size = steps['count'] -1
starting(steps['opts'])
except:
raise