A (basic) Knights and Knaves Solver

In case you're not familiar with Knights and Knaves, it's a classic type of logic problem.

Here's an example:


"A very special island is inhabited only by knights and knaves. Knights always tell the truth, and knaves always lie.You meet two inhabitants: Zoey and Mel. Zoey tells you that Mel is a knave. Mel says, Neither Zoey nor I are knaves.' So who is a knight and who is a knave?"

Something that annoyed me when doing these problems was the possibility of ambiguous cases. Often, there are multiple valid solutions. Thus, my goal was to develop a program to solve problems such as this, outputting all valid possible solutions.

Main Class:

``
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;
import java.util.Set;

public class LogicDriver
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
HashMap hm = new HashMap<>();

System.out.println("Welcome to the Knights and Knaves solver! Let's quickly define the syntax.\n");
System.out.println("Precede every statement with the name of the speaker followed by a colon, like so:\n");
System.out.println(" Jack: I am a knave\n");
System.out.println("There are 6 valid rule configurations. They are as follows:\n");
System.out.println(" name: X is a [knight/knave]\n");
System.out.println(" name: [either/neither] X [or/nor] Y is a [knight/knave]");
System.out.println(" name: [either/neither] X is [knight/knave] [or/nor] Y is [knight/knave]\n");
System.out.println(" name: X [and/or] Y is [knight/knave]");
System.out.println(" name: X is [knight/knave] [and/or] Y is [knight/knave]\n");
System.out.println(" name: X could say [any previous rule here]\n");
System.out
.println("There are also two additional keywords: 'not' and 'I'. The former negates the statement after it,\nand the latter refers to the current speaker.\n");

I don't have answers to your questions right now, but I do have some general suggestions to make your code cleaner and more readable:

Coding Style

• always use curly braces, even for one-line statements to avoid bugs and to make your code easier to read.

• you are consistent with your use of { on the next line, which is the most important thing. But in Java, it is customary to put it on the same line, so that's what I would do.

• use spaces around ==.

Naming

• abstract classes should have abstract in their name (Rule -> AbstractRule), so you can see right away that it is abstract.

• avoid short variable names, use expressive names instead. Avoid numbers in variable names (most of the time, they are a sign of bad naming). Examples: ion, ioe, ioo, ioa, tmpRaw1, tmpSp1, name1, name2, isKnight2, type, self, raw, ps, hm, tmp, r, p, s, pos, ind, etc). This might not seem that important, but it really is. Code becomes extremely hard to read if the variable names are not expressive. If I look at a method signature, I should have at least some idea what it does. This is not the case for a lot of these methods (for example ArrayList setTrue(ArrayList ps, int ind)).

• avoid short method names. For example, get should be getPerson.

• getPerson in JunctionRule is named wrong (it doesn't return a person, but something else instead).

JunctionRule

JunctionRule is way too complex. A first step to fixing this would be to extract some logic to functions (for example parsing of neither-nor, parsing of the other case).

Dublicate Code

Try to avoid duplicate code. For example:

• the code for checking if it is a knight is present in all *Rule classes.

• the isValid code for IsRule, SelfRule and CouldRule contains a lot of duplicate code.

Another example is your JunctionRule:isValid method:

@Override
boolean isValid(ArrayList ps)
{
    //not exactly D-R-Y coding here, but I think this is the clearest way to do this
    boolean invert = !get(ps, self).isKnight;
    if (type == 0)
        return invert ? (get(ps, name1).isKnight == getPerson(name1)) || (get(ps, name2).isKnight == getPerson(name2))
                : !(get(ps, name1).isKnight == getPerson(name1)) && !(get(ps, name2).isKnight == getPerson(name2));
    if (type == 1)
        return get(ps, name1).isKnight == getPerson(name1) ^ get(ps, name2).isKnight == getPerson(name2); //XOR is its own inverse
    if (type == 2)
        return invert ? !(get(ps, name1).isKnight == getPerson(name1)) && !(get(ps, name2).isKnight == getPerson(name2))
                : get(ps, name1).isKnight == getPerson(name1) || get(ps, name2).isKnight == getPerson(name2);
    if (type == 3)
        return invert ? !(get(ps, name1).isKnight == getPerson(name1)) || !(get(ps, name2).isKnight == getPerson(name2))
                : get(ps, name1).isKnight == getPerson(name1) && get(ps, name2).isKnight == getPerson(name2);
    return false;
}

It is practically unreadable and contains a lot of duplicate code. It could look something like this instead (but try to find better variable names than b1 and b2, I'm just honestly not sure what they represent):

@Override
boolean isValid(ArrayList ps) {
    boolean invert = !get(ps, self).isKnight;
    boolean b1 = get(ps, name1).isKnight == getPerson(name1);
    boolean b2 = (get(ps, name2).isKnight == getPerson(name2));
    boolean returnValue = false;
    switch (type) {
        case 0:
            returnValue = !b1 && !b2;
            break;
        case 1:
            returnValue = b1 ^ b2; //XOR is its own inverse
            break;
        case 2:
            returnValue = b1 || b2;
            break;
        case 3:
            returnValue = b1 && b2;
            break;
    }
    if (type != 1 && invert) {
        returnValue = !returnValue;
    }
    return returnValue;
}

Misc

• use an enum for type instead of using int (and give the values a good name). Then you could also use a switch in JunctionRule:isValid.

• don't hardcode magic numbers. This makes it hard to change your code, and named fields would tell a reader what the number means. An example is 5 in CouldRule and 7 in JunctionRule.

• use more comments, especially JavaDoc method comments.

• your main should do nothing but start the program. Move your current code to functions (help, readConsoleInput, parse, or similar). If you follow this rule, it will be a lot easier to test your code (right now, the only way to even test it manually is to use the command line).

• isKnight1 = tmpRaw1.contains("knight") ? false : true; can be written as isKnight1 = !tmpRaw1.contains("knight"). The same idea can be applied for return invert ? get(ps,name).isKnight==false which should be return invert ? !get(ps,name).isKnight.

• use interfaces instead of concrete implementations in method signatures/variable declarations (ArrayList -> List).

• use private for fie

StackExchange Code Review Q#64911, answer score: 4