this post was submitted on 20 Aug 2023
3 points (100.0% liked)

Programming Challenges

235 readers
1 users here now

Welcome to the programming.dev challenge community!

Three challenges will be posted every week to complete

Easy challenges will give 1 point, medium will give 2, and hard will give 3. If you have the fastest time or use the least amount of characters you will get a bonus point (in ties everyone gets the bonus point)

Exact duplicate solutions are not allowed and will not give you any points. Submissions on a challenge will be open for a week.

A leaderboard will be posted every month showing the top people for that month

founded 1 year ago
MODERATORS
Ategon@programming.dev
3
[Hard] Longest Valid Bracket Pattern (programming.dev)
submitted 1 year ago* (last edited 1 year ago) by Ategon@programming.dev to c/challenges@programming.dev
15 comments fedilink hide all child comments
 

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)

you are viewing a single comment's thread
view the rest of the comments
[–] lavafroth@programming.dev 0 points 1 year ago (1 children)

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

[–] Ategon@programming.dev 1 points 1 year ago (1 children)

4/6 test cases passed

[–] lavafroth@programming.dev 1 points 1 year ago

lol forgot the cases where there might be multiple nested braces!