Is it a properly tiered list?

Question

A ragged list is a (finite depth) list where each element is either a positive integer or a ragged list.

A ragged list is properly tiered if it contains either all positive integers or all properly tiered ragged lists.

For example [1,2,3,6] is properly tiered because it is a list of only positive integers. [[1,2],[[1]],[[6],[[]]]] is also properly tiered, because it has 3 elements which are all properly tiered lists themselves. Note that all the lists don't have to be the same depth.

The list [[1,2],[[6],4]] is not properly tiered because one of it's elements is a ragged list which contains a mixture of lists and positive integers.

Task

Take a ragged list via any natural format and determine if it is a properly tiered list. You should output one of two consistent values, the first if the input is a properly tiered list and the second if it is not.

This is code-golf so your goal is to minimize the size of your source code as measured in bytes.

Test cases

[] -> Yes
[1,2,3,6] -> Yes
[[1,2],[[1]],[[6],[[]]]] -> Yes
[[]] -> Yes
[1,[2]] -> No
[[1,2],[[6],4]] -> No
[[1,[2]],[[3],4]] -> No
[1,[]] -> No

Answer 1

JavaScript (Node.js), 39 bytes

-1 thanks to @emanresuA

Returns false for valid, true for invalid.

a=>/\d,\[|],\d/.test(JSON.stringify(a))

Attempt This Online!

Or 23 bytes if we simply take a string as input:

a=>/\d,\[|],\d/.test(a)

Attempt This Online!

---

JavaScript (Node.js), 41 bytes

Returns false for valid, true for invalid.

f=(a,q)=>a.some(b=>q-(q=!b.at)||!q&&f(b))

Attempt This Online!

Or:

f=(a,q)=>a.some(b=>q-(q=!b.at)|f(q?[]:b))

Attempt This Online!

Answer 2

Python, 61 40 39 35 32 bytes

f=lambda l:l*-1or[l.sort(key=f)]

Attempt This Online!

Errors if the list is not properly tiered, otherwise returns [].

---

-1 byte from @Mukundan314
-5 bytes from @loopy walt for various cleverness
-3 bytes from @Mukundan314

Answer 3

BQN, 17 15 bytes^SBCS

Thanks to DLosc for -2 bytes!

{1<≡𝕩?∧´𝕊¨𝕩;≡𝕩}

Run online!

≡ gives the nesting depth of a list:

1<≡𝕩? If the depth is larger than 1 (𝕩 contains at least one list):
    ∧´𝕊¨𝕩 Are all the elements in the list properly tiered?
Else, if 𝕩 is either an integer or a list of integers:
    ≡𝕩 Return the depth (1 for a list, 0 for an integer)

Answer 4

Brachylog, 8 7 bytes

ℕᵐ|ċᵐ↰ᵐ

Try it online!

Explanation

ℕᵐ        The input is a list of only integers
  |       Or
   ċᵐ     The input is a list of only lists
     ↰ᵐ   Recursive call on each sub-list

Answer 5

Typescript, 19 bytes

type A=number[]|A[]

Try it online!

Type system shows an error whenever the typed variable doesn't conform to the requirements.

Answer 6

05AB1E, 19 (or 2..) bytes

d"Ð1åi˜Që®δ.V"©.Vß_

Outputs 0 for truthy and 1 for falsey.

Try it online or verify all test cases.

If the challenge would have used the default truthy/falsey definition instead of overwriting the meta, it could have been 2 bytes instead by erroring:

¸P

Gives an error† as falsey value, or not as truthy value.

Try it online or verify all test cases (somewhat.. the falsey test cases contain rubbish output and lack trailing newline. Not sure how to properly try-catch the inner Elixir errors in 05AB1E.)

Explanation:

d            # Convert each value in the (implicit) input-list to a 1
             # (with a >=0 check)
 "..."       # Push the recursive string defined below
      ©      # Store it in variable `®` (without popping)
       .V    # Evaluate and execute it as 05AB1E code
         ß   # Pop and push the flattened minimum
             # (0 for falsey; 1 or "" for truthy)
          _  # Check that this value is equal to 0 (1 if 0; 0 otherwise)
             # (after which the result is output implicitly)
