17
\$\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\$
  • \$\begingroup\$ Can we accept input with Unicode inequality signs like ≤ and ≥ instead of <= and >=? \$\endgroup\$ – FUZxxl Mar 5 '15 at 12:11
  • \$\begingroup\$ @FUZxxl You can't. \$\endgroup\$ – xnor Mar 5 '15 at 21:58
7
\$\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\$
  • \$\begingroup\$ What a clever strategy! \$\endgroup\$ – xnor Mar 5 '15 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\$
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\$

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\$

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\$
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\$
1
\$\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\$
  • \$\begingroup\$ You need to take in a as input. \$\endgroup\$ – xnor Mar 6 '15 at 4:36
  • \$\begingroup\$ @xnor Whoops. Corrected. \$\endgroup\$ – DLosc Mar 6 '15 at 4:38
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 bytes

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

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 from 0 to the length - 1
  if((x=new Byte(b[i]))!=(y=new Byte(b[++i]))&(a[i].equals("=="))
                                //   If "==" and `x` and `y` as int are not equal:
     |(a[i].equals("!=")&x==y)  //   Or "!=" and `x` and `y` are equal
     |(a[i].equals(">")&x<=y)   //   Or ">" and `x` is smaller or equal to `y`
     |(a[i].equals(">=")&x<y)   //   Or ">=" and `x` is smaller than `y`
     |(a[i].equals("<")&x>=y)   //   Or "<" and `x` is larger or equal to `y`
     |(a[i].equals("<=")&x>y))  //   Or "<=" and `x` is larger than `y`
    r--;                        //    Decrease `r` by 1
                                //  End of loop (implicit / single-line body)
  return r>0;                   //  Return if `r` is still 1
}                               // End of method
\$\endgroup\$

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.