First clear solution for Remove Brackets by yoichi - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

First solution in Clear category for Remove Brackets by yoichi

import itertools


def is_balanced(a):
    while True:
        if '()' in a:
            a = a.replace('()', '')
        elif '[]' in a:
            a = a.replace('[]', '')
        elif '{}' in a:
            a = a.replace('{}', '')
        else:
            return not a


def remove_brackets(a):
    for i in range(len(a)+1):
        for c in itertools.combinations(range(len(a)), i):
            s = ''.join(v for j, v in enumerate(a) if j not in c)
            if is_balanced(s):
                return s

Feb. 19, 2019

Comments:

quarkov on Feb. 20, 2019, 1:51 p.m.
Although this solution looks neat and concise it's very time and memory greedy, especially in the worst-case scenario.

przemyslaw.daniel on Feb. 21, 2019, 6:35 p.m.
This is the right and beautiful way to solve it. Just lunch code below to see the difference. Maximum number of steps is 2^k but in this implementation it is possible to finish earlier without generating all of them <pre class='brush: python'>def remove_brackets_yoichi(a): import itertools def is_balanced(a): while True: if '()' in a: a = a.replace('()', '') elif '[]' in a: a = a.replace('[]', '') elif '{}' in a: a = a.replace('{}', '') else: return not a for i in range(len(a)+1): for c in itertools.combinations(range(len(a)), i): s = ''.join(v for j, v in enumerate(a) if j not in c) if is_balanced(s): return s def remove_brackets_quarkov(brackets): stack, matching = [], [] counter = {40: 0, 41: 0, 91: 0, 93: 0, 123: 0, 125: 0} for bracket in brackets: counter[ord(bracket)] += 1 for pos, bracket in enumerate(brackets): if bracket == '(' and counter[(ord(bracket)+1)] >= stack.count(bracket) + 1: stack.extend([bracket, pos]) elif bracket in '[{' and counter[(ord(bracket)+2)] >= stack.count(bracket) + 1: stack.extend([bracket, pos]) elif bracket in ")]}" and stack and abs(ord(bracket) - ord(stack[-2])) <= 2: matching.extend([(pos, bracket), (stack.pop(), stack.pop())]) return "".join([bracket for pos, bracket in sorted(matching)]) from random import randint for _ in range(100): text = ''.join('(){}[]'[randint(0, 5)] for _ in range(10)) a, b = remove_brackets_yoichi(text), remove_brackets_quarkov(text) assert a == b, "guru meditation: %s >>> %s vs %s <<<" % (text, a, b) </pre>

quarkov on Feb. 21, 2019, 6:59 p.m.
Well I can't answer with numbers, just need some time to figure it out. I may preliminarily agree that in case of len(a) == 5 my solution should work slower, but what about, let's say, len(a) == 20? Btw any links related to this algorithm would be appreciated because algorithms aren't my strong side and I'd like to know more about this one.

quarkov on Feb. 21, 2019, 7:18 p.m.
Yeah, I see, my solution works improper. I will work with it. Could you say how this algorithm is called?

przemyslaw.daniel on Feb. 21, 2019, 9:29 p.m.
This is a simple brute force which tries to generate all possible substrings of the string. For example, for ABC you have: ABC, AB, BC, AC, A, B, C. For every string it checks whether this is correct. Because it starts from the longest and going to the shortest it can be stopped when the first one is found. Problem is it has exponential complexity and for 20 charters we need 2^20 steps in worst case scenario (Sum(Binomial(k, n) for k in range(n+1)) == 2**n)

syed9ine on Dec. 5, 2022, 12:48 a.m.
why len(a) +1 and not just len(a)?

Strings Theory

0 %

You ClassRoom Demo is Ready With the new tool CheckiO ClassRoom, you will be able to analyze your students' progress, have your own leaderboard, change missions order on the map, and so on.