# Evaluate left-or-right

Originally sandboxed by @xnor

Left-or-right is a very simple language @xnor made up. Its expressions are made of arrows < (left), > (right), and parentheses. The goal is to evaluate an expression to either < or >.

An expression A<B picks the left item A, while A>B picks the right one B. Think of < and > as arrows pointing to the item we want, not as comparison operators.

Take, for example, ><>. The operator in the middle is <, and confusingly, the items on each side A and B are also arrows. Since the operator tells us to take the left one A, which is >. So, ><> equals >.

Expressions also nest. We can replace the expression with its value. So, for example, (><>)<< equals ><< equals >. And, >(><>)< equals >>< equals <. For another example, (><>)(<<<)(>><) equals ><< equals >.

In the input, you'll be given a well-formed expression consisting of either a trio of arrows like ><> or the result of repeatedly replacing some arrow by a trio of arrows in parens like ><(><>) . You can assume the input won't already be a lone arrow. You may alternately accept the whole inputs encased in parens like (><>) or (<(><>)>).

The input is given as a flat string consisting of symbols <>(). You may not take it in a pre-parsed form like a tree.

The shortest code in bytes wins.

## Test cases

Generated using this script.

### Evaluates to <

>><
<<(<><)
(>>>)><
(<(<<>)(<<<))<<
((>(>><)>)(><>)>)><
(<<(>(<>>)<))((><>)(><<)>)(<<<)
((<<<)<>)((>><)<(<><))((>>>)<<)
>(>((><>)<>)(<>>))((>><)((><>)<<)<)
((><<)(><<)(<<>))(<(>><)(>><))(<<(<<>))
(<(><<)(>(>>>)>))((>>>)>>)((<>(>><))<<)


### Evaluates to >

<>>
((<<<)>(<<>))(><<)>
((>>>)<>)<((<<<)>>)
>(>>(<<<))(>((<>>)<<)<)
((><>)(<<>)>)(<<(<<<))(<(>>>)<)
(><((><>)><))(>(>>(>>>))(<><))(>>>)
(((>><)<>)(><>)(><>))(<<(<>>))(<<>)
((><>)<(<<(<<>)))((<(<<>)<)(<><)>)(>>>)
(<<(<><))(((<>>)><)(><<)(><>))(<(><>)>)
((>>>)<<)(<(<><)<)((<<(<<<))>(>(><>)<))

• Is a single > valid input? And maybe also (>)(<)(>)? – tsh Feb 5 at 1:50
• @tsh No and no. Think of it as a valid ternary tree where the leaves are one of <>, given in a linear form using parens. Also "You can assume the input won't already be a lone arrow." – Bubbler Feb 5 at 1:57
• Is there an original post or other resource by @xnor introducing left-or-right that you can link to? – Oliphaunt - reinstate Monica Feb 7 at 9:12
• @Oliphaunt It's the linked sandbox post at the top, though it's deleted now (only 10k+ rep users can view). – Bubbler Feb 7 at 12:11
• Thanks for bringing this challenge to life! Might you be interested in any of the other Sandboxed challenges I have lying around? – xnor Feb 11 at 22:50

# JavaScript (Node.js), 50 bytes

