File indexing completed on 2024-11-03 06:54:50

0001 /*
0002     SPDX-FileCopyrightText: 2004-2005 Andi Peredri <andi@ukr.net>
0003     SPDX-FileCopyrightText: 2007-2008 Fela Winkelmolen <fela.kde@gmail.com>
0004 
0005     SPDX-License-Identifier: GPL-2.0-or-later
0006 */
0007 
0008 #include "abstractgrid.h"
0009 
0010 #include <QMap>
0011 #include <QString>
0012 #include <QDebug>
0013 #include <QRandomGenerator>
0014 
0015 AbstractCell::AbstractCell(int index)
0016     : m_index(index)
0017 {
0018     makeEmpty();
0019 }
0020 
0021 char *AbstractCell::toString() {
0022     char *str = new char[4];
0023     str[0] = (m_cables & Left) ? '-'  : ' ' ;
0024     str[2] = (m_cables & Right) ? '-'  :  ' ' ;
0025     if ((m_cables & Up) && (m_cables & Down)) {
0026         str[1] = '|';
0027     } else if (m_cables & Up) {
0028         str[1] = '\'';
0029     } else if (m_cables & Down) {
0030         str[1] = ',';
0031     } else if ((m_cables & Left) && (m_cables & Right)){
0032         str[1] = '-';
0033     } else {
0034         str[1] = ' ';
0035     }
0036     str[3] = '\0';
0037 
0038     return str;
0039 }
0040 
0041 bool AbstractCell::isTerminal() const
0042 {
0043     if (m_isServer){
0044         return false;
0045     }
0046     return (m_cables == Up || m_cables == Right
0047             || m_cables == Down || m_cables == Left);
0048 }
0049 
0050 // only used to change the cables (not to rotate the cell!)
0051 void AbstractCell::setCables(Directions newCables)
0052 {
0053     m_cables = originalCables = newCables;
0054     m_hasBeenMoved = false;
0055 }
0056 
0057 void AbstractCell::setServer(bool isServer)
0058 {
0059     m_isServer = isServer;
0060 }
0061 
0062 void AbstractCell::setConnected(bool isConnected)
0063 {
0064     m_isConnected = isConnected;
0065 }
0066 
0067 void AbstractCell::makeEmpty()
0068 {
0069     m_cables = originalCables = None;
0070     m_isServer = false;
0071     m_isConnected = false;
0072     m_hasBeenMoved = false;
0073 }
0074 
0075 void AbstractCell::emptyMove()
0076 {
0077     m_hasBeenMoved = true;
0078 }
0079 
0080 void AbstractCell::rotateClockwise()
0081 {
0082     Directions newdirs = None;
0083     if (m_cables & Up) newdirs = Directions(newdirs | Right);
0084     if (m_cables & Right) newdirs = Directions(newdirs | Down);
0085     if (m_cables & Down) newdirs = Directions(newdirs | Left);
0086     if (m_cables & Left) newdirs = Directions(newdirs | Up);
0087     m_cables = newdirs;
0088     m_hasBeenMoved = true;
0089 }
0090 
0091 void AbstractCell::rotateCounterclockwise()
0092 {
0093     Directions newdirs = None;
0094     if (m_cables & Up) newdirs = Directions(newdirs | Left);
0095     if (m_cables & Right) newdirs = Directions(newdirs | Up);
0096     if (m_cables & Down) newdirs = Directions(newdirs | Right);
0097     if (m_cables & Left) newdirs = Directions(newdirs | Down);
0098     m_cables = newdirs;
0099     m_hasBeenMoved = true;
0100 }
0101 
0102 void AbstractCell::invert()
0103 {
0104     rotateClockwise();
0105     rotateClockwise();
0106 }
0107 
0108 void AbstractCell::reset()
0109 {
0110     m_cables = originalCables;
0111     m_hasBeenMoved = false;
0112 }
0113 
0114 
0115 
0116 AbstractGrid::AbstractGrid()
0117     : m_width(0), m_height(0)
0118 {
0119 }
0120 
0121 AbstractGrid::~AbstractGrid()
0122 {
0123     qDeleteAll(m_cells);
0124 }
0125 
0126 void AbstractGrid::initializeGrid(uint width, uint height, Wrapping wrapping)
0127 {
0128     if ((width * height) != (m_width * m_height)) {
0129         qDeleteAll(m_cells);
0130         m_cells.clear();
0131 
0132         for (uint index = 0; index < width*height; ++index) {
0133             m_cells.append(newCell(index));
0134         }
0135     }
0136 
0137     m_width = width;
0138     m_height = height;
0139     m_isWrapped = wrapping;
0140 
0141     createGrid();
0142 
0143     while(hasUnneededCables() || solutionCount() != 1) {
0144         // the grid is invalid: create a new one
0145         createGrid();
0146     }
0147 
0148     m_minimumMoves = 0;
0149     const int shuffleLimit = cellCount() * minCellRatio;
0150     QList<int> notShuffledCells;
0151     for (int i = 0; i < cellCount(); ++i)
0152         notShuffledCells.append(i);
0153 
0154     // select a random cell that is not yet shuffled
0155     // rotate such that initial and final states are not same
0156     // repeat above two steps until minimum moves equal to shuffle limit
0157     auto *generator = QRandomGenerator::global();
0158     while(m_minimumMoves < shuffleLimit)
0159     {
0160         // selecting a random index
0161         int index = generator->bounded(notShuffledCells.count());
0162         int cellNo = notShuffledCells[index];
0163         // removing the selected index so that it must not be used again
0164         notShuffledCells.removeAt(index);
0165         AbstractCell *cell = m_cells[cellNo];
0166         Directions dir = cell->cables();
0167 
0168         // excludes None(Empty cell)
0169         if (dir == None) {
0170             continue;
0171         }
0172         // if straight line rotate once
0173         // cant rotate twice(it will be back on its initial state)
0174         else if ((dir == (Up | Down)) || (dir == (Left | Right))) {
0175             m_minimumMoves += 1;
0176             cell->rotateClockwise();
0177         }
0178         // for every other case rotate 1..3 times
0179         else {
0180             int rotation = generator->bounded(3) + 1; // 1..3
0181             // cant rotate twice when m_minimumMoves == shuffleLimit - 1
0182             if (m_minimumMoves == shuffleLimit - 1 && rotation == 2){
0183                 rotation = (generator->bounded(2))? 1 : 3; // 1 or 3
0184             }
0185             m_minimumMoves += (rotation == 3) ? 1 : rotation;
0186             while(rotation--) {
0187                 cell->rotateClockwise();
0188             }
0189         }
0190     }
0191 
0192     updateConnections();
0193 }
0194 
0195 void AbstractGrid::print() {
0196     //system("clear");
0197     QString str1;
0198     QString str2;
0199     int index = 0;
0200     for (uint r = 0; r < m_height; ++r) {
0201         for (uint c = 0; c < m_width; ++c) {
0202             str1 +=QLatin1String( m_cells[index]->toString() );
0203             str1 += QLatin1String( "  " );
0204             if (m_cells[index]->hasBeenMoved()) {
0205                 str2 += QLatin1String( "M " );
0206             } else {
0207                 str2 += QLatin1String( "  " );
0208             }
0209             ++index;
0210         }
0211         qDebug() << str1 << "     " << str2;
0212         qDebug() << QLatin1String( " " );
0213         str1 = str2 = QLatin1String( "" );
0214     }
0215 }
0216 
0217 // ============ auxiliary funciontions ===================== //
0218 
0219 void AbstractGrid::createGrid()
0220 {
0221     // add a random server
0222     auto *generator = QRandomGenerator::global();
0223     server_index = generator->bounded(cellCount());
0224 
0225     // number of cells that aren't free
0226     int notFreeCells = 0;
0227     const int minimumNumCells = cellCount() * minCellRatio;
0228     // retries until the minimum number of cells is big enough
0229     while (notFreeCells < minimumNumCells) {
0230 
0231         for (int i = 0; i < cellCount(); ++i) {
0232             m_cells[i]->makeEmpty();
0233         }
0234         m_cells[server_index]->setServer(true);
0235 
0236         QList<uint> list;
0237         list.append(server_index);
0238         if (generator->bounded(2)) addRandomCable(list);
0239 
0240         // add some random cables...
0241         // the list empties if there aren't many free cells left
0242         // (because of addRandomCable() not doing anything)
0243         while (!list.isEmpty()) {
0244             if (generator->bounded(2)) {
0245                 addRandomCable(list);
0246                 if (generator->bounded(2)) addRandomCable(list);
0247                 list.erase(list.begin());
0248             }
0249             else {
0250                 list.append(list.first());
0251                 list.erase(list.begin());
0252             }
0253         }
0254 
0255         // count not empty cells
0256         notFreeCells = 0;
0257         for (int i = 0; i < cellCount(); ++i) {
0258             if (m_cells[i]->cables() != None) ++notFreeCells;
0259         }
0260     }
0261 }
0262 
0263 // adds a random direction and moves on (if possible)
0264 void AbstractGrid::addRandomCable(QList<uint>& list)
0265 {
0266     int cell = list.first();
0267     // find all the cells surrounding list.first()
0268     // (0 when cells don't exist)
0269     int ucell = uCell(cell); // up
0270     int rcell = rCell(cell); // right
0271     int dcell = dCell(cell); // down
0272     int lcell = lCell(cell); // left
0273 
0274     QMap<Directions, int> freeCells;
0275 
0276     // of those cells map the ones that are free
0277     if (ucell != NO_CELL && m_cells[ucell]->cables() == None) {
0278         freeCells[Up] = ucell;
0279     }
0280     if (rcell != NO_CELL && m_cells[rcell]->cables() == None) {
0281         freeCells[Right] = rcell;
0282     }
0283     if (dcell != NO_CELL && m_cells[dcell]->cables() == None) {
0284         freeCells[Down] = dcell;
0285     }
0286     if (lcell != NO_CELL && m_cells[lcell]->cables() == None) {
0287         freeCells[Left] = lcell;
0288     }
0289 
0290     if (freeCells.isEmpty()) return; // no free cells left
0291 
0292     QMap<Directions, int>::ConstIterator it = freeCells.constBegin();
0293     // move the iterator to a random direction connecting to a free cell
0294     for (int i = QRandomGenerator::global()->bounded(freeCells.count()); i > 0; --i) ++it;
0295 
0296     // add the cable in the direction of cell
0297     Directions newCables = Directions(m_cells[cell]->cables() | it.key());
0298     m_cells[cell]->setCables(newCables);
0299     // add a cable in the opposite direction, on the free cell
0300     m_cells[it.value()]->setCables(invertDirection(it.key()));
0301     // append the cell that was free to the list
0302     list.append(it.value());
0303 }
0304 
0305 int AbstractGrid::uCell(uint cell) const
0306 {
0307     if (cell >= m_width) {
0308         return cell - m_width;
0309     } else if (m_isWrapped) {
0310         return m_width * (m_height - 1) + cell;
0311     } else {
0312         return NO_CELL;
0313     }
0314 }
0315 
0316 int AbstractGrid::dCell(uint cell) const
0317 {
0318     if (cell < m_width * (m_height - 1)) {
0319         return cell + m_width;
0320     } else if (m_isWrapped) {
0321         return cell - m_width * (m_height - 1);
0322     } else {
0323         return NO_CELL;
0324     }
0325 }
0326 
0327 int AbstractGrid::lCell(uint cell) const
0328 {
0329     if (cell % m_width > 0) {
0330         return cell - 1;
0331     } else if (m_isWrapped) {
0332         return cell - 1 + m_width;
0333     } else {
0334         return NO_CELL;
0335     }
0336 }
0337 
0338 int AbstractGrid::rCell(uint cell) const
0339 {
0340     if (cell % m_width < m_width - 1) {
0341         return cell + 1;
0342     } else if (m_isWrapped) {
0343         return cell + 1 - m_width;
0344     } else {
0345         return NO_CELL;
0346     }
0347 }
0348 
0349 // TODO: something better to invert directions (remove duplication etc...)
0350 Directions AbstractGrid::invertDirection(Directions givenDirection)
0351 {
0352     QMap<Directions, Directions> invDirs;
0353     invDirs[Up]    = Down;
0354     invDirs[Right] = Left;
0355     invDirs[Down]  = Up;
0356     invDirs[Left]  = Right;
0357 
0358     return invDirs[givenDirection];
0359 }
0360 
0361 
0362 int AbstractGrid::solutionCount()
0363 {
0364     MoveList possibleNextMoves;
0365     // TODO: put following in external function
0366     for (AbstractCell *cell : std::as_const(m_cells)) {
0367         if (!cell->hasBeenMoved()) {
0368             Directions dirs = cell->cables();
0369             Move move;
0370             if (dirs == None) {
0371                 // no cables
0372                 move = Move(cell->index(), Move::None);
0373                 possibleNextMoves.append(move);
0374             } else if (dirs == (Up | Down) || dirs == (Left | Right)) {
0375                 // cables forming a line
0376                 move = Move(cell->index(), Move::None);
0377                 possibleNextMoves.append(move);
0378 
0379                 move = Move(cell->index(), Move::Left);
0380                 possibleNextMoves.append(move);
0381             } else {
0382                 // other kind of cables
0383                 move = Move(cell->index(), Move::None);
0384                 possibleNextMoves.append(move);
0385 
0386                 move = Move(cell->index(), Move::Left);
0387                 possibleNextMoves.append(move);
0388 
0389                 move = Move(cell->index(), Move::Right);
0390                 possibleNextMoves.append(move);
0391 
0392                 move = Move(cell->index(), Move::Inverted);
0393                 possibleNextMoves.append(move);
0394             }
0395             break;
0396         }
0397     }
0398 
0399     // all cells have been moved
0400     if (possibleNextMoves.isEmpty()) {
0401         return isPossibleSolution() ? 1 : 0;
0402     }
0403     // else
0404 
0405     int solutionsFound = 0;
0406     for (const Move &nextMove : std::as_const(possibleNextMoves)) {
0407         int index = nextMove.index();
0408 
0409         switch (nextMove.move()) {
0410         case Move::None:
0411             m_cells[index]->emptyMove();
0412             break;
0413         case Move::Right:
0414             m_cells[index]->rotateClockwise();
0415             break;
0416         case Move::Left:
0417             m_cells[index]->rotateCounterclockwise();
0418             break;
0419         case Move::Inverted:
0420             m_cells[index]->invert();
0421             break;
0422         }
0423 
0424         if (movesDoneArePossible()) {
0425             solutionsFound += solutionCount(); // recursive call
0426         }
0427 
0428         m_cells[index]->reset(); // undo move
0429     }
0430     return solutionsFound;
0431 }
0432 
0433 bool AbstractGrid::movesDoneArePossible()
0434 {
0435 
0436     for (AbstractCell *cell : std::as_const(m_cells)) {
0437         if (!cell->hasBeenMoved()) continue;
0438 
0439         uint x = cell->index() % m_width;
0440         uint y = cell->index() / m_width;
0441         Directions cables = cell->cables();
0442 
0443         // check if there are moved cells near the borders that are wrong
0444         if (!m_isWrapped) {
0445             if (x == 0          && cables & Left)  return false;
0446             if (x == m_width-1  && cables & Right) return false;
0447             if (y == 0          && cables & Up)    return false;
0448             if (y == m_height-1 && cables & Down)  return false;
0449         }
0450 
0451         // check if there are contiguous moved cells that are wrong
0452 
0453         if (cables & Left) {
0454             int lcell = lCell(cell->index());
0455             if (lcell != NO_CELL && m_cells[lcell]->hasBeenMoved()) {
0456                 // also the cell to the left of the current has been moved
0457 
0458                 // if it doesn't connect return false
0459                 if (!(m_cells[lcell]->cables() & Right)) return false;
0460             }
0461         }
0462         if (cables & Right) {
0463             int rcell = rCell(cell->index());
0464             if (rcell != NO_CELL && m_cells[rcell]->hasBeenMoved()) {
0465                 if (!(m_cells[rcell]->cables() & Left)) return false;
0466             }
0467         }
0468         if (cables & Up) {
0469             int ucell = uCell(cell->index());
0470             if (ucell != NO_CELL && m_cells[ucell]->hasBeenMoved()) {
0471                 if (!(m_cells[ucell]->cables() & Down)) return false;
0472             }
0473         }
0474         if (cables & Down) {
0475             int dcell = dCell(cell->index());
0476             if (dcell != NO_CELL && m_cells[dcell]->hasBeenMoved()) {
0477                 if (!(m_cells[dcell]->cables() & Up)) return false;
0478             }
0479         }
0480     }
0481 
0482     // nothing was wrong
0483     return true;
0484 }
0485 
0486 bool AbstractGrid::hasUnneededCables()
0487 {
0488     for (AbstractCell *cell : std::as_const(m_cells)) {
0489         if (cell->isTerminal() || cell->isServer() || cell->cables() == None) {
0490             continue;
0491         }
0492 
0493         Directions oldCables = cell->cables();
0494         cell->setCables(None);
0495 
0496         bool solution = isPossibleSolution();
0497         cell->setCables(oldCables);
0498 
0499         if (solution) {
0500             // it has a solution also when the cables of cell are removed
0501             return true;
0502         }
0503     }
0504 
0505     return false;
0506 }
0507 
0508 bool AbstractGrid::isPossibleSolution()
0509 {
0510     for (AbstractCell *cell : std::as_const(m_cells)) {
0511         cell->setConnected(false);
0512     }
0513     updateConnections();
0514 
0515     return allTerminalsConnected();
0516 }
0517 
0518 bool AbstractGrid::allTerminalsConnected() {
0519     // return false if there is a terminal that isn't connected
0520     for (AbstractCell *cell : std::as_const(m_cells)) {
0521         if (cell->isTerminal() && !cell->isConnected()) {
0522             return false;
0523         }
0524     }
0525     // all terminals are connected
0526     return true;
0527 }
0528 
0529 QList<int> AbstractGrid::updateConnections()
0530 {
0531     // TODO: add int AbstractGrid::cellsCount()
0532     QList<bool> newConnections(m_width * m_height);
0533     for (uint i = 0; i < m_width * m_height; ++i) {
0534         newConnections[i] = false;
0535     }
0536 
0537     // indexes of the changed cells
0538     QList<int> changedCells;
0539     changedCells.append(server_index);
0540     newConnections[server_index] = true;
0541 
0542     while (!changedCells.isEmpty())
0543     {
0544         int cell_index = changedCells.first();
0545         int uindex = uCell(cell_index);
0546         int rindex = rCell(cell_index);
0547         int dindex = dCell(cell_index);
0548         int lindex = lCell(cell_index);
0549 
0550         AbstractCell *cell = m_cells[cell_index];
0551         AbstractCell *ucell = (uindex != NO_CELL) ? m_cells[uindex] : nullptr;
0552         AbstractCell *rcell = (rindex != NO_CELL) ? m_cells[rindex] : nullptr;
0553         AbstractCell *dcell = (dindex != NO_CELL) ? m_cells[dindex] : nullptr;
0554         AbstractCell *lcell = (lindex != NO_CELL) ? m_cells[lindex] : nullptr;
0555 
0556         if ((cell->cables() & Up) && ucell != nullptr &&
0557                 (ucell->cables() & Down) && !newConnections[uindex]) {
0558             newConnections[uindex] = true;
0559             changedCells.append(ucell->index());
0560         }
0561         if ((cell->cables() & Right) && rcell != nullptr &&
0562                 (rcell->cables() & Left) && !newConnections[rindex]) {
0563             newConnections[rindex] = true;
0564             changedCells.append(rcell->index());
0565         }
0566         if ((cell->cables() & Down) && dcell != nullptr &&
0567                 (dcell->cables() & Up) && !newConnections[dindex]) {
0568             newConnections[dindex] = true;
0569             changedCells.append(dcell->index());
0570         }
0571         if ((cell->cables() & Left) && lcell != nullptr &&
0572                 (lcell->cables() & Right) && !newConnections[lindex]) {
0573             newConnections[lindex] = true;
0574             changedCells.append(lcell->index());
0575         }
0576         changedCells.erase(changedCells.begin());
0577     }
0578 
0579     // changedCells is empty here
0580     for (uint i = 0; i < m_width * m_height; i++){
0581         AbstractCell *cell = m_cells[i];
0582         if (cell->isConnected() != newConnections[i]) {
0583             changedCells.append(i);
0584             cell->setConnected(newConnections[i]);
0585         }
0586     }
0587 
0588     return changedCells;
0589 }
0590