29
\$\begingroup\$

Consider a grammar over the alphabet {0, 1, ?, :} defined by the production rule

s → 010 ? 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.
\$\endgroup\$
11
  • \$\begingroup\$ How about using language built-ins like eval that interpret strings as $my_language code after changing the string radically? \$\endgroup\$
    – Adám
    Aug 15, 2016 at 9:04
  • \$\begingroup\$ What about builtins that interpret strings as $some_other_language code? \$\endgroup\$
    – user45941
    Aug 15, 2016 at 9:04
  • \$\begingroup\$ @Adám That would be disallowed, sorry. \$\endgroup\$
    – Lynn
    Aug 15, 2016 at 10:05
  • \$\begingroup\$ @Mego Hmm, there’s a trivial cheating opportunity there, so I extended the rule to cover all such built-ins. \$\endgroup\$
    – Lynn
    Aug 15, 2016 at 10:06
  • 1
    \$\begingroup\$ In 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? \$\endgroup\$ Aug 15, 2016 at 12:23

13 Answers 13

17
\$\begingroup\$

Retina, 23 bytes

r-1=+`0\?.:|1\?(.):.
$1

Try it online! (The first line enables a linefeed-separated test suite.)

Explanation

It's fairly simple actually. The input is reduced to the result by repeatedly (+) evaluating ternaries that contain only literals. To make sure this is done right-associatively, we look for matches from right to left (r) and replace only the last match we find (-1=).

The regex itself either matches 0\?.: and removes it (leaving only the stuff after :) or 1\?.:. and replaces it with the value after the ?.

\$\endgroup\$
2
  • \$\begingroup\$ If the regex starts from the right then shouldn't you process the 1st match instead of the -1st? \$\endgroup\$
    – Leaky Nun
    Aug 15, 2016 at 12:47
  • \$\begingroup\$ @LeakyNun Unfortunately, I think I reverse the matches before applying the limit. \$\endgroup\$ Aug 15, 2016 at 14:00
10
\$\begingroup\$

Haskell, 106 101 100 90 83 bytes

This heavily relies on pattern Haskell's pattern matching capabilities. First of all, we reverse the string such that we can just seach for the first occurence of b:a?x (which would normally read as x?a:b) and replace it with it's value. This automatically provides the right associativity. Here we make use of x:xs pattern. This is what the function f is doing. Then we basically apply f to it's output over and over again, until we have a single number (0 or 1) left.

Thanks @Lynn for 12 bytes!

f(b:':':a:'?':x:l)|x>'0'=a:l|1>0=b:l
f(x:l)=x:f l
f x=x
until((<2).length)f.reverse
\$\endgroup\$
8
\$\begingroup\$

Brainfuck, 82 64 63 bytes

+
[
  ,>>,>
  +++++++[<---<<-[------>>]<-]
  <<
  [
    ->[<++>[+]]
  ]
  +>[>>]
  <<<-
]
<.

The output is \xff for 0 and \x00 for 1. The brainfuck implementation must allow going to the left of the starting cell.

This uses essentially the same approach as xsot's Python answer, but the branching is probably harder to follow compared with my initial 82-byte submission:

-
[
  +
  [
    ->,,>+++++++[<--------->-]
    <[<++>[+]]
    <
  ]
  ,->,>+++++++[<[-------<]>>-->-]
  <[<]
  <
]
>>.

(For this solution, the output is \xfe for 0 and \xff for 1, and wider compatibility is achieved when the input ends with a newline.)

If you can't be bothered to analyse xsot's solution, the idea is this: Proceed from left to right. If you see 1? then greedily discard it. If you see 0? then discard everything between that and the corresponding :. When ? does not appear as the second character, stop looping and print the first character of the remaining string.

So, the 82-byte solution actually mirrors that scheme pretty closely. The inner loop handles 0?, just like xsot's inner loop. Some care is taken in order to enter the main loop without checking any input characters; i.e., we want to check whether the second character is ? just once at the end of the main loop, and not also at the beginning before entering the main loop.

The 63-byte solution essentially combines the inner and outer loops into one, which I suspected was possible given the similarity between those loops. The memory layout in the main loop could be described as:

[s] d c

where [x] means current cell -- the s starts as a dummy nonzero value that just indicates we are still looping, and is immediately overwritten with an input character (either 0 or 1). The d cell holds the (negative) depth in case we are in the middle of a 0?, otherwise 0. The c is going to be either ? or : or newline or EOF.

After updating s and c, we handle the 0? case by updating d accordingly and adjusting the pointer, otherwise we use the current value of c as the value of d in the next iteration, or stop if we are done.

\$\endgroup\$
0
7
\$\begingroup\$

Python 2, 76 74 73 72 bytes

a=`id`
for c in input()[::-1]:a=(c+a,a[ord(c)*7%9]+a[4:])[a>'?']
print a

With input as string literal to avoid raw_.

The output is 0 or 1 followed by <built-in function id>.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Haha, I just read your answer for b lang and was about to post an almost identical answer! Here's an additional optimisation: 3>>int(c) \$\endgroup\$
    – xsot
    Aug 15, 2016 at 13:25
  • \$\begingroup\$ Care to explain how this works? Looks really neat \$\endgroup\$ Aug 15, 2016 at 14:05
  • \$\begingroup\$ @WorldSEnder I think it's the type of solution that can be tricky to come up with, but easy to understand once you see it. It runs through the string backwards and repeatedly processes the rightmost conditional, as other solvers have done as well. \$\endgroup\$ Aug 15, 2016 at 14:16
  • \$\begingroup\$ That `id` trick…! Well done :) \$\endgroup\$
    – Lynn
    Aug 15, 2016 at 15:09
5
\$\begingroup\$

GolfScript, 21 bytes

2/-1%{)2%{0`=@@if}*}/

