/** \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;

/**
 * <h3>
 * AntMonteCarlo
 * </h3>
 * <h3>
 *  The problem:
 * </h3>
 * <blockquote> 
 * <p>
 * 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?
 * </p>
 * <p>
 * According to a follow up question: the ants are random ants
 * </p> 
 * </blockquote>
 * <p>
 * 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:
 * </p>
 * <ul>
 * <li> {0,0} is the top left corner </li>
 * <li> {0,7} is the top right corner </li>
 * <li> {7,0} is the bottom left corner</li>
 * <li> {7,7} is the bottom right corner (diagonally across the board from {0,0})</li>
 * </ul> 
 * </p>
 * <p>
 * The ants move at random to a new square. Ants must always move, they can't stay on the
 * same square.
 * </p>
 * <p>
 * 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
 * </p>
 * <p>
 * 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.
 * </p>
 * <p>
 * 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.
 * </p>
 * <p>
 * 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.
 * </p>
 * <p> 
 * Apr 4, 2015
 * </p>
 * 
 * @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;
        }
    }
    
    /**
     * <p>
     * Point
     * </p>
     * <p>
     * A point on a board, indexed by columns and rows.
     * </p>
     * 
     * @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
    
    /**
     * <p>
     * Ant 
     * </p>
     * <p>
     * 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.
     * </p>
     * 
     * 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 {
        /**
         * <p>
         * 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.
         * </p>
         * <p>
         * Recall that nextInt(n) is an integer function that returns a uniform distribution
         * between 0..n-1.
         * </p> 
         * @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 );
    }

}