Игра чисел отсчета (генератор решений)


Я пытаюсь запрограммировать решение генератор для отсчета игра чисел в Python, после некоторых указаний из DataGenetics -- тех, кто незнаком с правилами, вы можете ознакомиться с ними здесь, а также, но я написал код сам.

Код

def postfix_to_infix(postfix):
    """
    :param postfix: tuple containing solution in reverse polish notation
    :return: string of solution in polish notation
    """
    soln = list(postfix)
    while True:
        try:
            op_idx, op = [(idx, tkn) for idx, tkn in enumerate(soln) if tkn in ['+', '-', '*', '/']][0]
        except IndexError:
            break
        else:
            block = '(' + str(soln[op_idx - 2]) + op + str(soln[op_idx - 1]) + ')'
            soln[op_idx - 2:op_idx + 1] = [''.join(block)]
    return soln


def main():
    import random

    # Print welcome message
    print("""
    =====================================
    Welcome to Countdown, Python version!
    =====================================
    """)

    # *** <Start game> ***
    play_new_game = True
    while play_new_game:
        # Generate the set of possible numbers allowed by Countdown rules
        large_numbers = [25, 50, 75, 100]
        small_numbers = list(range(1, 11)) * 2

        # Generate six number tiles according to user input for large numbers
        while True:
            try:
                usr_large_num = int(input("How many LARGE numbers do you want (0-4)? "))
            except ValueError:
                pass
            else:
                if 0 <= usr_large_num <= 4:
                    break
        six_tiles = random.sample(large_numbers, usr_large_num) + \
                    random.sample(small_numbers, 6 - usr_large_num)

        # Generate random target output: any three-digit number
        target = random.randint(100, 999)

        print(six_tiles)
        print(f"Target: {target}")

        # Algorithm to find solution to target
        import itertools as it
        from more_itertools import distinct_permutations
        import operator

        ops_tiles = {"+": operator.add,
                     "-": operator.sub,
                     "*": operator.mul,
                     "/": operator.truediv}
        for nums in distinct_permutations(six_tiles):
            for ops in it.combinations_with_replacement(ops_tiles, 4):
                # Generate the list of postfix's (6 numbers + operators)
                # by permuting over all elements,
                # But removing those postfix's that begin with two operators
                postfix_gen = (pf for pf in distinct_permutations(nums + ops) if
                               pf[0] not in ops_tiles and pf[1] not in ops_tiles)
                for postfix in postfix_gen:
                    # Implement postfix algorithm
                    stack = list(postfix[0:2])
                    for idx, token in enumerate(postfix[2:], start=2):
                        # If token is an operator...
                        if token in ops_tiles:
                            # Take the last 2 tokens in the stack
                            try:
                                operand_2 = stack.pop()
                                operand_1 = stack.pop()
                            except IndexError:
                                break
                            # And operate on the 2 tokens
                            else:
                                # Capture ZeroDivisionError
                                try:
                                    result = ops_tiles[token](operand_1, operand_2)
                                except ZeroDivisionError:
                                    break
                                else:
                                    # Intermediate numbers can only be whole numbers
                                    if (result < 0) or (result != int(result)):
                                        break
                                    elif result == target:
                                        postfix = postfix[0:idx + 1]
                                        break
                                    else:
                                        stack.append(result)
                        # Else token is a number
                        else:
                            # Add number to the stack and await an operator
                            stack.append(token)
                    if result == target:
                        break
                else:
                    continue
                break
            else:
                continue
            break

        # Print results!
        if result != target:
            print("No solution found!")
        else:
            print(postfix)
            print(postfix_to_infix(postfix))

        # Play again?
        while True:
            try:
                print("Do you want to play again (y/n)?")
                play_again = input()[0]
            except IndexError:
                pass
            else:
                if play_again.lower() == 'n':
                    play_new_game = False
                    break
                elif play_again.lower() == 'y':
                    print("\n==========")
                    break


if __name__ == '__main__':
    main()

Краткое описание

