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:
- @SleveMcDichael@programming.dev -
6.64s
-1203 chars
(rust) - @shape-warrior-t@kbin.social -
0.148s
-1251 chars
(python) - @nieceandtows@programming.dev -
0.008s
-1268 chars
(python) - @brie@beehaw.org -
0.001s
-1516 chars
(c) (fastest) - @Quasari@programming.dev
0.031s
-317 chars
(javascript) (shortest)
submissions open for another day (since the last time I edited the post)
Rust: https://pastebin.com/frYcgdxh
Like last time, a brute force solution: checking if every substring is a set of well formed brackets, and, if so, recording it if its the longest seen so far.
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
C: gcc -
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);
}
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
This is interesting, though I am 3 weeks late.
Raku code: https://glot.io/snippets/gonclpwl3p