Welcome back to the weekly programming contests! If you are new to the contest or need a refresher don’t forget to read up on the rules and information Posted Here
This week’s challenge is to write a method that takes in one String (a valid boolean formula in the form: "(a | ~b | ...) & (b | a | c | ...) ...") and returns true if a there set of values for the variables exist that make the expression true and false if it is not possible. For this challenge '&' represents AND, '|' represents OR, and '~' represents NOT. If you would like some further reading, please see Wikipedia
You can assume all conjunctions are surrounded with parentheses, that the formatting of the whitespace found in the examples is true for all inputs, that all variables are a single lowercase letters a-z, and that the syntax is valid.
Examples:
verify("(a | b | c) & (~a | b | c)") -> true
verify("(a | b) & (~b) & (~a)") -> false
verify("(a | b) & (~a | ~b | ~c) & (~b) & (~a)") -> false
verify("(a | b) & (~a | ~b)") -> true
verify("(a) & (~b) & (~a | b)") -> false
verify("(~b) & (a | c) & (a | ~b)") -> true
verify("(a) & (~a)") -> false
Also, if you like these weekly programming problems, please make some suggestions for the contest or specific challenges (in the main thread)! This takes time out of my Sunday and its not always fun! Using suggested challenges makes it a lot faster and easier for me.
// 1. Finds unique variables in the expression
// 2. Counting between 0 and 2^(number of vars found), uses Integer.toBinaryString to assign a
// true/false (1/0) value to each variable.
// 3. Loops through expression and evaluates using the above determined true/false values
public static boolean verify(String in)
{
Set<Integer> args = new HashSet<>();
for (char c : in.toCharArray())
{
// 97 & 122
if (c >= 'a' && c <= 'z')
{
args.add((int) c);
}
}
StringBuilder sb = new StringBuilder();
int i = 0, j, k;
for (; i < Math.pow(2, args.size()); i++)
{
int[] points = new int[args.size()];
String s = Integer.toBinaryString(i);
for (j = points.length - 1, k = s.length() - 1; j >= 0 && k >= 0; j--, k--)
{
points[j] = s.charAt(k) - '0'; // 48
}
j = 0;
Map<Integer, Integer> _case = new HashMap<>();
for (int c : args)
{
_case.put(c, points[j++]);
}
int result = 1, and = '&' /*38*/, or = '|', operator = and;
for (j = 0; j < in.length(); j++)
{
int c = in.charAt(j);
if (c == '(') // 40
{
int val = 1, op = and;
boolean invert = false;
while (j < in.length() && c != ')') // 41
{
c = in.charAt(j++);
op = c == or || c == and ? c : op;
Integer p = _case.get(c);
if (p != null)
{
p = invert ? p > 0 ? 0 : 1 : p;
val = op == and ? val * p : val + p;
}
invert = c == '~';
}
result = operator == and ? result * val : result + val;
}
operator = c == or || c == and ? c : operator;
}
if (result > 0)
{
sb.append(sb.length() == 0 ? "Valid Case(s):\n" : "\n");
j = _case.size();
for (Map.Entry<Integer, Integer> e : _case.entrySet())
{
sb.append((char) e.getKey().intValue()).append("=").append(e.getValue() == 1);
if (--j > 0) sb.append(",");
}
}
}
if (sb.length() > 0) System.out.println(sb.toString());
return sb.length() > 0;
}
public static boolean v(String a){int r=0,i=-1,j=1,f=1,e[]=new int[127];for(;++i<1<<j;r|=f++){j=0;for(int z:a.chars().distinct().toArray())e[z]=i>>j++;for(int c:a.toCharArray()){f=c>96&c<'{'?e[c]*4^f*2|f:c==41?f/4&f&1:c=='~'?2|f:f&5;}}return r>0;}
Unminified (still not readable, sorry):
public static boolean v(String a) {
int r = 0, i = -1, j = 1, f = 1, e[] = new int[127];
for (; ++i < 1 << j; r |= f++) {
j = 0;
for (int z : a.chars().distinct().toArray())
e[z] = i >> j++;
for (int c : a.toCharArray()) {
f = c > 96 & c < '{'
? e[c] * 4 ^ f * 2 | f
: c == 41
? f / 4 & f & 1
: c == '~'
? 2 | f
: f & 5;
}
}
return r > 0;
}
This is based off of @dags’s answer, but has been altered to pretty much unrecognizable. f stores three boolean values in its least significant bits, equivalent to @dags’s val, invert, result variables respectively.
public static boolean v(String a){int r=0,i=0,f=1;for(List l=Arrays.asList(a.chars().distinct().boxed().toArray());++i<1<<l.size();r|=f++)for(int c:a.toCharArray())f=c>96&c<'{'?(i>>l.indexOf(c))*4^f*2|f:c==41?f/4&f&1:c=='~'?2|f:f&5;return r>0;}
public static boolean v(String a) {
int r = 0, i = 0, f = 1;
for (List l = Arrays.asList(a.chars().distinct().boxed().toArray()); ++i < 1 << l.size(); r |= f++)
for (int c : a.toCharArray())
f = c > 96 & c < '{' ? (i >> l.indexOf(c)) * 4 ^ f * 2 | f : c == 41 ? f / 4 & f & 1 : c == '~' ? 2 | f : f & 5;
return r > 0;
}
