Bitwise Operations in Java

The bitwise operations in Java are rarely discussed, and you can sense that by reading the official tutorials on this topic. However, there are interesting usages that you should probably be aware of.

The bitwise operators operates on integral types (int and long). Before explaining how bitwise operators work, you should have an idea of how integers are represented in the binary form. As mentioned by the official primitive data type tutorials, the int data type is a 32-bit signed 2's complement integer, whose value ranges from -2^32 to 2^32-1, inclusively. On the other hand, the long data type is a 64-bit signed 2's complement integer, whose value ranges from -2^64 to 2^64-1, inclusively. In both cases, the highest order bit of int and long shows the sign of the value and is not part of the numeric value, where 0 being positive and 1 being negative.

For example, an int value of 1 in binary form looks like this

00000000000000000000000000000001

while an int value of -1 in binary form looks like this

11111111111111111111111111111111

The negative value is transformed in 2 steps:

Step 1: bitwise complement of +1, such that
00000000000000000000000000000001 
becomes
11111111111111111111111111111110

Step 2: add 1, such that
11111111111111111111111111111110 
becomes
11111111111111111111111111111111

Given a negative value, where the highest (leftmost) bit is 1, you can work out what value the binary form represents in 2 steps:

Step 1: bitwise complement of the binary value, such that
11111111111111111111111111111011
becomes
00000000000000000000000000000100

Step 2: add 1, such that
00000000000000000000000000000100
becomes
00000000000000000000000000000101

Therefore, the original binary form represents -5.

The bitwise operators

Operator	Name	Example	Result	Description
a & b	and	6 & 9	0	1 if both bits are 1, or 0 if either bit is 0
a | b	or	6 | 9	15	1 if either bit is 1, or 0 if both bits are 0
a ^ b	xor	6 ^ 9	15	1 if both bits are different, 0 if both bits are the same
~a	not	~9	-10	Inverts the bits. (equivalent to +1 and then change sign)
n << p	left shift	60 << 2	240	Shifts the bits of n left p positions. Zero bits are shifted into the low-order positions.
n >> p	right shift	60 >> 2	15	Shifts the bits of n right p positions. If n is a 2's complement signed number, the sign bit is shifted into the high-order positions.
n >>> p	unsigned right shift	-60 >>> 20	4095	Shifts the bits of n right p positions. Zeros are shifted into the high-order positions.

Packing and Unpacking

Multiple int values of limited range can be "packed" into one int, by using the bitwise operators. For example, we have the following integer variables age (range 0~255, or 8-bit), gender (0~1, or 1-bit), weight (range 0~255, or 8-bit), and height (range 0-255, or 8-bit). These integers can be packed and unpacked into/from a 32-bit integer like this:

Represent boolean values in a byte

Suppose we have 8 boolean values that are true or false, and we want to store them in a single byte, and sent it across the network, and then unpack it and use it to toggle 8 different things:

Multiply and Divide

When using x << 3, it is equivalent to multiply x by 8 (or 2^3); similarly, when using x >> 2, it is equivalent to divide x by 4 (or 2^2). In fact, a smart enough compiler will replace your multiplication or division expressions using bit shift operators such that it is more compact and faster. So there is no need to explicitly use bit shift operator if you want multiply or divide by a power of 2!

Sorting Algorithm Performance Comparisons with Caliper's Micro Benchmarking

After inspired by Martin Thompson's presentation on Performance Testing Java Application, I decided to try out the micro benchmarking framework Caliper on the sorting algorithms that I recently wrote in order to understand better how different sorting algorithms behaves given an array of randomly distributed values.

It was actually a bit involving to find out where I could download the caliper JAR file, as it was not available on their google code base. You can download it from the maven repository, or grab it from my git described at the bottom of this article.

I created a SortingAlgorithmsBenchmark class that extends SimpleBenchmark, and some public methods, whose names have prefix 'time'. Then use the caliper Runner to run the benchmarks on the SortingAlgorithmsBenchmark class, as shown below

import com.google.caliper.Runner;
import com.google.caliper.SimpleBenchmark;
import sorting.*;

import java.util.Arrays;
import java.util.Random;

public class SortingAlgorithmsBenchmark extends SimpleBenchmark {

    private static final int SIZE = 10000;
    private static final int MAX_VALUE = 10000;
    private int[] values;

    @Override
    protected void setUp() throws Exception {
        values = new int[SIZE];
        Random generator = new Random();
        for (int i = 0; i < values.length; i++) {
            values[i] = generator.nextInt(MAX_VALUE);
        }
    }

    public void timeBubbleSort(int reps) {
        for (int i = 0; i < reps; i++) {
            BubbleSort.sort(values);
        }
    }

    public void timeInsertionSort(int reps) {
        for (int i = 0; i < reps; i++) {
            InsertionSort.sort(values);
        }
    }

