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;
}
