DouKaku? 3550 ところてん: あってるか自信なし。愚直な方法でやっ...(水の移し替えパズル)

Comment detail

あってるか自信なし。
愚直な方法でやっています。

どこのカップに水を入れるかで、無限ループするケースがあるので、
並列にまわして、一番初めに答えを出したやつを帰すというクソ仕様。

ちなみに、[3,1,12]は12回
[827392,65536,122880]は、827392回
が最小(?)手数でした。

import copy
import threading
import time

class calcThread(threading.Thread):
    def __init__(self, cups, result):
        self.cups = cups
        self.result = result
        threading.Thread.__init__(self)
    def run(self):
        count = 0
        cups = self.cups
        while(cups[1]!=0 or cups[2] !=0):
            count+=1

            if cups[1] and cups[2] :
                cups[0] += 2
                cups[1] -= 1
                cups[2] -= 1
                continue

            if cups[1] == 0:
                cups[1] += 2
                cups[0] -= 1
                cups[2] -= 1
                continue

            if cups[2] == 0:
                cups[2] += 2
                cups[0] -= 1
                cups[1] -= 1
                continue
        self.result[0] = count

def water_move(cups):
    count = [[0],[0],[0]]
    threadholder = []
    for x in xrange(3):
        c = copy.copy(cups)
        c[0], c[x] = c[x], c[0]
        threadholder.append(calcThread(c, count[x]))
        threadholder[-1].setDaemon(True)
        threadholder[-1].start()

    while (1):
        for x in range(3):
            if not threadholder[x].isAlive():
                return count[x][0]
        

#print water_move([3,1,12])
print water_move([827392,65536,122880])

ちなみに、[3,1,12]は12回
↑答えのペアはあってるんですが要求されてる答えとは違いますね。
[4,2,10]はｂに水を集めて、10回でした。

water_move([1,1,4]) で 4 が返ってきません？

スレッドを三つ同時に走らせて、一番速く帰ってきた奴を採用しているんですが、
処理時間が短すぎて、スレッドの終了チェック前にすべてのスレッドが終了しているようです。
そのため、一番目のスレッド（カップaに水を集める）の答えが採用されてしまっているようです。

45行目から下のコードにすることで、1がちゃんと帰ってきます。

一番乗り目指して愚直にやったのが、仇になったなぁ。

    time.sleep(0.1)
    result = []
    while (1):
        for x in range(3):
            if not threadholder[x].isAlive():
                result.append(count[x][0])
        if len(result) :
            break
    return min(result)

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq