Это продолжение Skyscraper Solver для NxN Size Version 3
Я знаю, что стареет …
Так что у меня все еще есть та же проблема: код не спешит решать головоломки с большими небоскребами.
Со времени последней версии я сделал следующие улучшения:
-Implement Class ClueHint напрямую с полями
- Я удалил ненужный std :: optional в
ClueHint
-Класс Row
теперь использует класс Board
ссылка для доступа к каждому полю на доске
- Реализация полей использует еще битовые маски. Но, как было предложено в ответах на старый код, я перевернул логику. Я также пробовал использовать
std::bitset
дляField
но это было намного медленнее, поэтому я остался с битовой маской.
Я все еще задаюсь вопросом, является ли возврат к самому быстрому решению? Что еще мы можем попытаться ускорить?
Вот код:
#include "codewarsbacktracking.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
namespace codewarsbacktracking {
using BitmaskType = std::uint32_t;
/*
Example size = 4
b0000 0 Impossible
b0001 1 Skyscraper = 1
b0010 2 Skyscraper = 2
b0011 3 Nopes = 3, 4
b0100 4 Skyscraper = 3
b0101 5 Nopes = 2, 4
b0110 6 Nopes = 1, 4
b0111 7 Nopes = 4
b1000 8 Skyscraper = 1
b1001 9 Nopes = 2, 3
b1010 10 Nopes = 1, 3
b1011 11 Nopes = 3
b1100 12 Nopes = 1,2
b1101 13 Nopes = 2
b1110 14 Nopes = 1
b1111 15 Nopes = {}
*/
class Field {
public:
Field() = default;
void insertSkyscraper(int skyscraper);
void insertNope(int nope);
void insertNopes(const std::vector<int> &nopes);
void insertNopes(const Field &field);
int skyscraper(std::size_t size) const;
std::vector<int> nopes(std::size_t size) const;
bool hasSkyscraper() const;
bool containsNope(int value) const;
bool containsNopes(const std::vector<int> &values) const;
private:
bool bitIsToggled(BitmaskType bitmask, int bit) const;
// same as c++20 std::has_single_bit()
bool hasSingleBit(BitmaskType bitmask) const;
BitmaskType mBitmask{static_cast<BitmaskType>(-1)};
friend inline bool operator==(const Field &lhs, const Field &rhs);
friend inline bool operator!=(const Field &lhs, const Field &rhs);
};
inline bool operator==(const Field &lhs, const Field &rhs)
{
return lhs.mBitmask == rhs.mBitmask;
}
inline bool operator!=(const Field &lhs, const Field &rhs)
{
return !(lhs == rhs);
}
void Field::insertSkyscraper(int skyscraper)
{
mBitmask = 1 << (skyscraper - 1);
}
void Field::insertNope(int nope)
{
mBitmask &= ~(1 << (nope - 1));
}
void Field::insertNopes(const std::vector<int> &nopes)
{
for (const auto nope : nopes) {
insertNope(nope);
}
}
void Field::insertNopes(const Field &field)
{
mBitmask &= field.mBitmask;
}
int Field::skyscraper(std::size_t size) const
{
if (!hasSkyscraper()) {
return 0;
}
for (std::size_t i = 0; i < size; ++i) {
if (bitIsToggled(mBitmask, i)) {
return i + 1;
}
}
assert(false);
return 0;
}
std::vector<int> Field::nopes(std::size_t size) const
{
std::vector<int> nopes;
nopes.reserve(size - 1);
for (std::size_t i = 0; i < size; ++i) {
if (!bitIsToggled(mBitmask, i)) {
nopes.emplace_back(i + 1);
}
}
return nopes;
}
bool Field::hasSkyscraper() const
{
return hasSingleBit(mBitmask);
}
bool Field::containsNope(int value) const
{
return !bitIsToggled(mBitmask, value - 1);
}
bool Field::containsNopes(const std::vector<int> &values) const
{
for (const auto &value : values) {
if (!containsNope(value)) {
return false;
}
}
return true;
}
bool Field::bitIsToggled(BitmaskType bitmask, int bit) const
{
return bitmask & (1 << bit);
}
bool Field::hasSingleBit(BitmaskType bitmask) const
{
return bitmask != 0 && (bitmask & (bitmask - 1)) == 0;
}
struct RowClues {
RowClues(std::size_t boardSize);
RowClues() = default;
void reverse();
bool isEmpty() const;
std::vector<Field> fields;
};
RowClues::RowClues(std::size_t boardSize)
: fields{std::vector<Field>(boardSize, Field{})}
{
}
void RowClues::reverse()
{
std::reverse(fields.begin(), fields.end());
}
bool RowClues::isEmpty() const
{
return fields.empty();
}
RowClues getRowClue(int clue, std::size_t boardSize)
{
if (clue == 0) {
return RowClues{};
}
RowClues rowClues{boardSize};
if (clue == static_cast<int>(boardSize)) {
for (std::size_t i = 0; i < boardSize; ++i) {
rowClues.fields[i].insertSkyscraper(i + 1);
}
}
else if (clue == 1) {
rowClues.fields[0].insertSkyscraper(boardSize);
}
else if (clue == 2) {
rowClues.fields[0].insertNope(boardSize);
rowClues.fields[1].insertNope(boardSize - 1);
}
else {
for (std::size_t fieldIdx = 0;
fieldIdx < static_cast<std::size_t>(clue - 1); ++fieldIdx) {
for (std::size_t nopeValue = boardSize;
nopeValue >= (boardSize - (clue - 2) + fieldIdx);
--nopeValue) {
rowClues.fields[fieldIdx].insertNope(nopeValue);
}
}
}
return rowClues;
}
RowClues merge(RowClues frontRowClues, RowClues backRowClues)
{
if (frontRowClues.isEmpty() && backRowClues.isEmpty()) {
return frontRowClues;
}
if (frontRowClues.isEmpty()) {
backRowClues.reverse();
return backRowClues;
}
if (backRowClues.isEmpty()) {
return backRowClues;
}
assert(frontRowClues.fields.size() == backRowClues.fields.size());
backRowClues.reverse();
for (std::size_t i = 0; i < frontRowClues.fields.size(); ++i) {
if (frontRowClues.fields[i].hasSkyscraper()) {
continue;
}
else if (backRowClues.fields[i].hasSkyscraper()) {
frontRowClues.fields[i] = backRowClues.fields[i];
}
else { // only nopes merge nopes
frontRowClues.fields[i].insertNopes(backRowClues.fields[i]);
}
}
return frontRowClues;
}
void mergeClueHintsPerRow(std::vector<RowClues> &rowClues)
{
std::size_t startOffset = rowClues.size() / 4 * 3 - 1;
std::size_t offset = startOffset;
for (std::size_t frontIdx = 0; frontIdx < rowClues.size() / 2;
++frontIdx, offset -= 2) {
if (frontIdx == rowClues.size() / 4) {
offset = startOffset;
}
int backIdx = frontIdx + offset;
rowClues[frontIdx] = merge(rowClues[frontIdx], rowClues[backIdx]);
}
rowClues.erase(rowClues.begin() + rowClues.size() / 2, rowClues.end());
}
std::vector<RowClues> getRowClues(const std::vector<int> &clues,
std::size_t boardSize)
{
std::vector<RowClues> rowClues;
rowClues.reserve(clues.size());
for (const auto &clue : clues) {
rowClues.emplace_back(getRowClue(clue, boardSize));
}
mergeClueHintsPerRow(rowClues);
return rowClues;
}
struct Point {
int x;
int y;
};
inline bool operator==(const Point &lhs, const Point &rhs)
{
return lhs.x == rhs.x && lhs.y == rhs.y;
}
inline bool operator!=(const Point &lhs, const Point &rhs)
{
return !(lhs == rhs);
}
enum class ReadDirection { topToBottom, rightToLeft };
void nextDirection(ReadDirection &readDirection)
{
assert(readDirection != ReadDirection::rightToLeft);
int dir = static_cast<int>(readDirection);
++dir;
readDirection = static_cast<ReadDirection>(dir);
}
void advanceToNextPosition(Point &point, ReadDirection readDirection,
int clueIdx)
{
if (clueIdx == 0) {
return;
}
switch (readDirection) {
case ReadDirection::topToBottom:
++point.x;
break;
case ReadDirection::rightToLeft:
++point.y;
break;
}
}
class BorderIterator {
public:
BorderIterator(std::size_t boardSize);
Point point() const;
ReadDirection readDirection() const;
BorderIterator &operator++();
private:
int mIdx = 0;
std::size_t mBoardSize;
Point mPoint{0, 0};
ReadDirection mReadDirection{ReadDirection::topToBottom};
};
BorderIterator::BorderIterator(std::size_t boardSize) : mBoardSize{boardSize}
{
}
Point BorderIterator::point() const
{
return mPoint;
}
ReadDirection BorderIterator::readDirection() const
{
return mReadDirection;
}
BorderIterator &BorderIterator::operator++()
{
++mIdx;
if (mIdx == static_cast<int>(2 * mBoardSize)) {
return *this;
}
if (mIdx != 0 && mIdx % mBoardSize == 0) {
nextDirection(mReadDirection);
}
advanceToNextPosition(mPoint, mReadDirection, mIdx % mBoardSize);
return *this;
}
class Board;
class Row {
public:
Row(Board &board, const Point &startPoint,
const ReadDirection &readDirection);
void addCrossingRows(Row *crossingRow);
bool hasOnlyOneNopeField() const;
void addLastMissingSkyscraper();
void addNopesToAllNopeFields(int nope);
bool allFieldsContainSkyscraper() const;
int skyscraperCount() const;
int nopeCount(int nope) const;
enum class Direction { front, back };
bool hasSkyscrapers(const std::vector<int> &skyscrapers,
Direction direction) const;
bool hasNopes(const std::vector<std::vector<int>> &nopes,
Direction direction) const;
void addFieldData(const std::vector<Field> &fieldData, Direction direction);
const Field &getFieldRef(std::size_t idx) const;
Field &getFieldRef(std::size_t idx);
private:
template <typename SkyIterator>
bool hasSkyscrapers(SkyIterator skyItBegin, SkyIterator skyItEnd) const;
template <typename NopesIterator>
bool hasNopes(NopesIterator nopesItBegin, NopesIterator nopesItEnd) const;
template <typename FieldDataIterator>
void addFieldData(FieldDataIterator fieldDataItBegin,
FieldDataIterator fieldDataItEnd);
void insertFieldData(std::size_t idx, const Field &fieldData);
void insertSkyscraperNeighbourHandling(std::size_t idx, int skyscraper);
void insertNopesNeighbourHandling(std::size_t idx, int nopes,
bool hadSkyscraperBefore);
bool onlyOneFieldWithoutNope(int nope) const;
bool nopeExistsAsSkyscraperInFields(int nope) const;
std::optional<int> nopeValueInAllButOneField() const;
void insertSkyscraperToFirstFieldWithoutNope(int nope);
bool hasSkyscraper(int skyscraper) const;
// Field &getFieldRef(std::size_t idx);
Board &mBoard;
Point mStartPoint;
ReadDirection mReadDirection;
std::vector<Row *> mCrossingRows;
};
class Board {
public:
Board(std::size_t size);
void insert(const std::vector<RowClues> &rowClues);
void insert(const std::vector<std::vector<int>> &startingSkyscrapers);
bool isSolved() const;
std::vector<Field> fields;
std::vector<Row> mRows;
std::vector<std::vector<int>> skyscrapers2d() const;
std::size_t size() const;
private:
void makeRows();
void connnectRowsWithCrossingRows();
std::size_t mSize;
};
template <typename It> int missingNumberInSequence(It begin, It end)
{
int n = std::distance(begin, end) + 1;
double projectedSum = (n + 1) * (n / 2.0);
int actualSum = std::accumulate(begin, end, 0);
return projectedSum - actualSum;
}
Row::Row(Board &board, const Point &startPoint,
const ReadDirection &readDirection)
: mBoard{board}, mStartPoint{startPoint}, mReadDirection{readDirection}
{
}
void Row::addCrossingRows(Row *crossingRow)
{
assert(crossingRow != nullptr);
assert(mCrossingRows.size() < mBoard.size());
mCrossingRows.push_back(crossingRow);
}
bool Row::hasOnlyOneNopeField() const
{
return skyscraperCount() == static_cast<int>(mBoard.size() - 1);
}
void Row::addLastMissingSkyscraper()
{
assert(hasOnlyOneNopeField());
std::vector<int> sequence;
sequence.reserve(mBoard.size() - 1);
std::size_t nopeFieldIdx = -1;
for (std::size_t idx = 0; idx < mBoard.size(); ++idx) {
if (getFieldRef(idx).hasSkyscraper()) {
sequence.emplace_back((getFieldRef(idx)).skyscraper(mBoard.size()));
}
else {
nopeFieldIdx = idx;
}
}
assert(nopeFieldIdx != -1);
assert(skyscraperCount() == static_cast<int>(sequence.size()));
auto missingValue =
missingNumberInSequence(sequence.begin(), sequence.end());
assert(missingValue >= 0 &&
missingValue <= static_cast<int>(mBoard.size()));
(getFieldRef(nopeFieldIdx)).insertSkyscraper(missingValue);
insertSkyscraperNeighbourHandling(nopeFieldIdx, missingValue);
}
void Row::addNopesToAllNopeFields(int nope)
{
for (std::size_t idx = 0; idx < mBoard.size(); ++idx) {
if (getFieldRef(idx).hasSkyscraper()) {
continue;
}
bool hasSkyscraperBefore = false;
getFieldRef(idx).insertNope(nope);
insertNopesNeighbourHandling(idx, nope, hasSkyscraperBefore);
}
}
bool Row::allFieldsContainSkyscraper() const
{
return skyscraperCount() == static_cast<int>(mBoard.size());
}
int Row::skyscraperCount() const
{
int count = 0;
for (std::size_t i = 0; i < mBoard.size(); ++i) {
if (getFieldRef(i).hasSkyscraper()) {
++count;
}
}
return count;
}
int Row::nopeCount(int nope) const
{
int count = 0;
for (std::size_t i = 0; i < mBoard.size(); ++i) {
if (getFieldRef(i).hasSkyscraper()) {
continue;
}
if (getFieldRef(i).containsNope(nope)) {
++count;
}
}
return count;
}
bool Row::hasSkyscrapers(const std::vector<int> &skyscrapers,
Row::Direction direction) const
{
if (direction == Direction::front) {
return hasSkyscrapers(skyscrapers.cbegin(), skyscrapers.cend());
}
return hasSkyscrapers(skyscrapers.crbegin(), skyscrapers.crend());
}
bool Row::hasNopes(const std::vector<std::vector<int>> &nopes,
Direction direction) const
{
if (direction == Direction::front) {
return hasNopes(nopes.cbegin(), nopes.cend());
}
return hasNopes(nopes.crbegin(), nopes.crend());
}
void Row::addFieldData(const std::vector<Field> &fieldData, Direction direction)
{
if (direction == Direction::front) {
addFieldData(fieldData.begin(), fieldData.end());
}
else {
addFieldData(fieldData.rbegin(), fieldData.rend());
}
}
template <typename SkyIterator>
bool Row::hasSkyscrapers(SkyIterator skyItBegin, SkyIterator skyItEnd) const
{
for (auto skyIt = skyItBegin; skyIt != skyItEnd; ++skyIt) {
auto idx = std::distance(skyItBegin, skyIt);
if (*skyIt == 0 && getFieldRef(idx).hasSkyscraper()) {
continue;
}
if (getFieldRef(idx).skyscraper(mBoard.size()) != *skyIt) {
return false;
}
}
return true;
}
template <typename NopesIterator>
bool Row::hasNopes(NopesIterator nopesItBegin, NopesIterator nopesItEnd) const
{
for (auto nopesIt = nopesItBegin; nopesIt != nopesItEnd; ++nopesIt) {
if (nopesIt->empty()) {
continue;
}
auto idx = std::distance(nopesItBegin, nopesIt);
if (getFieldRef(idx).hasSkyscraper()) {
return false;
}
if (!getFieldRef(idx).containsNopes(*nopesIt)) {
return false;
}
}
return true;
}
template <typename FieldDataIterator>
void Row::addFieldData(FieldDataIterator fieldDataItBegin,
FieldDataIterator fieldDataItEnd)
{
for (auto fieldDataIt = fieldDataItBegin; fieldDataIt != fieldDataItEnd;
++fieldDataIt) {
auto idx = std::distance(fieldDataItBegin, fieldDataIt);
insertFieldData(idx, *fieldDataIt);
}
}
const Field &Row::getFieldRef(std::size_t idx) const
{
assert(idx >= 0 && idx < mBoard.size());
if (mReadDirection == ReadDirection::topToBottom) {
return mBoard
.fields[mStartPoint.x + (mStartPoint.y + idx) * mBoard.size()];
}
return mBoard.fields[mStartPoint.x - idx + (mStartPoint.y) * mBoard.size()];
}
void Row::insertFieldData(std::size_t idx, const Field &fieldData)
{
if (fieldData.hasSkyscraper()) {
if (getFieldRef(idx).hasSkyscraper()) {
return;
}
getFieldRef(idx) = fieldData;
insertSkyscraperNeighbourHandling(
idx, getFieldRef(idx).skyscraper(mBoard.size()));
}
else {
bool hasSkyscraperBefore = getFieldRef(idx).hasSkyscraper();
getFieldRef(idx).insertNopes(fieldData);
auto nopes = fieldData.nopes(mBoard.size());
for (const auto &nope : nopes) {
insertNopesNeighbourHandling(idx, nope, hasSkyscraperBefore);
}
}
}
void Row::insertSkyscraperNeighbourHandling(std::size_t idx, int skyscraper)
{
if (hasOnlyOneNopeField()) {
addLastMissingSkyscraper();
}
addNopesToAllNopeFields(skyscraper);
if (mCrossingRows[idx]->hasOnlyOneNopeField()) {
mCrossingRows[idx]->addLastMissingSkyscraper();
}
mCrossingRows[idx]->addNopesToAllNopeFields(skyscraper);
}
void Row::insertNopesNeighbourHandling(std::size_t idx, int nope,
bool hadSkyscraperBefore)
{
// skyscraper was added so we have to add nopes to the neighbours
if (!hadSkyscraperBefore && getFieldRef(idx).hasSkyscraper()) {
insertSkyscraperNeighbourHandling(
idx, getFieldRef(idx).skyscraper(mBoard.size()));
}
if (onlyOneFieldWithoutNope(nope)) {
insertSkyscraperToFirstFieldWithoutNope(nope);
}
if (mCrossingRows[idx]->onlyOneFieldWithoutNope(nope)) {
mCrossingRows[idx]->insertSkyscraperToFirstFieldWithoutNope(nope);
}
}
bool Row::onlyOneFieldWithoutNope(int nope) const
{
if (nopeExistsAsSkyscraperInFields(nope)) {
return false;
}
if (nopeCount(nope) <
static_cast<int>(mBoard.size()) - skyscraperCount() - 1) {
return false;
}
return true;
}
bool Row::nopeExistsAsSkyscraperInFields(int nope) const
{
for (std::size_t idx = 0; idx < mBoard.size(); ++idx) {
if (getFieldRef(idx).skyscraper(mBoard.size()) == nope) {
return true;
}
}
return false;
}
std::optional<int> Row::nopeValueInAllButOneField() const
{
std::unordered_map<int, int> nopeAndCount;
for (std::size_t i = 0; i < mBoard.size(); ++i) {
if (!getFieldRef(i).hasSkyscraper()) {
auto nopes = getFieldRef(i).nopes(mBoard.size());
for (const auto &nope : nopes) {
if (hasSkyscraper(nope)) {
continue;
}
++nopeAndCount[nope];
}
}
}
for (auto cit = nopeAndCount.cbegin(); cit != nopeAndCount.end(); ++cit) {
if (cit->second ==
static_cast<int>(mBoard.size()) - skyscraperCount() - 1) {
return {cit->first};
}
}
return {};
}
void Row::insertSkyscraperToFirstFieldWithoutNope(int nope)
{
for (std::size_t idx = 0; idx < mBoard.size(); ++idx) {
if ((getFieldRef(idx)).hasSkyscraper()) {
continue;
}
if (!(getFieldRef(idx)).containsNope(nope)) {
(getFieldRef(idx).insertSkyscraper(nope));
insertSkyscraperNeighbourHandling(idx, nope);
return; // there can be max one skyscraper per row;
}
}
}
bool Row::hasSkyscraper(int skyscraper) const
{
for (std::size_t i = 0; i < mBoard.size(); ++i) {
if (getFieldRef(i).skyscraper(mBoard.size()) == skyscraper) {
return true;
}
}
return false;
}
Field &Row::getFieldRef(std::size_t idx)
{
assert(idx >= 0 && idx < mBoard.size());
if (mReadDirection == ReadDirection::topToBottom) {
return mBoard
.fields[mStartPoint.x + (mStartPoint.y + idx) * mBoard.size()];
}
return mBoard.fields[mStartPoint.x - idx + (mStartPoint.y) * mBoard.size()];
}
Board::Board(std::size_t size)
: fields{std::vector<Field>(size * size, Field{})}, mSize{size}
{
makeRows();
}
void Board::insert(const std::vector<RowClues> &rowClues)
{
assert(rowClues.size() == mRows.size());
for (std::size_t i = 0; i < rowClues.size(); ++i) {
if (rowClues[i].isEmpty()) {
continue;
}
mRows[i].addFieldData(rowClues[i].fields, Row::Direction::front);
}
}
void Board::insert(const std::vector<std::vector<int>> &startingSkyscrapers)
{
if (startingSkyscrapers.empty()) {
return;
}
std::size_t boardSize = mRows.size() / 2;
assert(startingSkyscrapers.size() == boardSize);
for (std::size_t i = 0; i < startingSkyscrapers.size(); ++i) {
// ugly glue code probaly better to set skyscrapers directly in the
// fields
std::vector<Field> fields(startingSkyscrapers[i].size());
for (std::size_t fieldIdx = 0; fieldIdx < fields.size(); ++fieldIdx) {
if (startingSkyscrapers[i][fieldIdx] == 0) {
continue;
}
fields[fieldIdx].insertSkyscraper(startingSkyscrapers[i][fieldIdx]);
}
mRows[i + boardSize].addFieldData(fields, Row::Direction::back);
}
}
bool Board::isSolved() const
{
std::size_t endVerticalRows = mRows.size() / 2;
for (std::size_t i = 0; i < endVerticalRows; ++i) {
if (!mRows[i].allFieldsContainSkyscraper()) {
return false;
}
}
return true;
}
std::vector<std::vector<int>> Board::skyscrapers2d() const
{
std::vector<std::vector<int>> skyscrapers2d(mSize, std::vector<int>());
std::size_t j = 0;
skyscrapers2d[j].reserve(mSize);
for (std::size_t i = 0; i < fields.size(); ++i) {
if (i != 0 && i % mSize == 0) {
++j;
skyscrapers2d[j].reserve(mSize);
}
skyscrapers2d[j].emplace_back(fields[i].skyscraper(mSize));
}
return skyscrapers2d;
}
std::size_t Board::size() const
{
return mSize;
}
void Board::makeRows()
{
BorderIterator borderIterator{mSize};
std::size_t rowSize = mSize * 2;
mRows.reserve(rowSize);
for (std::size_t i = 0; i < rowSize; ++i, ++borderIterator) {
mRows.emplace_back(
Row{*this, borderIterator.point(), borderIterator.readDirection()});
}
connnectRowsWithCrossingRows();
}
void Board::connnectRowsWithCrossingRows()
{
std::size_t boardSize = mRows.size() / 2;
std::vector<int> targetRowsIdx(boardSize);
std::iota(targetRowsIdx.begin(), targetRowsIdx.end(), boardSize);
for (std::size_t i = 0; i < mRows.size(); ++i) {
if (i == mRows.size() / 2) {
std::iota(targetRowsIdx.begin(), targetRowsIdx.end(), 0);
std::reverse(targetRowsIdx.begin(), targetRowsIdx.end());
}
for (const auto &targetRowIdx : targetRowsIdx) {
mRows[i].addCrossingRows(&mRows[targetRowIdx]);
}
}
}
void debug_print(Board &board, const std::string &title)
{
std::cout << title << 'n';
for (std::size_t i = 0; i < board.fields.size(); ++i) {
if (i % board.size() == 0 && i != 0) {
std::cout << 'n';
}
auto elementSize = board.size() * 2;
std::string element;
element.reserve(elementSize);
if (board.fields[i].skyscraper(board.size()) != 0) {
element =
"V" + std::to_string(board.fields[i].skyscraper(board.size()));
}
else if (board.fields[i].skyscraper(board.size()) == 0 &&
!board.fields[i].nopes(board.size()).empty()) {
auto nopes_set = board.fields[i].nopes(board.size());
std::vector<int> nopes(nopes_set.begin(), nopes_set.end());
std::sort(nopes.begin(), nopes.end());
for (std::size_t i = 0; i < nopes.size(); ++i) {
element.append(std::to_string(nopes[i]));
if (i != nopes.size() - 1) {
element.push_back(',');
}
}
}
element.resize(elementSize, ' ');
std::cout << element;
}
std::cout << 'n';
}
bool rowsAreValid(const std::vector<Field> &fields, std::size_t index,
std::size_t rowSize)
{
std::size_t row = index / rowSize;
for (std::size_t currIndex = row * rowSize; currIndex < (row + 1) * rowSize;
++currIndex) {
if (currIndex == index) {
continue;
}
if (fields[currIndex].skyscraper(rowSize) ==
fields[index].skyscraper(rowSize)) {
return false;
}
}
return true;
}
bool columnsAreValid(const std::vector<Field> &fields, std::size_t index,
std::size_t rowSize)
{
std::size_t column = index % rowSize;
for (std::size_t i = 0; i < rowSize; ++i) {
std::size_t currIndex = column + i * rowSize;
if (currIndex == index) {
continue;
}
if (fields[currIndex].skyscraper(rowSize) ==
fields[index].skyscraper(rowSize)) {
return false;
}
}
return true;
}
template <typename FieldIterator>
int visibleBuildings(FieldIterator begin, FieldIterator end,
std::size_t rowSize)
{
int visibleBuildingsCount = 0;
int highestSeen = 0;
for (auto it = begin; it != end; ++it) {
if (it->skyscraper(rowSize) != 0 &&
it->skyscraper(rowSize) > highestSeen) {
++visibleBuildingsCount;
highestSeen = it->skyscraper(rowSize);
}
}
return visibleBuildingsCount;
}
std::tuple<int, int> getCluesInRow(const std::vector<int> &clues,
std::size_t row, std::size_t rowSize)
{
int frontClue = clues[clues.size() - 1 - row];
int backClue = clues[rowSize + row];
return {frontClue, backClue};
}
bool cluesInRowAreValid(const std::vector<Field> &fields,
const std::vector<int> &clues, std::size_t index,
std::size_t rowSize)
{
std::size_t row = index / rowSize;
auto [frontClue, backClue] = getCluesInRow(clues, row, rowSize);
if (frontClue == 0 && backClue == 0) {
return true;
}
std::size_t rowIndexBegin = row * rowSize;
std::size_t rowIndexEnd = (row + 1) * rowSize;
auto citBegin = fields.cbegin() + rowIndexBegin;
auto citEnd = fields.cbegin() + rowIndexEnd;
bool rowIsFull = std::find_if(citBegin, citEnd, [](const Field &field) {
return !field.hasSkyscraper();
}) == citEnd;
if (!rowIsFull) {
return true;
}
if (frontClue != 0) {
auto frontVisible = visibleBuildings(citBegin, citEnd, rowSize);
if (frontClue != frontVisible) {
return false;
}
}
auto critBegin = std::make_reverse_iterator(citEnd);
auto critEnd = std::make_reverse_iterator(citBegin);
if (backClue != 0) {
auto backVisible = visibleBuildings(critBegin, critEnd, rowSize);
if (backClue != backVisible) {
return false;
}
}
return true;
}
std::tuple<int, int> getCluesInColumn(const std::vector<int> &clues,
std::size_t column, std::size_t rowSize)
{
int frontClue = clues[column];
int backClue = clues[rowSize * 3 - 1 - column];
return {frontClue, backClue};
}
bool cluesInColumnAreValid(const std::vector<Field> &fields,
const std::vector<int> &clues, std::size_t index,
std::size_t rowSize)
{
std::size_t column = index % rowSize;
auto [frontClue, backClue] = getCluesInColumn(clues, column, rowSize);
if (frontClue == 0 && backClue == 0) {
return true;
}
std::vector<Field> verticalFields;
verticalFields.reserve(rowSize);
for (std::size_t i = 0; i < rowSize; ++i) {
verticalFields.emplace_back(fields[column + i * rowSize]);
}
bool columnIsFull =
std::find_if(verticalFields.cbegin(), verticalFields.cend(),
[](const Field &field) {
return !field.hasSkyscraper();
}) == verticalFields.cend();
if (!columnIsFull) {
return true;
}
if (frontClue != 0) {
auto frontVisible = visibleBuildings(verticalFields.cbegin(),
verticalFields.cend(), rowSize);
if (frontClue != frontVisible) {
return false;
}
}
if (backClue != 0) {
auto backVisible = visibleBuildings(verticalFields.crbegin(),
verticalFields.crend(), rowSize);
if (backClue != backVisible) {
return false;
}
}
return true;
}
bool skyscrapersAreValidPositioned(const std::vector<Field> &fields,
const std::vector<int> &clues,
std::size_t index, std::size_t rowSize)
{
if (!rowsAreValid(fields, index, rowSize)) {
return false;
}
if (!columnsAreValid(fields, index, rowSize)) {
return false;
}
if (!cluesInRowAreValid(fields, clues, index, rowSize)) {
return false;
}
if (!cluesInColumnAreValid(fields, clues, index, rowSize)) {
return false;
}
return true;
}
bool guessSkyscrapers(Board &board, const std::vector<int> &clues,
std::size_t index, std::size_t countOfElements,
std::size_t rowSize)
{
if (index == countOfElements) {
return true;
}
if (board.fields[index].hasSkyscraper()) {
if (!skyscrapersAreValidPositioned(board.fields, clues, index,
rowSize)) {
return false;
}
if (guessSkyscrapers(board, clues, index + 1, countOfElements,
rowSize)) {
return true;
}
return false;
}
auto oldField = board.fields[index];
for (int trySkyscraper = 1; trySkyscraper <= static_cast<int>(rowSize);
++trySkyscraper) {
if (board.fields[index].containsNope(trySkyscraper)) {
continue;
}
board.fields[index].insertSkyscraper(trySkyscraper);
if (!skyscrapersAreValidPositioned(board.fields, clues, index,
rowSize)) {
board.fields[index] = oldField;
continue;
}
if (guessSkyscrapers(board, clues, index + 1, countOfElements,
rowSize)) {
return true;
}
board.fields[index] = oldField;
}
board.fields[index] = oldField;
return false;
}
void solveBoard(Board &board, const std::vector<int> &clues)
{
guessSkyscrapers(board, clues, 0, board.fields.size(), board.size());
}
std::vector<std::vector<int>>
SolvePuzzle(const std::vector<int> &clues,
std::vector<std::vector<int>> startingGrid, int)
{
assert(clues.size() % 4 == 0);
std::size_t boardSize = clues.size() / 4;
auto rowClues = getRowClues(clues, boardSize);
Board board{boardSize};
board.insert(rowClues);
board.insert(startingGrid);
if (board.isSolved()) {
return board.skyscrapers2d();
}
solveBoard(board, clues);
return board.skyscrapers2d();
}
std::vector<std::vector<int>> SolvePuzzle(const std::vector<int> &clues)
{
return SolvePuzzle(clues, std::vector<std::vector<int>>{}, 0);
}
} // namespace codewarsbacktracking
Я также люблю включать несколько модульных тестов. Здесь я перечисляю все модульные тесты, которые в настоящее время работают медленно. Эти доски не очень заполнены стартовыми подсказками. Из-за этого возврат с возвратом должен вставляться много-много раз, чтобы найти решение. Можно ли сделать это быстрее?
#include <gmock/gmock-matchers.h>
#include <gtest/gtest.h>
#include "../Skyscrapers/codewarsbacktracking.h"
#include <vector>
using namespace testing;
struct TestSkyscraperProvider {
std::vector<int> clues;
std::vector<std::vector<int>> result;
};
TestSkyscraperProvider sky6_medium{
{0, 0, 0, 2, 2, 0, 0, 0, 0, 6, 3, 0, 0, 4, 0, 0, 0, 0, 4, 4, 0, 3, 0, 0},
{{{5, 6, 1, 4, 3, 2},
{4, 1, 3, 2, 6, 5},
{2, 3, 6, 1, 5, 4},
{6, 5, 4, 3, 2, 1},
{1, 2, 5, 6, 4, 3},
{3, 4, 2, 5, 1, 6}}}};
TestSkyscraperProvider sky6_hard{
{0, 3, 0, 5, 3, 4, 0, 0, 0, 0, 0, 1, 0, 3, 0, 3, 2, 3, 3, 2, 0, 3, 1, 0},
{{{5, 2, 6, 1, 4, 3},
{6, 4, 3, 2, 5, 1},
{3, 1, 5, 4, 6, 2},
{2, 6, 1, 5, 3, 4},
{4, 3, 2, 6, 1, 5},
{1, 5, 4, 3, 2, 6}}}};
TestSkyscraperProvider sky6_random_2{
{4, 1, 0, 0, 3, 0, 0, 2, 1, 0, 6, 0, 2, 0, 2, 4, 0, 0, 0, 0, 0, 0, 0, 0},
{{{2, 6, 1, 5, 3, 4},
{3, 4, 6, 2, 1, 5},
{4, 2, 3, 1, 5, 6},
{1, 3, 5, 6, 4, 2},
{6, 5, 4, 3, 2, 1},
{5, 1, 2, 4, 6, 3}}}};
TestSkyscraperProvider sky7_medium{{7, 0, 0, 0, 2, 2, 3, 0, 0, 3, 0, 0, 0, 0,
3, 0, 3, 0, 0, 5, 0, 0, 0, 0, 0, 5, 0, 4},
{{{1, 5, 6, 7, 4, 3, 2},
{2, 7, 4, 5, 3, 1, 6},
{3, 4, 5, 6, 7, 2, 1},
{4, 6, 3, 1, 2, 7, 5},
{5, 3, 1, 2, 6, 4, 7},
{6, 2, 7, 3, 1, 5, 4},
{7, 1, 2, 4, 5, 6, 3}}}};
TestSkyscraperProvider sky7_very_hard{{0, 0, 5, 0, 0, 0, 6, 4, 0, 0,
2, 0, 2, 0, 0, 5, 2, 0, 0, 0,
5, 0, 3, 0, 5, 0, 0, 3},
{{{3, 4, 1, 7, 6, 5, 2},
{7, 1, 2, 5, 4, 6, 3},
{6, 3, 5, 2, 1, 7, 4},
{1, 2, 3, 6, 7, 4, 5},
{5, 7, 6, 4, 2, 3, 1},
{4, 5, 7, 1, 3, 2, 6},
{2, 6, 4, 3, 5, 1, 7}}}};
TestSkyscraperProvider sky7_random{{0, 5, 0, 5, 0, 2, 0, 0, 0, 0, 4, 0, 0, 3,
6, 4, 0, 2, 0, 0, 3, 0, 3, 3, 3, 0, 0, 4},
{{{2, 3, 6, 1, 4, 5, 7},
{7, 1, 5, 2, 3, 4, 6},
{6, 4, 2, 3, 1, 7, 5},
{4, 5, 7, 6, 2, 3, 1},
{3, 2, 1, 5, 7, 6, 4},
{1, 6, 4, 7, 5, 2, 3},
{5, 7, 3, 4, 6, 1, 2}}}};
struct TestDataPartialProvider {
std::vector<int> clues;
std::vector<std::vector<int>> result;
std::vector<std::vector<int>> board{};
};
TestDataPartialProvider sky8_hard_partial{{3, 0, 4, 3, 3, 0, 3, 2, 0, 0, 2,
4, 0, 4, 1, 5, 0, 4, 0, 3, 0, 0,
4, 3, 0, 0, 0, 3, 3, 4, 0, 3},
{{1, 6, 2, 4, 3, 8, 5, 7},
{6, 8, 5, 2, 4, 1, 7, 3},
{2, 3, 7, 5, 8, 4, 1, 6},
{3, 1, 6, 8, 7, 5, 2, 4},
{4, 7, 1, 6, 5, 3, 8, 2},
{8, 2, 4, 3, 1, 7, 6, 5},
{7, 5, 3, 1, 2, 6, 4, 8},
{5, 4, 8, 7, 6, 2, 3, 1}},
{{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 5, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 0, 4},
{0, 0, 1, 6, 5, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 3, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 1}}};
TestDataPartialProvider sky11_medium_partial{
{3, 2, 2, 3, 1, 4, 4, 3, 5, 2, 6, 5, 2, 3, 3, 2, 2, 1, 4, 3, 3, 5,
4, 4, 3, 2, 1, 5, 3, 4, 3, 3, 2, 2, 4, 3, 3, 5, 3, 3, 2, 1, 3, 4},
{{6, 8, 10, 5, 11, 3, 7, 9, 4, 2, 1},
{9, 5, 6, 10, 7, 2, 1, 4, 8, 11, 3},
{11, 2, 7, 8, 1, 4, 6, 3, 9, 10, 5},
{3, 11, 2, 4, 5, 6, 9, 7, 10, 1, 8},
{8, 10, 3, 7, 9, 11, 4, 1, 2, 5, 6},
{5, 4, 9, 2, 8, 1, 3, 6, 11, 7, 10},
{2, 7, 1, 9, 4, 10, 8, 5, 3, 6, 11},
{4, 1, 5, 11, 3, 9, 10, 2, 6, 8, 7},
{1, 3, 11, 6, 2, 8, 5, 10, 7, 4, 9},
{7, 6, 8, 3, 10, 5, 2, 11, 1, 9, 4},
{10, 9, 4, 1, 6, 7, 11, 8, 5, 3, 2}},
{{0, 8, 0, 0, 0, 3, 0, 0, 0, 2, 0},
{0, 0, 0, 0, 7, 2, 0, 0, 0, 0, 3},
{0, 0, 7, 0, 0, 0, 6, 0, 0, 10, 0},
{0, 11, 0, 4, 0, 0, 0, 0, 10, 1, 8},
{8, 0, 0, 7, 0, 0, 0, 1, 2, 0, 6},
{0, 4, 0, 0, 8, 1, 0, 0, 0, 7, 0},
{2, 0, 0, 0, 4, 0, 8, 5, 3, 0, 0},
{0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{1, 3, 11, 0, 2, 0, 0, 10, 0, 4, 0},
{0, 0, 0, 3, 10, 5, 0, 11, 0, 0, 0},
{0, 0, 4, 0, 0, 0, 0, 0, 0, 3, 0}}};
TestDataPartialProvider sky11_medium_partial_2{
{1, 2, 2, 5, 3, 2, 5, 3, 5, 4, 3, 4, 2, 3, 1, 2, 3, 2, 4, 3, 4, 4,
3, 4, 3, 2, 3, 5, 3, 1, 2, 3, 3, 3, 3, 2, 3, 5, 2, 5, 3, 4, 2, 1},
{{11, 9, 10, 5, 8, 6, 2, 4, 1, 3, 7},
{9, 1, 3, 8, 7, 11, 6, 5, 2, 4, 10},
{6, 2, 1, 7, 3, 9, 8, 11, 5, 10, 4},
{7, 6, 4, 2, 10, 8, 1, 3, 9, 5, 11},
{2, 7, 6, 9, 4, 10, 3, 8, 11, 1, 5},
{4, 11, 2, 6, 9, 5, 10, 1, 3, 7, 8},
{1, 4, 7, 10, 2, 3, 5, 6, 8, 11, 9},
{3, 8, 5, 4, 11, 7, 9, 2, 10, 6, 1},
{10, 5, 8, 1, 6, 2, 11, 7, 4, 9, 3},
{5, 10, 11, 3, 1, 4, 7, 9, 6, 8, 2},
{8, 3, 9, 11, 5, 1, 4, 10, 7, 2, 6}},
{{0, 0, 10, 0, 8, 0, 2, 0, 1, 0, 0},
{0, 0, 0, 0, 7, 11, 0, 5, 0, 0, 0},
{0, 0, 0, 0, 0, 9, 0, 0, 0, 0, 4},
{0, 0, 0, 0, 0, 0, 1, 3, 9, 0, 0},
{0, 0, 6, 0, 4, 0, 3, 0, 11, 1, 0},
{0, 0, 0, 6, 9, 0, 0, 1, 3, 0, 8},
{0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 9},
{0, 0, 0, 4, 11, 0, 0, 0, 0, 0, 1},
{10, 0, 8, 1, 0, 2, 11, 7, 4, 0, 0},
{5, 10, 0, 0, 0, 0, 0, 0, 0, 8, 0},
{0, 0, 9, 0, 5, 0, 0, 0, 7, 0, 6}}};
TEST(CodewarsBacktracking, sky6_medium)
{
EXPECT_EQ(codewarsbacktracking::SolvePuzzle(sky6_medium.clues),
sky6_medium.result);
}
TEST(CodewarsBacktracking, sky6_hard)
{
EXPECT_EQ(codewarsbacktracking::SolvePuzzle(sky6_hard.clues),
sky6_hard.result);
}
TEST(CodewarsBacktracking, sky6_random_2)
{
EXPECT_EQ(codewarsbacktracking::SolvePuzzle(sky6_random_2.clues),
sky6_random_2.result);
}
TEST(CodewarsBacktracking, sky7_medium)
{
EXPECT_EQ(codewarsbacktracking::SolvePuzzle(sky7_medium.clues),
sky7_medium.result);
}
TEST(CodewarsBacktracking, sky7_very_hard)
{
EXPECT_EQ(codewarsbacktracking::SolvePuzzle(sky7_very_hard.clues),
sky7_very_hard.result);
}
TEST(CodewarsBacktracking, sky7_random)
{
EXPECT_EQ(codewarsbacktracking::SolvePuzzle(sky7_random.clues),
sky7_random.result);
}
TEST(CodewarsBacktracking, sky8_hard_partial)
{
EXPECT_EQ(codewarsbacktracking::SolvePuzzle(sky8_hard_partial.clues,
sky8_hard_partial.board,
sky8_hard_partial.board.size()),
sky8_hard_partial.result);
}
TEST(CodewarsBacktracking, sky11_medium_partial)
{
EXPECT_EQ(codewarsbacktracking::SolvePuzzle(
sky11_medium_partial.clues, sky11_medium_partial.board,
sky11_medium_partial.board.size()),
sky11_medium_partial.result);
}
TEST(CodewarsBacktracking, sky11_medium_partial_2)
{
EXPECT_EQ(codewarsbacktracking::SolvePuzzle(
sky11_medium_partial_2.clues, sky11_medium_partial_2.board,
sky11_medium_partial_2.board.size()),
sky11_medium_partial_2.result);
}
int main(int argc, char *argv[])
{
::testing::InitGoogleTest(&argc, argv);
return RUN_ALL_TESTS();
}