 (ns euler.problem61
   "https://projecteuler.net/problem=61
 
-  Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers are
-  all figurate (polygonal) numbers and are generated by the following formulae:
+  Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers
+  are all figurate (polygonal) numbers and are generated by the following
+  formulae:
 
       Triangle   P[3,n]=n(n+1)/2  --> 1, 3, 6, 10, 15, ...
       Square     P[4,n]=n2        --> 1, 4, 9, 16, 25, ...

      Heptagonal P[7,n]=n(5n−3)/2 --> 1, 7, 18, 34, 55, ...
      Octagonal  P[8,n]=n(3n−2)   --> 1, 8, 21, 40, 65, ...

  The ordered set of three 4-digit numbers: 8128, 2882, 8281, has
  three interesting properties.

      1. The set is cyclic, in that the last two digits of each number is the
      first two digits of the next number (including the last number with the
      first).
      2. Each polygonal type: triangle (P[3,127]=8128), square (P[4,91]=8281),
      and pentagonal (P[5,44]=2882), is represented by a different number in the
      set.
      3. This is the only set of 4-digit numbers with this property.

  Find the sum of the only ordered set of six cyclic 4-digit numbers for which

                          (map func (iterate inc 0)))]
       (take-while fourdigit? dw)))))

(defn search-permutation
  "Given a permutation of functions representing polygonal types, search for a
  solution, or return nil if not found."
  [poly-funcs]
  ;; We will build up candidate solutions incrementally. The starting
  ;; frontier is therefore full of one-length vectors of all the four
  ;; digit numbers for the first polygonal type of this permutation.
  (loop [frontier (vec (for [x (fourdigit-polys (first poly-funcs))] [x]))]
    (let [node (peek frontier)
          z (count node)]
      (cond
        ;; This permutation failed.
        (empty? frontier)
        nil
        ;; Success: evaluate to the sum of the values in this node.
        (and (= z 6) (all-cyclic? node))
        (reduce + node)
        ;; Append child nodes to the frontier and continue the search.
        (< z 6)
        (let [children (for [y (fourdigit-polys (nth poly-funcs z))
                             :when (cyclic? (last node) y)]
                         (conj node y))]
          (recur (into (pop frontier) (reverse children))))))))

(defn problem61 []
  ;; For every way to order the polygonal types, perform depth-first search.
  (let [polys [octagonal heptagonal hexagonal pentagonal square triangle]
        perms (comb/permutations polys)]
    ;; Return the first non-nil result.
    (first (remove nil? (map search-permutation perms)))))
