水の移し替えパズル in Python DouKaku?

A, B, Cの容器があり，それぞれ水が4L, 2L, 10L入っている．ここで次の操作を繰り返す．

(*)「A, B, Cのどれか二つの容器から水を1Lずつくみ上げ，残りの容器に移す．」

たとえばA, Bから1Lずつくみ上げて移せばA=3L, B=1L, C=12Lとなる．くみ上げる前の容器には必ず水が入っているとする．

(*)を繰り返してどれか一つの容器にのみ水がはいっている状態にする最小手数を求めよ．

可能ならA=827392L，B=65536L，C=122880Lのときも求めよ．

このお題は光成さんの投稿を元に作成しました。ご協力ありがとうございます。

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

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

ちなみに、[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])

スレッドを三つ同時に走らせて、一番速く帰ってきた奴を採用しているんですが、
処理時間が短すぎて、スレッドの終了チェック前にすべてのスレッドが終了しているようです。
そのため、一番目のスレッド（カップ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?

水の移し替えパズル

Posted feedbacks - Python

Index

Feed

Other

Link

Pathtraq