python - 计算飞镖分数结帐python的最短路径

Question

我想创建一个 python 文件，它返回给定某个 dart 分数的所有最短路径。需要注意的是，最后一次飞镖投掷应该是双靶心或双靶心（50）。

这是我到目前为止得到的

import re


SCORES = ['DB','SB','T20','T19','T18','T17','T16','T15','T14','T13','T12','T11','T10',
          'T9','T8','T7','T6','T5','T4','T3','T2','D20','D19','D18','D17','D18','D17',
          'D16','D15','D14','D13','D12','D11','D10','D9','D8','D7','D6','D5','D4','D3',
          'D2','S20','S19','S18','S17','S16','S15','S14','S13','S12','S11','S10','S9',
          'S8','S7','S6','S5','S4','S3','S2']


def caculate_numerical_score(score: str) -> int:
   if score == 'DB':
      return 50
   elif score == 'SB':
      return 25
   elif score.startswith('T'):
      return 3 * int(re.findall('\d+', score)[0])
   elif score.startswith('D'):
      return 2 * int(re.findall('\d+', score)[0])
   else:
      return int(re.findall('\d+', score)[0])

上面的代码将所有可能的飞镖结果转换为实际的数字分数。现在我需要遍历这些分数并检查哪些组合导致的投掷次数最少。我得到了以下不完整的代码，需要一些帮助......

def calculate_checkout(to_score: int):
   paths = []
   left_to_score = to_score
   throw = 1

   while left_to_score > 0:
      # throw
      paths[throw] = #  loop  over scores
      throw += 1
      left_to_score = to_score - sum(paths)
      if left_to_score % 2 and left_to_score <= 40 and left_to_score != 0:
         print(f'throw double and game is finished')
         paths[throw] = left_to_score / 2
         print(paths)

9 镖是飞镖中的圣杯。在这种情况下，您只使用 9 个飞镖，尽可能少地从 501 签出。因此，如果我们使用 501 as to to_score，代码应显示以下（部分）输出

['T20','T20'.'T20','T20','T20','T20','T20','T19','D12']

这是可归类为 9 镖的 3944条路径之一。非常感谢您的帮助。

标签： python

Answer 1

我使用python-mip将其作为一个整数程序进行了尝试，它确实产生了解决方案。不幸的是，默认情况下它只能找到一个解决方案 - 它需要一些强制来生成多个溶胶。

在此之前，我从字面上知道零飞镖规则。我不知道如何阅读您链接的那张图片。因此，几乎可以肯定，我在几分钟的谷歌搜索中没有发现一些需要纳入的规则。

pip install mip对于优化库。

import re
import mip
from pprint import pprint

SCORES = ['DB','SB','T20','T19','T18','T17','T16','T15','T14','T13','T12','T11','T10',
          'T9','T8','T7','T6','T5','T4','T3','T2','D20','D19','D18','D17','D18','D17',
          'D16','D15','D14','D13','D12','D11','D10','D9','D8','D7','D6','D5','D4','D3',
          'D2','S20','S19','S18','S17','S16','S15','S14','S13','S12','S11','S10','S9',
          'S8','S7','S6','S5','S4','S3','S2']


def caculate_numerical_score(score: str) -> int:
   if score == 'DB':
      return 50
   elif score == 'SB':
      return 25
   elif score.startswith('T'):
      return 3 * int(re.findall('\d+', score)[0])
   elif score.startswith('D'):
      return 2 * int(re.findall('\d+', score)[0])
   else:
      return int(re.findall('\d+', score)[0])


def main():
    score_to_value = {score: caculate_numerical_score(score) for score in SCORES}
    uq_values = list(set(score_to_value.values()))  # unique values of all scores

    value_to_scores = {value: set() for value in uq_values}
    for score, value in score_to_value.items():
        value_to_scores[value].add(score)

    # pprint(value_to_scores)
    for nthrows in range(9, 12):
        print(f"Solving for {nthrows} throws")
        m = mip.Model()

        # 2D array, where each row represents one throw.
        # The 1/0 values correspond to which value in the the ``uq_values``
        # array is associated with the throw.
        throws = [
            [m.add_var(var_type=mip.BINARY) for _ in uq_values]
            for _ in range(nthrows)
        ]

        # Each throw must have exactly one associated value.
        for throw in throws:
            m += mip.xsum(throw) == 1

        # Linear expression of the value (score) for each throw, for later use.
        linexpr_scores = [
            mip.xsum([value * b for value, b in zip(uq_values, throw)])
            for throw in throws
        ]

        # The last throw must have a score of less than 40
        m += linexpr_scores[-1] <= 40

        # The last throw's value must be an integer multiple of 2.
        # So, force throw to zero if that's not the case.
        for i, value in enumerate(uq_values):
            if value % 2 != 0:
                m += throws[-1][i] == 0

        # The sum of all throw scores must be 501
        m += mip.xsum(linexpr_scores) == 501

        m.verbose = False
        m.max_solutions = 100
        status = m.optimize(max_seconds=10)
        if status != mip.OptimizationStatus.OPTIMAL:
            print(f"optimisation status {status}")
            continue
        print(f"{status.name}, found {m.num_solutions} solutions")

        # Pull out solution 1/0 values
        throws_sol = [[float(x.x) for x in throw] for throw in throws]
        # Pull out the selected value index for each throw
        throws_idx = [
            [i for i, v in enumerate(throw_sol) if v > 1e-3][0]
            for throw_sol in throws_sol
        ]
        # Convert selected value index to a value for each throw.
        throws_val = [uq_values[throw_idx] for throw_idx in throws_idx]
        # Convert the throw values to scores
        throws_scores = [value_to_scores[throw_val] for throw_val in throws_val]
        print(throws_scores)

        # TODO: coerce program into generating more solutions (hmu)

if __name__ == '__main__':
    main()

Solving for 9 throws
OPTIMAL, found 1 solutions
[{'T20'}, {'T20'}, {'T20'}, {'T20'}, {'T18'}, {'T19'}, {'T20'}, {'T20'}, {'D15', 'T10'}]
Solving for 10 throws
OPTIMAL, found 1 solutions
[{'DB'}, {'T20'}, {'T20'}, {'T20'}, {'T20'}, {'T13'}, {'DB'}, {'T20'}, {'T20'}, {'S2'}]
Solving for 11 throws
OPTIMAL, found 1 solutions
[{'T20'}, {'D17'}, {'T17'}, {'T20'}, {'T20'}, {'T11'}, {'T13'}, {'T17'}, {'T19'}, {'S20', 'D10'}, {'T12', 'D18'}]