PuzzleTest.java

package nl.siegmann.destiny2.puzzle;

import org.junit.jupiter.api.Test;

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

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.groups.Tuple.tuple;

public class PuzzleTest {


    private static final int width = 3;
    private static final int height = 2;
    private static final int nrStates = 4;

    private static class Node {
        private final Node parent;
        private int move;
        private int[] board;
        private Node[] children = new Node[width * height];

        private Node(Node parent, int move, int[] board) {
            this.parent = parent;
            this.move = move;
            this.board = board;
        }

        public int getPathLength() {
            if (parent == null) {
                return 1;
            }
            return 1 + parent.getPathLength();
        }
    }

    private void printBoard(int[] board) {
        for (int i = 0; i < height; i++) {
            for(int j = 0 ; j < width; j++) {
                System.out.print(board[(i*width) + j]);
            }
            System.out.println();
        }
    }

    @Test
    public void testSimpleBoard() {
        // given
        int[] targetState = new int[] {1,1,1,
                                       1,1,1};

        int[] startState =  new int[] {0,0,0,
                                       0,1,1};

        // when
        Node successNode = findPathToTargetState(startState, targetState);

        // then
        assertThat(successNode).isNotNull();
        List<Coordinate> moveSet = createMoveSet(successNode);
        assertThat(moveSet)
                .extracting("x", "y")
                .containsExactly(
                        tuple(0, 0));

    }

    @Test
    public void testSimpleBoard2() {
        // given
        int[] targetState = new int[] {1,2,1,
                                       1,1,2};

        int[] startState =  new int[] {0,0,0,
                                       0,0,0};

        // when
        Node successNode = findPathToTargetState(startState, targetState);

        // then
        assertThat(successNode).isNotNull();
        List<Coordinate> moveSet = createMoveSet(successNode);
        assertThat(moveSet)
                .extracting("x", "y")
                .containsExactly(
                        tuple(1, 1),
                        tuple(2, 0));

    }

    public Node findPathToTargetState(int[] startState, int[] targetState) {
//        printBoard(startState);
        Node rootNode = new Node(null, -1, Arrays.copyOf(startState, startState.length));
        if(Arrays.equals(rootNode.board, targetState)) {
            return rootNode;
        }
        Node successNode = null;
        while(successNode == null) {
            for(int i = 0; i < 10; i++) {
                rootNode = new Node(null, -1, Arrays.copyOf(startState, startState.length));
                successNode = calculate_it(rootNode, targetState, i);
                if (successNode != null) {
                    break;
                }
            }
        }
        return successNode;
    }

    private Node doMove(Node parentNode, int move) {
        int[] board = calculateNextBoard(parentNode, move);
        Node node = new Node(parentNode, move, board);
        return node;
    }

    private static class Coordinate {
        int x;
        int y;

        public Coordinate(int move) {
            this(calculateX(move), calculateY(move));
        }

        public Coordinate(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public static int calculateX(int move) {
            return move % width;
        }

        public static int calculateY(int move) {
            return move / width;
        }
    }

    private int[] calculateNextBoard(Node parentNode, int move) {
        int[] board = new int[parentNode.board.length];
        int x = Coordinate.calculateX(move);
        int y = Coordinate.calculateY(move);

        for(int i = 0; i < board.length; i++) {
            if (Coordinate.calculateX(i) == x || Coordinate.calculateY(i) == y) {
                board[i] = (parentNode.board[i] + 1) % nrStates;
            } else {
                board[i] = parentNode.board[i];
            }
        }
        return board;
    }


    List<Coordinate> createMoveSet(Node node) {
       List<Coordinate> coordinates = new ArrayList<>();
       Node currentNode = node;
       do {
           coordinates.add(new Coordinate(currentNode.move));
           currentNode = currentNode.parent;
       } while(currentNode.parent != null);

       return coordinates;
    }

    private Node calculate_it(Node parentNode, int[] targetState, int movesLeft) {
        if(Arrays.equals(parentNode.board, targetState)) {
            System.out.println("Found it!");
            return parentNode;
        }

        if (movesLeft < 0) {
//            System.err.println("No moves left");
            return null;
        }

        Node[] nodes = new Node[parentNode.board.length];
        for (int i = 0; i < nodes.length; i++) {
            Node nextNode = doMove(parentNode, i);
            nodes[i] = nextNode;
        }
        parentNode.board = null; // save memory
        Node successNode = null;
        for (int i = 0; i < nodes.length; i++) {
            successNode = calculate_it(nodes[i], targetState, movesLeft-1);
            if (successNode != null) {
                break;
            }
        }
        return successNode;
    }
}