    public void timeSelectionSort(int reps) {
        for (int i = 0; i < reps; i++) {
            SelectionSort.sort(values);
        }
    }

    public void timeMergeSort(int reps) {
        for (int i = 0; i < reps; i++) {
            MergeSort.sort(values);
        }
    }

    public void timeShellSort(int reps) {
        for (int i = 0; i < reps; i++) {
            ShellSort.sort(values);
        }
    }

    public void timeArraysSort(int reps) {
        for (int i = 0; i < reps; i++) {
            Arrays.sort(values);
        }
    }

    public static void main(String[] args) {
        Runner.main(SortingAlgorithmsBenchmark.class, args);
    }

}

Here are the results when running the benchmarks with a random array of size 10,000. Apparently, bubble sort and selection sort are the slowest of all, with selection sort behaving rather unstable (you will notice the selection sort benchmark is quite different across different runs. It is pleased to see that the sorting algorithm (Dual-Pivot Quick Sort) used by Arrays performs fairly well with a medium size array.

0% Scenario{vm=java, trial=0, benchmark=BubbleSort} 75703105.85 ns; σ=3428843.80 ns @ 10 trials
17% Scenario{vm=java, trial=0, benchmark=InsertionSort} 73305.66 ns; σ=712.37 ns @ 6 trials
33% Scenario{vm=java, trial=0, benchmark=SelectionSort} 49624130.05 ns; σ=345774.06 ns @ 3 trials
50% Scenario{vm=java, trial=0, benchmark=MergeSort} 478932.15 ns; σ=683.99 ns @ 3 trials
67% Scenario{vm=java, trial=0, benchmark=ShellSort} 262061.27 ns; σ=11605.29 ns @ 10 trials
83% Scenario{vm=java, trial=0, benchmark=ArraysSort} 8063.53 ns; σ=20167.07 ns @ 10 trials

    benchmark       us linear runtime
   BubbleSort 75703.11 ==============================
InsertionSort    73.31 =
SelectionSort 49624.13 ===================
    MergeSort   478.93 =
    ShellSort   262.06 =
   ArraysSort     8.06 =

vm: java
trial: 0

Increasing the array size to 100,000, and excluding the bubble sort and selection sort in the benckmarks, we have another set of results, where insertion sort starts to behave terribly in this case, and the dual-pivot quick sort is still the quickest.

0% Scenario{vm=java, trial=0, benchmark=InsertionSort} 2031873339.00 ns; σ=3247182.51 ns @ 3 trials
25% Scenario{vm=java, trial=0, benchmark=MergeSort} 5701257.43 ns; σ=37183.00 ns @ 3 trials
50% Scenario{vm=java, trial=0, benchmark=ShellSort} 2277851.07 ns; σ=21077.62 ns @ 3 trials
75% Scenario{vm=java, trial=0, benchmark=ArraysSort} 210179.59 ns; σ=164843.22 ns @ 10 trials

    benchmark      us linear runtime
InsertionSort 2031873 ==============================
    MergeSort    5701 =
    ShellSort    2278 =
   ArraysSort     210 =

vm: java
trial: 0

You can find the source code for the sorting algorithms here, and the benchmarks runner here, all of which are part of my github project DataStructureAndAlgorithms

A Different Builder Pattern Example in Java

Builder design pattern is often used to separate the construction of a complex object from its various representations. I will show you a nicer way of writing a Builder pattern, rather than the example shown in the wiki.

First of all, I created a POJO called Vehicle, which has some simple properties about its model, its make, etc. Then, nested within this POJO, I created a Builder that holds some default properties which can be used to build a vehicle. The builder can be created by a static method newBuilder(), and we can override the vehicle properties by chaining the with* methods, and finally return the constructed vehicle using the build() method.

public class Vehicle {

    private String model;
    private String make;
    private int numberOfWheels;
    private double height;
    private double width;
    private double length;
    private int numberOfDoors;

    private Vehicle(String model, String make, int numberOfWheels, double height, double width, double length, int numberOfDoors) {
        this.model = model;
        this.make = make;
        this.numberOfWheels = numberOfWheels;
        this.height = height;
        this.width = width;
        this.length = length;
        this.numberOfDoors = numberOfDoors;
    }

    public static class Builder {

        private String model = "M5";
        private String make = "BMW";
        private int numberOfWheels = 4;
        private double height = 1.45;
        private double width = 1.9;
        private double length = 4.62;
        private int numberOfDoors = 5;

        public static Builder newBuilder() {
            return new Builder();
        }

        public Builder withModel(String model) {
            this.model = model;
            return this;
        }

        public Builder withMake(String make) {
            this.make = make;
            return this;
        }

        public Vehicle build() {
            return new Vehicle(model, make, numberOfWheels, height, width,length, numberOfDoors);
        }
    }
}

Let me use a unit test, written in Groovy, to demonstrate exactly how we use the builder. I created a test to show how we can build a default vehicle without providing any overrides to the default vehicle properties, and another test to show how we can override the default vehicle properties to create a different vehicle.

import org.junit.Test

class VehicleTest {

    @Test
    public void canBuildADefaultVehicle() {
        def defaultVehicle = Vehicle.Builder.newBuilder().build()
        assert defaultVehicle.model == "M5"
        assert defaultVehicle.make == "BMW"
        assert defaultVehicle.numberOfWheels == 4
        assert defaultVehicle.height == 1.45
        assert defaultVehicle.width == 1.9
        assert defaultVehicle.length == 4.62
        assert defaultVehicle.numberOfDoors == 5
    }

    @Test
    public void canBuildADifferentVehicle() {
        def defaultVehicle = Vehicle.Builder.newBuilder().withModel("M3").build()
        assert defaultVehicle.model == "M3"
        assert defaultVehicle.make == "BMW"
        assert defaultVehicle.numberOfWheels == 4
        assert defaultVehicle.height == 1.45
        assert defaultVehicle.width == 1.9
        assert defaultVehicle.length == 4.62
        assert defaultVehicle.numberOfDoors == 5
    }
}

Some says the chaining syntax makes the building block easier to read. :)

