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 find_paths
  "All paths without repeating vertices in a given graph"
  [g]
  (let [paths (atom #{})]
    (letfn
	[(search_tree [v p]
		      (if (not ((set p) v))
			(let [p+ (cons v p)]
			  (swap! paths conj p+)
			  (search (g v) p+))))
	 (search [vs p]
		 (if (seq vs)
		   (doseq [v vs]
		     (search_tree v p))))]
      (search (range 0 (count g)) []))
    @paths))

(defn am_to_al
  "A vector of adjacency lists for a given adjacency matrix"
  [m]
  ((comp vec map)
   (fn [r] (keep-indexed #(if (== 1 %2) %1) r))
   m))

(defn print_pattern_paths_info []
  "Prints path count information for Android Pattern Lock"
  (let [paths (find_paths (am_to_al 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 + (map #(length_counts %) valid_lengths)))))