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 []
  (->> (read-lines "keylog.txt")                             
       (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.