Calculate how many permutations there are for the Android pattern lock-screen

android_lockscreen_permutations.rb

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