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
119
120
121
122
123
124
125
126
127
| from collections import defaultdict
import thread, time
def div(a,b):
n = float(a)/b
intn = int(n)
return intn if intn == n else -1
OPS = {"+": lambda a,b: a+b,
"-": lambda a,b: a-b,
"*": lambda a,b: a*b,
"/": div}
last_len = defaultdict(lambda: 1000)
solutions = defaultdict(list)
def solve(target, all_numbers, numbers=None, operations=[]):
if not numbers:
numbers = all_numbers
for i, a in enumerate(numbers):
if a<=0: continue
for j, b in enumerate(numbers):
if i == j or b<=0: continue
for op, func in OPS.iteritems():
n = func(a, b)
if n<=0: continue
left_numbers = list(numbers)
left_numbers.remove(a)
left_numbers.remove(b)
left_numbers.append(n)
added_operations = operations+[(a,op,b,n)]
if n == target:
add(target, all_numbers, added_operations)
else:
solve(target, all_numbers, left_numbers, added_operations)
def add(target, all_numbers, operations):
global last_len
if len(operations) < last_len[target, all_numbers]:
show(target, all_numbers, operations)
last_len[target, all_numbers] = len(operations)
solutions[target, all_numbers].append(tuple(operations))
def show(target, all_numbers, operations):
all_numbers = tuple(all_numbers)
len_ops = len(operations)
print _('SHOW') % locals()
for (a,op,b,n) in operations:
print a, op, b, '=', n
print '*'*10
def shortest(target, all_numbers):
s = tuple(solutions[target, all_numbers])
print _('SHORTEST')
if len(s) == 0:
print _('NO SOLUTION')
return
show(target, all_numbers, sorted(reversed(s), key=len)[0])
def test():
puzzles = [(468, (1,6,6,7,2,3))]
for p in puzzles:
solve(*p)
shortest(*p)
def play():
global started
all_numbers = []
print '*'*20
while True:
try:
n = input(_("NEXT NUMBER"))
except KeyboardInterrupt:
return False
except:
all_numbers = tuple(all_numbers)
if len(all_numbers) == 0:
return False
v = input(_("TARGET"))
try:
start = time.time()
solve(v, all_numbers)
end = time.time()
shortest(v, all_numbers)
s = end-start
m = int(s/60)
s = int(s-m*60)
duration = '%sm%ss' % (m, s)
count = len(solutions[v, all_numbers])
print _('TOOK') % locals()
except KeyboardInterrupt:
pass
return True
else:
all_numbers.append(n)
return True
messages = {'fr': {'NEXT NUMBER': 'Numero suivant (laisser vide si complet)? ',
'TARGET': 'Compte? ',
'NO SOLUTION': 'Pas de solution!',
'SHORTEST': 'Recherche de la plus courte solution en cours...',
'SHOW': 'Compte %(target)s, avec %(all_numbers)s en %(len_ops)s etapes:',
'TOOK': 'Trouve %(count)s solutions en %(duration)s.',
'HELLO': 'Salut.',
'GOODBYE': 'Au revoir.'},
'en': {'NEXT NUMBER': 'Next number (Leave empty if full)? ',
'TARGET': 'Target number? ',
'NO SOLUTION': 'No solution!',
'SHORTEST': 'Finding shortest...',
'SHOW': 'Target %(target)s, with %(all_numbers)s in %(len_ops)s steps:',
'TOOK': 'Took %(duration)s to find %(count)s solutions.',
'HELLO': 'Hello.',
'GOODBYE': 'Goodbye.'},
}
def _(msg):
global messages, lang
return messages[lang][msg]
if __name__ == "__main__":
lang = raw_input('fr/en?')
if lang not in messages:
lang = 'en'
print _('HELLO')
while play():
pass
print _('GOODBYE') |
