logicgridsolver.java

package com.hafthor;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Main {

    public static void main(final String[] args) {
        final String[][] l = new String[][]{
                "first second third fourth last".split(" "),
                "Alvin Bart Carol Doug Erin".split(" "),
                "band cooking hiking karaoke photography".split(" "),
                "blue crimson green purple white".split(" ")
        };
        final Grid g = new Grid(l);
        g.addStatements("green~cooking Alvin=second purple!hiking purple>Erin Carol!karaoke photography=first photography=green Doug=white Bart~blue purple~cooking purple~karaoke".split(" "));
        g.solve();
    }

    private record Ref(int grid, int index) {
    }

    private record Statement(Ref left, char op, Ref right) {
    }

    public static class Grid {
        final String[][] labels;
        final int[][] grids;
        final int gridCount;
        final List<Statement> statements = new ArrayList<>();

        int combinationsTested = 0;

        public Grid(final String[][] labels) {
            this.labels = labels;
            gridCount = labels[0].length;
            for (String[] label : labels) if (label.length != gridCount) throw new IllegalArgumentException();
            grids = new int[labels.length - 1][gridCount];
        }

        public void addStatements(final String[] statements) {
            for(final String statement : statements) {
                addStatement(statement);
            }
        }

        public void addStatement(final String statement) {
            final String[] operands = statement.split("[><~!=()]");
            final char op = statement.charAt(operands[0].length());
            if (operands.length != 2) throw new IllegalArgumentException();
            Ref left = null, right = null;
            for (int labelIndex = 0; labelIndex < labels.length; labelIndex++) {
                final String[] labels = this.labels[labelIndex];
                for (int i = 0; i < labels.length; i++) {
                    final String label = labels[i];
                    if (label.equals(operands[0])) left = new Ref(labelIndex, i);
                    if (label.equals(operands[1])) right = new Ref(labelIndex, i);
                }
            }
            if (left == null) throw new IllegalArgumentException(statement);
            if (right == null) throw new IllegalArgumentException(statement);
            statements.add(new Statement(left, op, right));
        }

        private static int fact(int n) {
            if (n > 12) throw new IllegalArgumentException("result of " + n + "! would be greater than int");
            int accum = n;
            while (n > 1) accum *= --n;
            return accum;
        }

        // solve tries every combination for every left-side grid (other grids are derived in printGrid)
        // we shortcut the combinations by seeing what the lowest grid that is incorrect is and incrementing
        // combinations from there.
        public void solve() {
            combinationsTested = 0;
            // sort statements so when we check, a failed statement will
            // indicate where in the combinations to increment.
            statements.sort((o1, o2) -> {
                int o10 = o1.left.grid * gridCount + o1.left.index;
                int o11 = o1.right.grid * gridCount + o1.right.index;
                int o20 = o2.left.grid * gridCount + o2.left.index;
                int o21 = o2.right.grid * gridCount + o2.right.index;
                return Math.max(o10, o11) - Math.max(o20, o21);
            });
            final int gridCombinations = fact(gridCount);
            int[] gridComboSolution = null;
            int[] gridCombo = new int[labels.length - 1];
            for (; ; ) {
                for (int grid = 0; grid < gridCombo.length; grid++) setSolutionForCombination(grid, gridCombo[grid]);
                int lowestGridInError = checkStatements();
                if (lowestGridInError < 0) {
                    if (gridComboSolution != null) throw new IllegalArgumentException("multiple solutions found");
                    gridComboSolution = Arrays.copyOf(gridCombo, gridCombo.length);
                    lowestGridInError = gridCount;
                }
                combinationsTested++;
                if (!increment(gridCombo, gridCombinations, Math.max(1, lowestGridInError))) break;
            }
            if (gridComboSolution == null) throw new IllegalArgumentException("no solution found");
            for (int grid = 0; grid < gridComboSolution.length; grid++) setSolutionForCombination(grid, gridComboSolution[grid]);
            printGrid();
        }

        private boolean increment(final int[] combos, final int limit, final int incrementPastGrid) {
            for (int grid = combos.length - 1; grid >= incrementPastGrid; grid--) combos[grid] = limit - 1;
            for (int grid = combos.length - 1; grid >= 0; combos[grid--] = 0)
                if (++combos[grid] < limit) return true;
            return false;
        }

        public void setSolutionForCombination(final int grid, int combination) {
            final LinkedList<Integer> possibilities = new LinkedList<>();
            for (int i = 0; i < gridCount; i++) possibilities.add(i);
            for (int i = 0; i < gridCount; i++) {
                final int l = possibilities.size();
                grids[grid][i] = possibilities.remove(combination % l);
                combination /= l;
            }
        }

        public int checkStatements() {
            for (final Statement statement : statements) {
                final int cs = checkStatement(statement);
                if (cs >= 0) return cs;
            }
            return -1;
        }

        private int checkStatement(final Statement statement) {
            final Ref left = statement.left, right = statement.right;
            final char op = statement.op;
            final int leftIndex = left.index, rightIndex = right.index;
            final int leftGrid = left.grid, rightGrid = right.grid;
            final int leftValue = leftGrid == 0 ? leftIndex : grids[leftGrid - 1][leftIndex];
            final int rightValue = rightGrid == 0 ? rightIndex : grids[rightGrid - 1][rightIndex];
            final boolean cs = switch (op) {
                case '=' -> leftValue == rightValue;
                case '>' -> leftValue > rightValue;
                case ')' -> (leftValue - rightValue) == 1; // just greater than
                case '(' -> (leftValue - rightValue) == -1; // just less than
                case '<' -> leftValue < rightValue;
                case '!' -> leftValue != rightValue; // not equal
                case '~' -> Math.abs(leftValue - rightValue) == 1; // next to
                default -> throw new IllegalArgumentException();
            };
            if (cs) return -1;
            return Math.max(leftGrid, rightGrid);
        }

        private int calcGridLine(int gridRow, int gridCol, int gridLine) {
            final int gridValue = grids[gridRow][gridLine];
            for (int grid = 0; grid < gridCount; grid++) {
                if (grids[gridCol][grid] == gridValue) return grid;
            }
            throw new IllegalArgumentException();
        }

        public void printGrid() {
            int strLen = 0;
            for (final String[] strings : labels)
                for (String str : strings) if (str.length() > strLen) strLen = str.length();
            final String strFmt = " %" + strLen + "s";

            // header
            System.out.printf(strFmt, "");
            for (final String str : labels[0])
                System.out.printf(strFmt, str);

            for (int gg = labels.length - 1; gg >= 2; gg--) {
                System.out.print("   ");
                for (final String str : labels[gg])
                    System.out.printf(strFmt, str);
            }
            System.out.println();

            for (int gridRow = 0; gridRow < labels.length - 1; gridRow++) {
                for (int row = 0; row < gridCount; row++) {
                    System.out.printf(strFmt, labels[gridRow + 1][row]);
                    for (int col = 0; col < gridCount; col++)
                        System.out.printf(strFmt, grids[gridRow][row] == col ? "@" : "x");
                    for (int gridCol = labels.length - 2; gridCol >= 1 + gridRow; gridCol--) {
                        System.out.print("   ");
                        int gridValue = calcGridLine(gridRow, gridCol, row);
                        for (int col = 0; col < gridCount; col++)
                            System.out.printf(strFmt, gridValue == col ? "@" : "x");
                    }
                    System.out.println();
                }
                System.out.println();
            }
            System.out.println("Combinations tested: " + combinationsTested);
        }
    }
}