google code jam practice problems

Problem description can be found here.

A. Alien Numbers

Follow is the solution:

    public String getTargetNumber(String alienNumber,String srcLang,String targetLang) {
        String ret = "";
        // convert alienNumber to decimal number first
        int decimalNumber = 0;     
        //the base of src language. 几进制
        int srcBaseNum = srcLang.length();
        //the base of target language.
        int targetBaseNum = targetLang.length();
        // alien number length
        int alienLen = alienNumber.length();
        
        //begin to calculate decimal number corresponding to alienNumber
        int i = alienLen;
        while(i>0) {
            decimalNumber += srcLang.indexOf(alienNumber.charAt(alienLen-i))*Math.pow(srcBaseNum,i-1);
            i--;
        }        
        
        //convert decimal number to target alien number system's nubmer
        // refer the information about how to convert decimal to binary or hex
        while(decimalNumber!=0) {
            int remainder = decimalNumber%targetBaseNum;
            decimalNumber = decimalNumber/targetBaseNum;
            ret = targetLang.charAt(remainder) + ret;
        }
        return ret;
    }

B. Always Turn Left

Follow is the solution:

public class AlwaysTurnLeft {

    Map<Integer,Integer> dict = new HashMap<Integer, Integer>();
    final int NORTH_VALUE = 1; //0001
    final int SOUTH_VALUE = 2; //0010
    final int WEST_VALUE = 4;  //0100
    final int EAST_VALUE = 8;  //1000
    
    final int NORTH =0;
    final int WEST = 1;
    final int SOUTH = 2;
    final int EAST = 3;
    
    public AlwaysTurnLeft() {
        dict.put(NORTH,NORTH_VALUE);
        dict.put(WEST,WEST_VALUE);
        dict.put(SOUTH,SOUTH_VALUE);
        dict.put(EAST,EAST_VALUE);
    }
    
    class Coordinate {
        public Coordinate() {            
        }
        public Coordinate(int _x, int _y) {
            x = _x;
            y = _y;
        }
        public int x;
        public int y;
    }
    
    int process(String path, int direction, List<Map<Integer,Integer>> mazeInfo, Coordinate curCoor) { 
        char[] arr = path.toCharArray();
        for(int i=1;i<arr.length-1;i++) {
            if(mazeInfo.size()<=curCoor.x) {
                mazeInfo.add(new HashMap<Integer,Integer>());
            }
            Map<Integer,Integer> rowMap = mazeInfo.get(curCoor.x);
            if(rowMap.get(curCoor.y)==null) {
                rowMap.put(curCoor.y,0);
            }
            int cellInfo = rowMap.get(curCoor.y);
            char c = arr[i];
            switch(c) {                
                case 'W':  
                    int toAddValue = dict.get(direction);       
                    if(cellInfo/toAddValue%2==0) {
                        rowMap.put(curCoor.y,cellInfo+toAddValue);
                    }
                    switch(direction) {                        
                        case NORTH: curCoor.x--; break;
                        case WEST: curCoor.y--; break;
                        case SOUTH: curCoor.x++; break;
                        case EAST: curCoor.y++; break;
                    }
                    break;
                case 'R':
                    direction--;
                    break;
                case 'L':
                    direction++;
                    break;
            }            
            direction += 4;
            direction %= 4;            
        }
        return direction;
    }
    
    public List<String> getMazeInfo(String entrance_to_exit, String exit_to_entrance) {  
        // At begin, the direction is SOUTH.
        int direction = SOUTH;
        // mazeInfo represent information for maze
        // Map<Integer, Integer> 
        // key is maze column index(maybe a negative number, because the entrance is at [0,0].).
        // value represents information for all directions that current cell can walk to.
        List<Map<Integer,Integer>> mazeInfo = new ArrayList<Map<Integer,Integer>>();
        // add information for entrance.
        mazeInfo.add(new HashMap<Integer,Integer>());
        mazeInfo.get(0).put(0,0);
        Coordinate curCoor = new Coordinate(0,0);
        
        List<String> ret = new ArrayList<String>();     
        // process path for entrance to exit
        direction = process(entrance_to_exit,direction,mazeInfo,curCoor);
        // for entrance cell, add north possibility
        mazeInfo.get(0).put(0,mazeInfo.get(0).get(0)+NORTH_VALUE);
        // for exit cell, add corresponding direction possibility. should add information for exit first.
        if(mazeInfo.size()<=curCoor.x) {
            mazeInfo.add(new HashMap<Integer,Integer>());
        }
        if(mazeInfo.get(curCoor.x).get(curCoor.y)==null) {
            mazeInfo.get(curCoor.x).put(curCoor.y,0);
        }
        mazeInfo.get(curCoor.x).put(curCoor.y,mazeInfo.get(curCoor.x).get(curCoor.y)+dict.get(direction));
        // turn right twice(180 degrees clockwise)
        direction += 2;
        direction %= 4;
        //process path for exit to entrance
        direction = process(exit_to_entrance,direction,mazeInfo,curCoor);
        for(Map<Integer,Integer> m : mazeInfo) {
            SortedSet<Integer> keySet = new TreeSet<Integer>(m.keySet());   
            StringBuilder sb = new StringBuilder();
            for(Integer key : keySet) {    
                sb.append(Integer.toHexString(m.get(key)));
            }
            ret.add(sb.toString());
        }
        return ret;
    }
    
    
    public static void main(String args[]) throws Exception {
        AlwaysTurnLeft t = new AlwaysTurnLeft();
        List<String> list = t.getMazeInfo("WWRWLWLWRRWLWLWRRWLWWLWLWRRWWWWRRWLWLWRRWRWLWLWRRWLWLWRWWWWRWLWLWW","WWLW");
        for(String s : list) {
            System.out.println(s);
        }
    }
}

<style type="text/css">.csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; } </style> <style type="text/css">.csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; } </style>