# Is it a valid list?

Given a string like [[[],[[]]],[]], made of only commas and square brackets, your challenge is to determine whether it represents a list.

A list is either:

• [], the empty list
• At least one list, joined with commas and wrapped in square brackets.

You may use any three characters instead of [,].

You may output as:

• Any two consistent values representing truthy and falsy
• One consistent value representing either truthy or falsy, and anything else as the other.

Output by erroring/not erroring is allowed, although eval-like solutions may be trickier than you think. Sometimes erroring and sometimes returning is not.

This is , shortest wins!

### Truthy

[[]]
[[],[]]
[[[[]],[[],[[]]],[]],[]]
[[[[]]]]
[]


### Falsy

]
[[][]]
[,]
,
[],[]
[[[]][[]]]
[[],]
,[]
[[]
[,[]]
[][]
[[],

• Do solutions need to handle the empty string as a (falsey) input? Jun 16 at 21:14
• Suggested test case: ,[]
– Adám
Jun 16 at 21:18
• In "One consistent value representing either truthy or falsy, and anything else as the other," can the "anything else" include sometimes returning a value and sometimes erroring? Jun 16 at 21:23
• Suggested test case: [[] Jun 17 at 5:00
• Let's mourn that Mathematica has ListQ ... which doesn't quite meet these specs for non-lists. Jun 19 at 19:19

# JavaScript, 10 bytes

JSON.parse


Outputs via the presence or absence of an error.

Try it online!

# Python3, 70 bytes:

def f(s):
try:return s==str(eval(s)).replace(' ','')
except:return 0


Try it online!

• 70 bytes, fixes the error signaled by @Unrelated String Jun 16 at 21:16

# PARI/GP, 0 bytes

Takes input from stdin, returns truthy iff stderr is empty.

PARI/GP automatically parses and evals everything from the stdin.

Attempt This Online!

# Haskell + hgl, 26 bytes

f=opn*>isP f ʃ_*>cls

x1 f


Uses the characters ()_.

Creates a parser object and uses x1 to determine if some input matches the parser.

f('(':')':>x)=mF f$' '|\x  Uses the characters () . Returns True on valid inputs and errors on invalid ones. This version is 1 byte shorter but I'm not sure if it's allowed by the rules. If you call the function expecting a bool, e.g. f x::Bool  It will work. However by default ghci infers () as the type, which does not meet the output specifications of the challenge. So you need to call it either with a type signature or in a context in which ghc can infer it's type to be Bool. # Relfections • hgl has a unwords function. It could be made a pattern like in the curry answer: f('(':')':>Uw x)=mF f x  • It's rather annoying that wR, the words function trims leading spaces. There is a 23 byte answer which would work if wR didn't do this. f('(':')':>x)=mF f$wR x

• mF should have an infix.
• isP should have an infix.
• isP should have a flip.

# APL (Dyalog Unicode), 5 bytes

Anonymous tacit prefix function taking input as [,] with output by erroring/not erroring.

⎕JSON


Try it online! (wrapped in error trapping code to give 0 when erroring and 1 when not erroring)

Attempts to convert from JSON.

# Python, 19 bytes (@dingledooper)

eval("set"+input())

Attempt This Online!

### Old Python, 22 bytes

def f(s):eval("set"+s)

Attempt This Online!

This takes a string composed of the characters "(+)" and signals by erroring/not erroring.

#### How?

Why can't we just use eval?

1. trailing commas
2. missing outer brackets

Both will be tolerated by eval.

To address 1 we replace , with +.

To address 2 we switch from [] to () and prepend set.

### Old Python, 28 bytes

def f(s):eval(s+","+s[1:-1])

Attempt This Online!

This takes a string composed of the characters "[+]" (note that we have cheekily but legally replaced "," with "+") and signals by erroring/not erroring.

I'm not 100% sure this is correct but it works on all test cases.

• Nice. Alternative: def f(s):eval('zip'+s) and using (,) Jun 17 at 1:51
• @mathjunkie I believe that will miss trailing commas like s="((),)". Jun 17 at 1:56
• I suppose taking input via STDIN will save a few bytes: eval("set"+input()) Jun 17 at 2:51

# Stax, 22 23 bytes

Ç╥╫ÜΦªt┌¢♣☺¢+╬ï▼6◘-6¡Zq


Run and debug it

### Approach

• Repeatedly
• Replace "[[]]" with "[]"
• Replace ",[]]" with "]"
• Replace "[[],[" with "[["
• Is result equal to "[]"?

# Curry (PAKCS), 29 bytes

f('[':unwords a++"]")=all f a


Try it online!

Uses a space   instead of ,. Returns True for truth, and nothing otherwise.

# Curry (PAKCS), 53 bytes

f('[':a++"]")=g a
f"[]"=1
g(a++',':b)=f a*g b
g a=f a


Try it online!

Returns 1 for truth, and nothing otherwise.

# Whython, 36 bytes

lambda s:eval(s)>=[]!=",]"not in s?0


Returns True for valid lists, False or 0 for invalid lists. Attempt This Online!

### Explanation

lambda s:eval(s)>=[]!=",]"not in s?0
lambda s:                             # Anonymous function that takes s, a string
eval(s)                      # Python eval
>=[]                  # True if the result is a list, error if tuple
!=                # Keep the comparison chain going
",]"not in s    # Check that there are no extra commas
?0  # If anything raised an error, return 0


# Regex (Perl / PCRE), 21 bytes

^(<(((?1),)*(?1))?>)$ Uses the characters <>,. (Avoids [] as they would require being \-escaped.) Try it online! - Perl Try it on regex101 - PCRE1 Try it online! - PCRE2 v10.33 Attempt This Online! - PCRE2 v10.39+ Like the regex in the Raku answer, this uses recursion. Unlike Raku, standard regex has no concept of "separator" characters, so there's no concise way of implementing a comma-separated list, and the recursive call (?1) needs to be in two places. There are many alternatives of the same length: ### Regex (Perl / PCRE), 21 bytes ^(<((?1)(,(?2))?)?>)$


Also uses the characters <>,.

Try it online! - Perl
Try it online! - PCRE

Uses (?2) recursion instead of * repetition for the comma-separated list.

^(a((?1),)*(?1)?\Bz)$ Uses the characters az, in order to take advantage of the \B non-word-boundary assertion. Try it online! - Perl Try it online! - PCRE Without the use of \B, there would be nothing stopping a comma-separated list ending in a comma from being accepted, as the (?1)? is optional independently of whether or not ((?1),)* matched anything. The \B prevents this; if any list ended with a comma, the sequence ,z would be part of it, so all we need to do is prohibit this sequence. \Bz accomplishes this, as a and z are word-characters but , is not, thus there is no word boundary in the middle of az or zz but there is one in ,z. ### Regex (Perl / PCRE), 21 bytes ^(a\B(?1)?(,(?1))*z)$


Also uses the characters az,. Mirror version of the above.

Try it online! - Perl
Try it online! - PCRE

^(<(\B(?1)|\b,\B)*z)$ Try it online! - Perl Try it online! - PCRE Uses the characters <z, in order to take advantage of the \b and \B word- and non-word-boundary assertions. ### Regex (Perl / PCRE), 21 bytes ^(a((?1)\B|\B,\b)*>)$


Uses the characters a>,. Mirror version of the above.

Try it online! - Perl
Try it online! - PCRE

# Regex (.NET), 3533 29 bytes

^((a)+(?<-2>z)+(?(2),\b|$))+$


Uses the characters az, in order to take advantage of the \b word-boundary assertion.

Try it online!

Based on the old 35 byte one-liner in Neil's Retina answer.

-1 byte by using the characters <>, instead of [],, because [ needed to be \-escaped
-1 byte by using an illegal character, instead of $., as the impossible condition to assert Group 2 being empty at the end -4 bytes by using the characters az, instead of <>,, obviating the need for explicitly asserting Group 2 is empty at the end ^ # Assert that we're at the beginning of the string. ( (a)+ # Capture at least one "a" on the Group 2 stack. (?<-2>z)+ # Match at least one "z", popping an entry from the Group 2 # stack for each one we match. (?(2),\b|$)  # If the Group 2 stack is non-empty, match a "," followed by a
# word boundary (since "," is a non-word character, this means
# it must be followed by a word character, i.e. [0-9A-Za-z_]),
# else assert that we're at the end of the string.
)+               # Loop the above at least 1 time.
$# Assert that we're at the end of the string. The Group 2 # conditional at the end of the above loop guarantees that the # only way to end the loop at the end of the string is for # Group 2 to be empty, due to the "\b" in its non-empty # clause. So there's no need to explicitly assert here # something like "(?(2)$.)" (which would assert something
# impossible in the case that Group 2 is non-empty).


Note that if the <>, characters are still used, it can be 32 bytes:

^((<)+(?<-2>>)+(?(2),(?!$)|$))+$ Try it online! ### $$\\large\textit{Anonymous functions}\$$ # Perl, 33 bytes sub{pop=~/^(<(((?1),)*(?1))?>)$/}


Try it online!

\(L)grepl('^(<(((?1),)*(?1))?>)$',L,,1)  Attempt This Online! -1 byte thanks to Giuseppe -4 bytes by using grepl() instead of sum(grep()) or any(grep()) -5 bytes by using a new anonymous function syntax introduced in R v4.1.0 # PowerShell, 46 42 bytes $args-match'^((a)+(?<-2>z)+(?(2),\b|$))+$'


Try it online!

• You can omit the 0 in the R answer, so it's grep(...,,1) Jun 18 at 1:57

# VyxalP, 8 bytes

øBEÞfSȧ=


Try it Online!

Still shorter than JavaScript! The link is a test suite, hence the additional flags - those are just to wrap all inputs into a list (a) and to treat all inputs as strings (S with updot - it's the equivalent of wrapping every input in quotation marks).

## Explained

øBEÞfSȧ=
øBE      # wrap the input in square brackets and try to evaluate it as a python literal
Þf    # attempt to flatten the list by a level - if the input was listlike (that is, valid for this challenge or valid as a python tuple), this will undo the øB. Otherwise it leaves the string as is
S   # convert the result of the above to string. The P flag makes it so that square brackets and commas are used for lists instead of the angular brackets and pipes Vyxal uses.
ȧ= # remove any whitespace and test to see if this new string is equal to the original input.



# R, 101 bytes

\(x,y='',s=\(p,b,x)sub(p,b,x,,,T)){while(y!=(y=x)){x=s('[[],[]','[[]',y);x=s('[[]]','[]',x)};y=='[]'}

Attempt This Online!

Text replacement solution, '[[],[]' -> '[[]' '[[]]' -> '[]'

Earlier attempts at this were using far too many \\ to escape [/].

# Wolfram Language (Mathematica), 31 bytes

{Times=N}~Block~ToExpression@#&


Try it online!

Uses {,}. Returns by presence/absence of an error.

Missing arguments are interpreted as Null, but will raise an error message.

Juxtaposition is a valid operation (Times), so we use Block to turn it into N. Since N only handles one or two arguments, it errors when passed three or more arguments. When N has exactly two arguments, the second argument must be of the form precision or {precision,accuracy}, where precision and accuracy are numbers. Input is guaranteed to never have numbers, so the 2-argument form is also guaranteed to error.

# Retina 0.8.2, 3935 23 bytes

<<>>
<>
}<<>,<
<<
^<>$ Try it online! Takes <,> characters but link is to test suite that converts from [] for convenience. Explanation: Port of @recursive's Stax solution. <<>> <>  Remove an empty list that's the only element of a list. <<>,< <<  Remove an empty list that's the first element of a list. }  Repeat until there are no more elements to remove. ^<>$


Check that we finished with an empty list.

Escaping means that it takes 29 bytes to use [,] characters:

\[\[]]
[]
}\[\[],\[
[[
^\[]$ Try it online! Link includes test cases. Previous 35-byte one-liner: ^((\[)+(?<-2>])+(?(2),|$))+(?(2)$.)  Try it online! Link includes test cases. Explanation: ^(  Start matching at the beginning of the string. (\[)+  Count the number of [s. (?<-2>])+  Count some ]s, but no more than the number of [s so far. (?(2),|$)


After each run of [s and ]s, if there are still unbalanced ]s, then there must be a , next, otherwise we must be at the end of the string.

)+


Repeat as many times as necessary.

(?(2)$.)  Check that there weren't more [s than ]s. • You can save 1 byte by changing (?(2)$.) to e.g. (?(2)z), since the statement of the question guarantees that the input is made of only commas and square brackets. You can save another 1 byte by using e.g. <,>, as the question also state you may use any three characters instead of [,]. Jun 18 at 1:19
• @Deadcode On the other hand I could just not do it as a 1-liner...
– Neil
Jun 18 at 6:33
• Nice, that's more in line with what I'd expect from Retina. Is it okay with you if I adapt your old answer as a .NET regex sub-answer in my answer? Jun 19 at 0:34
• @Deadcode If you mean the 2 byte savings you mentioned above then sure. If you mean something else that I can backport while maintaining compatibility then I might want to update my answer with the appropriate saving.
– Neil
Jun 19 at 0:39
• Thanks, done. It's just the 2 bytes; I had to suggest two new test cases because without them, the regex could be reduced to 25 bytes and pass all test cases. Jun 19 at 0:47

# Rust (compile-time), 43 bytes

macro_rules!v{([$($a:tt),*])=>($(v!{$a})*)}


Try it online!

This is a Rust macro (the compile-time equivalent of a function) named v!. Use as v!{…}, where … is the string you want to check (without delimiters – string literals are opaque to the usual sort of Rust macro). I used [, ,, ] as in the question, although this could easily be adapted to use almost any Rust token in place of , and/or () rather than [].

Outputs via error/non-error: an invalid list causes a compile time error, a valid list causes no error (and the macro expands to an empty declaration).

## Explanation

macro_rules!v{([$($a:tt),*])=>($(v!{$a})*)}
macro_rules!v{                            }   Macro declaration
([          ])                  Match something surrounded by []
$( ) * which consists of 0 or more$a:tt                         balanced token trees $a , separated by commas =>( ) and replace it with,$(   $a )* for each$a,
v!{$a} a recursive call to v!{$a}


We verify the structure of the outermost list, then recurse into the inner lists to make sure that those are also correct. Rust macros have a :tt builtin that matches brackets, which makes it easy to use the strategy of parsing out the elements first and recursing over them afterwards. The base case of the recursion is that when we match a zero-length list, the replacement expands into zero macro calls, because the loop in the replacement runs for zero iterations.

Note that Rust normally allows a trailing comma on lists, so we do actually have to write our own verification macro rather than using something that Rust has predefined.

# Yacc, 22 bytes

s:'['b']'b:l|l:s|s','l


Try it online! (note: Yacc is installed on TIO, but doesn't have a TIO wrapper, so I had to write one myself; I also wrapped the function into a full program. The wrapper outputs by exit code.)

Function submission. (I originally forgot PPCG allowed functions to be sumbitted, so the first version of this was a full program with a lot of boilerplate. Submitting it as a function obviously makes more sense.)

This is a function/parser named s that reads input from yacc's usual input source. It does the yacc equivalent of throwing an exception if the input is not a list, or returns normally if the input is a list. (It doesn't explicitly return a value – Yacc uses "implicit int" like in C, so these parsers are technically returning integers, but we don't set the return value to anything in particular.)

This function uses [, ], , as suggested by the question, but could easily be adapted to use any three characters (although some choices would make the program longer due to needing to be escaped).

## Explanation

Yacc is a language for writing parsers; you provide a description of syntactically legal input and it generates a parser for you. This program contains three parsers, s, b and l:

s:'['b']'b:l|l:s|s','l
s:                       An "s" is
'['                      an opening square bracket
b                     then a "b"
']'                  then a closing square bracket;
b:              A "b" is
l|              either an "l", or {an empty string};
l:          An "l" is
|          either
s             an "s"
|          or
s           an "s"
','        followed by a comma
l       followed by another "l"


A direct translation of the question to Yacc would be s:'['']'|'['l']'l:s|s','l, but factoring out the brackets from the two branches of s into a separate rule b allows the program to be a byte shorter.

Yacc programs don't normally look this condensed; they're normally written with more whitespace, and semicolons between rules. However, the semicolons are optional, and whitespace is optional except between two identifiers (and I arranged this program so that it never had two identifiers in a row, allowing all the whitespace to be golfed off). A weird side effect of this flexibility is that Yacc's syntax is very hard to parse due to false positives (e.g. b:l|l is a valid rule, but b:l|l: has to be parsed as b:l|; l: despite that), and in fact, it isn't sufficiently powerful to write a parser for its own syntax (it's powerful, but its syntax is weird enough that it needs even more power to parse). It's helpful in golfing, though!

# Factor + json.reader, 5 bytes

json>


Try it online!

Outputs by the presence of an error.

# Rust, 406 bytes

fn a(d:&str)->bool{let c=d.chars().collect::<Vec<_>>();let c=c.as_slice();let b=c.iter().fold((0,0),|mut a,&i|{if i=='['{a.0+=1}else if i==']'{a.1+=1}a});let m=c.windows(2).any(|a|a[0]==']'&&a[1]=='[');let mut j=false;c.iter().fold(0,|a,&i|{if i=='['{a+1}else if i==']'{a-1}else if i==','&&a==0{j=true;a}else{a}});let o=c.windows(3).find(|a|a[1]==','&&(a[0]!=']'||a[2]!='['));b.0==b.1&&!m&&!j&&o.is_none()}


Try it online!

Not a golfing language by any means, but it's worth giving it a try. It can be golfed down a lot as it's currently using a really naïve approach.

# 05AB1E, 10 bytes

„,]å≠i.E}˜


No error as truthy; error (** (Protocol.UndefinedError) protocol Enumerable not implemented for ...) as falsey.

Try it online or verify all test cases. (Wrap the single TIO input in """ quotes to get the input as string, instead of implicitly as (possibly faulty) list.)

Explanation:

     i  }   # If
# the (implicit) input-string
≠       # does NOT
å        # contain the substring
„,]         # ",]":
.E    #  Evaluate the (implicit) input-string as Elixir
# (implicit else)
#  (implicitly use the input-string)
˜  # Flatten (results in [] for lists; or an error for strings)


The if-statement is for edge-case [[],], which unfortunately is a valid Elixir/Python list that evaluates to [[]]. If it wasn't for this test cases, .E˜ would have been enough in the new version of 05AB1E: verify all test cases.
And it could even have been 1 byte in the legacy version of 05AB1E using the -e/--eval flag: verify all test cases.

# Haskell (GHCi), 0 bytes

Takes input from stdin, returns truthy iff stderr is empty.

• This doesn't seem to meet either of the allowed output formats, since neither the truthy nor falsy values are consistent. Jun 17 at 12:19
• The program outputs "one consistent value representing either truthy or falsy, and anything else as the other" as the rules stay: empty stderr represents truthy, anything else (non-empty stderr) represents falsy. Jun 17 at 14:10
• I guess the question is whether you are allowed to ignore the non-stderr output. Because at current neither is consistent unless you only look at output from stderr. The question is at least a bit unclear as to whether this is allowed, unless there is some meta-consensus I am missing. Jun 17 at 14:12
• Well, since programs may output to stderr, and I'm stating that the program outpus to stderr, I don't see why one should look to the things that the program outputs via other I/O methods Jun 17 at 14:22
• Moreover, the challenge explicitly states "Output by erroring/not erroring is allowed" Jun 17 at 14:23

# Raku, 31 bytes

{($^a~~/"["<~~>*%",""]"/)~~$^a}


This is a function which takes the string as input and produces typical Raku Booleans (True or False).

Let's break it down. First, better spacing

{ ($^a ~~ /"[" <~~> * % "," "]"/) ~~$^a}


First, $^a is a sort of special syntax for declaring lambdas without explicitly mentioning their arguments, so this is equivalent to the single-argument function ->$a { ($a ~~ /"[" <~~> * % "," "]"/) ~~$a}


Now, ~~ is a terribly clever thing in Raku called the smart-match operator. At a high-level, it's going to evaluate its right-hand side and then call the .ACCEPTS method on the right-hand side with the left-hand side as argument. We use it twice here: The leftmost application is on a regex object and will do a regular expression match. The rightmost application is on the input string and will perform ordinary string equality.

We're going to do a regex match against that regular expression enclosed in /. That match will return either a special regex Match object, or Nil if the match fails. We then compare that for string equality. A Match object stringifies as the substring it matched, so we're simply checking whether the match that was found is in fact the whole string. Nil, on the other hand, stringifies to "", and as per the comments the empty string is not valid input, so \$^a will never compare equal to that.

Now let's look at the regex itself.

/"[" <~~> * % "," "]"/


If you haven't seen Raku regexes before, it may be best to forget everything you know about regular expressions, because the syntax is only superficially similar. Anything enclosed is quotes is matched literally, so "[", ",", and "]" are matched literally. * works like it does in most regex languages: It's the Kleene star and matches zero or more. % is a modifier on * which delimits multiple matches by the thing on its right (in our case, a comma). Finally, <~~> is the recursive matcher, which matches the entire regular expression again. So, in summary

/                      # Start of regex
"["                   # Match an opening bracket
*            # Then match zero or more...
% ","      # delimited by commas...
<~~>              # of the current regular expression recursively
"]"  # Finally, match a closing bracket
/ # End of regex


# SNOBOL4 (CSNOBOL4), 84 bytes

	L ='[]' | ('[' *L ARBNO(',' *L) ']')
INPUT POS(0) L RPOS(0)	:F(END)
OUTPUT =1
END


Try it online!

Prints 1 for truthy and nothing for falsey.

Recursive pattern matching is pretty slick.

# Javascript, 7978 77 bytes

f=s=>eval("r=/(<(<>,)+<>>)|(<<>>)/;r.test(s)&&f(s.replace(r,'<>'))||s=='<>'")


uses the characters <,> and returns true/false

saved 1 byte thanks to @RadvylfPrograms
saved 1 byte by using recursion and joining expressions

Try it online!

• Welcome to Code Golf, and nice answer! I think you can save a few bytes with this trick, and possibly more with recursion. Jun 17 at 23:28
• Also, this seems to give false for <<<<>>,<<>,<<>>>,<>>,<> which is in the truthy cases section, not sure if that's an issue with this answer or the test cases. Jun 17 at 23:30
• I think that’s an issue with the case. if you count up the pairs on that one, you are missing a closing bracket. it should be <<<<>>,<<>,<<>>>,<>>,<>>. (Note the final ending > Jun 17 at 23:41

# Charcoal, 29 bytes

Ｆθ≔⪫⪪⪫⪪θ[[]]¦[]¦[[],[¦[[θ⁼θ[]


Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for valid, nothing for invalid. Explanation: Boring port of @recursive's Stax answer.

Ｆθ


Repeat more than enough times...

≔⪫⪪⪫⪪θ[[]]¦[]¦[[],[¦[[θ


... remove the first or only element of a list if it's an empty list.

⁼θ[]


Check that we're left with an empty list.

Less boring 34 byte solution:

›⬤⁺,θ№,[[]],⁺ι§⁺θ,κ⊙θ∧κ⁼№…θκ[№…θκ]


Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for valid, nothing for invalid. Explanation:

   ,                                Literal string ,
⁺                                 Concatenated with
θ                               Input string
⬤                                  All characters satisfy
,[[]],                        Literal string ,[[]],
№                              Contains
ι                      Current character
⁺                       Concatenated with
θ                   Input string
⁺                    Concatenated with
,                  Literal string ,
§                     Indexed by
κ                 Current index
›                                   And not
θ               Input string
⊙                All characters satisfy
κ             Current index
∧              Logical And
№           Count of
[       Literal string [
…θκ        In current prefix
⁼            Equals
№      Count of
]  Literal string ]
…θκ   In current prefix
Implicitly print


Note that by default Charcoal tries to parse an input in a JSON-like format so to defeat that you need to wrap the input in JSON i.e. prepend [" and append "].

# C, 178 bytes

int v(char *s){int d=1;for(s++;*s!='\0';s++){if(d==0)return 0;if(*s=='{')d++;if(*s=='}'){d--;if(*(s+1)=='{')return 0;}if(*s==','&&!(*(s-1)=='}'&&*(s+1)=='{'))return 0;}return!d;}

• this doesn't work for the input ,}, it assumes the first character is a {`.
– c--
Jun 18 at 22:14
• oh shit, I was sure I checked for this. oh well, next time then. Jul 4 at 12:28