18
\$\begingroup\$

Write code to evaluate whether a chain of inequalities is true or false. An example input is the string

3<=4!=9>3==3

This is true because each of its components is true:

(3<=4) and (4!=9) and (9>3) and (3==3)

Input:

A string that represents a chain of one or more inequalities. The allowed comparison operators are

==   equals
!=   does not equal
>    is greater than
>=   is greater than or equal to
<    is less than
<=   is less than or equal to

The allowed numbers are single-digit numbers 0 through 9. There won't be any spaces, parentheses, or other symbols.

Output:

The correctness of the inequality as a consistent Truthy or Falsey value. Consistent means every Truthy output is the same and every Falsey output is the same.

Restriction:

The intent of this challenge is for you to write code that processes the inequalities, rather than have them be evaluating them as code, even for a single inequality in the chain. As such, methods like Python's eval and exec that evaluate or execute code are banned. So are functions which look up a method or operator given its name as a string. Nor is it allowed to launching processes or programs to do the evaluation for you.

Test cases:

3<=4!=9>3==3
True

3<=4!=4
False

5>5
False

8==8<9>0!=2>=1
True
\$\endgroup\$
2
  • \$\begingroup\$ Can we accept input with Unicode inequality signs like ≤ and ≥ instead of <= and >=? \$\endgroup\$
    – FUZxxl
    Mar 5, 2015 at 12:11
  • \$\begingroup\$ @FUZxxl You can't. \$\endgroup\$
    – xnor
    Mar 5, 2015 at 21:58

10 Answers 10

8
\$\begingroup\$

Ruby, 71 + 1 = 72

With command-line flag -n, run

p (0..99).none?{|i|~/#{a=i%10}(#{%w/!=|. <?=* >?=*/[a<=>b=i/10]})#{b}/}

Generates all possible failing regular expressions, and checks whether the input string matches any of them. Outputs true if none do, else false. Takes input via STDIN, separated by newlines.

Tricks:

  • We get all possible pairs of digits by looping from 0 to 99 and extracting the 10s and 1s digits.
  • The only actual comparison we do is a<=>b, which returns -1,0,or 1 for less than, equal to, or greater. These all slice to different elements of a three-string array, finding the regular expression for comparisons that don't match.
\$\endgroup\$
1
  • \$\begingroup\$ What a clever strategy! \$\endgroup\$
    – xnor
    Mar 5, 2015 at 23:05
6
\$\begingroup\$

Perl, 82

$_=<>;($'<=>$&)-61+ord$1&&($2&&$&==$')^('$'lt$1)&&die"\n"while/\d(.)(=?)/g;print 1

Prints 1 when true and a blank line when false, since the empty string is Perl's main falsey value.

The while loop goes over the string matching the regex \d(.)(=?). Then the variables $1 and $2 correspond to the characters of the operator, and the special variables $& and $' will behave as the two operands in a numerical context. The operands are compared with <=> and the result matched against the first character of the operator. Then equality and inequality is dealt with specially.

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

CJam, 60 bytes

This code seems a bit ugly and potentially not fully optimized, but it's the best I've got so far.

Try it online.

q_A,sSer_S%@@-(])1\@z{~:X\:^i['=")<"P"(>"P'<'^'>PPP]=~e&X}/;

Explanation

q               "Read the input";
_A,sSer         "Copy the input and replace each digit with a space";
_S%             "Split around spaces to obtain the operation list";
@@-             "Remove operations from the input to obtain the operand list";
(])1\@z         "Remove the first operand from the list to be the initial left
                 operand, initialize the result to 1 (true), and pair up the
                 operations and remaining operands";
{               "For each operation-operand pair:";
  ~:X             "Let the operand be the right operand of this operation";
  \:^i            "Hash the operation (bitwise XOR of all characters)";
  [               "Begin cases:";
    '=              " 0: Equals";
    ")<"            " 1: Less than or equal to";
    P               " 2: (Invalid)";
    "(>"            " 3: Greater than or equal to";
    P               " 4: (Invalid)";
    '<              " 5: Less than";
    '^              " 6: Bitwise XOR (stand-in for not equal to)";
    '>              " 7: Greater than";
    P               " 8: (Invalid)";
    P               " 9: (Invalid)";
    P               "10: (Invalid)";
  ]=~             "Execute the case selected by the operation hash modulo 11";
  e&              "Compute the logical AND of the result and the value produced
                   by this operation to be the new result";
  X               "Let the right operand be the new left operand";
}/              "End for each";
;               "Clean up and implicitly print result";
\$\endgroup\$
4
\$\begingroup\$

Haskell, 156 bytes

r a=read[a]::Int
l"!"=(/=)
l"="=(==)
l">"=(>=)
l"<"=(<=)
k">"=(>)
k"<"=(<)
[]#_=1<2
(a:'=':b:c)#i=l[a]i(r b)&&c#r b
(a:b:c)#i=k[a]i(r b)&&c#r b
f(h:t)=t#r h

