path: root/challenge-118/paulo-custodio/cpp/ch-2.cpp

/*
Challenge 118

TASK #2 - Adventure of Knight
Submitted by : Cheok - Yin Fung
A knight is restricted to move on an 8�8 chessboard.The knight is denoted by
N and its way of movement is the same as what it is defined in Chess.
* represents an empty square. x represents a square with treasure.

The Knight�s movement is unique.It may move two squares vertically and one
square horizontally, or two squares horizontally and one square vertically
(with both forming the shape of an L).

There are 6 squares with treasures.

Write a script to find the path such that Knight can capture all treasures.
The Knight can start from the top - left square.

  a b c d e f g h
8 N * * * * * * * 8
7 * * * * * * * * 7
6 * * * * x * * * 6
5 * * * * * * * * 5
4 * * x * * * * * 4
3 * x * * * * * * 3
2 x x * * * * * * 2
1 * x * * * * * * 1
  a b c d e f g h

https://en.m.wikipedia.org/wiki/Knight%27s_tour
*/

#include <cassert>
#include <cctype>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

#define NROWS       8
#define NCOLS       8
#define MAX_MOVES   8

struct Board {
    Board() {
        clear();
    }

    void clear() {
        memset(cells, 0, NROWS);
    }

    bool empty() const {
        for (int i = 0; i < NROWS; i++)
            if (cells[i] != 0)
                return false;
        return true;
    }

    void set(int row, int col) {
        assert(row >= 0 && row < NROWS);
        assert(col >= 0 && col < NCOLS);
        int mask = 1 << col;
        cells[row] |= mask;
    }

    void reset(int row, int col) {
        assert(row >= 0 && row < NROWS);
        assert(col >= 0 && col < NCOLS);
        int mask = 1 << col;
        cells[row] &= ~mask;
    }

    bool peek(int row, int col) const {
        assert(row >= 0 && row < NROWS);
        assert(col >= 0 && col < NCOLS);
        int mask = 1 << col;
        return (cells[row] & mask) == 0 ? false : true;
    }

    char cells[NROWS];
};

struct Game {
    Game() {
        clear();
    }

    void clear() {
        row = col = 0;
        visited.clear();
        treasure.clear();
        path.clear();
    }

    void set_visited(int row, int col) {
        visited.set(row, col);
    }

    bool peek_visited(int row, int col) const {
        return visited.peek(row, col);
    }

    void set_treasure(int row, int col) {
        treasure.set(row, col);
    }

    void clear_treasure(int row, int col) {
        treasure.reset(row, col);
    }

    bool peek_treasure(int row, int col) const {
        return treasure.peek(row, col);
    }

    bool done() const {
        return treasure.empty();
    }

    void move(int row, int col) {
        set_visited(row, col);
        clear_treasure(row, col);
        path += 'a' + col;
        path += to_string(NROWS - row);
        path += " ";
        this->row = row;
        this->col = col;
    }

    friend ostream& operator<<(ostream& os, const Game& game) {
        os << "  a b c d e f g h" << endl;
        for (int row = 0; row < NROWS; row++) {
            os << NROWS - row;
            for (int col = 0; col < NCOLS; col++) {
                if (game.peek_treasure(row, col))
                    os << " x";
                else if (game.row == row && game.col == col)
                    os << " N";
                else if (game.peek_visited(row, col))
                    os << " .";
                else
                    os << " *";
            }
            os << " " << NROWS - row << endl;
        }
        os << "  a b c d e f g h" << endl;
        os << endl << "> " << game.path << endl;
        return os;
    }

    void parse_header() {
        string line;
        if (!getline(cin, line)) {
            cerr << "expected header or footer" << endl;
            exit(EXIT_FAILURE);
        }
        const char* p = line.c_str();
        while (*p && isspace(*p)) p++;
        if (strncmp(p, "a b c d e f g h", 15) != 0) {
            cerr << "invalid header or footer" << endl;
            exit(EXIT_FAILURE);
        }
    }

    void parse_row(int row) {
        string line;
        if (!getline(cin, line)) {
            cerr << "expected row " << NROWS - row << endl;
            exit(EXIT_FAILURE);
        }
        const char* p = line.c_str();
        while (*p && isspace(*p)) p++;
        if (!isdigit(*p) || *p - '0' != NROWS - row) {
            cerr << "invalid row " << NROWS - row << endl;
            exit(EXIT_FAILURE);
        }
        p++;
        for (int col = 0; col < NCOLS; col++) {
            while (*p && isspace(*p)) p++;
            switch (*p) {
                case 'N': move(row, col); break;
                case 'x': set_treasure(row, col); break;
                case '*': break;
                default:
                    cerr << "invalid row " << NROWS - row << endl;
                    exit(EXIT_FAILURE);
            }
            p++;
        }
    }

    void parse() {
        clear();
        parse_header();
        for (int row = 0; row < NROWS; row++)
            parse_row(row);
        parse_header();
    }

    int row{ 0 }, col{ 0 };
    Board visited, treasure;
    string path;
};

struct Move {
    int row, col, num_moves;

    Move(int row = 0, int col = 0, int num_moves = 0)
        : row(row), col(col), num_moves(num_moves) {}
};

void try_move(vector<Move>& moves, Game& game, int nrow, int ncol) {
    if (nrow < 0 || nrow >= NROWS) return;
    if (ncol < 0 || ncol >= NCOLS) return;
    if (game.peek_visited(nrow, ncol)) return;

    moves.push_back(Move(nrow, ncol, 0));
}

void try_num_moves(vector<Move>& moves, Game& game, int row, int col) {
    moves.clear();
    try_move(moves, game, row + 2, col + 1);
    try_move(moves, game, row + 2, col - 1);
    try_move(moves, game, row - 2, col + 1);
    try_move(moves, game, row - 2, col - 1);
    try_move(moves, game, row + 1, col + 2);
    try_move(moves, game, row - 1, col + 2);
    try_move(moves, game, row + 1, col - 2);
    try_move(moves, game, row - 1, col -