Currently I'm in hunting for jobs and one of the companies I have interviewed with sent me a
skills test to complete.
The test was to list all the possible entries of a combination lock with no-repeating
Basically the lock would look like something like this:
since every button can be pressed once.
The problem I was given is right here: LockCo.
I thought of different methods to solve the problem:
1)De Bruijn Sequence which lists all
possible cycles in
graph similar to a Hamiltonian Path.
My idea was
to parse the output string from the De Bruijn algorithm.
2)Write an algorithm that will throw all the numbers in a list and just loop through them and take out the
used ones out of the list. This obviously required some work and I wasn't sure how I, actually wanted it to
3)Generate random numbers for sometime and keep adding the unique ones to a list (horrible idea for
And finally I realized the best approach is to actually count up from smallest possible combination. Then
repeat for set of digits in the combinations.
Below is an example explaining this..
Let's say we're trying to find all combinations of numbers 1,2,3.
We start from the smallest number (remember non-repeating digits):
Then we add 1 to this number (in number base 3 of course!). Our number becomes
131 (# 1 is listed twice so this number is useless but that's ok). We add 1 again and it becomes
132 (Now we got it!)
And we keep adding one to generate all the possible combinations and just don't print the ones
who have repeating digits in them.
Here is the full solution for you to test it out ;)
Combo Lock Solution
Now let's look at some code:
And that is all. Can similar code be used for a dictionary attack? Perhaps.
I hope you found this interesting.
Stay Smart friends,