Find the “unwrapped size” of a list

Let's define the "unwrapped size" function u of a nested list l (containing only lists) by the following rules:

• If l is empty, then u(l) is 1.
• If l is non-empty, u(l) is equal to the sum of the unwrapped sizes of every element in l, plus one.

Your task is to write a program (or function) that takes a list as input and outputs (or returns) the unwrapped size of the list.

Test Cases:

[]                                           ->  1
[[[]],[]]                                    ->  4
[[[]],[[[[]],[]]],[[[]],[[[[]],[[],[[]]]]]]] -> 19
[[[[]]]]                                     ->  4


This is , so the shortest program (in bytes) wins.

• Can input be taken as a string, i.e. with enclosing quote marks? Can we use () instead of []? – Luis Mendo Nov 10 '16 at 15:49
• can we take input in this format [[[]][]] instead of this [[[]],[]] in your second example? – Mukul Kumar Nov 10 '16 at 16:50
• What is the size of ["This is some text [with square brackets in] ...[& maybe more than one pair]"]? – Jonathan Allan Nov 10 '16 at 16:54
• Possible duplicate of Find the occurrences of a character in an input string – James Nov 11 '16 at 4:40
• @DrMcMoylex I disagree. While counting the number of ] does seem to be the shortest solution in many languages, there are also a lot of answers that actually solve this challenge via list manipulation, and at least in esolangs counting the occurrences of a fixed character is also quite different from counting the occurrences of an input character. – Martin Ender Nov 11 '16 at 8:19

Retina, 1 byte

]


Try it online! (The first line enables a linefeed-separated test suite.)

By default, Retina counts the number of matches of the given regex in the input. The unwrapped size is simply equal to the number of [] pairs in the input and therefore to the number of ].

• Thre right tool for the job! – Cyoce Nov 11 '16 at 8:21
• @MartinEnder do you ever add new functions to your language in order to save bytes in a codegolf question? – lois6b Nov 11 '16 at 9:45
• @lois6b not retroactively, but I do occasionally improve the language to make it more powerful for future uses. That said, this answer would have worked in the very first version of Retina from back when it was simply a way to run a single regex (/substitution) against the input without syntactic overhead. – Martin Ender Nov 11 '16 at 10:05

Mathematica, 9 bytes

LeafCount


Turns out there's a built-in for that...

Note that this wouldn't work if the lists actually contained non-list elements. What LeafCount really does is count the number of atomic subexpressions. For input {{}, {{}}}, the expression actually reads:

List[List[], List[List[]]]


Here the atomic subexpressions are actually the heads List.

• Mathematica has a built-in for everything... – kirbyfan64sos Nov 10 '16 at 22:31
• @Challenger5 Oy, plagiarism. :P – Martin Ender Nov 14 '16 at 21:43

Brainfuck, 7161 59 bytes

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


Takes input from STDIN in the format given in the question, and outputs the character whose ASCII code is the list's "unwrapped size."

I'm still a complete amateur at Brainfuck, so there are most likely many optimizations that can still be made.

Try it online!

Ungolfed:

read input to tape
>>+[>,]<
current tape: (0 0 1 a b *c)
where abc represents input and * is IP

now we loop over each character (from the end)
this loops assumes we are starting on the (current) last char
and it zeroes the entire string by the time it finishes
[

subtract 91 from this character
technically we only subtract 85 here and correct the answer
with the 6 minus signs below
>-[<->---]
current tape: (0 0 1 a b cminus91 *0)

invert the result and put that in the next cell
+<------[->[-]<]>
current tape: (0 0 1 a b 0 *c==91)

move that result back to the original cell
[-<+>]<
current tape: (0 0 1 a b *c==91)

if the result is true we found a brace
increment the very first cell if so
[-<[<]<+>>[>]]<
current tape: (count 0 1 a *b)

]
current tape: (count *0)

<.


JavaScript (ES6), 29 27 bytes

f=([x,...a])=>x?f(x)+f(a):1


i love it when a recursion turns out this cleanly. This is basically a depth-first search of the input, adding 1 whenever the end of an array is reached.

If an empty array were falsy in JS, this could be 24 bytes:

f=a=>a?f(a.pop())+f(a):1


But alas, it's not. Other attempts:

