水の移し替えパズル
Posted feedbacks - Arc
その必要はないと知りつつも、律儀に水を移し替える実装にしてみました。 問題が解決できない(水量の差が 3 の倍数である容器の組が存在しない)場合は nil を返して終了します。 実行例: arc> (mizu '(4 2 10)) 10 arc> (mizu '(827392 65536 122880)) 827392 arc> (mizu '(5 7 9)) nil 水が移動する様を見たい方は 9 行目の (prn w) をアンコメントしてください。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | (def mizu (waters)
(let index (indexing waters)
(if (is index nil) nil
(with (lcr '((2 -1 -1) (-1 2 -1) (-1 -1 2))
n1 (index 0)
n2 (index 1)
aw (index 2))
((rfn lp (w step)
; (prn w)
(if (is (w n1) (w n2) 0) step
(is (w n1) 0) (lp (map + (lcr n1) w) (+ step 1))
(< (w aw) (/ (- (w n2) (w n1)) 3)) (lp (map + (lcr aw) w) (+ step 1))
(isnt (w n2) (w n1)) (lp (map + (lcr n1) w) (+ step 1))
(lp (map + (lcr aw) w) (+ step 1))))
waters 0)))))
(def indexing (ls)
(withs (mm (map [pos _ ls] (sort < ls))
min (ls (mm 0))
mid (ls (mm 1))
max (ls (mm 2)))
(if (is 0 (mod (- mid min) 3)) (list (mm 0) (mm 1) (mm 2))
(is 0 (mod (- max min) 3)) (list (mm 0) (mm 2) (mm 1))
(is 0 (mod (- max mid) 3)) (list (mm 1) (mm 2) (mm 0))
nil)))
|
にしお
#3547()
Rating0/2=0.00
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のときも求めよ．
このお題は光成さんの投稿を元に作成しました。ご協力ありがとうございます。
[ reply ]