Programming Challenges

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

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

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

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

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

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"

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!

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.

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.

(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 '[(({})({)(()}]' '(){}[]'

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

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([], &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()

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

Zsh:

s=$1 l=$#s
while (( 1 )) {
  s=${s//(\{\}|\(\)|\[\])}
  if [[ $#s < $l ]] { l=$#s } else { break }
}
<<<$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

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(&'{')) | (']', Some(&'[')) | (')', Some(&'(')) => {
                stack.pop();
            }
            _ => stack.push(ch),
        }
    }
    let output: String = stack.iter().collect();
    println!("{}", output);
}

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