Google Code Jam: Always Turn Left Solution

The problem definition could be found at Code Jam web site.

Idea

• walk through maze in one direction room by room according the path
• update maze room properties, we know entry and exit sides of each room
• turn back, for example turn right 2 times
• walk through maze in another direction room by room according the path
• update maze room properties
• as a result we know properties of each room

My solution is published below.

Helper classes:

• MazeOptions - maze room properties
• MazeCoordinates - maze coordinates and walk logic
• MazeDirection - maze directions

Main function is solve.
Main "walking" function is solveOneWay.

Class diagram:

Source code:

public class AlwaysTurnLeft {

    private Scanner scanner;
    private PrintWriter writer;

    public AlwaysTurnLeft(InputStream is, OutputStream os) {
        scanner = new Scanner(is);
        writer = new PrintWriter(os);
    }
   
   ...
   
    private static final int mazeSize = 2 * (int) Math.sqrt(10000);
    private MazeOptions maze[][];
   
    public void solve() {
        initMaze();
   
        int n = scanner.nextInt();
        for (int i = 1; i <= n; i++) {
            writer.print("Case #");
            writer.println(i + ": ");
   
            char[] entranceToExit = scanner.next().toCharArray();
            char[] exitToEntrance = scanner.next().toCharArray();
   
            cleanOptions();
   
            MazeCoordinates mc = new MazeCoordinates(0, 0, MazeDirection.SOUTH);
            mc = solveOneWay(mc, entranceToExit);
   
            MazeDirection exitMd = mc.getMd();
   
            mc.turnBack();
            mc = solveOneWay(mc, exitToEntrance);
   
            writer.print(getOptionsCode(mc, exitMd));
        }
    }
   
    private void initMaze() {
        maze = new MazeOptions[mazeSize][2 * mazeSize];
   
        for (int i = 0; i < maze.length; i++)
            for (int j = 0; j < maze[i].length; j++)
                maze[i][j] = new MazeOptions();
    }
   
    private MazeCoordinates solveOneWay(MazeCoordinates mc, char[] path) {
        for (int i = 0; i < path.length; i++) {
            switch (path[i]) {
                case 'W':
                    updateOptionsExit(mc);
                    mc.walk();
                    updateOptionsEnter(mc);
                    break;
   
                case 'L':
                    mc.turnLeft();
                    break;
   
                case 'R':
                    mc.turnRight();
                    break;
            }
        }
        return mc;
    }
   
    private String getOptionsCode(MazeCoordinates enterMc, MazeDirection exitMd) {
        int minY = 1;
        int maxY = enterMc.getMaxY();
   
        int minX = enterMc.getMinX();
        int maxX = enterMc.getMaxX();
   
        switch (exitMd) {
            case NORTH:
                // nothing, already 1
                break;
   
            case EAST:
                maxX--;
                break;
   
            case SOUTH:
                maxY--;
                break;
   
            case WEST:
                minX++;
                break;
        }
        return getOptionsCode(minY, maxY, minX, maxX);
    }
   
    private String getOptionsCode(int minY, int maxY, int minX, int maxX) {
        StringBuilder sb = new StringBuilder();
        for (int y = minY; y <= maxY; y++) {
            for (int x = minX; x <= maxX; x++) {
                MazeOptions mo = getMazeOptions(x, y);
                sb.append(mo.toString());
            }
            sb.append("\n");
        }
        return sb.toString();
    }
   
    private void cleanOptions() {
        for (int i = 0; i < maze.length; i++)
            for (int j = 0; j < maze[i].length; j++)
                maze[i][j].clean();
    }
   
    private void updateOptionsExit(MazeCoordinates mc) {
        MazeOptions mo = getMazeOptions(mc.getX(), mc.getY());
        mo.canWalkOnExit(mc);
    }
   
    private void updateOptionsEnter(MazeCoordinates mc) {
        MazeOptions mo = getMazeOptions(mc.getX(), mc.getY());
        mo.canWalkOnEnter(mc);
    }
   
    private MazeOptions getMazeOptions(int x, int y) {
        return maze[y][mazeSize + x];
    }
   
   
    private class MazeOptions {
        private boolean canWalkNorth;
        private boolean canWalkSouth;
        private boolean canWalkWest;
        private boolean canWalkEast;
   
