UVA - 10477 - The Hybrid Knight

This article will explain my thought process to solve a problem called The Hybrid Knight (PDF) from UVA Online Judge. Read the original problem statement before reading this article.

Keywords: Graph, Chessboard Problem, Single-source Shortest Paths

Objective

Given:

Dimension of the board.
Origin position of a hybrid knight.
Destination position of a hybrid knight.
Hybrid knight move set:
1. 4 types of moves: knight, mutant knight, mutant pawn, final attacking mutant pawn.
2. Move cycles: knight → mutant knight → mutant pawn → knight (repeat, circular).
3. Start with any type of moves, followed by the move cycles.
4. Optionally finish with the final attacking mutant pawn move.

We want to:

Find the minimum total moves to travel from the origin to the destination.

Glossary

Graph — A structure consisting of a set of objects where some pairs of the objects are related.
Chessboard Problem — A class of puzzles that involve solving a problem based on a chessboard.
Single-source Shortest Paths (SSSP) — A problem of finding the shortest paths from a single source vertex to all other vertices in a graph.
Breadth-first Search (BFS) — A graph traversal algorithm that starts from a source vertex and explores the graph level by level.

Observation

We could model the relationship between the positions and the moves as a graph, where the positions are the vertices and the moves are the edges. For each vertices, we have 24 edges (8 knight moves, 8 mutant knight moves, 4 mutant pawn moves, 4 final attacking mutant pawn moves). This is a variation of the chessboard problem and the graph for chessboard problem can be simplified as a 2 dimensional array of rows and columns.

We want to find the minimum total moves from a single origin to a single destination, which is similar to the concept of SSSP. Starting from the origin position, we want to explore every possible positions by following the move rules. At the first step of the traversal, we are given a flexibility to choose the type of moves that we want to perform, and then the subsequent moves must follow the move cycles or stop immediately after using the attacking move. During each iteration of the traversal, we keep track of the position, type of move and total moves. We also need to keep track of the iteration state to avoid re-visiting a state.

Algorithm

There are multiple ways to implement SSSP, but the most optimal way for this problem is by using BFS. Since BFS traverse the graph level-by-level, by the time we reach the destination position, it should be the minimum time to reach that destination position.

To avoid re-visit, we store the visit state on a 3 dimensional array of move type, row and column. This will ensure that the path taken by each types of the piece to reach every possible positions are minimized.

The time complexity of this solution is O({total queries} * {board size} * {board size} * {total moves}) or O(10^6).

Implementation

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * 10477 - The Hybrid Knight
 * Time limit: 3.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1418
 */
public class Main {
    public static void main(final String... args) {
        final Scanner in = new Scanner(new BufferedInputStream(System.in));
        final PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        final Process process = new Process();

        for (int setId = 1; ; setId++) {
            final Input input = new Input();
            input.setId = setId;
            input.boardSize = in.nextInt();
            if (input.isEOF()) break;
            input.totalQueries = in.nextInt();
            input.queries = new int[input.totalQueries][2];
            for (int queryId = 0; queryId < input.totalQueries; queryId++) {
                input.queries[queryId][0] = in.nextInt();
                input.queries[queryId][1] = in.nextInt();
            }

            final Output output = process.process(input);
            out.format("Set %d:\n", output.setId);
            for (final int answer : output.answers) {
                out.println(answer);
            }
        }

        in.close();
        out.flush();
        out.close();
    }
}

class Input {
    public int setId;
    public int boardSize;
    public int totalQueries;
    public int[][] queries;

    public boolean isEOF() {
        return boardSize == 0;
    }
}

class Output {
    public int setId;
    public int[] answers;
}

class Process {
    public Output process(final Input input) {
        final Output output = new Output();
        output.setId = input.setId;
        output.answers = new int[input.totalQueries];

        for (int queryId = 0; queryId < input.totalQueries; queryId++) {
            final int[] query = input.queries[queryId];
            final int answer = findTotalMoves(input.boardSize, query);
            output.answers[queryId] = answer;
        }

        return output;
    }

    private int findTotalMoves(final int boardSize, final int[] originAndDestination) {
        final int originId = originAndDestination[0];
        final int destinationId = originAndDestination[1];
        if (originId == destinationId) {
            return 0;
        }

        final int[] origin = getPosition(boardSize, originId);
        final int[] destination = getPosition(boardSize, destinationId);

        final Queue<Path> pathQueue = new LinkedList<>();
        final Path initial = new Path(boardSize, origin);
        pathQueue.add(initial);

        final boolean[][][] visited = new boolean[4][boardSize][boardSize];
        visited[initial.type][initial.position[0]][initial.position[1]] = true;

        while (!pathQueue.isEmpty()) {
            final Path current = pathQueue.remove();

            final boolean finished = Arrays.equals(current.position, destination);
            if (finished) {
                return current.distance;
            }

            for (final Path next : current.nextPaths()) {
                if (visited[next.type][next.position[0]][next.position[1]]) {
                    continue;
                }
                pathQueue.add(next);
                visited[next.type][next.position[0]][next.position[1]] = true;
            }
        }

        return Integer.MAX_VALUE;
    }

    private int[] getPosition(final int boardSize, final int id) {
        final int id0 = id - 1;
        final int row = id0 / boardSize;
        final int col = id0 % boardSize;

        return new int[]{row, col};
    }
}

