Кости код решение вареньем прям


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

from operator import itemgetter
from itertools import groupby    


def get_straight(chunk: list, idx: int, straight: int, dice: set) -> int:
    """Get max straight starting at index idx."""
    if idx == len(chunk) - 1:
        return straight

    item = chunk[idx]

    return max((get_straight(chunk, idx+1, straight+1, dice-{x})
                for x in item[1] if x in dice), default=straight)


def main():
    T = int(input())

    for i in range(T):
        ndice = int(input())
        integers = []

        for j in range(ndice):
            integers.extend((int(x), j) for x in input().split())

        integers.sort(key=itemgetter(0))

        grouped = [(k, [x[1] for x in g])
                   for k, g in groupby(integers, itemgetter(0))]
        chunks = []

        # find runs of consecutive numbers
        for k, g in groupby(enumerate(grouped), lambda x: x[0]-x[1][0]):
            g = list(g)
            if len(g) > 1:
                chunks.append(list(map(itemgetter(1), g)))

        chunks.sort(key=len, reverse=True)

        max_straight = 1

        for chunk in chunks:
            if len(chunk) <= max_straight:
                break

            for k in range(len(chunk)-1):
                if len(chunk) - k < max_straight:
                    break
                dice = set(range(ndice))
                straight = get_straight(chunk, k, 0, dice)
                if straight > max_straight:
                    max_straight = straight

        print("Case #{}: {}".format(i+1, max_straight))

main()


Комментарии
1 ответ

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

Организации код

Ваш призыв к main могли быть перемещены за if __name__ == "__main__": охранник в случае, если вы когда-либо хотите использовать get_straight(). Это могут быть не актуальны в вашем случае, но это хорошая привычка брать.

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

Поступая таким образом, вы бы также отдельные проблемы моего кода вычисления результатов нужно не перепутали с логика обработки ввода/вывода.

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

from operator import itemgetter
from itertools import groupby

def get_straight(chunk: list, idx: int, straight: int, dice: set) -> int:
"""Get max straight starting at index idx."""
if idx == len(chunk) - 1:
return straight

item = chunk[idx]

return max((get_straight(chunk, idx+1, straight+1, dice-{x})
for x in item[1] if x in dice), default=straight)

def longest_straight_length(dices):
"""Return the length of the longest possible straight using `dices`."""
integers = []
for j, dice in enumerate(dices):
integers.extend((val, j) for val in dice)
integers.sort(key=itemgetter(0))

grouped = [(k, [x[1] for x in g])
for k, g in groupby(integers, itemgetter(0))]
chunks = []

# find runs of consecutive numbers
for k, g in groupby(enumerate(grouped), lambda x: x[0]-x[1][0]):
g = list(g)
if len(g) > 1:
chunks.append(list(map(itemgetter(1), g)))

chunks.sort(key=len, reverse=True)

max_straight = 1

for chunk in chunks:
if len(chunk) <= max_straight:
break

for k in range(len(chunk)-1):
if len(chunk) - k < max_straight:
break
dice = set(range(len(dices)))
straight = get_straight(chunk, k, 0, dice)
if straight > max_straight:
max_straight = straight
return max_straight

def interactive():
for i in range(int(input())):
ndice = int(input())
dices = [[int(x) for x in input().split()] for _ in range(ndice)]
print("Case #{}: {}".format(i+1, longest_straight_length(dices)))

def unit_tests():
test_cases = [
([[4, 8, 15, 16, 23, 42],
[8, 6, 7, 5, 30, 9],
[1, 2, 3, 4, 55, 6],
[2, 10, 18, 36, 54, 86]],
4),
([[1, 2, 3, 4, 5, 6],
[60, 50, 40, 30, 20, 10]],
1),
([[1, 2, 3, 4, 5, 6],
[1, 2, 3, 4, 5, 6],
[1, 4, 2, 6, 5, 3]],
3)
]
for dices, expected_result in test_cases:
actual_result = longest_straight_length(dices)
if actual_result != expected_result:
print(expected_result, actual_result, dices)

if __name__ == "__main__":
if True:
unit_tests()
else:
interactive()

Переписывание логики

Начало логики создания чанков может быть переписан с использованием словаря, а не выполнения groupby и хитрый индекс доступов. (В конце концов, я заново строить структуры данных вы используете, чтобы быть в состоянии держать кода, который вы написали). Мы хотели сделать что-то вроде:

def longest_straight_length(dices):
"""Return the length of the longest possible straight using `dices`."""
# Mapping value to list of dice indices
number_on_dices = dict()
for i, dice in enumerate(dices):
for val in dice:
number_on_dices.setdefault(val, []).append(i)

# Consecutive chunks
chunks = []
for k, g in groupby(enumerate(sorted(number_on_dices.keys())), lambda x: x[0] - x[1]):
g = list(g)
if len(g) > 1:
chunk = [y for (_, y) in g]
chunks.append(chunk)
chunks.sort(key=len, reverse=True)

# Re-add values to be reuse existing logic for the time being
chunks = [[(val, number_on_dices[val]) for val in chunk] for chunk in chunks]

max_straight = 1

for chunk in chunks:
if len(chunk) <= max_straight:
break

for k in range(len(chunk)-1):
if len(chunk) - k < max_straight:
break
dice = set(range(len(dices)))
straight = get_straight(chunk, k, 0, dice)
if straight > max_straight:
max_straight = straight
return max_straight

Тогда, кажется, понятно, что первый элемент пары из chunks никогда не используются.
Мы можем просто иметь:

chunks = [[number_on_dices[val] for val in chunk] for chunk in chunks]

и в get_straight:

return max((get_straight(chunk, idx+1, straight+1, dice-{x})
for x in item if x in dice), default=straight)

В конечном счете, мы можем упростить код здания chunks:

# Consecutive chunks
chunks = []
for k, g in groupby(enumerate(sorted(number_on_dices.keys())), lambda x: x[0] - x[1]):
g = list(g)
if len(g) > 1:
chunk = [number_on_dices[y] for (_, y) in g]
chunks.append(chunk)
chunks.sort(key=len, reverse=True)

Однако затратная часть все еще здесь, в рекурсивных вызовов get_straight. (Я не нашел хитрость для этого, но нынешний вариант Кодекса можно ознакомиться здесь: http://termbin.com/yg5l ).

Ошибка ?

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

    ([[1, 2, 3, 4, 5, 6],
[7, 2, 3, 4, 5, 6],
[7, 8, 3, 4, 5, 6],
[7, 8, 9, 4, 5, 6],
[7, 8, 9,10, 5, 6],
[7, 8, 9,10,11, 6],
[7, 8, 9,10,11,12]],
7),
([[1, 1, 1, 1, 1, 1],
[2, 2, 2, 2, 2, 2],
[3, 3, 3, 3, 3, 3],
[4, 4, 4, 4, 4, 4],
[5, 5, 5, 5, 5, 5],
[6, 6, 6, 6, 6, 6],
[7, 7, 7, 7, 7, 7]],
7),

В обоих случаях, мы могли бы генерировать последовательности [1, 2, 3, 4, 5, 6, 7] длины 7. Однако, код, возвращаемый 6. Если вы хотите пойти дальше из этой части кода с помощью дополнительных тестов и показателей деятельности можно ознакомиться здесь: http://termbin.com/c690 .

2
ответ дан 15 апреля 2018 в 06:04 Источник Поделиться