5
\$\begingroup\$

The development and testing was performed on a Dell M6400 Laptop (Intel Core 2 Duo) running Centos 7, g++ compiler version 4.8.5, compiler switches -O3 -std=c++0x -D__cplusplus=201103L. (machine bought August 2009 with Windows XP ). It was also tested on a four core i7 based version of CentOS 7 with 12GB of DDR3 RAM (built 2011).

The code, makefile and gz compressed gprof output are posted on GitHub.

This is a refactored version of the code presented in Recursive Breadth First Search for Knights Tour.

Please make any and all suggestions on improvement, I am especially interested in the following
1. Are the any Containers or Library Algorithms in C++11 that would have decreased the amount of code or improved the quality of the code?
2. Improving readability
3. Improving maintainability
4. Improved Data Encapsulation.
5. Reducing coupling between classes as much as possible.
6. More optimization (speed freak).

The code was refactored several reasons:
1. There was too much couping between the KMPath class and the KnightMovesImplementation class.
2. The KMPath class was too complex (KISS principal or Demeter's Law).
3. The KMPath class did not properly encapsule the data.
4. The recursive algorithm in the KnightMovesImplementation class was too complex.
5. Too much data was being copied.
6. The number of attempted paths was being recorded wrong.
7. The implementation was too difficult to translate to other languages.

Due to the new implementation:
1. There is about 6% less code
2. The implementation is 2 to 4 times faster than the original, based on individual test cases. 2.6 times faster in Overall statistics.
3. The output results other than the execution times and the number of attempted paths is the same.

After implementing all of suggestions from the last review, the overall timing was
The average execution time is 0.00511662 seconds
The median execution time is 0.00271199 seconds
The longest execution time is 0.0319622 seconds
The shortest execution time is 0.00229607 seconds

With the refactoring the overall timing statistics are:
The average execution time is 0.00195405 seconds
The median execution time is 0.00103346 seconds
The longest execution time is 0.00130368 seconds
The shortest execution time is 0.000716237 seconds

All classes are presented, but the classes that changed the most are first.

KMPath.h

/*
 * KMPath.h
 *
 *  Created on: Mar 18, 2016
 *  Extensively refactored: June 20, 2016
 *  Comments added: June 24, 2016
 *      Author: pacmaninbw
 *
 *      This class maintains a history of the current path for reporting purposes
 *      as well as for the search algorithm. Within the algorithm it is used as a
 *      stack, for reporting purposes it is used as a linear list.
 *
 */

#ifndef KMPATH_H_
#define KMPATH_H_

#include "KMBoardLocation.h"
#include "KMMove.h"
#include "KnightMoves.h"

class KMPath {
private:
    KMFastAccessMoveCollection m_RecordOfMoves;

public:
    KMPath() = default;
    KMPath(const KMPath &Original) = default;
    virtual ~KMPath() = default;
    void AddMoveToPath(KMMove Move) { m_RecordOfMoves.push_back(Move); }
    void RemoveLastMove() { m_RecordOfMoves.pop_back(); }
    unsigned int GetLength() const { return m_RecordOfMoves.size(); }
    KMFastAccessMoveCollection GetRecordOfMoves() const { return m_RecordOfMoves; }
    KMMove GetLastMove();
    friend std::ostream &operator<<( std::ostream &output, KMPath &Path)
    {
        output << "This path contains " << Path.GetLength() << " moves." << std::endl;
        KMFastAccessMoveCollection RecordOfMoves = Path.GetRecordOfMoves();
        for (auto CurrentMove: RecordOfMoves) {
            output << CurrentMove << std::endl;
        }
        return output;
    }
};

#endif /* KMPATH_H_ */

KMPath.cpp

/*
 * KMPath.cpp
 *
 *  Created on: Mar 18, 2016
 *      Author: pacmaninbw
 */

#include <stdexcept>
#include "KMPath.h"
#include "KMBoardDimensionConstants.h"

KMMove KMPath::GetLastMove()
{
    KMMove LastMove;
    if (m_RecordOfMoves.size() > 0) {
        LastMove = m_RecordOfMoves.back();
    }
    else
    {
        std::cerr << "In KMPath::GetLastMove() : There was no last move" << std::endl;
    }

    return LastMove;
}

KMMoveFilters.h

/*
 * KMMoveFilters.h
 *
 *  Created on: Jun 20, 2016
 *      Author: pacmaninbw
 *
 *      This class provides all the possible Knight moves for a specified location
 *      on the chess board. In the center of the chess board there are 8 possible
 *      moves. In the middle of the edge on the chess board there are 4 possible
 *      moves. In a corner of the chess board there are 2 possible moves. The
 *      location on the board provides the first filter.
 *      Slicing is used to allow the program to complete in a reasonable finite
 *      amount of time. The slicing method can be varied, the default slicing
 *      method is the knight can't return to any row or column it has previously
 *      visited. The slicing is the second filter.
 */

#ifndef KMMOVEFILTERS_H_
#define KMMOVEFILTERS_H_

#include <vector>
#include "KnightMoves.h"
#include "KMMove.h"

class KMMoveFilters {
private:
    std::vector<KMBoardLocation> m_VisitedLocations;
    std::vector<unsigned int> m_VisitedRows;
    std::vector<unsigned int> m_VisitedColumns;
    unsigned int m_SingleSideBoardDimension;
    KnightMovesMethodLimitations m_PathLimitations;
    static const KMRandomAccessMoveCollection AllPossibleMoves;
    // The 8 possible moves the knight can make.
    static KMMove Left1Up2;
    static KMMove Left2Up1;
    static KMMove Left2Down1;
    static KMMove Left1Down2;
    static KMMove Right1Up2;
    static KMMove Right2Up1;
    static KMMove Right2Down1;
    static KMMove Right1Down2;

protected:
    bool IsNotPreviouslyVisited(KMMove Move) const { return IsNotPreviouslyVisited(Move.GetNextLocation()); };
    bool IsNotPreviouslyVisited(KMBoardLocation Destination) const;

public:
    KMMoveFilters();
    void ResetFilters(unsigned int BoardDimension, KnightMovesMethodLimitations SlicingMethod) {m_SingleSideBoardDimension = BoardDimension; m_PathLimitations = SlicingMethod; }
    virtual ~KMMoveFilters() = default;
    void PushVisited(KMBoardLocation Location);
    void PopVisited();
    KMRandomAccessMoveCollection GetPossibleMoves(const KMBoardLocation CurrentLocation) const;
};

#endif /* KMMOVEFILTERS_H_ */

KMMoveFilters.cpp

/*
 * KMMoveFilters.cpp
 *
 *  Created on: Jun 20, 2016
 *      Author: pacmaninbw
 */

#include <stdexcept>
#include <algorithm>
#include "KMBoardDimensionConstants.h"
#include "KMMoveFilters.h"

KMMoveFilters::KMMoveFilters()
 : m_SingleSideBoardDimension{DefaultBoardDimensionOnOneSide},
   m_PathLimitations{DenyByPreviousRowOrColumn}
{

}

const int Left1 = -1;
const int Left2 = -2;
const int Down1 = -1;
const int Down2 = -2;
const int Right1 = 1;
const int Right2 = 2;
const int Up1 = 1;
const int Up2 = 2;

KMMove KMMoveFilters::Left1Up2(Left1, Up2, DefaultBoardDimensionOnOneSide);
KMMove KMMoveFilters::Left2Up1(Left2, Up1, DefaultBoardDimensionOnOneSide);
KMMove KMMoveFilters::Left2Down1(Left2, Down1, DefaultBoardDimensionOnOneSide);
KMMove KMMoveFilters::Left1Down2(Left1, Down2, DefaultBoardDimensionOnOneSide);
KMMove KMMoveFilters::Right1Up2(Right1, Up2, DefaultBoardDimensionOnOneSide);
KMMove KMMoveFilters::Right2Up1(Right2, Up1, DefaultBoardDimensionOnOneSide);
KMMove KMMoveFilters::Right2Down1(Right2, Down1, DefaultBoardDimensionOnOneSide);
KMMove KMMoveFilters::Right1Down2(Right1, Down2, DefaultBoardDimensionOnOneSide);

const KMRandomAccessMoveCollection KMMoveFilters::AllPossibleMoves{
    Left1Up2,
    Left2Up1,
    Left2Down1,
    Left1Down2,
    Right1Up2,
    Right2Up1,
    Right2Down1,
    Right1Down2,
};

KMRandomAccessMoveCollection KMMoveFilters::GetPossibleMoves(const KMBoardLocation CurrentLocation) const
{
    KMRandomAccessMoveCollection PossibleMoves;
    for (auto PossibeMove : AllPossibleMoves) {
        PossibeMove.SetBoardDimension(m_SingleSideBoardDimension);
        PossibeMove.SetOriginCalculateDestination(CurrentLocation);
        if ((PossibeMove.IsValid()) && (IsNotPreviouslyVisited(PossibeMove))) {
            PossibleMoves.push_back(PossibeMove);
        }
    }
    return PossibleMoves;
}

bool KMMoveFilters::IsNotPreviouslyVisited(KMBoardLocation PossibleDestination) const
{
    bool NotPrevioslyVisited = true;

    if (!m_VisitedLocations.empty()) {    // This is always a test, we can't move backwards
        if (std::find(m_VisitedLocations.begin(), m_VisitedLocations.end(), PossibleDestination)
            != m_VisitedLocations.end()) {
            NotPrevioslyVisited = false;
        }
    }

    switch (m_PathLimitations) {
    default :
        throw std::runtime_error("KMPath::CheckMoveAgainstPreviousLocations : Unknown type of Path Limitation.");
    case DenyByPreviousLocation :
        // Always tested above.
        break;
    case DenyByPreviousRowOrColumn:
        if ((!m_VisitedRows.empty()) && (!m_VisitedColumns.empty())) {
            unsigned int PossibleRow = PossibleDestination.GetRow();
            if (std::find(m_VisitedRows.begin(), m_VisitedRows.end(), PossibleRow) != m_VisitedRows.end()) {
                NotPrevioslyVisited = false;
                break;
            }
            unsigned int PossibleColum = PossibleDestination.GetColumn();
            if (std::find(m_VisitedColumns.begin(), m_VisitedColumns.end(), PossibleColum) != m_VisitedColumns.end()) {
                NotPrevioslyVisited = false;
            }
        }
        break;
    }

    return NotPrevioslyVisited;
}

void KMMoveFilters::PushVisited(KMBoardLocation Location)
{
    m_VisitedRows.push_back(Location.GetRow());
    m_VisitedColumns.push_back(Location.GetColumn());
    m_VisitedLocations.push_back(Location);
}

void KMMoveFilters::PopVisited()
{
    m_VisitedRows.pop_back();
    m_VisitedColumns.pop_back();
    m_VisitedLocations.pop_back();
}

KnightMovesImplementation.h

/*
 * KnightMovesImplementation.h
 *
 *  Created on: Mar 18, 2016
 *  Modified on: June 20, 2016
 *      Author: pacmaninbw
 *
 *      This class provides the search for all the paths a Knight on a chess
 *      board can take from the point of origin to the destination. It
 *      implements a modified Knights Tour. The classic knights tour problem
 *      is to visit every location on the chess board without returning to a
 *      previous location. That is a single path for the knight. This
 *      implementation returns all possible paths from point a to point b.
 *      The actual implementation is documented in the CPP file because it
 *      can be changed. This head file provides the public interface which
 *      should not be changed. The public interface may be moved to a
 *      super class in the future.
 */

#ifndef KNIGHTMOVESIMPLEMENTATION_H_
#define KNIGHTMOVESIMPLEMENTATION_H_

#include "KMPath.h"
#include "KMOutputData.h"
#include "KMMoveFilters.h"

class KnightMovesImplementation {
private:
    KMBoardLocation m_PointOfOrigin;
    KMBoardLocation m_Destination;
    unsigned int m_SingleSideBoardDimension;
    KnightMovesMethodLimitations m_PathLimitations;
    KMOutputData m_Results;
    KMMoveFilters m_MoveFilters;
    KMPath m_Path;

protected:
    bool CalculatePath(KMMove CurrentMove);        // Recursive function
    void InitPointOfOrigin(KMBaseData UserData);
    void InitDestination(KMBaseData UserData);

public:
    KnightMovesImplementation(KMBaseData UserData);
    virtual ~KnightMovesImplementation() = default;
    KMOutputData CalculatePaths();
};

#endif /* KNIGHTMOVESIMPLEMENTATION_H_ */

KnightMovesImplementation.cpp

/*
 * KnightMovesImplementation.cpp
 *
 *  Created on: Mar 18, 2016
 *  Modified on: June 21, 2016
 *  Commented on: June 24, 2016
 *      Author: pacmaninbw
 *
 *      This class implements the search for all possible paths for a Knight
 *      on a chess board from one particular square on the board to another
 *      particular square on the board.
 *
 *      The current implementation is a Recursive Breadth First Search. Conceptually
 *      the algorithm implements a B+ tree with a maximum of 8 possible branches
 *      at each level. The root of the tree is the point of origin. A particular
 *      path terminates in a leaf. A leaf is the result of either reaching the
 *      destination, or reaching a point where there are no more branches to
 *      traverse.
 *
 *      The m_Path variable is used as a stack within the search.
 *
 *      The public interface CalculatePaths establishes the root and creates
 *      the first level of branching. The protected interface CalculatePath
 *      performs the recursive depth first search, however, the
 *      m_MoveFilters.GetPossibleMoves() function it calls performs a breadth
 *      first search of the current level.
 *
 */

#include "KnightMoves.h"
#include "KnightMovesImplementation.h"
#include "KMBoardDimensionConstants.h"

KnightMovesImplementation::KnightMovesImplementation(KMBaseData UserInputData)
 : m_SingleSideBoardDimension{UserInputData.m_DimensionOneSide},
   m_PathLimitations{UserInputData.m_LimitationsOnMoves}
{
    InitPointOfOrigin(UserInputData);
    InitDestination(UserInputData);
    m_MoveFilters.ResetFilters(static_cast<unsigned int>(UserInputData.m_DimensionOneSide), UserInputData.m_LimitationsOnMoves);
    m_Results.SetPointOfOrigin(m_PointOfOrigin);
    m_Results.SetDestination(m_Destination);
    m_Results.SetBoardDimension(m_SingleSideBoardDimension);
    m_Results.SetSlicingMethod(m_PathLimitations);
}

void KnightMovesImplementation::InitPointOfOrigin(KMBaseData UserInputData)
{
    m_PointOfOrigin.SetRow(UserInputData.m_StartRow);
    m_PointOfOrigin.SetColumn(UserInputData.m_StartColumn);
    m_PointOfOrigin.SetName(UserInputData.m_StartName);
    m_PointOfOrigin.SetBoardDimension(m_SingleSideBoardDimension);
}

void KnightMovesImplementation::InitDestination(KMBaseData UserInputData)
{
    m_Destination.SetRow(UserInputData.m_TargetRow);
    m_Destination.SetColumn(UserInputData.m_TargetColumn);
    m_Destination.SetName(UserInputData.m_TargetName);
    m_Destination.SetBoardDimension(m_SingleSideBoardDimension);
}

KMOutputData KnightMovesImplementation::CalculatePaths()
{
    KMRandomAccessMoveCollection PossibleFirstMoves = m_MoveFilters.GetPossibleMoves(m_PointOfOrigin);

    if (PossibleFirstMoves.empty())
    {
        std::cerr << "No Possible Moves in KnightMovesImplementation::CalculatePaths" << std::endl;
    }
    else
    {
        for (auto CurrentMoveIter : PossibleFirstMoves)
        {
            KMMove CurrentMove = CurrentMoveIter;
            CurrentMove.SetOriginCalculateDestination(m_PointOfOrigin);
            if (CurrentMove.IsValid()) {
                /**
                 * This might be a good place to improve performance by
                 * using multiple threads.
                 */
                CalculatePath(CurrentMove);
            }
        }
    }
    return m_Results;
}

bool KnightMovesImplementation::CalculatePath(KMMove CurrentMove)
{
    bool CompletedSearch = false;
    KMBoardLocation CurrentLocation = CurrentMove.GetNextLocation();
    m_Path.AddMoveToPath(CurrentMove);
    m_MoveFilters.PushVisited(CurrentLocation);

    if (CurrentLocation == m_Destination)
    {
        m_Results.AddPath(m_Path);
        CompletedSearch =  true;
        m_Results.IncrementAttemptedPaths();
    }
    else
    {
        if (CurrentMove.IsValid())
        {
            KMRandomAccessMoveCollection PossibleMoves = m_MoveFilters.GetPossibleMoves(CurrentLocation);
            if (!PossibleMoves.empty())
            {
                for (auto NextMove : PossibleMoves)
                {
                    CalculatePath(NextMove);
                }
            }
            else
            {
                // No more moves to test, record the attempted path
                m_Results.IncrementAttemptedPaths();
            }
        }
        else
        {
            // There is a logic error if we get here.
            std::cerr << "In KnightMovesImplementation::CalculatePath CurrentMove Not Valid" << std::endl;
        }
    }

    m_Path.RemoveLastMove();
    m_MoveFilters.PopVisited();
    return CompletedSearch;
}

KMOutputData.h

/*
 * KMOutputData.h
 *
 *  Created on: Mar 19, 2016
 *  Modified on: June 21, 2016
 *      Author: pacmaninbw
 *
 *      This class reports the data after the test is complete. Each successful
 *      path is stored for output. Statistics on all the successful paths are
 *      always provided, printing all the moves in the successful paths is
 *      optional. A count of all attempted paths is maintained and reported.
 *      The current configuration is a command line program with text output,
 *      this class could be converted to providing graphic output.
 */

#ifndef KMOUTPUTDATA_H_
#define KMOUTPUTDATA_H_

#include <vector>
#include "KMPath.h"

class KMOutputData {
private:
    KMBoardLocation m_Origin;
    KMBoardLocation m_Destination;
    unsigned int m_BoardDimension;
    std::vector<KMPath> m_PathRecords;
    unsigned int m_AttemptedPaths;
    KnightMovesMethodLimitations m_LimitationsOnMoves;
    bool m_ShowPathData;
protected:
    void OutputSlicingMethodlogy();

public:
    KMOutputData();
    virtual ~KMOutputData() = default;
    void IncrementAttemptedPaths() { m_AttemptedPaths++; }
    void AddPath(const KMPath PathData) { m_PathRecords.push_back(PathData); }
    int GetPathCount() const { return m_PathRecords.size(); }
    std::vector<KMPath> GetAllPaths() const { return m_PathRecords; }
    unsigned int GetAttempts() const { return m_AttemptedPaths; }
    void SetPointOfOrigin(KMBoardLocation Origin) { m_Origin = Origin; }
    KMBoardLocation GetPointOfOrigin() { return m_Origin; }
    void SetDestination(KMBoardLocation Destination) { m_Destination = Destination; }
    KMBoardLocation GetDestination() { return m_Destination; }
    void SetBoardDimension(unsigned int BoardDimension) { m_BoardDimension = BoardDimension; }
    unsigned int GetBoardDimension() const { return m_BoardDimension; }
    // Statistics on the returned paths.
    void ShowStats();
    double Average(std::vector<double> PathLengths);
    void SetSlicingMethod(KnightMovesMethodLimitations Limitations) { m_LimitationsOnMoves = Limitations; }
    KnightMovesMethodLimitations GetSlicingMethod() { return m_LimitationsOnMoves; }
    void DontShowPathData() { m_ShowPathData = false; }
    void ShowPathData() { m_ShowPathData = true; }
    bool GetShowPathData() const { return m_ShowPathData; }
    void ShowResults();
};

#endif /* KMOUTPUTDATA_H_ */

KMOutputData.cpp

/*
 * KMOutputData.cpp
 *
 *  Created on: Mar 19, 2016
 *  Updated June 20, 2016
 *      Author: pacmaninbw
 */

#include <vector>
#include <algorithm>
#include <functional>
#include "KMOutputData.h"

KMOutputData::KMOutputData()
 : m_BoardDimension{0}, m_AttemptedPaths{0}, m_LimitationsOnMoves{DenyByPreviousRowOrColumn}, m_ShowPathData{false}
{
}

void KMOutputData::ShowStats()
{

    std::vector<double> PathLengths;
    for (auto PathsIter : m_PathRecords)
    {
        PathLengths.push_back(static_cast<double>(PathsIter.GetLength()));
    }

    std::cout << "The average path length is " << Average(PathLengths) << std::endl;
    std::nth_element(PathLengths.begin(), PathLengths.begin() + PathLengths.size()/2, PathLengths.end());
    std::cout << "The median path length is " << PathLengths[PathLengths.size()/2] << std::endl;
    std::nth_element(PathLengths.begin(), PathLengths.begin()+1, PathLengths.end(), std::greater<int>());
    std::cout << "The longest path is " << PathLengths[0] << " moves" << std::endl;
    std::nth_element(PathLengths.begin(), PathLengths.begin()+1, PathLengths.end(), std::less<int>());
    std::cout << "The shortest path is " << PathLengths[0] << " moves" << std::endl;
}

double KMOutputData::Average(std::vector<double> PathLengths)
{
    double AverageLength = 0.0;

    for (auto PathLenthsIter : PathLengths)
    {
        AverageLength += PathLenthsIter;
    }

    AverageLength = AverageLength / static_cast<double>(PathLengths.size());

    return AverageLength;
}

void KMOutputData::ShowResults()
{
    std::cout << "The point of origin for all path searches was " << m_Origin << std::endl;
    std::cout << "The destination point for all path searches was " << m_Destination << std::endl;
    std::cout << "The number of squares on each edge of the board is " << m_BoardDimension << std::endl;
    OutputSlicingMethodlogy();
    std::cout << "There are " << m_PathRecords.size() << " Resulting Paths" << std::endl;
    std::cout << "There were " << m_AttemptedPaths << " attempted paths" << std::endl;
    ShowStats();

    if (!m_ShowPathData) {
        for (int i = 0; i < 25; i++) std::cout << "-";
        std::cout << std::endl << std::endl;
        return;
    }
    std::cout << std::endl << std::endl << std::endl << "Here is the listing of the paths" << std::endl << std::endl;


    for (auto CurrentPath : m_PathRecords)
    {
        for (int i = 0; i < 25; i++) std::cout << "-";
        std::cout << std::endl << std::endl;
        std::cout << CurrentPath << std::endl;
    }

}

void KMOutputData::OutputSlicingMethodlogy()
{
    switch (m_LimitationsOnMoves) {
    default :
        throw std::runtime_error("KnightMovesTIO::OutputSlicingMethodlogy : Unknown type of Path Limitation.");
    case DenyByPreviousLocation :
        std::cout << "The slicing methodology used to further limit searches was no repeat visits to squares on the board." << std::endl;
        break;
    case DenyByPreviousRowOrColumn:
        std::cout << "The slicing methodology used to further limit searches was no repeat visits to any rows or columns." << std::endl;
        break;
    }

}

KMBoardLocation.h

/*
 * KMBoardLocation.h
 *
 *  Created on: Mar 17, 2016
 *      Author: pacmaninbw
 */

#ifndef KMBOARDLOCATION_H_
#define KMBOARDLOCATION_H_

#include <iostream>
#include <string>

class KMBoardLocation {
private:
    std::string m_Name;
    unsigned int m_Row;
    unsigned int m_Column;
    unsigned int m_BoardDimension;
    void ThrowBoundsException(const char* FormatString);

public:
    KMBoardLocation();
    KMBoardLocation(unsigned int Row, unsigned int Column, unsigned int BoardSingleSideDimension);
    virtual ~KMBoardLocation() = default;
    std::string GetName() const { return m_Name; }
    void SetName(std::string Name) { m_Name = Name; }
    void MakeName();
    void SetRow(const unsigned int Row) { m_Row = Row; }
    unsigned int GetRow() const { return m_Row; }
    void SetColumn(const unsigned int Column) { m_Column = Column; }
    unsigned int GetColumn() const { return m_Column; }
    bool IsSet() const { return (m_Row && m_Column); }
    bool IsValid() const;
    void SetBoardDimension(unsigned int Dimension) { m_BoardDimension = Dimension; }
    int GetBoardDimension() const { return m_BoardDimension; }
    bool operator ==(const KMBoardLocation &OtherLocation) const {
        if ((m_Row == OtherLocation.m_Row) && (m_Column == OtherLocation.m_Column)) {
            return true;
        }
        return false;
    }
    friend std::ostream &operator<<( std::ostream &output, KMBoardLocation &KMLoc)
    {
        output << " " << KMLoc.GetName();
        return output;
    }
};

#endif /* KMBOARDLOCATION_H_ */

KMBoardLocation.cpp

/*
 * KMBoardLocation.cpp
 *
 *  Created on: Mar 17, 2016
 *      Author: pacmaninbw
 */

#include "KnightMoves.h"
#include <stdio.h>
#include <string>
#include <stdexcept>
#include "KMBoardLocation.h"
#include "KMBoardDimensionConstants.h"

const int ExceptionMessageBufferSize = 1024;


KMBoardLocation::KMBoardLocation()
: m_Row{0}, m_Column{0}, m_BoardDimension{DefaultBoardDimensionOnOneSide}
{
    m_Name = "";
}

KMBoardLocation::KMBoardLocation(unsigned int Row, unsigned int Column, unsigned int BoardSingleSideDimension)
 : m_Row{Row}, m_Column{Column}, m_BoardDimension{BoardSingleSideDimension}
{
    if (((m_Row < MinimumBoardLocationValue)|| (m_Row > m_BoardDimension)) ||
        ((m_Column < MinimumBoardLocationValue) || (m_Column > m_BoardDimension))) {
        ThrowBoundsException("KMBoardLocation::KMBoardLocation");
    }
    MakeName();
}

/**
 * A common chess notation for location is using A-H for rows and 1-8 for columns.
 * MakeName creates a name for the location using that notation.
 */
void KMBoardLocation::MakeName()
{
    const unsigned int RowCStrSize = 2; // Enough for a null terminated string of 1 character
    const unsigned int RowCharacterPosition = 0;
    const unsigned int RowNullTerminatorPosition = 1;

    if (((m_Row < MinimumBoardLocationValue)|| (m_Row > m_BoardDimension)) ||
        ((m_Column < MinimumBoardLocationValue) || (m_Column > m_BoardDimension))) {
        ThrowBoundsException("KMBoardLocation::MakeName()");
    }

    char RowCStr[RowCStrSize];
    RowCStr[RowCharacterPosition] = ('A' + (m_Row - 1));
    RowCStr[RowNullTerminatorPosition] = '\0';

    std::string tempRow(RowCStr);
    std::string tempColumn = std::to_string(m_Column);
    m_Name = tempRow + tempColumn;
}

void KMBoardLocation::ThrowBoundsException(const char *CallingFunction)
{
    char estrbuff[ExceptionMessageBufferSize];
    sprintf(estrbuff, "%s value out of range (%d to %d) : ", CallingFunction, MinimumBoardLocationValue, m_BoardDimension);
    std::string EMessage(estrbuff);
    sprintf(estrbuff, "Row = %d, Column = %d", m_Row, m_Column);
    EMessage.append(estrbuff);
    throw std::runtime_error(EMessage);
}

bool KMBoardLocation::IsValid() const
{
    bool ValidLocation = true;
    if (!IsSet())
    {
        ValidLocation = false;
    }
    else
    {
        if ((m_Row < MinimumBoardLocationValue)|| (m_Row > m_BoardDimension)) {
            ValidLocation = false;
        }
        if ((m_Column < MinimumBoardLocationValue)|| (m_Column > m_BoardDimension)) {
            ValidLocation = false;
        }
    }

    return ValidLocation;
}

KMMove.h

/*
 * KMMove.h
 *
 *  Created on: Mar 18, 2016
 *      Author: pacmaninbw
 */

#ifndef KMMOVE_H_
#define KMMOVE_H_

#include <vector>
#include <list>
#include "KMBoardLocation.h"

class KMMove {
private:
    int m_RowTransition;
    int m_ColumnTransition;
    int m_BoardDimension;
    KMBoardLocation m_Origin;
    KMBoardLocation m_Destination;

public:
    KMMove();
    KMMove(int RowTransition, int ColumnTransition, unsigned int BoardDimension);
    virtual ~KMMove() = default;
    bool IsValid() const { return ((((!m_RowTransition) || (!m_ColumnTransition)) || (!m_Destination.IsValid())) ? false : true); };
    void CalculateDestination();
    void SetOriginCalculateDestination(const KMBoardLocation Origin);
    KMBoardLocation GetNextLocation() const { return m_Destination; }
    void SetOrigin(KMBoardLocation Origin) { m_Origin = Origin; }
    KMBoardLocation GetOrigin() const { return m_Origin; }
    void SetRowTransition(int RowTransition){ m_RowTransition = RowTransition; }
    int GetRowTransition() const { return m_RowTransition; }
    void SetColumnTransition(int ColumnTransition){ m_ColumnTransition = ColumnTransition; }
    int GetColumnTransition() const { return m_ColumnTransition; }
    void SetBoardDimension(unsigned int BoardDimension) { m_BoardDimension = static_cast<int>(BoardDimension); }
    int GetBoardDimension() const { return m_BoardDimension; }
    void SetTransitionsAndDimension(const int RowTransition, const int ColumnTransition, const unsigned int BoardDimension) {
        m_RowTransition = RowTransition;
        m_ColumnTransition = ColumnTransition;
        m_BoardDimension = static_cast<int>(BoardDimension);
    }
    void MakeNamesForOutPut();
    friend std::ostream &operator<<( std::ostream &output, KMMove &Move)
    {
        output << "Move from " << Move.GetOrigin().GetName();
        output << " To " << Move.GetNextLocation().GetName();
        return output;
    }
};

typedef std::vector<KMMove> KMRandomAccessMoveCollection;
typedef std::list<KMMove> KMFastAccessMoveCollection;

#endif /* KMMOVE_H_ */

KMMove.cpp

/*
 * KMMove.cpp
 *
 *  Created on: Mar 18, 2016
 *      Author: pacmaninbw
 */

#include <stdexcept>
#include "KMMove.h"
#include "KMBoardDimensionConstants.h"

KMMove::KMMove()
 : m_RowTransition{0},
   m_ColumnTransition{0},
   m_BoardDimension{DefaultBoardDimensionOnOneSide}
{
}

/**
 * BoardDimension is converted to int for type safe comparisions.
 */
KMMove::KMMove(int RowTransition, int ColumnTransition, unsigned int BoardDimension)
: m_RowTransition{RowTransition},
  m_ColumnTransition{ColumnTransition},
  m_BoardDimension{static_cast<int>(BoardDimension)}
{
}

void KMMove::CalculateDestination()
{
    if (m_Origin.IsSet()) {
        m_Destination.SetRow(m_RowTransition + m_Origin.GetRow());
        m_Destination.SetColumn(m_ColumnTransition + m_Origin.GetColumn());
        m_Destination.SetBoardDimension(m_Origin.GetBoardDimension());
    }
    else
    {
        throw std::runtime_error("KMMove::CalculateDestination : Point of Origin has not been set;\n");
    }
}

void KMMove::SetOriginCalculateDestination(KMBoardLocation Origin)
{
    if (Origin.IsValid()) {
        m_Origin = Origin;
        CalculateDestination();
    }
    else
    {
        throw std::runtime_error("KMMove::CalculateDestination : Parameter Origin has not been set;\n");
    }
}

void KMMove::MakeNamesForOutPut()
{
    if (m_Origin.IsValid()) {
        m_Origin.MakeName();
    }
    if (m_Destination.IsValid()) {
        m_Destination.MakeName();
    }
}

KMBaseData.h

/*
 * KMBaseData.h
 *
 *  Created on: Mar 20, 2016
 *      Author: pacmaninbw
 */

#ifndef KMBASEDATA_H_
#define KMBASEDATA_H_

struct KMBaseData {
    unsigned int m_StartRow;
    unsigned int m_StartColumn;
    std::string m_StartName;
    unsigned int m_TargetRow;
    unsigned int m_TargetColumn;
    std::string m_TargetName;
    unsigned int m_DimensionOneSide;
    KnightMovesMethodLimitations m_LimitationsOnMoves;
};

#endif /* KMBASEDATA_H_ */

KMBoardDimensionConstants.h

/*
 * KMBoardDimensionConstants.h
 *
 *  Created on: Mar 20, 2016
 *      Author: pacmaninbw
 */

#ifndef KMBOARDDIMENSIONCONSTANTS_H_
#define KMBOARDDIMENSIONCONSTANTS_H_

const int MinimumBoardLocationValue = 1;       // While arrays are 0 to N, the minimum board location is A and 1
const unsigned int DefaultBoardDimensionOnOneSide = 8;    // Standard Chess board size
const unsigned int MaximumBoardDimension = 26; // A to Z, common chess notation of a square on the board is [A-H][1-8]

#endif /* KMBOARDDIMENSIONCONSTANTS_H_ */

KMMethodLimitations.h

/*
 * KMMethodLimitations.h
 *
 *  Created on: Mar 20, 2016
 *      Author: pacmaninbw
 */

#ifndef KMKMMETHODlIMITATIONS_H_
#define KMKMMETHODlIMITATIONS_H_

enum KnightMovesMethodLimitations
{
    DenyByPreviousRowOrColumn,
    DenyByPreviousLocation
};

#endif /* KMKMMETHODlIMITATIONS_H_ */

KnightMoves.h

/*
 * KnightMoves.h
 *
 *  Created on: Mar 17, 2016
 *      Author: pacmaninbw
 */

#ifndef KNIGHTMOVES_H_
#define KNIGHTMOVES_H_

#include <string>

#include "KMMethodLimitations.h"
#include "KMBaseData.h"

#endif /* KNIGHTMOVES_H_ */

KnightMoves.cpp

/*
 * KnightMoves.cpp
 *
 *  Created on: Mar 17, 2016
 *      Author: pacmaninbw
 */

#include <iostream>
#include <stdexcept>
#include <chrono>
#include <ctime>
#include <algorithm>
#include <vector>
#include "KnightMoves.h"
#include "KnightMovesImplementation.h"
#include "KMBoardDimensionConstants.h"

double Average(std::vector<double> TestTimes)
{
    double AverageTestTime = 0.0;
    double SumOfTestTimes = 0.0;
    int CountOfTestTimes = 0;

    for (auto TestTimesIter : TestTimes)
    {
        SumOfTestTimes += TestTimesIter;
        CountOfTestTimes++;
    }

    if (CountOfTestTimes) { // Prevent division by zero.
        AverageTestTime = SumOfTestTimes / static_cast<double>(CountOfTestTimes);
    }

    return AverageTestTime;
}

void OutputOverAllStatistics(std::vector<double> TestTimes)
{
    if (TestTimes.size() < 1) {
        std::cout << "No test times to run statistics on!" << std::endl;
        return;
    }

    std::cout << std::endl << "Overall Results" << std::endl;
    std::cout << "The average execution time is " << Average(TestTimes) << " seconds" << std::endl;
    std::nth_element(TestTimes.begin(), TestTimes.begin() + TestTimes.size()/2, TestTimes.end());
    std::cout << "The median execution time is " << TestTimes[TestTimes.size()/2] << " seconds" << std::endl;
    std::nth_element(TestTimes.begin(), TestTimes.begin()+1, TestTimes.end(), std::greater<int>());
    std::cout << "The longest execution time is " << TestTimes[0] << " seconds" << std::endl;
    std::nth_element(TestTimes.begin(), TestTimes.begin()+1, TestTimes.end(), std::less<int>());
    std::cout << "The shortest execution time is " << TestTimes[0] << " seconds" << std::endl;
}

double ExecutionLoop(KMBaseData UserInputData)
{
    KnightMovesImplementation KnightPathFinder(UserInputData);
    std::chrono::time_point<std::chrono::system_clock> start, end;
    start = std::chrono::system_clock::now();
    KMOutputData OutputData = KnightPathFinder.CalculatePaths();
    end = std::chrono::system_clock::now();

    std::chrono::duration<double> elapsed_seconds = end-start;
    std::time_t end_time = std::chrono::system_clock::to_time_t(end);
    double ElapsedTimeForOutPut = elapsed_seconds.count();

    std::cout << "finished computation at " << std::ctime(&end_time)
              << "elapsed time: " << ElapsedTimeForOutPut << std::endl << std::endl << std:: endl;
    // Don't include output of results in elapsed time calculation
    OutputData.DontShowPathData();
    // OutputData.ShowPathData();
    OutputData.ShowResults();

    return ElapsedTimeForOutPut;
}

void InitTestData(std::vector<KMBaseData> &TestData)
{

    TestData.push_back({1,3,"A3",8,4,"H4",DefaultBoardDimensionOnOneSide,DenyByPreviousRowOrColumn});
    TestData.push_back({1,1,"A1",8,8,"H8",DefaultBoardDimensionOnOneSide,DenyByPreviousRowOrColumn});
    TestData.push_back({1,8,"A8",8,1,"H1",DefaultBoardDimensionOnOneSide,DenyByPreviousRowOrColumn});
    TestData.push_back({2,3,"B3",8,4,"H4",DefaultBoardDimensionOnOneSide,DenyByPreviousRowOrColumn});
    TestData.push_back({2,3,"B3",8,8,"H8",DefaultBoardDimensionOnOneSide,DenyByPreviousRowOrColumn});
    TestData.push_back({3,1,"C1",8,4,"H4",DefaultBoardDimensionOnOneSide,DenyByPreviousRowOrColumn});
    TestData.push_back({3,1,"A3",8,8,"H8",DefaultBoardDimensionOnOneSide,DenyByPreviousRowOrColumn});
    TestData.push_back({1,3,"A3",2,5,"B5",DefaultBoardDimensionOnOneSide,DenyByPreviousRowOrColumn});    // Minimum should be one move
    TestData.push_back({1,3,"A3",2,5,"B5",12,DenyByPreviousRowOrColumn});                            // Minimum should be one move
//  TestData.push_back({1,3,"A3",2,5,"B5",MaximumBoardDimension,DenyByPreviousRowOrColumn});        // Minimum should be one move
//  TestData.push_back({1,3,"A3",2,5,"B5",MaximumBoardDimension,DenyByPreviousLocation});            // Minimum should be one move
    TestData.push_back({8,4,"H4",1,3,"A3",DefaultBoardDimensionOnOneSide,DenyByPreviousRowOrColumn});
    TestData.push_back({4,4,"D4",1,8,"A8",DefaultBoardDimensionOnOneSide,DenyByPreviousRowOrColumn});
    TestData.push_back({4,4,"D4",5,6,"E6",DefaultBoardDimensionOnOneSide,DenyByPreviousRowOrColumn});
}

int main(int argc, char *argv[])
{
    int status = 0;

    std::vector<KMBaseData> TestData;
    std::vector<double> TestTimes;

    try {

        InitTestData(TestData);

        for (auto TestDataIter: TestData) {
            TestTimes.push_back(ExecutionLoop(TestDataIter));
        }

        OutputOverAllStatistics(TestTimes);

        return status;
    }
    catch(std::runtime_error &e) {
        std::cerr << "A fatal error occurred in KnightMoves: ";
        std::cerr << e.what()  << std::endl;
        status = 1;
    }
    catch(std::runtime_error *e) {
        std::cerr << "A fatal error occurred in KnightMoves: ";
        std::cerr << e->what()  << std::endl;
        status = 1;
    }
    catch(...) {
        std::cerr << "An unknown fatal error occurred in KnightMoves." << std::endl;
        status = 1;
    }
    return status;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Holy carp... that's a wall of code if I ever saw one \$\endgroup\$ – syb0rg Jun 23 '16 at 18:11
  • \$\begingroup\$ @syb0rg Thanks I think, guess I better start writing some trivial questions. \$\endgroup\$ – pacmaninbw Jun 23 '16 at 19:59
  • 1
    \$\begingroup\$ There's something off with your timings. Your longest after refactoring is 0.00130368 which is less than your average 0.00195405 which doesn't make any sense... \$\endgroup\$ – forsvarir Jul 23 '16 at 19:03
  • \$\begingroup\$ Your timings could be off because you use the system clock, which could have a max resolution of around 1ms, use a high resolution timer instead. \$\endgroup\$ – Surt Aug 24 '16 at 10:09
  • \$\begingroup\$ @forsvarir This bug is fixed in the GitHub version. I can't fix it here because it might invalidate the answer. I changed from multiple uses of nth_element to a single sort. There are a few additional features in the GitHub version. \$\endgroup\$ – pacmaninbw Aug 24 '16 at 11:48
3
\$\begingroup\$
  1. Improving readability

The code suffers from wall-of-text syndrome.

Make a vertical space between the different function groups in the code: constructors/destructor/assigners set/get doers.

Also before each if, while, for and others that starts a new block.

More optimization (speed freak).

You have a lot of const, if they really are const use constexpr instead.

When you then have a fixed sized std::vector use std::array instead.

Using an emplace_back instead of push_back when possible.

You have a lot of std::string copying and creating these takes a lot of time. Instead create a std::array of all the texts and use an index into it instead.

std::string GetName() const { return m_Name; }

gets to be something like

std::string& GetName() const { return NameArray[m_Name]; }

or

int GetName() const { return m_Name; }

depending on the usage.

Your using std::list that is seldom a good choice if you use it in critical loops. Depending on your usage you might be better off with std::array or std::vector.

If you want to check if a row or column has been visited, you could use a bitmask instead. With a maximum of 26 rows/columns a int32_t can be used for each.

(untested code)

bool visited(int row, int col) {
  row = (1<<(row-1); // convert to bit mask.
  col = (1<<(col-1);

  if (row & prevRow || col & prevCol) // bitwise and
    return false; // already visited

  prevRow |= row; // bitwise or
  prevCol |= col;
  return true; // ok visit
}

bool unvisited(int row, int col) {
  row = (1<<(row-1); // convert to bit mask.
  col = (1<<(col-1);

  // sanity check
  if (!(row & prevRow && col & prevCol)) // bitwise and
    return false; // trying to remove wrong col/row

  prevRow &= ~row; // bitwise and, removing the bits by masking
  prevCol &= ~col;
  return true; // remove was ok.
}

2 ints should be a lot easier to handle than the large state your hauling around.

Your timings could be off because you use the system clock, which could have a max resolution of around 1ms. Use a std::chrono::high_resolution_clock instead, read the notes as it might still be the system clock.

\$\endgroup\$
  • \$\begingroup\$ Due to the recursive nature of the program, can you describe how to pop the current location off an implicit visited stack using the bit mask storage of visited. How would you implement an unvisit() function as implemented in KMMoveFilters::PopVisited() ? \$\endgroup\$ – pacmaninbw Aug 23 '16 at 14:22
  • \$\begingroup\$ If you add prevRow and prevCol to your recursive call you get it for free, else you need the unvisit, i'll update with an proto-type unvisite. \$\endgroup\$ – Surt Aug 23 '16 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.