20
\$\begingroup\$

Say I have a ragged list, like:

[
  [1, 2],
  [3, 
    [4, 5]
  ]
]

And I want to iterate over each item and delete it one-by-one. However, I don't know the structure of the list.

So, I have to iterate over the list, with the following algorithm:

  • Look at the first item of the list.
  • If it's a list, concatenate it to the start of the rest of the list.
  • Else, delete it.

For example, with the above example [[1, 2], [3, [4, 5]]]:

  • [1, 2] is a list. Concatenate it - [1, 2, [3, [4, 5]]]
  • 1 is a number. Delete it - [2, [3, [4, 5]]]
  • 2 is a number. Delete it - [[3, [4, 5]]]
  • [3, [4, 5]] is a list. Concatenate it - [3, [4, 5]]
  • 3 is a number. Delete it - [[4, 5]]
  • [4, 5] is a list. Concatenate it - [4, 5]
  • 4 is a number. Delete it - [5]
  • 5 is a number. Delete it - []

There are no more items left, so our work is done.

Your challenge is to compute the sizes of the lists resulting from applying this. For example, with the above, the list starts with length 2. It then goes to lengths 3, 2, 1, 2, 1, 2, 1, 0.

Standard rules apply - that is, you may take a list \$l\$ and generate all terms, or take a list \$l\$ and a number \$n\$ and calculate the nth or first n terms. Your results may or may not contain the length of the initial list at the start, and the 0 at the end, and you may take \$n\$ 0-indexed or 1-indexed.

Since only the shape of \$l\$ matters, you may take it filled with any consistent value instead of arbitrary integers.

\$l\$ may contain empty lists. In this case, it's concatenated as normal and the length decreases by 1.

This is , shortest wins!

Testcases

These include the leading length but not the trailing 0. Reference implementation

[[1, 2], [3, [4, 5]]] -> [2, 3, 2, 1, 2, 1, 2, 1]
[[6, 3, [1, 3, 4]], 4, [2, 3, 9, [5, 6]]] -> [3, 5, 4, 3, 5, 4, 3, 2, 1, 4, 3, 2, 1, 2, 1]
[3, 4, 5] -> [3, 2, 1]
[[[[[[[[1]]]]]]]] -> [1, 1, 1, 1, 1, 1, 1, 1]
[] -> []
[1, [], 1] -> [3, 2, 1]
[[],[[[]]],[]] -> [3, 2, 2, 2, 1]
\$\endgroup\$
4
  • \$\begingroup\$ I assume the consistent value can't itself be the empty list? \$\endgroup\$ Jun 14 at 6:53
  • 2
    \$\begingroup\$ @UnrelatedString Yes, it can't \$\endgroup\$
    – emanresu A
    Jun 14 at 6:57
  • \$\begingroup\$ What is the "sizes of the lists resulting from applying this" \$\endgroup\$ Jun 14 at 7:09
  • 2
    \$\begingroup\$ Suggested test case: [[],[[[]]],[]] -> [3, 2, 2, 2, 1] \$\endgroup\$ Jun 14 at 7:19

20 Answers 20

6
\$\begingroup\$

R, 62 61 bytes

Edit: -1 byte thanks to pajonk

f=\(l)if(h<-length(l))c(h,f(c(if(is.list(g<-el(l)))g,l[-1])))

Attempt This Online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ l[[1]] -> el(l) for -1 byte \$\endgroup\$
    – pajonk
    Jun 14 at 9:55
5
\$\begingroup\$

APL (Dyalog Unicode), 27 25 bytes

Anonymous prefix lambda.

{×⎕←≢⍵:∇((0≠≡⊃⍵)/⊃⍵),1↓⍵}

Try it online!

{} "dfn"; argument is :

≢⍵ tally the argument

⎕← print that

× signum of that