This outputs 0 or 1. Input is assumed to have a single trailing newline. Using ~ (which evaluates strings) would save a byte:

2/-1%{)2%{~!@@if}*}/

This is based on http://golf.shinh.org/reveal.rb?The+B+Programming+Language/tails_1462638030&gs .

\$\endgroup\$
0
5
\$\begingroup\$

Python 2, 89 bytes

s=input()
while'?'<=s[1:]:
 n=s<'1'
 while n:s=s[2:];n+=-(s[1]<'?')|1
 s=s[2:]
print s[0]

Input is taken as a string literal.

\$\endgroup\$
5
\$\begingroup\$

Grime, 34 31 bytes

E=d|d\?E.E
e`\1|\1\?_.E|\0\?E._

Prints 1 for truthy inputs and 0 for falsy ones. Try it online! The last test case unfortunately runs out of memory on TIO.

Explanation

The right-associativity essentially means that in a?b:c, a is always either 0 or 1, never a longer expression. I'll just recursively define a pattern that matches a truthy expression like that, and check the input against it. It's also unnecessary to check that every : is really a :, if the ?s are all checked: there is an equal number of ?s and :s in the input, and if some ? is incorrectly classified as a :, the corresponding : will fail to match, and Grime's matching engine will backtrack.

E=d|d\?E.E
E=                      Define nonterminal E (for "expression") as
  d|                     a digit, OR
    d                    a digit,
     \?                  a literal ?,
       E                 a match of E,
        .                any character (will match a :), and
         E               another match of E.
e`\1|\1\?_.E|\0\?E._
e`                      Match entire input against this pattern (truthy expression):
  \1|                    a literal 1, OR
     \1\?                a literal 1?,
         _               a recursive match of truthy expression,
          .              any character (will match a :), and
           E|            any expression, OR
             \0\?E._     the same, but with 0 in front, and _ and E swapped.
\$\endgroup\$
5
\$\begingroup\$

Haskell, 79 71 70 62 60 56 bytes

Edit: Thanks to @Zgarb for 3 bytes and to @nimi for 4 bytes!

e(x:'?':r)|a:_:s<-e r=last$e s:[a:tail(e s)|x>'0']
e x=x

This a recursive approach that somewhat abuses the "some fixed value"-output rule. Edit: Getting rid of the tuples doesn't only save 8 bytes, it also yields a nicer output: "0" or "1".

Ungolfed version:

eval (x:'?':r1) = if x=='1' then (a, r3) else (b, r3)
    where (a,':':r2) = eval r1
          (b, r3)    = eval r2
eval (x:r) = (x,r)

How does it work?
The eval function traverses the implicit tree of the expressions

eval 1?0?0:1:0?1:0 -> eval 1?          :
                             eval 0?0:1 eval 0?1:0

and returns a tuple of the form (result, rest).
The first pattern (x:'?':r1) matches x to '1' and r1 to "0?0:1:0?1:0". Recursively applying eval to r1 evaluates the sub-expression 0?0:1 and returns (0,":0?1:0"). Matching this to the pattern (a,':':r2) yields a=0 and r2=0?1:0. This sub-formula is also recursively evaluated so that b='0' and r3="". Check if x is '1' or '0' and return either (a, r3) or (b, r3).

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Nice approach! Would x>'0' work in place of x=='1'? \$\endgroup\$
    – Zgarb
    Aug 15, 2016 at 15:11
  • \$\begingroup\$ Thanks, I didn't think of that while dealing with chars. \$\endgroup\$
    – Laikoni
    Aug 15, 2016 at 15:17
  • 1
    \$\begingroup\$ I think you can also replace ':' by _. \$\endgroup\$
    – Zgarb
    Aug 15, 2016 at 15:40
  • \$\begingroup\$ Yes, then the code even works for arbitrary delimiters instead of just :. Thanks again! \$\endgroup\$
    – Laikoni
    Aug 15, 2016 at 16:08
  • 1
    \$\begingroup\$ Nice! You can replace the if .. then .. else with last$e s:[a:tail(e s)|x>'0']. \$\endgroup\$
    – nimi
    Aug 15, 2016 at 16:19
3
\$\begingroup\$

JavaScript (ES6), 53 bytes

f=s=>s[1]?f(s.replace(/0\?.:|1\?(.):.(?!\?)/,"$1")):s

Returns 0 or 1 for valid input; hangs for invalid input. Explanation: because reversing a string is awkward in JavaScript, my first 71-byte attempt worked by using a negative lookahead for a ? which would otherwise disturb the associativity:

f=s=>s[1]?f(s.replace(/(.)\?(.):(.)(?!\?)/,(_,a,b,c)=>+a?b:c)):s

Since this was somewhat long I wondered whether I could improve matters by incorporating the decision making into the regexp. As it turned out, it wasn't an immediate success, as it also took 71 bytes:

f=s=>s[1]?f(s.replace(/0\?.:(.)(?!\?)|1\?(.):.(?!\?)/,"$1$2")):s

Then it occurred to me that 0?0: and 0?1: are always no-ops, without concern for associativity. This saved me almost 25%.

\$\endgroup\$
4
  • \$\begingroup\$ Your code block at the top is missing f=. I haven't checked if your byte count is taking it into account or not. \$\endgroup\$ Aug 16, 2016 at 6:24
  • \$\begingroup\$ @PatrickRoberts I'm forever doing that, because I copy from the log, which only shows the result of the assignment (which is enough for nonrecursive functions of course). \$\endgroup\$
    – Neil
    Aug 16, 2016 at 7:44
  • \$\begingroup\$ @Neil you can copy from log input instead of output \$\endgroup\$
    – ASCII-only
    Aug 16, 2016 at 8:44
  • \$\begingroup\$ @MarsUltor The log input includes the prompt, which I have to then remember to exclude. This is an awkward extra step for non-recursive functions, which is why I copy from the output by default. \$\endgroup\$
    – Neil
    Aug 16, 2016 at 9:40
3
\$\begingroup\$

Perl, 32 + 1 (-p flag) = 33 bytes

Full credit to @Mitch Swartch, as his solution was 14 bytes shorter than mine!
Thanks also to @Neil who suggested a solution 1 byte longer than Mitch.

s/.*\K(0\?..|1\?(.)..)/\2/&&redo

Needs -p flag, as well as -M5.010 or -E to run. For instance :

perl -pE 's/.*\K(0\?..|1\?(.)..)/\2/&&redo' <<< "0
0?0:1
0?1?0:1:1
1?0:1?0?1:1?1:0:1?1?1:1:1?0: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"

Explanations : It basically reduces the blocks of a?b:c (starting from the end to be sure no ? follows) into b or c depending on the truthness of a, over and over until the string only contains 1 or 0.

\$\endgroup\$
6
  • \$\begingroup\$ Does the - not count towards your score? Hrm. Interesting... Good answer! \$\endgroup\$
    – bren
    Aug 15, 2016 at 16:00
  • \$\begingroup\$ @MayorMonty For a 1-liner you can invoke it on the command line using perl -e '<code>' thus adding a p only costs 1 byte perl -pe '<code>'. \$\endgroup\$
    – Neil
    Aug 15, 2016 at 18:17
  • \$\begingroup\$ @Neil Ahh, that makes sense \$\endgroup\$
    – bren
    Aug 15, 2016 at 18:35
  • \$\begingroup\$ Actually you don't have to reverse the string, you can just negative lookahead for a ?, I was able to cut this down to 34 bytes this way. \$\endgroup\$
    – Neil
    Aug 15, 2016 at 18:38
  • \$\begingroup\$ Here is a 32 + 1: s/.*\K(1\?(.)..|0\?..)/\2/&&redo \$\endgroup\$ Aug 15, 2016 at 19:51
2
\$\begingroup\$

Python 3, 93 69 bytes

def f(s):z=s.pop;r=z(0);return s and':'<z(0)and(f(s),f(s))[r<'1']or r

Input is the string as a list of characters, output is either "0" or "1"

>>>f(list("0?0:1"))
<<<"1"

Ungolfed version:

def parse(s):
    predicate = s.pop(0)
    if s and s.pop(0) == '?':
        left, right = parse(s), parse(s)
        if predicate == '0':
            return right
        return left
    return predicate

Another try, but with considerably more bytes:

i=input()[::-1]
a=[i[0]]
for o,z in zip(i[1::2],i[2::2]):a+=[z]if o<'?' else[[a.pop(),a.pop()][z>'0']]
print(a[0])
\$\endgroup\$
5
  • \$\begingroup\$ Your answer may be a function — you can remove the second line. \$\endgroup\$
    – Lynn
    Aug 15, 2016 at 16:25
  • \$\begingroup\$ This is clearly untested, as it doesn't pass the test cases, and the ungolfed version gives a runtime error. Your basic idea is good though. With some adjustments I get 68 in Python 2 and 69 in Python 3. \$\endgroup\$ Aug 15, 2016 at 19:33
  • 1
    \$\begingroup\$ Well I think it makes more sense for me to give you the answer than to edit it into my own (since I wasn't thinking about this kind of approach before I saw your answer) or sit around waiting while your answer is buggy. Here is the 68 I mentioned def f(s):x=s.pop(0);return[]<s<s.pop(0)>'>'and(f(s),f(s))[x<'1']or x, and for Python 3 with small edit distance to yours, there is def f(s):z=s.pop;r=z(0);return s and':'<z(0)and(f(s),f(s))[r<'1']or r . \$\endgroup\$ Aug 15, 2016 at 20:12
  • \$\begingroup\$ Thanks @MitchSchwartz, pretty much parse from right, instead of left, gotcha \$\endgroup\$ Aug 15, 2016 at 21:17
  • 1
    \$\begingroup\$ Otherway, left instead of right, ~~~ \$\endgroup\$ Aug 15, 2016 at 21:27
1
\$\begingroup\$

SED, 75 74 68 (40 + 1 for -r) 41

:
s,(.*)1\?(.):.,\1\2,
s,(.*)0\?.:,\1,
t
\$\endgroup\$
7
  • \$\begingroup\$ You can probably cut this down using @MitchSchwartz's trick in his comment, although you may have to use (.*) and add an extra replacement term. \$\endgroup\$
    – Neil
    Aug 15, 2016 at 20:48
  • \$\begingroup\$ @Neil, you could be right, but I can't figure out how to make it work. \$\endgroup\$
    – Riley
    Aug 15, 2016 at 21:28
  • \$\begingroup\$ I wrote it in chat, since formatting in a comment might be confusing: chat.stackexchange.com/transcript/message/31709640#31709640 \$\endgroup\$ Aug 15, 2016 at 22:41
  • \$\begingroup\$ @MitchSchwartz Heh, blank labels work? But I think you meant \3 instead of \2. Also, you can join the lines with ; to get :;s/(.*)(1\?(.):.|0\?.:)/\1\3/;t. \$\endgroup\$
    – Neil
    Aug 15, 2016 at 23:02
  • \$\begingroup\$ @Neil I had \3 so that means I accidentally copied a previous version. I know about semicolons. But yuck, why would you want to use semicolons. \$\endgroup\$ Aug 15, 2016 at 23:10
0
\$\begingroup\$

Bash + GNU utilities, 42

rev|sed -r ':
s/(.):.\?0|.:(.)\?1/\1\2/
t'

Similar idea to most of the other pattern-matching answers.

Ideone.

\$\endgroup\$
1
  • \$\begingroup\$ You don't need to capture the first character in the 0 case, that saves you 5 bytes. \$\endgroup\$
    – Neil
    Aug 16, 2016 at 7:46

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.