        public MazeOptions() {
            clean();
        }
   
        public void clean() {
            canWalkNorth = false;
            canWalkSouth = false;
            canWalkWest = false;
            canWalkEast = false;
        }
   
        public void canWalkOnExit(MazeCoordinates mc) {
            switch (mc.getMd()) {
                case NORTH:
                    canWalkNorth = true;
                    break;
   
                case EAST:
                    canWalkEast = true;
                    break;
   
                case SOUTH:
                    canWalkSouth = true;
                    break;
   
                case WEST:
                    canWalkWest = true;
                    break;
            }
        }
   
        public void canWalkOnEnter(MazeCoordinates mc) {
            switch (mc.getMd()) {
                case NORTH:
                    canWalkSouth = true;
                    break;
   
                case EAST:
                    canWalkWest = true;
                    break;
   
                case SOUTH:
                    canWalkNorth = true;
                    break;
   
                case WEST:
                    canWalkEast = true;
                    break;
            }
        }
   
        @Override
        public String toString() {
            int north = (canWalkNorth) ? 1 : 0;
            int south = (canWalkSouth) ? 2 : 0;
            int west = (canWalkWest) ? 4 : 0;
            int east = (canWalkEast) ? 8 : 0;

            int result = north | south | west | east;
            return Integer.toHexString(result);
        }
    }
   
   
    private class MazeCoordinates {
        private int x;
        private int y;
   
        private MazeDirection md;
   
        private int minX;
        private int maxX;
   
        private int minY;
        private int maxY;
   
        public MazeCoordinates(int x, int y, MazeDirection md) {
            this.x = x;
            this.y = y;
            this.md = md;
   
            minX = x;
            maxX = x;
   
            minY = y;
            maxY = y;
        }
   
        public MazeCoordinates(MazeCoordinates mc) {
            this.x = mc.x;
            this.y = mc.y;
            this.md = mc.md;
   
            this.minX = mc.minX;
            this.maxX = mc.maxX;
   
            this.minY = mc.minY;
            this.maxY = mc.maxY;
        }
   
        public void walk() {
            switch (md) {
                case NORTH:
                    y--;
                    break;
   
                case EAST:
                    x++;
                    break;
   
                case SOUTH:
                    y++;
                    break;
   
                case WEST:
                    x--;
                    break;
   
                default:
                    throw new IllegalStateException("Illegal walk");
            }
            updateMinMax();
        }
   
        private void updateMinMax() {
            if (minX > x)
                minX = x;
            if (maxX < x)
                maxX = x;
            if (minY > y)
                minY = y;
            if (maxY < y)
                maxY = y;
        }
   
        public void turnLeft() {
            md = md.turnLeft();
        }
   
        public void turnRight() {
            md = md.turnRight();
        }
   
        public void turnBack() {
            md = md.turnRight();
            md = md.turnRight();
        }
   
        public int getX() {
            return x;
        }
   
        public int getY() {
            return y;
        }
   
        public int getMinX() {
            return minX;
        }
   
        public int getMaxX() {
            return maxX;
        }
   
        public int getMinY() {
            return minY;
        }
   
        public int getMaxY() {
            return maxY;
        }
   
        public MazeDirection getMd() {
            return md;
        }
   
        @Override
        public String toString() {
            return "x: " + x + ", y: " + y + ", " + md;
        }
    }
   
   
    private enum MazeDirection {
        NORTH, SOUTH, WEST, EAST;
   
        public MazeDirection turnLeft() {
            switch (this) {
                case NORTH:
                    return MazeDirection.WEST;
   
                case EAST:
                    return MazeDirection.NORTH;
   
                case SOUTH:
                    return MazeDirection.EAST;
   
                case WEST:
                    return MazeDirection.SOUTH;
            }
            throw new IllegalStateException("Illegal turn left");
        }
   
        public MazeDirection turnRight() {
            switch (this) {
                case NORTH:
                    return MazeDirection.EAST;
   
                case EAST:
                    return MazeDirection.SOUTH;
   
                case SOUTH:
                    return MazeDirection.WEST;
   
                case WEST:
                    return MazeDirection.NORTH;
            }
            throw new IllegalStateException("Illegal turn right");
        }
    }
}

