Well that's odd... no wait, that's even!

Question

Preamble

Integers are always either even or odd. Even integers are divisible by two, odd integers are not.

When you add two integers you can infer whether the result will be even or odd based on whether the summands were even or odd:

• Even + Even = Even
• Even + Odd = Odd
• Odd + Even = Odd
• Odd + Odd = Even

Likewise, when you multiply two integers you can infer whether the result will be even or odd based on whether the factors were even or odd:

• Even * Even = Even
• Even * Odd = Even
• Odd * Even = Even
• Odd * Odd = Odd

Thus, if you know the evenness or oddness of all the variables in a math expression that only involves addition and multiplication, you can infer whether the result will be even or odd.

For example, we can confidently say that (68 + 99) * 37 results in an odd because an even plus an odd (68 + 99) is an odd, and that odd times another odd (odd * 37) gives an odd.

Challenge

Write a program or function that takes in a string only containing the four characters eo+*. This string represents a mathematical expression given in prefix notation involving only addition (+) and multiplication (*). Each e represents some arbitrary even number, and each o represents some arbitrary odd number.

Your task is to simplify the expression, printing or returning a single e or o based on whether the result of the expression is even or odd.

You can assume that the input will always be in valid prefix notation. Specifically, each + and * will always have two corresponding operands occurring after it. These operands may be a single e or o, or another + or * expression that in turn has operands.

For example, the input *+eoo could be read as mul(add(e, o), o), or (e + o) * o in normal infix notation. The e and the first o are the operands corresponding to the +, and +eo and the last o are the operands corresponding to the *.

Just to make it clear, here are some invalid inputs that have incorrect prefix notation:

eo
ooe
o+e
ee*
+*oe
+e*o

A single trailing newline in the output is fine, but otherwise a plain e for even or o for odd is all that should be output.

The shortest code in bytes wins.

Test Cases

^{(Empty lines are only to help visually separate similar cases.)}

e -> e
o -> o

+ee -> e
+eo -> o
+oe -> o
+oo -> e
*ee -> e
*eo -> e
*oe -> e
*oo -> o

+e+ee -> e
+e+eo -> o
+e+oe -> o
+e+oo -> e
+e*ee -> e
+e*eo -> e
+e*oe -> e
+e*oo -> o

+o+ee -> o
+o+eo -> e
+o+oe -> e
+o+oo -> o
+o*ee -> o
+o*eo -> o
+o*oe -> o
+o*oo -> e

*e+ee -> e
*e+eo -> e
*e+oe -> e
*e+oo -> e
*e*ee -> e
*e*eo -> e
*e*oe -> e
*e*oo -> e

*o+ee -> e
*o+eo -> o
*o+oe -> o
*o+oo -> e
*o*ee -> e
*o*eo -> e
*o*oe -> e
*o*oo -> o

++eee -> e
++eeo -> o
++eoe -> o
++eoo -> e
++oee -> o
++oeo -> e
++ooe -> e
++ooo -> o

+*eee -> e
+*eeo -> o
+*eoe -> e
+*eoo -> o
+*oee -> e
+*oeo -> o
+*ooe -> o
+*ooo -> e

*+eee -> e
*+eeo -> e
*+eoe -> e
*+eoo -> o
*+oee -> e
*+oeo -> o
*+ooe -> e
*+ooo -> e

**eee -> e
**eeo -> e
**eoe -> e
**eoo -> e
**oee -> e
**oeo -> e
**ooe -> e
**ooo -> o

+e+e+e+ee -> e
+o+o+o+oo -> o
*e*e*e*ee -> e
*o*o*o*oo -> o
+e+o+e+oe -> e
+o+e+o+eo -> o
*e*o*e*oe -> e
*o*e*o*eo -> e
+e*e+e*ee -> e
+o*o+o*oo -> o
*e+e*e+ee -> e
*o+o*o+oo -> o

+**++*+*eeoeeooee -> e
+**++*+***eooeoeooeoe -> e
+**+***+**++**+eooeoeeoeeoeooeo -> o

