Programming the Number Plate Game

by Hamilton Chapman


Last Summer I went to T in the Park, a music festival in Kinross, Scotland. My trip up to Scotland was split into two parts due to me having my graduation on the first day of the festival. However, on the way back home I was able to get a lift with some friends in a car. Travelling from Scotland down to Guildford takes a good long while, about 10 hours in our case, and as you can imagine things can start to get a bit boring.

One of the games we played while driving down was new to me. It was cleverly referred to as "The Numberplate Game". It involves looking out of the front of the car and reading the last three letters on a car's numberplate, for example you'd take DCD from HM09 DCD. With these letters you're then tasked with thinking of a word that contains all of the letters in that order. The letters don't necessarily have to be adjacent nor does the first letter of the word have to be the first letter of the three from the numberplate.

Continuing on with HM09 DCD a valid answer would be DECIDE. Equally you could go with UNDECIDED. Everyone in the car enjoyed the game and there was some healthy competition between us all.

When I got home I asked the rest of my family if any of them had played the game before and none of them had. At the time I was teaching myself to do some programming using Objective-C and so I thought it would be a fun little practice app to make.

At the core of the game is the ability to determine whether or not a given answer is acceptable given the three letters from the numberplate. It's simple enough to code this up. My first attempt was something roughly like this:

bool isCharInString(NSString *charToCheck, NSString *stringToCheckForChar)
{
  return [stringToCheckForChar rangeOfString:charToCheck options:NSCaseInsensitiveSearch].location != NSNotFound;
}

bool guessContainsValidTriple(NSString *randomTriple, NSRange firstLetter, NSRange secondLetter, NSRange thirdLetter, NSString *guess)
{
 bool validGuess = false;
 NSString *firstLetterOfTriple = [randomTriple substringWithRange:firstLetter];
 NSString *secondLetterOfTriple = [randomTriple substringWithRange:secondLetter];
 NSString *thirdLetterOfTriple = [randomTriple substringWithRange:thirdLetter];

 if(isCharInString(guess, firstLetterOfTriple))
 {
   NSInteger firstLetterLocation = [guess rangeOfString:[randomTriple substringWithRange:firstLetter] options:NSCaseInsensitiveSearch].location;

   if(firstLetterLocation == [guess length] - 1)
   {
     return validGuess;
   }

   NSRange rangeForSecondLetter = {firstLetterLocation + 1, [guess length] - (firstLetterLocation + 1)};       
   NSString *stringToCheckForSecondLetter = [guess substringWithRange:rangeForSecondLetter];

   if(isCharInString(stringToCheckForSecondLetter, secondLetterOfTriple))
   {
     NSInteger secondLetterLocation = [stringToCheckForSecondLetter rangeOfString:[randomTriple substringWithRange:secondLetter] options:NSCaseInsensitiveSearch].location + firstLetterLocation + 1;
     if(secondLetterLocation == [guess length] - 1)
     {
       return validGuess;
     }

     NSRange rangeForThirdLetter = {secondLetterLocation + 1, [guess length] - (secondLetterLocation + 1)};
     NSString *stringToCheckForThirdLetter = [guess substringWithRange:rangeForThirdLetter];

     if(isCharInString(stringToCheckForThirdLetter, thirdLetterOfTriple))
     {
       validGuess = true;
     }
   }
 }
 return validGuess;
}

Not pretty. And not very fast. Not at all. Speed isn't a problem when you're just checking if one word contains a given set of three letters. However, I realised that if I wanted to make the game usable and fun to play then I'd want to have an idea of how many occurrences there are of each set of three letters in the English dictionary, if any. You don't want to ask a player to try and come up with a word that contains three letters that are never actually found in the given order in a word in the dictionary. I didn't even know if such a set of letters existed. Moreover, knowing the number of occurrences would allow me to implement some concept of difficulty.

At the same time as all of this I decided that it would be fun to be able to do it with pairs of letters as well as sets of 4 letters. Even with the pairs of letters I still wanted to know how frequently they were found in the dictionary. It's easy to guess whether words containing ES are more common than words containing ZJ, but by what magnitude?

