13
\$\begingroup\$

Part of Advent of Code Golf 2021 event. See the linked meta post for details.

Related to AoC2017 Day 9.

Weekends are Bubbler's days off from posting these lol


A large stream blocks your path. According to the locals, it's not safe to cross the stream at the moment because it's full of garbage. You look down at the stream; rather than water, you discover that it's a stream of characters.

You sit for a while and record part of the stream (the input). The characters represent groups - sequences that begin with { and end with }. Within a group, there are zero or more other things, separated by commas: either another group or garbage. Since groups can contain other groups, a } only closes the most-recently-opened unclosed group - that is, they are nestable. The input represents a single group which itself may or may not contain smaller ones.

Sometimes, instead of a group, you will find garbage. Garbage begins with < and ends with >. Between those angle brackets, almost any character can appear, including { and }. Within garbage, < has no special meaning.

In a futile attempt to clean up the garbage, some program has canceled some of the characters within it using !: inside garbage, any character that comes after ! should be ignored, including <, >, and even another !.

You don't see any characters that deviate from these rules. Outside garbage, you only find well-formed groups, and garbage always terminates according to the rules above.

The following are some example streams with the number of groups they contain:

  • {}, 1 group.
  • {{{}}}, 3 groups.
  • {{},{}}, also 3 groups.
  • {{{},{},{{}}}}, 6 groups.
  • {<{},{},{{}}>}, 1 group (which itself contains garbage).
  • {<a>,<a>,<a>,<a>}, 1 group (containing four pieces of garbage).
  • {{<a>},{<a>},{<a>},{<a>}}, 5 groups.
  • {{<!>},{<!>},{<!>},{<a>}}, 2 groups (since all >s except the last one are cancelled, creating one large garbage).
  • {{<!!>,{<abc>},<!!!>>,{{<{!>}>},<yes<<<no>}},<>}, 5 groups.

Input: A self-contained, well-formed group as a string.

Output: The total number of groups it contains, including itself.

Standard rules apply. The shortest code in bytes wins.

\$\endgroup\$
2
  • 4
    \$\begingroup\$ So ! only cancels the single character after it? I think that it should be made clear that it's only the one character after ! that is ignored \$\endgroup\$ Dec 11 '21 at 6:03
  • 1
    \$\begingroup\$ Suggested test case: {{<>,<!!>}}, 2 groups. My initial approach worked for all existing test cases, but not for this one (because I removed !> before !!, and therefore also incorrectly removed !}). \$\endgroup\$ Dec 13 '21 at 10:03

16 Answers 16

13
\$\begingroup\$

Retina 0.8.2, 12 bytes

!.

<.*?>

}

Try it online! Link includes test cases. Explanation: The first stage deletes !s and the character they protect, the second stage deletes garbage, and the final stage counts the number of remaining groups.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Talk about the right tool for the job… \$\endgroup\$
    – Jonah
    Dec 11 '21 at 1:07
5
\$\begingroup\$

JavaScript (Node.js), 41 bytes

x=>x.replace(/<(!?.)*?>|[^}]/g,'').length

Try it online!

If it's acceptable to output in unary, remove the .length for 34 bytes.

This removes garbage and characters that aren't }, then counts what's left.

\$\endgroup\$
9
  • \$\begingroup\$ /<(!?.)*?>|./g saves you 6 bytes. \$\endgroup\$
    – Neil
    Dec 11 '21 at 0:44
  • \$\begingroup\$ @Neil Nice, thanks! \$\endgroup\$
    – emanresu A
    Dec 11 '21 at 0:49
  • 1
    \$\begingroup\$ @Neil What does *? do differently to *? \$\endgroup\$
    – emanresu A
    Dec 11 '21 at 0:51
  • 1
    \$\begingroup\$ Unary output isn't normally allowed, is it? \$\endgroup\$
    – pxeger
    Dec 11 '21 at 7:29
  • 1
    \$\begingroup\$ @emanresuA the most upvoted answer there says "only for sed/retina/etc.". JS's most natural number representation is definitely not unary. \$\endgroup\$
    – pxeger
    Dec 11 '21 at 9:46
4
\$\begingroup\$

Zsh, 35 bytes

