Skip to content

Instantly share code, notes, and snippets.

@raek
Forked from Netpilgrim/gist:1165353
Created August 23, 2011 15:16
Show Gist options
  • Save raek/1165399 to your computer and use it in GitHub Desktop.
Save raek/1165399 to your computer and use it in GitHub Desktop.
Analyzing Android Pattern Lock
(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)))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment