Comparing Date Formatting Options

Since Java's SimpleDateFormat object isn't thread-safe and synchronizing it in a production application is a bad idea, I've looked into a few alternatives:
1) Create a new SimpleDateFormat object each time we wish to parse a string into a date
2) Create a single SimpleDateFormat object per thread
3) Use the Joda Time library do format dates

I've run two tests on six methods of parsing text:
1) One instance of SimpleDateFormat called many times
2) One static instance of SimpleDateFormat called many times
3) Many instances of SimpleDateFormat called once each
4) One instance of DateTimeFormatter (JodaTime) called many times
5) One static instance of DateTimeFormatter (Joda Time) called many times
6) Many instances of DateTimeFormatter (Joda Time) called once each

The two tests are:
a) 1 formatter x 10,000 parses
b) 10,000 formatters x 2 parses

Test a:

1a) 23 ms.

2a) 28 ms.

3a) 198 ms.

4a) 9 ms.

5a) 10 ms.

6a) 11 ms.
Test b:

1b) 24 ms.

2b) 24 ms.

3b) 304 ms.

4b) 54 ms.

5b) 12 ms.

6b) 9 ms.
Option 1 is the control group because it represents the status-quo (and it's not usable since it doesn't work properly in a multi-threaded environment).  Option 3 is clearly out since it has the worst performance on both metrics.  Options 5 and 6 are both appealing since they both perform well on the tests.


I've chosen to go with option 6 because it removes any concerns abouth multi-threading (though Joda Time doesn't have many).

Building Numerical Approximations In Erlang

This post is partially complete (I don't have a lot of time to work on it)...

I'm writing this post for a few reasons:
1) I keep telling people that I'm actually going to redo projects or homework that I've done for class, but in Erlang (because Erlang is cool)
2) I might have volunteered to give a short talk on Erlang, so I need to have something prepared in just in case


Erlang documentation is limited due to its low number of users.  There are two excellent books and a great language walk-through at http://learnyousomeerlang.com/contents.


Root finding (a.k.a., where does a function cross zero) is common in scientific computing: it is concernted with finding a number r such that f(r) = 0.  There are several common root finding algorithms: Newton's Method, the Finite-Distance Newton's Method, the Secant Method, and the Bisection Method.  Let's start by considering Newton's Method; it is defined by the sequence xn+1 = xn - f(xn)/f'(xn).  When, you might ask, should we stop getting new xn+1's?  When we are "close" to zero (the root of the equation); "close" is not really codable though.  Or is it?  On a floating-point system (i.e., any computer ever built), there are numbers so small (i.e., close to 0) that, when added to another number, the equal that other number.  By convention, we say that a number n is less than the machine epsilon when (1 + n) = 1.  The machine epsilon is the smallest number emsuch that (1 + em) != 1.

Ok, let's code finding the machine epsilon and determining if a number is smaller than it.

Erlang is simple and elegant.  Let's walk through the lines of code to see what they do.

Line 1: Declare this file as a module (so that we can reuse it later)

Lines 3 & 4: Export three functions with 0, 1, and 1 argument each, respectively

Line 7: If no argument is passed to calculate_machine_epsilon, pass 2 in (base 2 is a simple algorithm)

Line 8 & 9: Make an initial guess about the machine epsilon; we use 1 because base^0 = 1 for any base.  The no indicates to our later code that we are not done guessing machine epsilons.  The no is called an atom in the Erlang language.  Any word starting with with a lower-case letter is an atom.  Note that function names are atoms; this is on purpose.


Lines 11 & 12: An Erlang function doesn't take in variables in the way you'd see in most languages.  Instead, functions are pattern matchers.  At runtime, when an Erlang function is called, the virtual machine looks for any matching functions, if none are found, it throws a bad_match error.  So when you we see