Solving Farmer-Wolf-Goat-Cabbage riddle with Groovy/Java

The Riddle - Farmer Wolf Goat Cabbage

A farmer is on the west bank of a river with a wolf, a goat and a cabbage in his care. Without his presence the wolf would eat the goat or the goat would eat the cabbage. The wolf is not interested in the cabbage. The farmer wishes to bring his three charges across the river. However the boat available to him can only carry one of the wolf, goat and cabbage besides himself. The puzzle is: is there a sequence of river crossings so that the farmer can transfer himself and the other three all intact to the east bank?

The Solution

It is a task that given an initial state, a final state, and a set of rules, one will start from the initial state and try to reach to the final state by passing through some intermediate states. Each move will transform from one state to the other, and there might be multiple valid moves from a given state. Such a collection of interconnected states can be represented by State Space Graph.
Let's use 'f', 'c', 'g', 'w' to denote the farmer, the cabbage, the goat, and the wolf, and use '|' to separate the river where left of the '|' denotes west bank and right of the '|' denotes east bank. Initially, they are all at the west bank of the river, which is represented as 'fcgw |' as shown below. We can solve the riddle by figuring out what the possible and valid moves are, using either Breadth-First Search or Depth-First Search, on a state space graph shown below

 

Depth First Search

I use DFS to find the first possible solution to the riddle, where it looks like this

or with a possibility of backtracking like this

Breadth First Search

I can build a complete state space graph using BFS, excluding the red states as shown below

Sample Source Code

Implemented in a mix of Groovy and Java, where Java is mainly used for the POJOs, the sample source code, including the unit test, demonstrates how to build a complete state space graph (which is also a directed graph) and how to find all possible solutions based on the state space graph.
DirectedGraph.java

import java.util.*;

public class DirectedGraph<T> implements Iterable<T> {

    // key is a Node, value is a set of Nodes connected by outgoing edges from the key
    private final Map<T, Set<T>> graph = new HashMap<T, Set<T>>();

    public boolean addNode(T node) {
        if (graph.containsKey(node)) {
            return false;
        }

        graph.put(node, new HashSet<T>());
        return true;
    }

    public void addNodes(Collection<T> nodes) {
        for (T node : nodes) {
            addNode(node);
        }
    }

    public void addEdge(T src, T dest) {
        validateSourceAndDestinationNodes(src, dest);

        // Add the edge by adding the dest node into the outgoing edges
        graph.get(src).add(dest);
    }

    public void removeEdge(T src, T dest) {
        validateSourceAndDestinationNodes(src, dest);

        graph.get(src).remove(dest);
    }

    public boolean edgeExists(T src, T dest) {
        validateSourceAndDestinationNodes(src, dest);

        return graph.get(src).contains(dest);
    }

    public Set<T> edgesFrom(T node) {
        // Check that the node exists.
        Set<T> edges = graph.get(node);
        if (edges == null)
            throw new NoSuchElementException("Source node does not exist.");

        return Collections.unmodifiableSet(edges);
    }

    public Iterator<T> iterator() {
        return graph.keySet().iterator();
    }

    public int size() {
        return graph.size();
    }

    public boolean isEmpty() {
        return graph.isEmpty();
    }

    private void validateSourceAndDestinationNodes(T src, T dest) {
        // Confirm both endpoints exist
        if (!graph.containsKey(src) || !graph.containsKey(dest))
            throw new NoSuchElementException("Both nodes must be in the graph.");
    }

}

BoatLocation.java

public enum BoatLocation {
    WestBank, EastBank
}

RiverRole.java, implemented Comparable interface in order to be used in a SortedSet

public class RiverRole implements Comparable<RiverRole> {

    public final String name;
    public final boolean canSailTheBoat;

