Проверка уникального вывода в Python

Question

Вчера я столкнулся с забавной математической задачей, и она была решена, но с кодом, который я написал, мне пришлось делать прерывание клавиатуры, иначе оно будет работать вечно, смеется. Поэтому я изменил его, чтобы иметь конечное условие, , но теперь он печатает только 1 решение и останавливается.

Проблема выглядит так: «У вас есть числа 123456789, в этом порядке. Между каждым числом вы должны вставить либо ничего, либо знак плюс, либо знак умножения, чтобы полученное выражение равнялось 2002. Напишите программу который печатает все решения. (Есть два.) "

import random


def try1(param):
    global solved
    opers = ['+', '*', '']
    hotpotato = ('%s'.join(param) % (random.choice(opers),
                                     random.choice(opers),
                                     random.choice(opers),
                                     random.choice(opers),
                                     random.choice(opers),
                                     random.choice(opers),
                                     random.choice(opers),
                                     random.choice(opers),
                                     )
             )
    if eval(hotpotato) == 2002:
        solved += 1
        print "Solution:", hotpotato, "= 2002     :-)"

    else:
        pass


solved = 0
while solved == 0:
    try1('123456789')

Этот код печатает первое решение, с которым он сталкивается и останавливается. Может кто-нибудь сказать мне, как заставить его печатать оба решения до его остановки?

Answer 1

Не используйте случайные, перечислите все возможные комбинации операторов (ну, вы можете немного сократить пространство поиска, если первая пара чисел, результат которых больше, чем 2002, результат никак не будет меньше ). itertools твой друг.

Если вы сделаете это, ваша программа завершит работу в кратчайшие сроки.

Если вы знаете, что есть точно два решения, вы можете вернуть решение из try1 и выполнить цикл, пока не соберете два разных решения, но это не очень элегантно, не так ли?

Answer 2

Решением вашей проблемы является решение проблемы == 2.

Но настоящая проблема вашего кода - использование случайного. Использование случайного в алгоритме, как правило, плохая идея. Существует вероятность того, что ваш код длится более века.

Существует гораздо более простой и быстрый способ использования itertools:

import itertools

for s in itertools.product(("+", "*", ""), repeat=8):
    z = itertools.izip_longest("123456789", s, fillvalue="")
    e = "".join(itertools.chain.from_iterable(z))

    if eval(e) == 2002:
        print(e)

Нет необходимости прерывать, когда найдено два решения, потому что код уже завершен за 0,2 секунды:).

Answer 3

Чтобы получить оба (все) решения, вам нужен совершенно другой подход к решению этой проблемы. Проверьте все перестановки вставленных операций. Как рассчитать перестановки приведены здесь: http://www.bearcave.com/random_hacks/permute.html

EDIT:

Пример:

ops = ['+', '*']

def gen(ver, i):
    if i == len(ver):
        return
    for op in ops:
        ver = ver[:i] + op + ver[i:]
        if eval(ver) == 2002:
            yield ver
        for j in range(i + 2, len(ver)):
            for sol in gen(ver, j):
                yield sol
        ver = ver[:i] + ver[i+1:]

for sol in gen("123456789", 1):
    print "solution:", sol

Выход:

solution: 1*2+34*56+7+89
solution: 1*23+45*6*7+89

Answer 4

Храните ваши решения в наборе:

solutions = set([])

Каждый раз, когда решение найдено, обновляйте набор:

solutions.append(solution)

Наборы хороши тем, что не хранят дубликаты:

>>> len(set([1, 1, 1, 1, 1, 1, 1]))
1

Так что просто зацикливайтесь, пока размер набора не станет больше единицы:

while len(solved) < 2:
    try1('123456789')

---

Кроме того, вы можете сократить этот код:

hotpotato = ('%s'.join(param) % (random.choice(opers),
                                 random.choice(opers),
                                 random.choice(opers),
                                 random.choice(opers),
                                 random.choice(opers),
                                 random.choice(opers),
                                 random.choice(opers),
                                 random.choice(opers),
                                 )
         )

К этому:

hotpotato = ('%s'.join(param) % (random.choice(opers) for i in range(8))))

Answer 5

Для справки, я бы рекомендовал другой подход к поиску решений, такой как предложенный в ответ Энди Т или yi_H ответ . Тем не менее, этот ответ решает проблему, представленную в вопросе.

Код, который вы предоставляете, будет выполняться до тех пор, пока не будет найден один ответ, и остановится, поскольку при нахождении первого ответа solved не будет равно 0. Поскольку вы знаете, что есть 2 решения, вы можете изменить условие цикла while:

while solved < 2:
    try1('123456789')

В ответ на комментарий Марка о том, что это может привести к дублированию ответов, приведем код, который обеспечит получение различных решений:

import random
def try1(param):
    global solved
    try1.prev_soln = []
    opers = ['+', '*', '']
    hotpotato = ('%s'.join(param) % (random.choice(opers),
                                     random.choice(opers),
                                     random.choice(opers),
                                     random.choice(opers),
                                     random.choice(opers),
                                     random.choice(opers),
                                     random.choice(opers),
                                     random.choice(opers),
                                     )
             )
    if eval(hotpotato) == 2002:
        if hotpotato not in try1.prev_soln:
            solved += 1
            try1.prev_soln.append(hotpotato)
            print "Solution:", hotpotato, "= 2002     :-)"    
    else:
        pass

solved = 0
while solved < 2:
    try1('123456789')

Конечно, этот подход предполагает 2 решения. Если бы у вас было неизвестное количество решений, вы бы не знали, когда остановиться, поэтому я рекомендую другой подход к поиску решений.