+e*o*e**eoe -> e
+*e+e+o+e**eeoe -> e
**o++*ee*++eoe*eo+eoo -> o

Answer 1

CJam, 18 17 13 bytes

Thanks to aditsu for saving 4 bytes.

qW:O%eu~"eo"=

Try the test suite here. (The test suite is too long for the permalink. Just copy them from the challenge spec.)

Explanation

q     e# Read the input.
W:O   e# Push a -1 and store it in variable O.
%     e# Use the -1 to reverse the string, because CJam's stack-based nature and the
      e# commutativity of the operators means we can evaluate the code in postfix notation.
eu    e# Convert the string to upper case, turning 'e' into 'E' (a variable with even value
      e# 14) and 'o' into 'O' (which we've stored the odd value -1 in).
~     e# Evaluate the string as CJam code, leaving the result on the stack.
"eo"= e# Use the result as an index into the string "eo". CJam's indexing is cyclic so it
      e# automatically takes inputs modulo 2. Negative indices also work as expected.

Answer 2

Pyth, 16 14 bytes

@"eo".vjdXzGU9

Pyth can itself evaluate a string, that is in Pyth syntax. Therefore I replace e and o with 4 and 5. Then the evaluation will give me an even or odd number, and I can easily print the result.

Try it online: Demonstration or Test Suite

Explanation:

@"eo".vjdXzGU9   implicit: z = input string
         XzGU9   replace "e" in z with 4 and "o" with 5
       jd        put a space between each char
     .v          evaluate it (Pyth style)
@"eo"            and print "e" or "o"

Additional explanation to the replace. G is a variable initialized with the alphabet abc...xyz. U9 is the list [0, 1, ..., 8]. XzGU9 replaces the letters of the alphabet with the values of the list. So a gets replaced with 0, b with 1, ..., e with 4, ..., i with 8, j with 0, ..., and o with 5. Therefore I e gets replaced with an even number and o with an odd number. All the other replacements have no effect at all.

Answer 3

Perl, 50 45 40 characters

(39 characters code + 1 character command line option.)

1while s/\+oe|\+eo|\*oo/o/||s/\W\w\w/e/

Sample run:

bash-4.3$ echo -n '**o++*ee*++eoe*eo+eoo' | perl -pe '1while s/\+oe|\+eo|\*oo/o/||s/\W\w\w/e/'
o

Answer 4

Retina, 29 bytes

