コーディング課題・5ℓと3ℓのバケツで4ℓの水を用意する問題
CodeIQの問題・パズルを考えよう!(by CodeIQ×はてな)
5リットルのバケツ(A)と3リットルのバケツ(B)だけ使って4リットルの水を測れと言われたら
- Aを満タンにする
- Aから注げるだけBに注いで、終わったらBの水は捨てる(Aに2リットルたまった)
- AからBに2リットルの水を移す
- Aを満タンにする
- AからBに注げるだけ注ぐと、Aに残るのは4リットル
これで最短手筋でしょうかね!?
はい、これを解くプログラムを書いてください。
問題は
バケツ容量はx, y(整数) 目標量はz(整数)
で与えられます。
許される操作は
- どちらかを満タンにする
- どちらかを空にする
- 一方から他方へ注げるだけ注ぐ
のどれかです。
問題に対する結果として、
- 手筋があるなら、操作を順序通りに返してください(操作を表現する形式はお任せします)。ただし最短のものです。
- 手筋がないなら、空の結果を返してください。
例題の(5,3,4)に対しては
A.full A.pour(B) B.empty A.pour(B) A.full A.pour(B)
という形の結果を出すということです。
応用問題
「なんのひねりもない*1幅優先探索じゃないの」と思った方、あなたは上位5%に入るエンジニアです。
そんなあなたに応用問題。
SQL SELECT文一本で解いてください。x,y,zにあたる数字は埋め込んでしまってかまいません。
*1:ひねっていないわけではなくて意地悪要素もあるんですがね。経路としてノード列でなくエッジ列を答えさせているところとか、解なし判定が必要なところとか。