保龄球调度器

Question

我在做保龄球比赛的调度程序。我的问题是有些保龄球运动员共用一个私人保龄球。所以保龄球号码相同的保龄球手不可能在同一个回合。

我能编一本这样的字典：

dict = {1:None,2:1,3:None,4:None,5:None,6:1,7:2,8:2,9:3,10:None}

dict ={ bowler_id，shared_ball} (None =无共享球)

这是我的第一次尝试，它有问题：

from operator import itemgetter

bowlers = {1:None,2:1,3:None,4:None,5:None,6:1,7:2,8:2,9:3,10:None,11:None,12:None,13:None,14:None,15:None,16:1,17:None,18:None,19:None,20:None,21:2,22:3,23:None}
Lanes = 6
Rounds = 6
Schedule = {}

sortedlist = sorted(bowlers.items(), key=itemgetter(1), reverse=True)

for x in xrange(1,Lanes+1):
    Schedule[''.join(['Lane', str(x)])] = []

while len(sortedlist) > 0:
    z = zip(Schedule,sortedlist)
    for i in z:
        Schedule[i[0]].append((i[1][0] , i[1][1]))
        sortedlist.pop(0)
print Schedule 

我有以下问题/关切：

这种方法有相反的效果:因为我在一个排序列表上，同一个球的保龄球被放在同一个回合。

谁能给我指明正确的方向？

程序的输出是：

   {    
    'Lane6': [(9, 3), (6, 1), (10, None), (17, None)], 
    'Lane5': [(22, 3), (16, 1), (11, None), (18, None)], 
    'Lane4': [(7, 2), (1, None), (12, None), (19, None)], 
    'Lane3': [(8, 2), (3, None), (13, None), (20, None)], 
    'Lane2': [(21, 2), (4, None), (14, None), (23, None)], 
    'Lane1': [(2, 1), (5, None), (15, None)]
}

每一列都是所有车道上的拐弯处。当您查看第一列时，您会看到共享球3和2在一列中多出现一次。这是错误的，因为你不能有两个保龄球，同一个球在一个回合。

正确的输出应该如下所示：

{   
    'Lane6': [(10, None),   (9, 3),     (6, 1),     (17, None)], 
    'Lane5': [(22, 3),      (16, 1),    (11, None), (18, None)], 
    'Lane4': [(7, 2),       (1, None),  (12, None), (19, None)], 
    'Lane3': [(3, None),    (13, None), (8, 2),     (20, None)], 
    'Lane2': [(14, None),   (21, 2),    (4, None),  (23, None)], 
    'Lane1': [(2, 1),       (5, None),  (15, None)]
}

保龄球的顺序可能是随机的，只要a没有共同的球在一个回合。

Answer 1

谢谢你提出了一个非常有趣的挑战！

为了更有意义，我重新命名了一些标识符，并将ball None更改为ball 0，以使输出更加整洁。

这个程序根据他们使用的球来分组保龄球，然后从每一组中最多选择一个，再加上不使用共享球的保龄球的数量。

from copy import deepcopy
from random import shuffle
from json import dumps     # for pretty printing of results

bowlers2balls = {
    1:0,2:1,3:0,4:0,5:0,6:1,7:2,8:2,9:3,10:0,11:0,12:0,13:0,
    14:0,15:0,16:1,17:0,18:0,19:0,20:0,21:2,22:3,23:0
}

Lanes = 6
Schedule = {}
min_turns = (len(bowlers2balls) - 1) / Lanes + 1

# Create a list of lists. Bowlers with a shared ball are all in the
# same sublist. Each bowler without a shared ball gets their own
# sublist. Ball numbers do not appear here.

shared = [[tup[0] for tup in bowlers2balls.items() if tup[1] == ball]
          for ball in set(bowlers2balls.values()) if ball]
for grp in shared:
    shuffle(grp)
unshared = [[tup[0]] for tup in bowlers2balls.items() if not tup[1]]
full_bgroups = shared + unshared

# Generate random schedules until we get one with minimum turns. It
# often happens that we get a suboptimal one because the bowlers with
# shared balls aren't used up.

while True:
    for lane in xrange(1,Lanes+1):
        Schedule['Lane{}'.format(lane)] = []

    bgroups = deepcopy(full_bgroups)
    while bgroups:
        shuffle(bgroups)
        for i, lane in enumerate(Schedule.keys()):
            if i >= len(bgroups):
                break
            bowler = bgroups[i].pop()
            Schedule[lane].append(
                ('{:2d}'.format(bowler),
                 bowlers2balls[bowler]))
        # Remove emptied lists from bgroups
        bgroups = filter(None, bgroups)

    turns = max([len(s) for s in Schedule.values()])
    if turns <= min_turns:
        break

print (dumps(Schedule, sort_keys=True)
       .strip('{}')
       .replace(']], ', ']],\n'))