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') |
Partager