Usage example:

f "3<=4!=9>3==3"        -> True
f "3<=4!=4"             -> False
f "5>5"                 -> False
f "8==8<9>0!=2>=1"      -> True

Ungolfed version:

digitToInt d = read [d] :: Int

lookup2 "!" = (/=)
lookup2 "=" = (==)
lookup2 ">" = (>=)
lookup2 "<" = (<=)

lookup1 ">" = (>)
lookup1 "<" = (<)

eval []              _ = True
eval (op:'=':d:rest) i = lookup2 [op] i (digitToInt d) && eval rest (digitToInt d)
eval (op:d:rest)     i = lookup1 [op] i (digitToInt d) && eval rest (digitToInt d)

evalChain (hd:rest) = eval rest (digitToInt hd)

eval takes two arguments: the string to parse (starting always with a comparison operator) and a number i which is the left argument for comparison (and was the right argument in the previous round). The operator is returned by lookup2 if it's a two character operator (check only 1st char, because 2nd is always =) and by lookup1 if it's just a single character. eval calls itself recursively and combines all return values with logical and &&.

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

JavaScript (ES6) 110 116

Straightforward:scan string, c is current digit, l is last digit, o is operator.

F=x=>(l='',[for(c of x)10-c?(v=!l||v&&(o<'<'?l!=c:(o[1]&&c==l)||(o<'='?l<c:o<'>'?c==l:l>c)),l=c,o=''):o+=c],v)

Test In Firefox / FireBug console

;['3<=4!=9>3==3','3<=4!=4','5>5','8==8<9>0!=2>=1']
.forEach(s=>console.log(s,F(s)))

3<=4!=9>3==3 true
3<=4!=4 false
5>5 false
8==8<9>0!=2>=1 true

\$\endgroup\$
3
\$\begingroup\$

Common Lisp - 300 185 169 165

(lambda(s)(loop for(a o b)on(mapcar'read-from-string(cdr(ppcre:split"([0-9]+)"s :with-registers-p t)))by #'cddr always(if o(funcall(case o(=='=)(!='/=)(t o))a b)t)))

Example

(mapcar (lambda(s) ...)
       '("2<=3<=6>2<10!=3"
         "3<=4!=9>3==3" 
         "3<=4!=4" 
         "5>5"
         "8==8<9>0!=2>=1"))
=> (T T NIL NIL T)

Explanation

