Addepar Ants (solution to https://addepar.com/challenge.php)

MyAnt.java

import ants.Action;
import ants.Ant;
import ants.Direction;
import ants.Surroundings;
import ants.Tile;

import java.awt.Point;
import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * MyAnt works like this. An Ant can only be in one of the following modes:
 * Going Home (to drop food):
 *      If at home, drop food and go into exploring mode
 *      Else keep going home
 * Going to Food (to pick up food):
 *      If another ant tells me that where I am going has no food, explore from current position
 *      Else if I am at my destination and there is food, pick up food, go into going-home mode (reverse my path)
 *      If I am at my destination, and there is no food, start exploring from here
 *      Else keep going towards my destination
 * Exploring (default one at spawn):
 *      If I am at home try seeing if there is a best plan*.
 *          If there is best plan, select it and set mode to Going-to-Food.
 *      Else if there is no best plan, move on
 *      If I just found food, go into Going Home mode and gather the food
 * Last case is I have no best plan and no food to gather:
 *      In this case move to a neighbouring unvisited cell which has highest food/ant ratio
 *      If there are multiple such choices, pick a random one
 *      If there are no unvisited cells left, backtrack to where I came from and mark this cell as a deadend
 * ---------------------------------------------------------------------------
 * Best plan selection algorithm:
 *  With probability IGNORE_BEST an ant discards the best solution and wanders around
 *  Else with probability AFFINITY_BEST an ant selects the cell to go to which has highest food minus distance_from_home value
 *  Else with probability AFFINITY_BEST an ant selects the second best such cell and so on.
 */

public class MyAnt implements Ant {

    Set<Point> visitedWhileExploring = new HashSet<Point>();
    Point current = new Point();
    Mode mode = Mode.Exploring;
    Route currentPlan = new Route();
    Knowledge knowledge = Knowledge.build();

    @Override
    public Action getAction(Surroundings surroundings) {
        knowledge.remember(current, surroundings, null);

        if (currentPlan.isEmpty()) {
            switch (mode) {
                case GoingHome: {
                    mode = Mode.Exploring;
                    return Action.DROP_OFF;
                }
                case GoingToFood: {
                    if (surroundings.getCurrentTile().getAmountOfFood() > 0) {
                        currentPlan = knowledge.get(current).directionFromHome.getReverseRoute();
                        mode = Mode.GoingHome;
                        return Action.GATHER;
                    } else { // oh no someone already collected the food i was supposed to pick up, ok explore
                        currentPlan = (Route) knowledge.get(current).directionFromHome.clone();
                        mode = Mode.Exploring;
                        break;
                    }
                }
                default:
                case Exploring: {
                    currentPlan = knowledge.getBestPlan();
                    if (currentPlan == null || currentPlan.isEmpty()) {
                        currentPlan = new Route();
                    } else {
                        mode = Mode.GoingToFood;
                    }
                }
            }
        }

        switch (mode) {
            case GoingHome: {
                Route bestRoute = knowledge.get(current).directionFromHome;
                if (bestRoute.size() < currentPlan.size()) {
                    currentPlan = bestRoute.getReverseRoute();  // there is a better way to go home some ant tells me
                }
                final Direction next = currentPlan.removeFirst();
                current = Route.getNextPoint(current, next);
                return Action.move(next);
            }

            case GoingToFood: {
                final Point destination = currentPlan.getEndPoint(current);
                if (knowledge.get(destination).food <= 0) {  // someone tells me where i am going has no food anymore; wander
                    currentPlan = (Route) knowledge.get(current).directionFromHome.clone();
                    mode = Mode.Exploring;
                } else {
                    final Direction next = currentPlan.removeFirst();
                    current = Route.getNextPoint(current, next);
                    return Action.move(next);
                }
            }

            default:
            case Exploring: {
                knowledge.remember(current, surroundings, currentPlan);
                visitedWhileExploring.add(current);

                final int foodFound = (current.x == 0 && current.y == 0) ? 0 : surroundings.getCurrentTile().getAmountOfFood();

                if (foodFound > 0) {
                    visitedWhileExploring.clear();
                    currentPlan = knowledge.get(current).directionFromHome.getReverseRoute();
                    mode = Mode.GoingHome;
                    return Action.GATHER;
                } else {
                    Direction next = getBestChoiceAroundHere(surroundings, false, false);
                    if (next == null) {
                        if (currentPlan.isEmpty()) { // WTFLOL - maybe select a best plan here?
                            next = getBestChoiceAroundHere(surroundings, true, false);
                            if (next == null) {
                                next = getBestChoiceAroundHere(surroundings, true, true);
                            }
                            currentPlan.add(next);
                            current = Route.getNextPoint(current, next);
                        } else { // uh oh i am stuck, back track and mark this cell as a deadend
                            knowledge.deadEnds.add(current);
                            next = Route.getOppositeDirection(currentPlan.removeLast());
                            current = Route.getNextPoint(current, next);
                            visitedWhileExploring.remove(current);
                        }
                    } else {
                        currentPlan.add(next);
                        current = Route.getNextPoint(current, next);
                    }
                    return Action.move(next);
                }
            }
        }
    }

    Direction getBestChoiceAroundHere(Surroundings surroundings, boolean ignoreVisitedInfo, boolean ignoreDeadendInfo) {
        int currentBestScore = Integer.MIN_VALUE;
        Direction best = null;
        for (Direction d : Route.getShuffledDirections()) {
            final int score = score(surroundings, d, ignoreVisitedInfo, ignoreDeadendInfo);
            if (score > currentBestScore) {
                currentBestScore = score;
                best = d;
            }
        }
        return best;
    }

    int score(Surroundings surroundings, Direction next, boolean ignoreVisitedInfo, boolean ignoreDeadendInfo) {
        final Point p = Route.getNextPoint(current, next);
        if ((!ignoreVisitedInfo && visitedWhileExploring.contains(p)) || (!ignoreDeadendInfo && knowledge.deadEnds.contains(p))) {
            return Integer.MIN_VALUE;
        }
        final Tile t = surroundings.getTile(next);
        return t.isTravelable() ? t.getAmountOfFood() - t.getNumAnts() : Integer.MIN_VALUE;
    }

    @Override
    public byte[] send() {
        return null;
    }

    @Override
    public void receive(byte[] data) {
    }
}

/*----------------------------------------------------------------*/
enum Mode {
    Exploring, GoingHome, GoingToFood
}

/*----------------------------------------------------------------*/
class Route extends ArrayDeque<Direction> implements Serializable {
    private static final long serialVersionUID = 2930709067881007325L;

    static Direction getOppositeDirection(final Direction d) {
        switch (d) {
            case NORTH: return Direction.SOUTH;
            case EAST:  return Direction.WEST;
            case WEST:  return Direction.EAST;
            case SOUTH: return Direction.NORTH;
            default:    return null;
        }
    }

    Route getReverseRoute() {
        final Route reverse = new Route();
        for (Direction d : this) {
            reverse.addFirst(getOppositeDirection(d));
        }
        return reverse;
    }

    Point getEndPoint(Point current) {
        Point temp = (Point) current.clone();
        for (Direction d : this) {
            temp = getNextPoint(temp, d);
        }
        return temp;
    }

    static Point getNextPoint(Point current, Direction next) {
        int nx = current.x, ny = current.y;
        switch (next) {
            case NORTH: ny++; break;
            case EAST:  nx++; break;
            case WEST:  nx--; break;
            case SOUTH: ny--; break;
        }
        return new Point(nx, ny);
    }

    static Iterable<Direction> getShuffledDirections() {
        final List<Direction> directions = getDirections();
        Collections.shuffle(directions);
        return directions;
    }

    static List<Direction> getDirections() {
        return Arrays.asList(Direction.values());
    }
}

/*----------------------------------------------------------------*/
class Cell implements Serializable {
    private static final long serialVersionUID = 1547019474924868844L;

    Route directionFromHome; // TODO: Instead of directions to home, each cell stores number of steps away from home    
    int food;

    Cell(int food, Route directionFromHome) {
        this.food = food;
        this.directionFromHome = (Route) directionFromHome.clone();
    }

    void merge(Cell c) {
        food = Math.min(food, c.food);  // food never goes up (except at home) so store latest info
        if (isUnknownDirection() || (!c.isUnknownDirection() && directionFromHome.size() > c.directionFromHome.size())) {
            directionFromHome = (Route) c.directionFromHome.clone();    // store shorter route
        }
    }

    int score() {
        return isUnknownDirection() ? Integer.MIN_VALUE : food - directionFromHome.size();
    }

    boolean isUnknownDirection() {
        return directionFromHome == null || directionFromHome.isEmpty();
    }
}

/*----------------------------------------------------------------*/
class Knowledge extends HashMap<Point, Cell> implements Serializable {
    private static final long serialVersionUID = 5838028995899578367L;

    private static Knowledge instance;

    static Knowledge build() {
        return instance == null ? instance = new Knowledge() : instance;
    }

    Set<Point> deadEnds = new HashSet<Point>();

    /**
     * Read class comment on how this is done
     * Basically if we always select best known plan, we don't get to explore that much
     * Exploring is crucial to find better food sources
     * If we randomly select plans, we waste time going to far away meagre foods
     * If we send everyone to same food source, by the time many ants go there that food is gone
     * Strike a balance between exploring and selecting good sources
     */
    Route getBestPlan() {
        final double IGNORE_BEST = 0.10, AFFINITY_BEST = 0.65;
        if (Math.random() < IGNORE_BEST) {
            return null;
        }

        final PriorityQueue<PQNode<Cell, Integer>> pq = new PriorityQueue<PQNode<Cell, Integer>>();
        for (Cell c : values()) {
            if (c.food > 0 && c.score() > Integer.MIN_VALUE) {
                pq.add(new PQNode(c.score(), c));
            }
        }

        Cell best = null;
        while (!pq.isEmpty()) {
            best = pq.poll().e;
            if (Math.random() < AFFINITY_BEST) {
                break;
            }
        }

        return best == null || best.isUnknownDirection() || best.food <= 0 ? null : (Route) best.directionFromHome.clone();
    }

    void remember(Point current, Surroundings surroundings, Route routeFromHome) {
        if (routeFromHome == null) {
            routeFromHome = new Route();
        }
        Tile tile = surroundings.getCurrentTile();
        merge(current, new Cell(tile.getAmountOfFood(), (Route) routeFromHome.clone()));
        for (Direction d : Route.getDirections()) {  // not only remember this cell but remember things around me
            tile = surroundings.getTile(d);
            if (tile.isTravelable()) {
                final Point tempPoint = Route.getNextPoint(current, d);
                final Route tempRoute = (Route) routeFromHome.clone();
                if (!routeFromHome.isEmpty()) {
                    tempRoute.addLast(d);
                }
                merge(tempPoint, new Cell(tile.getAmountOfFood(), tempRoute));
            }
        }
    }

    private void merge(Point p, Cell newCell) {
        if (p.x == 0 && p.y == 0) {
            return;
        }
        final Cell oldCell = get(p);
        if (oldCell == null) {
            put(p, newCell);
        } else {
            oldCell.merge(newCell);
        }
    }
}

/*----------------------------------------------------------------*/
// TODO: Use some kind of custom serializer/deserializer instead of this heavy weight
class ObjectIO<V> {
    byte[] toByteArray(V obj) {
        final ByteArrayOutputStream baos = new ByteArrayOutputStream();
        try {
            final ObjectOutputStream oos = new ObjectOutputStream(baos);
            oos.writeObject(obj);
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(-1);

        }
        return baos.toByteArray();
    }

    V fromByteArray(byte[] bytes) {
        final ByteArrayInputStream bais = new ByteArrayInputStream(bytes);
        V t = null;
        try {
            final ObjectInputStream ois = new ObjectInputStream(bais);
            t = (V) ois.readObject();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(-1);
        }
        return t;
    }
}

/*----------------------------------------------------------------*/
class PQNode<E, C extends Comparable> implements Comparable<PQNode> {
    C c;
    E e;

    PQNode(C c, E e) {
        this.c = c;
        this.e = e;
    }

    @Override
    public int compareTo(PQNode p) {
        return p.c.compareTo(c);
    }
}