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

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 7

Stax, 15 bytes

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

Run and debug it

Stax, 16 bytes

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

Run and debug it

a generator.

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

JavaScript (ES2019), 51 48 47 bytes

i=0;f=(v=[])=>[i+=v.length-!!i,...v.flatMap(f)]

Attempt This Online!

Input requires undefined as leaves. Output includes initial size and trailing 0.

I assume the output must be a flat array instead of allowing nested array. If nested array is acceptable then there is this 40-byte solution:

i=0;f=(v=[])=>[i+=v.length-!!i,v.map(f)]

Algorithm

Instead of implementing the specified process and constructing the intermediate arrays, this submission uses an analytical solution to calculate the output.

Notice that, with the process in the question, each item of the root array is completely deleted before moving on to the next item. Using the original example [[1,2],[3,[4,5]], the [1,2] subarray is fully deleted before [3,[4,5]] is touched. This means that while processing [1,2], the sizes of the intermediate arrays at each step is the same as those while processing [1,2] as a root, but plus 1 because we have to count [3,[4,5]]

[[1, 2], [3, [4, 5]]]
[1, 2, [3, [4, 5]]]   (size: 3)        |        [1,2]   (size: 2)
[2, [3, [4, 5]]]      (size: 2)        |        [2]     (size: 1)
[[3, [4, 5]]]         (size: 1)        |        []      (size: 0)

Take another example from the test cases

[[6, 3, [1, 3, 4]], 4, [2, 3, 9, [5, 6]]]
[6, 3, [1, 3, 4], 4, [2, 3, 9, [5, 6]]]   (size: 5)        |        [6, 3, [1, 3, 4]] (size: 3)
[3, [1, 3, 4], 4, [2, 3, 9, [5, 6]]]      (size: 4)        |        [3, [1, 3, 4]]    (size: 2)
[[1, 3, 4], 4, [2, 3, 9, [5, 6]]]         (size: 3)        |        [[1, 3, 4]]       (size: 1)
[1, 3, 4, 4, [2, 3, 9, [5, 6]]]           (size: 5)        |        [1, 3, 4]         (size: 3)
[3, 4, 4, [2, 3, 9, [5, 6]]]              (size: 4)        |        [3, 4]            (size: 2)
[4, 4, [2, 3, 9, [5, 6]]]                 (size: 3)        |        [4]               (size: 1)
[4, [2, 3, 9, [5, 6]]]                    (size: 2)        |        []                (size: 0)

The size difference is 2 here because there are 2 items after the item being processed ([6, 3, [1, 3, 4]]).

This shows that this problem can be solved with a recursive algorithm

f([1, 2]) = [2, 1, 0]
f([3, [4, 5]]) = [2, 1, 2, 1, 0]

                                [2, 1, 0][2, 1, 2, 1, 0]
                           + [2,       1,             0]
                           --------------------------------
f([[1, 2], [3, [4, 5]]]) =   [2, 3, 2, 1, 2, 1, 2, 1, 0]

More precisely, the output of processing an array consists of:

• The initial length of the array, then
• For each item, the result of processing that item, plus adding the number of items after it to each element.

Naive, readable implementation

function f(value) {
    if (value !== undefined) {
        return [
            value.length,
            ...value.flatMap((item, index) => f(item).map((n) => n + value.length - index - 1))
        ]
    }
    return [0]
}

Golfing

First, of course, is to apply basic golfing techniques

// 70 bytes
f=v=>v?[v.length,...v.flatMap((u,j)=>f(u).map($=>$+v.length-j-1))]:[0]

Then, since leaves are undefined, we can actually use default argument to treat leaves as [] and merge the two branches

// 69 bytes
f=(v=[])=>[v.length,...v.flatMap((u,j)=>f(u).map($=>$+v.length-j-1))]

Then, instead of mapping a second time to add the "base" value v.length-j-1, we can make f accept a second argument for a value to add to everything.

// 67 bytes
f=(v=[],i=0)=>[v.length+i,...v.flatMap((u,j)=>f(u,v.length+i-j-1))]

Next, we can pull i up to the global scope and mutate it instead of passing it around and using a lengthy expression to calculate the base

// 53 bytes
i=0;f=(v=[])=>[i+=v.length,...v.flatMap(u=>f(u,i--))]

Finally, we can move the i-- decrement into f so that, instead of decrementing at each flatMap iteration, we just decrement i at the start of f.

// 45 bytes
i=1;f=(v=[])=>[i+=v.length-1,...v.flatMap(f)]

BUT, this breaks because the global variable i is changed after calling f, which is forbiddened. Specifically, i is decremented by 1 for each root call to f. Before the change, i is decremented by 1 by one per child while looping in flatMap, but now i is decremented by 1 per call (i.e. per node), and the root is the only node that is not a child.

To counter this, we need to change the increment to "number of children" (instead of "number of children - 1") but only for the root node. This is doable by noticing that i is at its initial value only at the start of a root f call and after processing the last leaf. So we can initialize i to 0 and when we increment i, we increment by "number of children" if i is 0 but by "number of children - 1" otherwise.

// 47 bytes
i=0;f=(v=[])=>[i+=v.length-!!i,...v.flatMap(f)]

Answer 10

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 four 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. Edit: Ironically, Times also doesn't vectorise correctly, so I needed to replace it with BitwiseAnd to fix a bug.)
• Alternatively, this could be two bytes shorter if the input integers were all zero. (Not applicable when vectorising Add works properly.)
• This could be one byte shorter by outputting the last length instead of the first.

16 bytes using the newer version of Charcoal on ATO:

Ｗθ«≔⁺§θ⁰Φθλθ⟦ＩＬθ

Attempt This Online! Link is to verbose version of code. Outputs the last length instead of the first.

Answer 11

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 12

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 13

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 14

BQN, 26 bytes

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

Try it here!

-1 byte thanks to @DLosc!

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 15

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 16

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 17

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 18

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 19

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 20

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 21

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.

Answer 22

Vyxal, 7 bytes

ḣȮßJ)↔@