Приведенный выше код выполняет следующие действия:

  1. Согласно правилам игры, игрок спрашивает, сколько "больших" чисел они хотят (от 0 до 4), а затем 6 цифры взял наугад (остальные - 'малый') и распечатать.
  2. Целевое число (случайное число от 100 до 999) печатается также.
  3. Он пытается найти выход с помощью грубой силы (перебора всех возможных комбинаций чисел и операторов, чтобы достигнуть целевого числа). Я использовать обратную польскую нотацию в моем решение-поисковый алгоритм.
  4. Печатать решение, если таковые имеются, и сделать так в (стандартный) польской нотацией. Преобразование из РПН к ПН осуществляется с помощью функции postfix_to_infix функция.

Примечания и вопросы

Просто для контекста: я относительно новый для Python и ООП в целом; у меня есть лучшее понимание функционального программирования. Я бы с удовольствием ценю обратную связь в отношении:

  • Как сделать код более эффективным? В настоящее время он занимает очень много времени, чтобы сообщить о данной комбинации имеет никакого решения. Примечание: это будет даже хуже, если я позволю дополнительные операторы в postfix выражение (>4). Таким образом, я не уверен на 100%, что этот код будет найти решения для всех возможных игр, но я могу только увеличить количество операторов один раз мой код работает более эффективно-в противном случае это приведет к затягиванию времени, чтобы найти решения не очень простых игр (например, 100, 25, 2, 4, 6, 8 с целью 650).
  • Есть действительно какие-то проверки эффективности предложенных в ссылке выше (на DataGenetics), что я не реализовать в моем коде, как я не слишком уверен (например, шаги, умножать и делить на 1 -- тратить ходы)
  • Можно ли реализовать для этого класса? Я не уверен, что объекты будут в этом случае. Я тоже готов выслушать, почему его не стоит реализовывать это в классе, если вы чувствовать себя таким образом (я подозреваю, что это тот случай).
  • Любые улучшения для postfix_to_infix функция и ее реализация в Python?

Спасибо!



902
7
задан 26 марта 2018 в 09:03 Источник Поделиться
Комментарии
3 ответа

Как и другие ответы сказать, разделить свои программы.

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

import operator
from itertools import permutations, combinations_with_replacement, product
DEFAULT_OPERATORS = {
"+": operator.add,
"-": operator.sub,
"*": operator.mul,
"/": operator.truediv,
}

Проверить, является ли последовательность действительных

Последовательность лексически если есть достаточно цифр, чтобы использовать в качестве операндов для операций. Это означает, что для любого места в последовательности, должно быть на 1 больше, чем оператор. Если вы представляете номером True и оператор как ложные, эта проверка может быть сделано так:

def is_valid(sequence):
count_nums = 0
for token in sequence:
if not token:
count_nums -= 1
if count_nums < 1:
return False
else:
count_nums +=1
return True


assert is_valid((True, True, False))
assert is_valid((True, True, False, True, True, False, False))
assert is_valid((True, True, False, True, False))
assert not is_valid((True, True, False, False))
assert not is_valid((True, False, True, False))
assert not is_valid((True, False))
assert not is_valid((False, True, True, False))

Генерировать последовательности

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

def valid_sequences(num_count):
base = (True,) * num_count + (False,) * (num_count - 1)
# print(base)
perms = distinct_permutations(base)
# perms = list(perms)
# print(f'possible permutations: {len(perms)}')
for sequence in perms:
# print(sequence)
if is_valid(sequence):
yield sequence


print(list(valid_sequences(2)))
print(list(valid_sequences(3)))
print(list(valid_sequences(4)))

[(True, True, False)]
[(True, True, True, False, False), (True, True, False, True, False)]
[(True, True, True, True, False, False, False), (True, True, True, False, True, False, False), (True, True, True, False, False, True, False), (True, True, False, True, True, False, False), (True, True, False, True, False, True, False)]

если вы посмотрите на дело 6 цифр и 5 операторов, есть 462 перестановок, но только 42 годные.

Заполнения последовательности

def distinct_ordered_combinations(iterable, r):
seen = set()
for combination in combinations_with_replacement(iterable, r):
for permutation in permutations(combination):
if permutation not in seen:
yield permutation
seen.add(permutation)