Ð            #  Triplicate the current list
 1åi         #  If it contains a 1 as item:
    ˜Q       #   Check if the list is unchanged when flattened (thus all are 1s,
             #   without inner lists)
   ë         #  Else:
     δ       #   Map over each inner list:
    ® .V     #    And do a recursive call to `®`

¸            # Wrap the (implicit) input-list into a list
 P           # Take the product of each inner-most list,
             # which will error if an inner list contains both integers and lists
             # (implicitly output the result if it didn't error)

† The (Elixir) error is either an ArithmeticError: bad argument in arithmetic expression or an UndefinedError: protocol Enumerable not implemented for int. depending on how deep the integer causing the error is.

Answer 7

Vyxal, 11 bytes

λÞjṅ[Þj|vxA

Try it Online!

Answer 8

K (ngn/k), 21 bytes

*/^9 56?4/'6!3':`j@^:

Try it online!

Uses a similar idea to Arnauld and Neil's regex approach, but without regex.

*/^9 56?4/'6!3':`j@^:   Input: a ragged list
                   ^:   change all numbers to zeros
                `j@     JSON stringify (which contains only `[]0,`)
             3':        get all length-3 contiguous substrings
           6!    each charcode mod 6 (`[]0,` -> 1 3 0 2)
        4/'      base 4 each
  ^9 56?         test if each number is not one of 9 or 56 (which can only appear if
                 the substring "0,[" or "],0" appear in the string respectively)
*/               1 if all true (or empty), 0 otherwise

Answer 9

Jelly, 9 bytes

߀ŒḊ⁺Ḋ$?P

Try it online!

Port of ovs's BQN solution.

  ŒḊ         The depth of the argument (0 if integer)
       ?     unless
    ⁺        the depth of the argument
     Ḋ       is greater than 1 (range [2 .. depth] is nonempty)
ß            in which case recur
 €           on each element
        P    and take the product of the results.

Answer 10

Python, 54 bytes

f=lambda x:x*0==0 or all((y*0==x[0]*0)&f(y)for y in x)

Attempt This Online!

We can get it a little shorter with Whython, because iterating through a number is an error:

Whython, 46 bytes

f=lambda x:all((y*0==x[0]*0)&f(y)for y in x)?1

Attempt This Online!

Answer 11

R, 56 bytes

f=\(x)`if`(all(y<-Map(is.list,x)),all(Map(f,x)),!any(y))

Attempt This Online!

Checks whether all elements are lists. If so, recurses, otherwise none of the elements may be a list.

Utilises the fact that all and any work on depth-1 lists so we may use Map over sapply.

Answer 12

Rust, 147 131 123 bytes

-18 bytes thanks to @alephaalpha for reminding me matches! exists

-8 bytes thanks to @bubbler for reminding me Vec impelments Deref<Target=[T]> and @alephaalpha for reminding me you can use if in matches!.

enum E{a(u8),b(Vec<E>)}fn f(e:&[E])->bool{e.iter().all(|m|matches!(m,E::a(_)))|e.iter().all(|m|matches!(m,E::b(k)if f(k)))}

Playground Link

Answer 13

Ruby, 21 16 bytes

p !/\],\d|\d,\[/

Try it online!

• Thanks to @Dom Hastings for saving 6.
• Fixed output to be of two consistent values.

Using Regexp.

Takes a string array literal and return true if list is tiered, false otherwise.

Or 50 bytes

Checking recursively.

f=->l{l.all?{|e|e*0==0}||l.all?{|e|e*0==[]&&f[e]}}

Try it online!

Answer 14

Wolfram Language (Mathematica), 28 24 19 bytes

Min[0#/.{0...}->1]&

Try it online!

Returns 1 if the list is properly tiered, or 0 otherwise.

Checks that integers are only present in non-nested lists.

    0#              zero integers
      /.{0...}->1   turn lists of 0s into 1
Min[             ]  0s remaining?

Answer 15

Factor + json,  ^{58 38}  37 bytes

[ >json R/ ],\d|\d,\[/ re-contains? ]

>json postdates the Factor builds on TIO and ATO, so have a picture of running this in Factor's REPL:

If we're allowed to take input as a string, >json can be removed for -6 bytes.

Answer 16

JavaScript, 36 bytes

f=a=>a.some?.(v=>v.at!=a[0].at|f(v))

Return false for valid, true for invalid.

f=a=>a.some?.(v=>v.at!=a[0].at|f(v))

update = () => { try { output.value = input.value.trim().split('\n').map(x => [JSON.parse(x.split('->')[0]), x.split('->')[1].trim() !== 'Yes']).map(([i, e]) => f(i) + ' ' + e).join('\n'); } catch {} }

update();
input.oninput = update;

<div style="display: flex">
<textarea id=input style="flex: 0 0 50%; font: inherit; padding: 10px;">[] -> Yes
[1,2,3,6] -> Yes
[[1,2],[[1]],[[6],[[]]]] -> Yes
[[]] -> Yes
[1,[2]] -> No
[[1,2],[[6],4]] -> No
[[1,[2]],[[3],4]] -> No
[1,[]] -> No</textarea>
<output id=output style="flex: 1 1 0; white-space: pre; padding: 15px;"></output>
</div>

Answer 17

jq, 35 bytes

[..|map(type)?|unique|length]|max<2

Try it online!

Below, "E" indicates where map(type) produces an error. This is supressed with ?.

input:        [1,[2,3]]
[..]:         [[1,[2,3]],          1, [2,3],                2, 3]
[|map(type)]: [["number","array"], E, ["number", "number"], E, E]
[|unique]:    [["number","array"],    ["number"]]
[|length]:    [2,                     1]
|max<2:       false

Answer 18

Retina 0.8.2, 12 bytes

1`\d,\[|],\d

Try it online! Link includes test cases. Outputs 0 for a properly tiered list. Explanation: Same approach as @Arnauld, just check for an integer next to a list. Would cost 3 bytes to output 1 for a properly tiered list.

Answer 19

Charcoal, 27 bytes

⊞υθＦυＦι⊞υ⁺⟦⟧κ⬤υΦ²⬤ι⁼μ⁼ν⁺⟦⟧ν

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

⊞υθＦυＦι⊞υ⁺⟦⟧κ

Enumerate the ragged list and all of its elements but replacing integers with empty lists (which are always properly tiered).

⬤υΦ²⬤ι⁼μ⁼ν⁺⟦⟧ν

Check that all lists contain either only integers or only sublists (or both, in the case of empty lists).

Answer 20

Wolfram Language (Mathematica), 26 bytes

FreeQ[a_/;!SameQ@@Head/@a]

Try it online!

Checks if the input contains any list whose elements do not have the same head (List or Integer).

Answer 21

Ruby, 40 36 29 bytes

f=->l{l*0!=0&&!l.uniq(&f)[1]}

Try it online!

Why?

First check if l is a list (l*0!=0)

Then map f on l and check that the result is the same for all elements. By applying uniq directly on the list, instead of l.map(&f).uniq we can just check if there is a second element (uniq returns elements of the list instead of true or false). If we map the function first, we must check that the size is 2, because if we check the second element, it could be false, which is not what we want.

Answer 22

PARI/GP, 38 bytes

f(a)=(#a>#b=[f(x)|x<-a,#x'==#x])*#b||b

Attempt This Online!

Returns 0 for valid, 1 for invalid.

---

PARI/GP, 40 bytes

f(a)=[#x'==#x|x<-a]&&[x'===0||f(x)|x<-a]

Attempt This Online!

Returns 0 for valid, 1 for invalid.

Answer 23

Pyth, 13 bytes

:w"\d,\[|],\d

Try it online!

Outputs False if list is properly tiered and True otherwise

Answer 24

JavaScript (Node.js), 37 bytes

f=v=>v.every?.(u=>!u.at)|v.every?.(f)

Attempt This Online!

Outputs 1 for properly tiered list, 0 for lists that is not properly tiered, or integers (only used for recursive case)

Answer 25

Whython, 36 bytes

f=lambda l:sum(l)>=0?all(map(f,l))?0

Attempt This Online!

Test harness stolen from the one Mukundan314 contributed to Adam's Python answer

Explanation

f=                                    # f is
  lambda l:                           # a function that takes one argument l:
           sum(l)                     # Sum the list (errors unless all items are numbers)
                 >=0                  # If that worked, return True
                    ?                 # If that errored,
                         map(f,l)     # Recurse on each item (errors if l is not a list)
                     all(        )    # If that worked, return True if every item returned True
                                  ?   # If that errored (l is not a list),
                                   0  # Return 0 (falsey)

The only time the function returns 0 is when it is called on an integer. If it is called on a list, it will always return either True or False.