25
Pyth is a golfing language based on Python. It uses prefix notation, with each command having a different arity (number of arguments it accepts).
Your task is to write a syntax checker for a (non-existent) Pyth-like language, Pith.
Pith's syntax
Pith only has 8 single-char commands:
01234()"
01234 each have arity of the corresponding number, and hence expect that many arguments after it. For example,
400010
is a correct Pith program because 4 is followed by four arguments 0 0 0 and 10, the last of which is a 1 followed by the single argument 0. To visualise this, we can look at the following tree:
R
|
4
|
-------------
| | | |
0 0 0 1
|
0
where R is the root node. An alternative way to think about this is that each number refers to the number of children the corresponding node has in the tree above.
Here's another valid Pith program, with more than one base command:
210010
corresponding to
R
|
-------------
| |
2 1
| |
--------- 0
| |
1 0
|
0
On the other hand,
3120102100
is not a correct Pith program because the initial 3 only has two arguments, which we can see by looking at the tree below:
R
|
3
|
------------------------ ??
| |
1 2
| |
2 ------
| | |
------ 1 0
| | |
0 1 0
|
0
Next ( starts an unbounded, and ) ends an unbounded. An unbounded takes any number of arguments (greedily), and counts as a single argument to any parent command. Any unboundeds still open by the end of the program are automatically closed. A ) command is not an error if no unboundeds are open — it just does nothing.*
For instance, the Pith program
)31(0)0(201000100
corresponds to the tree
R
|
3
|
------------------------------
| | |
1 0 (
| |
( -----------------------------
| | | | | |
0 2 0 0 1 0
| |
------- 0
| |
0 1
|
0
Empty unboundeds are okay, so () is a valid Pith program.
An invalid Pith program with an unbounded is
12(010
since the 2 only receives one argument (the unbounded).
Finally, " starts and ends a string, which is always 0 arity and counts as a single argument, e.g.
2"010""44)()4"
which is just a 2 being passed two string arguments "010" and "44)()4". Like unboundeds, strings may also be empty, and any unclosed strings by the end of the program are automatically closed.
*This part is different from the original Pyth which actually does do something in a case like 1), ending the 1-arity and raising an error.
Input/output
Input will be a single non-empty string consisting of only the characters 01234()". You may optionally assume that an additional trailing newline is always present. You may write a function or a full program for this challenge.
You should output a truthy value if the input is syntactically valid Pith, or a falsy value otherwise. The truthy and falsy values must be fixed, so you can't output 1 for one valid program and 2 for another.
Scoring
This is code-golf, so the code in the fewest bytes wins.
Test cases
Truthy:
0
)
(
"
()
""
10
400010
210010
("")00
3"""""
(0)))0)1)0
2(2(2(0)0)0)0
2"010""44)()4"
)31(0)0(201000100
())2)1))0"3())"))
3("4321("301(0)21100"4")"123"00)40"121"31000""01010
Falsy:
1
1(310
(1)0)
12(010
4"00010"
3120102100
20(2((0)(0)))
2(2(2(0)0)0)01)
4(0102)00)00000
2"00"("00"2(""))
Sp3000
Posted 2015-03-15T14:44:00.653
Reputation: 58 729
Shouldn't the tree for 20100100 (in the first unbounded example) be
[( [2 [0] [1 [0] ] ] [0] [1 [0]] [0] ]? The one you have has branches of 2, 0, 0, 1 and 0 - the second one shouldn't be there. – bcsb1001 – 2015-03-15T14:55:48.220@bcsb1001 Thanks and corrected. I wanted to show that unboundeds can go above 4. – Sp3000 – 2015-03-15T14:57:39.013
@Ypnypn there are test cases saying that its valid to have multiple roots – Optimizer – 2015-03-15T20:04:15.783
Would you please add the test case for
())2)1))0"3())"))(which should be true, I think). – n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ – 2015-03-16T04:30:33.643@n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Added - it is indeed true (since it's basically
()210""with a lot of no-ops) – Sp3000 – 2015-03-16T04:55:57.720Also
(0)))0)1)0(true) and(1)0)(false). – jimmy23013 – 2015-03-16T09:07:15.177@user23013 Thanks and added – Sp3000 – 2015-03-16T09:09:06.730
"Any unboundeds still open by the end of the program are automatically closed. A ) command is not an error if no unboundeds are open — it just does nothing.*" is there any reason for this bit of syntax to exist other than to pander to code golf and miscellaneous source formatting challenges? – Sparr – 2015-05-14T19:15:24.520
@Sparr Admittedly that was the only part of the spec I messed up, because what I meant was that unmatched
)on the top level was not an error. It's a bit late to change though, unfortunately. – Sp3000 – 2015-05-14T23:20:46.467