we can guess that the developer indended this function to only have two valid values for the final argument of this function: yes and no (this is a good bet since I wrote the code).  Thus, if you called calculate_machine_epsilon(_Base, LastGuess, 100.5) your code would crash.  In practice, this is helpful because you code for specific patterns and testing will indicate bugs pretty quickly.  You'll note that the first definition of this function  has a _Base argument for the first variable; whereas, the second has Base.  Erlang's compiler warns if you do not use every variable that you've set; the _ prefix to a variable name tells the compiler that you don't intend to use the variable (so it doesn't warn).  Keeping the name the same (except for the _) is useful when somebody tries to figure out what code does months later.   Note that, in this case, the function has the same number of arguments and they appear to be (from the definition) the same "type."  Functions do not need to have the same number of arguments, and the types of each function with the same number of arguments don't need to be the same (think patterns instead of traditional c-style functions).

Line 11 (specific): The second variable is the last guess; the third variable should be yes if the last guess is less than the machine epsilon.  Thus, if it is yes, we're done, so return the last guess.

Line 12 (specific):  The last guess of machine epsilon isn't small enough, so do more.  Note that line 9 passed no to this function with the initial guess of 1.

Line 13: The next guess of the machine epsilon is the current guess divided by the number base.

Line 14: Call this same function again, passing in the guess we just calculated and the value of is_less_than_machine_epsilon.

Lines 16 - 19: A number n is less than the machine epsilon if 1 + n = 1.  These three lines of code show Erlang's pattern matching at its strongest.  I call machine_epsilon_test(number + 1) and pattern match it against machine_epsilon_test(1.0) and machine_epsilon_test(_Other).  In another language, this would be done with an if statement.  Erlang, however, allows you to do it via pattern matching.  This is both elegant and reusable.


You may have noticed that the algorithm is correct for base 2 but not for any other meaningful base.  It doesn't find the true machine epsilon.  Let's update the algorithm to do so:


Now that we have a mechanism for determining if a number is "close" to zero (it is less than the machine epsilon), let's build Newton's Method:

Now, an Emakefile:

And an ant build file (because Ant is great):

It's time for me to run some errands with my wife and daughter, so I'm going to finish the commentary later.

calculate_machine_epsilon(_Base, LastGuess, yes) -> ...

calculate_machine_epsilon(Base, LastGuess, no) -> ...

calculate_machine_epsilon(_Base, LastGuess, yes) ->...

calculate_machine_epsilon(Base, LastGuess, no) -> ...

Using Lucene

Basic Resources
Java Docs: http://lucene.apache.org/java/3_3_0/api/core/index.html
Wiki: http://wiki.apache.org/lucene-java/FrontPage?action=show&redirect=FrontPageEN
Lucene in Action, Chapter 1 (provided by publisher for free): http://www.manning.com/hatcher3/Sample-1.pdf*

* The examples in the book are deprecated, so I suggest downloading the source jar file and looking at the demo classes.


Lucene Query Syntax: http://lucene.apache.org/java/3_3_0/queryparsersyntax.html

Useful Function Calculator

The function calculator at http://wims.unice.fr/wims/en_tool~analysis~function.en.html is useful when approximating functions because it can give you up to 5 derivatives and graph ranges.

Using the Erlang re module (Regular Expressions)

1> re:replace("/var/lib/test/nick", "^.*\/", "hi ",[{return,list}]).

"hi nick"

If  you don't specify the [{return,list}], you get something generally useless:
2>re:replace("/var/lib/test/nick", "^.*\/", "hi ").               
[<<"hi ">>|<<"nick">>]



References:
[1] http://www.erlang.org/doc/man/re.html

Using glpsol (GNU Linear Program Solver)

Suppose you have a linear programming problem like:

maximize x1 - 3x2 + 9x3 -x4
such that:
x1 - 1.5x2 + 0.5x3 - x4 <=90
2x1 + x2 - x3 - x4 <= 15
-x1 -x2 + x3 - x4 <= 9
-x1 + x2 +4x3 - 5x4 <= 10

x1, x2, x3, x4 >= 0

It translates into the input for glpsol:
var x1 >= 0;
var x2 >= 0;
var x3 >= 0;
var x4 >= 0;


maximize z : x1 - (3 * x2) + (9 * x3) -x4;
s.t. x5 : x1 - (1.5 * x2) + (0.5 * x3) - x4 <=90;
s.t. x6 : (2 * x1) + x2 - x3 - x4 <= 15;
s.t. x7 : -x1 -x2 + x3 - x4 <= 9;
s.t. x8 : -x1 + x2 +(4 * x3) - (5 * x4) <= 10;


end;

Once your file is constructed to correctly represent the problem, simply execute glpsol on it:
glpsol -m problem.txt -o problem.out
This assumes that problem.txt is the file you just wrote; the output will be written to problem.out

This problem.out file looks like:
Problem:    problem
Rows:       5
Columns:    4
Non-zeros:  20
Status:     UNDEFINED
Objective:  z = 0 (MAXimum)
   No.   Row name   St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 z            B              0
     2 x5           B              0                          90
     3 x6           B              0                          15
     4 x7           B              0                           9
     5 x8           B              0                          10
   No. Column name  St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 x1           NL             0             0                       < eps
     2 x2           NL             0             0                       < eps
     3 x3           NL             0             0                       < eps
     4 x4           NL             0             0                       < eps
Karush-Kuhn-Tucker optimality conditions:
KKT.PE: max.abs.err = 0.00e+00 on row 0
        max.rel.err = 0.00e+00 on row 0
        High quality
KKT.PB: max.abs.err = 0.00e+00 on row 0
        max.rel.err = 0.00e+00 on row 0
        High quality
KKT.DE: max.abs.err = 9.00e+00 on column 3
        max.rel.err = 9.00e-01 on column 3
        DUAL SOLUTION IS WRONG
KKT.DB: max.abs.err = 0.00e+00 on row 0
        max.rel.err = 0.00e+00 on row 0
        High quality
End of output

The objective function (z) has an optimum value of 0 (the yellow highlight).  The values of the x's are all 0 (because I made up this problem); the green highlight shows the x values.  Note that if an x doesn't show up in that section, it was an entering value at some point and never left to rejoin the basis.

Code War

Thanks to Windward Reporting for sponsoring and CU's Computer Science Depatment for hosting the 2011 Code War.

My team, Team 42, composed of Luke Jeter, Trystan Brinkley-Jones, and me) divided the problem into simpler components:
- Take the cards given to our robot and create a large number of randomly-shuffeled sets of them.
- Score each set, keeping track of the set with the best score
- Play the set with the best score

