プログラムで総当たりしてみた
昨日の問題で、”OOPS!”AOIさんから以下のコメントを頂いた。
お茶休憩にmixiで発見！
あー、こういうの好きー。俺も考えてみた・・・。
２つの組で1log下げるより（4log下がる）、３つの組で2log下げた方（8log下がる）
が効率よさそう・・・と思って、電卓計算・・・。試行錯誤の結果、
2.0/(1.2-1.9/1.6)(1.3-1.8/1.4)(1.7/1.5-1.1)
が30万ちょっと超えた。多分組み合わせをプログラムして総当たりすると、
いいんだろうけど、それは、mjhさんにおまかせ〜。^^;
おまかせされたので、プログラムを書いてみた。（笑）
明日はRubyKaigiに出かけるけど、気分的にきょうはJavaで書いたw
p1/(abs(p2-p3/p4) * abs(p5-p6/p7) * abs(p8-p9/p10))
で、求めた値の大きな上位10通りの組み合わせを求めてみた。MacBook Pro(Corei7 2.66GHz)で、実行時間は1.5秒ほど。
以下、実行結果。
RANKING#1 ... 335999.9999999977 : 2.0 / (abs(1.2-1.9/1.6) * abs(1.1-1.7/1.5) * abs(1.3-1.8/1.4)
RANKING#2 ... 335999.9999999977 : 2.0 / (abs(1.1-1.7/1.5) * abs(1.2-1.9/1.6) * abs(1.3-1.8/1.4)
RANKING#3 ... 335999.9999999976 : 2.0 / (abs(1.2-1.9/1.6) * abs(1.3-1.8/1.4) * abs(1.1-1.7/1.5)
RANKING#4 ... 335999.9999999976 : 2.0 / (abs(1.1-1.7/1.5) * abs(1.3-1.8/1.4) * abs(1.2-1.9/1.6)
RANKING#5 ... 335999.9999999976 : 2.0 / (abs(1.3-1.8/1.4) * abs(1.1-1.7/1.5) * abs(1.2-1.9/1.6)
RANKING#6 ... 335999.9999999976 : 2.0 / (abs(1.3-1.8/1.4) * abs(1.2-1.9/1.6) * abs(1.1-1.7/1.5)
RANKING#7 ... 311999.9999999978 : 2.0 / (abs(1.2-1.9/1.6) * abs(1.1-1.7/1.5) * abs(1.4-1.8/1.3)
RANKING#8 ... 311999.9999999978 : 2.0 / (abs(1.1-1.7/1.5) * abs(1.2-1.9/1.6) * abs(1.4-1.8/1.3)
RANKING#9 ... 311999.9999999978 : 2.0 / (abs(1.4-1.8/1.3) * abs(1.1-1.7/1.5) * abs(1.2-1.9/1.6)
RANKING#10 ... 311999.9999999978 : 2.0 / (abs(1.1-1.7/1.5) * abs(1.4-1.8/1.3) * abs(1.2-1.9/1.6)
”OOPS!”AOIさんの試行錯誤結果がトップに出てきて驚いた。すごい!!
最初の1log**4法と今回の2log**3法以外でも何か良い方法があるか引き続き考えてみたい。
以下、プログラムリスト。
import java.lang.*; import java.util.*; public class Puzzle01 { protected static final int RANKING = 10; public static void main(String[] args) { final double[] data = new double[] { 1.1 , 1.2 , 1.3 , 1.4 , 1.5 , 1.6 , 1.7 , 1.8 , 1.9 , 2.0 }; final TopN topn= new TopN(RANKING); new Combinator(data.length,new CombinationHandler() { public void execute(int[] indeces) { double result = calc(data,indeces); if (!(result == Double.POSITIVE_INFINITY || result == Double.NEGATIVE_INFINITY)) { topn.update(result,indeces); } } private double calc(double[] data,int[] idx) { return data[idx[0]] / (Math.abs(data[idx[1]]-data[idx[2]]/data[idx[3]]) * Math.abs(data[idx[4]]-data[idx[5]]/data[idx[6]]) * Math.abs(data[idx[7]]-data[idx[8]]/data[idx[9]])); } }).doCombinate(); for (int i=0 ; i<RANKING ; i++) { System.out.print("RANKING#"+(i+1)+" ... "); System.out.print(""+topn.getData(i)+" : "); int[] ds = (int[])topn.getDescription(i); System.out.println(""+data[ds[0]]+ " / (abs("+data[ds[1]]+"-"+data[ds[2]]+"/"+data[ds[3]]+")" + " * abs("+data[ds[4]]+"-"+data[ds[5]]+"/"+data[ds[6]]+")" + " * abs("+data[ds[7]]+"-"+data[ds[8]]+"/"+data[ds[9]]+")" ); } System.out.println("End of execution..."); } } class TopN { protected DataHolder[] dataList_; protected boolean sorted_; public TopN(int n) { dataList_ = new DataHolder[n]; sorted_ = false; } public void update(double value,Object description) { double minValue = Double.MAX_VALUE; int minIndex = -1; for (int i=0 ; i<dataList_.length ; i++) { if (dataList_[i] == null) { dataList_[i] = new DataHolder(value,description); return; } if (minValue > dataList_[i].data) { minValue = dataList_[i].data; minIndex = i; } } if (value > minValue) { dataList_[minIndex] = new DataHolder(value,description); sorted_ = false; } } public double getData(int rank) { sort(); return dataList_[rank].data; } public Object getDescription(int rank) { sort(); return dataList_[rank].description; } protected void sort() { if (sorted_ == false) { Arrays.sort(dataList_,new Comparator<DataHolder>() { public int compare(DataHolder d1,DataHolder d2) { double data1 = d1.data; double data2 = d2.data; if (data1 < data2) { return 1; } else if (data1 > data2) { return -1; } else { return 0; } } }); sorted_ = true; } } protected class DataHolder { public double data; public Object description; public DataHolder(double data,Object description) { this.data = data; this.description = description; } } } interface CombinationHandler { public void execute(int[] indeces); } class Combinator { protected int digit_; protected CombinationHandler handler_; public Combinator(int digit,CombinationHandler handler) { digit_ = digit; handler_ = handler; } public void doCombinate() { for (int i=0 ; i<digit_ ; i++) { long[] context = new long[1]; context[0] = (1<<i); calcCombination(context,digit_-1); } } protected void calcCombination(long[] context,int remain) { long markedPoints = getMarkedPoints(context); if (remain == 1) { for (int i=0 ; i<digit_ ; i++) { if ((markedPoints & (1<<i)) == 0) { handler_.execute(makeIndeces(generateContext(context,i))); break; } } } else { for (int i=0 ; i<digit_ ; i++) { if ((markedPoints & (1<<i)) == 0) { calcCombination(generateContext(context,i),remain-1); } } } } protected long getMarkedPoints(long[] dataset) { long points = 0; for (long data : dataset) { points |= data; } return points; } protected int[] makeIndeces(long[] context) { int[] indeces = new int[context.length]; for (int i=0 ; i<context.length ; i++) { for (int pos=0 ; pos<context.length ; pos++) { if (context[i] == (1<<pos)) { indeces[i] = pos; break; } } } return indeces; } protected long[] generateContext(long[] context,int value) { long[] newContext = new long[context.length + 1]; for (int i=0 ; i<context.length ; i++) { newContext[i] = context[i]; } newContext[context.length] = 1<<value; return newContext; } }
