Find the "unwrapped size" of a list

Question

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 code-golf, so the shortest program (in bytes) wins.

Answer 1

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

Answer 2

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.

Answer 3

Brainfuck, 71 61 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)

<.

Answer 4

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

Answer 5

Perl, 9 8 7 + 1 = 8 bytes

Requires the -p flag

$_=y;[;

Thanks to @Dada for two byte saves (I'm loving this semicolon exploit btw)

Answer 6

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

Answer 7

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

Answer 8

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

Answer 9

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.

Answer 10

Python, 26 bytes

f=lambda a:sum(map(f,a))+1

Simple recursive formula.

Answer 11

Ruby, 13 (+1) bytes

p $_.count ?[

Called with -n argument:

ruby -ne 'p $_.count ?['

EDIT: Changed to actually print out the answer

Answer 12

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

Answer 13

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.

Answer 14

C#, 46 41 bytes

int u(string l){return l.Count(c=>c=='[');}

l is the string of nested list. Test it here.

Answer 15

Befunge, 22 18 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

Answer 16

Regex, 1 byte

]

Try it online!

Answer 17

///, 13 bytes

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

Output in unary.

Try it online!

Explanation:

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

Answer 18

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

Answer 19

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

Answer 20

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

Answer 21

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]m`jò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

Answer 22

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:

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

Answer 23

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.

Answer 24

><>, 21 20 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!

Answer 25

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

Answer 26

Befunge-98, 12 11 10 9 bytes

~3%!+2j@.

TryItOnline!

Edit: Thanks to Martin Ender for shaving off a byte

Answer 27

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

Answer 28

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.

Answer 29

Clojure, 42 bytes

Does not leave much room for tweaking as the syntax is so limited. Basically just follows the definition.

(fn[i](if(empty? i)1(apply + 1(map f i))))

Answer 30

Bash + coreutils, 29 bytes

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

Answer 31

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

Answer 32

Java 7, 48 bytes

int c(String l){return l.split("\\[").length-1;}

If we aren't allowed to use a String as input, then we have the following instead (60 bytes - Try it here):

int c(java.util.List l){return(l+"").split("\\[").length-1;}

Ungolfed & test cases:

Try it here.

class M{
    static int c(String l){
        return l.split("\\[").length - 1;
    }

    public static void main(String[]a){
        System.out.println(c("[]"));
        System.out.println(c("[[[]],[]]"));
        System.out.println(c("[[[]],[[[[]],[]]],[[[]],[[[[]],[[],[[]]]]]]]"));
        System.out.println(c("[[[[]]]]"));
    }
}

Output:

1
4
19
4

Answer 33

Prolog (SWI), 43 bytes

u(L,N):-L=[H|T],u(H,A),u(T,B),N is A+B;N=1.

Defines a predicate u that takes a list as its first argument and unifies its second argument with the unwrapped size of that list. Verify all test cases on Ideone.

Explanation

First, L=[H|T] tries to unify L with a list of the structure "one item H, followed by the rest of the list T."

• If the list is nonempty, the unification succeeds. We then run u recursively on H and T, getting the results in A and B. Finally, we add these two and assign the result to N.
• If the unification fails, we have an empty list, in which case we need only unify N with 1.