def generate_sequences(numbers, operators):
l = len(numbers)
for sequence in valid_sequences(l):
for nums, ops in product(
distinct_permutations(numbers),
distinct_ordered_combinations(operators, l - 1),
):
nums = iter(nums)
ops = iter(ops)
yield tuple(next(nums) if token else next(ops) for token in sequence)


list(generate_sequences((1, 2), operators=DEFAULT_OPERATORS))

[(1, 2, '+'),
(1, 2, '-'),
(1, 2, '*'),
(1, 2, '/'),
(2, 1, '+'),
(2, 1, '-'),
(2, 1, '*'),
(2, 1, '/')]


 list(generate_sequences((1, 2, 2), operators='+-'))

[(1, 2, 2, '+', '+'),
(1, 2, 2, '+', '-'),
(1, 2, 2, '-', '+'),
(1, 2, 2, '-', '-'),
(2, 1, 2, '+', '+'),
(2, 1, 2, '+', '-'),
(2, 1, 2, '-', '+'),
(2, 1, 2, '-', '-'),
(2, 2, 1, '+', '+'),
(2, 2, 1, '+', '-'),
(2, 2, 1, '-', '+'),
(2, 2, 1, '-', '-'),
(1, 2, '+', 2, '+'),
(1, 2, '+', 2, '-'),
(1, 2, '-', 2, '+'),
(1, 2, '-', 2, '-'),
(2, 1, '+', 2, '+'),
(2, 1, '+', 2, '-'),
(2, 1, '-', 2, '+'),
(2, 1, '-', 2, '-'),
(2, 2, '+', 1, '+'),
(2, 2, '+', 1, '-'),
(2, 2, '-', 1, '+'),
(2, 2, '-', 1, '-')]

Приятно то, что каждый из этих шагов может быть проверена и испытана, который не может быть сделано с помощью гигантского вложенный цикл for

Вычислить промежуточные итоги для последовательностей

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

class FalseOperation(ValueError):
pass
def calculate_sequence(sequence, operators):
# Implement postfix algorithm
stack = list(sequence[:2])
for idx, token in enumerate(sequence[2:], start=3):
if token not in operators:
stack.append(token)
continue
operand2 = stack.pop()
operand1 = stack.pop()
try:
result = operators[token](operand1, operand2)
except ZeroDivisionError:
raise FalseOperation('Division by zero')
if int(result) != result:
raise FalseOperation('non-int value')
if result < 0:
raise FalseOperation('negative value')
yield result, sequence[:idx]
stack.append(result)


list(calculate_sequence((7, 3, 2, 8, 50, '+', '-', 10, '*', '+', '-'), > DEFAULT_OPERATORS))

[(58, (7, 3, 2, 8, 50, '+')),
(56, (7, 3, 2, 8, 50, '+', '-')),
(560, (7, 3, 2, 8, 50, '+', '-', 10, '*')),
(563, (7, 3, 2, 8, 50, '+', '-', 10, '*', '+')),
(556, (7, 3, 2, 8, 50, '+', '-', 10, '*', '+', '-'))]

Тест последовательности

С другими методами делать тяжелую работу, это становится довольно тривиально. Все, что вам нужно сделать, это поставить цель, последовательность чисел, и сколько операторов необходимо смешать в

def test_sequences(target, numbers, operators):
for sequence in generate_sequences(numbers, operators):
try:
for result , seq in calculate_sequence(sequence, operators):
if result == target:
yield seq
except FalseOperation:
pass


list(test_sequences(56, (2, 8, 50), DEFAULT_OPERATORS))

[(2, 8, 50, '+', '-'),
(2, 50, 8, '+', '-'),
(8, 2, 50, '-', '+'),
(50, 2, 8, '-', '+'),
(2, 8, '-', 50, '+'),
(2, 50, '-', 8, '+')]

4
ответ дан 27 марта 2018 в 10:03 Источник Поделиться

Начнем с postfix_to_infix функция. Поскольку вы уже используете f-stringС в другом месте в коде, вы могли бы также использовать их здесь. Также обратите внимание, что ''.join(block), такой же, как и blockпотому что, это одна строка.