tr -dc }<<<${1//<(!?|[^>])#>}|wc -c

Attempt This Online!

Removes all matches of the pattern <(!?|[^>])#>, which matches all garbage.

A few notes:

  • Zsh doesn't support greedy vs. non-greedy matching, so I have to use [^>] rather than just ?. (? matches any single character, but in order to get the garbage properly, >s must not be matched)
  • I count closing braces rather than opening braces at the end - they give the same result since they're always balanced, but } does not need to be escaped thanks to the ignore_closing_braces option
\$\endgroup\$
4
\$\begingroup\$

Ruby, 39 36 33 bytes

->s{s.scan(/{(<(!?.)*?>)*/).size}

Try it online!

Thanks lonelyelk for -3 bytes, I suck at regex.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can save one character since you don't need to remove the closing «>»: TIO \$\endgroup\$
    – lonelyelk
    Dec 11 '21 at 13:33
  • 1
    \$\begingroup\$ Or using a lazy regexp it can even be made shorter (with removing of the closing «>» though) 36 bytes \$\endgroup\$
    – lonelyelk
    Dec 11 '21 at 13:50
4
\$\begingroup\$

TypeScript Types, 192 bytes

//@ts-ignore
type M<T,N=[],A=[0]>=T extends`${infer C}${infer T}`?M<C extends"!"?T extends`${string}${infer T}`?T:0:T,C extends"{"?[...N,...A]:N,C extends"<"?[]:C extends">"?[0]:A>:N["length"]

Try It Online!

Ungolfed / Explanation

// Mode is [0] if parsing groups, or [] if parsing garbage
type Main<Str, Count=[], Mode=[0]> =
  // Get the first character of Str
  Str extends `${infer Char}${infer Rest}`
    ? Main<
      // If char is "!", set Str to Str[2..]; otherwise, set Str to Str[1..]
      Char extends "!" ? Rest extends`${string}${infer RestRest}` ? RestRest : 0 : Rest,
      // If char is "{", add Mode to Count
      Char extends "{" ? [...Count, ...Mode] : Count,
      // If char is "<", set Mode to [] (garbage); if char is ">", set Mode to [0] (not garbage)
      Char extends "<" ? [] : Char extends">" ? [0] : Mode
    >
    // Str is empty; return Count
    : Count["length"]
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 39 bytes

≔⁰η≔¹ζ≔⁰εFS«¿ε≔⁰ε≡ι!≔¹ε<≔⁰ζ>≔¹ζ}≧⁺ζη»Iη

Try it online! Link is to verbose version of code. Explanation:

≔⁰η

Start off with no groups.

≔¹ζ

Start off with no garbage.

≔⁰ε

Start off without cancellation.

FS«

Loop over the input characters.

¿ε≔⁰ε

If the previous character was a ! then cancel this character.

≡ι

Otherwise, switch on the current character.

!≔¹ε

If it's a ! then cancel the next character.

<≔⁰ζ

If it's a < then turn on garbage.

>≔¹ζ

If it's a > then turn off garbage.

}≧⁺ζη

If it's a } that's not inside garbage then increment the number of groups.

»Iη

Output the final number of groups.

\$\endgroup\$
2
\$\begingroup\$

Python 3, 117 bytes

n=0;g=1;s=input()
for x,y in zip(s,s[1:]):
 if '!'not in x+y:
  if y in'<>':g='<>'.index(y)
  if g:n+=y=='}'
print(n)

Try it online!

A regex less solution, shorter than @Ajax1234

Python 2, 114 bytes (Unsure if allowed)

n=0;g=1;s=input()
for x,y in zip(s,s[1:]):
 if '!'not in x+y:
  if y in'<>':g='<>'.index(y)
  if g*y=='}':print 1,

Try it online!

outputs in unary with space between each digit

\$\endgroup\$
2
  • \$\begingroup\$ Fails for {<!!>,{}} (should be 2 groups). Other than that, n+=g*y=='}' works for the first answer to make it the same length as the second. \$\endgroup\$
    – Neil
    Dec 11 '21 at 11:06
  • \$\begingroup\$ g=y=='>' saves you another 7 bytes. \$\endgroup\$
    – Neil
    Dec 11 '21 at 11:16
2
\$\begingroup\$

Python 3, 74 bytes

f=lambda s,m=1:s>''and(s[0]=='{'*m)+f(s[1+('!'==s[0]):],m^('><'[m]==s[0]))

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 68 bytes

