Programming Questions

  • Newest
  • Popular Tags
  • Ask A Question
  • Bracket Combinations in Ruby - Tests failing
    I have submitted the following for the hard challenge Bracket Combinations, and it is failing a few tests for reasons I do not understand - because the output is correct. I tested against another user's code (who got all tests right), for example, when the input is 5, output should be 42 - my code does just that, but still fails this test. I think it has to do with the efficiency. It takes about 20 seconds for it to do it when num == 5. Can coderbyte not handle O(n^2) for these things?
    def BracketCombinations(num)
      return 0 if num == 0
      return 1 if num == 1
      o = "("
      c = ")"
      arr = []
      num.times do
          arr << o
          arr << c
      end
      
      # Now do permutations of all of them, then run them through an algorithm to see if it is valid.
      perms = arr.permutation.to_a.uniq!
      puts perms.count
      perms.keep_if{|x| valid?(x)}
      perms.map!(&:join).count
    end
    
    def valid?(arr)
      if arr.last == "(" || arr[0] == ")"
        return false
      end
    	
      i = 0
      arr.each do |parenthesis|
        if parenthesis == "("
          i+=1
        else
          i-=1
        end
        if i < 0
          return false
        end
      end
      return true
    end
    willashley23 posted this question on 5/24/16 | bracket, combinations, ruby
    Answers
    Log in to write an answer.