2つのバケツ問題
こんにちは、今日はプログラミングのことについて最近やっていることをお話します。
アルゴリズムについてなのかな？ ある問題を解いていました。
問題「５ℓはいるバケツと３ℓはいるバケツがあります。これらに水を注いだり移し替えたりして、４ℓの水を図ってください。」
ただ、この内容だけでしたら、
①５ℓのバケツをいっぱいにする。
②３ℓに水を移す
→この時点で５ℓのバケツに２ℓ水が入っている
③３ℓのバケツを空にする。
④５ℓのバケツの中身を３ℓのバケツに移す
→この時点で３ℓのバケツに２ℓ水が入っている
⑤５ℓのバケツをいっぱいにする。
⑥３リットルのバケツにできるだけ移し替える
→ここで３ℓのバケツは空きが１ℓのため、５ℓのバケツに４ℓの水が残る。
完成！
というわけですが、今回はこの手順を導出するプログラム（導出可能かどうかも判定する）を書いてみようということで昨日から少し考えていました。
Twitterなどでいろいろな方から事前知識をいただいていたので、その影響が強いですが考えとしては、、、
・５ℓはいるバケツ→バケツA
・３ℓはいるバケツ→バケツB
とすると、動作の取り方は、
・バケツAをいっぱいにする。
・バケツAを空にする。
・バケツAの中身をバケツBに移す。
・バケツBをいっぱいにする。
・バケツBを空にする。
・バケツBの中身をバケツAに移す。
の六通りとあらわすことができるわけです。 一番初めは両方共のバケツが空なのでこれがスタートです。
プログラムではとりあえず、順々に手順を試行してチェック→条件確認
といったところでしょうか。
はじめの状態を根として、手順を全通り試行して掘り下げていき試行を繰り返します。
構造としては木構造ですね。
ただ、言っといてよく知らないんだなこれが、、
木構造の探索法に関しては調べてみると深さ優先探索と幅優先探索とあるらしいです。
今回は深さが無限に増加していくことと、最短手順を調べるということなので幅優先で行きましょう。（分かってないです，エッヘン
こんな感じで、階層の上のほうから順に探索を進めていきます。（たぶん
正直、探索法知ったの昨日でよくわかってないのでセオリーとかわかんないですし、かなり非効率な気もしますが、せっかくコード書いたので載せようと思います。（５ℓのカップでかくね？とか英語おかしいとかはやめて＞＜ 分かってるから・・・orz
//--Cup関数（バケツのつもり（汗）-----//
package com.abs104a.cuptest.data;
public class Cup {
//現在のカップに入っている量
private final int now;
//このカップの最大容量
final private int capacity;
/**
* インスタンス生成，カップの最大容量を決定する
* @param capacity カップの最大容量
*/
public Cup(int capacity){
this.capacity = capacity;
now = 0;
}
/**
* インスタンス生成，内部用データ再生成
* @param now カップの現在の容量
* @param capacity カップの最大容量
*/
private Cup(int now,int capacity){
this.now = now;
this.capacity = capacity;
}
/**
* 現在の容量を返す
* @return
*/
public int getNow(){
return now;
}
/**
* このカップを満タンにする
* @return 現在の容量
*/
public Cup full(){
return new Cup(capacity,capacity);
}
/**
* 自分のカップをからにする
* @return ゼロ
*/
public Cup empty(){
return new Cup(0,capacity);
}
/**
* 自カップへの移し替えを行う
* 自分A→引数cupBへ内容を移し替える
* @param cup 相手のカップ
* @return 自分のカップの容量
*/
public Cup pour(Cup cup){
Cup result = new Cup[2];
int _sum = now + cup.now;
result[CUP_OTHER] = new Cup(Math.min(cup.capacity, _sum),cup.capacity);
result[CUP_MINE] = new Cup(Math.max(0, _sum - cup.capacity),capacity);
return result;
}
//自分のカップ
public static final int CUP_MINE = 0;
//相手のカップ
public static final int CUP_OTHER = 1;
}
このクラスにて，バケツ操作を受け持ちます．現在の容量と最大容量を記憶します．
そして，木構造においてそれらCupオブジェクトを関連付けるHolderクラスを定義します．
//--CompareHolderクラス-----//
package com.abs104a.cuptest.data;
public final class CompareHolder {
//子要素の関連
private final CompareHolder children;
//親要素の関連
private final CompareHolder rootHolder;
//バケツAの内容
private final Cup tmpResult_A;
//バケツBの内容
private final Cup tmpResult_B;
//現在の配列位置
private final int position;
/**
* 比較する際のホルダー
* @param rootHolder 上位のクラス
* @param tmpResult 現時点での値
* @param maxChildren 最大の持つべき子の数
* @param pattern
*/
public CompareHolder(CompareHolder rootHolder,Cup tmpResult_A,Cup tmpResult_B,int position,int maxChildren){
this.rootHolder = rootHolder;
this.tmpResult_A = tmpResult_A;
this.tmpResult_B = tmpResult_B;
children = new CompareHolder[maxChildren];
this.position = position;
}
public int getPostion(){
return position;
}
public CompareHolder getRootHolder(){
return rootHolder;
}
public Cup getTmpResult_A(){
return tmpResult_A;
}
public Cup getTmpResult_B(){
return tmpResult_B;
}
public boolean setChildren(int position,CompareHolder holder){
if(position < 0 || position >= children.length)
return false;
else{
children[position] = holder;
return true;
}
}
public CompareHolder getChildren(int position){
if(position < 0 || position >= children.length)
return null;
else
return children[position];
}
}
ほとんどゲッターとセッターですね．
この二つがこのプログラムの基となります．
何かある意味で双方向リストみたいな感じになってしまいました．
このホルダーではその木要素のポジションにおける状態の記憶と上流，下流へのアクセスができるようになっています．
もし解が確定した場合，親のクラスを遡る事で解答の手順を取得する事が可能です．
そしてメインルーチン（探索部分ですね
//--searchメソッド-----//
public final static int PATTERN = 3*2;
/**
* メインルーチン
* 探索を行う
* @param root
* @param capacity_A
* @param capacity_B
*/
public void search(final int capacity_A,final int capacity_B,final int goal){
//ルートホルダーの作成
final CompareHolder srootHolder = new CompareHolder(null, new Cup(capacity_A), new Cup(capacity_B),-1, PATTERN);
//探索用のキュー
final LinkedList list = new LinkedList();
//枝切り用の解答キャッシュ
final ArrayList cache = new ArrayList();
list.offer(srootHolder);
//現在の木位置記憶用
CompareHolder tmpHolder = null;
//ループ判定用フラグ
boolean roopFlag = true;
//試行回数
int count = 0;
do{
CompareHolder rootHolder = list.poll();
for(int i = 0;i < PATTERN;i++){
Cup tmp = doActions(i, rootHolder.getTmpResult_A(), rootHolder.getTmpResult_B());
tmpHolder = new CompareHolder(rootHolder, tmp[DATA_A], tmp[DATA_B],i,PATTERN);
rootHolder.setChildren(i, tmpHolder);
count++;
MapData data = new MapData(tmp[DATA_A].getNow(),tmp[DATA_B].getNow());
//判定を行う
if(tmp[DATA_A].getNow() == goal || tmp[DATA_B].getNow() == goal){
System.out.println(i + ": A:"+tmp[DATA_A].getNow()+" ,B:"+tmp[DATA_B].getNow());
roopFlag = false;
break;
}else if(!(data.getA_data() == 0 && data.getB_data() == 0)){
if(cache.indexOf(data) == -1){
list.offer(tmpHolder);
cache.add(data);
}
}
}
}while(roopFlag && list.size() > 0);
System.out.println("試行回数は"+count+"回でした．");
if(!roopFlag){
//結果が出ている場合
LinkedList resultStrings = new LinkedList();
while(tmpHolder.getRootHolder() != null){
resultStrings.push(getString(tmpHolder.getPostion()));
tmpHolder = tmpHolder.getRootHolder();
}
while(resultStrings.size() > 0){
System.out.println(resultStrings.pop());
}
}else{
//結果がでない場合
System.out.println("この試行は不可能です");
}
}
この部分は付随するメソッドがあるのですが一部省略させてください．
簡単に説明すると，
・ホルダーを作ってそれぞれの子要素を作成，計算を行う．
・子要素の解が解答であるか確認する．
・解答でない場合で，双方ともに0または既出以外であればキューに入れる．
・キューが捌けるまで試行を繰り返す．
このような感じです．
キューが捌けた時点で解答が見つからない場合は試行不可能という結論になります．
色々中途半端な気もしますが，今日はもう力尽きてしまったのでこの辺にさせてください．(^_^;)
気が向いたらまた編集かけます．
それでは！
追記：
ソースは
https://github.com/ABS104a/cuptest
に置いておきます．突っ込みや質問はTwitterまでお願いします．