Fold[StringDelete,#,{"!"~~_,"<"~~Shortest@__~~">"}]~StringCount~"{"&

Try it online!

\$\endgroup\$
2
\$\begingroup\$

x86 32-bit machine code, 31 bytes

56 96 31 d2 31 c9 4a 42 41 ac 3c 21 75 01 46 3c 3e 74 f1 e2 f3 7a f1 73 ee 48 7b ed 5e 92 c3

Try it online!

Following the regparm(1) calling convention, this takes the address of a null-terminated byte string in EAX.

Assembly:

.text                   # In the main loop, EDX will count the number of {
.global gstr            #  and ECX will be 1 outside garbage, 0 inside garbage.
.intel_syntax noprefix
gstr:
    push esi        # Save the value of ESI onto the stack
    xchg esi, eax   # Switch the string address into ESI
    xor edx, edx    # Set EDX to 0
c1: xor ecx, ecx    # Set ECX to 0
    dec edx         #  (These two instructions have a net effect of nothing,
iD: inc edx         #    but we can jump into the middle to add 1 to EDX.)
r:  inc ecx         # Increment ECX, at first to 1
l:  lodsb           # Read a character from the string into AL
    cmp al, 0x21    # Check for !
    jne s           #  Jump if not !
    inc esi         #  If !, increment ESI to skip the next character
s:  cmp al, 0x3E    # Compare with >
    je c1           #  Jump on > to reset ECX to 1
    loop r          # Decrement ECX and jump (to restore it and proceed)
                    #  if it was 0 (within garbage)
    jpe r           # Jump (same) to ignore } and ,
    jnc iD          # Jump on { to count up in EDX (and restore ECX) 
    dec eax         # Decrement EAX, setting PF from the low 8 bits
    jpo l           # Jump on < to proceed (ECX remains 0)
    pop esi         # NUL: Restore the value of ESI from the stack
    xchg edx, eax   # Switch the count into EAX
    ret             # Return
\$\endgroup\$
2
\$\begingroup\$

Rust, 170 166 bytes

|i:&str|{let(mut g,mut s)=(0,vec![123]);for c in i.bytes(){match&[s[s.len()-1],c]{b"<!"|b"{<"|b"{{"=>s.push(c),[33,_]|b"<>"=>{s.pop();}b"{}"=>{g+=1;s.pop();}_=>()}}g}

Try it online!

  • -4 bytes by not using Option (thanks @AnttiP)
\$\endgroup\$
1
  • 1
    \$\begingroup\$ -4 bytes by removing the question mark: |i:&str|{let(mut g,mut s)=(0,vec![123]);for c in i.bytes(){match&[s[s.len()-1],c]{b"<!"|b"{<"|b"{{"=>s.push(c),[33,_]|b"<>"=>{s.pop();}b"{}"=>{g+=1;s.pop();}_=>()}}g} \$\endgroup\$
    – AnttiP
    Dec 12 '21 at 17:59
2
\$\begingroup\$

BQN, 56 bytesSBCS

{⌈2÷˜≠','⊸≠⊸/{𝕩/˜¬∨⟜»×{𝕨+𝕩×1⌈|𝕨}`-˝"<>"=⌜𝕩}𝕩/˜¬∨⟜»'!'=𝕩}

Run online!

-10 bytes from ovs.

Individually removes each main pattern (!, <>, ,) and checks length. Then divide that by 2 and take ceiling.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ (𝕨=0)+|𝕨 can be shortened to 1⌈|𝕨. And ('<'⊸=-'>'⊸=)𝕩 -> -˝"<>"=⌜𝕩. \$\endgroup\$
    – ovs
    Dec 11 '21 at 12:44
  • \$\begingroup\$ This is actually 56 bytes. Javascript's String.length counts some characters such as 𝕩 and 𝕨 as 2 chars. You can fix that in the userscript by replacing fun.length with Array.from(fun).length. \$\endgroup\$
    – ovs
    Dec 15 '21 at 10:02
  • \$\begingroup\$ oh, i see what's happening \$\endgroup\$
    – Razetime
    Dec 15 '21 at 10:20
  • \$\begingroup\$ @ovs update has been pushed \$\endgroup\$
    – Razetime
    Dec 15 '21 at 10:23
2
\$\begingroup\$

Pari/GP, 78 bytes

s->a=b=0;#[1|d<-Vec(s),if(a,a=0,d=="!",!a=1,b,d==">"&&b=0,d=="<",!b=1,d=="{")]

Try it online!

When your language doesn't have regexp or any string pattern matching built-in...

\$\endgroup\$
1
\$\begingroup\$

Python3, 156 bytes:

f=lambda x,g=0,c=0,i=0:c if not x else f(x[1:],(g:=(x[0]=='<'or(x[0]!='>'and g))),c+(not g and x[0]=='}' and not i),x[0]=='!'or(i and x[0]not in [",","}"]))

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Python 3, 54 bytes

lambda x:re.sub('<(!?.)*?>','',x).count('{')
import re

Try it online!

Port of my JS answer. Go read that, it's almost the same thing.

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 17 bytes

S'!ìõ:DŒ€…<ÿ>K¤¢

Despite 05AB1E's lack of regex, it turned out surprisingly short. :)

Try it online or verify all test cases.

Explanation:

          # Remove all "!" and the character after it:
S         #  Split the (implicit) input-string to a list of characters
 '!š     '#  Prepend a "!" in front of this list
    ¬     #  Push the first item (without popping), which is the "!"
     ì    #  Prepend this "!" in front of each character
      K   #  Remove all those 2-char strings from the (implicit) input-string
          #  (the `š¬` is necessary to first remove all "!!")
          # Remove all "<...>" garbage groups:
D         #  Duplicate the string
 Π       #  Pop the copy, and push all its substrings
  €       #  Map each substring to:
   …<ÿ>   #  Prepend a "<" and append a ">"
       K  #  Remove all those from the string as well
          # Count how many groups are left:
¤         #  Push the last character (without popping), which is "}"
 ¢        #  Count how many "}" are in the string
          # (after which the result is output implicitly)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.