    public RiverRole(String name, boolean canSailTheBoat) {
        this.name = name;
        this.canSailTheBoat = canSailTheBoat;
    }

    @Override
    public int compareTo(RiverRole o) {
        return this.name.compareTo(o.name);
    }

    @Override
    public String toString() {
        return name;
    }
}

RiverState.java

import java.util.Collection;
import java.util.SortedSet;
import java.util.TreeSet;

public class RiverState {

    private SortedSet<RiverRole> westBank;
    private SortedSet<RiverRole> eastBank;
    private BoatLocation boatLocation;

    public RiverState(Collection<RiverRole> westBank, Collection<RiverRole> eastBank, BoatLocation boatLocation) {
        this.westBank = new TreeSet<RiverRole>(westBank);
        this.eastBank = new TreeSet<RiverRole>(eastBank);
        this.boatLocation = boatLocation;
    }

    public SortedSet<RiverRole> getWestBank() {
        return new TreeSet<RiverRole>(westBank);
    }

    public SortedSet<RiverRole> getEastBank() {
        return new TreeSet<RiverRole>(eastBank);
    }

    public BoatLocation getBoatLocation() {
        return boatLocation;
    }

    @Override
    public String toString() {
        return "State{westBank=" + westBank + ", eastBank=" + eastBank + ", boatLocation=" + boatLocation + "}";
    }

    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof RiverState)) return false;

        RiverState riverState = (RiverState) o;

        return eastBank.equals(riverState.eastBank) &&
               westBank.equals(riverState.westBank) &&
               boatLocation.equals(riverState.boatLocation);
    }

    public int hashCode() {
        int result;
        result = westBank.hashCode();
        result = 31 * result + eastBank.hashCode();
        result = 31 * result + boatLocation.hashCode();
        return result;
    }
}

FarmerWolfGoatRiddle.groovy

import graph.DirectedGraph
import org.codehaus.groovy.runtime.MethodClosure

import static fun.rivercrossing.BoatLocation.EastBank
import static fun.rivercrossing.BoatLocation.WestBank

public class FarmerWolfGoatRiddle {

    /*  Farmer Wolf Goat Puzzle
        A farmer is on the east bank of a river with a wolf, goat and cabbage in his care. Without his presence the wolf would eat
        the goat or the goat would eat the cabbage. The wolf is not interested in the cabbage. The farmer wishes to bring his three
        charges across the river. However the boat available to him can only carry one of the wolf, goat and cabbage besides
        himself. The puzzle is: is there a sequence of river crossings so that the farmer can transfer himself and the other three all
        intact to the west bank?
    */

    RiverRole farmer = new RiverRole("farmer", true);
    RiverRole wolf = new RiverRole("wolf", false);
    RiverRole goat = new RiverRole("goat", false);
    RiverRole cabbage = new RiverRole("cabbage", false);

    RiverState initialState = new RiverState([farmer, wolf, goat, cabbage], [], BoatLocation.WestBank)
    RiverState finalState = new RiverState([], [farmer, wolf, goat, cabbage], EastBank)

    Closure<Boolean> areRolesHarmonisedOnRiverBank = { Collection<RiverRole> roles ->
        // describe clearly what the rules are
        if (!roles.contains(farmer)) {
            if (roles.contains(wolf) && roles.contains(goat)) return false
            if (roles.contains(goat) && roles.contains(cabbage)) return false
        }
        return true
    }


    public Collection<Deque<RiverState>> findAllPossibleSolutions() {
        DirectedGraph<RiverState> graph = buildCompleteGraph()

        Collection<Deque<RiverState>> solutions = []
        Deque<RiverState> currentSolution = new ArrayDeque<RiverState>()

        explore(graph, initialState, currentSolution, solutions)

        return solutions
    }

    // using Depth First Search (Stack Implementation) to identify a solution
    private void explore(DirectedGraph<RiverState> graph, RiverState currentNode, Deque<RiverState> currentSolution, Collection<Deque<RiverState>> solutions) {
        currentSolution.push(currentNode)
        graph.edgesFrom(currentNode).each { RiverState node ->
            if (node == finalState) {
                // add the current solution, including the final node, to the solutions
                currentSolution.push(node)
                solutions.add(new ArrayDeque<RiverState>(currentSolution))
                currentSolution.pop()
            } else {
                // recursively explore
                explore(graph, node, currentSolution, solutions)
            }
        }
        currentSolution.pop()
    }