f=a=>a.reduce((n,x)=>n+f(x),1) // Works, but 3 bytes longer
f=a=>a.map(x=>n+=f(x),n=1)&&n  // Works, but 2 bytes longer
f=a=>(x=a.pop())?f(x)+f(a):1   // Works, but 1 byte longer
f=a=>a[0]?f(a.pop())+f(a):1    // Works, but same byte count
f=a=>a+a?f(a.pop())+f(a):1     // Doesn't work on any array containing 1 sub-array
f=a=>a-1?f(a.pop())+f(a):1     // Same

• Would f=a=>a[0]?f(a.pop())+f(a):1 work? (Same byte count though.) – Neil Nov 10 '16 at 16:14
• @Neil Yes, that's one of the solutions I've already tried. I don't think it's possible to get any shorter... – ETHproductions Nov 10 '16 at 16:16
• (By the way, I would have gone for the extravagant f=a=>a.reduce((n,a)=>n+f(a),1). Now, f=(n,a)=>n+a.reduce(f,1) is only 24 bytes, but sadly the parameters are in the wrong order.) – Neil Nov 10 '16 at 16:19
• @Neil I actually did that first, except shortening it by 1 byte: f=a=>a.map(a=>n+=f(a),n=1)&&n – ETHproductions Nov 10 '16 at 16:23
• Ah, sorry, I hadn't thought to browse the edit history. – Neil Nov 10 '16 at 16:49

Perl, 98 7 + 1 = 8 bytes

Requires the -p flag

