Решатель небоскребов для размера NxN, версия 4

От: Из: Общие

Это продолжение 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();
}

0

Похожие записи:

  1. Программа расчета небоскребов для размера NxN, версия 3 (с использованием битовых масок)
  2. Программа расчета небоскребов для размера NxN, версия 2 (с использованием функции отслеживания с возвратом)
  3. Функция batch_recursive_count_if с уровнем распаковки для произвольной вложенной итерируемой реализации произвольного типа в C ++
  4. Код крестики-нолики с использованием c #
  5. Игра Connect Four, созданная на основе игры Tic Tac Toe [closed]

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *