this post was submitted on 15 Aug 2023
4 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
 

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)

all 12 comments
sorted by: hot top controversial new old
[–] shape-warrior-t@kbin.social 3 points 1 year ago* (last edited 1 year ago) (1 children)

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))

[–] brie@beehaw.org 1 points 1 year ago

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);
	}
}
[–] gifti@programming.dev 2 points 1 year ago* (last edited 1 year ago)

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!

[–] DrillingStricken@programming.dev 1 points 1 year ago* (last edited 1 year ago)

gjafkjgdhasdhlaksdfaskdfjlkasdjfkasdfklsdjfkasdfasdfncvquioweru9ncna,.2

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

Hi! I created a stack-based language called kcats that is meant to be a simple and powerful language and good for small programs like this one. You can read more about it here: https://skyrod-vactai.github.io/kcats/book-of-kcats.html

Here's the solution in kcats (assumes the input is on the stack):

[[\[ \]] [\{ \}] [\( \)]]
"" float
[[[last] dive wrap swap [lookup] dip =]
 [drop pop drop]
 [put]
 if] step
dropdown

A bit of explanation: First place a mapping of opening bracket to its matching closing bracket on the stack. Then place the empty result which will be modified as we go. Float the input to the top of stack. Then an if statement. The first part of the if statement is the condition: look up the matching close bracket to the last item in the result, see if it equals the current character. If the condition is true, drop the current character and the last item in the result. If not, put the item into the result. Then 'step' runs that if statement on each character of the input. Finally, when we're done we don't need the mapping of matching brackets anymore, and we drop it.

[–] Andy@programming.dev 1 points 1 year ago* (last edited 1 year ago)

Factor:

For foolish brevity, renamed lemmy -> l and rid -> r.

USING: kernel regexp command-line namespaces sequences io ;
IN: l

: r ( S -- s )
  R/ (\{\}|\(\)|\[\])/
  [ 2dup re-contains? ] [
    [ "" re-replace ] keep
  ] while drop
;

MAIN: [ command-line get [ r print ] each ]

When compiled to an executable ridpairs, pass each string as an argument:

$ ./ridpairs '[(({})({)(()}]' '(){}[]' '((){}[]]'
[(({)(}]

(]
$ hyperfine "./ridpairs '[(({})({)(()}]' '(){}[]' '((){}[]]'"
Benchmark 1: ./ridpairs '[(({})({)(()}]' '(){}[]' '((){}[]]'
  Time (mean ± σ):       4.0 ms ±   0.4 ms    [User: 1.5 ms, System: 2.5 ms]
  Range (min … max):     3.3 ms …   5.9 ms    576 runs

I think that amounts to 207 significant chars, definitely not the winner there.


EDIT: build instructions:

  • Download and extract the ~~development~~ release from https://factorcode.org/
  • Paste the solution code into a new file at work/l/l.factor (the work folder is already present in the factor folder)
  • Launch the Factor UI: ./factor and inside the UI enter "l" deploy-tool
  • A menu with options pops up, choose to "Use the ... vocabulary"
  • Click "Deploy"