: if 1 (i.e. there's content):

  1↓⍵ drop the first element of the argument

  (), prepend:

   ⊃⍵ the first element of the argument

   ()/ replicated by (i.e. if the following holds true):

    ⊃⍵ the first element of the argument

    0≠≡ is its depth different from zero? (i.e. a list)

   recurse

\$\endgroup\$
5
\$\begingroup\$

Python 2, 44 bytes

def f(x,*r):print-~len(r);x>{}<f(*x+r);f(*r)

Attempt This Online!

Prints to STDOUT; terminates with an error.

Whython, 37 bytes

-7 bytes thanks to @ovs

def f(x,*r):print(len(r)+1);f(*x+r?r)

Attempt This Online!

Despite being Whython, this still also terminates with an error.

\$\endgroup\$
2
  • \$\begingroup\$ I think the Whython version can be shortened with f(*x+r)?f(*r)?1 -> f(*x+r?r) \$\endgroup\$
    – ovs
    Jun 14 at 7:53
  • \$\begingroup\$ @ovs Yep, you're right, although it now terminates with an error all the time, rather than just for the input (). \$\endgroup\$
    – pxeger
    Jun 14 at 8:21
5
\$\begingroup\$

JavaScript (Node.js),  55 53  52 bytes

Saved 2 bytes thanks to @pfg
Saved 1 more byte thanks to @tsh and @pfg

f=a=>[n=a.length,...n?f(a.shift().concat?.(a)??a):a]

Attempt This Online!

Commented

f = a =>           // f is a recursive function taking the input list a[]
[                  // build the output:
  n = a.length,    //   append the length of a[] and save it in n
  ...n ?           //   if a[] is not empty:
    f(             //     do a recursive call:
      a.shift()    //       extract the leading entry and attempt to
      .concat?.(a) //       concatenate it with the remaining entries
      ??a          //       if it fails, just append a[] (the leading entry
                   //       was not an array)
    )              //     end of recursive call
  :                //   else:
    a              //     stop the recursion and return a[] (which is empty)
]                  // end of output
\$\endgroup\$
5
  • 2
    \$\begingroup\$ Saves two bytes: s(m.at?[...m,...r]:r)s(m.concat?.(r)??r) \$\endgroup\$
    – pfg
    Jun 14 at 19:20
  • 1
    \$\begingroup\$ This is also 53 bytes, sadly: f=a=>a[0]?[a.length,...f(a.shift().concat?.(a)??a)]:a \$\endgroup\$
    – tsh
    Jun 15 at 2:47
  • 1
    \$\begingroup\$ 52 bytes following from @tsh's code: f=a=>[m=a.length,...m?f(a.shift().concat?.(a)??a):a] \$\endgroup\$
    – pfg
    Jun 15 at 6:00
  • \$\begingroup\$ @pfg I can't decide whether this syntax is elegant or ugly. :-p Nice golf anyway! \$\endgroup\$
    – Arnauld
    Jun 15 at 9:44
  • 1
    \$\begingroup\$ I believe that ?. followed by ?? could be a very common pattern for golfing in JavaScript. \$\endgroup\$
    – tsh
    Jun 16 at 2:06
4
\$\begingroup\$

05AB1E, 10 bytes

ΔDg,ćDi\ëì

A byte is saved by taking the input filled with 1s instead of positive integers.
Outputs the lengths on separated newlines to STDOUT, including a trailing 0.

Try it online or verify all test cases.

Explanation:

Δ      # Loop until the result no longer changes (e.g. until the list is empty):
 D     #  Duplicate the current list
  g    #  Pop and push the length
   ,   #  Pop and output this length with trailing newline to STDOUT
 ć     #  Extract head; pop and push remainder-list and first item separately
  D    #  Duplicate this extracted head
   i   #  If it's a 1:
    \  #   Discard it from the stack
   ë   #  Else (it's a list instead)
    ì  #   Prepend-merge it to the remainder-list
\$\endgroup\$
3
\$\begingroup\$

Stax, 15 bytes

Ö┬☻╪<æ·ë97╞φº♠B

Run and debug it

Stax, 16 bytes

ü╜←Φ■Yxbo╟ⁿ▀í▼ε~

Run and debug it

a generator.

\$\endgroup\$
3
\$\begingroup\$

Charcoal, (16) 21 bytes

Wθ«⟦ILθ⟧≔⁺∨×⁰§θ⁰υΦθλθ

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

Wθ«

Repeat until the input list is empty.

⟦ILθ⟧

Output its length on its own line.

≔⁺∨×⁰§θ⁰υΦθλθ

Add the tail of the list to the first element.

  • This would be three bytes shorter if the list was to be iteratively deleted from the end rather than the start.
  • This would be two bytes shorter if Charcoal's vectorising Add worked properly, but unfortunately it only vectorises to depth 1. (Other operators, such as BitwiseAnd, do vectorise correctly, so I'm assuming this is an oversight.)
  • This could be two bytes shorter if the input integers were all zero.
  • This could be one byte shorter by outputting the last length instead of the first.
\$\endgroup\$
2
  • 1
    \$\begingroup\$ "This could be two bytes shorter if the input integers were all zero." This is allowed in the challenge rules: "Since only the shape of \$l\$ matters, you may take it filled with any consistent value instead of arbitrary integers." \$\endgroup\$ Jun 14 at 7:31
  • 1
    \$\begingroup\$ "This could be one byte shorter by outputting the last length instead of the first". I'm not 100% sure what you mean by this, but it might be allowed in the challenge rules. ("Your results may or may not contain the length of the initial list at the start, and the 0 at the end") \$\endgroup\$
    – pxeger
    Jun 14 at 7:40
