Auto Painting (Ice Base) - アイテムの塗装

さて、いよいよ最後の島となった。全問クリアまであと少しがんばろー。
（このIce Baseをクリアしても、No Stationの問題があるけども。）

どんな問題？

Auto Painting
http://www.checkio.org/mission/auto-painting/

同時に K個のアイテムを塗ることができるペイント器具がある。各アイテムは2回ずつ塗らなくてはならない。このとき、N個のアイテムを塗り終わるための最短の手順を求めよ。（同じアイテムは3度以上塗ってはいけない。）

引数は、ペイント器具が同時に塗ることができる数(K)と、塗るべきアイテムの数(N)が渡される。K,Nともに10以下の整数。
戻り値は、何番のアイテムを器具に載せるかの手順をコンマ区切りの文字列で返す。アイテムは、0から9までの番号が付いている。

例題：

checkio(2, 3)  # "01,12,02"
checkio(6, 3)  # "012,012"
checkio(3, 6)  # "012,012,345,345"
checkio(1, 4)  # "0,0,1,1,2,2,3,3"
checkio(2, 5)  # "01,01,23,42,34"

どうやって解く？

各アイテムにA,Bの両面があると考えてみる。アイテム毎に {'A', 'B'} というsetを用意して、塗り終わった面は削除していくようにしてみた。
適当に取り出すと、最短手順にならないので、塗り残した面が多い順にソートしておくようにした。

def checkio(capacity, number):
    items = [[str(n), {'A', 'B'}] for n in range(number)]
    operations = []
    while items:
        operation = ''
        for n, sides in items[:capacity]:  # capacity個のアイテムを取り出し
            sides.pop()  # 塗った面を削除
            operation += n
        operations.append(operation)
        # 塗り残しが多い順にソート（塗り終わったアイテムは除去）
        items = sorted([i for i in items if i[1]], key=lambda i: len(i[1]), reverse=True)
    return ','.join(operations)

わざわざ、{'A', 'B'} としなくても、もっと簡単に、塗り残しの数をintで持っておけばいいか。書き直してみた。

def checkio(capacity, number):
    items = [[str(n), 2] for n in range(number)]  # list of [number, unpainted count]
    operations = []
    while items:
        operation = ''
        for item in items[:capacity]:
            item[1] -= 1
            operation += item[0]
        operations.append(operation)
        items = sorted([i for i in items if i[1] > 0], key=lambda i: i[1], reverse=True)
    return ','.join(operations)

http://www.checkio.org/mission/auto-painting/publications/natsuki/python-3/first/

他の人の答え

def checkio(capacity, number):
    sides = string.digits[:number] * 2
    step = min(capacity, number)
    return ','.join([sides[i:i+step] for i in range(0, len(sides), step)])

http://www.checkio.org/mission/auto-painting/publications/bunnychai/python-27/auto-painting/

K=2、N=3 なら、'012012'としておいて、前から2文字ずつ区切れば、'01,20,12'となる。なんて簡単。