Javaでreduce(l|r)

404 Blog Not Found:Code Snippets - reduce(l|r)を実装汁!より、面白そうだし、コーディングの練習にもなるのでやってみた。

まずはループで。

public class Reduce {

	public static String reducel(String...a){
		//最初の2つだけ特別扱い
		String tmp = cat(a[0], a[1]);
		for(int i=2; i < a.length; i++){
			tmp = cat(tmp, a[i]);
		}
		return tmp;
	}
	
	public static String reducer(String...a){
		String tmp = cat(a[a.length-2], a[a.length-1]);
		for(int i=a.length-3; i>=0; i--){
			tmp = cat(a[i], tmp);
		}
		return tmp;
	}
	
	private static String cat(String a, String b){
		return "(" + a + "#" + b +")";		
	}
	
	public static void main(String args[]){
		System.out.println(reducel("1","2","3","4","5"));
		System.out.println(reducer("1","2","3","4","5"));
	}

}

長さ判定してないのでマズイコードだ。
次はちゃんと考えて再帰で。

public class Reduce2 {

	public static String reducel(int lastIndex, String[] array){
		if(array.length <= 1){
			// 1つだけ-> reducel無理
			return "can't reducel";
		}else if(lastIndex == 1){
			// 最初の2つだけになったら具体的な文字列を返す
			return cat(array[0], array[1]);
		}
		return cat(reducel(lastIndex-1, array), array[lastIndex]);
	}
	
	public static String reducer(int index, String[] array){
		if(array.length <= 1){
			// 1つだけ-> reducer無理
			return "can't reducer";
		}else if(index == array.length-2){
			// 最後の2つだけになったら具体的な文字列を返す
			return cat(array[array.length-2], array[array.length-1]);
		}
		return cat(array[index], reducer(index+1, array));
	}
	
	private static String cat(String a, String b){
		return "(" + a + "#" + b +")";		
	}
	
	public static void main(String args[]){
		String[] a = {"1","2","3","4","5"};
		System.out.println(reducel(a.length-1, a));
		System.out.println(reducer(0, a));
	}

}

結果はどちらも
((((1#2)#3)#4)#5)
(1#(2#(3#(4#5))))

再帰だと制限の10分を超えてしまった。がふん。
reducel()を実装の時、最初→方向で考えてしまったけど、再帰だとでかい塊から徐々に小さい塊へってなるから逆方向(←)だよね。