diff options
author | Jack Sangdahl <[email protected]> | 2024-11-12 18:03:25 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-11-12 18:03:25 -0700 |
commit | 727982d9551b2d1c8238cf40e3fdfeb32c0355ad (patch) | |
tree | f57627ea2b9d626de23aa9ff3a5a08e3afc70c71 /count_fertile_pyramids_land.c | |
parent | c1fa3ef5d1586d1569f59c88c884029ab9bc9a29 (diff) | |
download | leetcode-727982d9551b2d1c8238cf40e3fdfeb32c0355ad.tar.gz leetcode-727982d9551b2d1c8238cf40e3fdfeb32c0355ad.zip |
2088. count fertile pyramids in a land
Diffstat (limited to 'count_fertile_pyramids_land.c')
-rw-r--r-- | count_fertile_pyramids_land.c | 142 |
1 files changed, 142 insertions, 0 deletions
diff --git a/count_fertile_pyramids_land.c b/count_fertile_pyramids_land.c new file mode 100644 index 0000000..4a0a4b1 --- /dev/null +++ b/count_fertile_pyramids_land.c @@ -0,0 +1,142 @@ +// 2088. Count Fertile Pyramids in a Land +#include "leetcode.h" + +#pragma GCC optimize("03") +#pragma GCC target("avx2") + +/* + * a farmer has a rectangular grid of land with 'm' rows and 'n' columns that + * can be divided into unit cells. each cell is either fertile (represented by a + * 1) or barren (represented by a 0). all cells outside the grid are considered + * barren. a pyamidal plot of land can be defined as a set of cells with the + * following criteria: the number of cells in the set has to be greater than 1 + * and all cells must be fertile, and the apex of the pyramid is the topmost + * cell of the pyramid. the height of a pyramid is the number of rows it covers. + * let '(r, c)' be the apex of the pyramid and its height be 'h'. given a + * 0-indexed 'm x n' binary matrix 'grid' representing the farmland, return the + * total number of pyramidal and inverse pyramidal plots that can be found in + * 'grid'. + */ + +uint32_t rows = 0, cols = 0; + +typedef struct __attribute__((packed, aligned(32))) { + uint64_t data[16 * 1024]; +} bit_plane; + +static inline void bit_plane_and(bit_plane *dest, const bit_plane *restrict s1, + const bit_plane *restrict s2) { + for (uint32_t r = 0; r < rows; r++) + for (uint32_t c = 0; c < cols; c += 4) { + uint32_t idx = r * 16 + c; + dest->data[idx] = s1->data[idx] & s2->data[idx]; + dest->data[idx + 1] = s1->data[idx + 1] & s2->data[idx + 1]; + dest->data[idx + 2] = s1->data[idx + 2] & s2->data[idx + 2]; + dest->data[idx + 3] = s1->data[idx + 3] & s2->data[idx + 3]; + } +} + +static inline void bit_plane_shift_r(bit_plane *dest, + const bit_plane *restrict s1, + uint32_t steps) { + for (uint32_t r = 0; r < rows; r++) + for (uint32_t c = 0; c < rows; c++) { + uint32_t idx = r * 16 + c; + dest->data[idx] = + (s1->data[idx] >> steps) | (s1->data[idx + 1] << (64 - steps)); + } +} + +static inline void bit_plane_shift_l(bit_plane *dest, + const bit_plane *restrict s1, + uint32_t steps) { + dest->data[0] = s1->data[0] << steps; + for (uint32_t c = 1; c < cols; c++) + dest->data[c] = (s1->data[c] << steps) | (s1->data[c - 1] >> (64 - steps)); + for (uint32_t r = 1; r < rows; r++) + for (uint32_t c = 0; c < cols; c++) { + uint32_t idx = r * 16 + c; + dest->data[idx] = + (s1->data[idx] << steps) | (s1->data[idx - 1] >> (64 - steps)); + } +} + +static inline void bit_plane_shift_u(bit_plane *restrict dest, + const bit_plane *restrict src, + uint32_t steps) { + __builtin_memcpy(dest->data, src->data + steps * 16, + 16 * (rows - steps) * sizeof(uint64_t)); + __builtin_memset(dest->data + (rows - steps) * 16, 0, steps * 16); +} + +static inline void bit_plane_shift_d(bit_plane *restrict dest, + const bit_plane *restrict src, + uint32_t steps) { + __builtin_memset(dest->data, 0, steps * 16); + __builtin_memcpy(dest->data + steps * 16, src->data, + 16 * (rows - steps) * sizeof(uint64_t)); +} + +static inline uint32_t bit_plane_popcount(const bit_plane *self) { + uint32_t sum = 0; + for (uint32_t r = 0; r < rows; r++) + for (uint32_t c = 0; c <= ((cols - 1) >> 6); c++) + sum += __builtin_popcountll(self->data[r * 16 + c]); + return sum; +} + +void bit_plane_print(const bit_plane *b) { + for (uint32_t r = 0; r < rows; r++) { + for (uint32_t c = (cols - 1) >> 6; ~c; c--) + printf("%064lb", b->data[r * 16 + c]); + printf("\n"); + } +} + +int countPyramids(int **grid, int gridSize, int *gridColSize) { + cols = *gridColSize; + rows = gridSize; + bit_plane org[1] = {0}; + for (uint32_t r = 0; r < rows; r++) + for (uint32_t c = 0; c < cols; c++) + org->data[r * 16U + (c >> 6U)] = (uint64_t)grid[r][c] << (c & 0x3F); + bit_plane curr[1] = {org[0]}, shr[1] = {0}, shu[1] = {0}, shd[1] = {0}, + shl[1] = {0}, tmpl[1] = {0}, tmpr[1] = {0}, mid[1] = {0}; + uint32_t cnt = 0, sqr = -1; + for (uint32_t i = 1; sqr && i < fmin(rows, cols); i++) { + bit_plane_shift_l(shl, curr, 1); + bit_plane_shift_r(shr, curr, 1); + bit_plane_and(tmpl, curr, shl); + bit_plane_and(tmpr, curr, shr); + bit_plane_and(mid, tmpl, tmpr); + bit_plane_shift_u(shu, mid, 1); + bit_plane_and(curr, shu, curr); + cnt += sqr = bit_plane_popcount(curr); + } + sqr = -1; + for (uint32_t i = 1; sqr && i < fmin(rows, cols); i++) { + bit_plane_shift_l(shl, org, 1); + bit_plane_shift_r(shr, org, 1); + bit_plane_and(tmpl, org, shl); + bit_plane_and(tmpr, org, shr); + bit_plane_and(mid, tmpl, tmpr); + bit_plane_shift_d(shd, mid, 1); + bit_plane_and(org, shd, org); + cnt += sqr = bit_plane_popcount(org); + } + return (int)cnt; +} + +int main() { + int g1i[2][4] = {{0, 1, 1, 0}, {1, 1, 1, 1}}, + g2i[3][3] = {{1, 1, 1}, {1, 1, 1}}, + g3i[3][5] = {{1, 1, 1, 1, 0}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}}; + struct two_d_arr g1, g2, g3; + two_d_arr_init(&g1, 2, 4, g1i); + two_d_arr_init(&g2, 3, 3, g2i); + two_d_arr_init(&g3, 3, 5, g3i); + printf("%d\n", countPyramids(g1.arr, g1.row_size, g1.col_size)); // expect: 2 + printf("%d\n", countPyramids(g2.arr, g2.row_size, g2.col_size)); // expect: 2 + printf("%d\n", countPyramids(g3.arr, g3.row_size, g3.col_size)); // expect: 13 + two_d_arr_free(&g1), two_d_arr_free(&g2), two_d_arr_free(&g3); +} |