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)

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

    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
      link
      fedilink
      arrow-up
      6
      ·
      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);
      	}
      }
      
  • SleveMcDichael@programming.dev
    link
    fedilink
    English
    arrow-up
    4
    ·
    edit-2
    1 year ago

    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

    • Ategon@programming.devOPM
      link
      fedilink
      English
      arrow-up
      2
      ·
      1 year ago

      10/10 Test cases passed

      • Time: 4.472s
      • Characters: 290

      Yeah haha, its fair game. Theres a reason this is classified under easy

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

        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…

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

          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

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

            It’s probably adding compilation time, because a system that runs my python regex in 40ms should probably run this rust program in less than 1ms

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

    python 3 using regex:

    import re
    i=input()
    p=r'(?:\(\)|\{\}|\[\])'
    while re.search(p,i):
     i=re.sub(p,'',i)
    print(i)
    

    edit: made it uglier for the least characters challenge

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

      10/10 Test cases passed

      • Time: 445ms
      • Characters (excluding input): 92

      Originally intended for it to take input in rather than values being hardcoded but I didnt specify so its fair game, Did an edit on the post to say it and you edited yours to account for it already

      edit: I see your edit, will do another run with that

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

    Here’s an attempt in Ruby. I haven’t coded in ruby in a while. I was going for character count, so I just used regex replacement.

    o=i=gets.chomp
    o=i.gsub!(/\(\)|{}|\[\]/,'') while o
    puts i
    

    I think I might do a speed one for fun.

    Edit (command line input):

    o=i=ARGV[0]
    o=i.gsub!(/\(\)|{}|\[\]/,'') while o
    puts i
    
  • Ategon@programming.devOPM
    link
    fedilink
    English
    arrow-up
    2
    ·
    1 year ago

    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

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

    Late to the game but I’d love to hear some feedbacks as I’m still a beginner.

    Language: C

    Warning: There is a problem when executing in Git that said >bash: syntax error near unexpected token ‘(’ if you have parentheses in the input. But it works normally in other terminals. And somehow Lemmy always remove the header file in my comment. So after the first “include” is “stdio.h”, and the second is “string.h”. And they are inside “<>”.

    #include #include

    void CharShifter(char* string, int LengthOfString, int IdxOfOpenChar);
    
    int main(int argc, char* agrv[])
    {
        if (argc != 2)
        {
            printf("Usage: matching your_string\n");
            return 1;
        }
    
        char* string = agrv[1];
    
        int LengthOfString = strlen(string);
        int NumberOfTurn = 0;
        int FoundAMatch = 0;
    
        while (NumberOfTurn &lt;= FoundAMatch)
        {
            for (int i = 0; i &lt; LengthOfString - 1; i++)
            {
                if (string[i] == '[')
                {
                    if (string[i+1] == ']')
                    {
                        LengthOfString = LengthOfString - 2;
                        
                        CharShifter(string, LengthOfString, i);
                        FoundAMatch++;
                    }
                }
                else if (string[i] == '(')
                {
                    if (string[i + 1] == ')')
                    {
                        LengthOfString = LengthOfString - 2;
    
                        CharShifter(string, LengthOfString, i);
                        FoundAMatch++;
                    }
                }
                else if (string[i] == '{')
                {
                    if (string[i+1] == '}')
                    {
                        LengthOfString = LengthOfString - 2;
    
                        CharShifter(string, LengthOfString, i);
                        FoundAMatch++;
                    }
                }
            }
            NumberOfTurn++;
        }
    
        for (int i = 0; i &lt; LengthOfString; i++)
        {
            printf("%c", string[i]);
        }
        printf("\n");
        return 0;
    }
    
    void CharShifter(char* string, int LengthOfString, int IdxOfOpenChar)
    {
        int NumberOfShiftedChar = LengthOfString - IdxOfOpenChar;
        int TwoAwayFromChar = IdxOfOpenChar + 2;
    
        for (int j = 0; j &lt; NumberOfShiftedChar; j++)
        {
            if (string[TwoAwayFromChar + j] == '(' || string[TwoAwayFromChar + j] == ')'
            || string[TwoAwayFromChar + j] == '[' || string[TwoAwayFromChar + j] == ']'
            || string[TwoAwayFromChar + j] == '{' || string[TwoAwayFromChar + j] == '}')
            {
                string[IdxOfOpenChar + j] = string[TwoAwayFromChar + j];
            }
        }
        return;
    }
    
    • metiulekm@sh.itjust.works
      link
      fedilink
      English
      arrow-up
      2
      ·
      1 year ago

      I thought I knew how to resolve the &lt; 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);
      ```
      
      • DrillingStricken@programming.dev
        link
        fedilink
        arrow-up
        1
        ·
        edit-2
        1 year ago

        Thank you!! It indeed looks nicer than before when wrapped around ```, but something still stays the same.

        The &lt; is the less than sign. But I don’t think I use greater than sign in my loops, what line do you get that problem? And if you can execute the code, let me know your thoughts. I’m learning, so it will be really helpful. Thanks!!

  • Andy@programming.dev
    link
    fedilink
    arrow-up
    2
    ·
    edit-2
    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”
  • gifti@programming.dev
    link
    fedilink
    arrow-up
    2
    ·
    edit-2
    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!

  • skyrod2@programming.dev
    link
    fedilink
    arrow-up
    1
    ·
    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.

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

    Skew, targetting Deno/JS, and recieving input via command-line parameters.

    @entry
    def main {
        dynamic.Deno.args.forEach(s => {
            var r=dynamic.RegExp("\\(\\)|{}|\\[]","g")
            while s != (s = s.replaceAll(r,"")) {}
            dynamic.console.log(s)
        })
    }
    

    Compile with skewc main.sk --output-file=main.js --release.

    Compiled JS
    (function(){function c(){Deno.args.forEach(function(a){for(var b=RegExp('\\(\\)|{}|\\[]','g');a!==(a=a.replaceAll(b,'')););console.log(a)})}c()})();
    

    To run:

    deno run main.js '[(({})({)(()}]' '(){}[]'
    
  • Phytolizer@programming.dev
    link
    fedilink
    arrow-up
    1
    ·
    edit-2
    1 year ago

    ISO C99:

    #include 
    #include 
    #include 
    #include 
    
    static char opener(char ch) {
        switch (ch) {
            case '}': return '{';
            case ']': return '[';
            case ')': return '(';
            default: return 0;
        }
    }
    
    enum { MAX_LINE_LENGTH = 2048 };
    static char buffer[MAX_LINE_LENGTH];
    
    int main(void) {
        char* line = fgets(buffer, sizeof(buffer), stdin);
        if (line == NULL) {
            fprintf(stderr, "Error: could not read input.\n");
            return EXIT_FAILURE;
        }
        size_t len = strlen(line);
        if (len > 0 and line[len - 1] == '\n') {
            line[--len] = 0;
        }
    
        char stack[128];
        size_t stack_size = 0;
        for (size_t i = 0; i &lt; len; ++i) {
            char pair = opener(line[i]);
            if (pair and stack_size != 0 and stack[stack_size - 1] == pair) {
                --stack_size;
            } else {
                stack[stack_size++] = line[i];
            }
        }
        stack[stack_size] = 0;
        puts(stack);
    }
    

    Mirrored code on bpa.st

    Compile: cc -std=c99 -pedantic-errors -O2 bracket.c -o bracket

    (Edited to add -O2 because you mentioned it would be timed.)

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

    Elixir solution

    To run it, you need Erlang and Elixir installed with iex available on path (installation instructions here)

    Paste the code in a file with extension .exs (e.g. solution.exs) and run with iex solution.exs.

    It prints the output to Standard Output and appends a newline at the end

    Please let me know if this method of running code does not work.

    defmodule Brackets do
      @pairs %{
        "]" => "[",
        "}" => "{",
        ")" => "("
      }
    
      def simplify(brackets) do
        brackets
        |> String.trim()
        |> String.graphemes()
        |> Enum.reduce([], &amp;reducer/2)
        |> Enum.reverse()
      end
    
      defp reducer(c, []), do: [c]
    
      defp reducer(c, [x | rest] = acc) do
        if @pairs[c] == x do
          rest
        else
          [c | acc]
        end
      end
    
    end
    
    brackets = IO.gets("Please enter your input> ")
    
    brackets
    |> Brackets.simplify()
    |> IO.puts()
    
  • Andy@programming.dev
    link
    fedilink
    arrow-up
    1
    ·
    edit-2
    1 year ago

    EDIT: Lemmy is bad at letting me include the less than sign in comments. So if you see &lt; it should be a single character instead.


    Zsh:

    s=$1 l=$#s
    while (( 1 )) {
      s=${s//(\{\}|\(\)|\[\])}
      if [[ $#s &lt; $l ]] { l=$#s } else { break }
    }
    &lt;&lt;&lt;$s
    

    Usage:

    $ zsh lemmy.zsh '[(({})({)(()}]'
    [(({)(}]
    

    Benchmarks:

    $ hyperfine "zsh ./lemmy.zsh '[(({})({)(()}]'
    Benchmark 1: zsh ./lemmy.zsh '[(({})({)(()}]'
      Time (mean ± σ):       2.2 ms ±   0.2 ms    [User: 1.9 ms, System: 0.4 ms]
      Range (min … max):     1.9 ms …   5.4 ms    980 runs
    
    • Andy@programming.dev
      link
      fedilink
      arrow-up
      1
      ·
      edit-2
      1 year ago

      If I figure out how to properly use the f (repeat) modifier, I’ll post a second attempt.

      The whole while loop and variable assignments should be replaceable with something like

      ${1:fs/(\\{\\}|\\(\\)|\\[\\])//}
      

      But it’s not quite right, or there’s a Zsh bug…

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

    Rust solution:

    fn main() {
        let input = std::env::args().skip(1).next().unwrap();
        let mut stack = Vec::with_capacity(input.len() / 4);
        for ch in input.chars() {
            match (ch, stack.last()) {
                ('}', Some(&amp;'{')) | (']', Some(&amp;'[')) | (')', Some(&amp;'(')) => {
                    stack.pop();
                }
                _ => stack.push(ch),
            }
        }
        let output: String = stack.iter().collect();
        println!("{}", output);
    }
    

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