# Project Euler Problem 79

Problem 79 asks us to crack a primitive security ‘feature’ asked by some (hypothetical) banks. Given 50 successful login attempts using an ordered subset of the digits from a passcode, we need to find what the original passcode was.

The algorithm to do this turns out to be pretty simple:

1. Assume that there are no repeated digits. This makes the problem much easier.
2. Since the given numbers [a,b,c] are ordered, each login attempt tells us that a is before b, a is before c, and b is before c.
3. Collect these orderings into sets – one set for each number.
4. Sort the digits so that the ordered dependencies are all satisfied.

In Clojure, that looks like this:

(use '[clojure.contrib.duck-streams :only (read-lines)])

(defn conj-in
"Conjs v into a set under key k of map m."
[m k v]
(assoc m k (conj (or (m k) #{}) v)))

(defn euler-79 []
(map (fn [l] (map #(Character/getNumericValue %) l)))
(reduce (fn [m [a b c]] (-> (conj-in m a b)
(conj-in a c)
(conj-in b c))) {})
(sort-by #(count (val %)))
(reduce (fn [l [k vs]]
(apply concat [k] (apply disj vs l) [l])) nil)))

(time (euler-79)) ;; "Elapsed time: 2.719621 msecs"


You may notice that this algorithm slightly cheats because of the strong assumption #1 and the fact that the data uniquely determines the possible password. Given less perfect data, several combinations of letters might be possible for which that this algorithm cannot account. Specifically,  (sort-by #(count (val %))) will not yield the correct answer except in these specific circumstances.

I wonder if a later problem will ask us to compute the number of possible passwords given a smaller, incomplete sample of successful logins? That might be interesting follow-up problem to this one.