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 

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 nonprime 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 Integer
s 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 

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.