    // using Breath First Search to build the complete graph
    private DirectedGraph<RiverState> buildCompleteGraph() {
        DirectedGraph<RiverState> graph = new DirectedGraph<RiverState>()
        graph.addNode(initialState)

        Set<RiverState> visitedNodes = new HashSet<RiverState>()

        // use a queue to keep the states to be visited in sequence
        Deque<RiverState> currentStates = new ArrayDeque<RiverState>()
        currentStates.add(initialState)

        while (!currentStates.isEmpty()) {
            if (currentStates.peek() != finalState) {
                def currentState = currentStates.removeFirst()
                if (!visitedNodes.contains(currentState)) {
                    visitedNodes.add(currentState)
                    def possibleStates = findNextPossibleStates(currentState)
                    def validStates = possibleStates.findAll { RiverState possibleState ->
                        // matched state should not be one of the visited states, and it should pass the validations
                        return !visitedNodes.contains(possibleState) && passRuleValidations(possibleState)
                    }
                    // add successors and edges
                    graph.addNodes(validStates)
                    validStates.each { graph.addEdge(currentState, it) }

                    // add to current states so that we can visit them next
                    currentStates.addAll(validStates)
                }
            } else {
                currentStates.removeFirst() // remove the final state from the currentStates queue
            }
        }

        return graph
    }

    private boolean passRuleValidations(RiverState state) {
        return areRolesHarmonisedOnRiverBank(state.eastBank) && areRolesHarmonisedOnRiverBank(state.westBank)
    }

    private List<RiverState> findNextPossibleStates(RiverState currentState) {
        // from the last visited state, find out who can sail the boat, and where is the sailor
        List<RiverState> possibleStates = []

        transitFrom(currentState, possibleStates)

        return possibleStates
    }

    private void transitFrom(RiverState currentState, List<RiverState> possibleStates) {
        // check where the boat is
        BoatLocation boatOrigin = currentState.boatLocation
        BoatLocation boatDestination

        // we use method closure to get a copy of west bank or east bank roles
        MethodClosure origin, destination

        // multiple assignments
        (origin, destination, boatDestination) = boatOrigin == WestBank ?
            [currentState.&getWestBank, currentState.&getEastBank, EastBank] :
            [currentState.&getEastBank, currentState.&getWestBank, WestBank]

        def possibleSailors = origin().findAll { RiverRole role -> role.canSailTheBoat }

        possibleSailors?.each { RiverRole sailor ->
            // pick 0 passengers onto the boat
            Collection<RiverRole> onBoat = [sailor]
            possibleStates.add(createNextPossibleState(origin, destination, onBoat, boatDestination))

            Collection<RiverRole> possiblePassengers = origin() as Collection<RiverRole>
            possiblePassengers.remove(sailor)

            // pick 1 passenger onto the boat
            possiblePassengers.each { RiverRole passenger ->
                onBoat = [passenger, sailor]
                possibleStates.add(createNextPossibleState(origin, destination, onBoat, boatDestination))
            }
        }
    }

    private RiverState createNextPossibleState(MethodClosure origin, MethodClosure destination, Collection<RiverRole> onBoat, BoatLocation boatDestination) {
        Collection<RiverRole> newDestination = destination() as Collection<RiverRole>
        Collection<RiverRole> newOrigin = origin() as Collection<RiverRole>

        // boat transits from origin to destination
        newOrigin.removeAll(onBoat)
        newDestination.addAll(onBoat)

        return boatDestination == WestBank ? new RiverState(newDestination, newOrigin, boatDestination) : new RiverState(newOrigin, newDestination, boatDestination)
    }


}

FarmerWolfGoatRiddleTest.groovy

import org.junit.Test

import static fun.rivercrossing.BoatLocation.EastBank
import static fun.rivercrossing.BoatLocation.WestBank


class FarmerWolfGoatRiddleTest {

    FarmerWolfGoatRiddle riddle = new FarmerWolfGoatRiddle()

    @Test
    public void findAllPossibleSolutions() {
        def solutions = riddle.findAllPossibleSolutions()
        // the ordering of solutions will be random
        assert solutions.size() == 2
        assert solutions[0].size() == 8
        assert solutions[1].size() == 8

        def assertAllSolutions = { Deque<RiverState> solution1, Deque<RiverState> solution2 ->
            assertFirstSolution(solution1)
            assertSecondSolution(solution2)
        }

        // assert with the correct expectations regardless of which is the first solution
        if (solutions[0].contains(new RiverState([riddle.wolf], [riddle.farmer, riddle.goat, riddle.cabbage], EastBank))) {
            assertAllSolutions(solutions[0], solutions[1])
        } else {
            assertAllSolutions(solutions[1], solutions[0])
        }
    }

    private void assertFirstSolution(Deque<RiverState> solution) {
        assert solution.poll() == new RiverState([riddle.farmer, riddle.wolf, riddle.goat, riddle.cabbage], [], WestBank)
        assert solution.poll() == new RiverState([riddle.wolf, riddle.cabbage], [riddle.farmer, riddle.goat], EastBank)
        assert solution.poll() == new RiverState([riddle.farmer, riddle.wolf, riddle.cabbage], [riddle.goat], WestBank)
        assert solution.poll() == new RiverState([riddle.wolf], [riddle.farmer, riddle.goat, riddle.cabbage], EastBank)
        assert solution.poll() == new RiverState([riddle.farmer, riddle.wolf, riddle.goat], [riddle.cabbage], WestBank)
        assert solution.poll() == new RiverState([riddle.goat], [riddle.farmer, riddle.wolf, riddle.cabbage], EastBank)
        assert solution.poll() == new RiverState([riddle.farmer, riddle.goat], [riddle.wolf, riddle.cabbage], WestBank)
        assert solution.poll() == new RiverState([], [riddle.farmer, riddle.wolf, riddle.goat, riddle.cabbage], EastBank)
        assert solution.poll() == null
    }