f=a=>a[1]?f(a.replace(/$$(.>)?(.)(<.)?$$/,'$2')):a  Try it online! Repeat apply regex replace until only 1 char left. The regex /$$(.>)?(.)(<.)?$$/ get the calculate result as 2nd capturing group. Save 1 byte, thanks to Arnauld ## x86-16 machine code, 3126 22 bytes Saved 5 bytes thanks to @Bubbler. Saved 4 bytes thanks to @640KB. 0000:0000 AC 3C 29 74 03 50 EB 0A-5A 58 3C 3E 58 74 01 92 .<)t.P..ZX<>Xt.. 0000:0010 58 52 E2 EC 58 C3 XR..X.  Callable function. Expects SI = address of code, CX = length of code. Expects the code to be enclosed in (...): You may alternately accept the whole inputs encased in parens like (><>) or (<(><>)>). Returns the output at AL. Disassembly:  LOOP: ; Main loop: AC LODSB ; AX = [SI++] 3C29 CMP AL, ')' ; AX == ')'? 7403 JZ BRACE ; * If so, jump to 'BRACE' PUSHSTH: ; Otherwise... 50 PUSH AX ; * Push AX onto stack EB0A JMP END ; * Jump to 'END' BRACE: ; If AX == ')'? 5A POP DX ; * pop TOS to DX ; * (So DX is now the rightmost angle brace) 58 POP AX ; * pop TOS to AX ; * (So AX is now the middle angle brace) 3C3E CMP AL,'>' ; * Compare current AL with '>' (result stored in PSW) 58 POP AX ; * AX = left argument 7401 JZ RAB ; * If prev. value of AL == '>', jump to 'RAB' LAB: ; * Handle prev. value of AL == '<': 92 XCHG DX,AX ; * DX = left argument instead RAB: ; Now, DX is the chosen value. 58 POP AX ; * Discard TOS (which is an excess '(') 52 PUSH DX ; * Push DX onto stack END: ; Finally, E2EC LOOP LOOP ; * Loop the above CX times 58 POP AX ; Pop TOS to AX C3 RET ; Return to caller  • Good old stack-based expression evaluation, in one loop. Btw, can't you change ADD SP,2 to, say, POP BX? – Bubbler Feb 5 at 7:59 • @Bubbler You're right! Silly me. :) – user99151 Feb 5 at 8:00 • Hmm now I see what you mean about output at top of the stack. Unfortunately I don't think this is okay by the rules since you're now leaving things on the stack and SP not preserved - that RET will not actually return to caller. Specifically ESP/RSP must be call-preserved and x87 st0 is reasonable, but returning in st3 with garbage in other x87 register isn't. The caller would have to clean up the x87 stack. If it's too costly to unwind the stack in the code, maybe save SP in the beginning and restore SP at the end? – 640KB Feb 5 at 17:47 • @640KB Hopefully fixed. – user99151 Feb 6 at 2:43 # APL (Dyalog Extended), 30 23 bytes (⍎'(⊣⊢)'['(<>'⍳⍞])/'<>' '(<>'⍳⍞ take the input ⍞ and get the indices of '(<>' this fills with the last index + 1 if not found, saving 1 char '(⊣⊢)'[ stuff ] index into '(⊣⊢)', replacing <> with ⊣⊢, the left and right tack functions ⍎ evaluate this as a train APL trains of the form (f g h) when applied to left and right arguments x and y produce (x f y) g (x h y) This translates directly to this language Replacing <> with ⊣ and ⊢ which do the same thing, the input becomes a valid function in APL ( train )/'<>' Reduce over '<>', which uses '<' as a left argument and '>' as a right one  Try it online! # Retina 0.8.2, 22 bytes {$$(.>)?(.)(<.)?$$$2


Try it online!

Basically the port of my JavaScript answer in Retina. I just learnt how to write loop in past 10 minutes and got this.

