Project Euler 240: количество способов бросить кости

Бесполезно перебирать все варианты, потому что существует 12²⁰ = 3833759992447475122176 способов бросить 20 двенадцатигранных игральных костей, и, скажем, при миллионе бросков в секунду на это уйдут миллионы лет. .

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

Например, пусть T(n, d, k, t) — количество способов бросить < em>n d-гранных игральных костей, так что сумма верхних k из них равна t. Как мы можем разделить это на подзадачи? Что ж, мы могли бы посчитать количество игральных костей, i, которые точно бросают d. Существует ⁿC_i способов выбрать эти i кубики, и T( n – i, d – 1, ...) способов выбора n – i оставшиеся кости, которые должны выбросить не более d − 1. (Для некоторого подходящего выбора параметров для k и t, которые я опустился.)

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

Количество подзадач, которые вам нужно вычислить, будет не более (n + 1)(d + 1)(k + 1 )(t + 1), что в случае проекта Эйлера (n = 20, d = 12, k = 10, t = 70) не превышает 213213. (На практике гораздо меньше, потому что многие ветви дерева быстро достигают базовых случаев: в моей реализации получается, что ответы всего 791 подзадачи достаточно для вычисления ответа.)

Чтобы написать динамическую программу, обычно проще всего выразить ее рекурсивно и использовать запоминание, чтобы избежать повторного использования. вычисление ответа на подзадачи. В Python вы можете использовать @functools.lru_cache декоратор.

Таким образом, скелет вашей программы может выглядеть так. Я заменил важные детали на ???, чтобы не лишать вас удовольствия разобраться самостоятельно. Поработайте с небольшими примерами (например, «два шестигранных кубика, 1 из которых в сумме дает 6»), чтобы убедиться, что ваша логика верна, прежде чем приступать к более крупным случаям.

def combinations(n, k):
    """Return C(n, k), the number of combinations of k out of n."""
    c = 1
    k = min(k, n - k)
    for i in range(1, k + 1):
        c *= (n - k + i)
        c //= i
    return c

@lru_cache(maxsize=None)
def T(n, d, k, t):
    """Return the number of ways n distinguishable d-sided dice can be
    rolled so that the top k dice sum to t.

    """
    # Base cases
    if ???: return 1
    if ???: return 0

    # Divide and conquer. Let N be the maximum number of dice that
    # can roll exactly d.
    N = ???
    return sum(combinations(n, i)
               * T(n - i, d - 1, ???)
               for i in range(N + 1))

При соответствующем выборе для всех ??? это решает задачу проекта Эйлера за несколько миллисекунд:

>>> from timeit import timeit
>>> timeit(lambda:T(20, 12, 10, 70), number=1)
0.008017531014047563
>>> T.cache_info()
CacheInfo(hits=1844, misses=791, maxsize=None, currsize=791)

это решение должно работать - не уверен, сколько времени это займет в вашей системе.

from itertools import product

lg = (p for p in product(xrange(1,13,1),repeat=10) if sum(p) == 70)

results = {}
for l in lg:
    results[l] = [p for p in product(xrange(1,min(l),1),repeat=10)]

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

результаты - это словарь, где key - это "десятка лучших", а значение - список возможных "следующих десяти"

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

count = 0
for k, v in results.items():    
    count += len(v)

и тогда count будет результатом.

обновить

Хорошо, я подумал о немного лучшем способе сделать это.

from itertools import product
import math

def calc_ways(dice, sides, top, total):
    top_dice = (p for p in product(xrange(1,sides+1,1),repeat=top) if sum(p) == total)
    n_count = dict((n, math.pow(n, dice-top)) for n in xrange(1,sides+1,1))

    count = 0
    for l in top_dice:
        count += n_count[min(l)]

    return count

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

удачи :)

обновление 2

после очередного вашего комментария я понял, что делаю не так, и попытался это исправить.

from itertools import product, combinations_with_replacement, permutations
import math

def calc_ways(dice, sides, top, total):
    top_dice = (p for p in product(xrange(1,sides+1,1),repeat=top) if sum(p) == total)
    n_dice = dice-top
    n_sets = len(set([p for p in permutations(range(n_dice)+['x']*top)]))
    n_count = dict((n, n_sets*len([p for p in combinations_with_replacement(range(1,n+1,1),n_dice)])) for n in xrange(1,sides+1,1))

    count = 0
    for l in top_dice:
        count += n_count[min(l)]

    return count

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

def calc_ways1(dice, sides, top, total):
    return len([p for p in product(xrange(1,sides+1,1),repeat=dice) if sum(sorted(p)[-top:]) == total])

которое представляет собой элегантное однострочное решение и дает правильный ответ для calc_ways1(5,6,3,15), но требует вечности для проблемы calc_ways1(20,12,10,70).

в любом случае, математика, похоже, подходит для этого, а не мои глупые идеи.