４つで１０

Javaについて少し勉強したので、練習として４つの数字で１０を作るプログラムを書きました。

４つで１０を作る遊びはテンパズルとかメイクテンと呼ばれてるらしいです。

package fourtoten.com;

import java.io.*;
import java.util.ArrayList;

public class FourToTen{
	double[] input=new double[4];
	String s;
	boolean b;
	
	FourToTen() throws IOException{
		BufferedReader br=
				new BufferedReader(new InputStreamReader(System.in));
		System.out.println("４つの数を,で区切って入力");
		String moji=br.readLine();
		String[] inputmoji=moji.split(",");
		for(int i=0;i<4;i++){
			input[i]=Double.parseDouble(inputmoji[i]);
		}
	}
	
	public void maketen(FourToTen result){
		ArrayList<ArrayList<Tree>> treelist=new ArrayList<ArrayList<Tree>>();
		ArrayList<Tree> subtreelist=new ArrayList<Tree>();
		for(int i=0;i<result.input.length;i++){
			Tree tree=new Tree();
			tree.children=new Tree[0];
			tree.value=Double.toString(result.input[i]);
			subtreelist.add(tree);
		}
		treelist.add(subtreelist);
		while(treelist.get(0).size()>=2){
			ArrayList<ArrayList<Tree>> sublist=new ArrayList<ArrayList<Tree>>();
			int jmax=ketugou(treelist.get(0)).size();
			for(int i=0;i<treelist.size();i++){
				for(int j=0;j<jmax;j++){
					sublist.add(ketugou(treelist.get(i)).get(j));
				}
			}
			treelist=sublist;
		}
		
		for(int i=0;i<treelist.size();i++){
			if(treelist.get(i).get(0).calc(0)==10.0){
				result.b=true;
				result.s=treelist.get(i).get(0).dump();
				return;
			}
		}
		result.b=false;
		result.s="0";
		return;
	}
	
	public static ArrayList<ArrayList<Tree>> ketugou(ArrayList<Tree> b){
		ArrayList<ArrayList<Tree>> treelist=new ArrayList<ArrayList<Tree>>();
		ArrayList<Tree> subtreelist;
		Tree subtree;
		
		for(int i=0;i<b.size();i++){
			for(int j=0;j<b.size();j++){
				if(i==j) continue;
				for(int k=0;k<=3;k++){
					subtreelist=new ArrayList<Tree>();
					
					subtree=new Tree();
					subtree.value=func_to_op(k);
					subtree.children=new Tree[2];
					subtree.children[0]=b.get(i);
					subtree.children[1]=b.get(j);
					subtreelist.add(subtree);
					for(int m=0;m<b.size();m++){
						if(m==i||m==j) continue;
						subtreelist.add(b.get(m));
					}
					treelist.add(subtreelist);
				}
			}
		}
		return treelist;
	}
	
	static double func(int k,double a,double b){
		switch(k){
		case 0:return a+b;
		case 1:return a-b;
		case 2:return a*b;
		case 3:return a/b;
		default:return 0;
		}
	}
	
	static String func_to_op(int k){
		switch(k){
		case 0:return "+";
		case 1:return "-";
		case 2:return "*";
		case 3:return "/";
		default:return "?";
		}
	}
	
}

package 遺伝的プログラミング.com;

public class Tree {
    public String value;
    public Tree[] children;

    public String dump() {
        String result = value;
        for (int i = 0; i < children.length; i++)
            result += " " + children[i].dump();
        return result;
    }

    public double calc(double x) {
        switch (value.charAt(0)) {
        case '+': return children[0].calc(x) + children[1].calc(x);
        case '-': return children[0].calc(x) - children[1].calc(x);
        case '*': return children[0].calc(x) * children[1].calc(x);
        case '/': return children[0].calc(x) / children[1].calc(x);
        case '^': return Math.pow(children[0].calc(x), children[1].calc(x));
        case 'x': return x;
        }
        return Double.parseDouble(value);
    }
    
    static public Tree make(java.util.Random rand, int len) {
        Tree result = new Tree();
        switch(len >= 5 ? 6 : rand.nextInt(7)) {
        case 0: result.value = "+"; result.children = new Tree[2]; break;
        case 1: result.value = "-"; result.children = new Tree[2]; break;
        case 2: result.value = "*"; result.children = new Tree[2]; break;
        case 3: result.value = "/"; result.children = new Tree[2]; break;
        case 4: result.value = "^"; result.children = new Tree[2]; break;
        case 5: result.value = "x"; result.children = new Tree[0]; break;
        default: result.value = ((Integer)(rand.nextInt(10) + 1)).toString(); result.children = new Tree[0];
        }
        for (int i = 0; i < result.children.length; i++)
            result.children[i] = make(rand, len + 1);
        return result;
    }
}

package fourtoten.com;

import java.io.*;

class Test{
	public static void main(String[] args) throws IOException{
		FourToTen result=new FourToTen();
		result.maketen(result);
		System.out.println("結果："+result.b);
		if(result.b==true) System.out.println("式:"+result.s);
	}
}

Treeクラスはこちらから借りました→http://shogo82148.github.io/blog/2012/10/04/6saiconf-3/

悩んだのはやはり、どう木構造を上手く定義するかと、４つの数字で何通り計算できるかですね。木構造の方は遺伝的プログラミングで検索したらすごいのが出てきたので迷わず使いました。
後、式の出力はポーランド記法なので少し解説すると、2+3を+23のように書きます。/*54-86は(5*4)/(8-6)ですね。
C++はまだ勉強してませんが、動的配列はCよりJavaのほうが使いやすいかなと思いました。ただ、プログラミング言語を複数学ぶと、どれを使っていいか迷っちゃいますよね。