/home/archives/knight-path/branch.1/branch.0/delta5682.018/knight-path/main.cc

Go to the documentation of this file.

//
// knight-path - shortest knight path between two squares
// Copyright (C) 2011 Peter Miller
//
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 3 of the License, or (at
// your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public License along
// with this program. If not, see <http://www.gnu.org/licenses/>.
//

#include <cstdlib>
#include <cstring>
#include <iostream>
#include <fstream>
#include <sys/time.h>
#include <sys/resource.h>
#include <unistd.h>
#include <iomanip>
#include <sstream>

#include <lib/print_version.h>
#include <lib/progname.h>

#include <knight-path/position.h>
#include <knight-path/solver.h>


static bool print_seconds;
static bool print_board;


static double
cpu_seconds(void)
{
#if 0
    struct rusage r;
    if (getrusage(RUSAGE_SELF, &r) < 0)
    {
        perror("getrusage");
        exit(EXIT_FAILURE);
    }
    return
        (
            (r.ru_utime.tv_sec + r.ru_stime.tv_sec)
        +
            1e-6 * (r.ru_utime.tv_usec + r.ru_stime.tv_usec)
        );
#else
    struct timeval tv;
    if (gettimeofday(&tv, 0) < 0)
    {
        perror("gettimeofday");
        exit(EXIT_FAILURE);
    }
    return (tv.tv_sec + 1e-6 * tv.tv_usec);
#endif
}


static void
process(std::istream &f, const solver::pointer &how)
{
    //
    // Read the start and finish positions.
    //
    position p1;
    f >> p1;
    position p2;
    f >> p2;

    //
    // Solve for the shortest path.
    //
    double t1 = cpu_seconds();
    solver::list_t result = how->solve(p1, p2);
    double t2 = cpu_seconds();
    if (result.empty())
    {
        std::cerr << "no path from " << p1 << " to " << p2 << std::endl;
        exit(EXIT_FAILURE);
    }
    assert(p2 == result.back());

    if (print_seconds)
    {
        //
        // Print the time used.  This helps measure which solution algorithm
        // is the best one.
        //
        std::cout << std::fixed << std::setprecision(6) << (t2 - t1)
            << " seconds" << std::endl;
    }

    //
    // Print the list of positions.
    //
    std::cout << "path:";
    for
    (
        solver::list_t::const_iterator it = result.begin();
        it != result.end();
        ++it
    )
    {
        std::cout << ' ';
        std::cout << *it;
    }
    std::cout << std::endl;

    if (print_board)
    {
        //
        // Plot it on a chess board, to make it easier to visualise.
        //
        char board[8][8];
        memset(board, ' ', sizeof(board));
        p1.plot(board, '0');
        char n = '1';
        for
        (
            solver::list_t::const_iterator it = result.begin();
            it != result.end();
            ++it, ++n
        )
        {
            it->plot(board, n);
        }
        for (int y = 7; y >= 0; --y)
        {
            std::cout << "  +---+---+---+---+---+---+---+---+" << std::endl;
            std::cout << (y + 1) << " |";
            for (int x = 0; x < 8; ++x)
            {
                std::cout << ' ';
                std::cout << board[y][x];
                std::cout << " |";
            }
            std::cout << std::endl;
        }
        std::cout << "  +---+---+---+---+---+---+---+---+" << std::endl;
        std::cout << "    a   b   c   d   e   f   g   h" << std::endl;
    }
}


static void
usage(void)
{
    std::cerr << "Usage: " << progname_get() << " [ -a <name> ][ <filename> ]"
        << std::endl;
    std::cerr << "       " << progname_get() << " -V" << std::endl;
    exit(EXIT_FAILURE);
}


int
main(int argc, char **argv)
{
    progname_set(argv[0]);
    solver::pointer how;
    for (;;)
    {
        int c = getopt(argc, argv, "a:blsV");
        if (c < 0)
            break;
        switch (c)
        {
        case 'a':
            if (how)
            {
                std::cerr << "only one algorithm may be specified" << std::endl;
                exit(EXIT_FAILURE);
            }
            how = solver::factory(optarg);
            break;

        case 'b':
            print_board = true;
            break;

        case 'l':
            solver::list_algorithms();
            return EXIT_SUCCESS;

        case 's':
            print_seconds = true;
            break;

        case 'V':
            print_version();
            return EXIT_SUCCESS;

        default:
            usage();
            // NOTREACHED
        }
    }

    // By default, use the brute force solver.
    if (!how)
        how = solver::factory("fastest");

    switch (argc - optind)
    {
    case 0:
        process(std::cin, how);
        break;

    case 1:
        {
            const char *filename = argv[optind];
            std::ifstream f;
            f.open(filename);
            if (f.fail())
            {
                perror(filename);
                exit(1);
            }
            process(f, how);
        }
        break;

    case 2:
        {
            std::string s = argv[optind];
            s += " ";
            s += argv[optind + 1];
            std::istringstream f(s);
            process(f, how);
        }
        break;

    default:
        usage();
    }
    return EXIT_SUCCESS;
}