algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

commit f58ad5212448b6566bce00c2a2f68df508271bb1
parent e499c2fe4d6700eae6adeb8fd2e21fa4f2f9addd
Author: Andrew Laack <andrew@laack.co>
Date:   Wed, 28 Oct 2026 12:02:54 -0500

Better robot factory, and lc problem

Diffstat:
Mcomp/robot-factory/main.cpp | 31++++++++++++++++---------------
Ccomp/robot-factory/main.cpp -> comp/robot-factory/old.cpp | 0
Aleetcode/number-of-closed-islands/number-of-closed-islands.cpp | 56++++++++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 72 insertions(+), 15 deletions(-)

diff --git a/comp/robot-factory/main.cpp b/comp/robot-factory/main.cpp @@ -1,3 +1,5 @@ +// relative to the other, this uses a 1d vector with a defined size to improve cache locality and decrease runtime allocations + #include <vector> #include <algorithm> #include <iostream> @@ -10,31 +12,33 @@ // - go up,left,right,down if there's not a wall on that side // - we don't have to check bounds because walls are on edges. -int searchFrom(std::vector<std::vector<int>>& grid, std::vector<bool>& visited, int y, int x) { - int currentIdx = (y * grid[0].size()) + x; +int searchFrom(std::vector<int>& grid, int& rows, int& cols, std::vector<bool>& visited, int y, int x) { + int currentIdx = (y * cols) + x; + if(visited[currentIdx]) { return 0; } + visited[currentIdx] = true; int res = 1; - int current = grid[y][x]; + int current = grid[currentIdx]; // North, East, South, West if((current & 0b1000) == 0) { - res += searchFrom(grid,visited, y-1, x); + res += searchFrom(grid, rows, cols, visited, y-1, x); } if((current & 0b0100) == 0) { - res += searchFrom(grid,visited, y, x+1); + res += searchFrom(grid, rows, cols,visited, y, x+1); } if((current & 0b0010) == 0) { - res += searchFrom(grid,visited, y+1, x); + res += searchFrom(grid,rows, cols, visited, y+1, x); } if((current & 0b0001) == 0) { - res += searchFrom(grid,visited, y, x-1); + res += searchFrom(grid,rows, cols, visited, y, x-1); } return res; } @@ -44,30 +48,27 @@ int main() { std::cin >> rows; std::cin >> cols; - std::vector<std::vector<int>> grid {}; + std::vector<int> grid (rows*cols); for(int y = 0; y < rows; ++y) { - std::vector<int> cLs {}; for(int x = 0; x < cols; ++x) { std::cin >> current; - cLs.push_back(current); + grid[y*cols + x] = current; } - grid.push_back(cLs); } - std::vector<bool> visited (grid[0].size() * grid.size(), false); + std::vector<bool> visited (grid.size(), false); std::vector<int> result {}; for(int y = 0; y < rows; ++y) { for(int x = 0; x < cols; ++x) { - int res = searchFrom(grid,visited,y,x); + int res = searchFrom(grid,rows,cols,visited,y,x); if(res != 0) { result.push_back(res); } } } - std::sort(result.begin(), result.end()); - std::reverse(result.begin(), result.end()); + std::sort(result.rbegin(), result.rend()); for(int i = 0; i < result.size(); ++i) { std::cout << result[i] << " "; diff --git a/comp/robot-factory/main.cpp b/comp/robot-factory/old.cpp diff --git a/leetcode/number-of-closed-islands/number-of-closed-islands.cpp b/leetcode/number-of-closed-islands/number-of-closed-islands.cpp @@ -0,0 +1,56 @@ +int dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited,int y, int x) { + + if(!(y >= 0 && y < visited.size() && x < visited[0].size() && x >= 0)) { + return -1; // out of bounds, means borders edge + } + + if(visited[y][x] || grid[y][x] == 1) { + return 0; + } + + visited[y][x] = true; + + int res = 0; + + res = min(res,dfs(grid,visited,y-1,x)); + res = min(res,dfs(grid,visited,y,x-1)); + res = min(res,dfs(grid,visited,y+1,x)); + res = min(res,dfs(grid,visited,y,x+1)); + + if(res == 0) { + return 1; + } + + return res; +} + +class Solution { +public: + int closedIsland(vector<vector<int>>& grid) { + // for each position: + // perform dfs for the island + // if the island borders an edge, don't count it + // return count of islands + + vector<vector<bool>> visited {}; + + for(int i = 0; i < grid.size(); ++i) { + visited.emplace_back(vector<bool> (grid[i].size(), false)); + } + + int res = 0; + + for(int y = 0; y < grid.size(); ++y) { + for(int x = 0; x < grid[y].size(); ++x) { + if(grid[y][x] == 0 && !visited[y][x]) { + int re = dfs(grid, visited, y, x); + if(re == 1) { + res += 1; + } + } + } + } + + return res; + } +};