29
4
Consider a grammar over the alphabet {0
, 1
, ?
, :
} defined by the production rule
s →
0
┃1
┃0
?
s:
s ┃1
?
s:
s
Given a string generated from s, parse it as an expression where ?:
is right-associative (for example, a?B?X:Y:c?d:e?f:g
means a?(B?X:Y):(c?d:(e?f:g))
) and evaluate it with the following semantics:
eval(0) = 0
eval(1) = 1
eval(0?a:b) = eval(b)
eval(1?a:b) = eval(a)
If the result is 0, output some fixed value; if the output is 1, output a different fixed value. Specify your chosen output values (e.g. 0
/1
, or False
/True
) in your answer.
Test cases
0 -> 0
1 -> 1
0?0:1 -> 1
0?1:0 -> 0
1?0:1 -> 0
1?1:0 -> 1
0?1?0:1:1 -> 1
1?0?1:1:1 -> 1
1?0:1?0:1?1:1 -> 0
1?1?1:0?1?0:0:0:0 -> 1
1?0:1?0?1:1?1:0:1?1?1:1:1?0:1 -> 0
1?1?1:0?0?1:1:0?1:0:1?1?0?0:0:1?1:0:0?1?0:1:1?0:1 -> 1
0?0?1?0?0:1:0?0:0:0?0?1:1:1?0:1:0?0?0?1:0:0?1:1:1?1?0:1:1 -> 0
Rules
- You may not use language built-ins that interpret strings as code in some programming language and run it (such as JavaScript/Perl/Ruby/Python’s
eval
). - That said, your code doesn’t actually have to parse and then evaluate the input string. You can take any approach the achieves equivalent results and doesn’t violate the previous rule.
- Your program will be checked against
perl -le 'print eval<>'
. - The shortest code (in bytes) wins.
How about using language built-ins like eval that interpret strings as $my_language code after changing the string radically? – Adám – 2016-08-15T09:04:04.827
What about builtins that interpret strings as $some_other_language code? – Mego – 2016-08-15T09:04:07.267
@Adám That would be disallowed, sorry. – Lynn – 2016-08-15T10:05:48.353
@Mego Hmm, there’s a trivial cheating opportunity there, so I extended the rule to cover all such built-ins. – Lynn – 2016-08-15T10:06:56.510
Would it be valid to just define an operator
?:
and consider the input as code? – flawr – 2016-08-15T10:47:26.030What do you mean by consider? I don’t see how that wouldn’t violate the first rule, sorry ^^; – Lynn – 2016-08-15T10:52:25.007
I don't quite see what you mean by the second rule then? – flawr – 2016-08-15T10:54:13.973
I agree that it’s confusing. Peter Taylor was just being pedantic in the sandbox :) It just means “I write ‘parse’ in the second paragraph, but you don’t actually have to construct a parse tree and recurse on it; you can use e.g. regexes instead”. – Lynn – 2016-08-15T10:58:30.787
1In the light of Martin's test cases, perhaps it would be simpler to define the grammar as
S → T | T ? S : S
,T → 0 | 1
, removing the need to talk about associativity? – Peter Taylor – 2016-08-15T12:23:41.997In PHP, can I write the input to a file and include that file (effectively causing it to execute) or is that
eval()
-ish? – MonkeyZeus – 2016-08-16T16:18:45.590Nope, that’s
eval()
-ish. – Lynn – 2016-08-16T19:20:40.480