adventofcode

Happy Advent 2020! Please put answers in the pinned threads or create one if it does not exist yet. | https://github.com/adventofcode-clojurians/adventofcode-clojurians | Join the private leaderboard with code 217019-4a55b8eb
2021-06-28T15:42:44.006Z

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?

tws 2021-06-28T16:47:57.009400Z

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.

👍 2
tws 2021-06-28T16:50:38.010400Z

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.

yubrshen 2021-06-28T17:22:24.015900Z

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.

yubrshen 2021-06-28T17:25:57.019700Z

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

nbardiuk 2021-06-28T17:29:38.020200Z

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

nbardiuk 2021-06-28T17:30:12.020300Z

(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)

nbardiuk 2021-06-28T17:35:06.021200Z

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

nbardiuk 2021-06-28T17:40:09.021500Z

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

tws 2021-06-28T17:42:29.021700Z

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.

nbardiuk 2021-06-28T17:44:54.021900Z

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

yubrshen 2021-06-28T19:10:06.022200Z

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