Diferença entre dois produtos mais próximos de zero: solução sem força bruta?
Em ummuseu de ciências na Noruega Me deparei com o seguinte jogo matemático:
O objetivo é colocar os 10 dígitos de 0 a 9, de modo que a diferença entre os dois produtos seja a mais próxima de zero. (O 246 é a pontuação mais baixa atual).
Em casa, escrevi o seguinte código de força bruta:
import time
from itertools import permutations
def form_number(x, y, z, a, b):
# not explicitly stated, but presume that leading zeroes are not allowed
if x == 0 or a == 0:
return 0
return ((100 * x) + (10 * y) + z) * ((10 * a) + b)
def find_nearest_zero(*args):
assert len(args) == 10
return form_number(*args[:5]) - form_number(*args[5:])
if __name__ == '__main__':
start = time.time()
count = 0
for p in permutations(range(10), 10):
result = find_nearest_zero(*p)
if result == 0:
count += 1
print '{}{}{} * {}{} = {n}'.format(*p[:5], n=form_number(*p[:5]))
print '{}{}{} * {}{} = {n}'.format(*p[5:], n=form_number(*p[5:]))
print
print 'found {} solutions'.format(count)
print time.time() - start
Se não permitirmos zeros à esquerda, isso imprimirá 128 soluções possíveis em cerca de 12 segundos.
Mas fico me perguntando: existe um algoritmo ou uma maneira melhor de resolver isso de maneira não-bruta?