18
\$\begingroup\$

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 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
\$\endgroup\$
5
  • \$\begingroup\$ How is [[1,[2]],[[3],4]] properly tiered? Both lists contain both lists and numbers. \$\endgroup\$
    – Steffan
    Aug 29 at 21:19
  • \$\begingroup\$ @Steffan It's not. Sorry that test cases was suggested and I thought the yeses and nos were the other way when I added it. \$\endgroup\$
    – Wheat Wizard
    Aug 29 at 21:23
  • 1
    \$\begingroup\$ May we error as truthy/falsey value (like the top Python answer currently does)? \$\endgroup\$ Aug 30 at 9:41
  • 2
    \$\begingroup\$ @KevinCruijssen It seems like it was generally accepted by the community -- see Functions may return a boolean value via the presence or absence of an error/exception. \$\endgroup\$ Aug 30 at 15:09
  • 1
    \$\begingroup\$ @Adam I know, but this challenge doesn't ask for a truthy/falsey result, but specifically "You should output one of two consistent values", overwriting the defaults defined in the meta. Hence my question. :) (I've linked that same post as you did in a comment below my 05AB1E when someone mentioned it earlier today.) \$\endgroup\$ Aug 30 at 18:49

25 Answers 25

10
\$\begingroup\$

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!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ You can get away with not escaping one bracket in your regex. \$\endgroup\$
    – emanresu A
    Aug 29 at 22:13
10
\$\begingroup\$

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

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

BQN, 17 15 bytesSBCS

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)

\$\endgroup\$
1
  • \$\begingroup\$ @DLosc indeed, thank you (🤦) \$\endgroup\$
    – ovs
    Aug 30 at 18:25
7
\$\begingroup\$

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
\$\endgroup\$
1
7
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Welcome to Code Golf! \$\endgroup\$
    – Steffan
    Aug 31 at 18:43
6
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ "You should output one of two consistent values". Not only do I think errors are not outputs in that context, but you say that the error can be one of two different values. \$\endgroup\$
    – Fatalize
    Aug 30 at 7:42
  • \$\begingroup\$ @Fatalize Ugh.. And that's why I hate challenged that overwrite the default truthy/falsey meta definition.. :/ Since error as falsey and no error as truthy is perfectly acceptable if the defaults would have been used.. I'll delete for now and see if I can find a way to do this challenge in 05AB1E. I tried it earlier today to have a program actually outputting truthy/falsey instead of erroring as extra, but couldn't really figure it out. Will try again later.. -_- \$\endgroup\$ Aug 30 at 8:40
  • 2
    \$\begingroup\$ @Fatalize Fixed.. at the cost of 17 bytes, because 05AB1E sucks with both ragged lists and recursive challenges. \$\endgroup\$ Aug 30 at 8:57
  • \$\begingroup\$ Based on that meta post, I think it would be fine if the error was consistently the same. Maybe other people have different opinions on the matter. (Personally, I disagree with the meta-post: erroring should not be considered a valid output) \$\endgroup\$
    – Fatalize
    Aug 30 at 9:01
5
\$\begingroup\$

Vyxal, 11 bytes

λÞjṅ[Þj|vxA

Try it Online!

\$\endgroup\$
6
  • \$\begingroup\$ Can Vyxal distinguish between "12" and 12? \$\endgroup\$
    – Sandra
    Aug 31 at 8:20
  • \$\begingroup\$ @Sandra Yes. Why? \$\endgroup\$
    – Steffan
    Aug 31 at 16:26
  • \$\begingroup\$ I don't understand Vyxal yet but I was working on this in a other language and what took a loot of bytes was rejecting ["12"] but accepting [12] \$\endgroup\$
    – Sandra
    Sep 1 at 20:57
  • \$\begingroup\$ @Sandra you shouldn't need to though, because the challenge gives you input containing lists of numbers, and by our meta defaults, input will always be valid \$\endgroup\$
    – Steffan
    Sep 1 at 21:41
  • \$\begingroup\$ But the challenge is to determine if a ragged list is a "a list of only positive integers": do I need to check polarity and type? @WheatWizard please chime in \$\endgroup\$
    – Sandra
    Sep 2 at 22:22
5
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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.
\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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

\$\endgroup\$
4
  • 1
    \$\begingroup\$ if let E::a(_)=m{true}else{false} -> matches!(m, E::a(_)), and false -> 1<0. \$\endgroup\$
    – alephalpha
    Aug 30 at 7:30
  • 1
    \$\begingroup\$ You can change f(e:&Vec<E>) to f(e:&[E]). Also if let E::b(k)=m{f(k)}else{1<0} -> match m{E::b(k)=>f(k),_=>1<0} \$\endgroup\$
    – Bubbler
    Aug 30 at 7:41
  • 1
    \$\begingroup\$ if let E::b(k)=m{f(k)}else{1<0} -> matches!(m,E::b(k)if f(k)). \$\endgroup\$
    – alephalpha
    Aug 30 at 7:45
  • \$\begingroup\$ @alephalpha That second tip is really smart thanks, no idea you could do that \$\endgroup\$
    – mousetail
    Aug 30 at 7:46
4
\$\begingroup\$

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!

\$\endgroup\$
6
  • \$\begingroup\$ Nice approach! Also, -6 for Ruby + -n: Try it online! \$\endgroup\$ Aug 30 at 9:01
  • 1
    \$\begingroup\$ Although I personally think it's pretty stupid, the challenge asks for "two consistent values", which the index isn't. :/ \$\endgroup\$ Aug 30 at 9:46
  • \$\begingroup\$ @KevinCruijssen right, i didn't pay attention , that's fine \$\endgroup\$
    – AZTECCO
    Aug 30 at 10:06
  • \$\begingroup\$ You can save one more byte dropping (...) and replacing with just a space (just enough so it's not parsed as !~ I guess?) \$\endgroup\$ Aug 30 at 10:45
  • \$\begingroup\$ @Dom Hastings yes! And ! is enough so I got rid of ~ \$\endgroup\$
    – AZTECCO
    Aug 30 at 11:27
4
\$\begingroup\$

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?
\$\endgroup\$
3
\$\begingroup\$

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:

enter image description here

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

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

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>

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

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
\$\endgroup\$
2
\$\begingroup\$

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.

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

Charcoal, 27 bytes

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

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

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

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

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

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

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

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.

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

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.

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

Pyth, 13 bytes

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

Try it online!

Outputs False if list is properly tiered and True otherwise

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

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)

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

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.

\$\endgroup\$
3
  • \$\begingroup\$ You could do f=lambda l:~sum(l)?all(map(f,l))?0 and just return truthy or falsey. \$\endgroup\$
    – Steffan
    Aug 30 at 17:39
  • \$\begingroup\$ You really should thank @Mukundan314 for the tests \$\endgroup\$ Aug 30 at 18:05
  • \$\begingroup\$ @Steffan This particular challenge specifies that "You should output one of two consistent values," so I don't think returning any of various negative numbers for truthy would be allowed. :( \$\endgroup\$
    – DLosc
    Aug 30 at 20:28

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.