I’ve recently had to set up and manage about a dozen Linux based virtual servers (not a huge number, but still) and it’s handly to have a separate user account on these machines that I can use to connect to for interactive use. With that in mind here are a couple of quick tips for setting things up for a more pleasant experience with minimal fuss.

I like to use zsh as my shell, but that’s easy enough to install via apt-get and so can be added to an automated build script. The fastest way to get a good configuration installed is via Oh My Zsh!, it uses the fairly horrible curl | sh installation style, so I don’t like to add it to an automated script, but it’s easy enough to check and run manually:

$ curl -L http://install.ohmyz.sh | sh

The other thing is to get a decent vim setup, for this I use SPF-13 which installs in a similar manner:

$ curl http://j.mp/spf13-vim3 -L -o - | sh

Then I usually set up a couple of aliases based on what the machine will be used for, and I’m done.

Following on from my previous post I’m attempting the next Programming Praxis excercise: computing the probability of a winning board at Bingo tournaments of various sizes.

Probably the most common means of solving this kind of probability problem is the Monte Carlo method, which uses randomization and statistical sampling to estimate probabilities. Luckiy for me, the problem space for Bingo is small enough that it is possible completely analyze the game and present exact numbers.

The individual functions are all pretty short so I’ll walk through the maths and code at the same time.

Laying the Foundations

Now, some of the numbers are going to get pretty big so primitive math won’t cut it. I’m going to define a few helper functions to make working with arbitrary-precision maths easier. I’m also gong to specify a limited precision context to use for division operations, as I’d rather lose a small amount of precision that get an ArithmeticException if we hit any irrational numbers.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

private static final MathContext DIVISION = new MathContext(128);

static BigDecimal d(long l) {
    return new BigDecimal(l, MathContext.UNLIMITED);
}

static BigDecimal add(BigDecimal a, BigDecimal b) {
    return a.add(b, MathContext.UNLIMITED);
}

static BigDecimal sub(BigDecimal a, BigDecimal b) {
    return a.subtract(b);
}

static BigDecimal mul(BigDecimal a, BigDecimal b) {
    return a.multiply(b, MathContext.UNLIMITED);
}

static BigDecimal div(BigDecimal a, BigDecimal b) {
    return a.divide(b, DIVISION);
}

static BigDecimal pow(BigDecimal a, int b) {
    return a.pow(b, MathContext.UNLIMITED);
}

To show how these work let’s define a factorial function, which is need in a moment anyway.

1
2
3
4
5
6
7

static BigDecimal fact(BigDecimal n) {
    switch (n.compareTo(ONE)) {
        case -1: return ZERO;
        case  0: return ONE;
        default: return mul(n, fact(sub(n, ONE)));
    }
}

We’re also going to need a combination function, which will return the number of distinct combinations of k values drawn from a set S. Formally this is known as the binomial coefficient and is described by:

\begin{equation} c(S,k) = {S! \over k!\space (S - k)!} \label{combine} \end{equation}

The code that implements this is pretty much a literal translation of the equation, with a little data conversion and a shortcut for the case where we want to select no items or the entire set.

1
2
3
4
5
6
7

static BigDecimal combinations(int S, int k) {
    if (k < 0 || k > S) { return ZERO; }
    if (k == 0 || k == S) { return ONE; }
    BigDecimal bS = d(S);
    BigDecimal bk = d(k);
    return div(fact(bS), mul(fact(bk), fact(sub(bS, bk))));
}

There are faster algorithms than this, but this is easy to understand and sufficient for our needs.

Describing Bingo Mathematically

A Bingo board is comprised of a set of squares S, each with a number n chosen at random from the set N. Typically S comprises a 5x5 grid and N is the set of integers from 1 to 75. As an added wrinkle the centre square in the grid is a free space which is always assumed to be hit, this means that a 5x5 grid is actually a 24 element set.

To keep things simple I’m going to assume that we are using a typical board and number set, so I’ll just use constants to hold the cardinalities (sizes) of the two sets.

1
2

static final int NUMBERS = 75;
static final int SQUARES = 24;

The first thing we need to figure out is the cumulative probabity of winning after n numbers have been called (i.e. the probability of winning when the 4th number is called, when the 5th number is called, and so on). This can be found by looking at the probability of there being 4 hits and those 4 forming a Bingo, plus the probability of there being 5 hits and those 5 forming a Bingo, and so on up to the number of calls made so far. Note that we start at 4 as this is the minimum number of calls needed for a Bingo.

Assuming that we have a function p(n) which returns the probability of there being a Bingo when there are n hits, the cumulative probability of winning after n calls is given by:

\begin{equation} w(n) = \sum _ {i=4}^n {c(|S|, i)\space c(|N| - |S|, n - i) \over c(|N|, n)} p(i) \label{cumulative} \end{equation}

Substituting in the values for the sizes of the board and number set simplifies this to:

\begin{equation} w(n) = \sum _ {i=4}^n {c(24, i)\space c(51, n - i) \over c(75, n)} p(i) \label{cumulative-simple} \end{equation}

But we still need to define p(n), this is where the small problem space comes in handy…

Assemble a Brute Squad

The probability of a Bingo given n hits on the board is the number of possible Bingo positions divided by the total number of positions, so before we can work out the probability we need to get the number of Bingo positions for each hit count.

As I mentioned earlier will use a brute force method of calculating the probability of a Bingo given n hits on the board. To do this we first need to come up with a representation of a board, as it only takes a single bit to represent the state of each square and there are only 24 squares, we can just use an int for this.

Here’s how we do that: number the squares from 0–23 left-to-right and top-to-bottom like so (FS represents the free space in the centre):

Then starting from the least significant bit we can use a 1 to represent a hit square and a 0 to represent an empty square. So a Bingo across the top row, with all other squares being empty is represented by 0b111110000000000000000000; this and the remaining 11 possible Bingo positions (5 rows, 5 columns, and the 2 diagonals) can be represented like so:

1
2
3
4
5
6
7
8

static final int[] BINGOS = {
    0b111110000000000000000000, 0b000001111100000000000000,
    0b000000000011110000000000, 0b000000000000001111100000,
    0b000000000000000000011111, 0b100001000010001000010000,
    0b010000100001000100001000, 0b001000010000000010000100,
    0b000100001000010001000010, 0b000010000100010000100001,
    0b100000100000000001000001, 0b000010001000000100010000
}

To create the array of Bingo combinations (indexed by number of hits, so a 25 element array) we will just loop through every possible board layout (i.e. the integers 0 through 0b11111111111111111111111) and check each of them against the list of Bingo positions, if there is a match we can use the Integer.bitCount() method to count the number of hits on the board and then increment the counter there. The full code for this is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

final long[] bingoCombinations = createBingoCombinations();

long[] createBingoCombinations() {
    long[] combinations = new long[SQUARES + 1];
    for (int i = 0; i <= 0b111111111111111111111111; ++i) {
        for (int bingo : BINGOS) {
            if ((i & bingo) == bingo) {
                combinations[Integer.bitCount(i)]++;
                break;
            }
        }
    }
    return combinations;
}

Given this we can now calculate the probability of a Bingo at each hit count as described above, the code for this is:

1
2
3
4
5
6
7
8
9
10
11
12

final BigDecimal[] bingoProbabilities = createBingoProbabilities();

BigDecimal[] createBingoProbabilities() {
    BigDecimal[] probabilities = new BigDecimal[SQUARES + 1];
    for (int i = 0; i < 4; ++i) {
        probabilities[i] = ZERO;
    }
    for (int i = 4; i <= SQUARES; ++i) {
        probabilities[i] = div(d(bingoCombinations[i]), combinations(SQUARES, i));
    }
    return probabilities;
}

The last thing we need before moving on to calculate the actual chances of winning is a function to determine the probability of there being k hits hits on the board after n numbers have been called (the bit in equation \eqref{cumulative} that is being multiplied by p(n) and then summed). It’s just a literal translation of the equation:

1
2
3
4

static BigDecimal getHitProbability(int numHits, int numCalls) {
    return div(mul(combinations(24, numHits), combinations(51, numCalls - numHits)),
            combinations(75, numCalls));
}

Chances of Winning?

We’ve now got everything we need to write the code for equation \eqref{cumulative}, given the previous function and the pre-computed array of proabilities the code to do this is simple:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

BigDecimal[] createBoardProbabilities() {
    BigDecimal[] probabilities = new BigDecimal[NUMBERS + 1];
    for (int n = 0; n < 4; ++n) {
        probabilities[n] = ZERO;
    }
    for (int n = 4; n <= NUMBERS; ++n) {
        BigDecimal sum = ZERO;
        for (int s = 4; s <= SQUARES; ++s) {
            sum = add(sum, mul(getHitProbability(s, n), bingoProbabilities[s]));
        }
        probabilities[n] = sum;
    }
    return probabilities;
}

This is fine for a single board, but what about the odds for a real game, with many players? The odds of finding a winner when there are k boards is given by:

\begin{equation} m(n,k) = 1 - (1 - w(n))^k \label{many} \end{equation}

