Given some assortment of brackets, you must find the largest substring that is a valid matching bracket pattern

  • A bracket match is an opening and closing version of the same kind of bracket beside each other ()
  • If a bracket matches then outer brackets can also match (())
  • The valid brackets are ()[]{}

For example for the input {([])()[(])}()] the answer would be ([])() as that is the largest substring that has all matches


You must accept the input as a command line argument (entered when your app is ran) and print out the result

(It will be called like node main.js [(]() or however else to run apps in your language)

You can use the solution tester in this post to test you followed the correct format https://programming.dev/post/1805174

Any programming language may be used. 3 points will be given if you pass all the test cases with 1 bonus point going to whoevers performs the quickest and 1 for whoever can get the least amount of characters

To submit put the code and the language you used below


People who completed the challenge:

submissions open for another day (since the last time I edited the post)

  • Quasari@programming.dev
    link
    fedilink
    English
    arrow-up
    2
    ·
    edit-2
    1 year ago

    I found this one easier than the medium as well. Maybe because I actually know a strategy for this one. Anywho, solution is in JavaScript. It’s super ugly as I went for lowest character count, so no declarations, single char variable names, no semicolons, etc…

    Basically use a anchor-runner pointer strategy to find a correct substring, I use a stack based solution for checking if the substring is correct. When the stack is empty, the substring is good, thus I record the start of it and its length. If, I get another good point, I just record the highest. If I hit a point where its no longer good, I jump the start to the end of the most recent good substring. Pretty fun.

    Formatting screwed mine up, so heres a pastbin

  • shape-warrior-t@kbin.social
    link
    fedilink
    arrow-up
    1
    ·
    1 year ago

    I actually found this challenge to be easier than this week’s medium challenge. (Watch me say that and get this wrong while also getting the medium one correct…) Here’s an O(n) solution:

    bracket_pairs = {('(', ')'), ('[', ']'), ('{', '}')}
    
    def main(brackets: str) -> str:
        n = len(brackets)
        has_match_at = {i: False for i in range(-1, n + 1)}
        acc = []
        for i, bracket in enumerate(brackets):
            acc.append((i, bracket))
            if len(acc) >= 2:
                opening_idx, opening = acc[-2]
                closing_idx, closing = acc[-1]
                if (opening, closing) in bracket_pairs:
                    acc.pop(), acc.pop()
                    has_match_at[opening_idx] = has_match_at[closing_idx] = True
        longest_start, longest_end = 0, 0
        most_recent_start = None
        for left_idx, right_idx in zip(range(-1, n), range(0, n + 1)):
            has_match_left = has_match_at[left_idx]
            has_match_right = has_match_at[right_idx]
            if (has_match_left, has_match_right) == (False, True):
                most_recent_start = right_idx
            if (has_match_left, has_match_right) == (True, False):
                most_recent_end = right_idx
                if most_recent_end - most_recent_start > longest_end - longest_start:
                    longest_start, longest_end = most_recent_start, most_recent_end
        return brackets[longest_start:longest_end]
    
    if __name__ == '__main__':
        from argparse import ArgumentParser
        parser = ArgumentParser()
        parser.add_argument('brackets')
        print(main(parser.parse_args().brackets))
    
    

    We start off by doing the same thing as this week’s easy challenge, except we keep track of the indices of all of the matched brackets that we remove (opening or closing). We then identify the longest stretch of consecutive removed-bracket indices, and use that information to slice into the input to get the output.

    For ease of implementation of the second part, I modelled the removed-bracket indices with a dict simulating a list indexed by [-1 … n + 1), with the values indicating whether the index corresponds to a matched bracket. The extra elements on both ends are always set to False. For example, {([])()[(])}()] -> FFTTTTTTFFFFFTTFF, and ([{}]) -> FTTTTTTF. To identify stretches of consecutive indices, we can simply watch for when the value switches from False to True (start of a stretch), and from True to False (end of a stretch). We do that by pairwise-looping through the dict-list, looking for ‘FT’ and ‘TF’.

  • brie@beehaw.org
    link
    fedilink
    English
    arrow-up
    1
    ·
    1 year ago

    C: gcc -O2 hard.c

    This is very poorly written, but does seem to work.

    The stack keeps track of the start of a match, and the character that would complete the match. In cases where a match just ended, the start is preserved (because two adjacent matches are effectively one), but the required matching character is changed to that of the new opening match.

    #include 
    #include 
    #include 
    #include 
    
    int main(int argc, char **argv)
    {
    	char map[256] = { 0 };
    	struct match {
    		char const *start;
    		char requirement;
    	};
    	char const *match_start;
    	ptrdiff_t length = 0;
    	char const *p;
    	struct match *stack, *top;
    	char opener;
    
    	if (argc != 2) {
    		fputs("Improper invocation\n", stderr);
    		exit(EXIT_FAILURE);
    	}
    
    	/* Initialise lookup table */
    	map[')'] = '(';
    	map[']'] = '[';
    	map['}'] = '{';
    
    	if (!(stack = calloc(sizeof(*stack), strlen(argv[1]) + 1))) {
    		fputs("Allocation failure\n", stderr);
    		exit(EXIT_FAILURE);
    	}
    	/* Note: stack[0].requirement must be 0. This is satisfied by calloc. */
    	top = stack;
    
    	match_start = argv[1];
    	for (p = argv[1]; *p; p++) {
    		/* Are we a closing brace? */
    		if ((opener = map[(size_t)*p])) { /* Yes */
    			if (top->requirement == opener) {
    				if (p - top->start >= length) {
    					length = p - top->start + 1;
    					match_start = top->start;
    				}
    				top[1].start = 0;
    				top--;
    			} else {
    				top[1].start = 0;
    				/* Set start to nullptr to invalidate the matches */
    				while (top > stack) {
    					top--->start = 0;
    				}
    			}
    		} else { /* No */
    			(++top)->requirement = *p;
    			/* If we are right outside another match, we can use their pointer instead */
    			if (!top->start) {
    				top->start = p;
    			}
    		}
    	}
    
    	printf("%.*s\n", (int)length, match_start);
    
    	free(stack);
    }
    
  • lavafroth@programming.dev
    link
    fedilink
    arrow-up
    1
    ·
    1 year ago

    Rust solution:

    use std::cmp::min;
    use std::ops::Range;
    
    fn completer(bracket: char) -> char {
        match bracket {
            ')' => '(',
            '}' => '{',
            ']' => '[',
            _ => unreachable!(),
        }
    }
    
    pub struct Char {
        index: usize,
        value: char,
    }
    
    fn main() {
        let input: String = std::env::args().nth(1).unwrap();
        let mut longest = Range::default();
        {
            let mut current = Range::default();
            let mut stack: Vec = Vec::with_capacity(input.len() << 1);
            let mut streak = false;
            for (i, c) in input.chars().enumerate() {
                match c {
                    ']' | '}' | ')' => {
                        let matched = stack
                            .last()
                            .map(|other| completer(c) == other.value)
                            .unwrap_or_default();
                        if matched {
                            current.start = if streak {
                                min(current.start, stack.pop().unwrap().index)
                            } else {
                                stack.pop().unwrap().index
                            };
                            current.end = i;
                            streak = true;
                        } else {
                            stack.clear();
                            if longest.len() < current.len() {
                                longest = current;
                            }
                            current = Range {
                                start: i + 1,
                                end: i + 1,
                            };
                            streak = false;
                        }
                    }
                    '[' | '{' | '(' => {
                        stack.push(Char { index: i, value: c });
                    }
                    _ => {}
                };
            }
    
            if streak {
                longest = current;
            }
        }
    
        if longest.start != longest.end {
            longest.end += 1;
        }
        println!("{}", &input[longest]);
    }
    

    Also available at: https://pastebin.com/EJsLYPqQ

  • nieceandtows@programming.dev
    link
    fedilink
    arrow-up
    1
    ·
    edit-2
    1 year ago

    Please feel free to suggest changes to make the code more efficient.

    EDIT: for some reason, < is not showing up properly inside a code block. Kindly replace it with the right symbol when you test.

    Python:

    import sys
    
    input_string = sys.argv[1]
    
    matches = {
        "}": "{",
        "]": "[",
        ")": "("
    }
    
    bracket_matches_strict = []
    
    def get_matching_substring_strict(string):
        substring = ''
        index_start = -1
        index_end = -1
        bracket_counts = {
            "{": 0,
            "[": 0,
            "(": 0
        }
        for index, letter in enumerate(string):
            if letter in matches.values():
                if index_start == -1:
                    index_start = index
                substring += letter
                bracket_counts[letter] += 1
            if letter in matches.keys():
                if not substring:
                    break
                if substring[-1] == matches[letter]:
                    substring = substring[:-1]
                    bracket_counts[matches[letter]] -= 1
                    if not [cnt for cnt in bracket_counts.values() if cnt]:
                        index_end = index
                    if [cnt for cnt in bracket_counts.values() if cnt &lt; 0]:
                        break
                else:
                    break
    
        if index_start != -1 and index_end != -1:
            matching_substring = string[index_start:index_end + 1]
            return len(matching_substring), matching_substring
    
    for i in range(len(input_string)):
        bracket_substring_strict = get_matching_substring_strict(input_string[i:])
        if bracket_substring_strict:
            bracket_matches_strict.append(bracket_substring_strict)
    
    print(sorted(bracket_matches_strict)[-1][1])