3
\$\begingroup\$

Wolfram Language (Mathematica), 34 bytes

Print[i+=Length@#-1]#0/@#&[i=1;#]&

Try it online!

Prints the lengths. Includes a trailing 0.

Print[i+=Length@#-1]#0/@#&[i=1;#]&
                          [i=1;#]   initialize i=1 before run
                    #0/@#           in depth-first, prefix order:
      i+=Length@#-1                   add length-1 to i (atoms have length 0)
Print[             ]                  print i
\$\endgroup\$
3
\$\begingroup\$

K (ngn/k), 24 bytes

#'{$[t~*t:*x;!0;t],1_x}\

Try it online!

Output includes the length of the initial list and a 0 at the end.

  • {...}\ set up a scan-converge, seeded with the (implicit) input and run until two successive iterations return the same result
    • $[t~*t:*x;!0;t] using $[c;t;f] cond, check if the first item is a list or an atom. if it is an atom, return an empty list (!0); if it is a list, return the first element of that list
    • ,1_x append the remainder of the list (dropping the first item)
  • #' return the number of items in each iteration
\$\endgroup\$
2
\$\begingroup\$

Jelly, 11 bytes

OḢ;$Ḋ⁼¡µƬẈṖ

A monadic Link that accepts a ragged list of integers and yields the lengths as a list, including both the initial length and a trailing 0.

Try it online! Or see the test-suite.

How?

OḢ;$Ḋ⁼¡µƬẈṖ - Link: ragged list of positive integers, L
        Ƭ   - collect input, X (initially L), while distinct, applying:
       µ    -   this monadic chain - f(X):
O           -     ordinal value (vectorises) -- only here to get us a copy of X
                                                so that we don't mutate it with Ḣ
   $        -     last two links as a monad - f(Y=that):
 Ḣ          -       head Y (alters Y, yields the first element or 0 when given [])
  ;         -       concatenate that with (the altered Y)
      ¡     -     if...
     ⁼      -     ...condition: that equals X? (head of X was an integer)
    Ḋ       -     ...then: dequeue
         Ẉ  - length of each
          Ṗ - pop the last length (removes the trailing 1, the length of 0)

Also 11 with no and, therefore, no O: 1ị;ḊḊ⁼¡µƬẈṖ

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

JavaScript (ES5),  84  80 bytes

Saved 4 bytes thanks to @tsh

function(a){for(r=[];m=a.shift(r.push(a.length));)a=m[0]?m.concat(a):a;return r}

Try it online!

Formatted and renamed:

function(array){
    result = [];
    while(
        result.push(array.length), 
        current = array.shift()
    ) {
        if(current !== +current) { // if current is not a number
            array = current.concat(array);
        }
    }
    return result;
}
\$\endgroup\$
1
  • \$\begingroup\$ function(a){for(r=[];m=a.shift(r.push(a.length));)a=m[0]?m.concat(a):a;return r} \$\endgroup\$
    – tsh
    Jun 15 at 1:59
1
\$\begingroup\$

Factor, 57 bytes

[ [ dup length . unclip [ prepend ] when* ] until-empty ]

Try it online!

Input consists of ragged sequences of f — Factor's canonical false value — as this saves about 20 bytes over integers.

  • [ ... ] until-empty Call [ ... ] on the input until it's empty.
  • dup length . Print the current length of the input non-destructively.
  • unclip Remove the first element from the sequence and place it on top of the data stack.
  • [ prepend ] when* when* is like when except it drops its input value if it's false, but retains its input if it's true (which is any non-false value in Factor). So, prepend it to the input if it's a sequence, or drop it if it's f.
\$\endgroup\$
1
\$\begingroup\$

MathGolf, 15 (non-competing†) bytes

{├_nn¡¿\;+ho}▲;

† The program above doesn't compile due to a bug in MathGolf with (do-)while loops using blocks above 8 characters. {...} is supposed to be a block for when ... contains more than 8 characters, but instead the { behaves as a for-each.

We can remove the {} and trailing ; so the do-while works on all preceding characters, so we can verify the test cases. Unfortunately, all test cases will then output an additional trailing empty list [].
Both programs also fail with an error for input [].

Outputs each length to STDOUT, without leading length and with trailing 0.

├_nn¡¿\;+ho▲: Try it online.

Explanation:

{           }▲  # Do-while true with pop:
 ├              #  Extract and push the left item of the list
                #  (this is where the `[]` test case errors)
  _             #  Duplicate it
   n            #  If it's a list: join it with newline delimiter to a string
                #  If it's an integer: push a newline "\n" character
    n¡          #  Check that this string is NOT equal to "\n"
      ¿         #  If it's indeed not "\n" (thus it's a list)
       \        #   Swap the top two values
      ¿         #  Else (it's an integer):
        ;       #   Discard it from the stack
         +      #  If it's a list: merge the top two lists together
                #  If it's an integer: add it to each inner-most value
          h     #  Push the length (without popping the list)
           o    #  Output it with trailing newline (without popping)
             ▲  #  Once the length is 0, the do-while stops
              ; # After the do-while: discard the empty list (since MathGolf
                # implicitly outputs the entire stack at the end of a program)
\$\endgroup\$
1
\$\begingroup\$

C (gcc), 266 bytes

#define S *w++=*r++
#define B b+=*r==91?1:-(*r==93)
f(r,b,w)char*r,*w;{w=++r;if(*++r==93)r++,r+=*r?*r==44:-1;else{if(*r!=44)for(b=1;b;B)S;r++;}for(;*r;)S;*w=0;}i;main(b,v,r)char**v,*r;{for(v++;*(*v+2);printf("%d ",i),f(*v))for(b=0,r=*v,i=1;*++r;B)(!b&&*r==44)&&i++;}

Try it online!

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

Retina 0.8.2, 82 bytes

0
[]
+`..(],?|(((\[)|(?<-4>])|,)+)])(.*)$
$&¶[$2$5
.(.((\[)|(?<-3>])|,)*].)*.?
$#1

Try it online! Outputs both leading and trailing counts and takes 0 as the consistent value (since [] is disallowed), but link is to test suite that replaces all non-negative integers with zero and deletes spaces for convenience. Explanation:

0
[]

Replace 0s with empty lists.

+`

Repeat until the last line is an empty list.

..(],?|(((\[)|(?<-4>])|,)+)])(.*)$

On the last line, match a list containing either an empty list as its first or only element, or otherwise the contents of the list at the first element.

$&¶[$2$5

Keep the original list to count its elements later and create a new list obtained by prepending the contents (if any) to the rest of the list.

.(.((\[)|(?<-3>])|,)*].)*.?
$#1

Count the number of elements of each list.

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

BQN, 27 bytes

{𝕩≠⊸∾(𝕊=∘⊑◶⟨⟩‿⊑∾1⊸↓)⍟(×≠)𝕩}

Try it here!

Explanation

  • 𝕩≠⊸∾... append input length to...
  • (...)⍟(×≠)𝕩 if input is nonempty...
  • ...∾1⊸↓ append tail to...
  • =∘⊑◶⟨⟩‿⊑ head if head is rank 1 (i.e. list), otherwise empty list
  • 𝕊 recurse
\$\endgroup\$
1
\$\begingroup\$

Brev, 85 bytes

(fn(descend(x)(cons(length x)(desc(if(pair?(car x))(append(car x)(cdr x))(cdr x))))))

Example:

((fn (descend (x)
              (cons
               (length x)
               (desc
                (if (pair? (car x))
                    (append (car x) (cdr x))
                    (cdr x))))))
 '((1 2) (3 (4 5))))

fn makes a function with an argument x. descend checks if it's null, if it is, return it. Otherwise, cons its length onto a recursive call of descend, where the car of x has been spliced if it's a pair? or dropped if it's an atom. For the test example, it returns (2 3 2 1 2 1 2 1)

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

Rust, 19 194 185 174 bytes

Even defining a type for a ragged list is bytes intensive in rust. Still shorter than C :)

enum K{N,Y(Vec<K>)}fn f(k:&K,n:usize)->Vec<usize>{if let K::Y(b)=k{[n+b.len()].into_iter().chain((1..).zip(b).map(|(i,z)|f(z,b.len()+n-i)).flatten()).collect()}else{vec![n]}}```

Sequences will have a extra 0 at the end. Verify all test cases

-9 bytes by using Vec instead of array slices

-11 bytes by replacing enumerate with zip and match with if let

\$\endgroup\$
1
  • \$\begingroup\$ If you can find a way to not explicitly refer to the type, you don't need it by consensus. \$\endgroup\$
    – emanresu A
    Jun 22 at 9:25
0
\$\begingroup\$

Burlesque, 32 bytes

saj{g_Jto'B~[{j_+}qvvIEsaj}qL[w!

Try it online!

saj      # Get initial length
{
 g_      # Pop head from list
 J       # Dup
 to'B~[  # Is Block
 {j_+}   # Prepend elements
 qvv     # Drop
 IE      # If (isBlock) else
 saj     # Length
}
qL[w!    # While non-empty
\$\endgroup\$
0
\$\begingroup\$

Pyth, 9 bytes

#l=+|hQYt

Try it online!

Accepts a ragged list filled with 0s.

Excludes the length of the initial list, and includes the 0 for the final list.

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