I set up the code to loop through all of the possible combinations of sets of 2, 3, and 4 letters and had my code then cycle through all of the words in the dictionary for each set of letters and check whether the word contained the letters. I started running the code and waited. I could see my CPU at 100%. Had it hung? Was there an infinite loop? Maybe it was just taking a while? I let it run a bit longer until about half an hour had passed. CPU still at 100%.

I decided to stop it and then put in some logging to see where it had gotten up to as it ploughed through the work.

It was slow. So slow. Out of curiosity I let it run to completion and could see from the logs that it had taken just shy of 30 hours to complete. Not ideal. Although given the numbers involved it didn't seem too ridiculous. 26 letters in the alphabet, about 250,000 words in the dictionary I had. That made about 26 * 26 * 250,000 = 169,000,000 passes just for the pairs of letters. In total it meant about 118,807,000,000 runs through the loops. I needed to speed it up.

I tried bolting on some changes to the previous attempt and then chopped bits up and moved them around but it felt like it was getting too cumbersome. I decided to just rewrite it with the same basic ideas powering it, but with some tweaks here and there. Oh, and it was generalised so that it would work with sets that contained any number of letters. This is what it ended up looking like.

bool isCharInString(NSString *charToCheck, NSString *stringToCheckForChar)
{
  return [stringToCheckForChar rangeOfString:charToCheck options:NSCaseInsensitiveSearch].location != NSNotFound;
}

bool guessContainsValidSetOfLetters(NSString *guess, NSString *setOfLetters)
{
  bool validGuess = false;

  NSInteger numOfLettersInSet = setOfLetters.length - (setOfLetters.length / 2);
  NSInteger numOfCurrentLetter = 1;
  NSString *stringToCheckForChar = guess;

  while(!validGuess && numOfCurrentLetter <= data-preserve-html-node="true" numOfLettersInSet)
  {
    NSRange letterToCheck = {2 * numOfCurrentLetter - 2, 1};
    NSString *charToCheck = [setOfLetters substringWithRange:letterToCheck];
    NSInteger letterLocationInWord = [guess rangeOfString:[setOfLetters substringWithRange:letterToCheck] options:NSCaseInsensitiveSearch].location;

    if(isCharInString(charToCheck, stringToCheckForChar))
    {
      if((letterLocationInWord == [guess length] - 1) && numOfCurrentLetter < numOfLettersInSet)
      {
        return validGuess;
      }
      NSRange rangeToCheckNext = {letterLocationInWord + 1, [guess length] - (letterLocationInWord+ 1)};
      stringToCheckForChar = [guess substringWithRange:rangeToCheckNext];

      if(numOfCurrentLetter == numOfLettersInSet)
      {
        validGuess = true;
      }
    }
    else
    {
      return validGuess;
    }
    numOfCurrentLetter++;
  }
  return validGuess;
}

A definite improvement. The generalisation was great, it was easier to read (and debug), but it wasn't really much quicker. There was a small bump, but nothing to make me feel satisfied.

Maybe regular expressions would help me speed things up? It seemed like I'd be able to cut out some code, which is always useful when you're looking for a speed boost.

I'll say it now; I'm by no means a master of regular expressions. This may well be a horrible way of using them but it made sense to me at the time.

NSRegularExpression *createRegexFromLetters(NSString *setOfLetters)
{
  NSString *regexString = @".*";
  for (NSString *letter in letters(setOfLetters))
  {
    regexString = [regexString stringByAppendingString:letter];
    regexString = [regexString stringByAppendingString:@".*"];
  }
  return [NSRegularExpression regularExpressionWithPattern:(@"%@", regexString)
   options:NSRegularExpressionCaseInsensitive
   error:nil];
}

bool wordContainsLetters(NSString *word, NSString *setOfLetters, NSRegularExpression *regex)
{
  return [regex numberOfMatchesInString:word options:0 range:NSMakeRange(0, [word length])] > 0;
}

Pretty compact. Pretty easy to follow. Pretty slow.

In fact SLOWER

Back to the drawing board.

How about using a recursive method instead of nesting for loops or using a while loop? I set about writing this method, again being conscious of performance, and ended up with the following.

