/**
* This models a Greedy Nim position. Greedy Nim is just like Nim, except that players must choose to remove sticks from the biggest pile.
*
* @author Kyle Burke <paithanq@gmail.com>
*
*/
import java.lang.*;
import java.io.*;
import java.util.*;
public class GreedyNim extends CombinatorialGame {
//instance variables
//Priority Queue of pile sizes
private PurePriorityQueue<Integer> piles;
//Integer comparator that sorts in DESCENDING order
private static final Comparator<Integer> MAX = new Comparator<Integer>() {
public int compare(Integer left, Integer right) {
return right.intValue() - left.intValue();
}
};
/**
* Class constructor.
*
* @param piles A List of natural numbers used as the pile sizes.
* @throws IllegalArgumentException if one of the pile sizes is negative.
*/
public GreedyNim(List<Integer> piles) throws IllegalArgumentException {
this.piles = new PurePriorityQueue<Integer>(MAX);
for (Integer pile : piles) {
if (pile.intValue() > 0) {
this.piles.add(pile);
} else if (pile.intValue() < 0) {
throw new IllegalArgumentException("Tried to use a negative pile size, " + pile.intValue() + ", in a GreedyNim position.");
}
}
}
/**
* Returns a string version of this.
*
* @return String version of this.
*/
public String toString() {
StringBuffer buffer = new StringBuffer();
buffer.append("GreedyNim position (max pile on left): ");
for (Integer pile : this.getPilesAsList()) {
buffer.append(pile + " ");
}
return buffer.toString();
}
/**
* Returns the piles of this.
*
* @return A PurePriorityQueue of the pile sizes.
*/
public PurePriorityQueue<Integer> getPiles() {
ArrayList<Integer> pileList = this.getPilesAsList();
//create the copy and put the piles into it.
PurePriorityQueue<Integer> pilesCopy = new PurePriorityQueue<Integer>(MAX);
for (Integer pile : pileList) {
pilesCopy.add(pile);
}
return pilesCopy;
}
/**
* Deep clones this.
*
* @return A deep clone of this.
*/
public CombinatorialGame clone() {
return new GreedyNim(this.getPilesAsList());
}
//@override
public boolean equals(CombinatorialGame other) {
if (other == null) {
return false;
} else if (this.getClass() == other.getClass()) {
GreedyNim otherGreedyNim;
try {
otherGreedyNim = (GreedyNim) other;
} catch (ClassCastException cce) {
//other is not the same type.
return false;
}
return this.piles.hasSameElementsAs(otherGreedyNim.piles);
} else {
return false;
}
}
//@override
public Collection<CombinatorialGame> getOptions(int playerId) {
Collection<CombinatorialGame> options = new Vector<CombinatorialGame>();
GreedyNim clone = (GreedyNim) this.clone();
Integer biggest;
try {
biggest = clone.piles.remove();
} catch (NoSuchElementException nsee) {
//no options available
return options;
}
//add the option where you take the entire max pile
//(clone is still missing it's biggest pile)
options.add(new GreedyNim(clone.getPilesAsList()));
for (int i = 1; i < biggest.intValue(); i++) {
GreedyNim copyOfClone = (GreedyNim) clone.clone();
copyOfClone.piles.add(new Integer(i));
options.add(copyOfClone);
}
return options;
}
//private methods
//returns an ArrayList of the piles in this.
private ArrayList<Integer> getPilesAsList() {
ArrayList<Integer> pilesList = new ArrayList<Integer>();
PurePriorityQueue<Integer> pilesCopy = new PurePriorityQueue<Integer>(MAX);
while (true) {
Integer nextPile;
try {
nextPile = this.piles.remove();
pilesCopy.add(nextPile);
pilesList.add(nextPile);
} catch (NoSuchElementException nsee) {
break; //exit the while loop
}
}
//reset the piles and return
this.piles = pilesCopy;
return pilesList;
}
/**
* Represents a factory that creates instances of GreedyNim.
*/
public static class PositionBuilder implements PositionFactory<GreedyNim> {
//maximum number of piles it will generate
private int numPiles;
//maximum piles size
private int maxPileSize;
/**
* Class constructor.
*
* @param numPiles The maximum number of piles.
* @param maxPileSize The maximum size of a pile.
*/
public PositionBuilder(int numPiles, int maxPileSize) {
this.numPiles = numPiles;
this.maxPileSize = maxPileSize;
}
//@override
public GreedyNim getPosition() {
List<Integer> piles = new ArrayList<Integer>();
Random randomGenerator = new Random();
for (int i = 0; i < numPiles; i++) {
int pileSize = randomGenerator.nextInt(this.maxPileSize + 1);
if (pileSize > 0) {
piles.add(new Integer(pileSize));
}
}
return new GreedyNim(piles);
}
} //end of GreedyNimFactory
//main method with the unit test
public static void main(String[] args) {
ArrayList<Integer> piles = new ArrayList<Integer>();
piles.add(new Integer(4));
piles.add(new Integer(1));
piles.add(new Integer(7));
piles.add(new Integer(0)); //shouldn't get added :)
piles.add(new Integer(5));
//test constructor and toString
GreedyNim nim = new GreedyNim(piles);
System.out.println("Standard starting position: " + nim.toString());
//test the exception throwing of the constructor
piles.add(new Integer(-5)); //adding this pile will cause an exception.
try {
//should cause an exception
nim = new GreedyNim(piles);
} catch (IllegalArgumentException are) {
System.out.println("Caught the exception caused by the negative pile size!");
}
//test getPiles (toString already tests this, but let's do it again for completeness)
PurePriorityQueue<Integer> pilePQ = nim.getPiles();
System.out.println("Piles in the position: ");
while (true) {
try {
System.out.print(pilePQ.remove() + " ");
} catch (NoSuchElementException nsee) {
break; //no more elements; quit the loop
}
}
System.out.println();
//test clone
GreedyNim clone = nim;
try {
clone = (GreedyNim) nim.clone();
System.out.println("Cloned game: " + clone.toString());
} catch (ClassCastException cce) {
System.out.println("ERROR! clone() caused a ClassCastException!");
cce.printStackTrace();
}
//test equals
//easy tests
System.out.println("nim equals clone? Should be true: " + nim.equals(clone));
System.out.println("clone equals nim? Should be true: " + clone.equals(nim));
//more difficult tests
ArrayList<Integer> differentPiles = new ArrayList<Integer>();
differentPiles.add(new Integer(7));
differentPiles.add(new Integer(5));
differentPiles.add(new Integer(4));
GreedyNim differentNim = new GreedyNim(differentPiles);
System.out.println("nim equals 7-5-4 position? Should be false: " + nim.equals(differentNim));
System.out.println("7-5-4 equals nim? Should be false: " + differentNim.equals(nim));
differentPiles.add(new Integer(4));
differentPiles.add(new Integer(1));
differentNim = new GreedyNim(differentPiles);
System.out.println("nim equals 7-5-4-4-1 position? Should be false: " + nim.equals(differentNim));
System.out.println("7-5-4-4-1 equals nim? Should be false: " + differentNim.equals(nim));
//more difficult true test
ArrayList<Integer> samePiles = differentPiles;
samePiles.remove(3);
GreedyNim sameNim = new GreedyNim(samePiles);
System.out.println("nim equals 7-5-4-1 position? Should be true: " + nim.equals(sameNim));
System.out.println("7-5-4-1 equals nim? Should be true: " + sameNim.equals(nim));
//test getOptions
System.out.println("Move options: ");
for (CombinatorialGame position : nim.getOptions(0)) {
System.out.println(position);
}
//test GreedyNimFactory
PositionBuilder gameGenerator = new PositionBuilder(4, 7);
System.out.println("A randomly-generated game: \n" + gameGenerator.getPosition());
System.out.println("Another randomly-generated game: \n" + gameGenerator.getPosition());
System.out.println("Yet another randomly-generated game: \n" + gameGenerator.getPosition());
}
} //end of GreedyNim.java