4
\$\begingroup\$

Objective

Given an expression involving ternary values, evaluate it into a ternary value.

Ternary Values

The three truth values in question are the values of Haskell's Ordering, namely LT, EQ, and GT. They stand for "less-than", "equal-to", and "greater-than", respectively. Furthermore, they themselves have an order; LT is the least, and GT is the greatest.

Operators

The binary operators for the ternary values are Haskell's min, max, compare, and (<>), all instantiated for Ordering. They're defined as:

min|LT EQ GT
---|--------
LT |LT LT LT
EQ |LT EQ EQ
GT |LT EQ GT
max|LT EQ GT
---|--------
LT |LT EQ GT
EQ |EQ EQ GT
GT |GT GT GT
compare|LT EQ GT
-------|--------
  LT   |EQ LT LT
  EQ   |GT EQ LT
  GT   |GT GT EQ
(<>)|LT EQ GT
----|--------
 LT |LT LT LT
 EQ |LT EQ GT
 GT |GT GT GT

I/O Format

Flexible. You may represent the values and the operators in an arbitrary way. In particular, the expression may be in Polish notation.

Examples

Here, the shorthands are T for LT, 0 for EQ, 1 for GT, & for min, | for max, c for compare, and s for (<>). The expressions are in Polish notation.

Expression, Evaluation

c01, T
sT1, T
|0&1T, 0
|&1T0, 0
s0s00, 0
s0s01, 1
sTcTT, T
cs10T, 1
cs01&|01T, 1
\$\endgroup\$
3
  • \$\begingroup\$ Can I take a fully parenthesized infix expression as input, such as "(0 | (1 & T))"? \$\endgroup\$
    – Bubbler
    Commented Mar 15 at 2:28
  • \$\begingroup\$ @Bubbler Yes, of course. \$\endgroup\$ Commented Mar 15 at 2:37
  • \$\begingroup\$ I think this is similar to Kleene's 3VL system. \$\endgroup\$
    – qwr
    Commented Mar 16 at 4:27

8 Answers 8

7
\$\begingroup\$

Vyxal 3, 1 byte

Ė

Try it Online!

Accepts input in reverse polish notation with LT represented by 1N, EQ represented by 0, and GT represented by 1. min is g, max is G, compare is , and <> is .

These operators are, respectively, min, max, difference into sign, and logical or, which is all these really are when we represent them like such.


As much as this feels like cheating, if I were required to follow the test cases' format I think the easiest method is probably to convert from prefix to postfix notation, map the characters to the above strings, and then evaluate, which is really not any more interesting in my opinion.

That said, here's a method without evaluate, though I honestly find it less clever because it's just trivial implementation. It takes the input like in the test cases but still in reverse polish notation because inverting it is already a different challenge.

Vyxal 3, 59 bytes

Ṛ0Ḣ&Ṛ₳:"01T"$c["01"$Ḟ&|$ṫ$ṫ$^"&|cs"$ḞᵈgᵈGᵉ-±ᵈ∨;JJiĖ&)"01T"i

Try it Online! (link is to literate version)

Here's a brief explanation of how this works:

Ṛ0Ḣ&Ṛ                  sets up [[], ...] containing the input
₳ ... )                reduce (so each time we take the list and one character)
  :"01T"$c             check if the character is one of 0, 1, or T
  [ ... | ...          IF-ELSE
    "01"$Ḟ&            if so, then just append it (-1 for T)
    ...                else:
      $ṫ$ṫ$^           pop the last two off the list and reorder the stack
      "&|cs"$Ḟ         find the character in "&|cs"
      ᵈgᵈGᵉ-±ᵈ∨;JJiĖ&  index into a list of the aforementioned functions
"01T"i                 finally, index into "01T" to format the output

Although this uses Ė, that's just to execute the function. It isn't being used as eval here; Vyxal just overloads that character to mean many things.

\$\endgroup\$
4
\$\begingroup\$

Python 2, 52 bytes

f=lambda s:s.pop(0)(f(s),f(s))if 1<s[0]else s.pop(0)

Attempt This Online!

Takes input in Polish notation with the following mapping:

LT -> -1
EQ -> 0
GT -> 1

min -> min
max -> max
compare -> cmp
(<>) -> int.__or__
\$\endgroup\$
4
\$\begingroup\$

Retina 0.8.2, 88 bytes

{`(?=(S.?L|S.?E?|B.?G|B.?E?|OE?.|CE.|CLG|CGL)(?<=(.))).[GEL]{2}
$2
CGE
L
CLE
G
CLL|CGG
E

Try it online! Link includes test cases. Key: L - LT; E - EQ; G - GT; S - min; B - max; C - compare, O - (<>). Note that Cs operands are reversed (test cases have been adapted accordingly). Explanation:

{`

Repeat until no more operators can be reduced.

(?=(S.?L|S.?E?|B.?G|B.?E?|OE?.|CE.|CLG|CGL)(?<=(.))).[GEL]{2}
$2

Look for an operator followed by two operands, where one of the operands is also the result, in which case replace the trio with that operand.

CGE
L
CLE
G
CLL|CGG
E

Replace trios where the result does not match any of the operands.

  • S.?L: min when at least one operand is L is that operand, otherwise
  • S.?E?: min of two non-L operands is E if it is either operand otherwise it is an operand (they are both G at this point)
  • B.?G: max when at least one operand is G is that operand, otherwise
  • B.?E?: max of two non-G operands is E if it is either operand otherwise it is an operand (they are both L at this point)
  • OE?.: (<>) of E with anything is the second operand otherwise it is the first operand
  • CE.: Reversed compare of E with anything is the second operand
  • CLG: Reversed compare of L with G is G
  • CGL: Reversed compare of G with L is L
\$\endgroup\$
2
\$\begingroup\$

APL(Dyalog Unicode), 1 byte SBCS

Try it on APLgolf!

Takes input as a parenthesized infix expression. This does feel a bit like cheating...

Uses this mapping:

LT -> ¯1
EQ -> 0
GT -> 1

min -> ⌊
max -> ⌈
compare -> (×-)
(<>) -> {⍺=0:⍵⋄⍺}
\$\endgroup\$
2
\$\begingroup\$

JavaScript (Node.js), 103 bytes

x=>x.map(i=>a.push(i<2?i:[p=>p<q?p:q,p=>p<q?q:p,p=>(p>q)-(q>p),p=>p||q][i-2](a.pop(q=a.pop()))),a=[])|a

Try it online!

const SSS = 5 mean <>

Reverse Polish Notation


JavaScript (Node.js), 64 bytes

-2B from tsh

eval
with(Math)M=max,m=min,T=-1,S=(a,b)=>a||b,C=(a,b)=>sign(a-b)

Try it online!

\$\endgroup\$
5
  • \$\begingroup\$ Second answer is invalid, since evaluation returns -1 and not T. \$\endgroup\$ Commented Mar 15 at 5:05
  • \$\begingroup\$ *whereas input uses T \$\endgroup\$ Commented Mar 15 at 5:21
  • \$\begingroup\$ @Mukundan314 Does removing definition of T fix it? \$\endgroup\$
    – l4m2
    Commented Mar 15 at 5:45
  • \$\begingroup\$ Probably, but if using multiple characters for a value is fine, you can also probably do the same for the operators in which cause you only need to define S and C \$\endgroup\$ Commented Mar 15 at 5:48
  • \$\begingroup\$ with(Math)M=max,m=min,T=-1,S=(a,b)=>a||b,C=(a,b)=>sign(a-b) \$\endgroup\$
    – tsh
    Commented Mar 19 at 7:42
1
\$\begingroup\$

Charcoal, 55 bytes

FA≡ιS⊞υ⌊E²⊟υB⊞υ⌈E²⊟υC⊞υ⁻›§υ±¹§υ±²‹⊟υ⊟υO⊞υ⊟ΦE²⊟υ∨κλ⊞υιIυ

Try it online! Link is to verbose version of code. Takes input as a list in reversed Polish with reversed arguments, i.e. the entire Polish is simply reversed. Key: -1 - LT; 0 - EQ; 1 - GT; S - min; B - max; C - compare, O - (<>). Explanation:

FA≡ι

Loop over the input list and switch over each element.

S⊞υ⌊E²⊟υ

Handle S by pushing the minimum of the top two values to the stack.

B⊞υ⌈E²⊟υ

Handle B by pushing the maximum of the top two values to the stack.

C⊞υ⁻›§υ±¹§υ±²‹⊟υ⊟υ

Handle C by comparing the top two values. (This is tricky when I don't have a comparison operator.)

O⊞υ⊟ΦE²⊟υ∨κλ

Handle O by pushing the first non-zero value of the top two values, if any. (I can't use Or itself because it's short-circuiting and would not remove the second value if the first was non-zero.)

⊞υι

Just push any other values to the stack.

Iυ

Output the final stack (which should hopefully be just one value at this point).

\$\endgroup\$
1
\$\begingroup\$

Uiua 0.10.0, 7 bytes

quote^!

Try on Uiua Pad!

This is a macro that takes a string in reverse Polish notation and outputs the result. We use the mapping:

  • GT -> 1
  • EQ -> 0
  • LT -> ¯1 (or `1)
  • min -> ↧ (or min)
  • max -> ↥ (or max)
  • comp -> ¯±- (or `sig-)
  • (<>) -> ±++. (or sig++.)

Similar to the Vyxal solution, this evaluates the given string as code. We have to use a macro rather than the 6-byte function quote∘ since quote's function cannot take input by default. As you can see, the entire code and test cases can be written entirely in ASCII, which is rare for Uiua.

\$\endgroup\$
1
\$\begingroup\$

Scala 3, 157 bytes

A port of @Mukundan314's Python 2 answer in Scala.


Golfed version. Attempt This Online!

type Q=(Int,Int)=>Int
def f(s:Seq[_]):(Seq[_],Int)=s match{case(q:Q)::t=>val(r1,r2)=f(t);val r3=f(r1);(r3._1,q(r2,r3._2));case v::t=>(t,v.asInstanceOf[Int])}

Ungolfed version. Attempt This Online!

object Main {
  // Function type for operations
  type Op = (Int, Int) => Int

  def main(args: Array[String]): Unit = {
    // Define the recursive function `f`
    def f(s: List[Any]): (List[Any], Int) = s match {
      case (op: Op) :: tail =>
        val (rest1, result1) = f(tail)
        val (rest2, result2) = f(rest1)
        (rest2, op(result1, result2))
      case value :: tail => (tail, value.asInstanceOf[Int])
    }

    // Define the mappings (functions) for clarity
    val m: Op = (x, y) => Math.min(x, y)
    val M: Op = (x, y) => Math.max(x, y)
    val c: Op = (x, y) => x.compareTo(y)
    val s: Op = (x, y) => x | y

    // Examples of using the function `f`
    println(f(List(c, 0, 1))._2)
    println(f(List(s, -1, 1))._2)
    println(f(List(M, 0, m, 1, -1))._2)
    println(f(List(M, m, 1, -1, 0))._2)
    println(f(List(s, 0, s, 0, 0))._2)
    println(f(List(s, 0, s, 0, 1))._2)
    println(f(List(s, -1, c, -1, -1))._2)
    println(f(List(c, s, 1, 0, -1))._2)
    println(f(List(c, s, 0, 1, m, M, 0, 1, -1))._2)
  }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.