Python Runtime Ошибка не работает должным образом - PullRequest
Новая
       32

Python Runtime Ошибка не работает должным образом

0 голосов
/ 21 июня 2019

У меня есть входной файл следующим образом 

3
01
0010100
11011

и вывод должен выглядеть следующим образом 

LIVES
DIES
LIVES

Однако мой код возвращает, 

DIES
[1, 0]
DIES
[0, 1, 0, 0, 0, 1, 0]
DIES
[1, 1, 0, 1, 1]

Я работаю с этой проблемой (https://open.kattis.com/problems/whowantstoliveforever). По сути, я смотрю на текущее значение битов в позициях i − 1 и i + 1 (если они существуют; в противном случае предположим, что они равны 0). Если мойпрограмма видит ровно 1, затем следующее значение i-го бита равно 1, в противном случае оно равно 0. Все биты меняются сразу, поэтому новые значения в следующем состоянии зависят только от значений в предыдущем состоянии.вселенная мертва, если она содержит только нули.

Я пытаюсь сказать, если программа перехватывает бесконечный цикл, который, вероятно, означает, что вселенная будет жить, 0 и 1 будут повторяться постоянно. И если len(set(x)) равно 1, тогда явозвращаю False. 

import sys


def get_bit(bits, i):
    if 0 <= i < len(bits):
        return int(bits[i])
    else:
        return 0


def print_result(boolean):
    print("LIVES" if boolean else "DIES")


def recursion(in_list, output_list):
    try:
        for index in range(len(in_list)):
            if (get_bit(in_list, index-1) == 0 and get_bit(in_list, index+1) == 0) or (get_bit(in_list, index-1) == 1 and get_bit(in_list, index+1) == 1):
                output_list.append(0)
            elif(get_bit(in_list, index-1) == 0 and get_bit(in_list, index+1) == 1) or (get_bit(in_list, index-1) == 1 and get_bit(in_list, index+1) == 0):
                output_list.append(1)
        if len(set(output_list)) == 1:
            return False
        else:
            in_list = output_list
            output_list = []
            recursion(in_list, output_list)
    except RuntimeError:
        return True


num_cases = int(sys.stdin.readline().strip())
for i in range(num_cases):
    _list = []
    case = sys.stdin.readline().strip()
    for char in case:
        _list.append(char)
    output_list = []
    print_result(recursion(_list, output_list))
    print(output_list)

Есть ли способ решить эту проблему, если не except RuntimeError не будет работать?

Ответы [ 2 ]

0 голосов
/ 21 июня 2019

Во-первых, @Blorgbeard прав, не делай этого.Это ужасный анти-паттерн.

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

recursion(in_list, output_list)

Если вселенная живет, то в какой-то момент это действительно выдает RuntimeError (точнее RecursionError) за превышение предела рекурсии (который не очень велик; в моей тестовой среде это было 2961, так что нене ожидайте, что это решит любые большие случаи правильно).Это означает, что какой-то экземпляр этого вызова вернет True.Однако это возвращаемое значение невидимо, и вмещающая функция завершает работу, ничего не возвращая, что означает, что она возвращает None.

Чтобы правильно поймать RecursionError, либо введите try - catchзаблокируйте рекурсивную функцию или передайте любое другое значение в стек следующим образом: 

return recursion(in_list, output_list)

Это дает правильное возвращаемое значение для небольших случаев, которые вы указали.

Что вы действительно должны сделать, тем не менее, это признать, что вы еще не знаете эффективного алгоритма для решения этой проблемы (постановка задачи допускает до 200000 символов в каждом входном случае).Поэтому вы должны распечатать все состояния, через которые проходит определенный ввод, и искать шаблоны.

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

0 голосов
/ 21 июня 2019

Использование предела рекурсии не является идеальным по нескольким причинам.Но в основном алгоритм «если он живет для X поколений, то, вероятно, живет вечно», в принципе не собирается сокращать его для более длительного ввода.

Вот скелет того, как я бы это реализовал: 

def get_new_state(old_state):
    pass # todo: implement

def is_dead(state):
    pass # todo: implement

def determine_fate(state):
    seen = set()       
    while True:
        if is_dead(state):
            return "DIES"
        if state in seen:
            return "LIVES"
        seen.add(state)
        state = get_new_state(state)

Я использую набор для запоминания старых состояний.Если мы когда-либо видим состояние более одного раза, то мы попадаем в цикл или устойчивое состояние, поэтому мы знаем, что результатом является «ЖИЗНЬ».Если этого не произойдет до того, как мы достигнем пустого состояния, то мы знаем, что результатом является «DIES».

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

...