    private void assertSecondSolution(Deque<RiverState> solution) {
        assert solution.poll() == new RiverState([riddle.farmer, riddle.wolf, riddle.goat, riddle.cabbage], [], WestBank)
        assert solution.poll() == new RiverState([riddle.wolf, riddle.cabbage], [riddle.farmer, riddle.goat], EastBank)
        assert solution.poll() == new RiverState([riddle.farmer, riddle.wolf, riddle.cabbage], [riddle.goat], WestBank)
        assert solution.poll() == new RiverState([riddle.cabbage], [riddle.farmer, riddle.goat, riddle.wolf], EastBank)
        assert solution.poll() == new RiverState([riddle.farmer, riddle.cabbage, riddle.goat], [riddle.wolf], WestBank)
        assert solution.poll() == new RiverState([riddle.goat], [riddle.farmer, riddle.wolf, riddle.cabbage], EastBank)
        assert solution.poll() == new RiverState([riddle.farmer, riddle.goat], [riddle.wolf, riddle.cabbage], WestBank)
        assert solution.poll() == new RiverState([], [riddle.farmer, riddle.wolf, riddle.goat, riddle.cabbage], EastBank)
        assert solution.poll() == null
    }
}

Fibonacci numbers in Python and Java

Fibonacci numbers,  introduced by Leonardo Pisano Bigollo nearly a thousand years ago, were used to solve a fascinating puzzle about the growth of an idealised rabbit population. Below are the first 11 Fibonacci numbers F_n where n=0, 1, 2,..., 10:

sequence	F0	F1	F2	F3	F4	F5	F6	F7	F8	F9	F10
number	0	1	1	2	3	5	8	13	21	34	55

or we can describe the Fibonacci numbers as

Fn = Fn-1 + Fn-2 (when n>=2)

To write a program to return a Fibonacci number given a sequence, there are many possible implementations. I shall present 2 solutions implemented in both Python and Java, where the first one is using recursion, and the second one is using a while loop, however, the performances of these 2 solutions are drastically different when the sequence is bigger.
Below are the results when running a Python test script. The recursion way is already showing very poor performance comparing to the while loop way.

> python test_fib.py 
.Working out Fibonacci(40)=102334155 recursively took 67.310534 seconds
.Working out Fibonacci(40)=102334155 with while loop took 1.8e-05 seconds
Working out Fibonacci(50)=12586269025 with while loop took 1.6e-05 seconds
Working out Fibonacci(60)=1548008755920 with while loop took 1.8e-05 seconds
..
----------------------------------------------------------------------
Ran 4 tests in 67.312s

OK

If we look at the results when running a similar timed test in Java, the same recursion is not as bad as in Python, though still far poorer than the while loop implementation.

> /somewhere/jdk1.6.0_33/bin/java -classpath ".:" fun.Fib
Working out Fibonacci(40)=102334155 recursively took 408 ms
Working out Fibonacci(40)=102334155 with while loop took 2033 ns
Working out Fibonacci(50)=12586269025 with while loop took 2115 ns
Working out Fibonacci(60)=1548008755920 with while loop took 2368 ns

The reason why recursion is slow in this case is because there are a lot of duplicated operations as the sequence grows. For example, to solve F(5), we need to solve F(4) once, F(3) twice, F(2) three times, and F(1) twice, as shown below

or the number of recursion required given a sequence n is

[1+(n-2)]*(n-2)/2 + (n-3) or n2/2-n/2-2  (when n>=4)

The complexity of using recursion is then actually O(n²), where, on the other hand, the while loop is O(n).
Below are the source code that are used in the test.
fib.py

import datetime


class Fib:
    def recursively(self, n):
        if n == 0:
            return 0
        elif n <= 2:
            return 1
        else:
            return self.recursively(n - 1) + self.recursively(n - 2)

    def whileLoop(self, n):
        if n == 0:
            return 0
        previous, fib, currentIndex = 0, 1, 1
        while currentIndex < n:
            previous, fib = fib, previous + fib
            currentIndex += 1

        return fib

    def timedRecursively(self, n):
        start = datetime.datetime.now()
        result = self.recursively(n)
        end = datetime.datetime.now()
        elapsed = end - start
        print "Working out Fibonacci({})={} recursively took {} seconds".format(str(n), str(result), str(elapsed.total_seconds()))
        return result

    def timedWhileLoop(self, n):
        start = datetime.datetime.now()
        result = self.whileLoop(n)
        end = datetime.datetime.now()
        elapsed = end - start
        print "Working out Fibonacci({})={} with while loop took {} seconds".format(str(n), str(result), str(elapsed.total_seconds()))
        return result