Armed with this we can implement a function to return the probability of a winning board for any number of boards and numbers called like so:

1
2
3
4
5
6

BigDecimal getProbability(int numCalls, int numBoards) {
    if (numBoards == 1) {
        return boardProbabilities[numCalls];
    }
    return sub(ONE, pow(sub(ONE, boardProbabilities[numCalls]), numBoards));
}

And that’s everything! All that’s left to add is a main method to print out some stats and that’s it.

1
2
3
4
5

public static void main(String[] args) {
    BingoOdds bingo = new BingoOdds();
    bingo.printStatistics();
    bingo.printProbabilities(1, 10, 25, 50);
}

If you want to play with this some more, an interesting excercise would be to generalize this for any size of board and token (number) set. To do that you’ll need to get rid of the static BINGOS array and calculate id dynamically, based on the size of the square, other than that and a coupl of constants that need to be replaced by variables everything else should work as is.

The full code, including the implementations of the print methods can be found on GitHub.

Over the weekend I stumbled across the Programming Praxis web site, a blog that aims to “publishes new programming exercises weekly, at least, so that savvy programmers can maintain their skills by working the exercises and thinking outside their normal skill set”. It’s been running for about three years now and at the time of writing there are almost 400 problems there. I thought that I’d like to have a go at solving a few of them, I’m going to try solving them in Java initially, and then maybe revisit them in other languages to compare the solutions.

I’ve got solutions to the first couple of problems ready to go, and all of my solutions can be found in this project on GitHub.

Reverse Polish Notation Calculator

This is trivial to implement in Java using the built in Console class, the complete implementation (sans class boilerplace and imports) is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

private static final Console console = System.console();
private static final Deque<BigDecimal> stack = new ArrayDeque<>();

private static void processLine(String line) {
    for (String s : line.split("\\s+")) {
        if ("+".equals(s)) {
            stack.push(stack.pop().add(stack.pop()));
        } else if ("-".equals(s)) {
            stack.push(stack.pop().subtract(stack.pop()));
        } else if ("*".equals(s)) {
            stack.push(stack.pop().multiply(stack.pop()));
        } else if ("/".equals(s)) {
            stack.push(stack.pop().divide(stack.pop()));
        } else if ("exit".equalsIgnoreCase(s) || "quit".equalsIgnoreCase(s)) {
            System.exit(0);
        } else {
            stack.push(new BigDecimal(s));
        }
    }
    console.format("%s%n", stack.peek()).flush();
}

public static void main(String[] args) {
    try {
        String line;
        while ((line = console.readLine("> ")) != null) {
            processLine(line);
        }
    } catch (Exception e) {
        console.format("%s: %s%n", e.getClass().getSimpleName(), e.getMessage());
    }
}

Compared with other solutions the only interesting things are the use of BigDecimal instead of primitive types, this means that the calculator supports a wider range of numbers and input formats, and the use of a Deque as the stack, this is a more modern class than the old Java 1.0 vintage Stack class.

The full class is here.

Sieve of Eratosthenes

This classic algotrithm is a bit more interesting: my first thought was to lazily create the list of primes using modulo checks to filter out non-prime numbers. Technically this isn’t the Sieve of Eratosthenes, but it’s logically the same. Well, it performed terribly taking several seconds to compute the first million primes.

It turns out that one of the reasons the actual sieve is so fast is that it only uses addition rather than the more expensive modulo operations. This, plus the memory saving gained from using a BitSet instead of a list of Integers gave me a nice, zippy, implementation. The relevant method is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public static BitSet sieve(int target) {
    BitSet primes = new BitSet(target);
    if (target < 2) { return primes; }
    primes.set(2);
    if (target < 3) { return primes; }
    for (int i = 3; i <= target; i += 2) {
        primes.set(i);
    }
    for (int prime = 3; prime * prime < target; prime = primes.nextSetBit(prime + 1)) {
        for (int i = prime + prime; i <= target; i += prime) {
            primes.clear(i);
        }
    }
    return primes;
}

And of course in a real implementation this would be a good candidate for memoization giving you O(1) performance in the common case.

The full class is here.

I started to write a ‘quick’ response to this post about builders and it kind of got out of hand, so I’m putting it up here instead.

The post isn’t bad, but I think that Marcin is getting the builder and factory patterns a little mixed up. To recap:

The intent of the Builder Pattern is to separate out the construction of an object from it’s final representation. Doing this makes it easier to enforce preconditions and invariants, and also makes the object construction easier to read in languages without keyword arguments.

The intent of the Factory Pattern on the other hand, is to delegate responsibility for creating an object to somebody else. It is commonly used in dependency injection frameworks.