(lambda (s)
  (loop for (a o b) on (mapcar
                        'read-from-string
                        (cdr
                         (cl-ppcre:split "([0-9]+)" s
                                         :with-registers-p t))) by #'cddr
        always (if o
                   (funcall (case o
                                  (== '=)
                                  (!= '/=)
                                  (t o))
                            a b)
                   t)))
  • ppcre:split splits on digits; for example:

    (ppcre:split "([0-9]+)" "2<=3<=6>2<10!=3" :with-registers-p t)
    => ("" "2" "<=" "3" "<=" "6" ">" "2" "<" "10" "!=" "3")
    

    Notice the first empty string, which is discarded using cdr

  • Mapping read-from-string to this list calls the read function for each strings, which returns symbols and numbers.

  • loop for (a op b) on '(3 < 5 > 2) by #'cddr iterates over the list by a step of 2 and thus binds a, op and b as follows, for each successive pass.

    a  op  b
    ----------
    3  <    5
    5  >    2
    2  nil  nil
    
  • always checks whether the next expression is always true: either the operator is nil (see above) or the result of the comparison holds (see below).

  • the case selects a Common-Lisp comparison function, according to the symbol previously read; since some operators are identical in Lisp and the given language we can simply return o in the default case.

\$\endgroup\$
2
\$\begingroup\$

Python 2, 95 102

t=1
n=o=3
for c in map(ord,raw_input()):
 o+=c
 if 47<c<58:t&=627>>(o-c+3*cmp(n,c))%13;n=c;o=0
print t

The loop is a straightforward pass through the string one character at a time. The t&=... part is where the magic happens. Basically, I hash the operator together with the value of cmp(lhs,rhs) (-1, 0, or 1 depending on if lhs is less, equal, or greater than rhs). The result is a key into a lookup table that gives 0 or 1 depending on whether the numbers compare properly given that operator. What lookup table, you ask? It's the number 627 = 0001001110011 in binary. Bitwise operators do the rest.

This works on the four given test cases; let me know if you find an error for another case. I haven't tested it very rigorously.

\$\endgroup\$
2
  • \$\begingroup\$ You need to take in a as input. \$\endgroup\$
    – xnor
    Mar 6, 2015 at 4:36
  • \$\begingroup\$ @xnor Whoops. Corrected. \$\endgroup\$
    – DLosc
    Mar 6, 2015 at 4:38
2
\$\begingroup\$

05AB1E, 37 bytes

þS¡¦Uþü.S"=<!>"2×Sć«'<š'>ª3ôÀsèXδåÅ\P

Try it online or verify all test cases.

Explanation:

þ         # Only leave the digits of the (implicit) input-string
          #  i.e. "3<=4!=9>3==3" → "34933"
 S        # Convert it to a list of digits
          #  → [3,4,9,3,3]
  ¡       # Split the (implicit) input-string by those, to have a list of the comparisons
          #  → ["","<=","!=",">","==",""]
   ¦      # Remove the first item (which is an empty string)
          #  → ["<=","!=",">","==",""]
          # (it also contains a trailing empty string, but we'll ignore that)
    U     # Pop and store it in variable `X`
þ         # Only leave the digits of the (implicit) input-string again
 ü        # For each overlapping pair of digits:
  .S      #  Compare them: -1 if a<b; 0 if a==b; 1 if a>b
          #   → [[3,4],[4,9],[9,3],[3,3]] → [-1,-1,1,0]
"=<!>"    # Push string "=<!>"
      2×  # Double it to "=<!>=<!>"
        S # Convert it to a list of characters: ["=","<","!",">","=","<","!",">"]
ć         # Extract the head: pop and push remainder-list and head separately
 «        # Append this "=" to each: ["<=","!=",">=","==","<=","!=",">="]
  '<š'>ª  # Prepend a "<" and append a ">": ["<","<=","!=",">=","==","<=","!=",">=",">"]
3ô        # Split it into parts of size 3: [["<","<=","!="],[">=","==","<="],["!=",">=",">"]]
  À       # Rotate this list once left: [[">=","==","<="],["!=",">=",">"],["<","<=","!="]]
   sè     # Index the digit-comparisons into it (where the -1 indexes into the last item)
          #  → [["<","<=","!="],["<","<=","!="],["!=",">=",">"],[">=","==","<="]]
X         # Push the input-comparisons from variable `X` again
 δ        # Apply double-vectorized:
  å       #  Check if the current comparison is in the current list
          #   → [[1,1,0,0,0],[1,1,0,0,0],[0,1,1,0,0],[1,0,0,1,0]]
   Å\     # Leave the main diagonal of these double-vectorized checks
          #  → [1,1,1,1]
     P    # And check if all are truthy by taking their product
          #  → 1
          # (after which the result is output implicitly)
\$\endgroup\$
1
\$\begingroup\$

Javascript 101 bytes

a different approach from the js solution posted here

F=(s,i=0,l=o="")=>[...s].every(c=>c>=0?[l^c,l==c,,l<c,l>c,l<=c,,l>=c]["!==<><=>=".search(o,l=c,o="")]:o+=c,l=o="")

console.log(F("3<=4!=9>3==3")==true)
console.log(F("3<=4!=4")==false)
console.log(F("5>5")==false)
console.log(F("8==8<9>0!=2>=1")==true)

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

Java 8, 283 270 bytes

s->{String[]a=s.split("\\d"),b=s.split("\\D+");int i=0,r=1,x,y;for(;i<a.length-1;y=new Byte(b[++i]),r-=a[i].equals("==")&x!=y|a[i].equals("!=")&x==y|a[i].equals(">")&x<=y|a[i].equals(">=")&x<y|a[i].equals("<")&x>=y|a[i].equals("<=")&x>y?1:0)x=new Byte(b[i]);return r>0;}

-13 bytes thanks to @ceilingcat.

Explanation:

Try it here.

s->{                             // Method with String parameter and boolean return-type
  String[]a=s.split("\\d"),      //  All the inequalities
          b=s.split("\\D+");     //  All the digits
  int i=0,                       //  Index-integer (starting at 0)
      r=1,                       //  Flag integer for the result, starting at 1
      x,y;                       //  Temp integer `x` and `y`
  for(;i<a.length-1              //  Loop `i` in the range [0, length]:
      ;                          //    After every iteration:
       y=new Byte(b[++i]),       //     Convert the `i+1`'th digit from String to integer,
                                 //     and store it in `y`
       r-=                       //     Decrease the result by:
          a[i].equals("==")&x!=y //      If "==" and `x` and `y` are not equal
          |a[i].equals("!=")&x==y//      or if "!=" and `x` and `y` are equal
          |a[i].equals(">")&x<=y //      or if ">" and `x` is smaller than or equal to `y`
          |a[i].equals(">=")&x<y //      or if ">=" and `x` is smaller than `y`
          |a[i].equals("<")&x>=y //      or if "<" and `x` is larger than o equal to `y`
          |a[i].equals("<=")&x>y //      or if "<=" and `x` is larger than `y`:
           1                     //       Decrease the result by 1
          :0;                    //      Else: keep it the same by decreasing with 0
    x=new Byte(b[i]);            //   Convert the `i`'th digit from String to integer,
                                 //   and store it in `x`
  return r>0;}                   //  Return whether the result is still 1
\$\endgroup\$
0

Your Answer

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

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