test_fib.py

import unittest
from fib import Fib


class TestFib(unittest.TestCase):
    def setUp(self):
        self.fib = Fib()

    def test_recursively(self):
        self.assertEqual(self.fib.recursively(0), 0)
        self.assertEqual(self.fib.recursively(1), 1)
        self.assertEqual(self.fib.recursively(2), 1)
        self.assertEqual(self.fib.recursively(3), 2)
        self.assertEqual(self.fib.recursively(4), 3)
        self.assertEqual(self.fib.recursively(5), 5)
        self.assertEqual(self.fib.recursively(6), 8)
        self.assertEqual(self.fib.recursively(7), 13)
        self.assertEqual(self.fib.recursively(8), 21)
        self.assertEqual(self.fib.recursively(9), 34)
        self.assertEqual(self.fib.recursively(10), 55)

    def test_whileLoop(self):
        self.assertEqual(self.fib.whileLoop(0), 0)
        self.assertEqual(self.fib.whileLoop(1), 1)
        self.assertEqual(self.fib.whileLoop(2), 1)
        self.assertEqual(self.fib.whileLoop(3), 2)
        self.assertEqual(self.fib.whileLoop(4), 3)
        self.assertEqual(self.fib.whileLoop(5), 5)
        self.assertEqual(self.fib.whileLoop(6), 8)
        self.assertEqual(self.fib.whileLoop(7), 13)
        self.assertEqual(self.fib.whileLoop(8), 21)
        self.assertEqual(self.fib.whileLoop(9), 34)
        self.assertEqual(self.fib.whileLoop(10), 55)

    def test_timedRecursively(self):
        self.assertEqual(self.fib.timedRecursively(40), 102334155)

    def test_timedWhileLoop(self):
        self.assertEqual(self.fib.timedWhileLoop(40), 102334155)
        self.assertEqual(self.fib.timedWhileLoop(50), 12586269025)
        self.assertEqual(self.fib.timedWhileLoop(60), 1548008755920)

unittest.main()

Fib.java

package fun;

public class Fib {


    public static void main(String[] args) {
        recursively(1);
        whileLoop(1);

        long start = System.nanoTime();

        long result = recursively(40);
        long elapsed = (System.nanoTime() - start) / 1000000;
        System.out.println(String.format("Working out Fibonacci(%s)=%s recursively took %s ms", 40, result, elapsed));

        start = System.nanoTime();
        result = whileLoop(40);
        elapsed = (System.nanoTime() - start);
        System.out.println(String.format("Working out Fibonacci(%s)=%s with while loop took %s ns", 40, result, elapsed));

        start = System.nanoTime();
        result = whileLoop(50);
        elapsed = (System.nanoTime() - start);
        System.out.println(String.format("Working out Fibonacci(%s)=%s with while loop took %s ns", 50, result, elapsed));

        start = System.nanoTime();
        result = whileLoop(60);
        elapsed = (System.nanoTime() - start);
        System.out.println(String.format("Working out Fibonacci(%s)=%s with while loop took %s ns", 60, result, elapsed));
    }

    static long recursively(long i) {
        if (i == 0) return 0;
        if (i <= 2) return 1;
        else return recursively(i - 1) + recursively(i - 2);
    }

    static long whileLoop(long i) {
        long previous = 0, fib = 1, currentIndex = 1;
        while (currentIndex < i) {
            long newFib = previous + fib;
            previous = fib;
            fib = newFib;
            currentIndex++;
        }
        return fib;
    }
}

First impression of Python

Born some two decades ago, Python has certainly accumulated enough interests to become one of the most popular programming languages used in the financial industry.

Designed to be a write-less-do-more language, Python has certain aspects that differ from Java:

1. It is an interpreted language, which means no compilation is required. 
2. It is not a strongly typed language
3. Its statement grouping is done by indentation instead of open and close braces
4. It does not require declaration of variable or argument
5. It supports complex number, for example (using Python interactive interpreter)

>>> 1j + 2J
(-2+0j)
>>> (1+2j) * complex(2,3)
(-4+7j)

6. Strings can be subscripted. For example, the first character of a string has index 0.

>>> word="HelloWorld"
>>> word[4]
'o'
>>> word[1:3]   # using the slice notation, returning characters from index 1 to 2
'el'

7. It supports multiple assignment, for example, 'a,b=b,a+b', where the expression on the right-hand side 'b,a+b' are evaluated first before any of the assignments take place
8. Not surprisingly, it supports lamda forms

>>> def incresedBy(n):
...     return lambda x: x + n
...
>>> f = incresedBy(42)
>>> f(1)
43

