Skip to content

Instantly share code, notes, and snippets.

@msharp
Created October 9, 2012 03:16
Show Gist options
  • Save msharp/3856367 to your computer and use it in GitHub Desktop.
Save msharp/3856367 to your computer and use it in GitHub Desktop.
Calculate how many permutations there are for the Android pattern lock-screen
NODES = {
1 => [2,4,5],
2 => [1,3,4,5,6],
3 => [2,5,6],
4 => [1,2,5,7,8],
5 => [1,2,3,4,6,7,8,9],
6 => [2,3,5,8,9],
7 => [4,5,8],
8 => [4,5,6,7,9],
9 => [5,6,8]
}
STEPS = 3
def path_next(paths)
new_paths = []
paths.each do |p|
available_next_steps = NODES[p.last] - p
available_next_steps.each do |s|
new_steps = p + [s]
new_paths << new_steps
end
end
new_paths
end
paths = []
NODES.each do |k,v|
path = [[k]]
STEPS.times do
path = path_next(path)
end
paths = paths + path.reject{|a|a.size != 4}
end
puts paths.size # 496
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment