~quf/computers-are-fast-2020

computers-are-fast-2020/src/11.c -rw-r--r-- 3.7 KiB
6f56515eLukas Himbert Draw the rest of the fine owl. 1 year, 7 months ago
                                                                                
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
#include <stdio.h>
#include <string.h>
#include <errno.h>
#include <stdbool.h>

#define MAX_DATASIZE 10000

#define LENGTH(a) (sizeof a / sizeof *a)

/* tile_t was originally an enum, but this is a few ms faster: */
#define tile_t char
#define FLOOR 0
#define EMPTY 1
#define OCC 2

typedef struct {
  tile_t data[MAX_DATASIZE+1]; /* data[MAX_DATASIZE] == FLOOR for neighbour map */
  size_t sx;
  size_t sy;
} grid_t;

#define flatten(g, i, j) (i * g.sy + j)

size_t count_occupied(const grid_t *g) {
  size_t count = 0;
  for (size_t i = 0; i < g->sx * g->sy; ++i) {
    count += g->data[i] == OCC;
  }
  return count;
}

size_t run(const grid_t *g, const size_t *neighbour_map, size_t max_neigh) {
  grid_t copy;
  memcpy(&copy, g, sizeof copy);
  size_t size = g->sx * g->sy;
  bool updated = false;
  unsigned occupied_neighbours[MAX_DATASIZE];
  do {
    for (size_t i = 0; i < size; ++i) {
      occupied_neighbours[i] =
          (copy.data[neighbour_map[i*8+0]] >> 1) /* FLOOR>>1 == 0 */
        + (copy.data[neighbour_map[i*8+1]] >> 1) /* EMPTY>>1 == 0 */
        + (copy.data[neighbour_map[i*8+2]] >> 1) /* OCC>>1 == 1 */
        + (copy.data[neighbour_map[i*8+3]] >> 1)
        + (copy.data[neighbour_map[i*8+4]] >> 1)
        + (copy.data[neighbour_map[i*8+5]] >> 1)
        + (copy.data[neighbour_map[i*8+6]] >> 1)
        + (copy.data[neighbour_map[i*8+7]] >> 1);
    }
    updated = false;
    for (size_t i = 0; i < size; ++i) {
      if (copy.data[i] == EMPTY && occupied_neighbours[i] == 0) {
        copy.data[i] = OCC;
        updated = true;
      }
      else if (copy.data[i] == OCC && occupied_neighbours[i] > max_neigh) {
        copy.data[i] = EMPTY;
        updated = true;
      }
    }
  } while (updated);
  return count_occupied(&copy);
}

int main(void) {
  grid_t grid = { .data = { 0, }, .sx = 0, .sy = 0};
  {
    size_t i = 0;
    size_t ix = 0;
    size_t iy = 0;
    int c;
    while ((c = getc(stdin)) != EOF && i < LENGTH(grid.data)) {
      if (c == '\n') {
        ++iy;
        if (ix > grid.sx) {
          grid.sx = ix;
        }
        ix = 0;
      }
      else {
        grid.data[i++] = (c == 'L');
        ++ix;
      }
    }
    grid.sy = iy;
    if (ferror(stdin)) {
      fprintf(stderr, "Read error: %s\n", strerror(errno));
      return 1;
    }
    else if (grid.sx * grid.sy > LENGTH(grid.data) - 1) {
      fprintf(stderr, "Input too large.\n");
      return 1;
    }
  }

  /* get nearest neighbours for each seat */
  const size_t NEIGH_DX[] = { 1, 1, 0, -1, -1, -1,  0,  1 };
  const size_t NEIGH_DY[] = { 0, 1, 1,  1,  0, -1, -1, -1 };
  size_t neighbour_map_1[MAX_DATASIZE*8] = { 0, };
  size_t neighbour_map_2[MAX_DATASIZE*8] = { 0, };
  for (size_t i = 0; i < grid.sx; ++i) {
    for (size_t j = 0; j < grid.sy; ++j) {
      size_t index = flatten(grid, i, j);
      for (size_t k = 0; k < 8; ++k) {
        size_t i_ = i + NEIGH_DX[k];
        size_t j_ = j + NEIGH_DY[k];
        if (i_ < grid.sx && j_ < grid.sy && grid.data[flatten(grid, i_, j_)] != FLOOR) {
          neighbour_map_1[index*8+k] = flatten(grid, i_, j_);
          neighbour_map_2[index*8+k] = flatten(grid, i_, j_);
        }
        else {
          neighbour_map_1[index*8+k] = MAX_DATASIZE;
          while (i_ < grid.sx && j_ < grid.sy && grid.data[flatten(grid, i_, j_)] == FLOOR) {
            i_ += NEIGH_DX[k];
            j_ += NEIGH_DY[k];
          }
          if (i_ < grid.sx && j_ < grid.sy) {
            neighbour_map_2[index*8+k] = flatten(grid, i_, j_);
          }
          else {
            neighbour_map_2[index*8+k] = MAX_DATASIZE;
          }
        }
      }
    }
  }

  printf("%zu\n", run(&grid, (const size_t*) neighbour_map_1, 3));
  printf("%zu\n", run(&grid, (const size_t*) neighbour_map_2, 4));

  return 0;
}