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\$
  • \$\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 '16 at 9:04
  • \$\begingroup\$ What about builtins that interpret strings as $some_other_language code? \$\endgroup\$ – Mego Aug 15 '16 at 9:04
  • \$\begingroup\$ @Adám That would be disallowed, sorry. \$\endgroup\$ – Lynn Aug 15 '16 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 '16 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\$ – Peter Taylor Aug 15 '16 at 12:23

13 Answers 13

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\$
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\$
  • \$\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 '16 at 12:47
  • \$\begingroup\$ @LeakyNun Unfortunately, I think I reverse the matches before applying the limit. \$\endgroup\$ – Martin Ender Aug 15 '16 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\$
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\$
  • 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 '16 at 13:25
  • \$\begingroup\$ Care to explain how this works? Looks really neat \$\endgroup\$ – WorldSEnder Aug 15 '16 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\$ – Mitch Schwartz Aug 15 '16 at 14:16
  • \$\begingroup\$ That `id` trick…! Well done :) \$\endgroup\$ – Lynn Aug 15 '16 at 15:09
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\$
  • 1
    \$\begingroup\$ Nice approach! Would x>'0' work in place of x=='1'? \$\endgroup\$ – Zgarb Aug 15 '16 at 15:11
  • \$\begingroup\$ Thanks, I didn't think of that while dealing with chars. \$\endgroup\$ – Laikoni Aug 15 '16 at 15:17
  • 1
    \$\begingroup\$ I think you can also replace ':' by _. \$\endgroup\$ – Zgarb Aug 15 '16 at 15:40
  • \$\begingroup\$ Yes, then the code even works for arbitrary delimiters instead of just :. Thanks again! \$\endgroup\$ – Laikoni Aug 15 '16 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 '16 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\$
  • \$\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\$ – Patrick Roberts Aug 16 '16 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 '16 at 7:44
  • \$\begingroup\$ @Neil you can copy from log input instead of output \$\endgroup\$ – ASCII-only Aug 16 '16 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 '16 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\$
  • \$\begingroup\$ Does the - not count towards your score? Hrm. Interesting... Good answer! \$\endgroup\$ – MayorMonty Aug 15 '16 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 '16 at 18:17
  • \$\begingroup\$ @Neil Ahh, that makes sense \$\endgroup\$ – MayorMonty Aug 15 '16 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 '16 at 18:38
  • \$\begingroup\$ Here is a 32 + 1: s/.*\K(1\?(.)..|0\?..)/\2/&&redo \$\endgroup\$ – Mitch Schwartz Aug 15 '16 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\$
  • \$\begingroup\$ Your answer may be a function — you can remove the second line. \$\endgroup\$ – Lynn Aug 15 '16 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\$ – Mitch Schwartz Aug 15 '16 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\$ – Mitch Schwartz Aug 15 '16 at 20:12
  • \$\begingroup\$ Thanks @MitchSchwartz, pretty much parse from right, instead of left, gotcha \$\endgroup\$ – WorldSEnder Aug 15 '16 at 21:17
  • 1
    \$\begingroup\$ Otherway, left instead of right, ~~~ \$\endgroup\$ – WorldSEnder Aug 15 '16 at 21:27
1
\$\begingroup\$

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

:
s,(.*)1\?(.):.,\1\2,
s,(.*)0\?.:,\1,
t
\$\endgroup\$
  • \$\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 '16 at 20:48
  • \$\begingroup\$ @Neil, you could be right, but I can't figure out how to make it work. \$\endgroup\$ – Riley Aug 15 '16 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\$ – Mitch Schwartz Aug 15 '16 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 '16 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\$ – Mitch Schwartz Aug 15 '16 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\$
  • \$\begingroup\$ You don't need to capture the first character in the 0 case, that saves you 5 bytes. \$\endgroup\$ – Neil Aug 16 '16 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.