油分け算の問題をJavaで解いてみた。

　油分け算の問題をJavaで解いてみました。(^_^;
　いつもの如く思いつきの即興で作った変なプログラムですが、とりあえず動きます。(^_^;
　定数M,N,GX,GYを変えるだけで、他の問題も解けると思います。

●MeasuringWithJugs01.java

/* 
 * MeasuringWithJugs01.java
 * 
 * 油分け算
 * 
 * Ｃ
 * ＋−＋−②−＋−⑥−＋
 * ｜　｜　｜＼｜　｜＼｜
 * ④−＋−＋−＋−＋−⑤
 * ｜＼｜　｜　｜＼｜　｜
 * ＋−＋−＋−＋−＋−＋
 * ｜　｜＼｜　｜　｜＼｜
 * ◎−＋−③−＋−⑦−①Ｂ
 * 
 * Ｃ
 * ①−⑦−＋−③−＋−＋
 * ｜＼｜＼｜　｜＼｜　｜
 * ＋−＋−＋−＋−＋−＋
 * ｜　｜＼｜＼｜　｜＼｜
 * ⑤−＋−＋−＋−＋−④
 * ｜＼｜　｜＼｜＼｜　｜
 * ◎−⑥−＋−②−⑧−＋Ｂ
 * 
 */

public class MeasuringWithJugs01 {
    public static void main(String[] args) {
        final int  M=5,  N=3;    // M:Bの最大値; N:Cの最大値
        final int GX=4, GY=0;    // GX:ゴールのX(B)座標; GY:ゴールのY(C)座標
        
        boolean sw=false;
        String ans1="",ans2="";
        
        long tm=System.nanoTime();  // Timer Start
        
        Point p = new Point(0,0,1,0,M,N);
        do {
            String t=p.sDisp();
            if(t=="") continue;
            
            //System.out.println(t);
            if(!sw) ans1+=t; else ans2 =t+ans2;
            if(p.isGoal(GX,GY)) { sw=true; ans2=t; }
        }while(p.nextTurn());
        System.out.println("[ A, B, C]");
        System.out.println("----------");
        System.out.print(ans1);
        System.out.println("----------");
        System.out.print(ans2);
        System.out.println();
        tm=System.nanoTime()-tm;    // Timer Stop
        System.out.printf("Runtime : %.3f [sec]\n",(double)tm/1e9);
    }
}

class Point {
    private int  x=0,  y=0,  z=0;
    private int dx=0, dy=0;
    private int mx=0, my=0;
    
    public Point()  { }
    public Point(int x, int y, int dx, int dy, int mx, int my) {
        this.x=x; this.y=y; this.dx=dx; this.dy=dy; this.mx=mx; this.my=my;
        z=(mx+my)-(x+y);
    }
    
    public boolean nextTurn() {
        int t=mx+my;
        x+=dx; y+=dy; z=t-x-y;
        
        if((y< 0 && x!=0)||x> mx)   { x-=dx; y-=dy; dx=-1; dy= 1; x+=dx; y+=dy; z=t-x-y; }
        else if(y> my)              { x-=dx; y-=dy; dx= 0; dy=-1; x+=dx; y+=dy; z=t-x-y; }
        else if(x< 0)               { x-=dx; y-=dy; dx= 1; dy= 0; x+=dx; y+=dy; z=t-x-y; }
        return isInArea();
    }
        
    public boolean isInArea() {
        if (0<=x && x<=mx && 0<=y && y<=my) return(true);
        else return(false);
    }
    
    public boolean isGoal(int a, int b) {
        if (x==a && y==b && dy==-1) return true; else return false;
    }
    
    public String sDisp() {
        String s="";
        if ((x==0 &&  y==0 )||
            (x==0 && dx==-1)||(x==mx && dx==1)||(y==0 && dy==-1)||(y==my && dy==1))
            s=String.format("[%2d,%2d,%2d]\n",z,x,y);
        return s;
    }
}

●実行結果

[ A, B, C]
----------
[ 8, 0, 0]
[ 3, 5, 0]
[ 3, 2, 3]
[ 6, 2, 0]
[ 6, 0, 2]
[ 1, 5, 2]
[ 1, 4, 3]
[ 4, 4, 0]
----------
[ 8, 0, 0]
[ 5, 0, 3]
[ 5, 3, 0]
[ 2, 3, 3]
[ 2, 5, 1]
[ 7, 0, 1]
[ 7, 1, 0]
[ 4, 1, 3]
[ 4, 4, 0]

Runtime : 0.027 [sec]

※参考URL
●油分け算 - rscの日記
●知恵袋の油分け算の問題をPythonで解いてみた。