Ad
Gnomorianvs.Talanger

C++ : Iterating over an infinate number of vectors at the same time till end of shortest one

this uses c++17 fold expressions to iterate over all the given arrays at the same time.

Code
Diff
  • #include <vector>
#include <iostream>
#include <algorithm>

constexpr auto iterateVectors = [](auto...vectors)
{
    constexpr auto getSmallestVector = [](auto...vectors)
    {
        size_t end{ reinterpret_cast<size_t>(std::numeric_limits<size_t>::max) };
        ((end = std::min(vectors.size(), end)), ...);
        return end;
    };
    constexpr auto writeRow = [](size_t position, auto...vectors) -> void
    {
        const auto rowLength{ sizeof...(vectors) };
        size_t i{ 0 };
        ((std::cerr << vectors[position] << (++i < rowLength ? ':' : '\n')), ...);
    };

    const size_t iterateFor{ getSmallestVector(vectors...) };
    for (size_t i{ 0 }; i < iterateFor; i++)
        writeRow(i, vectors...);
};
    • #include <vector>
    • #include <utility>
    • #include <iostream>
    • template <class T, class U>
    • void iterateTwoVectors(std::vector<T> A, std::vector<U> B)
    • #include <algorithm>
    • constexpr auto iterateVectors = [](auto...vectors)
    • {
    • constexpr auto getSmallestVector = [](auto...vectors)
    • {
    • size_t end{ reinterpret_cast<size_t>(std::numeric_limits<size_t>::max) };
    • ((end = std::min(vectors.size(), end)), ...);
    • return end;
    • };
    • constexpr auto writeRow = [](size_t position, auto...vectors) -> void
    • {
    • const auto rowLength{ sizeof...(vectors) };
    • size_t i{ 0 };
    • ((std::cerr << vectors[position] << (++i < rowLength ? ':' : '\n')), ...);
    • };
    • for (auto [a,b] = std::pair{A.begin(), B.begin()}; a != A.end() && b != B.end(); a++, b++)
    • {
    • std::cout << *a << ":" << *b << "\n";
    • }
    • }
    • const size_t iterateFor{ getSmallestVector(vectors...) };
    • for (size_t i{ 0 }; i < iterateFor; i++)
    • writeRow(i, vectors...);
    • };
Gnomorianvs.or_shazam

Knight's tour problem for n x n board

given a board of NxN, if it's possible for a chess knight starting at position [0,0] to reach all the squares once only, the function should return true , otherwise the function should return false

In this implementation, there is an interface ChessPiece which we can implement to add the rules for all the chess pieces.

we recursivly check valid moves using a unique set to store the Squares we have already visited to prevent infinite recursion.

Code
Diff
  • class Knight : public ChessPiece
{
	std::vector<Square> possibleDirections{
			{2, 1},
			{2, -1},
			{-2, 1},
			{-2, -1},
			{1, 2},
			{-1, 2},
			{1, -2},
			{-1, -2},
	};
public:
	Knight(int boardSize) : ChessPiece(boardSize)
	{
	}
  virtual ~Knight() = default;

	bool positionInBounds(const Square& position)
	{
		return position.first > -1 && position.first < boardSize()
			&& position.second > -1 && position.second < boardSize();
	}

	// Inherited via ChessPiece
	virtual std::vector<Square> validMovesFromPosition(const Square& position) override
	{
		std::vector<Square> validDirections;
		for (auto direction : possibleDirections)
		{
			const Square possibleNewPos{position + direction};
			if (positionInBounds(possibleNewPos))
				validDirections.emplace_back(possibleNewPos);
		}

		return validDirections;
	}
};

void traverseBoard(const std::unique_ptr<ChessPiece>& piece, const Square& currentPosition, std::set<Square>& visitedSquares)
{
	const auto validPositions{piece->validMovesFromPosition(currentPosition)};
	if (validPositions.size() == 0)
		return;

	std::vector<Square> unattemptedMoves;
	for (auto possibleMove : validPositions)
	{
		const auto result{visitedSquares.insert(possibleMove)};
		if (result.second)
			unattemptedMoves.emplace_back(possibleMove);
	}

	for (auto unattemptedMove : unattemptedMoves)
		traverseBoard(piece, unattemptedMove, visitedSquares);
}

template<class C>
bool attemptBoard(int width, Square startingPosition)
{
	if (width < 1)
		return false;
	if (width == 1)
		return true;

	const std::unique_ptr<ChessPiece> piece{std::make_unique<C>(width)};

	std::set<std::pair<int, int>> visitedSquares;
	traverseBoard(piece, startingPosition, visitedSquares);

	return visitedSquares.size() == static_cast<std::set<Square>::size_type>(width * width);
}

bool KnightTour(int n)
{
	return attemptBoard<Knight>(n, {0, 0});
}
    • bool KnightTour(int n){
    • class Knight : public ChessPiece
    • {
    • std::vector<Square> possibleDirections{
    • {2, 1},
    • {2, -1},
    • {-2, 1},
    • {-2, -1},
    • {1, 2},
    • {-1, 2},
    • {1, -2},
    • {-1, -2},
    • };
    • public:
    • Knight(int boardSize) : ChessPiece(boardSize)
    • {
    • }
    • virtual ~Knight() = default;
    • bool positionInBounds(const Square& position)
    • {
    • return position.first > -1 && position.first < boardSize()
    • && position.second > -1 && position.second < boardSize();
    • }
    • // Inherited via ChessPiece
    • virtual std::vector<Square> validMovesFromPosition(const Square& position) override
    • {
    • std::vector<Square> validDirections;
    • for (auto direction : possibleDirections)
    • {
    • const Square possibleNewPos{position + direction};
    • if (positionInBounds(possibleNewPos))
    • validDirections.emplace_back(possibleNewPos);
    • }
    • return validDirections;
    • }
    • };
    • void traverseBoard(const std::unique_ptr<ChessPiece>& piece, const Square& currentPosition, std::set<Square>& visitedSquares)
    • {
    • const auto validPositions{piece->validMovesFromPosition(currentPosition)};
    • if (validPositions.size() == 0)
    • return;
    • std::vector<Square> unattemptedMoves;
    • for (auto possibleMove : validPositions)
    • {
    • const auto result{visitedSquares.insert(possibleMove)};
    • if (result.second)
    • unattemptedMoves.emplace_back(possibleMove);
    • }
    • for (auto unattemptedMove : unattemptedMoves)
    • traverseBoard(piece, unattemptedMove, visitedSquares);
    • }
    • template<class C>
    • bool attemptBoard(int width, Square startingPosition)
    • {
    • if (width < 1)
    • return false;
    • if (width == 1)
    • return true;
    • const std::unique_ptr<ChessPiece> piece{std::make_unique<C>(width)};
    • std::set<std::pair<int, int>> visitedSquares;
    • traverseBoard(piece, startingPosition, visitedSquares);
    • return visitedSquares.size() == static_cast<std::set<Square>::size_type>(width * width);
    • }
    • bool KnightTour(int n)
    • {
    • return attemptBoard<Knight>(n, {0, 0});
    • }