Iteratively delete a list

Question

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 sequence 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 code-golf, 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]

Answer 1

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!

Answer 2

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

Answer 3

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.

Answer 4

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

Answer 5

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

Answer 6

Stax, 15 bytes

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

Run and debug it

Stax, 16 bytes

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

Run and debug it

a generator.

Answer 7

Charcoal, (16) 21 bytes

Ｗθ«⟦ＩＬθ⟧≔⁺∨×⁰§θ⁰υΦθλθ

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

Ｗθ«

Repeat until the input list is empty.

⟦ＩＬθ⟧

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.

Answer 8

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

Answer 9

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

Answer 10

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ị;ḊḊ⁼¡µƬẈṖ

Answer 11

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

Answer 12

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.

Answer 13

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)

Answer 14

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!

Answer 15

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.

Answer 16

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

Answer 17

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)

Answer 18

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

Answer 19

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

Answer 20

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.