A concrete example should serve to illustrate the differences.

A Builder Example

Assume that we have an interface for a simple Pojo:

1
2
3
4
5
6
7

public interface Employee {
    public Date getHiredAt();
    public String getId();
    public String getName();
    public int getSalary();
    public String getTitle();
}

and a default implementation (shown here as a separae class, but it could also be a static inner class in the interface):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class EmployeeImpl implements Employee {

    private final String _id;
    private final String _name;
    private final String _title;
    private final int _salary;
    private final Date _hiredAt;

    EmployeeImpl(String id, String name, String title, int salary, Date hiredAt) {
        _id = id;
        _name = name;
        _title = title;
        _salary = salary;
        _hiredAt = hiredAt;
    }

    public Date getHiredAt() {
        return _hiredAt;
    }

    public String getId() {
        return _id;
    }

    // ...

    @Override
    public String toString() {
        return Objects.toStringHelper(this).omitNullValues()
            .add("id", _id)
            .add("name", _name)
            .add("title", _title)
            .add("salary", _salary)
            .add("hiredAt", _hiredAt)
            .toString();
    }
}

Even with just a few fields like this invoking the constructor becomes somewhat ugly:

1
2

Employee e = new EmployeeImpl(
    "1", "Fred Foobar", "Engineer", 100000, new Date());

Without referring to the docs or source code how do you know what all of those strings mean? How do you know that you have them in the correct order? And if it seems reasonable clear in this example imaging if your Pojo was mainly non-string data!

1

MyPojo p = new MyPojoImpl(123, true false, false 45.83, "wtf???");

Clear as mud, right?

Other languages don’t have this problem, for example in Objective-C we would write something like:

1
2

id obj = [EGEmployee employeeWithId:@"1" name:@"Fred Foobar"
        title:@"Apple Engineer" salary:200000 hiredAt:@"2001-03-24"];

which is much clearer. Ruby, Python, and other languages all have similar constructs. Adding a builder allows us to gain the same level of clarity in Java, and it provides a good place for us to perform any additional checks before creating the object. Here’s a typical implementation and an example of calling it:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

public class Builder {

    private static final AtomicInteger _ids = new AtomicInteger();

    private static String checkString(String value, String name) {
        value = nullToEmpty(value).trim();
        checkArgument(!value.isEmpty(), "%s cannot be null or empty", name);
        return value;
    }

    private String _id;
    private String _name;
    private String _title;
    private Integer _salary;
    private Date _hiredAt;

    public Builder hiredAt(Date hiredAt) {
        _hiredAt = hiredAt;
        return this;
    }

    public Builder id(String id) {
        _id = id;
        return this;
    }

    public Builder name(String name) {
        _name = name;
        return this;
    }

    public Builder salary(int salary) {
        checkArgument(salary >= 0, "salary cannot be negative");
        _salary = salary;
        return this;
    }

    public Builder title(String title) {
        _title = title;
        return this;
    }

    public Employee build() {
        return new Impl(
                _id != null ? _id : String.format("emp:%06d", _ids.incrementAndGet()),
                checkString(_name, "name"),
                checkString(_title, "title"),
                checkNotNull(_salary, "salary"),
                _hiredAt != null ? _hiredAt : new Date());
    }
}

// elsewhere ...
public Employee findEmployeeById(String id) {
    if ("1".equals(id)) {
        return new Builder().id(id)
            .name("Fred Foobar")
            .title("Engineer")
            .salary(100000)
            .hiredAt("2001-03-24").build();
    }
    return null;
}

Again, all pretty clear now, and HotSpot will inline all of those method calls no there should be no additional overhead once the JVM is up and running.

A Factory Example

Factories are different, but it would be common for a factory to use a builder to create the objects that it vends. For example, here is a factory for employee objects (it doesn’t need to have the word Factory in it’s name):

1
2
3
4

public interface Employees {
    Iterable<Employee> all();
    Employee findbyId(String id);
}

We can then have different implementations of this, maybe one that loads data from a CSV or JSON file for testing purposes, and one that loads data via JDBC for production use.

Aside: if you’re familiar with domain-driven design you’ll be forgiven for noticing a lot of overlap between the factory pattern and DDD’s concept of repositories, they’re very similar concepts. One difference being that factories are often able to create new objects ex nihilo while repositories usually retreive objects from external sources. Compare the findById() method with the newInstance() methods employed by many of the factory classes in the JDK.

Hopefully you can see from this post that the two patterns have different—if complementary—aims.

A complete example project with all of this code, as well as test cases and a CSV based implementation the the factory are available on Github.

This is a joke, right?