Clojurians Log v2

I had a tech test for a job application where the problem was for a given n pairs of brackets, calculate the number of possible valid (open/close) combinations. e.g. • 2 pairs => ()(), (()) answer = 2 • 3 pairs => ()()(), ()(()), (())(), ((())), (()()) answer = 5 I started with a brute-force solution: 1. Generate all possible permutations of the brackets. 2. Remove duplicate permutations. 3. For each permutation, check if it is valid. Obviously, the above solution is poor. I’d like to be better and learn. So, how would you approach this problem?

Look at your examples, moving from 2->3. There’s a pattern there. You can extrapolate this. I’m also confident there’s an O(1) formula that spits out the answer. If you want more hints lmk.

lots of interview questions work this way. Figure out an approach that goes from level N to level N+1 and you’re mostly there.

For induction from n to n+1, consider the cases of 1. () and. n-1 case [a pair of closed brackets, followed by the rest of n-1 brackets closed in whatever fashion.] 2. n-1 case and () [reverse of 1. above] 3. (n-1 case) [a pair brackets enclosing the rest of n-1 brackets closed in whatever fashion.] The above 1. and 2 are symmetry, and need to minus the duplicates.

So f(n) = 3*f(n-1)-1

for brute-force solution I would go with trees - balanced brackets represent some sort of a tree. Case n+1 takes all previous trees and for each node in those trees tries to add new node to the left, to the right and a child

(require '[clojure.zip :as zip])

(defn locations [z]
  (when-not (zip/end? z)
    (lazy-seq (cons z (locations (zip/next z))))))

(defn add-node [tree]
  (let [ls (->> tree zip/vector-zip locations)]
    (->> (concat
          (map #(zip/insert-child % []) ls)
          (map #(zip/insert-left % []) (rest ls))
          (map #(zip/insert-right % []) (rest ls)))
         (map zip/root)
         set)))

(defn trees [n]
  (case n
    0 []
    1 (add-node [])
    (->> (trees (dec n))
         (mapcat add-node)
         set)))

(defn parens [n]
  (count (trees n)))

(->> (range 10)
     (map parens))
; => (0 1 2 5 14 42 132 429 1430 4862)

Looks like closed formula is a https://en.wikipedia.org/wiki/Catalan_number

I would not be able to come up with the formula during interview

no, but I think you’d get credit saying you know there’s likely an O(1) formula and you’d use OEIS to get it.

Good point, the intuition that sequence should have a formula would be enough for me if I was giving such task.

The way of thinking in recursion, or mathematically, in deduction can give us a long way forward sometimes.