NSInteger numberOfLettersInSet(NSString *setOfLetters)
{
  return [letters(setOfLetters) count];
}

NSArray *letters(NSString *setOfLetters)
{
  return [setOfLetters componentsSeparatedByString:@" "];
}

bool lettersAreInWord (NSString *word, NSString *setOfLetters)
{
  if(setOfLetters.length == 1)
  {
    return [word rangeOfString:setOfLetters options:NSCaseInsensitiveSearch].location != NSNotFound;
  }

  if([word rangeOfString:[setOfLetters substringToIndex:1] options:NSCaseInsensitiveSearch].location != NSNotFound)
  {
    NSString *newWord = [word substringFromIndex:[word rangeOfString:[setOfLetters substringToIndex:1] options:NSCaseInsensitiveSearch].location + 1];
    word = [word substringFromIndex:[word rangeOfString:[setOfLetters substringToIndex:1] options:NSCaseInsensitiveSearch].location];
    return lettersAreInWord(newWord, [setOfLetters substringFromIndex:2]);
  }
  else
  {
    return false;
  }
}

Nicely separated logic in this attempt and again it's fairly straightforward to follow what's going on. How did it fare in the speed test though?

Not too badly. It was quicker than the previous non-regex attempt and also a good deal quicker than the regex attempt. I was nearly happy to call it a day because it was just about quick enough for what I needed it to do such that it wasn't an annoyance, nor a real bottleneck.

I told my Dad about it though and saw that look on his face he gets when he senses there's a challenge afoot. He got me to explain exactly what I was trying to do and then he set out on writing some code to achieve the desired outcome. He spends most of his time programming in C#, C++ or straight C. He decided to write his attempt in C. Here's what he came up with.

unichar* FindLetterInSequence(unichar letterToFind, unichar *stringToSearch)
{
  unichar* foundLocation = NULL;
  while (*stringToSearch)
  {
    if (*stringToSearch == letterToFind)
    {
      foundLocation = stringToSearch;
      break;
    }
    else
    {
      ++stringToSearch;
    }
  }
  return foundLocation;
}

bool FindLettersInSequence(unichar *lettersToFind, unichar *stringToSearch)
{
  bool found = false;

  if (lettersToFind)
  {
    unichar *startPositionInStringToSearch = stringToSearch;
    found = true;
    while (*lettersToFind)
    {
      startPositionInStringToSearch = FindLetterInSequence(*lettersToFind, startPositionInStringToSearch);
      if (startPositionInStringToSearch)
      {
        ++startPositionInStringToSearch;
        ++lettersToFind;
      }
      else
      {
        found = false;
        break;
      }
    }
  }
  return found;
}

Easy to read, easy to follow, and it also happens to be really quick. At least compared to what I'd come up with using my variety of Objective-C based attempts.

I did a crude version of a benchmark for the best versions of each of the different types of solution; the fastest regex, recursive, and vanilla C solutions. I made each one loop through an array of all of the pairs of letters and count up the number of occurrences of each pair of letters in the dictionary. The results show how large the potential speed boosts can be.

  • Regular Expression: 8 minutes 54 seconds
  • Recursive: 2 minutes 7 seconds
  • Vanilla C: 13 seconds

