计算省道得分的最短路径签出python

Question

我想要创建一个python文件，该文件返回所有给定省道分数的最短路径。重要的是要注意的是，最后的飞镖投掷应该是双或双多头眼(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作为to_score，代码应该显示以下(部分)输出

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

这是3944个路径中的一个，它可以被归类为9通道.我们非常感谢你的帮助。

Answer 1

我尝试了一个整数程序，使用python，它确实产生了解决方案。不幸的是，在默认情况下，它只找到一个解决方案--它需要一点强制才能生成多个sols。

在此之前，我确实知道零飞镖规则。我不知道怎么看你链接的那张照片。因此，几乎可以肯定的是，我在谷歌上花了几分钟的时间就没有学到一些需要合并的规则。

优化库的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'}]

Answer 2

我知道已经有答案了，但是这里有一个扩展版本(用于3种或更少的省道签出)，它打印所有可能的解决方案(不包括那些可以翻转省道顺序的解决方案，比如从22开始完成签出) (d2、d4、d5) (并不是最优的)，订单也不重要。

import itertools

fields = {"S1": 1, "S2": 2, "S3": 3, "S4": 4, "S5": 5, "S6": 6, "S7": 7, "S8": 8, "S9": 9, "S10": 10, "S11": 11,
          "S12": 12, "S13": 13, "S14": 14, "S15": 15, "S16": 16, "S17": 17, "S18": 18, "S19": 19, "S20": 20, "S25": 25,
          "D1": 2, "D2": 4, "D3": 6, "D4": 8, "D5": 10, "D6": 12, "D7": 14, "D8": 16, "D9": 18, "D10": 20, "D11": 22,
          "D12": 24, "D13": 26, "D14": 28, "D15": 30, "D16": 32, "D17": 34, "D18": 36, "D19": 38, "D20": 40, "D25": 50,
          "T1": 3, "T2": 6, "T3": 9, "T4": 12, "T5": 15, "T6": 18, "T7": 21, "T8": 24, "T9": 27, "T10": 30, "T11": 33,
          "T12": 36, "T13": 39, "T14": 42, "T15": 45, "T16": 48, "T17": 51, "T18": 54, "T19": 57, "T20": 60}


def get_checkouts(points_remain: int) -> list:
    outs = []

    for field in fields:
        if fields[field] == points_remain:
            outs.append((field,))
    for seq in itertools.product(fields, repeat=2):
        val = [fields[i] for i in seq]
        if sum(val) == points_remain:
            outs.append(seq)
    for seq in itertools.product(fields, repeat=3):
        val = [fields[i] for i in seq]
        if sum(val) == points_remain:
            outs.append(seq)

    outs = [tuple(sorted(seq, reverse=True)) for seq in outs]
    outs = [out for out in set(outs) if "D" in out[-1]]

    return outs


checkout = get_checkouts(8)

print(checkout)