Remove oddly nested substrings

Question

Task:

Input will consist of some text, with nested [] separating some of it into nested groups:

abc[d[fgijk]nopq]rst[u[v[[w]]]xy[[[z]]]]

Your task is to remove all brackets, and everything wrapped in an odd number of brackets. For example, a[b]c would remove the [], and the b inside of it. a[[b]]c, however, would only remove the brackets (as b is wrapped in an even number of brackets). If the string were instead a[b[c]d]f, the result would be acf, as the b and d are wrapped in an odd number of brackets, but c is not.

The correct output for the input given at the top would be:

abcfgijkrstvwz

I/O:

You can take input as a string, or any reasonable representation of one (like an array of characters). You can output in a similar fashion, with trailing whitespacing being allowed. You can assume all non-bracket characters are lowercase letters, and you can choose whether the brackets are (), [], or {}.

You can assume the brackets are properly nested (e.g., [ or ][ won't be given as inputs), and that there is at least one letter in the input.

Test cases:

abc                                                 abc
a[b]c                                               ac
[ab]c                                               c
ab[c]                                               ab
[]abc                                               abc
a[]bc                                               abc
abc[]                                               abc
a[[b]]c                                             abc
a[[[b]]]c                                           ac
a[b][c]d                                            ad
a[b][]c                                             ac
[a[b]c]                                             b
a[b[c]d]f                                           acf
[ab]c[df]                                           c
a[a]a[[a]]                                          aaa
abc[d[fgijk]nopq]rst[u[v[[w]]]xy[[[z]]]]            abcfgijkrstvwz
zyx[w]v[ut[s]r[[qp][kj]i]gf][d][][][c][b[][a]]      zyxvsia

Other:

This is code-golf, so shortest answer (in bytes) per language wins!

Answer 1

Retina, 7 bytes

\W\w*.

Try it online!

• -7 bytes (50%) thanks to DLosc :)

Answer 2

Jelly, 10 8 bytes

e€Ø[œpm2

Try it online! or see all test cases

Full program as we use Jelly' smash printing. Uses some tricks from Jonah's J answer, so be sure to upvote that as well!

-2 bytes thanks to Nick Kennedy.

How it works

e€Ø[œpm2 - Main link. Takes a string S on the left e.g. S = "a[b[c]d]e"
  Ø[     - Builtin constant; Yield "[]"
 €       - Over each character in S:
e        -   Is it a bracket?                      e.g. [0,1,0,1,0,1,0,1,0] 
    œp   - Partition S at the truthy indices       e.g. [['a'], ['b'], ['c'], ['d'], ['e']]
      m2 - Take every second sublist               e.g. [['a'], ['c'], ['e']]
           Smash-print and return                  e.g. 'abc'

Answer 3

Vyxal s, 4 bytes

øW4Ḟ

Try it Online!

øW   # Split on words (Matches sequences of word chars + single non-word chars)
     # (Used for dictionary compression algorithm)
  4Ḟ # Get every fourth item.

Beating Jelly :) -2 thanks to Aaron Miller.

Answer 4

Japt v2.0a0 -P, 7 5 bytes

Vyxal was being too cocky for my liking! :D

q\W ë

Try it or run all test cases

q\W ë     :Implicit input of string
q         :Split on
 \W       :  RegEx /[^a-z0-9]/i
    ë     :Get every second element, starting with the first
          :Implicitly join and output

Answer 5

J, ^{39 24 23 18} 15 bytes

#~'_'(*=/\)@I.]

Try it online!

-3 bytes and new approach thanks to FrownyFrog!

old answer, ^{39 24 23} 18 bytes

(+:~:/\)@e.&'[]'#]

Try it online!

Saved around 10 bytes after reading dingledooper's answer and realizing I didn't have distinguish between open and close brackets.

-6 thanks to some damn clever tricks by Bubbler!

Consider 'a[b[c]d]f':

• e.&'[]' Is the input a bracket? Returns a boolean mask:

  0 1 0 1 0 1 0 1 0
  

• (+:~:/\)@ Transform that mask first by a scan using a not equal reduction. Only items with odd numbers of brackets to their left (including themselves) become 1. Then "not-or" +: that result with the original mask:

  1 0 0 0 1 0 0 0 1
  

• #] Use that to filter the original input:

  acf
  

Answer 6

Python 3, 45 bytes

Input is taken from STDIN, and outputs a list of characters, each on its own line.

n=1
for c in input():n^=c<'a'or n>0==print(c)

Try it online!

The main observation is that whether or not a letter is wrapped in an odd number of brackets can be solely determined by taking the parity of the number of brackets preceding that letter.

Python 3, 48 bytes

Same as above, but outputs the entire string on one line.

n=1
for c in input():n^=not'`'<c!=print(end=c*n)

Try it online!

Python 3.8 (pre-release), 49 bytes

A lambda-based solution which is just slightly longer, in comparison:

lambda L,n=1:[c for c in L if(n:=n^(b:=c<'a'))>b]

Try it online!

Answer 7

Wolfram Language (Mathematica), 40 bytes

StringSplit[#,"["|"]",All][[;;;;2]]<>""&

Try it online!

Answer 8

R, 33 32 bytes

-1 byte thanks to @Shaggy.

function(s)gsub("\\W\\w*.","",s)

Try it online!

Simple regex-based solution.

Answer 9

Zsh, 19 bytes

<<<${(e)1//[][]/\`}

Attempt This Online!

Replaces [ and ] with `, and (e)xpands the backtick substitutions. For example, A[[]BCD] becomes

A```BCD`

The contents of backticks when in strings are evaluated as commands. Since there are no commands made only of uppercase letters, the bits in backticks do nothing and aren't included in the output.

If we can't assume input is uppercase, the same method can be adapted to force it to uppercase:

Zsh, 26 bytes

<<<${(L)${(eU)1//[][]/\`}}

Attempt This Online!

---

Zsh, 21 bytes

<<<${1//[][][a-z]#?/}

Attempt This Online!

A less interesting alternative that uses the equivalent of the \W\w*. regex method used by some other answers: [][] matches any square bracket, then [a-z] any letter (# means "0 or more times"), then ? matches any single character.

Must be run with --extendedglob to enable the # pattern feature.

Answer 10

brainfuck, 96 89 71 bytes

-25(!) bytes thanks to Daniel Cristofani

Uses () as brackets.

,[[>+>+<<-]+++++[>--------<-]>[-[[-]>>[<]<[.<<]]]>[>-[++>]<[<]]>[-]<<,]

Try it online!

This is the most complex brainfuck I've ever written and I had quite a few troubles with getting the pointer back to a common position after branches, so I suspect there is some room for optimization.

With some comments:

                              tape layout: _; input1; input2; parity flag
,[                            while loop: runs as long as there is input
  [>+>+<<-]                   make two copies of the input to the right
  +++++[>--------<-]>         subtract 40 from the first copy
  [-[                         if the result is not 0 or 1:
    [-]                         set first copy to 0
    >>[<]<[.<<]                 print second copy is not set
                                pointer is now at _
  ]]
  >[                          if the pointer is at input1
    >-[++>]<[<]                 toggle the parity flag
  ]                  
  >[-]<<                      set second copy to 0
,]

Try it online!

Answer 11

AutoHotKey, 44 bytes

#UseHook
[::
]::
A:=not A
BlockInput,%A%

You need execute it as Administrator permission. And you can always back to normal input status with Ctrl-Alt-Delete if you are in trouble.

Answer 12

Pip, 10 bytes

@UW:a^`\W`

Try it online!

Explanation

The key observation is that the two types of brackets don't need to be distinguished...

    a       First command-line argument
     ^`\W`  Split on this regex (any non-word character, i.e. a bracket)
 UW:        Unweave (the : is needed for precedence reasons, unfortunately)
@           Take the first of the unweave results

Unweave turns a list like [1 2 3 4 5] into [[1 3 5] [2 4]], so @UW applied to the split results gives every other result, starting with the first.

Answer 13

JavaScript, 27 26 bytes

Using pajonk's RegEx replacement approach; be sure to +1 them if you're +1ing this.

s=>s.replace(/\W\w*./g,``)

Try it online!

Original, 44 bytes

Adaptation of my Japt solution.

s=>s.split(/\W/).filter((_,y)=>++y%2).join``

Try it online!

Answer 14

C (gcc), 55 52 bytes

-3 thanks to dingledooper.

Scans through the string and increments a even-starting depth counter, printing any characters on an even depth: as the input is guaranteed to be balanced, the starting depth will always be an even number. Uses Jonah's trick of only scanning for brackets regardless of direction.

l;f(char*s){for(;*s;s++)*s>96?l%2||putchar(*s):l++;}

Try it online!

Answer 15

Haskell, 50 bytes

f(h:t)=[h|h>']',even$sum[1|b<-t,b<'a']]++f t
f x=x

Try it online!

Answer 16

Vyxal K, 24 bytes

Thanks to exedraj, emanresu A and hyper-neutrino for guiding me through my Vyxal journey's beginning.

ƛ91≠*;ƛ93≠*;'[¥¬|¥¬£];C∑

Try it Online!

Answer 17

JavaScript (Node.js), 46 bytes

x=>[...x].filter(x=>(z^=b=x>'z')>b,z=1).join``

Try it online!

Port of dingledooper's answer thanks to dingledooper.

JavaScript (Node.js), 51 bytes

x=>x.replace(/[{}]([^{}]*)/g,(a,b)=>i++%2?b:'',i=0)

Try it online!

This makes use of the fact that after an even amount of open or close brackets, the bit of the string up until the next bracket should be kept. After an odd amount, it shouldn't. For example, on the demo input string, the following happens:

Full:    abc[d[fgijk]nopq]rst[u[v[[w]]]xy[[[z]]]]
Valid:   abc  [fgijk     ]rst  [v [w ]   [ [z ] ]
Invalid:    [d      ]nopq    [u  [  ] ]xy [  ] ]

We just smoosh the valid half together, remove all the brackets, and we have our answer!

Answer 18

APL (Dyalog Classic), 22 bytes

{((~≠\⍵∊'[]')/⍵)~'[]'}

Try it online!

Explained

{                    }   ⍝ Monadic function, takes string on left
      ⍵∊'[]')            ⍝ Boolean mask for characters which are braces
 ((~≠\                   ⍝ Scan the mask by not-equal and negate (Mask for characters that is needed to kept with braces)
             /⍵)         ⍝ Filter the input using the scanned mask
                ~'[]'    ⍝ Remove the braces

Try it online!

APL (Dyalog Classic), 24 bytes

{((~2|+\⍵∊'[]')/⍵)~'[]'}

Try it online!

Monadic function, takes the string on right

Approaches in array oriented languages are really neat

Answer 19

jq, 19 bytes

gsub("\\W\\w*.";"")

Uses the regular expression from tsh's answer.

Try it online!

Answer 20

Charcoal, 16 bytes

ＦＳ¿№βιＦ¬﹪Ｌυ²ι⊞υι

Try it online! Link is to verbose version of code. Explanation: Prints lowercase letters unless an odd number of other characters have been recorded.

Alternative solution, also 16 bytes:

⪫Φ⪪⪫⪪Ｓ]¦[¦[¬﹪κ²ω

Try it online! Link is to verbose version of code. Explanation: Replaces ]s with [s, then splits on [s and outputs alternate elements.

Answer 21

Haskell, 66 61 bytes

f(x,y)c=(x-sum[x+x|c>'z'],y++[c|c<'{',x>0])
snd.foldl f(1,"")

Try it online!

Haskell doesn't really do regex.

Answer 22

Python 3, 40 bytes (using regex)

lambda s:re.sub("\W\w*.","",s)
import re

Try it online!

Version without lambda, 44 bytes

import re
print(re.sub("\W\w*.","",input()))

Try it online!

Thanks to @emanresu A for the lambda version

Answer 23

K (ngn/k), 12 bytes

{x&=\x>:93}#

Try it online!

Takes advantage of the input restrictions, i.e. only having to deal with lower cased characters and [] as the brackets.

• {...}# set up a filter, removing items from the (implicit) input that do not match the criteria in {...}
  • x>:93 determine which characters in the input are letters, updating x inplace (ASCII codes for [] are 91 93, a..z are 97..122)
  • =\ do an equals-scan over this (characters at an even level of nesting become 1, otherwise are 0)
  • x& take the logical and, essentially asking "is this a letter AND is it at even level of nesting?"

Answer 24

Ly, 37 bytes

1s>ir['aL:[pfpl!sp0]p![pl[p:o0]pp0]p]

Try it online!

This code takes advantage of the input constraints that the characters will only come from the set of characters a-z and [ or ]. Which means checking to see if the codepoint is less than the codepoint for a is sufficient to identify the brackets. It also relies on the constraint that only valid sequences of open and close brackets will given. That allows each bracket to be a "on/off" toggle for the print setting, since it doesn't matter whether it's an open or close, it will always change the even/odd state of the accumulated groupings.

1s                                    -- Set "true" as initial print boolean state
  >                                   -- Change to a clean stack
   ir                                 -- Read all input as codepoints, reverse stack
     [                              ] -- Loop to process each input codepoint
      'aL                             -- Compare top of stack to "a"
         :[p      0]p                 -- if/then, true is codepoint is "[" or "]"
            fp                        -- Pull codepoint forward and delete
              l!sp                    -- Flip "on/off" boolean print state 
                     ![p         0]p  -- if/then, true if codepoint is "a-z"
                        l             -- Load print boolean state
                         [p  0]p      -- if/then, true if we should print the character 
                           :o         -- Duplicate the codepoint and print one copy
                                p     -- Delete the current codepoint from the stack

Answer 25

brainfuck, 439 bytes

,[>[-]>[-]+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>[-]>[-]<<<<[->>>+>+<<<<]>>>>[-<<<<+>>>>]<[-<->][-]>[-]<<[->+>+<<]>>[-<<+>>][-]+<[[-]>[-]<]>[[-]>[-]+<<<<<<[->>>>>>[-]<<<<<<]>>>>>>[-<<<<<<+>>>>>>]<<<<+>>>]<<++>[-]+<[[-]>[-]<]>[[-]>[-]+<<<<<[->>>>>[-]<<<<<]>>>>>[-<<<<<+>>>>>]<<<+>>]<[-]+<[[-]>[-]<]>[[-]>[-]>[-]<<<<<[->>>>+>+<<<<<]>>>>>[-<<<<<+>>>>>][-]+<[[-]>[-]<]>[[-]<<<<.>>>>]<<]<<,]

Try it online!

---

Generated using a self-written yet poorly optimizing brainfuck compiler still under development. Its brainfuck macro assembler source code without the prelude can be seen below. I am certain a carefully layed out tape together with hand-written brainfuck would dramatically improve this byte count.

(macro ppcg233884 () (
    ; define parity cell
    (let:nve $parity 0 (
        ; read in character stream
        (let:nve $char 0 (
            (getc:w $char)
            (while:re $char (

                ; check if it is a bracket and update parity
                (let:nve $wasbracket 0 (
                    (let:nve $bracket 91 (
                        ; '['
                        (sub:ra $char $bracket)
                        (ifnot:re $bracket (
                            (not:a $parity)
                            (inc:a $wasbracket)))
                        ; ']'
                        (inc:a $bracket)
                        (inc:a $bracket)
                        (ifnot:ze $bracket (
                            (not:a $parity)
                            (inc:a $wasbracket)))))

                    ; only print on even parity when it was not a bracket
                    (ifnot:ze $wasbracket (
                        (ifnot:re $parity (
                            (putc:r $char)))))))

                (getc:w $char)))))))))

(macro main () (
    (ppcg233884)))

Answer 26

05AB1E, 6 bytes

Aм¡ιн˜

I/O as a list of characters. If a nested list output is allowed, the trailing ˜ could be removed.

Try it online or verify all test cases.

Explanation:

A       # Push the lowercase alphabet
 м      # Remove all these letters from the (implicit) input-list
  ¡     # Split the (implicit) input-list on the remaining characters ["[","]"]
   ι    # Uninterleave this list of lists into two parts
    н   # Only leave the first part of sublists
     ˜  # Flatten this nested list into a single list of characters
        # (after which it is output implicitly as result)

(Could also work for mixed cased letters by replacing A with á.)

Answer 27

V (vim), 19 bytes

Thanks to Aaron Miller for this two bytes shorter version.

äh:s/]/[/g
òf[df[òx

Try it online!

---

V (vim), 21 bytes

xPP:s/]/[/g
òf[df[ò0x

Try it online!

Explanation

xPP       " Duplicate initial character,
          "     since `f[` would else skip it.
          "     If the input is empty, error out.
:s/]/[/g  " Unify all brackets to `[`.
ò         " As long as necessary,
 f[       "     keep everything until even `[` and
 df[      "     discard everything until odd `[`.
ò         " End the loop.
0x        " Remove the duplicate character.

Answer 28

Curry (PAKCS), 55 bytes

f(h:t)=[h|h>']',0<foldl(*)1[-1|b<-t,b<'a']]++f t
f[]=[]

Try it online!

This is based on Lynn's Haskell answer. There are two difficulties adapting it to Curry however. The first is that curry doesn't have falling through so the case f x=x needs to be replaced* with f[]=[] for an extra byte.

The next is that curry doesn't have sum so we need to replace it with some sort of fold. The most efficient way to do this is to actually make a product instead of a sum since it is way cheaper to check if something is positive than whether it is even.

^{*: This doesn't actually behave like I would expect. I'm not a curry expert. However in both the expected behavior and the actual behavior it fails so...}

Answer 29

C (gcc), 66 63 bytes

f(char*s){for(char*z=s,n=0;*z=*s++;*z-91&&*z-93?n%2||++z:++n);}

Try it online!

Answer 30

Haskell, 53 bytes

s?(x:r)|x<'a'=(1-s)?r|s>0=s?r|s<1=x:s?r;_?q=q;f=(0?)

Try it online!