Network Transparent Boolean Logic Evaluator

Question

Write an expression evaluator for boolean expressions encoded as JSON. Read on for explanation and rules.

Motivation:

Consider a scenario where two agents (Alice and Bob) are communicating with each other under the following constraints:

• All communication must be done as valid JSON strings (no JSONP or extensions), because Bob and Alice love JSON. They have had problems with character encoding in the past, so they have decided to restrict themselves to ASCII.
• Alice needs Bob to notify her in case a certain condition is met, but:
  • Bob doesn't know what the condition is in advance.
  • Alice can't evaluate the condition herself because it requires information that only Bob has.
  • The status of the variables can change rapidly enough (and the network is slow enough) that it would be infeasible for Bob to continuously transmit the data to Alice.
• Neither knows anything about the implementation of the other agent (for example, they can't make assumptions about the implementation language of the other agent).

Alice and Bob have worked out a protocol to help them complete their task.

Representing Conditional Expressions:

1. They have agreed to represent Boolean literals by strings, for example "foo" or "!bar", where ! represents the negation of a literal, and valid names contain only letters and numbers (case sensitive, any strictly positive length; "" and "!" are not valid; i.e. a literal is a string whose contents match the regex /^!?[a-zA-Z0-9]+$/).

2. Expressions are only transmitted in negation normal form. This means that only literals can be negated, not subexpressions.

3. Expressions are normalized as a conjunction of disjunctions of conjunctions of disjunctions ... etc encoded as nested arrays of strings. This needs a bit more explanation, so...

Expression Syntax:

Consider the following boolean expression:

(¬a ∧ b ∧ (c ∨ ¬d ∨ e ∨ ¬f) ∧ (c ∨ (d ∧ (f ∨ ¬e))))

Notice that the entire expression is contained in parentheses. Also notice that the first level(and all odd levels) contains only conjunctions(∧), the second level(and all even levels) contains only disjunctions(∨). Also notice that no subexpression is negated. Anyway meat and potatoes... This would be represented by Alice in JSON as:

["!a","b",["c","!d","e","!f"],["c",["d",["f","!e"]]]]

Another example:

((a ∨ b ∨ c))

Becomes:

[["a","b","c"]]

In summary: [] are interpreted as parentheses, literals are wrapped in "",! means negation, and , means AND or OR depending on nesting depth.

NB: the empty conjunction (the result of ANDing no variables) is true, and the empty disjunction (the result of ORing no variables) is false. They are both valid boolean expressions.

Bob's data:

Bob's data is emitted by a program on his computer as a simple JSON object as key-value pairs, where the key is the name of the variable, and the value is either true or false. For example:

{"a":false,"b":true,"c":false}

Bob needs our help!

Bob has little programming experience, and he's in over his head. He has handed you the task.

You need to write a program that accepts the JSON text that Alice sent along with the JSON text for Bob's data, and evaluates the expression with those values, returning true or false (the actual strings true and false; Bob and Alice love JSON, remember?)

• Bob says less is more, so he wants you to make your source code as short as possible (this is a code-golf)

• You are allowed to use an external library to parse the JSON text, but this is the only exception. Only standard library functionality is allowed.

• Note that the JSON is accepted and returned as a string. There is no requirement to explicitly parse it though, if you can get it to always work without doing so.

• If Alice uses a variable that Bob doesn't know, assume it is false. Bob's data may contain variables that Alice doesn't use.

• If Alice's or Bob's JSON Object contains an invalid literal, or the JSON is invalid, or it contains a non ASCII character, then your program must return null

Some test cases(in JSON):

[
 {"alice":"[\"\"]","bob":"{}","result":"null"},
 {"alice":"[\"!\"]","bob":"{}","result":"null"},
 {"alice":"[\"0\"]","bob":"{\"0\":true}","result":"true"},
 {"alice":"[]","bob":"{}","result":"true"},
 {"alice":"[[]]","bob":"{}","result":"false"},
 {"alice":"[\"a>\"]","bob":"{\"a\":true}","result":"null"},
 {"alice":"[\"0\"]","bob":"{}","result":"false"},
 {"alice":"[\"0\"]","bob":"","result":"null"},
 {"alice":"[\"1\"]","bob":"{\"1\":false}","result":"false"},
 {"alice":"[\"true\"]","bob":"{\"true\":false}","result":"false"},
 {"alice":"[\"foo\",\"bar\",\"baz\"]","bob":"{\"foo\":true,\"bar\":true,\"biz\":true}","result":"false"},
 {"alice":"[[[\"a\",[\"!b\",\"c\"],\"!c\"],\"d\"]]","bob":"{\"a\":true,\"b\":false,\"c\":true,\"d\":false}","result":"false"},
 {"alice":"[\"!a\",\"b\",[\"c\",\"!d\",\"e\",\"!f\"],[\"c\",[\"d\",[\"f\",\"!e\"]]]]","bob":"{\"a\":false,\"b\":true,\"c\":true,\"e\":true,\"f\":false}","result":"true"}
]

As can be seen from the test cases, input and output are strings that are correctly parseable JSON. The empty string test case for bob was originally in error, the correct value to return is null, but if it saves you characters to return false, then that is also acceptable. I added cases for the empty clauses to make that explicit. I added another 2 test cases in response to a bug I found in someone's implementation

Answer 1

ECMASCript 6 variation, 213 194 190 189 192 166 chars

try{P=_=>JSON.parse(prompt())
B=P()
f=(a,c)=>a[c?'some':'every'](v=>v.big?[B][+/\W|_/.test(s=v.slice(C=v[0]=='!'))-!s][s]^C:f(v,!c))
q=f(P())}catch(_){q=null}alert(q)

Note: takes Bob's input first, and then Alice's input. This saves us four bytes.

• Checks for syntactically valid JSON since JSON.parse throws if it isn't.
• Since we're already relying on the try-catch for the above, we (ab)use out-of-bounds access to trigger our "failed validation" path when validating the (possibly negated) literals
  • This is accomplished with the [B][...][s] part (thanks, @l4m2! used to use a slightly more verbose construction)
  • The -!s is to catch "" and "!" as invalid literals
  • The C variable holds the "should negate" state, which is accomplished with a "bitwise" XOR (and relies on implicit type coercion)

---

ES5 solution: https://codegolf.stackexchange.com/revisions/19863/8

Answer 2

Ruby, 335 (327?) characters

begin;a,b=*$<;require'json';b=JSON[b];q if a=~/{|}/||!a[?[]||b.any?{|v,x|v=~/[\W_]/||x!=!!x}
l=0;a.gsub!(/\[|\]/){"[{}]"[($&==?]?2:0)+l=1-l]};a.gsub!(/"(!)?([a-z\d]+)"/i){b[$2]^$1}
0 while [[/\[[#{f=!1},\s]*\]/,f],[/{[#{t=!f},\s]*?}/,t],[/\[[\w,\s]*\]/,t],[/{[\w,\s]*}/,f]].any?{|k,v|a.sub!(k){v}}
rescue a=??;end;puts a=~/\W/?"null":a

I've heard you can't parse HTML with Regex, but I've never been told you cannot parse JSON this way, so I tried.

Alice's input is separated from Bob's input by a newline; also, it's assumed that neither input contains newlines itself. This assumption is for I/O purposes only, and is not used later. If I can make an extra assumption that Alice's input contains no whitespace, we can drop 8 characters by removing all \s's on line #3. If we can only assume it contains no whitespace but spaces, we can still replace \s's with the space characters to save 4 characters.

Answer 3

Python 3 (429)

Longer than the other answers, but arguably the most readable so far... :)

import json,sys,re
r,p,m='^!?[a-zA-Z\d]+$',print,re.match
def g(a,b,s):
 if type(a)is str:
  if m(r,a):
   try:return('not '+str(b[a[1:]]))if a[0]=='!'else str(b[a])
   except:return'False'
  raise Exception
 return'('+((' and 'if s else' or ').join(g(x,b,not s)for x in a))+')'
s,j=sys.argv,json.loads
try:
 a,b = j(s[1]),j(s[2]or'{}');
 if all(m(r,x)and x[0]!='!'for x in b):p(str(eval(g(a,b,1))).lower())
except:
 p('null')

Answer 4

Node.JS (331 335 310 296)

As a starting point, manually minified, could definitely be improved a bit; it basically just "brute force" evaluates the expression;

As a golf hack restriction, the variable y can not be defined or it won't work :)

r=/^[a-z\d]+$/i;function g(a,b,s,c){c=s;for(k in a){if((k=a[k]).trim){k=k.slice(i=k[0]=='!');
if(!k.match(r))y;k=i?!b[k]:b[k]}else{k=g(k,b,!s)}c=s?c&k:c|k}return!!c;}z=process.argv;a=z[2]
;b=z[3];try{p=JSON.parse;l=console.log;a=p(a);b=p(b);for(k in b)if(!k.match(r))y;l(g(a,b,1))}
catch(e){l(null)}

Called with alice as first argument, bob as second argument, outputs result to stdout.

EDIT: Shrunk the code a little with the help of @FireFly and by removing support for "empty bob".

Answer 5

JavaScript, 178 bytes

Optimized from Tim Seguine's answer

try{P=JSON.parse,p=prompt;A=P(p());B=P(p());f=(a,c)=>a.map(v=>v.big?[B][/\W|_/.test(s=v.replace(/^!/,''))-!s][s]^s>v:f(v,!c))[c?'some':'every'](P);q=f(A)}catch(_){q=null}alert(q)

Try it online!