Abbott's Revenge

[Garrett Rowe]

One cool resource I've found for interesting programming questions is The online-judge problem set archive. Although Java support for the online submission portion of the site leaves a lot to be desired, (currently only Java 1.2 is supported with very limited support for java.io.* operations), there are plenty of problems that span a whole range of difficulties. The problem I'm currently pounding my head against is problem #816 Abbott's Revenge. This problem combines a slew of programming goodies, from parsing a domain-specific language, to finding a good abstraction of the problem (my current headache), to discovering a good algorithm to solve the maze. I figured it might be fun to discuss one or several of the interesting facets of this problem here.

To the mods: I'm not sure if its OK to post problems from this site here, but I figured since these weren't active contest problems, but more like individual programming brain teasers it might not be a problem. There are no prizes associated with solving the problems as far as I'm aware, just the general feeling of accomplishment. If it is an issue, just let me know and I'll cease and desist.

[Garrett Rowe]

More fun interactive mazes designed by Robert Abbott can be found here.

[Garrett Rowe]

As far as the problem abstraction goes, this is what I'm currently thinking.

interface Cell
{
   boolean isGoal();
   CellCoordinates getCoordinates();
   List<Cell> listCellsAvailableFrom(Direction d);
   Direction directionTo(Cell c) throws CellNotAdjacentException;
}
 
enum Direction {NORTH, SOUTH, EAST, WEST;}
 
interface CellCoordinates
{
   int getX();
   int getY();
}

Maybe I'll use this as a jumping-off point and see where it leads me, although I'm sure the TDD guys will say I'm getting way ahead of myself. I just not as comfortable with their style yet.

[Steve Fahlbusch]

Garrett,

On monday saw your post at work and as soon as i got home had to spend a few minutes banging this out in python - it's a great classic problem with a twist.

How goes it for you?

Just for my own interest. Did you use a forwards or backwards evaluation approach to solving the path (did backwards myself)? And as to enumerating the solution domain did you use a depth first search or breadth first search (since it seems to want a minimal solution, i did the BFS and punted at the first solution).

thanks for the link

[Gabriel Claramunt]