{$$$$ loops the replace until nothing changed. The replacement calculate one step each time.

• For a single-stage loop you should prefer + rather than {. – Neil Feb 5 at 10:56
• Thanks for pointing out the + loop. I just find the { trick by searching "retina loop" on ppcg. I didn't ever know the + way. Since switching to + won't help me save a single byte, I would leave it as is... – tsh Feb 7 at 1:34

# J, 30 bytes

')/''<>'''".@,~'(',rplc&'<[>]'


Try it online!

Very similar to rak1507's APL answer, though I had the idea independently -- it's natural for J, though loses some elegance because of the quote escaping.

• rplc&'<[>]' replace <> with [], which in J are the "left" and "right" identity operators, meaning they return the left or right argument.
• ( Prepend a left paren to that result.
• ')/''<>'''...,~ Append )/'<>' to the previous result.
• Now we have ( ~~input with [] instead of <>~~ )/'<>'.
• Which is the same as: '<' ( ~~input with [] instead of <>~~ ) '>'
• ".@ Evaluate that string. From here, J trains and the definition of [ and ] do exactly what we want.

# Perl 5-p, 32 bytes

s/$$(.>(.)|(.)<.)$$/$2$3/g&&redo


Try it online!

Takes advantage of the spec allowing outside parentheses to be required.

• Drop the g to save a byte, then that allows you to use . instead of $$ to save another byte. – Neil Feb 6 at 1:08 # Red, 136120 86 bytes This version is courtesy @hiimboris (https://gitter.im/red/parse)! func[s][r:["<"|">"]while[parse s[to change["("x: r["<"r |">"x: r]")"](x/1)to end]][]s]  Try it online! • Beautiful, someone is using Red! What do you think about suggesting it for LotM? – Wezl Feb 5 at 14:28 • @Wezl Thank you! I'm affraid I'm not good at it, although I've been trying to solve some of the challenges here. About the LoTM - I don't know - I think I've only seen a single Red solution in CGCC from person other than me. – Galen Ivanov Feb 5 at 14:33 • Then there are at least two people who use it, which is enough, and a lot more who can be introduced. – Wezl Feb 5 at 14:35 • ok it's posted, but feel free to edit it because I don't have much experience with Red, and probably missed lots. – Wezl Feb 5 at 15:17 • I've been using Rebol/Red on and off for a few months now, good to see interest in it! – Razetime Feb 5 at 17:24 # C (gcc), 117 $$\\cdots\$$ 101 98 bytes Saved 10 bytes thanks to an idea from Davide!!! Saved 3 bytes (and got below 100!) thanks to ceilingcat!!! i;f(char*p){for(i=0;*p++-40||p[3]-41;++i);p[-1]=p[p[1]-62?0:2];bcopy(p+4,p,strlen(p));i&&f(p+~i);}  Try it online! Takes an input string with enclosing parentheses and reduces it to either a left (<) or a right (>). ### Explanation (before some golfs) i;f(char*p){ // function taking a string parameter p for(i=0;p[i++]-40||p[i+3]-41;); // loop until we find chars '(' and ')' // separated by 3 characters. // since our input is enclosed in // parentheses we will always find one. p[i-1]= // i has gone forward one but set the // first of these characters - the '(' // to... p[i+1]-62? // ...depending on whether the middle // char is a '<' or a '>'... p[i]: // ...the one before the middle if '<' p[i+2]; // ...the one after the middle if '>' memcpy(p+i,p+i+4,strlen(p)); // move the back end of the string forward // over the other 4 chars. // now a "(A<B)" is reduced to "A" // and a "(A>B)" is reduced to "B" ~-i&& // if we didn't just reduce the start of p f(p); // then recursively call f. // otherwise p is reduced to the answer // and we're done. }  • You can save 9 bytes by incrementing the pointer in the loop. The link to the TIO doesn't fit in a comment so I am going to put it as an edit. Also check the second code that is even shorter but doesn't work and I don't know why: I just moved i++ to the end of the loop and swapped ~-i with i – Sheik Yerbouti Feb 5 at 18:05 • @Davide The first one core dumps and the second doesn't work either. It's a golf why the i++ is where it is. – Noodle9 Feb 5 at 18:21 • @Davide That 3rd suggestion doesn't work either. – Noodle9 Feb 5 at 18:23 • For me it works, I don't know maybe there was something wrong with the link, just copy/paste this code i;f(char*p){for(i=0;i++,*p++-40||p[3]-41;);p[-1]=p[1]-62?*p:p[2];memcpy(p,p+4,strlen(p));~-i&&f(p-i);} – Sheik Yerbouti Feb 5 at 18:30 • @Davide Yeah, i lags behind the pointer bumps by one. I just re-wrote it with your idea of bumping the pointer and having i keep track of where the string starts. – Noodle9 Feb 5 at 18:48 # Jelly, 17 bytes “)ɗ<ḷ>ṛ( ”y;”/vØ<  Try it online! Same essential approach as rak1507's APL answer. Requires the input fully parenthesized. “ ”y Replace ) ) with ɗ last-three-links-as-dyad, < < with ḷ return-left-argument-and-ignore-right, > > with ṛ return-right-argument-and-ignore-left, ( and ( with a space which is essentially ignored. ;”/ Append the reduce quick, v and evaluate the result as a monad with argument Ø< "<>".  • Thought someone would do this, as Jelly has the right built-ins for everything. (I was wondering why there's no > at the end, until I realized Ø< is a built-in for the two chars <>.) – Bubbler Feb 5 at 3:28 # Python 3, 98 74 bytes Saved a whopping 24 bytes thanks to ovs!!! import re f=lambda p:p[1:]and f(re.sub('\(((.)<.|.>(.))$$',r'\2\3',p))or p


Try it online!

Takes an input string with enclosing in parentheses and returns whether it's left (<) or right (>).

• 74 bytes – ovs Feb 5 at 9:27
• @ovs Nice ones - thanks! :D – Noodle9 Feb 5 at 11:12

# 05AB1E, 20 bytes

Δ„<>3ã€…(ÿ)¬¦¨ºĆ'>ª:


Takes the input wrapped in parenthesis in both programs, as is allowed.

# 05AB1E (legacy), 20 bytes

'<∞©3ãε…(ÿ)}¬®Ã∞®«S:


Should have been 19 bytes by also using €…(ÿ), but apparently there is a bug in the legacy version, so we'll have to use ε…(ÿ)} (or '(ì')«) instead.

Explanation:

Δ                     # Continue until it no longer changes, using the (implicit) input:
„<>                  #  Push string "<>"
3ã                #  Create all possible triplets of these two characters:
#   ["<<<","<<>","<><","<>>","><<","><>",">><",">>>"]
€               #  Map over each string in the list
…(ÿ)           #   And wrap it in parenthesis
¬          #  Get the first item (without popping the list): "(<<<)"
¦¨        #  Remove its first/last characters: "<<<"
º       #  Mirror it: "<<<>>>"
Ć      #  Enclose; appending its own head: "<<<>>><"
'>ª  '#  Convert it to a list of characters, and append ">":
#   ["<","<","<",">",">",">","<",">"]
:  #  Replace all ["(<<<)",...,"(>>>)"] with ["<",...,">"]
# (after the loop, the result is output implicitly)

'<∞                  '# Push "<" and mirror it to "<>"
©                  # Store this string in variable ® (without popping)
3ãε…(ÿ)}¬         # Same as above
®Ã       # Only keep the characters that are also in ®, removing the "()"
∞      # Mirror it: "<<<>>>"
®«    # Append ®: "<<<>>><>"
S   # Convert it to a list of characters:
#  ["<","<","<",">",">",">","<",">"]
:  # Keep replacing all ["(<<<)",...,"(>>>)"] with ["<",...,">"]
# until there is nothing more to replace
# (after which the result is output implicitly)


# JavaScript (ES6),  69  67 bytes

Saved 2 bytes thanks to @Neil

f=s=>s<(s=s.replace(/.?([<>]{3}).?/,(_,s)=>s[s[1]>'<'?2:0]))?f(s):s


Try it online!

• "You may alternately accept the whole inputs encased in parens", which should simplify the handling of the last step. – Bubbler Feb 5 at 2:03
• Save 2 bytes by using . instead of $$ and $$. – Neil Feb 5 at 17:15

# PCRE, 52 bytes

(((<|>|$$(?3){3}$$)(?=(?>(?4))?>)(?3))?($$(?1))?)(.)  Try it online! Link includes Perl 5 test harness. Does not take outer parentheses (admittedly a version that takes outer parentheses would probably be shorter.) The desired result is captured in group 5. Explanation: Group 3 matches an operator. Group 2 matches two operators, but only if the second operator evaluates to >; a recursive atomic match is used to determine whether that is true. Group 4 then recurses if the current operator is an expression. ( Group 1 is: ( Group 2, which is: ( Group 3, which is either: <|>| ... a literal < or > or... \((?3){3}$$  ... three recursive matches of group 3 inside parentheses;
)
(?=           Followed by a lookahead to:
(?>(?4))?    An optional atomic recursive match of group 4...
>            ... which must be followed by a >;
)
(?3)          Followed by another recursive match of group 3.
)?             Group 2 is optional.
(              Group 4, which is...
$$... a literal (... (?1) ... followed by a recursive match of group 1. )? Group 4 is optional. ) End of group 1. (.) Group 5 then captures the desired result.  • I've just noticed that the inputs I shamelessly stole from some other answer include the enclosing ()s, but fortunately the regex itself doesn't validate the expression and so it assumes extra <s exist where necessary, so the output is still correct. – Neil Feb 7 at 19:01 # Stax, 23 bytes ü▼2δ▀ÆH╞íqº╪ ≈♀ô☺ßX→ú  Run and debug it Uses the same regex as tsh's Javascript solution, and replaces till a fixed point is reached. ## Explanation "\((.>)?(.)(<.)?$$".$2RgiH g generator: i apply the following till invariant: "$$(.>)?(.)(<.)?$$".$2     regex replace with second capture group
H take last generated value


# Wolfram Language (Mathematica), 54 bytes

#//._[a___,"(",b_,c_,d_,")",e___]->a.If[c=="<",b,d].e&


Try it online!

Input a list of characters.

# Jelly, 15 bytes

O;1ị“/ṛ  ɗḷ”vØ<


A monadic Link accepting a list of characters*, which yields a character.

* Uses the encased in parens option.

Try it online!

### How?

Converts the input to Jelly code which will reduce the pair ['<', '>'] to produce the answer. Jelly ignores spaces and has a 1-indexed and modular index-into function, ị, so the Link starts by converting the input characters to their ordinal values and uses ị to form the code:

input character   ordinal   indexed into "/ṛ  ɗḷ"   meaning
(        40        (space)                 ignored
<        60        ḷ                       yield left argument
>        62        ṛ                       yield right argument
)        41        ɗ                       last three links as a dyadic function
(or reduce command)  1        /                       reduce by


So:

O;1ị“/ṛ  ɗḷ”vØ< - Link: list of characters   e.g. (<>>)
O               - ordinals                        [40,60,62,62,41]
;1             - concatenate a one               [40,60,62,62,41,1]
“/ṛ  ɗḷ”    - "/ṛ  ɗḷ"                        "/ṛ  ɗḷ"
ị            - index into                      " ḷṛṛɗ/"
Ø< - "<>"                            "<>"
v   - evaluate with input             '>'


The example above evaluated:

ḷṛṛɗ/ - monadic chain (with left argument ['<', '>'])
/ - reduce (['<', '>']) by - i.e. f('<', '>'):
ɗ  -   last three links as a dyad - i.e. g('<', '>'):
ḷ     -     yield left = '<'
ṛ   -     yield right = '>'
ṛ    -     (ḷ) yield right (ṛ) = '>'


# C (gcc) (no builtins), 147 143 bytes

4 bytes saved thanks to ceilingcat!

i,m,c,q,w;f(char*s){for(i=m=w=0;c=s[i]%9;i++)if(c-1?c-4?w+=w-~c%3,++m==4:(q=i,m=w=0):0)for(s[q]=w-2&&w<9?62:60;q++<i;)s[q]=1;s=*s%3-1?*s:f(s);}


Try it online!

Function that takes a null-terminated char array as input, and returns a char (int).

Here's a visualization of how it works:

(((>>>)<<)(<(<><)<)((<<(<<<))>(>(><>)<)))
((>....<<)(<<....<)((<<<....)>(>>....<)))
(>........<........(<........><........))
(>........<........<....................)
>........................................


(In the code, it uses 0x01 instead of ., but due to the modulus, they're equivalent even in data representation.)

Essentially it scans the code looking for instances of (data), where data consists of substring of 3 characters, except '.' and '('. (4, in the code, since it tracks the ) as the 4th character.) The program keeps track of the start of this string (q) and a binary representation of the visited characters (w). If we consider '>' to be equivalent to the binary 1, and '<' the binary 0, we simply look at a table of what the results of the binary strings should be. As it turns out, for q=1,4,5,6, the answer is '<', and '>' otherwise. Thus, w-1&&w<5 is a sufficient determiner. (In fact, since we keep track of ) as part of this binary string, we have to consider that everything is doubled, and for no byte cost, we can modify this formula to obtain the w-2&&w<9.)

After we determine what the result should be, we replace the initial ( with the result, and all subsequent characters with .. Then, so long as the initial character of the string is (, we repeat our function. This allows us to skip moving the string around, which, in my head, should save bytes, but I haven't tested the alternative.

Started working on this before I saw the existing (much shorter) C answer. But I enjoyed this nonetheless.

• @ceilingcat amazing, thank you! – Conor O'Brien Feb 7 at 0:37
• thanks @2x-1 :D – Conor O'Brien Feb 7 at 0:37

# Ruby, 5149 44 bytes

-1 byte thanks to Neil! (match any character . instead of the opening bracket $$) -4 bytes thanks to Dingus! (String#sub! returns nil if there was no match) Outputs by modifying the input. This would be 43 bytes with tsh's regex. ->s{s.sub!(/.((.)<.|.>(.))$$/,'\2\3')&&redo}


Try it online!

# Ruby-p, 4039 38 bytes

-1 byte thanks to Sisyphus!

sub /.((.)<.|.>(.))\)/,'\2\3'while/../


Try it online!

• Because you're using sub and not gsub you can save a byte by using . instead of $$ since the first ) must have an opening ( and your regex is fixed length. – Neil Feb 5 at 11:23 • Is the lambda version legit? The lambda itself returns nil. – Dingus Feb 6 at 21:03 • – ovs Feb 6 at 21:18 • Thanks - I must have read that before but can't recall seeing it used, so there's another trick to add to my golfing. In that case you can save 4 bytes (only on the lambda one) by replacing while s[1] with &&redo. – Dingus Feb 6 at 21:26 • For the second one you can replace _[1] with /../ for a byte saved. – Sisyphus Feb 7 at 10:14 # Charcoal, 27 bytes Ｆ⁻Ｓ(≡ι)«≔⊟υθ≡⊟υ>§≔υ±¹θ»⊞υιυ  Try it online! Link is to verbose version of code. Takes input wrapped in ()s. Explanation: Port of @2x-1's answer. Ｆ⁻Ｓ(  Remove (s from the input and loop over the remaining characters. ≡ι)«  If the current character is a ) then... ≔⊟υθ  ... pop the last character from the stack; and ... ≡⊟υ>  ... if the (second) last character was a > then... §≔υ±¹θ  ... overwrite the (third) last character with the originally popped character. »⊞υι  Otherwise push the current character to the stack. υ  Print the final remaining character. # Java (JDK), 76 bytes s->{while(s.length()>1)s=s.replaceAll("\\((.>)?(.)(<.)?\$$","\$2");return s;}


Try it online!

## Credits

• 76 bytes by porting the regex of tsh's JavaScript answer. And maybe you're missed it, but the rules allow the input to be wrapped in parenthesis: "You may alternately accept the whole inputs encased in parens" – Kevin Cruijssen Feb 5 at 13:19
• Yes, I missed it. Totally. I was wondering how their regex succeeded (because I tried porting that one regex but without wrapping in parentheses), now I know :p – Olivier Grégoire Feb 5 at 14:25

# Julia, 61 bytes

using tsh's regex

f(x,y=replace(x,r"$$(.>)?(.)(<.)?$$"=>s"\2"))=x==y ? x : f(y)


Try it online!

# APL (Dyalog Unicode), 27 bytes

'$$(.>)?(.)(<.)?$$'⎕R'\2'⍣≡


Try it online!

This is longer than rak1507's answer, but I just wanted to use a different approach. Uses the same regex as everyone else.

# Pyth, 25 bytes

u:G."(\‹Kž%<—åkí2""\\2


Try it online!

Uses the regex from tsh's Javascript answer. Replaces each match with its second matching group until a fixed point is found and printed.

# sed -r 4.2.2, 27

Using the same regex as everyone else:

:
s/$$(.>)?(.)(<.)?$$/\2/
t


Try it online!