9. It supports map and reduce functions as part of its functional programming offerings
10. It supports Tuples, which are immutable and usually contain an heterogeneous sequence of elements

>>> t=123,321,'hello'
>>> t
(123, 321, 'hello')

11. It allows multiple inheritance, for example

class DerivedClassName(Base1, Base2, Base3):
    <statement-1>
    .
    .
    .
    <statement-N>

An efficient Stack implementation with getMin() and getMax() methods

When we use stack to keep a collection of numbers, we might want to know what are the minimum and maximum numbers in the stack. 

Suppose we are pushing {72,12,55,78,22,34} into a stack, this is what happens

Action	Stack Elements (Top ... Bottom)	Min	Max
push(72)	72	72	72
push(12)	12,72	12	72
push(55)	55,12,72	12	72
push(78)	78,55,12,72	12	78
push(22)	22,78,55,12,72	12	78
push(34)	34,22,78,55,12,72	12	78

If we pop the stack above 3 times, the max should change to 72; if we pop 2 more times, the min should change to 72. It sounds like we need a data structure that keeps the current min and max when we push or pop the stack. Indeed, a stack is a perfect choice here. When pushing a number to the stack, we also push the current min and max values into the min and max stacks respectively. Similarly, when poping out a number from the stack, we also pop out from the min and max stacks, such that the top of the min and max stacks will always have the min and max values of the current stack respectively.

The complexity of the getMin() and getMax() methods are O(1), regardless of how many items are in the stack, same as the push(item) and pop() methods.

Here is an implementation of the Stack with getMin() and getMax() methods

import java.util.Stack;
import java.util.concurrent.locks.ReentrantReadWriteLock;

public class SmartStack<E extends Comparable<E>> {

    private ReentrantReadWriteLock readWriteLock = new ReentrantReadWriteLock();
    private ReentrantReadWriteLock.ReadLock readLock = readWriteLock.readLock();
    private ReentrantReadWriteLock.WriteLock writeLock = readWriteLock.writeLock();

    private Stack<E> mins = new Stack<E>();
    private Stack<E> maxs = new Stack<E>();
    private Stack<E> delegate = new Stack<E>();

    public E push(E item) {
        writeLock.lock();
        try {
            // stores the current min to the mins stack
            if (mins.isEmpty() || (!mins.isEmpty() && item.compareTo(mins.peek()) < 0)) {
                mins.push(item);
            } else {
                mins.push(mins.peek());
            }

            // stores the current max to the maxs stack
            if (maxs.isEmpty() || (!maxs.isEmpty() && item.compareTo(maxs.peek()) > 0)) {
                maxs.push(item);
            } else {
                maxs.push(maxs.peek());
            }

            return delegate.push(item);
        } finally {
            writeLock.unlock();
        }
    }

    public E pop() {
        writeLock.lock();
        try {
            E item = delegate.pop();
            // pop both mins and maxs stacks, such that peeking on them will tell us the current min or max
            mins.pop();
            maxs.pop();
            return item;
        } finally {
            writeLock.unlock();
        }
    }

    public E peek() {
        readLock.lock();
        try {
            return delegate.peek();
        } finally {
            readLock.unlock();
        }
    }

    public E getMin() {
        readLock.lock();
        try {
            return mins.peek();
        } finally {
            readLock.unlock();
        }
    }

    public E getMax() {
        readLock.lock();
        try {
            return maxs.peek();
        } finally {
            readLock.unlock();
        }
    }

    public boolean empty() {
        readLock.lock();
        try {
            return delegate.empty();
        } finally {
            readLock.unlock();
        }
    }

    public int search(E item) {
        readLock.lock();
        try {
            return delegate.search(item);
        } finally {
            readLock.unlock();
        }
    }
    
}

Here is the unit test of the above class written in Groovy

import org.junit.Before
import org.junit.Test

class SmartStackTest {

    SmartStack stack

    @Before
    public void before() {
        stack = new SmartStack()
        stack.push(72)
        stack.push(12)
        stack.push(55)
        stack.push(78)
        stack.push(22)
        stack.push(34)
    }

    @Test
    public void canGetCurrentMinValue() {
        assert stack.min == 12

        5.times { stack.pop() }

        assert stack.min == 72
    }

    @Test
    public void canGetCurrentMaxValue() {
        assert stack.max == 78

        4.times { stack.pop() }

        assert stack.max == 72
    }

    @Test
    public void canPeek() {
        assert stack.peek() == 34
    }

    @Test
    public void isEmpty() {
        assert !stack.empty()
    }

    @Test
    public void canSearch() {
        // the 1-based position from the top of the stack where the object is located
        assert stack.search(34) == 1
        assert stack.search(22) == 2
        assert stack.search(78) == 3
        assert stack.search(55) == 4
        assert stack.search(12) == 5
        assert stack.search(72) == 6
        // not in the stack should return -1
        assert stack.search(11112) == -1
    }
    
}