Introduction

Matthias Wandel of Research in Motion (RIM) has a programming challenge posted on his website. The challenge is to write a program that generates all the possible combinations for an N button combination lock. The twist is the multi-button possibilities as well. Read on to see how I solved the problem.

Updated on November 29, 2005: The version described below is the second published version of the code. The first program was 160 lines of code and involved a more complicated way of producing the combinations. It is, however, faster than the current version.

Constraints

Matthias presents the programming challenge while describing the position of an embedded developer. The original code traded memory usage for more complicated code. The new version reverses this decision since the amount of memory consumed is still much lower than a typical 8-bit micro-controller. The other driving constraint is to keep the source to less than 100 lines of code. The current version is at 125, so there is still some room for improvement.

Theory of Operation

The problem can be described as a simple combinatoric (k-of-n) where an increasing number of keys are drawn (starting with one and increasing to a maximum of eight.) After each choice the permutations of the set are generated. Pretty straight forward.

The insight I had for the second version of the program is to pre-compute all the button pair combinations. With only eight possible keys, there are only:

total_pairs = (total_keys * (total_keys - 1)) / 2
            = (8 * (8 - 1)) / 2
            = 28

Therefore, there are 28 pair combinations plus eight single key presses for a total of 36 possible button presses. Now, I can consider the whole single versus pair problem as a simple k-of-36 with k increasing from 1 to 8. This simplifies a lot of the code.

Pairs are stored in a single integer as the upper and lower nibbles of a byte. Single buttons are also stored in an integer, but the upper nibble is zero to differentiate them from the pairs. The display routine uses this information to determine how the output should be handled.

In order to ensure that invalid combinations are not picked a simple bitmask is used to track the keys already used in the current combination. This decision does slow down the program a bit (with my tests showing the current code calculates all the combinations and permutations for eight keys in 4.6 seconds, while the older code could do the same in 2.9 seconds.)

I’m not happy about the slowdown in the execution, but the code is easier to understand, and the change did eliminate 35 lines of source code.

Source Code

The complete source code for combos.c can be compiled into an executable by doing: cc -o combos combos.c

Conclusion

I found the process of writing this application to be fascinating. I had never developed code requiring either permutations or combinations. Even after I wrote a version that solved the problem I still felt compelled to come up with a better version. At 125 lines, this version is closer to meeting the requirements of the challenge, but it’s still not enough. I’ll have to come back to this problem again.