/**
* RubieRecursion.java
*
* Apr 15, 2014
*/
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* @author aussiemcgr
*
* The class which does the recursion.
*/
public class RubieRecursion {
/**
* The list of rubies which can be bought for exchange. Note: ascending order for greedy algorithm.
*/
public static int[] buyRubies = new int[]{600,1200,2700,6500,17000};
/**
* The list of rubie packages which can be bought. Note: descending order for greedy algorithm.
*/
public static int[] packages = new int[]{3250,1820,1350,975,750,520,390,260};
/**
* The bounds threshold so the recursive numbers do not grow too large. This is set to twice the largest
* package.
*/
public static int bound_threshold = (int)(packages[0]*2.0);
/**
* A map of numbers which have already been visited by recursions. This exists so we can prevent recursing
* with numbers we already have. It is assumed that the first item to be mapped to a number is the shortest
* path to that number.
*/
public static Map<Integer,RubieRecursion> mappedValues = new HashMap<Integer,RubieRecursion>();
/**
* The rubie value for the recursion.
*/
private int value;
/**
* A list of rubie conversions made for this recursion.
*/
private List<Integer> rubiesPurchased;
/**
* A list of rubie packages purchased for this recursion.
*/
private List<Integer> packagesPurchased;
/**
* A list of all sub-recursions for this recursion.
*/
private List<RubieRecursion> recursions;
/**
* <b>true</b> if the sub-recursions have already been built, <b>false</b> otherwise.
*/
private boolean recursionsBuilt = false;
/**
* The parent recursion to this sub-recursion. <b>null</b> if this is the
* recursion called from the main.
*/
private RubieRecursion parent;
/**
* A sub-recursion which should be removed because it has reached a dead end.
*/
private RubieRecursion triggerRemoveChild;
/**
* Creates a new RubieRecursion. The parent is set to null.
*
* @param val the initial rubie value for the recursion
*/
public RubieRecursion(int val) {
/* According to the conversions and packages available, the initial value must be
* divisible by 5. If it is not divisible by 5, no solution can be found
*/
if(val%5!=0)
throw new RuntimeException("Invalid input: "+val+". Value must be divisible by 5.");
this.value = val;
this.rubiesPurchased = new ArrayList<>();
this.packagesPurchased = new ArrayList<>();
this.recursions = new ArrayList<>();
}
/**
* Creates a new RubieRecursion with the initial value and parent recursion.
*
* @param val the initial rubie value for the recursion
* @param par the parent recursion
*/
public RubieRecursion(int val, RubieRecursion par) {
this(val);
this.parent = par;
}
/**
* @return the list of rubies conversions for this recursion
*/
public List<Integer> getRubiesPurchased() {
return this.rubiesPurchased;
}
/**
* @return the list of rubie packages purchased for this recursion
*/
public List<Integer> getPackagesPurchased() {
return this.packagesPurchased;
}
/**
* Adds a new rubies conversion to the list.
*
* @param amount the conversion value to add
*/
@SuppressWarnings("boxing")
public void addRubiesPurchase(int amount) {
this.rubiesPurchased.add(amount);
}
/**
* Adds a new rubies purchase package to the list.
*
* @param amount the package value to add
*/
@SuppressWarnings("boxing")
public void addPackagePurchase(int amount) {
this.packagesPurchased.add(amount);
}
/**
* @return the value of this recursion
*/
public int getValue() {
return this.value;
}
/**
* Adds a recursion to the sub-recursions. If the value for this recursion is already found
* in the map, the value is not added, because a shorter path to it has already been discovered
* and is already being recursed.
*
* @param toAdd the recursion to add
*/
public void addToRecursions(RubieRecursion toAdd) {
Object existing = RubieRecursion.mappedValues.get(Integer.valueOf(toAdd.value));
if(existing==null) {
RubieRecursion.mappedValues.put(Integer.valueOf(toAdd.value), toAdd);
this.recursions.add(toAdd);
}
else {
//System.out.println("Already existing: "+toAdd.value);
//System.out.println("Existing: "+existing+", Adding: "+toAdd);
}
}
/**
* Runs the recursion. This is called only from the main.
*
* @return the shortest recursion to the goal
*/
public RubieRecursion run() {
// value is 0, we can cleanup the recursion and return this as the fastest result
if(this.value==0) {
while(cleanUp()) {/*do nothing*/}
return this;
}
// build the sub-recursions
RubieRecursion check = buildRecursions();
// if check is not null, a successful result was found, so we should clean it and return it
if(check!=null) {
this.packagesPurchased.addAll(check.packagesPurchased);
this.rubiesPurchased.addAll(check.rubiesPurchased);
while(cleanUp()) {/*do nothing*/}
return this;
}
// max iterations of 50, just to be safe that the program doesn't run forever.
// 50 should be more than big enough.
int iterations = 50;
for(int its=0;its<iterations;its++) {
System.out.println("its: "+its+", size: "+this.recursions.size());
// iterate over the sub-recursions and recurse each one
for(int i=0;i<this.recursions.size();i++) {
RubieRecursion temp = this.recursions.get(i);
RubieRecursion result = recurse(temp);
// if result is not null, a sub-recursion was successful, so we should return it
if(result!=null) {
this.packagesPurchased.addAll(result.packagesPurchased);
this.rubiesPurchased.addAll(result.rubiesPurchased);
while(cleanUp()) {/*do nothing*/}
return this;
}
// if a child has been set to remove, we remove it and continue with the rest of the list
if(this.triggerRemoveChild!=null) {
this.recursions.remove(this.triggerRemoveChild);
this.triggerRemoveChild = null;
i--;
}
}
}
// no successful recursion was found
return null;
}
/**
* Attempts to shorten the recursion by combining purchases and conversions.
*
* @return <b>true</b> if a change occurred and a cleanup should be ran again,
* <b>false</b> if there was nothing to clean up.
*/
@SuppressWarnings("boxing")
public boolean cleanUp() {
boolean change = false;
for(int x=0;x<this.rubiesPurchased.size();x++) {
int tempValue = this.rubiesPurchased.get(x);
OUTER:
for(int y=x+1;y<this.rubiesPurchased.size();y++) {
int value2 = this.rubiesPurchased.get(y);
for(int option : RubieRecursion.buyRubies) {
if(tempValue+value2==option) {
this.rubiesPurchased.remove(x);
this.rubiesPurchased.remove(y);
this.rubiesPurchased.add(option);
x--;
change = true;
break OUTER;
}
}
}
}
for(int x=0;x<this.packagesPurchased.size();x++) {
int tempValue = this.packagesPurchased.get(x);
OUTER:
for(int y=x+1;y<this.packagesPurchased.size();y++) {
int value2 = this.packagesPurchased.get(y);
for(int option : RubieRecursion.packages) {
if(tempValue+value2==option) {
this.packagesPurchased.remove(x);
this.packagesPurchased.remove(y);
this.packagesPurchased.add(option);
x--;
change = true;
break OUTER;
}
}
}
}
return change;
}
/**
* The recursive call to check the sent recursion and build sub-recursions.
*
* @param check the recursion to build off of
* @return a successful recursion, or <b>null</b> if the recursion was not finished
*/
public RubieRecursion recurse(RubieRecursion check) {
// if the value is 0, we have a successful recursion, so we return it
if(check.getValue()==0) {
return check;
}
System.out.println(check.toString()+", recursions: "+check.recursions.size()+", "+check.recursionsBuilt);
// if the sub-recursion size is 0...
if(check.recursions.size()==0) {
// ... and if the recursions have already been built, it means we have exhausted all the children, so
// this recursion can be removed from its parent
if(check.recursionsBuilt) {
System.out.println("Already built");
check.parent.triggerRemoveChild = check;
return null;
}
//... we build the sub-recursions
RubieRecursion temp = check.buildRecursions();
check.recursionsBuilt = true;
if(temp!=null) {
return check;
}
// return null pause this recursion and cycle to the next recursive call
return null;
}
// recurse each sub-recursion
for(int i=0;i<check.recursions.size();i++) {
RubieRecursion result = check.recurse(check.recursions.get(i));
if(result!=null) {
check.rubiesPurchased.addAll(result.rubiesPurchased);
check.packagesPurchased.addAll(result.packagesPurchased);
return check;
}
if(check.triggerRemoveChild!=null) {
check.recursions.remove(check.triggerRemoveChild);
check.triggerRemoveChild = null;
i--;
}
}
// a solution has not been found yet, return null to pause this recursion and cycle to the next
return null;
}
/**
* Builds the sub-recursions for this recursion.
*
* @return a successful recursion, or <b>null</b> if the recursion is not finished
*/
@SuppressWarnings("boxing")
public RubieRecursion buildRecursions() {
System.out.println("Value: "+this.toString());
// the value of 0, so we can return this recursion as successful
if(this.value==0) {
return this;
}
// iterate over the package options
for(int pack : RubieRecursion.packages) {
// if the value is smaller than the package size, there is no point in try to do any math with it
if(this.value<pack)
continue;
/* if the value is divisible by the package size, we know a direct path is just purchasing x number
* of these packages. However, just purchasing x number of packages may not be the shortest path, so
* we just recurse with one package for now, and exit the loop to conserve our greedy-algorithm design.
*/
if(this.value%pack==0) {
RubieRecursion temp = new RubieRecursion(this.value-pack,this);
temp.packagesPurchased.add(pack);
addToRecursions(temp);
break;
}
// add a recursion where one of these packages have been purchased
RubieRecursion temp = new RubieRecursion(this.value-pack,this);
temp.addPackagePurchase(pack);
addToRecursions(temp);
}
// if the bounds threshold has been reached, return null to indicate the recursion has hit a dead end.
// It will automatically be cleaned up from its parent later.
if(this.value>RubieRecursion.bound_threshold) {
System.out.println("Bound hit - "+this.recursions.size());
return null;
}
// loop through the conversion options for the rubies and build a recursion off of each one
for(int buy : RubieRecursion.buyRubies) {
RubieRecursion temp = new RubieRecursion(this.value+buy,this);
temp.addRubiesPurchase(buy);
addToRecursions(temp);
// loop through the packages and build a recursion of each purchase package off of each conversion option
for(int pack : RubieRecursion.packages) {
if(temp.getValue()<pack) {
continue;
}
RubieRecursion newTemp = new RubieRecursion(temp.getValue()-pack,this);
newTemp.addRubiesPurchase(buy);
newTemp.addPackagePurchase(pack);
addToRecursions(newTemp);
}
}
// return null to pause the current recursion (and all sub-recursions) and cycle to the next recursion call
return null;
}
@Override
public String toString() {
String result = ""+this.value;
if(this.parent!=null) {
result = this.parent.toString()+"->"+result;
}
return result;
}
}
LinkBack URL
About LinkBacks
Need help on how to tackle this Java Project.
Reply With Quote
Related threads:
Originally Posted by GregBrannon
. Would i be able to look at your solution?