0

The requirement is to parse a complex expression and assign the value to the variable that satisfies the condition. For e.g.

((!(($weatherResult.cityName=="Seattle")||($weatherResult.cityName=="Portland")))&&($weatherResult.cityName=="Folsom")) So based on this expression, the value of $weatherResult1.cityName should be Folsom.

Now if we take this expression

((!(($weatherResult.cityName=="Seattle")||($weatherResult.cityName=="Portland")))&&(!($weatherResult.cityName=="Folsom"))) Here the value of $weatherResult1.cityName should be any other city that does not match Seattle or Portland or Folsom. E.g. Boston

There is a catalog of US cities but not necessary that every expression needs to be backed by a catalog. The values can be plain strings as well.

One idea is to randomly pick a value and evaluate the expression to true. If it is false, then keep repeating, but this approach is time consuming and expensive. Rather I want to parse the expression and pick the value intelligently. I was thinking to use ANTLR to parse the expression but still not able to come up with an algorithm that would allow me to parse the tree and pick/assign values.

Anyone has any recommendations, please suggest.

Vignesh
  • 3
  • 2
  • So, you want to determine which value of city name will have the expression equal to True? – Tarik Jan 15 '23 at 02:49
  • yes that is correct. So the assumption is, expression should be true and what values would make it evaluate to true. – Vignesh Jan 15 '23 at 02:58
  • Is the city the only variable that will appear in the expression? Or is there a chance there could be two or more unknowns you need to determine a value for? What are the operators/functions that can be used in the expression? Is it possible there would a condition on the string length, on the number of letters "a" in the variable, ...etc? – trincot Jan 15 '23 at 07:47
  • No `cityName` is just an example given here. It could be any variable here. So for e.g. `(($result.variableA=="success")&&(((!($result.variableB=="failure"))&&($result.variableB=="no_result")))`. So here the value of `variableA` should be "sucess" and value of `variableB` should be "no_result". These values `success`, `failure` and `no_result` could be arbitary string values or could be from a well known catalog like US City names. The operators are `==` and `!=` for now. Lets assume there wont be condition on string length and number of letters in variable like that. It would be value check. – Vignesh Jan 15 '23 at 08:13
  • An SMT solver like z3 can provide access to arbitrary data-types etc. so you don't even need to encode it using some arbitrary integer mapping. Take a look at https://ericpony.github.io/z3py-tutorial/guide-examples.htm – alias Jan 18 '23 at 18:01

1 Answers1

0

A potential solution is to use a constraint programming solver. See https://mlabonne.github.io/blog/constraintprogramming/

Note that this problem is NP complete. It will quickly be solved for small inputs but runtime will explode for large inputs.

In fact, if all what you got is equalities to city names, you could use a SAT solver.

Tarik
  • 10,810
  • 2
  • 26
  • 40
  • So cityName is just an example given here. It could be any variable here. So for e.g. (($result.variableA=="success")&&(((!($result.variableB=="failure"))&&($result.variableB=="no_result"))). So here the value of variableA should be "sucess" and value of variableB should be "no_result". These values success, failure and no_result could be arbitary string values or could be from a well known catalog like US City names. Is there any well known SAT solver algorithm that can be applied here ? – Vignesh Jan 15 '23 at 08:15
  • What you could do is assign a logical variable for each potential equality: `$result.VariableA == "failure"` would be variable `v1`, `$result.variableB=="no_result"` would be v2 and so on. You solve the SAT and then you map back the results. Note that you would have to add a condition stating that `!($result.variableB=="no_result" && $result.variableB=="failure")` – Tarik Jan 15 '23 at 10:01
  • Thanks. So I am thinking to map the strings to integers so then I can use one of the SAT solvers to solve it. E.g. `(($result.variableA=="success")&&(((!($result.variableB=="failure"))&&($result.variableB=="no_result")))` would become `((A == 2 && ((B != 1) && (B == 3))) `. So if I map like this, I would be able to use some SAT solver. I have two questions: – Vignesh Jan 17 '23 at 21:47
  • 1. Which is a better SAT solver for these use cases - Z3 or CP-SAT ? Any recommendations ? I feel Z3 has easier/intutive syntax compared to CP-SAT but my requirement is to get all feasible solutions which Z3 does not support. Latency aspect ? 2. Any recommendations on how to handle these cases ? `(($weatherResult.cityName!=null)&&($weatherResult.cityName=="Portland"))` `(($weatherResult.cityName==null)&&($weatherResult.temp==80))` How to handle null checks ? I was thinking to represent boolean variable but sometimes variable `cityName` needs both a boolean answer and integer answer – Vignesh Jan 17 '23 at 21:55
  • You need to map a pair made of a variable and a value to a SAT variable. Example cityName == 'Bombay' becomes A. Null is a value too. A null value, but still a value. No reason to handle it differently. – Tarik Jan 18 '23 at 04:54
  • The alternative is to represent each value by an integer and use a contraint programming solver. There is a discussion here comparing z3 to ortool: https://stackoverflow.com/questions/71749970/z3-much-slower-than-ortools-sat-why. ortool is able to use multiple cores to solve problems. I think it will also be easier to state your problem using constraint programming. Using SAT will require you to carefully map your problem to SAT. So, I recommend using ortool instead of z3. Please, mark this question as answered if this help was useful. – Tarik Jan 18 '23 at 05:07
  • I just noticed this "So I am thinking to map the strings to integers". SAT solvers only deal with bool. Each integer value can be mapped to a bool variable. However, you need to add a constraint that one and only one of these set of variables can be true at a time. That would be a XOR constraint. Example: cityName can be Portland, Rio, Algiers. That would be three variables A, B, C. In addition to the logical expression you come up with from the original expression, you need to add A XOR B XOR C == TRUE. Failing that, you would end up with cityName being equal to more than one value. – Tarik Jan 18 '23 at 05:14
  • So, to make things easier, stick to constraint programming. – Tarik Jan 18 '23 at 05:15