Kata

Your task:

• Write a function that takes in a series of logical expressions in 2-CNF as inputs.
• Each logical expression "clue" will contain one or two strings naming variables.
• Those strings may be preceded by a - character to denote a FALSE assignment, or lack such a character to denote a TRUE assignment.
• If it is possible to devise some assignment of variables to True or False such that all clues are satisfied, return a set of strings, formatted as the clues are, denoting a valid assignment that satisfies all clues.
• If it is impossible to assign the variables values that satisfy all clues, i.e. the clues are self-contradictory, just return None.

This is sort of a lot, so it makes sense to do some research before tackling the problem.

...so what is 2-CNF?

Conjunctive normal form (CNF) is a way of expressing boolean equations as a bunch of ANDed sets of ORed variables. See below examples:

1. (a OR b) AND (b OR NOT c) AND (NOT b OR a OR c)
   There are three sets of ORed terms, i.e. (a OR b), (b OR NOT c), and (NOT b or a or c). A matching set of values might be a, -b, -c. A failing set of assignments might be -a, -b, -c. If a is False and b is False, the first set of ORed terms, (a or b), fails.

2. (a OR b) and (NOT b OR NOT a)
   This equation could be fulfilled by assignments (a, -b) or (-a, b). Assignments (a, b) and (-a, -b) will fail either the first or second groupings, which must both resolve to True for the equation as a whole to be True.

3. (a) AND (NOT a)
   This equation will ALWAYS fail, regardless of what assignments you apply to it. If a is True, the second term fails. If a is False, the first term fails.

2-CNF is a subset of CNF, where each ANDed part of the CNF equation has only up to 2 terms. Examples 2 and 3 are valid 2-CNF, as no part has over 2 terms. Example 1 is not valid 2-CNF, as the final part, (NOT b or a or c), has 3 terms, which is more than 2 terms.

For a more in-depth discussion of CNF, see here (https://www.wikiwand.com/en/Conjunctive_normal_form).

What are my inputs?

Inputs for this kata are 2D arrays containing 2-CNF equations, each of which is a lists of parts containing up to 2 terms. Rather than saying variable_a is True or variable_b is False, this kata uses the - character to denote that the variable name after it is FALSE, and the LACK of a - character to denote that a variable name is TRUE. The examples above might be given as:

1. You won't see Example 1. It's not in 2-CNF, but in 3-CNF, because the final term, (NOT b or a or c), has 3 variables (a, b, and c) in it.
2. (a OR b) and (NOT b OR NOT a) becomes [["a", "b"], ["-a", "-b"]]
3. (a) AND (NOT a) becomes [["a"], ["-a"]]

Again: note that NOT v is given as -v, and v is given simply as v.

Also, note that while the example input variables are single letters (like a and b above), the variable names could potentially be any alphabetic sequences of up to 10 letters (e.g. AbcThaeiGV, or -AbcThaeiGV if it were being negated).

What are my outputs?

Your goal here is to assign output values to each of the variables mentioned in the input clues. There are two cases that can occur when you look for a valid set of variable assignments.

• Sometimes, that goal is possible, like in Example 2 above, which can be satisfied by either (a, -b) or (-a, b).
  • Your output should be a SET of STRINGS denoting whether each variable mentioned in the clues is true (in which case you provide a string with the variable name, and no -) or false (in which you provide a string with the variable name, preceded by a -, as shown above). This is the same way the variables are denoted in the clues.
  • For Example 2, you should return {"a", "-b"} or {"b", "-a"}.
• Sometimes, it impossible to satisfy all clues, like in Example 3 above, which can be satisfied neither by {"a"} nor by {"-a"}.
  • In that case, return a simple None, to show that nothing can satisfy the given clues.

Tests start out with revealed single-letter tests, then move to:

• 20x tests of 5-letter variables, of which there are 5, defined by 5 clues.
• 20x tests of 5-letter variables, of which there are 50, defined by 60 clues.
• 20x tests of 5-letter variables, of which there are 500, defined by 600 clues.
• 10x tests of 10-letter variables, of which there are 1000, defined by 1100 clues.

Initial tests have descriptive output showing where answers are wrong, but later tests cannot do that, as there is a hard cap on terminal output length.

Kata in this Series

1. Coping with NP-Hardness #1: 2-SAT
2. Coping with NP-Hardness #2: Max Weight Independent Set of a Tree
3. Coping with NP-Hardness #3: Finding the Minimum Hamiltonian Cycle
4. Coping with NP-Hardness #4: 3-Recoloring