aboutsummaryrefslogtreecommitdiff
path: root/count_fertile_pyramids_land.c
blob: 4a0a4b1306f2537db3aec3591c73f519bedf6bfd (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
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);
}