Forty Two - A Java Solver
Created | Updated Dec 8, 2002
import java.util.HashMap;
public class GFortyTwo
{
// Data
private HashMap results;
private static final Value impossible=new Value(false, "");
// Constructors
GFortyTwo()
{
results=new HashMap(1000000);
}
public static void main(String[] arguments)
{
GFortyTwo finder=new GFortyTwo();
double[] digits=new double[arguments.length];
for(int i=0; i!=arguments.length; i++)
{
digits[i]=Integer.parseInt(arguments[i]);
}
System.out.println(finder.make(new Key(digits, 42), true));
}
private Value attempt(double[] leftDigits, double leftTarget,
double[] rightDigits, double rightTarget,
boolean switchSides, String symbol)
{
if(switchSides)
{
Value rightResult=make(new Key(rightDigits, rightTarget), true);
if(rightResult.possible)
{
Value leftResult=make(new Key(leftDigits, leftTarget), true);
if(leftResult.possible)
{
return new Value(true, leftResult.toString()+symbol+rightResult.toString());
}
}
}
else
{
Value leftResult=make(new Key(leftDigits, leftTarget), true);
if(leftResult.possible)
{
Value rightResult=make(new Key(rightDigits, rightTarget), true);
if(rightResult.possible)
{
return new Value(true, leftResult.toString()+symbol+rightResult.toString());
}
}
}
return impossible;
}
private Value tryUnary(double from, double to)
{
if(from==to)
{
Value value=new Value(true,
Integer.toString((int)from));
return value;
}
if(((to==2)&&(from==4))||
((to==3)&&(from==9)))
{
Value value=new Value(true,
"q"+Integer.toString((int)from));
return value;
}
if((to==1)&&(from==0)||
(to==6)&&(from==3)||
(to==24)&&(from==4)||
(to==120)&&(from==5)||
(to==720)&&(from==6))
{
Value value=new Value(true,
Integer.toString((int)from)+"!");
return value;
}
if((to==45)&&(from==1))
{
Value value=new Value(true,
"ATN("+Integer.toString((int)from)+")");
return value;
}
if((to==90)&&(from==0))
{
Value value=new Value(true,
"ACOS("+Integer.toString((int)from)+")");
return value;
}
if((to==90)&&(from==1))
{
Value value=new Value(true,
"ASIN("+Integer.toString((int)from)+")");
return value;
}
if((to==0)&&(from==1))
{
Value value=new Value(true,
"ACOS("+Integer.toString((int)from)+")");
return value;
}
return impossible;
}
private Value make(Key key, boolean allowUnary)
{
if(key.digits.length==1)
{
return(tryUnary(key.digits[0], key.target));
}
else
{
Value value=(Value)results.get(key);
if(value!=null)
{
// System.out.println("Old: "+key+" "+value);
// System.out.print("?");
return value;
}
else
{
value=new Value(false, "");
}
try
{
// Digit concatenation
double concatenated=concatenate(key.digits);
if(concatenated==key.target)
{
value.possible=true;
value.formula=Integer.toString((int)key.target);
return value;
}
if((key.target>0)&&(key.target*key.target==concatenated))
{
value.possible=true;
value.formula="q"+Integer.toString((int)concatenated);
return value;
}
// Cycle over split points
int middle=key.digits.length/2;
for(int o=1; o!=key.digits.length; o++)
{
int d=0;
if((o&1)==0)
{
d=middle+o/2;
}
else
{
d=middle-o/2;
}
double[] leftDigits=new double[d];
double[] rightDigits=new double[key.digits.length-d];
double leftTarget=0;
double rightTarget=0;
Value leftResult;
Value rightResult;
boolean switchSides=d>(key.digits.length/2);
for(int i=0; i!=key.digits.length; i++)
{
if(i<d) leftDigits[i]=key.digits[i];
else rightDigits[i-d]=key.digits[i];
}
for(int index=0; index!=key.target*2; index=index<0?-index:-index-1)
{
// Addition
leftTarget=index;
rightTarget=key.target-leftTarget;
value=attempt(leftDigits, leftTarget, rightDigits, rightTarget,
switchSides, "+");
if(value.possible) return value;
// Subtraction
leftTarget=index;
rightTarget=leftTarget-key.target;
value=attempt(leftDigits, leftTarget, rightDigits, rightTarget,
switchSides, "-");
if(value.possible) return value;
// Multiplication
if((index!=0)||(key.target==0))
{
leftTarget=index;
if(key.target!=0) rightTarget=key.target/leftTarget;
else rightTarget=0;
if(rightTarget==(int)rightTarget)
{
value=attempt(leftDigits, leftTarget, rightDigits, rightTarget,
switchSides, "*");
if(value.possible) return value;
}
if(key.target==0)
{
value=attempt(leftDigits, rightTarget, rightDigits, leftTarget,
switchSides, "*");
if(value.possible) return value;
}
}
// Division
if((index!=0)||(key.target==0))
{
leftTarget=index;
rightTarget=leftTarget/key.target;
if(rightTarget==(int)rightTarget)
{
value=attempt(leftDigits, leftTarget, rightDigits, rightTarget,
switchSides, "/");
if(value.possible) return value;
}
}
// Zeroth power
leftTarget=index;
if((key.target==1)&&(leftTarget>0))
{
value=attempt(leftDigits, leftTarget, rightDigits, 0,
switchSides, "^");
if(value.possible) return value;
}
if((key.target==-1)&&(rightTarget<0))
{
value=attempt(leftDigits, leftTarget, rightDigits, 0,
switchSides, "^");
if(value.possible) return value;
}
}
}
return value;
}
finally
{
results.put(key, value);
if(value.possible) System.out.println("New: "+key+" "+value);
}
}
}
private double concatenate(double[] digits)
{
double result=0;
for(int i=0; i!=digits.length; i++)
{
result=result*10+digits[i];
}
return result;
}
private static class Key
{
public double[] digits;
public double target;
Key(double[] digits, double target)
{
this.digits=digits;
this.target=target;
}
public String toString()
{
String result="";
for(int i=0; i!=digits.length; i++)
{
result+=(int)digits[i];
}
result+="=>";
result+=target;
return result;
}
public int hashCode()
{
int result=(int)target;
for(int i=0; i!=digits.length; i++)
{
result=result*13+(int)digits[i];
}
return result;
}
public boolean equals(Object object)
{
if(!(object instanceof Key)) return false;
if(((Key)object).target!=target) return false;
if(((Key)object).digits.length!=digits.length) return false;
for(int i=0; i!=digits.length; i++)
{
if(((Key)object).digits[i]!=digits[i]) return false;
}
return true;
}
}
private static class Value
{
public boolean possible;
public String formula;
Value(boolean possible, String formula)
{
this.possible=possible;
this.formula=formula;
}
public String toString()
{
if(!possible) return "not possible";
else if(formula.length()<3) return formula; else return "("+formula+")";
}
}
}