$_=y;[;  Thanks to @Dada for two byte saves (I'm loving this semicolon exploit btw) • -p to save 1 byte ;) – Dada Nov 10 '16 at 15:05 • You can use y;[; to save one more byte – Dada Nov 10 '16 at 17:57 CJam, 7 5 bytes Thanks to Peter Taylor for removing 2 bytes! (e= instead of f=:+) r'[e=  Try it online! r e# Read input '[ e# Push open bracket char e= e# Count occurrences. Implicit display  05AB1E, 4 bytes I'[¢ I Get input as a string '[¢ Count the opening square brackets and implicitly print them  Try it online! I think it can be golfed more but that 'I' is mandatory, otherwise the input is considered an actual array instead of a string • "[[[]],[[[[]],[]]],[[[]],[[[[]],[[],[[]]]]]]]" in the input removes that I requirement, though I don't know if that is allowed. – Magic Octopus Urn Nov 10 '16 at 15:49 • @carusocomputing: It's not currently allowed, but that could change (I see Luis asking the OP that same question) – Emigna Nov 10 '16 at 15:54 • Dang, 14 hours before me. – Oliver Ni Nov 11 '16 at 5:30 Labyrinth, 8 bytes &- #,(/!  Try it online! Explanation This counts the opening brackets via a bit of bitwise magic. If we consider the results of the character codes of the bitwise AND of [, , and ] with 2, we get: [ , ] 2 0 0  So if we just sum up the result of this operation for each character, we get twice the value we want. As for the code itself, the 2x2 block at the beginning is a small loop. On the first iteration &- don't really do anything except that they put an explicit zero on top of the implicit ones at the bottom of the stack. This will be the running total (and it will actually be negative to save a byte later). Then the loop goes as follows: , Read character. At EOF this gives -1 which causes the instruction pointer to leave the loop. Otherwise, the loop continues. # Push the stack depth, 2. & Bitwise AND. - Subtract from running total.  Once we leave the loop, the following linear bit is executed: ( Decrement to turn the -1 into a -2. / Divide negative running total by -2 to get desired result. ! Print.  The IP then hits a dead and turns around. When it tries to executed / again, the program terminates due to the attempted division by zero. Python 3 2, 36 23 bytes lambda x:x.count("[")  I noticed that u(l) is equal to the number of [ in the string representation of l, so this program tries to do that. It could probably be golfed further by finding another way to do this, though... • 23 bytes: lambda x:x.count("[") – acrolith Nov 10 '16 at 15:20 Python, 26 bytes f=lambda a:sum(map(f,a))+1  Simple recursive formula. C#, 46 41 bytes int u(string l){return l.Count(c=>c=='[');}  l is the string of nested list. Test it here. • Use the 4 spaces (before the code) for formatting it into a code block – user41805 Nov 10 '16 at 19:23 • @KritixiLithos oops, I forgot to correctly do that. Thanks for pointing it out :) – Ave Nov 10 '16 at 19:24 • And this has to be a program or a function, this is neither. – user41805 Nov 10 '16 at 19:27 • @KritixiLithos oops, thanks for pointing it out, just fixed it. – Ave Nov 10 '16 at 19:31 • You can drop the curly braces and return by using an expression bodied function. Also char implicitly casts to int so you can use 91 instead of '[': int u(string l)=>l.Count(c=>c==91); Further, you could drop the function signature and use a lambda method: l=>l.Count(c=>c==91);. – milk Nov 10 '16 at 19:55 Jelly, 4 bytes ß€S‘  Doesn't use string manipulation. Try it online! or verify all test cases. How it works ß€S‘ Main link. Argument: A (array) ß€ Map the main link over A. S Sum. For empty arrays, this yields zero. ‘ Increment.  Ruby, 13 (+1) bytes p$_.count ?[


Called with -n argument:

ruby -ne 'p $_.count ?['  EDIT: Changed to actually print out the answer • This doesn't seem to print anything. (Unless this is a REPL answer, in which case the language should be specified as Ruby REPL.) – Martin Ender Nov 10 '16 at 17:20 • @Martin Ender♦ The specification allowed for returning the value instead of printing it. – Lee W Nov 10 '16 at 19:18 • That refers to function submissions. E.g. ->s{s.count ?[} would be a valid submission. – Martin Ender Nov 10 '16 at 19:31 • Is that a general rule? – Lee W Nov 10 '16 at 19:44 • See this post for admissible I/O methods. – Martin Ender Nov 10 '16 at 19:49 Regex, 1 byte ]  Try it online! • I'm not sure Regex is a programming language, but even if it is, there's already an identical Retina answer. – Dennis Nov 12 '16 at 15:24 Brain-Flak, 63, 61 bytes {({}[(((()()()){}){}()){({}[()])}{}]){{}(<>{}())(<>)}{}}<>  Try it online! 58 bytes of code, and +3 for the -a flag enabling ASCII input. Readable version/explanation: #While non-empty: { #subtract ({}[ #91 (((()()()){}){}()){({}[()])}{} ]) #if non-zero { # Remove the difference {} #Increment the counter on the other stack (<>{}()) #Push a zero onto the main stack (<>) } #pop the left-over zero {} #endwhile } #Move back to the stack with the counter, implicitly display <>  Befunge, 2218 16 bytes ~:0#@#.!#$_3%!+


TryItOnline!

Edit: Thanks to Martin Ender for shaving off 4 bytes!

Edit2: Credit to David Holderness for optimizing out two more

///, 13 bytes

/[/0//]///,//


Output in unary.

Try it online!

Explanation:

/[/0/          Replace every [ with 0
/]///,//  Remove every ] and ,

• How do you pronounce /// ? – roblogic Dec 16 '16 at 0:41
• @ropata Slashes – acrolith Dec 16 '16 at 12:21

PHP, 35 bytes

<?=preg_match_all('/\[/',$argv[1]);  preg_match_all finds all of the matching instances of the regular expression and returns a number, which is why the short echo tags are needed. Like most answers, it counts the number of [ in the input and outputs that number • If you use ] instead of [, you won't have to escape it. – Martin Ender Nov 10 '16 at 15:36 • count_chars()[91]; does much the same thing but is shorter. – user59178 Nov 10 '16 at 16:27 Racket 82 bytes (define n 0)(let p((l l))(if(null? l)(set! n(+ 1 n))(begin(p(car l))(p(cdr l)))))n  Ungolfed: (define (f l) (define n 0) (let loop ((l l)) (if (null? l) (set! n (add1 n)) (begin (loop (first l)) (loop (rest l))))) n)  Testing: (f '[]) (f '[[[]] []]) (f '[[[]] [[[[]] []]] [[[]] [[[[]] [[] [[]]]]]]]) (f '[[[[]]]])  Output: 1 4 19 4  V, 10 bytes ÓÛ ÒC0@"  Try it online! This contains some unprintable characters, here is the readable version: ÓÛ Ò<C-a>C0<esc>@"  <C-a> represents "ctrl-a" (ASCII 0x01) and <esc> represents the escape key (ASCII 0x1b). ÓÛ " Remove all '['s " Ò<C-a> " Replace what's left with '<C-a>' (the increment command) C " Delete this line 0<esc> " And replace it with a '0' @" " Run what we just deleted as V code (A bunch of increment commands  More fun, less golfy version: o0kòf]mjòd  Try it online! o0<esc> " Put a '0' on the line below us k " Move back up a line ò ò " Recursively: f] " Move to a right-bracket m " Add this location to our jumplist j " Move down a line <C-a> " Increment this number <C-o> " Move to the previous location d " Delete the bracket line " Implicitly display  Scala, 15 bytes s=>s.count(92<)  Ungolfed: s=>s.count(c=>92<c)  count counts how many elements satisfy a predicate, in this case 92<, which is the method < of 92. O, 15 bytes i~{1\{nJ+}d}J;J  Try it here! In the input, any commas must be either removed or replaced by spaces. Explanation i~{1\{nJ+}d}J;J i Read a line of input. ~ Evaluate it. { }J; Define a function and save it into the J variable. Currently, the input array is at the top of the stack. 1\ Push 1 and swap it with the input array. { }d For each element in the array... Because the array was popped by d, 1 is at the TOS. nJ+ Recurse and add the result to 1. J Initiate the function call. The result is printed implicitly.  If we're allowed to take work on a string: 10 bytes ie\']-e@-p  ><>, 2120 18 bytes 0i:0(90.;n?|3%0=+!  Edit: score 1 for goto statements! Edit 2: Apparently ><> differs from Befunge in that it allows non-zero IP offset after wrapping (in other words, by using a trampoline instruction, I can wrap to (1, 0) instead of (0, 0)). Interesting. TryItOnline! Brainfuck, 28 bytes , [ - [ - [ >+<- [->] ] >[>>] <<< ] , ] >.  Try it online. This counts the number of input characters divisible by 3, i.e. the number of ] characters. Alternate 34-byte solution counting [ characters directly and relying on 8-bit cells: , [ <-[>-<---] >------ [>-<[-]] >+<, ] >.  C, 48 46 Bytes Saved two bytes thanks to kirbyfan64sos i;f(char*v){for(i=0;*v;i+=*v++==91);return i;} i;f(char*v){for(i=0;*v;*v++^91?0:i++);return i;}  Test code main() { printf("%d\n", f("[]")); printf("%d\n", f("[[[]] []]")); printf("%d\n", f("[[[]] [[[[]] []]] [[[]] [[[[]] [[] [[]]]]]]]")); }  Test cases a.exe 1 4 19  • Change *v++^91?0:i++ to i+=*v==91 to save 3 bytes. – kirbyfan64sos Nov 10 '16 at 22:45 • @kirbyfan64sos Thanks! I still need to increment v but I can use i+=*v++==91 to save two bytes. – cleblanc Nov 11 '16 at 14:13 tinylisp repl, 39 bytes (d u(q((L)(i L(s(u(h L))(s 0(u(t L))))1  Defines a function u that can be called like (u (q ((())()) )) (for the second test case). Doing it in the repl saves 4 bytes due to auto-closed parentheses. Explanation (d u ) Define u as (q ) the following, unevaluated ( ) list (which acts as a function in tinylisp): (L) Given arglist of one element, L, return: (i L ) If L (is nonempty): (s(u(h L)) ) Call u on head of L and subtract (s 0 ) 0 minus (u(t L)) call u on tail of L 1 Else, 1  The x-(0-y) construct is necessary because tinylisp doesn't have a built-in addition function, only subtraction. Befunge-98, 121110 9 bytes ~3%!+2j@.  TryItOnline! Edit: Thanks to Martin Ender for shaving off a byte Haskell, 20 19 17 bytes f s=sum[1|']'<-s]  Try it online! Takes the list as string and puts a 1 in a list for each ], then sums up all the 1s. Pointfree version: (19 bytes) length.filter(>'[')  Assumes , [ ] are the only chars in the string. Filters the list to get all chars greater than [, which are all ] and returns the length. Usage: Prelude> length.filter(=='[')$"[[[]],[[[[]],[]]],[[[]],[[[[]],[[],[[]]]]]]]"
19


Bash + coreutils, 29 bytes

f()(echo \$1|tr -d -c [|wc -c)

• You can remove most of this and just do tr -d -c [|wc -c, which will by default read the list from standard input. – kirbyfan64sos Nov 10 '16 at 22:42

DASH, 14 bytes

(ss[len;!> ="]


Simply counts ]'s. Usage:

(ss[len;!> ="]"])"[[]]"


Bonus solution, 15 bytes

a\@+1sum ->#a#0


This one recursively counts from a real list. Usage:

(f\@+1sum ->#f#0)[[]]
`