Try it Online! Takes 0 as the filler element, outputs both the leading length and the trailing 0.

    )↔  # Apply until no change, collecting intermediate results
ḣ       # Extract the first item
  ß     # If it's truthy (nonempty list)
 Ȯ J    # Concatenate it (otherwise leave the list beheaded)
      @ # Take the length of each intermediate results

Answer 23

APL (Dyalog Classic), 22 bytes

{⍴⍴⍵:∊(⍴,∇¨+⍴-⍳∘⍴)⍵⋄0}

Try it online!

I assume the output must be a flat array instead of allowing nested array. If nested array is acceptable then ∊ is not needed for -1 byte

Uses the same algorithm as my other submission, but pretty much ungolfed because tacit APL is that good

{⍴⍴⍵:∊(⍴⍵),(∇¨⍵)+(⍴⍵)-(⍳⍴⍵)⋄0}  With trains expanded
                                
 ⍴⍴⍵:                           If argument is array
           (∇¨⍵)                  recursive call with each element
                 +(⍴⍵)-(⍳⍴⍵)      add (length of argument - index)
                                    note that APL arrays are 1-based by default
      (⍴⍵),                       prepend length of argument
     ∊                            flatten
                           ⋄0   Else return 0

Answer 24

Pyth (arbitrary values), 15 bytes

lM.u+.x[.*hN[)t

Test suite

Takes a ragged list of arbitrary values (even accepts floats). Includes length of original list and final 0.

Explanation:

lM.u+.x[.*hN[)t   | Full code
lM.u+.x[.*hN[)tNQ | with implicit variables
------------------+----------------------------------------------------------------------------------------------------------------
  .u            Q | Collect N, starting with the input, with each succussive N defined by the following until a result is repeated:
    +         tN  |  Prepend to the tail of N:
       [.*hN      |   N if N is a list
     .x     [)    |   or the empty list if N is not a list
lM                | Convert each element to its length