Вместо [...][0]вы можете просто использовать next(...), который создает только первое значение, а не весь список, только чтобы взять первый элемент. Единственное изменение, которое вам нужно, чтобы поймать StopIterationвместо IndexErrorв случае отсутствия оператора слева.

Я хотел бы использовать set для операторов, так что вы получаете \$\mathcal{О,} (1)\$ подстановки и задайте его только один раз а не на каждой итерации цикла.

soln не очень красивое имя. Либо это заклинание, как solution (это не так долго) или использовать имя, которое более ясно говорит о том, что это просто переменная, магазин выходной (возможно out?). То же самое верно для tkn. Я даже не имеют понятия, что это означает. Но вы можете повторно использовать имя это присваивается здесь op. Я бы также использовать универсальный iвместо op_idx, потому что это единственный показатель в этот метод и позволяет все линии, чтобы вписаться в 80 символов, рекомендованных PEP8, питона официальный стиль руководства.

def postfix_to_infix(postfix):
"""
:param postfix: tuple containing solution in reverse polish notation
:return: string of solution in polish notation
"""
operators = set('+-*/')
out = list(postfix)
while True:
try:
i, op = next((i, op) for i, op in enumerate(out) if op in operators)
except StopIteration:
break
else:
out[i - 2:i + 1] = [f"({out[i - 2]}{op}{out[i - 1]})"]
return out


Теперь для вашего main функция. Общая структура модуль Python должны быть следующие:

import somemodule
from someothermodule import something

GLOBAL_CONSTANT = None

class ClassName:
pass

def function():
pass

if __name__ == "__main__":
# Some code using all the above or a direct call to `main()`, if it exists
c = ClassName()
function()

Согласно этому, вы должны тянуть свой импорт из main функция.

Вы также должны разделить ваш код на более мелкие функции, так что вы можете повторно использовать их в других местах, если это необходимо. Главный кандидат на это функция, которая запрашивает у пользователя ввод, проверка его в то же время:

def ask_user(message, type_=str, allowed=None):
while True:
try:
usr_input = type_(input(message))
except ValueError:
print(f"Please enter a(n) '{type_.__name__}'")
else:
if allowed is not None and usr_input not in allowed:
print(f"Value must be in {allowed}")
continue
return usr_input

Эта функция может использоваться для обоих входов пользователей:

usr_large_num = ask_user("How many LARGE numbers do you want (0-4)? ", int, range(5))
play_new_game = ask_user("Do you want to play again (y/n)?", allowed="yYnN").lower() == "y"

Это имеет немного меньше функций, чем ваш код ("yes" больше не считается "y"небольшая цена, чтобы заплатить, хотя, ИМО).

6
ответ дан 27 марта 2018 в 07:03 Источник Поделиться

В main функция очень длинная: она, наверное, стоит по крайней мере вытаскивания решение процедуру поиска. Но помимо этого я не буду комментировать много на стиль, потому что я не Pythonista и другие могут сделать это лучше меня.


Как сделать код более эффективным?

Простой: не повторяйся. Здесь я не имею в виду копировать-вставить код, но для повторных расчетов. Сколько перестановок начинается num num op op код генерации и потом выкидывание с IndexError на втором op? Я делаю это почти пять миллионов.

Если цифры включают 2 и 3сколько перестановок начинается 2 3 + код генерации? Сколько начало 3 2 + Она производит? Сколько его нужно создать?

Таким образом, два ключа, чтобы сделать его более эффективным, чтобы построить стек последовательно таким образом, что вы только толкать оператора, когда есть хотя бы два числа на стеке; и использовать словарь или какой-нибудь подобный механизм определения выражения с одинаковыми номерами, и в тот же результирующий стек, так что только один из них сочетается как часть большего выражения. Один подход будет работать только с закрытыми выражения (т. е. те, которые дают стопку один номер) и только объединить их в порядке убывания (так вот чего мы хотим для деления и вычитания).

В качестве бонуса, это исправляет то, что ИМО это баг в оригинальной программе: обратный отсчет не требует все 6 чисел, которые будут использоваться.

5
ответ дан 27 марта 2018 в 08:03 Источник Поделиться