Factors in scoring:

• Does the move get the flag (does doing so also result in death)?
• Does the move result in death?
• Does the move result in damage?
• Does the move get the robot closer to the flag?

The approach is limited by the number of sets that the AI can process in the allocated time.  If time were not a factor, every card combination could be attempted.  The random nature of the cards, however, is preferable to attempting to build a "good" set of turns because it handles possiblities that the human player ignores.  Moreover, our framework includes the ability to plug in strategies (e.g., use 4 moves and 1 rotate if possible).  Our final product did not use any custom strategies because we found that they didn't, in general, improve our solutions over the random ones.

The "Java" (it was J#) code for my team's AI is:

package PlayerJSharpAI;
import RoboRallyAPI.*;
import java.io.File;
import java.io.FileOutputStream;
import java.io.OutputStream;
import java.util.*;

//import javax.smartcardio.Card;
/**
 * The sample J# AI. Start with this project but write your own code as this is a very simplistic implementation of the AI.
 *
 * Notes about using this in RoboRally:
 * 1. Best practice here is do import for java.* and explicitly specify any System.* classes
 * 2. You can set breakpoints here when running RoboRally by opening this file in VS 2010 and setting them - but the source must be freshly compiled.
 * 3. A property like player.Damage in C# becomes player.get_Damage() and player.setDamage().
 */
public class Team42 implements IPlayer
{
 private Random rand = new Random();
 /**
  * The name of the player.
  */
 public String get_Name()
 {
  return "Team 42";
 }
 /**
  * The avatar of the player. Must be 32 x 32.
  */
 public System.Drawing.Image get_Avatar()
 {
  return null;
 }
 /**
  * Called when your robot must be placed on the board. This is called at the start of the game and each time your robot dies.
  * @param map The game map. There will be no units on this map.
  * @param you Your player object.
  * @param robotStart The position(s) on the map where you can place your robot. This will be a single point unless another robot is on your archive point.
  * @return Where to place your unit (location and direction.
  */
 public PlayerSetup Setup(GameMap map, Player you, System.Drawing.Point[] robotStart)
 {
  return new PlayerSetup(robotStart[0], MapSquare.DIRECTION.NORTH);
 }

 private class Timer {
  private long start = 0;
  private long maxThreshold = 900;
  public Timer() {
   //start = Calendar.getInstance().getTimeInMillis();
  }

  public boolean areWeShortOnTime() {

   /*
   long now = Calendar.getInstance().getTimeInMillis();
   if(now - start > maxThreshold) {
    return true;
   }
   return false;
   */

   return false;
  }


 }

 private ArrayList bestFoundSolution = null;

 /*private class CardHolder {
  public Card card;
  public int frequency = 1;

  public CardHolder(Card card) {
   this.card = card;
  }

  public boolean equals(Object o) {
   CardHolder other = (CardHolder) o;

   return new Integer(card.get_Move()).equals(other.card.get_Move());
  }
 }

 private ArrayList distinctCards(ArrayList allCards) {
  HashMap distinctCards = new HashMap();

  for(int i = 0; i < allCards.size(); i++) {
   CardHolder thisCard = new CardHolder(allCards[i]);
   CardHolder existingCard = distinctCards.get(thisCard);

   if(existingCard == null) {
    distinctCards.put(thisCard, new Integer(0));
   }
   else {
    existingCard.frequency++;
   }
  }

  return new ArrayList(distinctCards.keySet());
 }*/

 private boolean isMove(Card card) {
  if(((int) card.get_Move()) <= 3) {
   return true;
  }
  return false;
 }

 private class CardsPair {
  public ArrayList moves = new ArrayList();
  public ArrayList rotates = new ArrayList();

  public CardsPair(ArrayList cards) {

   for(int i = 0; i < cards.size(); i++) {
    Card card = (Card) cards.get(i);
    if(isMove(card)) {
     moves.add(card);
    }
    else {
     rotates.add(card);
    }
   }

  }
 }

 class RandomSorter implements Comparator {
  Random random = new Random();
  public int compare(Object o1, Object o2) {
   if(random.nextDouble() < 0.5) {
    return -1;
   }
   return 1;
  }
 }

 private ArrayList generateMovesAndRotations(CardsPair pair, int moves, int rotations) {

  if(pair.moves.size() < 4 || pair.rotates.size() < 1) {
   return new ArrayList();
  }

  //ArrayList solutions = new ArrayList();
  //for(int i = 0; i < 10; i++) {

  ArrayList moveCards = chooseX(moves, new ArrayList(pair.moves));
  ArrayList rotateCards = chooseX(rotations, new ArrayList(pair.rotates));

  if(moveCards == null || rotateCards == null) {
   return null;
  }
  moveCards.addAll(rotateCards);

  //Collections.sort(moveCards, new RandomSorter());
  return moveCards;
   //solutions.add(moves);
  //}

  //return solutions;
 }


 private ArrayList chooseX(int x, ArrayList list) {
  ArrayList aSolution = new ArrayList();
  for(int i = 0; i < x; i++) {
   int cardIndex = choseCard(list);
   if(cardIndex < 0) {
    return null;
   }

   Card aCard = (Card) list.get(cardIndex);
   aSolution.add(aCard);
   list.remove(cardIndex);
  }

  return aSolution;
 }


 private ArrayList preprocess(ArrayList cards, int numLockedInCards, int maxSets) {

  if(cards == null) {
   return new ArrayList();
  }

  boolean first = false;
  ArrayList cardSets = new ArrayList();
  for(int j = 0; j < maxSets; j++) {
   ArrayList possibleCards = new ArrayList(cards);
   ArrayList chosenCards = new ArrayList();
   for(int i = 0; i < 5 - numLockedInCards; i++) {
    int chosenIndex = choseCard(possibleCards);
    Card card = (Card) possibleCards.get(chosenIndex);
    chosenCards.add(card);
    possibleCards.remove(chosenIndex);
   }

   cardSets.add(chosenCards);
   if(first) {
    first = false;
    bestFoundSolution = chosenCards;
   }
  }

  return cardSets;
 }

 private int bestPossibleScore = 0;
 private int bestAchievedSolution = 1000;
 private ArrayList bestCards = null;

 private int laserDamage(Utilities.MovePoint mp) {
  //BoardLocation point = new BoardLocation(mp, MapSquare.DIRECTION.NORTH);
  //return Utilities.CalcLaserDamage(map, mp.get_Location());
  return mp.get_Damage();
 }

 private int distanceToFlag(Utilities.MovePoint mp) {
  return Math.abs(currentFlag.get_X() - mp.get_Location().get_MapPosition().get_X())
  + Math.abs(currentFlag.get_Y() - mp.get_Location().get_MapPosition().get_Y());
 }

 public static final int gotFlagAndDied = -1;
 public static final int getFlagAndLived = 1;
 public static final int noFlag = 0;

 private class ScoreHolder {
  public int flagScore = noFlag;
  public int conveyerScore = 0;
 }

 private ScoreHolder getFlagScore(Utilities.MovePoint[] pointsOnPath) {

  ScoreHolder scoreHolder = new ScoreHolder();

  for(int i = 0; i < pointsOnPath.length; i++) {
   Utilities.MovePoint thisPoint = pointsOnPath[i];
   if(distanceToFlag(thisPoint) == 0) {
 
    if(pointsOnPath[pointsOnPath.length - 1].get_Dead()) {
     scoreHolder.flagScore = gotFlagAndDied;
    }
 
    scoreHolder.flagScore = getFlagAndLived;
   }

   if(map.GetSquare(thisPoint.get_Location().get_MapPosition()).get_Conveyor() != null) {
    if(scoreHolder.conveyerScore == 0) {
     scoreHolder.conveyerScore = 500000;
    }
   }

  }

  return scoreHolder;
 }


 private int healthScore(Utilities.MovePoint thisPoint) {
  Object o = map.GetSquare(thisPoint.get_Location().get_MapPosition()).get_Type();
  return 0;

 }

 private int valueOfSolution(ArrayList cards) {

  //Utilities.cardDestination(you.)
  Utilities.MovePoint[] pointsOnPath = Utilities.CardPath(map, you.get_Robot().get_Location(), toArray(cards));
  Utilities.MovePoint mp = pointsOnPath[pointsOnPath.length - 1];
   //Utilities.CardDestination(map, you.get_Robot().get_Location(), toArray(cards));

  int diff = Math.abs(currentFlag.get_X() - mp.get_Location().get_MapPosition().get_X())
  + Math.abs(currentFlag.get_Y() - mp.get_Location().get_MapPosition().get_Y());
  int laserDamage = this.laserDamage(mp);
  int diffScore = 100 * diff;
  int damageScore = 10000 * laserDamage;
  int flagScore = 0;
  int deadScore = 0;
  int healthScore = healthScore(mp);

  if(mp.get_Dead()) {
   deadScore = 1000000;
  }
  boolean dieToGetFlag = true;
  ScoreHolder pathScoreHolder = getFlagScore(pointsOnPath);
  switch (pathScoreHolder.flagScore) {
   case getFlagAndLived : flagScore = 1000000; break;
   case gotFlagAndDied : flagScore = (dieToGetFlag ? 10000000 : 0); break;
   case noFlag : flagScore = 0; break;
   default : flagScore = 0; break;
  }

  int value = diffScore + damageScore + pathScoreHolder.conveyerScore + deadScore - flagScore - healthScore;
  return value;

  //return 999999;
 }

 private void processSolutions(ArrayList setOfSolutions, ArrayList lockedInCards) {
  int solutionsToCheck = setOfSolutions.size();
  for(Iterator i = setOfSolutions.iterator(); i.hasNext(); ) {
   try {
    ArrayList solution = (ArrayList) i.next();
    solution.addAll(lockedInCards);
    int score = this.valueOfSolution(solution);
    if(score < bestAchievedSolution) {
     bestAchievedSolution = score;
     bestCards = solution;
     if(bestAchievedSolution <= bestPossibleScore) {
      return;
     }
    }
    else {
     int y = 121221;
    }
   }
   catch(Exception e) {
    e.printStackTrace();
   }
  }
 }

 private int choseCard(ArrayList cards) {
  if(cards == null || cards.size() == 0) {
   return -1;
  }

  int cardSize = cards.size();

  double randNumBetween1and0 = new Random().nextDouble();

  double x = randNumBetween1and0 * cards.size();
  long rounded = Math.round(x);

  int index = new Double(rounded).intValue() % cards.size();
  if(index >= cardSize) {
   return cardSize - 1;
  }
  return index;
 }

 private ArrayList choose5of9(ArrayList setOfCards, ArrayList lockedInCards) {
  processSolutions(setOfCards, lockedInCards);
  return bestCards;
 }

 private Card[] toArray(ArrayList list) {
  int size = list.size();
  Card[] cards = new Card[size];
  for(int i = 0; i < list.size() ; i++) {
   cards[i] = (Card) list.get(i);
  }

  return cards;
 }

 private ArrayList toArrayList(Card[] cards) {
  ArrayList x = new ArrayList();
  for(int i = 0; i < cards.length; i++) {
   x.add(cards[i]);
  }

  return x;
 }

 private GameMap map;
 private Player you;
 private System.Drawing.Point currentFlag;


 /*
 private ArrayList buildMoveLast(int numLockedCards, CardsPair thisPair) {
  for(int i = 5 - numLockedCards; i >= 1; i--) {
   choseCard(cards)
  }
 }
 */


 private ArrayList generatePreprocessedSolutions(int numLockedCards, CardsPair thisPair) {
  ArrayList possibleSolutions = new ArrayList();

  ArrayList allCards = new ArrayList();
  allCards.addAll(thisPair.moves);
  allCards.addAll(thisPair.rotates);

  if(true) {
   possibleSolutions.addAll(preprocess(allCards, numLockedCards, 10000));
   return possibleSolutions;
  }

  if(numLockedCards == 0) {

   possibleSolutions.addAll(preprocess(allCards, numLockedCards, 500));

   for(int i = 0; i < 10; i++) {
    possibleSolutions.addAll(preprocess(generateMovesAndRotations(thisPair, 4, 1), numLockedCards, 50));
   }
   for(int i = 0; i < 10; i++) {
    possibleSolutions.addAll(preprocess(generateMovesAndRotations(thisPair, 3, 2), numLockedCards, 50));
   }
   for(int i = 0; i < 10; i++) {
    possibleSolutions.addAll(preprocess(generateMovesAndRotations(thisPair, 2, 3), numLockedCards, 50));
   }
  }
  else if (numLockedCards == 1) {

   possibleSolutions.addAll(preprocess(allCards, numLockedCards, 500));

   for(int i = 0; i < 15; i++) {
    possibleSolutions.addAll(preprocess(generateMovesAndRotations(thisPair, 3, 1), numLockedCards, 50));
   }
   for(int i = 0; i < 15; i++) {
    possibleSolutions.addAll(preprocess(generateMovesAndRotations(thisPair, 2, 2), numLockedCards, 50));
   }


  }
  else if (numLockedCards == 2) {

   possibleSolutions.addAll(preprocess(allCards, numLockedCards, 500));

   for(int i = 0; i < 15; i++) {
    possibleSolutions.addAll(preprocess(generateMovesAndRotations(thisPair, 2, 1), numLockedCards, 50));
   }
   for(int i = 0; i < 15; i++) {
    possibleSolutions.addAll(preprocess(generateMovesAndRotations(thisPair, 1, 2), numLockedCards, 50));
   }
   for(int i = 0; i < 15; i++) {
    possibleSolutions.addAll(preprocess(generateMovesAndRotations(thisPair, 3, 0), numLockedCards, 50));
   }

   for(int i = 0; i < 15; i++) {
    possibleSolutions.addAll(preprocess(generateMovesAndRotations(thisPair, 0, 3), numLockedCards, 50));
   }



  }
  else if (numLockedCards == 3) {

   possibleSolutions.addAll(preprocess(allCards, numLockedCards, 500));

   for(int i = 0; i < 15; i++) {
    possibleSolutions.addAll(preprocess(generateMovesAndRotations(thisPair, 1, 1), numLockedCards, 50));
   }
   for(int i = 0; i < 15; i++) {
    possibleSolutions.addAll(preprocess(generateMovesAndRotations(thisPair, 2, 0), numLockedCards, 50));
   }

   for(int i = 0; i < 15; i++) {
    possibleSolutions.addAll(preprocess(generateMovesAndRotations(thisPair, 0, 2), numLockedCards, 50));
   }






  }
  else if (numLockedCards == 4) {

   possibleSolutions.addAll(preprocess(allCards, numLockedCards, 500));

   for(int i = 0; i < 15; i++) {
    possibleSolutions.addAll(preprocess(generateMovesAndRotations(thisPair, 1, 0), numLockedCards, 50));
   }

   for(int i = 0; i < 15; i++) {
    possibleSolutions.addAll(preprocess(generateMovesAndRotations(thisPair, 0, 1), numLockedCards, 50));
   }







  }

  return possibleSolutions;
 }

 private void printOutput(Card[] cards, Card[] lockedInCards, ArrayList chosenMoves) {
  try {
   OutputStream outputStream = new FileOutputStream(new File("c:\\output\\output.txt"));
   write(outputStream, "Dealt cards:\n");
   for(int i = 0; i < cards.length; i++) {
    write(outputStream, cards[i].ToString());
    write(outputStream, "\n");
   }
   write(outputStream, "Locked in cards:\n");
   for(int i = 0; i < lockedInCards.length; i++) {
    write(outputStream, cards[i].ToString());
    write(outputStream, "\n");
   }

   write(outputStream, "Chosen cards:\n");
   for(int i = 0; i < chosenMoves.size(); i++) {
    write(outputStream, chosenMoves.get(i).ToString());
    write(outputStream, "\n");
   }

   outputStream.close();
  } catch(Exception e) {
   e.printStackTrace();
  }

 }

 private void write(OutputStream outputStream, String x) throws Exception {
  outputStream.write(x.getBytes());
 }

 private ArrayList getLockedInCards(int numLockedInCards, Card[] cards) {
  ArrayList lockedInCards = new ArrayList();
  for (int ind = 5 - you.get_NumLockedCards(); ind < 5; ind++) {
   lockedInCards.add(cards[ind]);
  }

  return lockedInCards;
 }
 /**
  * Called each time the system needs another turn. If you do not return a valid turn, the game will randomly move one of your units.
  * This call must return in under 1 second. If it has not returned in 1 second the call will be aborted and a random move will be assigned.
  * @param map The game map with all units on it.
  * @param you Your player object. This is created for each call.
  * @param allPlayers All players including you. This is created for each call.
  * @param priorityNumbers The priority numbers that will be assigned to the cards you return. This order is fixed.
  * @return Your requested turn.
  */
 public PlayerTurn Turn(GameMap map, Player you, Player[] allPlayers, Card[] cards)
 {
  this.map = map;
  this.you = you;

  bestAchievedSolution = 1000000;
  bestCards = null;

  //Timer timer = new Timer();
  // if hurt bad, consider power down
  boolean powerDown = false;
  if ((you.get_Damage() > 5) && (rand.nextInt(3) == 0))
   powerDown = true;
  // get 40 sets, pick the one that's closest to the flag
  Card[] best = null;
  int bestDiff = Integer.MAX_VALUE;
  int okDiff = rand.nextInt(3);
  Player.FlagState fs = null;
  for (int ind = 0; ind < you.get_FlagStates().length; ind++)
   if (!you.get_FlagStates()[ind].get_Touched())
   {
    fs = you.get_FlagStates()[ind];
    break;
   }
  System.Drawing.Point ptFlag = fs == null ? new System.Drawing.Point(5, 6) : fs.get_Position();
  currentFlag = fs.get_Position();
  for (int turnOn = 0; turnOn < 1; turnOn++)
  {
   // pick 5 (or fewer if locked) random cards
   Card[] moveCards = new Card[5];
   //boolean[] cardUsed = new boolean[cards.length];

   int numLockedCards = you.get_NumLockedCards();
   ArrayList myCards = toArrayList(cards);
   CardsPair thisPair = new CardsPair(myCards);


   //possibleSolutions.addAll(preprocess(myCards, numLockedCards, 500));

   ArrayList possibleSolutions = generatePreprocessedSolutions(numLockedCards, thisPair);
   ArrayList chosenCards = choose5of9(possibleSolutions, getLockedInCards(numLockedCards, you.get_Cards()));
   //printOutput(cards, you.get_Cards(), chosenCards);

   /*
   for (int ind = 0; ind < 5 - you.get_NumLockedCards(); ind++)
    while (true)
    {
     int index = ind; // rand.nextInt(cards.length);
     if (cardUsed[index])
      continue;
     moveCards[ind] = cards[index];
     cardUsed[index] = true;
     break;
    }
    */
   // add in the locked cards
   /*
   for (int ind = 5 - you.get_NumLockedCards(); ind < 5; ind++)
    moveCards[ind] = you.get_Cards()[ind];
   */

   return new PlayerTurn(toArray(chosenCards), false);
   /*

   Utilities.MovePoint mp = Utilities.CardDestination(map, you.get_Robot().get_Location(), moveCards);
   if (!mp.get_Dead())
   {
    int diff = Math.abs(ptFlag.get_X() - mp.get_Location().get_MapPosition().get_X()) + Math.abs(ptFlag.get_Y() - mp.get_Location().get_MapPosition().get_Y());
    if (diff <= okDiff)
     return new PlayerTurn(moveCards, powerDown);
    if (diff < bestDiff)
    {
     bestDiff = diff;
     best = moveCards;
    }
   }
   */
  }
  return new PlayerTurn(best, powerDown);
 }
}