Edit: meh, durante un edit errato ho cancellato il vecchio messaggio, quindi riscrivo di che si tratta xD
Oggi ho sentito parlare di "percolation" in un video, pur non sapendo spiegare bene di che si tratta (mi sa che devo rivedermi il video :S ) ho provato ad implementare l'algoritmo richiesto, come esercizio giornaliero.
In sostanza evidenzia in blu tutti i quadratini che hanno un collegamento diretto o indiretto alla prima riga, e scopre in maniera efficiente se c'è una strada che collega il una cella dell'ultima riga alla prima.
In maniera efficiente ammesso che non ho fatto boiate implementando una "weighted Union-find"... xD
Cmq, visto che cancello sempre tutto, almeno lascio il codice qui come ricordo :D
Oggi ho sentito parlare di "percolation" in un video, pur non sapendo spiegare bene di che si tratta (mi sa che devo rivedermi il video :S ) ho provato ad implementare l'algoritmo richiesto, come esercizio giornaliero.
In sostanza evidenzia in blu tutti i quadratini che hanno un collegamento diretto o indiretto alla prima riga, e scopre in maniera efficiente se c'è una strada che collega il una cella dell'ultima riga alla prima.
In maniera efficiente ammesso che non ho fatto boiate implementando una "weighted Union-find"... xD
Cmq, visto che cancello sempre tutto, almeno lascio il codice qui come ricordo :D
C++:
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <iomanip>
#include <random>
#include <memory>
#include <chrono>
#include "SDL2\SDL.h"
using namespace std;
default_random_engine engine;
SDL_Window* window{ nullptr };
SDL_Renderer* renderer{ nullptr };
constexpr int winWidth{ 1100 };
constexpr int winHeight{ 840 };
constexpr int cellsN{ 45 };
constexpr int cellsPixelSize{ 17 };
constexpr int padding{ 1 };
struct Cell {
int row{};
int col{};
};
class Union
{
int cellsN;
vector<vector<bool>> state;
vector<int> tree;
vector<int> treeSize;
vector<int> offList;
set<int> startPoints;
map<int, SDL_Color> colors;
Cell getRandomOffSite();
void connect(const Cell& first, const Cell& second);
int& root(int);
public:
Union(int size)
:cellsN{ size },
state(cellsN, vector<bool>(cellsN, false)),
tree(cellsN*cellsN),
treeSize(cellsN*cellsN, 1),
offList(cellsN*cellsN)
{
for (size_t id = 0; id < tree.size(); id++) {
tree[id] = offList[id] = id;
}
}
void drawState();
void openSite();
void degubPrintUnionState();
};
void errorCheck(bool);
int main(int argc, char* argv[])
{
engine.seed(chrono::steady_clock::now().time_since_epoch().count());
errorCheck(!SDL_Init(SDL_INIT_EVERYTHING));
window = SDL_CreateWindow("Percolation Test",
SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED,
winWidth, winHeight,
SDL_WINDOW_SHOWN);
errorCheck(window);
renderer = SDL_CreateRenderer(window, -1, SDL_RENDERER_ACCELERATED | SDL_RENDERER_PRESENTVSYNC);
errorCheck(renderer);
///////////////////////////////////////////////////////////
SDL_Event event;
auto myUnion = make_unique<Union>(cellsN);
while (true)
{
SDL_PollEvent(&event);
switch (event.type)
{
case SDL_KEYDOWN:
{
auto key = event.key.keysym.sym;
if (key == SDLK_ESCAPE) {
myUnion = make_unique<Union>(cellsN);
}
if (key == SDLK_SPACE) {
SDL_Event wait{};
myUnion->degubPrintUnionState();
while (wait.key.keysym.sym != SDLK_SPACE) {
SDL_PollEvent(&wait);
}
}
}
}
//draw
SDL_SetRenderDrawColor(renderer, 0, 0, 0, 255);
SDL_RenderClear(renderer);
myUnion->drawState();
SDL_RenderPresent(renderer);
//update
myUnion->openSite();
}
SDL_DestroyWindow(window);
SDL_DestroyRenderer(renderer);
SDL_Quit();
return 0;
}
///////////////////////////////////////////////////////////
void errorCheck(bool b) {
if (!b) {
cout << SDL_GetError() << endl;
exit(EXIT_FAILURE);
}
}
void Union::drawState()
{
int totalPadding = padding * (cellsN - 1);
int totalGridSize = cellsN * cellsPixelSize;
int offsetX = (winWidth - (totalGridSize + totalPadding)) / 2;
int offsetY = (winHeight - (totalGridSize + totalPadding)) / 2;
SDL_Rect rect{ offsetX ,offsetY, cellsPixelSize,cellsPixelSize };
SDL_Color white{ 255,255,255,255 }, lightBlue{ 30,120,220,255 }, clr{};
for (size_t i = 0; i < tree.size(); i++)
{
int row = i / cellsN;
int col = i % cellsN;
//is openSite?
if (state[row][col])
{
//calculate cell position on screen
int y = row * cellsPixelSize + row * padding;
int x = col * cellsPixelSize + col * padding;
rect.x = offsetX + x;
rect.y = offsetY + y;
//has a way to reach the top line?
int rootOfID = root(tree[i]);
if (startPoints.find(rootOfID) != startPoints.end()) { clr = colors[rootOfID]; }
else { clr = white; }
SDL_SetRenderDrawColor(renderer, clr.r, clr.g, clr.b, clr.a);
SDL_RenderFillRect(renderer, &rect);
}
}
}
Cell Union::getRandomOffSite() {
Cell cell{};
if (!offList.empty())
{
uniform_int_distribution<int> distribution(0, offList.size() - 1);
int randomID = distribution(engine);
int site = offList[randomID];
offList.erase(offList.begin() + randomID);
cell.row = site / cellsN;
cell.col = site % cellsN;
}
return cell;
}
void Union::openSite()
{
Cell cell = getRandomOffSite();
state[cell.row][cell.col] = true;
if (cell.row == 0) {
startPoints.insert(cell.col);
uniform_int_distribution<int> c(20, 220);
colors[cell.col] = SDL_Color{ (Uint8)c(engine), (Uint8)c(engine), (Uint8)c(engine), 255 };
}
connect(cell, Cell{ cell.row - 1, cell.col });//UP
connect(cell, Cell{ cell.row , cell.col + 1 });//RIGHT
connect(cell, Cell{ cell.row + 1, cell.col });//DOWN
connect(cell, Cell{ cell.row , cell.col - 1 });//LEFT
}
void Union::connect(const Cell& first, const Cell& second)
{
//first is expected to be valid
if (second.row >= 0 && second.row < cellsN &&
second.col >= 0 && second.col < cellsN)
{
if (state[second.row][second.col])
{
int firstID = (first.row * cellsN) + first.col;
int secondID = (second.row * cellsN) + second.col;
int& rootA = root(firstID);
int& rootB = root(secondID);
int& rootSmaller = (treeSize[rootA] < treeSize[rootB]) ? rootA : rootB;
int& rootBigger = (treeSize[rootA] < treeSize[rootB]) ? rootB : rootA;
if (rootSmaller != rootBigger)
{
if (startPoints.find(rootSmaller) != startPoints.end())
{
startPoints.erase(rootSmaller);
startPoints.insert(rootBigger);
//if rootBigger has no color, then is not connected to the top. Keep smaller color.
if (colors.find(rootBigger) == colors.end())
{
colors[rootBigger] = colors[rootSmaller];
}
}
rootSmaller = rootBigger;
treeSize[rootBigger]++;
}
}
}
}
int& Union::root(int child)
{
while (tree[child] != child) { child = tree[child]; }
return tree[child];
}
void Union::degubPrintUnionState()
{
map<int, set<int>> groups;
for (int i = 0; i < tree.size(); i++){
groups[tree[i]].insert(i);
}
cout << "\n\n\n\n\n\n\n\n\n" << endl;
int count{};
for (auto& [Key, Set] : groups)
{
count = 0;
std::cout << "child of"<< Key << "{ " << flush;
for (int val : Set)
{
cout << setw(4) << val << " " << flush;
count++;
if (count > 6) {
count = 0; cout << "\\\n " << flush;
}
}
cout << setw(4) << "}" << endl;
}
}
Ultima modifica: