Listing of Android lock combinations

(Friday, January 21, 2011, at 03:14 PM)

This morning, I woke up to a small argument with my girlfriend. 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 (she keeps a tight lid on her electronics). I 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. So, I argued some more, and then when I ran out of combos, I finally handed over the device. 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:

1. Start with a random number on the keyboard
2. 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)
3. 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 full_opts or right_opts 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.

Back