Free Cheat Sheets for Developers - part 3

Latest Free Cheat Sheets for Developers:

• Core Java Concurrency

• Getting Started with Java EE Security
• Getting Started with JBoss Enterprise Application Platform 5

• Getting Started with Java GUI Development
• Getting Started with Ajax
  

• Getting Started with Git
• Getting Started with Maven Repository Management
  

• Getting Started with Cloud Computing
• Spring Web Flow

Free Cheat Sheets for Developers - part 2

Another set of interesting Free Cheat Sheets for Developers:

• Getting Started with JPA
• GlassFish Application Server - Updated for Version 3
• Dependency Injection in EJB 3

• JavaServer Faces
  
• Struts2
• Getting Started with Ajax
  

• Design Patterns

Free Cheat Sheets for Developers

Recently I reviewed set of Free Cheat Sheets for Developers and found some very interesting:

• Apache Maven 2
• Continuous Integration: Servers and Tools
• Continuous Integration: Patterns and Anti-patterns
• Contexts and Dependency Injection for the Java EE Platform

• Agile Adoption: Reducing Cost
• Scrum
• Getting Started with Lean Software Development

• Scalability & High Availability

• Using XML in Java
• Core Java
• IntelliJ IDEA: Updated for 8.1

Code Jam 2010: Theme Park

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

Official Contest Analysis could be found at Code Jam web site.

My solution is published below.

Main functions:

• public solve - high-level problem solving
• private solve - low -level problem solving
calculateByMap - calculates euros based on ride cache

Helper classes:

• Key - ride cache key
• Value - ride cache value

public class ThemePark {
    ...
    private Scanner scanner;
    private PrintWriter writer;
    
    public ThemePark(InputStream is, OutputStream os) {
        scanner = new Scanner(is);
        writer = new PrintWriter(os);
    }
    ...
    /**
     * Solve the problem
     */
    public void solve() {
        int t = scanner.nextInt();
   
        for (int i = 1; i <= t; i++) {
            writer.print("Case #");
            writer.print(i + ": ");
   
            // 1 <= R <= 10^8
            long r = scanner.nextInt();
   
            // 1 <= k <= 10^9
            long k = scanner.nextInt();
   
            // 1 <= N <= 1000
            int n = scanner.nextInt();
   
            // 1 <= g[i] <= 10^7
            long g[] = new long[n];
            for (int j = 0; j < n; j++)
                g[j] = scanner.nextInt();
   
            writer.println(solve(r, k, g));
        }
    }
   
    private String solve(long r, long k, long g[]) {
        Queue<Long> queue = new LinkedList<Long>();
        Queue<Long> ride = new LinkedList<Long>();
   
        // queue, ride -> count, euros
        Map<Key, Value> map = new LinkedHashMap<Key, Value>();
   
        for (int i = 0; i < g.length; i++)
            queue.add(g[i]);
   
        BigInteger euros = new BigInteger("0");
        for (int i = 0; i < r; i++) {
            long sum = 0;
            ride.clear();
   
            while ((queue.size() > 0) && (sum + queue.peek() <= k)) {
                ride.add(queue.peek());
                sum += queue.poll();
            }
   
            // prepare key->value pair for caching...
            Key key = new Key(queue.toString(), ride.toString());
            Value value = new Value(ride.size(), sum);
   
            if (!map.containsKey(key)) {
                map.put(key, value);
   
                euros = euros.add(new BigInteger(((Long) sum).toString()));
                queue.addAll(ride);
            } else {
                // the same [ride, queue] found in cache  
                // so calculate euros based on cache
                euros = euros.add(calculateByMap(map, key, r - i));
                break;
            }
        }
        return euros.toString();
    }
   
    private BigInteger calculateByMap(Map<Key, Value> map, Key key, long ridesLeft) {
        long storedSum = 0;
        boolean found = false;
        int foundIndex = 0;
   
        long remainder = 0;
        long remainderSum = 0;
   
        for (Key storedKey : map.keySet()) {
            // if item found - calculate remainder
            if ((!found) && (storedKey.equals(key))) {
                found = true;
                remainder = ridesLeft % (map.size() - foundIndex);
            }
            if (found) {
                // calculate stored sum
                storedSum += map.get(storedKey).getSum();
   
                // calculate remainder
                if (remainder > 0) {
                    remainderSum += map.get(storedKey).getSum();
                    remainder--;
                }
            } else
                foundIndex++;
        }
        long storedCount = map.size() - foundIndex;
        long mult = ridesLeft / (storedCount);
        mult = mult * storedSum + remainderSum;
        return new BigInteger(((Long) mult).toString());
    }
   
    class Key {
        private String queue;
        private String ride;
   
        Key(String queue, String ride) {
            this.queue = queue;
            this.ride = ride;
        }
   
