phone_unlock_patterns.rb

# This script calculates all possible paths through mobile phone unlock codes.
# Results are sorted in a depth first manner. There are exactly 389,498
# valid paths. However, Android only allows paths with length > 3, resulting
# in only 389,112 paths[1].
#
# [1]: Dissecting pattern unlock: The effect of pattern strength meter on
#      pattern selection; Chen Sun and Yang Wang and Jun Zheng; J. Inf. Secur.
#      Appl.; Volume 19; 2014
#
module UnlockPatterns

  # Reachable indices in dense representation. The indices of the nodes are:
  # 0  1  2
  # 3  4  5
  # 6  7  8
  EDGES = {
    0 => [1, 3, 4, 5, 7],
    1 => [0, 2, 3, 4, 5, 6, 8],
    2 => [1, 3, 4, 5, 7],
    3 => [0, 1, 2, 4, 6, 7, 8],
    4 => [0, 1, 2, 3, 5, 6, 7, 8],
    5 => [0, 1, 2, 4, 6, 7, 8],
    6 => [1, 3, 4, 5, 7],
    7 => [0, 2, 3, 4, 5, 6, 8],
    8 => [1, 3, 4, 5, 7]
  }

  # After some indices have been visited, allow additional edges
  # E.g. path [1, 0, 2], where index 1 gets permeable
  ADDITIONAL_EDGES = {
    1 => [[0, 2]],
    3 => [[0, 6]],
    4 => [[0, 8], [2, 6], [3, 5], [1, 7]],
    5 => [[2, 8]],
    7 => [[6, 8]]
  }

  def self.paths(min_length: 3)

    # Hold the result, which looks like:
    # [[0], [0, 1], [0, 3], ..., [8, 7, 6, 5, 4, 3, 2, 1, 0]]
    @visited_paths = [[]]

    # Run algorithm with all possible starting indices
    (0..8).each { |i| visit_path([i]) }

    # Filter results by path lengths (for Anroid min length is 3) and
    # return result paths
    @visited_paths.select { |p| p.size >= min_length }
  end

  private

    # Recursively visits all possible paths depth first
    # Results are appended to the visisted_paths list
    def self.visit_path(current_path)
      @visited_paths << current_path

      # Compute which target indices are in reach
      possible_target_indices = (

        # All indices from the base graph are always in reach
        EDGES[current_path.last] +

        # Indices get permeable after they got visited, therefore we
        # have to compute which additional edges are reachable
        ADDITIONAL_EDGES.select do |key, _|
          current_path.include?(key)

        # Filter indices which are reachable from the current index
        end.values.flatten(1).select do |edge|
          edge.include?(current_path.last)
        end

      # Format possible target indices and subtract all indices of
      # current path. We do not want to visit already visisted indices
      ).flatten.uniq.sort - current_path

      # Use recursion to iterate all possible target indices
      possible_target_indices.each { |i| visit_path(current_path + [i]) }
    end
end

Use it like that:

# Run algorithm and print result
paths = UnlockPatterns.paths(min_length: 3)
paths.each { |p| puts p.inspect }

Or use it with ruby2d:

Screen.Recording.2022-01-10.at.06.32.55.mov

# Use ruby2d library for drawing
require "ruby2d"

# Set the window size
set width: 400, height: 400

# Keep tick count and path index
tick = 0
path_index = 0

Ruby2D::Window::update do

  # Refresh window every 0.5s
  tick += 1
  next if tick % 30 > 0

  # Clear window
  clear

  # Draw indices
  3.times do |y|
    3.times do |x|
      Circle.new(
        x: 100 + x * 100,
        y: 100 + y * 100,
        radius: 20,
        color: "#4444ff"
      )
    end
  end

  # Draw lines by iterating two indices from the path at the time
  paths[path_index].each_cons(2) do |from, to|

    # Coordinates for from-index
    x1 = 100 + (from % 3) * 100
    y1 = 100 + (from / 3) * 100

    # Coordinates for to-index
    x2 = 100 + (to % 3) * 100
    y2 = 100 + (to / 3) * 100

    # Draw line from-to
    Line.new(
      x1: x1, y1: y1,
      x2: x2, y2: y2,
      width: 5,
      color: "lime"
    )
  end

  # Increase counter to draw next path next time
  path_index += 1
end

# Render window
Ruby2D::Window::show