(+`\*oo|\+(eo|oe)
o
\W\w\w
e

For the convenient one file version the -s flag is used.

We swap odd expressions (*oo, +oe, +eo) to o until we can, then swap the remaining symbol-letter-letter expressions to e. We repeat this until we can and the final one letter is our output.

(This solution is similar to manatwork's Perl answer.)

Try it online! (by Dennis)

Answer 5

Python 2, 90

def f(s):i=iter(s);a=next(i);return(a>'a')*a or'oe'[f(i)==f(i)if'*'<a else'e'in f(i)+f(i)]

The iter function is a good way to make the input string into a FIFO queue which remembers how much of the string has been parsed across calls of f. It is idempotent, so it is harmless to call it again when the input is already an iterator rather than a string. The trailing half of the answer beginning with or'oe'... seems like it should be golfable, but I couldn't find anything.

-1 thanks to Sp3000.

Answer 6

Mathematica, 91 84 bytes

#//.s_:>s~StringReplace~{"+ee"|"+oo"|"*ee"|"*eo"|"*oe"->"e","+eo"|"+oe"|"*oo"->"o"}&

Looking for a way to compress this...

Answer 7

Python 2, 80 bytes

def f(s,e=0,o=1):i=iter(s);a=next(i);return(a>'a')*a or'eo'[eval(f(i)+a+f(i))%2]

This is built on feersum's very clever answer that uses an iter to implement Polish-notation operations. The new idea is to use eval to evaluate the expressions + and * with eval(f(i)+a+f(i)), where the operator a is placed infix between the recursive results. The eval uses the bindings e=0,o=1 in the optional function arguments. The output is then taken mod 2.

Answer 8

Shell + GNU utilities, 33

dc -eFo`rev|tr oe OK`2%p|tr 10 oe

Input is taken from STDIN.

This does the same trick of reversing the input and evaluating with a stack-based calculator - in this case dc. We could replace e and o with 0 and 1, but then spaces would need to be inserted to prevent greedy parsing of the digits into the incorrect numbers.

Instead e is replaced with K which is the dc command to push the current precision to the stack, which by default is 0. And o is replaced with O which is the dc command to push the current output base to the stack. This needs to be odd, so we set it to 15 with Fo before doing anything else in dc.

Then it is simply a matter of taking mod 2 and printing 2%p. The only possible values are now 0 and 1, so it doesn't matter that the output base is 15. Then tr translates back to o or e.

---

I like that if you squint your eyes, this source almost looks like dc Forever OK.

Answer 9

C, 79 bytes

Straightforward recursion. Relies on some (coincidental?) bitwise properties of the four allowed input characters.

f(){int c=getchar();return c&4?c:c&1?f()^f()^'e':f()&f();}main(){putchar(f());}

Answer 10

Seriously, 24 bytes

,R'2'e(Æ'1'o(Æ£ƒ'e'o2(%I

More efficient stack manipulation could probably make this shorter, but meh, I'm happy with it.

Takes input as a string, like "+*oee"

Try it online (input must be manually entered)

Explanation:

,R        get input and reverse it
'2'e(Æ    replace all "e"s with "2"s
'1'o(Æ    replace all "o"s with "1"s
£ƒ        cast as function and call
'e'o2(%I  push "e" if result is even, else "o"

Answer 11

Ruby, 61 bytes

Using recursive descent parsing and boolean algebra.

def f
gets(1)==?+?f^f : ~/\*/?f&f : $_==?o
end
puts f ? ?o:?e

The function reads one character from stdin at a time. If it reads a + or a *, it calls itself twice to determine odd or even. The function returns true for odd and false for even. The ^ XOR and & AND operators are used to determine "oddness" of addition and multiplication expressions respectively.

Here's an ungolfed version:

def f
  x = gets(1)
  case x
  when '+'
    f ^ f
  when '*'
    f & f
  else
    x == 'o'
  end
end

puts f ? 'o' : 'e'

_{Thanks @Shel for pointing out a bug in the initial version.}

Answer 12

Minkolang 0.14, 40 bytes

I tried to do a clever eval method, but it turns out that any values added to the codebox outside of the original space will never be reached by the program counter. So I did a less clever eval method. :P

$o"eo+*"r0I4-[4g1Z2*1F]l*"e"+O.
0f1f+f*f

Try it here.

Explanation

$o                                Read in whole input as characters
  "eo+*"                          Push these characters onto the stack (in reverse order)
        r                         Reverse the stack
         I4-                      Push the length of the stack - 4
            [                     For loop; pop n and repeat that many times
             4g                   Get the item at the fourth index and put it on top
               1Z                 Pops n and pushes first index of n in stack
                 2*               Multiply by 2
                   1F             Gosub; goes to codebox(2n,1) to be returned to
                     ]            Close for loop
                      l*          Multiply by 10
                        "e"+      Add 101 ("o" is 111)
                            O.    Output as character and stop.
0f1f+f*f                          Does the appropriate operation then returns to F

Answer 13

JavaScript, 110 106 94 bytes

while(i.length>2)i=i.replace(/([+*][eo]{2})/,(o,e)=>{return"+oe+eo*oo".indexOf(o)<0?"e":"o"});

Certainly not the smallest solution, but likely the smallest solution possible in a verbose language like JavaScript!

Answer 14

GNU Sed, 36

:
s/*oo\|+eo\|+oe/o/
t
s/\W\w\w/e/
t

After posting I saw this exactly the same approach as @manatwork's Perl answer and @randomra's Retina answer. So I guess I may as well go all the way and borrow their \W\w\w as well.

Thanks to @Ruud for shaving off 4 bytes.

Answer 15

O, 24 20 19 18 bytes

i`2:e;1:o;~2%'o'e?

Takes input, reverses it, assigns e to 2 and o to 1 and posts it to Tumblr evaluates it as O code.

Explanation:

i`     Get input and reverse it, because O uses postfix notation
2:e;   Assign `e` to 2
1:o;   Assign `o` to 1
~2%    Eval and check if result is even
'o'e?  Output 'e' if even, 'o' if odd

Answer 16

Haskell, 160 bytes

Call f.

f=until((==1).l)r
r s|l s<3=s|3#s?o=r('o':3%s)|3#s?sequence["+*","oe","oe"]=r('e':3%s)|0<1=1#s++r(1%s)
l=length
(#)=take
(%)=drop
(?)=elem
o=["+eo","+oe","*oo"]

Answer 17

JavaScript, 92 71 bytes

f=i=>i>"0"?i:f(i.replace(/.[eo]{2}/,e=>"eo"[eval((e[1]>"e")+"^&"[+(e[0]<"+")]+(e[2]>"e"))]))

It's a bit obfuscated, but I wanted to do something using eval and bitwise operators. Annotated:

f = (i) => // function(i) { return
    i>"0"  // i[0] == "o" || i[0] == "e" :-) - the characters `*` and `+` are both <"0"
      ? i  // finish
      : f(i.replace( // recursively repeat with
          /.[eo]{2}/, // first occurrence of "something" followed by two values
          (e) =>    // replaced by
              "eo"[ // string indexing
                eval(
                    (e[1]>"e")        // e[1] == "o" ? "true" : "false"
                  + "^&"[+(e[0]<"+")] // e[0] == "+" ? "^" : "&"
                  + (e[2]>"e")        // e[2] == "o" ? "true" : "false"
                )
              ]     // like eval(…) ? "o" : "e"
        ))

The repetition of (e[…]>"e") annoys me a bit, but the following is not better either (103 bytes):

f=i=>i>"0"?i:f(i.replace(/e|o/g,x=>+(x>"e")).replace(/.\d\d/,e=>"eo"[eval(e[1]+"^&"[+(e[0]<"+")]+e[2])]))

So in the end, @Arkain's approach with simple substring matching is superiour. Made into a function, with some optimisations:

f=i=>i>"0"?i:f(i.replace(/.[eo]{2}/,v=>"eo"[+"+oe+eo*oo".includes(v)]))

Answer 18

Dart, 173 bytes

f(i){var l=i.split(''),e='e',o='o';g(p){if(l[p]!=e&&l[p]!=o){var x=p+1,y=p+2;g(x);g(y);l[p]=l[p]=='+'?l[x]!=l[y]?o:e:l[x]==o?l[y]:e;l.removeRange(x,p+3);}}g(0);print(l[0]);}

This isn't competitive, but whatever. The gist of the solution is, starting at 0, recursively replace every operator with the evaluation the pair of characters following that operator and then remove those characters from the list.

Answer 19

Haskell, 231 bytes

Here is an approach using a serious language ;)

Golfed version:

p(s:_)[]=s
p s(x:y)=p(r$x:s)y
r[]=[]
r('e':'e':'+':x)=r$'e':x
r('e':'o':'+':x)=r$'o':x
r('o':'e':'+':x)=r$'o':x
r('o':'o':'+':x)=r$'e':x
r('e':'e':'*':x)=r$'e':x
r('e':'o':'*':x)=r$'e':x
r('o':'e':'*':x)=r$'e':x
r('o':'o':'*':x)=r$'o':x
r x=x

Example:

*Main> p [] "+**+***+**++**+eooeoeeoeeoeooeo"
'o'

Ungolfed and pretty comprehensive version:

type Stack = String

parse :: String -> Char
parse = parse' []

parse' :: Stack -> String -> Char
parse' (s:_) []     = s
parse' s     (x:xs) = parse' (reduce $ x:s) xs

reduce :: Stack -> Stack
reduce [] = []
reduce ('e':'e':'+':xs) = reduce $ 'e':xs
reduce ('e':'o':'+':xs) = reduce $ 'o':xs
reduce ('o':'e':'+':xs) = reduce $ 'o':xs
reduce ('o':'o':'+':xs) = reduce $ 'e':xs
reduce ('e':'e':'*':xs) = reduce $ 'e':xs
reduce ('e':'o':'*':xs) = reduce $ 'e':xs
reduce ('o':'e':'*':xs) = reduce $ 'e':xs
reduce ('o':'o':'*':xs) = reduce $ 'o':xs
reduce xs               = xs

Example:

*Main> parse "+**+***+**++**+eooeoeeoeeoeooeo"
'o'

Features: Pattern matching and recursion.

Answer 20

Jolf, 11 bytes

(Noncompetitive, as the language postdates the question.) Try it here!

FVyAi"oe"@\x12

(Replace \x12 with the actual character \x12. This should be done automatically in the interpreter.)

Explanation:

FVyAi"oe"@\x12
    i          input
          \x12 character 12
         @     char code at
   A "oe"      replace all os with 1s and all es with 2s
  y            eval as jolf, returning the answer
 V             return parity "even" or "odd"
F              get first character
               implicit output

Answer 21

Python 3, 171 145 135 bytes

Not competitive, but I had fun doing it, so I just couldn't keep it to myself. Unlike the (very clever) recursive-iterator Python entry by feersum, this one reverses the input and then does a good old stack-based parsing of reverse Polish notation.

def p(i):
 s=[]
 for c in i[::-1]:
  s+=[c>'e'if c>'a'else getattr(s.pop(),'__'+('axnodr'[c>'*'::2])+'__')(s.pop())]
 return'eo'[s[0]]

Answer 22

Haskell, 98 94 bytes

Sorry to bother you with yet another Haskell attempt; just wanted to prove it is very well possible in less than 100 bytes.

p(c:s)|any(<'a')s=p(c:p s)
p('+':x:y:s)|x/=y='o':s
p('*':'o':s)=s
p(c:_:_:s)|c<'a'='e':s
p s=s

Defines a function p that accepts any valid expression as parameter, and returns the result as a string of length 1.

Example:

*Main> p "**o++*ee*++eoe*eo+eoo"
"o"

The function works by repeatedly reducing the rightmost operator in the string until no operators are left.

Answer 23

Add++, 46 bytes

D,g,@,d"oe"$eA"e"=+o
D,f,@,bR€gbU32CjbV2%"eo":

Try it online!

The footer simply enumerates all the example inputs and their corresponding outputs.

How it works

Like a lost of the answers here, this uses replacement and evaluation. Our main function is f, and g is a helper function. We'll use "*e*o*e*oe" (which is e) as an example.

f begins by taking the input string and reversing it, yielding "eo*e*o*e*". We then map g over each element:

g starts by duplicating the argument, to keep a copy until the final command. We then check if the argument is in the string "oe", yielding 1 for letters and 0 for * or +. We then push the argument again and check whether it is equal to "e". This result is then added to the previous check. This yields 0 for either * or +, 1 for o and 2 for e. We then take the logical OR between this value and the argument. If the value is 0, it is replaced by the argument (i.e. * or +), otherwise it is left as-is (i.e. 1 and 2).

This converts all letters in the reverse of the input into a numerical value. We then join each element by spaces, to ensure digits aren't concatenated. For our example, this yields the string "2 1 * 2 * 1 * 2 *". We can then evaluate this, using Add++'s postfix notation, yielding 8. We then take the parity of this value, yielding either 0 for even numbers and 1 for odd numbers, before indexing into the string "eo" and returning the corresponding letter.