        public String getQueue() {
            return queue;
        }
   
        public String getRide() {
            return ride;
        }
   
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
   
            Key key = (Key) o;
   
            if (!queue.equals(key.queue)) return false;
            if (!ride.equals(key.ride)) return false;
   
            return true;
        }
   
        @Override
        public int hashCode() {
            int result = queue.hashCode();
            result = 31 * result + ride.hashCode();
            return result;
        }
    }
   
    class Value {
        private int size;
        private long sum;
   
        Value(int size, long sum) {
            this.size = size;
            this.sum = sum;
        }
   
        public int getSize() {
            return size;
        }
   
        public long getSum() {
            return sum;
        }
    }
}

See also other posts in Code Jam

Code Jam 2010: Fair Warning

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

Official Contest Analysis could be found at Code Jam web site.

My solution is published below.

Main functions:

• public solve - high-level problem solving
• private solve - low -level problem solving

public class FairWarning {
    ...
    private Scanner scanner;
    private PrintWriter writer;
   
    public FairWarning(InputStream is, OutputStream os) {
        scanner = new Scanner(is);
        writer = new PrintWriter(os);
    }
    ...
    /**
     * Solve the problem
     */
    public void solve() {
        int c = scanner.nextInt();
   
        for (int i = 1; i <= c; i++) {
            writer.print("Case #");
            writer.print(i + ": ");
   
            // 2 <= N <= 1000
            int n = scanner.nextInt();
   
            // 1 <= t[i] <= 10^50
            // collect t[i] into a TreeSet to have them sorted
            NavigableSet<BigInteger> t = new TreeSet<BigInteger>();
            for (int j = 0; j < n; j++)
                t.add(new BigInteger(scanner.next()));
   
            writer.println(solve(t));
        }
    }
   
    private BigInteger solve(NavigableSet<BigInteger> t) {
        // find GCD of all differences between
        Iterator i = t.descendingIterator();
        BigInteger prev = null;
        BigInteger div = null;
        while (i.hasNext()) {
            if (prev == null)
                prev = (BigInteger) i.next();
            else {
                BigInteger diff = prev.subtract((BigInteger) i.next()).abs();
                if (diff.equals(BigInteger.ZERO))
                    continue;
                if (div == null)
                    div = diff;
                else
                    div = div.gcd(diff);
            }
        }
   
        // calculate slarboseconds 
        BigInteger mod = prev.mod(div);
        if (mod.equals(BigInteger.ZERO))
            return BigInteger.ZERO;
        return div.subtract(mod);
    }
}

See also other posts in Code Jam

Code Jam 2010: Snapper Chain

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

Official Contest Analysis could be found at Code Jam web site.

Dynamic programming could be used:

1. state[j] - state of j-Snapper
2. power[j] - is j-Snapper powered
3. power[j+1] - do we have power after j-Snapper
4. state[i][j] - state of j-Snapper after i-snaps
5. power[i][j] - is j-Snapper powered after i-snaps
6. state[i][j] = (power[i-1][j]) ? !state[i-1][j] : state[i-1][j]
7. power[i][j+1] = power[i][j] && state[i][j]

state[i][j], where i-rows, j-columns
  0  0 0 0 0 0 0 0 0 0 0 
  1  1 0 0 0 0 0 0 0 0 0 
  2  0 1 0 0 0 0 0 0 0 0 
  3  1 1 0 0 0 0 0 0 0 0 
  4  0 0 1 0 0 0 0 0 0 0 
  5  1 0 1 0 0 0 0 0 0 0 
  6  0 1 1 0 0 0 0 0 0 0 
  7  1 1 1 0 0 0 0 0 0 0 
  8  0 0 0 1 0 0 0 0 0 0 
  9  1 0 0 1 0 0 0 0 0 0 
 10  0 1 0 1 0 0 0 0 0 0 
 11  1 1 0 1 0 0 0 0 0 0 
 12  0 0 1 1 0 0 0 0 0 0 
 13  1 0 1 1 0 0 0 0 0 0 
 14  0 1 1 1 0 0 0 0 0 0 
 15  1 1 1 1 0 0 0 0 0 0 
 16  0 0 0 0 1 0 0 0 0 0 

power[i][j], where i-rows, j-columns
  0  1 0 0 0 0 0 0 0 0 0 0 
  1  1 1 0 0 0 0 0 0 0 0 0 
  2  1 0 0 0 0 0 0 0 0 0 0 
  3  1 1 1 0 0 0 0 0 0 0 0 
  4  1 0 0 0 0 0 0 0 0 0 0 
  5  1 1 0 0 0 0 0 0 0 0 0 
  6  1 0 0 0 0 0 0 0 0 0 0 
  7  1 1 1 1 0 0 0 0 0 0 0 
  8  1 0 0 0 0 0 0 0 0 0 0 
  9  1 1 0 0 0 0 0 0 0 0 0 
 10  1 0 0 0 0 0 0 0 0 0 0 
 11  1 1 1 0 0 0 0 0 0 0 0 
 12  1 0 0 0 0 0 0 0 0 0 0 
 13  1 1 0 0 0 0 0 0 0 0 0 
 14  1 0 0 0 0 0 0 0 0 0 0 
 15  1 1 1 1 1 0 0 0 0 0 0 
 16  1 0 0 0 0 0 0 0 0 0 0 