See also other posts in Code Jam

Google Code Jam: Alien Numbers Solution

The problem definition could be found at Code Jam web site.

Idea

• get sequence_number of a alien_number in source alien_language
• by a sequence_number get alien_number in target alien_language

My solution is published below.
Main function is solve.

public class AlienNumbers {
   
    private Scanner scanner;
    private PrintWriter writer;
   
   ...
   
    public AlienNumbers(InputStream is, OutputStream os) {
        scanner = new Scanner(is);
        writer = new PrintWriter(os);
    }
   
   ...
   
    /**
     * Solve the problem
     */
    public void solve() {
        int n = scanner.nextInt();
   
        for (int i = 1; i <= n; i++) {
            writer.print("Case #");
            writer.print(i + ": ");
   
            char[] alienNumber = scanner.next().toCharArray();
            char[] sourceLanguage = scanner.next().toCharArray();
            char[] targetLanguage = scanner.next().toCharArray();
   
            // long is enough to store sequence number
            // see Long.MAX_VALUE (9223372036854775807 ~ 10^19)
            long sequenceNumber = getSequenceNumber(alienNumber, sourceLanguage);
            char target[] = getAlienNumber(sequenceNumber, targetLanguage);
   
            writer.println(target);
        }
    }
   
    /**
     * Gets sequence number of a alien_number in alien language
     *
     * @param alienNumber   alien number
     * @param alienLanguage alien language
     * @return sequence number
     */
    private long getSequenceNumber(char[] alienNumber, char[] alienLanguage) {
        long result = 0;
        for (int i = 0; i < alienNumber.length; i++) {
            for (int j = 0; j < alienLanguage.length; j++) {
                if (alienNumber[alienNumber.length - i - 1] == alienLanguage[j]) {
                    result += (long) Math.pow(alienLanguage.length, i) * j;
                    break;
                }
            }
        }
        return result;
    }
   
    /**
     * Gets alien_number by a sequence number in alien language
     *
     * @param sequenceNumber sequence number
     * @param alienLanguage  alien language
     * @return alien number
     */
    private char[] getAlienNumber(long sequenceNumber, char[] alienLanguage) {
        StringBuilder alienNumber = new StringBuilder();
   
        for (int i = (int) log(sequenceNumber, alienLanguage.length); i >= 0; i--) {
            long power = (long) Math.pow(alienLanguage.length, i);
            int index = (int) (sequenceNumber / power);
            alienNumber.append(alienLanguage[index]);
            sequenceNumber -= index * power;
        }
        return alienNumber.toString().toCharArray();
    }
   
    /**
     * Base based logarithm of number
     *
     * @param number number
     * @param base   base
     * @return logarithm
     */
    private long log(long number, long base) {
        return (long) (Math.log(number) / Math.log(base));
    }
}

See also other posts in Code Jam

XML API Internals

XML gurus define 5 styles of XML APIs:

• event-based API or streaming API:
  • push model: SAX, Xerces Native Interface (XNI);
  • pull model: XPP3, StAX;
• tree-based API: DOM, JDOM, dom4j;
• data-binding API;
• query API: XSLT, XPath;

More details could be found here.

Analysis illustrating how XML APIs relate to each other could be found here.

Estimated timeline of Java XML APIs could be found here.

Optimize Queries in MySQL

List of resources about MySQL query optimization:

• 10 Tips for Optimizing MySQL Queries
• MySQL Performance Blog

Interview Questions

Below is the list of Interview Questions by Jesse Farmer:

• Database Indexes
  
• Loops in Linked Lists
  
• When It’s Your Turn
  
• Shuffling an Array
  
• Two Bowling Balls
  
• Counting Bits

Suffix Trees based Diff Java Applet

Suffix Trees based Diff Java Applet:

• enter 2 strings;
• press "Identical" button to find identical parts of 2 strings;
  
• more information about how it works could be found here - Suffix Trees: Longest Common Substring and Diff Implementation.

See also: my other Suffix Trees posts