class Path {
    public static final int KNIGHT = 0;
    public static final int MUTANT_KNIGHT = 1;
    public static final int MUTANT_PAWN = 2;
    public static final int ATTACKING_MUTANT_PAWN = 3;

    public final int boardSize;
    public final int[] position;
    public final int distance;
    public final int type;

    public Path(final int boardSize, final int[] origin) {
        this(boardSize, origin, 0, KNIGHT);
    }

    private Path(final int boardSize, final int[] position, final int distance, final int type) {
        this.boardSize = boardSize;
        this.position = position;
        this.distance = distance;
        this.type = type;
    }

    public Path[] nextPaths() {
        final LinkedList<Path> nextPaths = new LinkedList<>();

        final int[][] knight = knightMoves(position);
        final int[][] mutantKnight = mutantKnightMoves(position);
        final int[][] mutantPawn = mutantPawnMoves(position);
        final int[][] attackingMutantPawn = attackingMutantPawnMoves(position);

        if (distance == 0) {
            for (final int[] position : knight) {
                if (!isValid(position)) continue;
                final Path path = new Path(boardSize, position, distance + 1, KNIGHT);
                nextPaths.add(path);
            }

            for (final int[] position : mutantKnight) {
                if (!isValid(position)) continue;
                final Path path = new Path(boardSize, position, distance + 1, MUTANT_KNIGHT);
                nextPaths.add(path);
            }

            for (final int[] position : mutantPawn) {
                if (!isValid(position)) continue;
                final Path path = new Path(boardSize, position, distance + 1, MUTANT_PAWN);
                nextPaths.add(path);
            }

            for (final int[] position : attackingMutantPawn) {
                if (!isValid(position)) continue;
                final Path path = new Path(boardSize, position, distance + 1, ATTACKING_MUTANT_PAWN);
                nextPaths.add(path);
            }

        } else if (type == KNIGHT) {
            for (final int[] position : mutantKnight) {
                if (!isValid(position)) continue;
                final Path path = new Path(boardSize, position, distance + 1, MUTANT_KNIGHT);
                nextPaths.add(path);
            }

            for (final int[] position : attackingMutantPawn) {
                if (!isValid(position)) continue;
                final Path path = new Path(boardSize, position, distance + 1, ATTACKING_MUTANT_PAWN);
                nextPaths.add(path);
            }

        } else if (type == MUTANT_KNIGHT) {
            for (final int[] position : mutantPawn) {
                if (!isValid(position)) continue;
                final Path path = new Path(boardSize, position, distance + 1, MUTANT_PAWN);
                nextPaths.add(path);
            }

            for (final int[] position : attackingMutantPawn) {
                if (!isValid(position)) continue;
                final Path path = new Path(boardSize, position, distance + 1, ATTACKING_MUTANT_PAWN);
                nextPaths.add(path);
            }

        } else if (type == MUTANT_PAWN) {
            for (final int[] position : knight) {
                if (!isValid(position)) continue;
                final Path path = new Path(boardSize, position, distance + 1, KNIGHT);
                nextPaths.add(path);
            }

            for (final int[] position : attackingMutantPawn) {
                if (!isValid(position)) continue;
                final Path path = new Path(boardSize, position, distance + 1, ATTACKING_MUTANT_PAWN);
                nextPaths.add(path);
            }
        }

        return nextPaths.toArray(new Path[0]);
    }

    private int[][] knightMoves(final int[] origin) {
        return new int[][]{
            new int[]{origin[0] - 1, origin[1] - 2},
            new int[]{origin[0] - 1, origin[1] + 2},
            new int[]{origin[0] - 2, origin[1] - 1},
            new int[]{origin[0] - 2, origin[1] + 1},
            new int[]{origin[0] + 1, origin[1] - 2},
            new int[]{origin[0] + 1, origin[1] + 2},
            new int[]{origin[0] + 2, origin[1] - 1},
            new int[]{origin[0] + 2, origin[1] + 1},
        };
    }

    private int[][] mutantKnightMoves(final int[] origin) {
        return new int[][]{
            new int[]{origin[0] - 1, origin[1] - 3},
            new int[]{origin[0] - 1, origin[1] + 3},
            new int[]{origin[0] - 3, origin[1] - 1},
            new int[]{origin[0] - 3, origin[1] + 1},
            new int[]{origin[0] + 1, origin[1] - 3},
            new int[]{origin[0] + 1, origin[1] + 3},
            new int[]{origin[0] + 3, origin[1] - 1},
            new int[]{origin[0] + 3, origin[1] + 1},
        };
    }

    private int[][] mutantPawnMoves(final int[] origin) {
        return new int[][]{
            new int[]{origin[0], origin[1] - 1},
            new int[]{origin[0], origin[1] + 1},
            new int[]{origin[0] - 1, origin[1]},
            new int[]{origin[0] + 1, origin[1]},
        };
    }

    private int[][] attackingMutantPawnMoves(final int[] origin) {
        return new int[][]{
            new int[]{origin[0] - 1, origin[1] - 1},
            new int[]{origin[0] - 1, origin[1] + 1},
            new int[]{origin[0] + 1, origin[1] - 1},
            new int[]{origin[0] + 1, origin[1] + 1},
        };
    }

    private boolean isValid(final int[] position) {
        final boolean valid1 = 0 <= position[0] && position[0] < boardSize;
        final boolean valid2 = 0 <= position[1] && position[1] < boardSize;
        return valid1 && valid2;
    }
}