/** \file * * Apr 3, 2015 * * Copyright Ian Kaplan 2015 * * @author Ian Kaplan, www.bearcave.com, iank@bearcave.com */ package ants; import java.util.Random; import org.apache.commons.math3.stat.descriptive.moment.Mean; import org.apache.commons.math3.stat.descriptive.moment.StandardDeviation; /** *

*

### * The problem: *

*
*

* Two ants start in opposite corners of a regular chessboard. * Every 10 seconds, they move from the center of the square they're on to the * center of an adjacent square. How long until they both land on the same * square? How long until their paths cross (Ant A moving from square K to L and * Ant B moving from square L to K)? What happens if we allow the ants to move * diagonally? What happens if we restrict ants from moving to their immediately * previous square? *

*

* According to a follow up question: the ants are random ants *

*
*

* The chess board is an 8x8 matrix. The matrix is defined by {row,col} coordinates, * which correspond to the rows and columns of the chess board: *

*
*
• {0,0} is the top left corner
• *
• {0,7} is the top right corner
• *
• {7,0} is the bottom left corner
• *
• {7,7} is the bottom right corner (diagonally across the board from {0,0})
• *
*

*

* The ants move at random to a new square. Ants must always move, they can't stay on the * same square. *

*

* These are Java 1.7.0_55 ants. The statistics functions are from the Apache commons Math library * (commons-math3-3.4.1.jar) from apache.org *

*

* This problem came up as a job interview question. I had a non-technical phone interview, sent them * my resume and two papers I've written. Then I sent them this code. And I never heard back from them. *

*

* If you decide to use this code for an interview, you might keep that in mind. The person I did the phone * interview with claimed that this problem could be solved with half an hour to an hour of work. Obviously * my solution is a lot more time consuming. Perhaps I missed something and there is a much simpler solution. *

*

* Although this is obviously a completely synthetic problem, it has some similarity to Monte Carlo codes that * are used to price financial instruments like American options which have no analytical solution. *

*

* Apr 4, 2015 *

* * @author Ian Kaplan, iank@bearcave.com */ public class AntMonteCarlo { private final static long SEED = 3191; // a random seed value // middle contains all of the move offsets from a point in the middle of the board (e.g., not on a corner or on an // edge) protected final static Point[] middle = new Point[] { new Point(0,-1), new Point(-1, 0), new Point(0, 1), new Point(1, 0), new Point(-1, -1), new Point(-1, 1), new Point(1, 1), new Point(1, -1)}; protected final static int COL_MAX = 7; // e.g., 0..7 protected final static int ROW_MAX = 7; // e.g., 0..7 protected class AntStat { final double avgMoves; final double stdDev; final double meanError; public AntStat(double avgMoves, double stdDev, double meanError) { this.avgMoves = avgMoves; this.stdDev = stdDev; this.meanError = meanError; } } /** *

* Point *

*

* A point on a board, indexed by columns and rows. *

* * @author Ian Kaplan, iank@bearcave.com */ protected static class Point { int row, col; public Point() {} public Point(Point p) { this.row = p.row; this.col = p.col; } public Point(int row, int col) { this.row = row; this.col = col; } public void set(int newRow, int newCol) { this.row = newRow; this.col = newCol; } public void set(Point p) { this.row = p.row; this.col = p.col; } Point incr(Point offset) { this.row = this.row + offset.row; this.col = this.col + offset.col; return this; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; Point other = (Point) obj; if (row != other.row) return false; if (col != other.col) return false; return true; } @Override public int hashCode() { int poly = this.col + this.col * this.row; return poly; } @Override public String toString() { String s = "{" + this.row + "," + this.col + "}"; return s; } } // class Point /** *

* Ant *

*

* An ant has a current position and a last position. The last position exists * so that we can determine if the ant paths cross and to avoid moving to the * previous position if that is what is being simulated. *

* * Apr 4, 2015 * * @author Ian Kaplan, iank@bearcave.com */ protected static class Ant { Point current; Point last = null; public Ant(int startRow, int startCol) { current = new Point(startRow, startCol); } /** The ant has a new position */ public void newPos(int newRow, int newCol) { if (last == null) { last = new Point(); } last.set(current); current.set(newRow, newCol); } /** return true if "other" collides with "this" ant, false otherwise */ public boolean collide(Ant other) { boolean sameSquare = this.current.equals(other.current); return sameSquare; } /** return true if the new move is to the same position as the last position */ public boolean equalLast(int newRow, int newCol) { boolean eqLast = false; if (last != null) { eqLast = (last.row == newRow && last.col == newCol); } return eqLast; } // equalLast /** return true if the ant paths cross, as defined in the problem definition */ public boolean pathsCross( Ant antB ) { boolean crossed = false; if (this.last != null && antB.last != null) { crossed = this.current.equals( antB.last ) && antB.current.equals(this.last); } return crossed; } } protected interface IAntMover { void makeMove(Ant ant, boolean useDiag); int antCollision(boolean useDiag); } protected abstract class AntMoverBase implements IAntMover { /** *

* Get the random point offset for a legal move from the current position. If an offset * is selected that his not legal, another random draw is made. *

*

* Recall that nextInt(n) is an integer function that returns a uniform distribution * between 0..n-1. *

* @param p the board point where the ant current resides. * @param useDiag * @return an offset point, with the row and column offset */ public Point getMoveOffset(Point p, boolean useDiag) { Point offset = null; int n = useDiag ? 8 : 4; while (offset == null) { int ix = mRand.nextInt(n); Point t = middle[ix]; int newRow = p.row + t.row; int newCol = p.col + t.col; if ((newRow >= 0 && newRow <= ROW_MAX) && (newCol >= 0 && newCol <= COL_MAX)) { offset = t; } } return offset; } // getMoveOffset } // AntMoverBase /** Ant moves with back-tracking allowed */ protected class AntMover extends AntMoverBase { /** make a move that is not constrained by the previous position */ public void makeMove( Ant ant, boolean useDiag ) { Point p = ant.current; Point offset = getMoveOffset(p, useDiag); int newRow = p.row + offset.row; int newCol = p.col + offset.col; ant.newPos(newRow, newCol); } public int antCollision(boolean useDiag) { int moves = 0; Ant antA = new Ant(0,0); Ant antB = new Ant(ROW_MAX, COL_MAX); while (! antA.collide(antB)) { this.makeMove(antA, useDiag); this.makeMove(antB, useDiag); moves++; } return moves; } } // class AntMover /** Ant moves with no back-tracking */ protected class NoBackAntMover extends AntMoverBase { /** Make a move that is constrained by the previous position */ public void makeMove( Ant ant, boolean useDiag ) { Point p = ant.current; int newRow = 0; int newCol = 0; do { Point offset = getMoveOffset(p, useDiag); newRow = p.row + offset.row; newCol = p.col + offset.col; } while (ant.equalLast(newRow, newCol)); ant.newPos(newRow, newCol); } public int antCollision(boolean useDiag) { int moves = 0; Ant antA = new Ant(0,0); Ant antB = new Ant(ROW_MAX, COL_MAX); while (! antA.collide(antB)) { this.makeMove(antA, useDiag); this.makeMove(antB, useDiag); moves++; } return moves; } } // class NoBackAntMover /** Calculate the time it takes ant paths to cross */ protected class AntPathCollision extends AntMoverBase { /** make a move that is not constrained by the previous position */ public void makeMove( Ant ant, boolean useDiag ) { Point p = ant.current; Point offset = getMoveOffset(p, useDiag); int newRow = p.row + offset.row; int newCol = p.col + offset.col; ant.newPos(newRow, newCol); } public int antCollision(boolean useDiag) { int moves = 0; Ant antA = new Ant(0,0); Ant antB = new Ant(ROW_MAX, COL_MAX); while (! antA.pathsCross(antB)) { this.makeMove(antA, useDiag); this.makeMove(antB, useDiag); moves++; } return moves; } } private Random mRand = new Random(SEED); /** Find the mean time (in seconds, where each move is 10 seconds) that it takes the ants * to collide on the same square. * * @param maxIter number of iterations over which to run the simulation * @param mover a class that provides a function to move the ants around the board * @param useDiag true if the board diagonal can be used, false otherwise * @return the mean, standard deviation and error of the mean for the simulation */ AntStat meanCollision(int maxIter, IAntMover mover, boolean useDiag) { double[] collisionTimes = new double[maxIter]; int i; for (i = 0; i < maxIter; i++) { int numMoves = mover.antCollision(useDiag); int seconds = numMoves * 10; collisionTimes[i] = seconds; } // for StandardDeviation stdDev = new StandardDeviation(); Mean calcMean = new Mean(); double sigma = stdDev.evaluate( collisionTimes ); double error = sigma / Math.sqrt( i ); double mean = calcMean.evaluate( collisionTimes ); AntStat stats = new AntStat(mean, sigma, error ); return stats; } void getAntStatistics(int maxIter) { System.out.println("Using " + maxIter + " iterations"); System.out.println(); System.out.println("All values are in seconds, where one move on the board is 10 seconds"); System.out.println("The error values are the errors of the mean"); System.out.println(); IAntMover mover = new AntMover(); AntStat collision = meanCollision(maxIter, mover, false); AntStat diagCollision = meanCollision(maxIter, mover, true ); System.out.format("collision (no diag) mean = %4.2f, stdDev = %4.2f, error = %1.5f\n", collision.avgMoves, collision.stdDev, collision.meanError ); System.out.format("collision (w/diag) mean = %4.2f, stdDev = %4.2f, error = %1.5f\n", diagCollision.avgMoves, diagCollision.stdDev, diagCollision.meanError ); System.out.println(); IAntMover noBackMover = new NoBackAntMover(); AntStat noBackCollision = meanCollision(maxIter, noBackMover, false); AntStat noBackDiagCollision = meanCollision(maxIter, noBackMover, true ); System.out.format("no back-track collision (no diag) mean = %4.2f, stdDev = %4.2f, error = %1.5f\n", noBackCollision.avgMoves, noBackCollision.stdDev, noBackCollision.meanError ); System.out.format("no back-track collision (w/diag) mean = %4.2f, stdDev = %4.2f, error = %1.5f\n", noBackDiagCollision.avgMoves, noBackDiagCollision.stdDev, noBackDiagCollision.meanError ); System.out.println(); IAntMover pathCollision = new AntPathCollision(); // The path overlap without use of the diagonal seems to take a very long time. So this simulation // was not run. // AntStat antPathCollision = meanCollision(maxIter, pathCollision, false); AntStat antPathDiagCollision = meanCollision(maxIter, pathCollision, true ); /* System.out.format("path overlap (no diag) mean = %4.2f, stdDev = %4.2f, error = %1.5f\n", antPathCollision.avgMoves, antPathCollision.stdDev, antPathCollision.meanError ); */ System.out.format("path overlap (w/diag) mean = %4.2f, stdDev = %4.2f, error = %1.5f\n", antPathDiagCollision.avgMoves, antPathDiagCollision.stdDev, antPathDiagCollision.meanError ); } public static void main(String[] args) { final int MAX_ITER = 1000000; AntMonteCarlo antWalks = new AntMonteCarlo(); antWalks.getAntStatistics( MAX_ITER ); } }