Alex Bowe

Blog

Regularly Divisble

by Leave a Comment

div3

Update: read the comments at Hacker News to see some succinct approaches to this, as discussed by gjm11, qntm and patio11. Thanks to Robin for providing this demonstration that can find a regex for testing divisibility of any number, in any base (he also made the code available, nice).

Earlier this year, at the advice (once more) of Chad Fowler, I took to the idea of practicing programming every day. Perhaps this appealed to me because it echoed the rituals of my better musician friends, and allowed me to draw parallels between programming and my fading dream of becoming a famous rockstar.

Possibly because of my failed interview at Google (hey, I wouldn’t have hired the back-then me either, so no hard feelings!), I was also interested in job-interview styled problems [1]. Not FizzBuzz though, more like the computer science ‘riddles’ found on this page [2].

At the time I was teaching Computing Theory [3], 80% of which was formal languages: regular expressions, context free and context sensitive grammars, Turing machines and other automata, and their locations in the Chomsky Hierarchy. So, this problem appealed to me:

Construct a finite state machine (or equivalently, write a regular expression) which accepts all strings over the alphabet {0,1} which are divisible by 3 when interpreted in binary.

It is pretty interesting that languages can be defined to communicate patterns in binary sequences that are divisible by 3. Let’s solve it in more detail than necessary :)…

[Read more…] about Regularly Divisble

Things Smarter People Said #1

by Leave a Comment

iterdesign

I am currently reading Code Complete 2 as per Jeff Atwood’s Recommended Reading for Developers list, where I came across this interesting quote by Glenford Myers:

We try to solve the problem by rushing through the design process so that enough time is left at the end of the project to uncover the errors that were made because we rushed through the design process”

I think it succinctly illustrates the need for balance in software design; it is just vague enough to communicate exactly what you need to hear.

I’m interested in hearing any other cool quotes, or book recommendations if you’ve got some =]

How to Win Friends and Generate People

by Leave a Comment

Dice

I’m doing a project for a subject at RMIT which needs to manage thousands of patient records for a hospital. We haven’t been given any sample data though, so I wanted to write a generator (so we can test it with small or large data sets whenever needed).

I started with the name generator (in Python), which selected a random male/female/last name from a file [1]. I then realised an address generator would behave similarly (street, city, country lists), so I decided to make a Generator base class. You can get the source code for these here.

I wanted the Generator base class to create methods dynamically; It would be instantiated with a bunch of methodname-filename pairs and have the methods for randomly selecting an entry from each file made dynamically. Exactly how to do this wasn’t easy to find, as it wasn’t well documented… the solution ended up being:

Niki (my brother) helped me get 70% of the way there… (after lots of scope and decorator issues) thanks man :)

[1] The name lists were taken from this census data, which actually provides percentages for each name too, if you wanted to make the name distribution more realistic…

Nanosecond Timing

by Leave a Comment

My Uni (RMIT) uses a mixture of Solaris, Mac OS X, Linux, and Windows computer labs. Our programs are nearly always tested on Solaris, though. Sometimes we are required to provide nanosecond timings in our experiments using the (real-time) POSIX function gethrtime().

Depending on which lab I work in, or if I’m working from home, I might need to comment out (or add compile guards) into my code to compile it correctly. This can make the code less readable, and can make its behavior (particularly output) on Solaris less obvious while testing on a foreign system.

Although the granularity, accuracy and any possible side effects (such as function overhead, or being affected by changing the system clock) may be different for each function, I find it helps to at least give a ball-park figure. Experiments should still be done on Solaris. If you want to use or modify my nanosecond function call wrapper, get it on GitHub.

Note: Not thoroughly tested on all target operating systems or compilers. It is only intended as a convenience.