AoCG2021 Day 11: Garbageful streams

Question

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 code-golf rules apply. The shortest code in bytes wins.

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

Ruby, 39 36 33 bytes

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

Try it online!

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

Answer 5

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"]

Answer 6

Charcoal, 39 bytes

≔⁰η≔¹ζ≔⁰εＦＳ«¿ε≔⁰ε≡ι!≔¹ε<≔⁰ζ>≔¹ζ}≧⁺ζη»Ｉη

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.

ＦＳ«

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.

»Ｉη

Output the final number of groups.

Answer 7

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

Answer 8

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!

Answer 9

Wolfram Language (Mathematica), 68 bytes

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

Try it online!

Answer 10

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

Answer 11

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)

Answer 12

BQN, 56 bytes^SBCS

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

Run online!

-10 bytes from ovs.

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

Answer 13

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

Answer 14

05AB1E, 17 16 bytes

'!š¬ìKDŒ€…<ÿ>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:
'!š     '#  Split the (implicit) input-string to a list of characters, and prepend a "!"
   ¬     #  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)

Answer 15

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!

Answer 16

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.

Answer 17

Perl 5 -p, 26 bytes

s/!.//g;s/<.*?>//g;$_=y;{;

Try it online!

Answer 18

SM83, 24 bytes

Input in hl as null-terminated string. Output in bc.

2A B7 C8 FE 7B 20 01 03
FE 3C 20 F4 2A FE 3E 28
EF FE 21 20 F7 23 18 F4

f:
    ld a,(hl+)      ;; 2A       ;; load char
    or a            ;; B7       ;; test for 0
    ret z           ;; C8       ;; if so, at end; return
    cp '{'          ;; FE 7B
    jr nz,x         ;; 20 01    ;; if not '{'
    inc bc          ;; 03       ;; increment result
x:
    cp '<'          ;; FE 3C    ;; if not '<'
    jr nz,f         ;; 20 F4    ;; loop
l:                              ;; degarbaging:
    ld a,(hl+)      ;; 2A       ;; load char
    cp '>'          ;; FE 3E    ;; if '>'
    jr z,f          ;; 28 EF    ;; go back to start
    cp '!'          ;; FE 21    ;; if not '!'
    jr nz,l         ;; 20 F7    ;; continue degarbaging
    inc hl          ;; 23       ;; skip char
    jr l            ;; 18 F4    ;; and continue degarbaging