So there you have my best solutions (and one of my Dad's!) to what is a pretty simple problem. If you can come up with a more efficient solution then please let me know!


User Accounts Using Sequelize and Passport in Node.js

by Hamilton Chapman


Setting up user accounts and authentication in Rails is incredibly easy. For most of what I've needed in the past I have been able to use a Ruby gem called Devise. If you've ever used Rails then this will almost certainly be familiar to you. It is ridiculously easy to setup. Even then, if you find yourself craving some customisation, the chances are that somebody will have already wanted to do exactly the same thing and you'll therefore be able to scoop some ideas or some code from StackOverflow.

The latest app I've been working on at Pusher has involved using Node.js, which before about 2 or 3 weeks ago, I'd never really looked into. It's been a great opportunity to learn something new, but as you'd expect, it's not all been plain sailing.

The app required that I use sqlite3 as the database (due to it being pre-installed on all Macs). As you'll know if you've ever used databases in a Node app, pretty much all of the examples you find involve using MongoDB and Mongoose. This is of course completely reasonable, but of not much use to me.

I discovered Sequelize and thought that it looked like it would prove helpful in interacting with my sqlite database through Node. Getting it setup in the first place took a little fiddling but eventually (with some help from some people in the office) I had it setup and I was able to save to and retrieve data from my sqlite database.

var Sequelize = require('sequelize');

var sequelize = new Sequelize("_databaseName_", "_username_", "_password_", {
  dialect: 'sqlite',
  storage: "/path/to/database.sqlite"
});

var User = sequelize.define('User', 
{
  username: DataTypes.STRING,
  password: DataTypes.STRING
})

User.sync();

var user = User.create({ username: "admin", password: "bolognese" });

That's all that's needed to setup the basic connection with the database, create a User model, then save an instance of a User, and then log out the user's password (probably not the best idea to save your passwords like this - take a look at crypto).

So the first part of user accounts and authentication is in place. We can now create a model and persist data. Node's answer to Devise is called Passport.js. It essentially allows you to do the same basic things as Devise that most people will want to be doing with user accounts. The only significant difference I've found is that the documentation isn't as easy to follow and the amount of questions you can find about it online is fewer than the number for Devise. To be expected though.

Integrating Sequelize with Passport is fairly simple when you've figured out how Passport works on a basic level.

var passport = require('passport');
var LocalStrategy = require('passport-local').Strategy;

// Serialize sessions
passport.serializeUser(function(user, done) {
  done(null, user.id);
});

passport.deserializeUser(function(id, done) {
  db.User.find({where: {id: id}}).success(function(user){
    done(null, user);
  }).error(function(err){
    done(err, null);
  });
});

// Use local strategy to create user account
passport.use(new LocalStrategy(
  function(username, password, done) {
    User.find({ where: { username: username }}).success(function(user) {
      if (!user) {
        done(null, false, { message: 'Unknown user' });
      } else if (password != user.password) {
        done(null, false, { message: 'Invalid password'});
      } else {
        done(null, user);
      }
    }).error(function(err){
      done(err);
    });
  }
));

The serializeUser and deserializeUser functions need to be there for Passport to be able to use sessions so that authentication works nicely in your app.

The passport.use(new LocalStrategy... block is there to define how you want your authentication to work. For example it's in this block of code where you can decide what you want the messages to be if an invalid username or password is provided.

Having got all of that setup and working together it's then easy to start hashing your passwords when you store them. Passport also allows you to easily implement other "strategies" in much the same way that you can use omniauth in conjunction with Devise.

All in all, Passport is a great module for use in Express apps and if you need to use sqlite then rest easy in the knowledge that you can use Sequelize together with Passport.


Setting up MongoDB for Heroku in a Sinatra App

by Hamilton Chapman


I've recently started a new job at Pusher. They provide a hosted API that lets you get up and running with adding realtime functionality to your web or mobile app. It's insanely easy to get setup and if you're wanting to play around with making something realtime then give it a try.

My first project required me to create a simple web app for the team to use in the office. Being most comfortable using Ruby I chose to start off with a Sinatra application.

Part of the app involved storing some data. In the past I'd only ever really used Postgres for my database needs, largely because it's widely supported (by Heroku for a start) and it's easy to grasp how it works. This time, however, I ended up using MongoDB.

Mongo is the NoSQL database. Instead of a more traditionl relational database, such as MySQL or Postgres, it is a document database. It has dynamic schemas and stores data using JSON-style documents. This is a why it's so wildly popular amongst Node.js developers who yearn for full-stack Javascript.

The first step to getting Mongo setup in your Sinatra app is to install Mongo. A simple brew install mongodb is all it takes. Then in your Sinatra app's Gemfile just add gem 'mongo' and then run bundle install (or just bundle).

Inside your app.rb or server.rb file include the Mongo module with include Mongo. Now, if you're planning on putting your app up on Heroku then you'll almost certainly end up using MongoHQ. To make your app work both locally and on Heroku you'll want to add the following:

  if ENV['MONGOHQ_URL']
    db = URI.parse(ENV['MONGOHQ_URL'])
    db_name = db.path.gsub(/^\//, '')
    db_connection = Mongo::Connection.new(db.host, db.port).db(db_name)
    db_connection.authenticate(db.user, db.password) unless (db.user.nil? || db.user.nil?)
    db_connection
    set :mongo_db, db_connection
  elsif ENV["RACK_ENV"] == 'test'
    conn = MongoClient.new("localhost", 27017)
    set :mongo_db, conn.db('DATABASE_NAME')
  else
    conn = MongoClient.new("localhost", 27017)
    set :mongo_db, conn.db('DATABASE_NAME')
  end

This bit of code has you covered if you run your app locally in development, locally in your test environment, or up on Heroku in production. Obviously if you don't want it setup for Heroku or for testing then you can remove the relevant bits of code.

With all of that setup you can then setup a collection like so:

my_collection =  mongo_db['DATABSE_NAME']['COLLECTION_NAME']

And now you're ready to start adding documents to your collection by using the following syntax:

my_collection.insert( { text: "some text", time: Time.now } )

It's that easy to get up and running with Mongo in a Sinatra app. I'll definitely be using it more in the future, both in Ruby and Node apps.


M7 vs Fitbit Flex - Getting an Accurate Step Count

by Hamilton Chapman


I'm a sucker for iPhones. Every year I tell myself that the new one won't be enough of an improvement to convince me to upgrade. Every year I end up buying the new one.

This year was no different and so I am now the owner of a Space Grey iPhone 5S.

Touch ID is impressive. Having 4G on the go is amazing. However, perhaps the feature of the new iPhone that I was most anticipating was the M7.

I'm a fan of the idea of quantified self and paersonal analytics and have played around with it in the last 6 months or so. I bought a Fitbit Flex when it was released in the UK and had dabbled with using Brett Terpstra's Slogger to track some of my digital activities.

When the iPhone 5S was announced it was the M7 that grabbed my attention. It brought with it the potential to track how I was moving around in the same way that the range of wearable tracking devices could already but without having to wear anything dedicated to tracking me. It would work with just my phone in my pocket.

David Smith's Pedometer++ was one of the first apps I installed when I eventually received my iPhone. I decided to keep on wearing my Flex and to use Pedometer++ to track the number of steps I took during a day.

Below is a graph detailing the numbers that I got from each of the devices.

The difference between the two is pretty consistent. The average number of steps tracked by the Flex was 8479 compared with the M7's 6995. That works out as 22% more steps being tracked by the Flex. 

I thought this seemed pretty high. There are of course some possible explanations. There are a few times during the day where I will not have my phone on me and so having the Flex on me all the time, other than when it's charging, would obviously add on a few steps. These moments aren't that frequent though. For example, I don't take my phone in the shower, but do keep my Flex on. Sometimes I will have my phone on my desk and quickly go off to the toilet or go and grab something from the fridge and so there are again a few steps not being counted by the M7. 

Then there are the discrepancies that will arise due to the Flex being worn on the wrist. Some things that aren't steps may be giving false readings to the Flex. This could range from brushing my teeth to shaking hands with someone. The few days where the M7's tally eclipses that of the Flex's are when the Flex will have been off my wrist, plugged in charging. 

The M7 is likely slightly underestimating my step count while the Flex is probably overestimating by a good chunk. My feeling is that the M7's numbers are more accurate (unfortunately for my health) but still fall slightly short of the real number.

I'll continue  to use both and will revisit the data in the future to see if the differences are the same. 


Hello world

by Hamilton Chapman


I'm 7 weeks into the course at Makers Academy and, as an aspiring software developer, I have decided to start this blog to write about all the things that interest me in software development.

I won't be writing here about my experiences at Makers Academy because I'm keeping a separate blog for that, which you can find here. However, I might be writing about some technical things or side-projects that are written in Ruby, the primary language that we are being taught at Makers Academy.

As well as reading my posts here you can also follow me on GitHub and on Twitter. For more details about me then you can go here.

If you come back here soon then you can look forward to posts about regex, recursion and getting close to the metal, as well as the M7 chip in the iPhone 5S and the Fitbit Flex.

Form an orderly queue.