But this idea requires 30 x 10^8 array which is not possible.
If we check state[i][j] then we could find that it is just binary representation of i-number. So are not required to store it.
power[i][j+1] could be calculated only based on state[i][j].

My solution is published below.

Main functions:

• solve - solves the problem
• snapper - returns power after j-Snapper after i-snaps

public class SnapperChain {
   ...
    private Scanner scanner;
    private PrintWriter writer;
   
    public SnapperChain(InputStream is, OutputStream os) {
        scanner = new Scanner(is);
        writer = new PrintWriter(os);
    }
   ...
    private static final int MAX_SNAPPER = 30;
   
    /**
     * Solve the problem
     */
    public void solve() {
        int t = scanner.nextInt();
   
        for (int i = 1; i <= t; i++) {
            writer.print("Case #");
            writer.print(i + ": ");
   
            // The light is plugged into the Nth Snapper.
            // 1 <= N <= 30;
            int n = scanner.nextInt();
   
            // I have snapped my fingers K times
            // 0 <= K <= 10^8;
            long k = scanner.nextInt();
   
            boolean light = snapper(n, k);
            writer.println((light) ? "ON" : "OFF");
        }
    }
   
    private boolean snapper(int n, long k) {
        boolean[] power = new boolean[MAX_SNAPPER + 1];
   
        power[0] = true;
        for (int j = 0; j < MAX_SNAPPER; j++) {
            boolean state = ((k >> j) & 0x01) == 0x01;
            power[j + 1] = power[j] && state;
        }
        return power[n];
    }
}

See also other posts in Code Jam

Code Jam 2010: Qualification Round - Solutions & Analysis

Solutions & Analysis of problems from Qualification Round of Google Code Jam 2010 could be found below
http://code.google.com/codejam/contests.html

Code Jam 2010: Qualification Round

Today I took part in Qualification Round of Google Code Jam 2010.
Successfully solved all problems with Small datasets.
Now I'm waiting for the end of the contest to verify my solutions with Large datasets.



I plan to publish my solutions later...

Graph Search Algorithms

In this post next graph search algorithm are discussed:

• Depth-First Search
• Breadth-First Search
• Dijkstra's algorithm

Class diagram:

Main methods of a class Graph:

• dfs - Depth-First Search
• bfs - Breadth-First Search
• dijkstra - Dijkstra's algorithm

Methods definition could be found below:

public class Graph {
   
   ...
   
    public List<Node> dfs(Node node) {
        clearVisited();
   
        return dfs(node, new LinkedList<Node>());
    }
   
    private List<Node> dfs(Node node, List<Node> dfsNodes) {
        if (isVisited(node))
            return dfsNodes;
   
        visit(node);
        dfsNodes.add(node);
   
        for (Edge edge : node.getEdges())
            dfsNodes = dfs(edge.getNode(), dfsNodes);
        return dfsNodes;
    }
   
    public List<Node> bfs(Node node) {
        clearVisited();
   
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(node);
   
        return bfs(queue, new LinkedList<Node>());
    }
   
    private List<Node> bfs(Queue<Node> queue, List<Node> bfsNodes) {
        while (!queue.isEmpty()) {
            Node node = queue.remove();
   
            if (!isVisited(node)) {
                visit(node);
                bfsNodes.add(node);
   
                for (Edge edge : node.getEdges())
                    queue.add(edge.getNode());
            }
        }
        return bfsNodes;
    }
   
    public Map<Node, Integer> dijkstra(Node current) {
        Map<Node, Integer> weights = new HashMap<Node, Integer>();
        for (Node node : getNodes())
            weights.put(node, Integer.MAX_VALUE);
        weights.put(current, 0);
   
        clearVisited();
        do {
            int minWeight = Integer.MAX_VALUE;
            Node minNode = null;
   
            for (Edge edge : current.getEdges()) {
                Node node = edge.getNode();
                int weight = weights.get(current) + edge.getWeight();
   
                if (weight < weights.get(node))
                    weights.put(node, weight);
   
                if ((weight < minWeight) && (!isVisited(node))) {
                    minWeight = weight;
                    minNode = node;
                }
            }
            visit(current);
            current = minNode;
        } while (current != null);
        return weights;
    }
}