项目Euler 240:掷骰子的方式数量

Question

我正在尝试解决Project Euler问题240:

有多少种方式可以滚动20个12面骰子(编号为1到12的边),使前十个骰子总和达到70？

我想出了解决这个问题的代码.但是计算真的需要很多时间.我知道这种方法非常糟糕.有人可以建议我如何修复此代码以更好地执行？

import itertools
def check(a,b):   # check all the elements in a list a, are lesser than or equal to value b
    chk=0
    for x in a:
        if x<=b:
            chk=1
    return chk

lst=[]
count=0
for x in itertools.product(range(1,13),repeat=20):
    a=sorted([x[y] for y in range(20)])
    if sum(a[-10:])==70 and check(a[:10],min(a[-10:])):
        count+=1

下面的代码是针对问题描述中定义的问题.它完美地工作并提供精确的解决方案....

import itertools
def check(a,b):
     chk=1
     for x in a:
         if x>b:
             chk=0
             break
     return chk


count=0
for x in itertools.product(range(1,7),repeat=5):
    a=sorted([x[y] for y in range(5)])
    if sum(a[-3:])==15 and check(a[:2],min(a[-3:])):
        count+=1

Answer 1

对所有可能性进行迭代并不是很好,因为有²⁰种方式可以滚动20个十二面骰子,例如每秒一百万卷,这需要数百万年才能完成.

解决此类问题的方法是使用动态编程.找到一些方法将问题分解为几个较小问题的总和,并建立一个表格来解决这些子问题,直到您可以计算出所需的结果.

例如,设T(Ñ,d,ķ,吨)是方式滚动数Ñ d -sided骰子使得顶ķ它们的总和为吨.我们如何将其分解为子问题？好吧,我们可以考虑骰子的数量,即,d完全滚动.有^Ñ Ç _我的方式来选择这些我骰子,和T(Ñ  - 我,d - 1,...)的方式来选择Ñ  - 我必须滚动至多剩余骰子d 1(对于一些合适的选择- 我已经省略了k和t的参数.)

拿出这些产品,并总结一下i的所有合适值,你就完成了.(好吧,还没完成:你必须指定基本情况,但这应该很容易.)

您需要计算的子问题的数量将是至多(Ñ + 1)(d + 1)(ķ + 1)(吨 + 1),它在项目欧拉情况下(Ñ = 20,d = 12 ,ķ = 10,牛逼 = 70)至多213213.(在实践中,比这少得多,因为树到达基地的情况下许多部门迅速:我在执行原来的答案,只是791的子问题足以计算答案.)

要编写动态程序,通常最简单的方式是递归表达它并使用memoization来避免重新计算子问题的答案.在Python中你可以使用@functools.lru_cache装饰器.

所以程序的骨架看起来像这样.我已经取代了关键细节,???以免剥夺你为自己解决问题的乐趣.在尝试更大的案例之前,使用小例子(例如"两个6面骰子,其中前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))

通过适当的选择???,这可以在几毫秒内解决Project Euler问题:

>>> 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)

Answer 2

这个解决方案应该有效 - 不确定您的系统需要多长时间。

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)]

它所做的就是首先创建“前十名”。然后将可能的“下十个”项目的列表添加到每个“前十个”，其中最大值限制为“前十个”中的最小项目

results 是一个字典，其中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 分钟的时间内运行了前 100 万个结果。所以我确信它在可行的范围内。

祝你好运 ：）

更新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])

这是一个优雅的 1 行解决方案，并为问题提供了正确的答案，calc_ways1(5,6,3,15)但需要花费很长时间calc_ways1(20,12,10,70)。

不管怎样，数学似乎确实是解决这个问题的方法，而不是我愚蠢的想法。