This morning, my girlfriend asked me for her phone when she woke up. She had the cell phone on the side of the bed, and when she asked for it, I clicked the screen on and saw the Android lock screen. I jokingly asked her what her combination was, and when she refused, I persisted, and then began to think about all the possibilities of the password – I told her that I’m sure the number was in billions, but I was way off. Either way, we argued about it, and I told her it was not about me knowing her password as much as it was about a legitimately interesting math question. I then went into my living room to start my day of work. I have been working from home – my life has become profoundly sedentary.
Anyways, I should have been doing work, but the question kept bothering me. I began to write up the program to solve the question, but got scared when I started writing a two-dimensional array, something I hadn’t done since college – it felt wrong, like I was reverting back to my first days of programming and getting very scared about the whole thing. I was worried that my analogizing of this particular question of permutations to early programming days would throw me off, and my approach was all wrong (the two-dimensional array, which really is totally appropriate, was keyboard=[[1,2,3],[4,5,6],[7,8,9]]).
After about a half hour of banging away, I realized I was going to get in work trouble, so I had to put it aside. But it kept bothering me. I pinged my best programming friend, someone I learned to program with and have programmed anything meaningful with since day one, Ian Pearce. I told him about this question, and basically outlined the problem. He agreed that it was interesting, and started thinking about it too. Basically, the algorithm we thought up was this:
- Start with a random number on the keyboard
- From this random number, jump to another that is allowed, granted you aren’t running over the allowed length of a password (which was just modulated every time we ran the loop from 1→9)
- Store the result into an array.
This was admittedly shamefully shitty. It was bad programming. But, it was the first thing I came up with. I wrote it out once, and I didn’t get it working right, so I started over and wrote it again. It looked like this:
def positions(number,path)
case number
when 1
base_paths = [2,4,5,6,8]-path
base_paths = allowed(7,4,base_paths,path)
base_paths = allowed(3,2,base_paths,path)
base_paths = allowed(9,5,base_paths,path)
when 2
base_paths = [1,3,4,5,6,7,9]-path
base_paths = allowed(8,5,base_paths,path)
when 3
base_paths = [2,4,5,6,8]-path
base_paths = allowed(7,5,base_paths,path)
base_paths = allowed(1,2,base_paths,path)
base_paths = allowed(9,6,base_paths,path)
when 4
base_paths = [1,2,3,5,7,8,9]-path
base_paths = allowed(6,5,base_paths,path)
when 5
base_paths = [1,2,3,4,6,7,8,9]-path
when 6
base_paths = [1,2,3,5,7,8,9]-path
base_paths = allowed(4,5,base_paths,path)
when 7
base_paths = [2,4,5,6,8]-path
base_paths = allowed(1,4,base_paths,path)
base_paths = allowed(9,8,base_paths,path)
base_paths = allowed(3,5,base_paths,path)
when 8
base_paths = [1,3,4,5,6,7,9]-path
base_paths = allowed(2,5,base_paths,path)
when 9
base_paths = [2,4,5,6,8]-path
base_paths = allowed(1,5,base_paths,path)
base_paths = allowed(3,6,base_paths,path)
base_paths = allowed(7,8,base_paths,path)
end
end
def allowed(jump_to,interfering_number,base_paths,path)
base_paths << jump_to if path.include?(interfering_number) && !path.include?(jump_to)
return base_paths
end
attempted_paths = []
number = rand(9)+1
length = 1
while attempted_paths.length!=389112
this_path=[number]
possibles = positions(number,this_path)
while !possibles.empty? && this_path.length<length
this_path<<possibles[rand(possibles.length)]
number = this_path.last
possibles = positions(number,this_path)
end
attempted_paths << this_path.join.to_i if !attempted_paths.include?(this_path.join.to_i)
length+=1
length=1 if length == 10
puts attempted_paths.length if Time.now.strftime("%S")=="00"
end
attempted_paths.select{|x| x.to_s.size==4}.uniq.sort
At this point, I had begun consulting the internet – I could tell that as time wore on, the possibility of adding a new number would not really happen. That’s where I got that magic “389112”, by the way. I was floundering, and messing it up. I was relying on an admittedly gorgeous and thoughtful posting on Stack Overflow for this magic number, and was putting so much reliance on them that I even dusted off my Python interpreter and tried the seeming winner, Omnifarous’s, code.
As time wore on, and I thought that perhaps my program was slowing to a point where it would never find the answer, I even questioned if the problem of calculating the listing of lock combinations (not just determining how many there would be, I wanted a list of them, I love data and I wanted to see it) was actually NP-Complete. If you think about it, it almost could be – really, the lock combo is a network of nodes connected by gestured edges. Hell, if you look at the wiki on Hamiltonian Paths, the graphic looks eerily similar to the screen. I thought that, with no knowledge of all the combinations, it couldn’t be done. Also, wouldn’t it be bad ass to have an NP-Complete process surrounding your locking mechanism?
BUT. What if we had a listing of every combination of possible groupings of numbers? This huge listing would include all the actual, valid groupings, and would likely have a whole bunch of bad ones interspersed. I was worried that this listing would be gigantic. It actually wasn’t so bad. Also, I learned of the wonderfully useful Array method permutation(), which is totally useful. So, I set out to calculate all of the possible combinations. Below is the code for that process:
list = [1,2,3,4,5,6,7,8,9]
full_opts = []
wrong_opts = []
1.upto(9) do |x|
puts "Calculating for #{x} space"
list.permutation(x) do |n|
full_opts<<n.to_s.to_i
end
puts "Calculated."
end
So, what you get is a bigass array (986,409 large) in a relatively small amount of time (<2min) of every possible permutation, without replacement, of the numbers 1-9 of lengths 1-9 (people were saying online that these phones can’t do combos less than four. From what I can tell from my girlfriend’s phone, those people are spooks and charlatans). Then, you can basically just reverse that original code to ask “is the next step in this given path a valid path?”, and once you know that some next step is not valid, you can just reject the whole path and move on. Much simpler, because really, you’re munching through a finite set of objects (a million in this case), and just testing some basic math on each integer within. So, that leaves us with code like this:
#smaller, more DRY version of that original
#function, does the same shit though.
def positions(number,path,base_paths=nil,special_paths=[])
case number
when 1
base_paths,special_paths = [2,4,5,6,8],[[3,2],[7,4],[9,5]]
when 2
base_paths,special_paths = [1,3,4,5,6,7,9],[[8,5]]
when 3
base_paths,special_paths = [2,4,5,6,8],[[1,2],[7,5],[9,6]]
when 4
base_paths,special_paths = [1,2,3,5,7,8,9],[[6,5]]
when 5
base_paths = [1,2,3,4,6,7,8,9]
when 6
base_paths,special_paths = [1,2,3,5,7,8,9],[[4,5]]
when 7
base_paths,special_paths = [2,4,5,6,8],[[1,4],[3,5],[9,8]]
when 8
base_paths,special_paths = [1,3,4,5,6,7,9],[[2,5]]
when 9
base_paths,special_paths = [2,4,5,6,8],[[1,5],[3,6],[7,8]]
end
return base_paths-path+allowed(special_paths,base_paths,path)
end
#this just returns the array of special hops that are capable.
#see below for a link on why that's important.
def allowed(special_paths,base_paths,path)
opts = []
special_paths.each do |jump_to,interfering_number|
opts<<jump_to if path.include?(interfering_number) && !path.include?(jump_to)
end
return opts
end
#no ugly code when a fun extension can do the work instead.
class Fixnum
def split(char="")
return to_s.split(char)
end
def split_to_i(char="")
return split(char).collect{|x|x.to_i}
end
end
#The actual Algorithm
full_opts.each do |opt|
opt_array = opt.split_to_i
opt_array.each do |number|
if number != opt_array.last
next_number=opt_array[opt_array.index(number)+1]
cur_path=opt_array[0..opt_array.index(number)]
if !positions(number,cur_path).include?(next_number)
wrong_opts<<opt
break
end
end
end
end
right_opts = full_opts-wrong_opts
Basically, the algorithm just iterates through that bigass listing, splits each listing into an array of integers (so that we don’t have an ugly bigass 2-dimensional array for the fullopts or rightopts later on), and then, for each number, asks if the next number is a valid step given the history of this path (which is just the array up to that point). Obviously, we could reverse the process and just generate the right opts, but it would mean that we would have to iterate through every single step in every path, which would be unnecessary in most cases.
This all gives you the following result, which concurs with previous statements on that Cédric Beust’s page on this:
9-space: 140,704 combinations
8-space: 140,704 combinations
7-space: 72,912 combinations
6-space: 26,016 combinations
5-space: 7,152 combinations
4-space: 1,624 combinations
3-space: 320 combinations
2-space: 56 combinations
1-space: 9 combinations
Attached here is the listing of every single possible lock combination.
Props go to Cédric Beust which outlines all of the various rules that the algorithm has to comply with in order to get the correct listings. I wouldn’t have guessed that “knight-style” moves were possible, which, when I assured my girlfriend that they were, began another argument. At least that one didn’t take 8 hours to reach a definitive conclusion.