Very interesting... It hook me up immediately!
Seems "easy" to solve : create a directed graph where the nodes represents the "hallways" and the arcs the "turns" connecting them (Yes, is somehow the "complement" of the maze's draw). Then, with Dijktra's algorithm should be a piece of cake (and is DFS)
Too lazy to code it right now, later I'll do it as an excuse to practice Ruby.

[Piet Verdriet]

Thanks for posting this fun puzzle! For those interested, here's how I solved it:

import java.io.*;
import java.util.*;
 
// AbbottsRevenge
class AbbottsRevenge {
 
    public AbbottsRevenge(String fileName) throws IOException {
        Scanner data = new Scanner(new File(fileName));
        while(data.hasNextLine()) {
            String name = data.nextLine().trim();
            if(name.equals("END")) break;
            MazeSolver solver = new MazeSolver(data.nextLine().trim());
            Maze maze = new Maze(name, data);
            solver.solve(maze);
            System.out.println(solver);
        }
    }
 
    public static void main(String[] args) throws IOException {
        new AbbottsRevenge("data.txt");
        // contents of data.txt:
        /*
                SAMPLE
                3 1 N 3 3
                1 1 WL NR *
                1 2 WLF NR ER *
                1 3 NL ER *
                2 1 SL WR NF *
                2 2 SL WF ELF *
                2 3 SFR EL *
                0
                NOSOLUTION
                3 1 N 3 2
                1 1 WL NR *
                1 2 NL ER *
                2 1 SL WR NFR *
                2 2 SR EL *
                0
                AtlantaMaze
                4 2 N 4 3
                1 1 WL NR *
                1 2 WF EFR NLR *
                1 3 WFL EFR NL *
                1 4 ER NL *
                2 1 NFR SFL WL *
                2 2 NFL SFLR WFRL EL *
                2 3 NF SF WFLR EFLR *
                2 4 ELR NF SR *
                3 1 SL WR *
                3 2 NF EFL WR SLR *
                3 3 EFL WL SLR *
                3 4 EL SR *
                0
                END
        */
    }
 
}
 
// Maze
class Maze {
    
    String name;
    Map<Point, Crossing> crossings;
    
    public Maze(String n, Scanner data) {
        name = n;
        crossings = new HashMap<Point, Crossing>();
        process(data);
    }
    
    public Direction getNextDirection(Point current, Direction last) {
        Crossing c = crossings.get(current);
        return c.popDirection(last);
    }
    
    private void process(Scanner data) {
        while(data.hasNextLine()) {
            String line = data.nextLine().trim();
            if(line.equals("0")) break;
            String[] array = line.split("\\s+");
            Crossing c = new Crossing(new Point(array[0], array[1]));
            for(int i = 2; i < array.length-1; i++) {
                for(int j = 1; j < array[i].length(); j++) {
                    c.addConnection(array[i].charAt(0)+""+array[i].charAt(j));
                }
            }
            crossings.put(c.point, c);
        }
    }
}
 
// Crossing
class Crossing {
    
    Point point;
    Map<Direction, Stack<Direction>> connections;
    
    public Crossing(Point p) {
        point = p;
        connections = new HashMap<Direction, Stack<Direction>>();
    }
    
    public void addConnection(String s) {
        Direction bearing = Direction.getDiretion(String.valueOf(s.charAt(0)));
        Direction heading = Direction.getDiretion(s);
        Stack<Direction> allHeadings = connections.remove(bearing);
        if(allHeadings == null) allHeadings = new Stack<Direction>();
        allHeadings.push(heading);
        connections.put(bearing, allHeadings);
    }
    
    public Direction popDirection(Direction d) {
        Stack<Direction> stack = connections.get(d);
        return stack == null || stack.isEmpty() ? null : stack.pop();
    }
}
 
// Point
class Point {
 
    int row; 
    int column;
    
    public Point(String r, String c) {
        this(Integer.parseInt(r), Integer.parseInt(c));
    }
    
    public Point(int r, int c) {
        row = r; 
        column = c;
    }
    
    public boolean equals(Object o) {
        Point that = (Point)o;
        return this.row == that.row && this.column == that.column;
    }
    
    public int hashCode() {
        return row*37 ^ column*43;
    }
    
    public Point move(Direction d) {
        switch(d) {
        case NORTH : return new Point(row-1, column);
        case SOUTH : return new Point(row+1, column);
        case EAST  : return new Point(row, column+1);
        default    : return new Point(row, column-1);
        }
    }
    
    public String toString() {
        return "("+row+","+column+")";
    }
}
 
// MazeSolver
class MazeSolver {
    
    Point finish;
    Maze maze;
    Stack<Decision> stack;
    List<Decision> path;
    
    public MazeSolver(String s) {
        String[] array = s.split("\\s+");
        Point start = new Point(array[0], array[1]);
        Direction bearing = Direction.getDiretion(array[2]);
        finish = new Point(array[3], array[4]);  
        stack = new Stack<Decision>();
        stack.push(new Decision(start, bearing));
    }
    
    private void move(Direction d) {
        Point next = stack.peek().point.move(d);
        stack.push(new Decision(next, d));
    }
 
    private Direction lastDirection() {
        return stack.peek().direction;
    }
    
    private Point currentPoint() {
        return stack.peek().point;
    }
    
    private void removeCycles() {
        if(stack.size() == 1) return;
        path = new ArrayList<Decision>(stack);
        for(int i = 0; i < path.size(); i++) {
            Decision temp = path.get(i);
            int start = path.indexOf(temp);
            int end = path.lastIndexOf(temp);
            while(end > start) {
                path.remove(end--);
            }
        }
    }
    
    public void solve(Maze m) {
        maze = m;
        move(lastDirection());
        while(true) {
            Direction next = maze.getNextDirection(
                    currentPoint(), lastDirection());
            if(next != null) {
                move(next);
            } else {
                stack.pop();
            }
            if(currentPoint().equals(finish) || stack.size() == 1) break;
        }
        removeCycles();
    }
    
    public String toString() {
        StringBuilder b = new StringBuilder(maze.name).append('\n').append(' ');
        if(path == null)
            return b.append(" No Solution Possible").toString();
        for(int i = 0; i < path.size(); i++) {
            if(i > 0 && i%10 == 0) b.append('\n').append(' ');
            b.append(' ').append(path.get(i).point);
        }
        return b.toString();
    }
}
 
// Decision
class Decision {
    
    Point point;
    Direction direction;
    
    public Decision(Point p, Direction d) {
        point = p;
        direction = d;
    }
    
    public boolean equals(Object o) {
        Decision that = (Decision)o;
        return this.point.equals(that.point) && 
                this.direction == that.direction;
    }
    
    public int hashCode() {
        return point.hashCode()*13 ^ direction.hashCode()*47;
    }
}
 
// Direction
enum Direction {
    
    NORTH, EAST, SOUTH, WEST;
    
    public static Direction getDiretion(String s) {
        if(s.equals("WR") || s.equals("EL") || s.equals("NF") || s.equals("N")) {
            return NORTH;
        } else if(s.equals("NR") || s.equals("SL") || s.equals("EF") || s.equals("E")) {
            return EAST;
        } else if(s.equals("ER") || s.equals("WL") || s.equals("SF") || s.equals("S")) {
            return SOUTH;
        } else {
            return WEST;
        }
    }
}