Analyzing Android Pattern Lock

gistfile1.clj

(def pattern-graph
     [[0 1 0 1 1 1 0 1 0]
      [1 0 1 1 1 1 1 0 1]
      [0 1 0 1 1 1 0 1 0]
      [1 1 1 0 1 0 1 1 1]
      [1 1 1 1 0 1 1 1 1]
      [1 1 1 0 1 0 1 1 1]
      [0 1 0 1 1 1 0 1 0]
      [1 0 1 1 1 1 1 0 1]
      [0 1 0 1 1 1 0 1 0]])

(defn simple-paths
  "Set of simple paths (paths w/o repeating vertices) for the given graph.
   The graph must be given as a vector of adjacency seqs."
  [g]
  (letfn
      [(search-tree [v p paths]
		    (if ((set p) v)
		      paths
		      (let [p+ (cons v p)]
			(search (g v) p+ (conj paths p+)))))
       (search [vs p paths]
	       (if (empty? vs)
		 paths
		 (reduce #(search-tree %2 p %1) paths vs)))]
    (search (range 0 (count g)) [] #{})))

(defn adj-lists
  "A vector with the adjacency lists for the given adjacency matrix"
  [m]
  (vec (for [r m] (keep-indexed #(if (= 1 %2) %1) r))))

(defn print-pattern-paths-info []
  "Prints information about the possible paths on an Android pattern lock"
  (let [paths (simple-paths (adj-lists pattern-graph))
	length-counts (frequencies (map count paths))
	valid-lengths (range 4 10)]
    (doseq [l valid-lengths]
      (println (str "Paths of length " l ":")
	       (length-counts l)))
    (println "Overall number of valid paths:"
	     (reduce + (for [l valid-lengths] (length-counts l))))))