Welcome to the first programming challenge! Three of these will be posted a week and you can complete it in any language you want.
You get a point for completing an easy challenge, 2 for a medium, and 3 for a hard. For each challenge if you solve it in the least amount of characters you get a bonus point, and if your code runs the fastest when I check it you also get a bonus point. (ties mean everyone who tied gets the bonus point although exact duplicate answers wont count)
Ill be posting a leaderboard that will show the people who have the most points every month
Submissions will be open for a week
As a new hire of bracket inc., you have been tasked with getting rid of excess brackets lying around the facility. You must simplify a series of brackets so that only brackets that dont have a match remain (a match is an opening and closing bracket of the same type beside each other). The final result should have no matches
As an example for the input [(({})({)(()}] the expected output would be [(({)(}]
These are the valid types of brackets: (){}[]
Your system will be tested against 10 different unknown test cases before it is unleashed on the facility. In order to complete this task you must pass all of the test cases.
Any programming language may be used and to submit an answer reply on this post with the code and the language you coded it in
Edit: Clarification, you must take input in from the user using the program instead of them being hardcoded. (makes it easier to test)
Here’s an O(n) solution using a stack instead of repeated search & replace:
closing_to_opening = {')': '(', ']': '[', '}': '{'}
brackets = input()
acc = []
for bracket in brackets:
if bracket in closing_to_opening:
if acc and acc[-1] == closing_to_opening[bracket]:
acc.pop()
else:
acc.append(bracket)
else:
acc.append(bracket)
print(''.join(acc))
Haven’t thoroughly thought the problem through (so I’m not 100% confident in the correctness of the solution), but the general intuition here is that pairs of brackets can only match up if they only have other matching pairs of brackets between them. You can deal with matching pairs of brackets on the fly simply by removing them, so there’s actually no need for backtracking.
Golfed, just for fun:
a=[]
[a.pop()if a and a[-1]==dict(zip(')]}','([{')).get(b)else a.append(b)for b in input()]
print(''.join(a))
This gave me the idea to do the same in C, but use the argument string itself as the stack to avoid any allocations. It could probably be further optimized.
#include
int main(int argc, char **argv)
{
char map[256] = { 0 };
map[')'] = '(';
map['}'] = '{';
map[']'] = '[';
while (--argc) {
char *top, *p, c;
top = p = *++argv;
while ((c = *p++)) {
if (top != *argv && map[(size_t)c] == top[-1]) {
top--;
} else {
*top++ = c;
}
}
*top = 0;
puts(*argv);
}
}
Here’s an entry in Rust, though it feels quite a bit like cheating:
fn main() {
let mut a = std::env::args().skip(1).next().unwrap();
println!("{}", f(&mut a));
}
fn f(a: &mut String) -> String {
let mut b = String::new();
while *a != b {
b = a.clone();
*a = a.replace("{}", "").replace("()", "").replace("[]", "");
}
return b;
}
edit: added main function to take cli input.
edit2: a rust based stack implementation: https://pastebin.com/FgfuxxRV
10/10 Test cases passed
- Time: 4.472s
- Characters: 290
Yeah haha, its fair game. Theres a reason this is classified under easy
Time: 4.472s
Ough. Those must be some hefty test cases, even the deepest ones I tested (250 loops) completed in less than a tenth of a second. If its possible I may try to find a faster solution and resubmit later…
Might be an issue with the system im using to test. Doing it through a site but I can set up an actual testing system and run it through it for the final results. Time was solidly around 500ms even with a small test case
Ill be going through and testing these before submissions close. Working on a system that will let me test them easier for future runs
If lemmy breaks your code formatting you can use a third party site to share the code or I can try to figure out what broke when I go to run it
I thought I knew how to resolve the and thing, but it didn’t work at all. I guess the sanitizing code is a bit overzealous after the recent vulnerability.
Anyway, your code will look slightly nicer, at least on the web interface, if you surround it with three backticks, like this
```c
void CharShifter(char* string, int LengthOfString, int IdxOfOpenChar);
```
I know I’m too late – but nonetheless …
Factor:
[ [ dup “()” “[]” “{}” [ “” splitting:replace ] tri@ tuck = not ] loop print flush ] each-line
Edit: Thanks to the Alexes from the Factor Discord for xer suggestion!