~quf/computers-are-fast-2020

computers-are-fast-2020/src/24.c -rw-r--r-- 2.5 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
#include <stdio.h>
#include <string.h>
#include <errno.h>
#include <stdbool.h>

#define N 301
#define CENTER (N/2)

#define ITERATIONS 100

#define flatten(i, j) ((i) * N + (j))
#define safe_get(g, i, j) ((i < N && j < N)? g[flatten(i, j)] : 0)
#define safe_set(g, v, i, j) do { \
    if (i < N && j < N) { \
      g[flatten(i, j)] = v; \
    } \
  } while (0)

#define min(a, b) ((a < b)? a : b)
#define max(a, b) ((a < b)? b : a)

int main(void) {
  bool isblack[N*N] = { 0, };

  /* part 1: read */
  size_t a = CENTER; // steps east
  size_t b = CENTER; // steps north east
  while (1) {
    int c = getchar();
    if (c == '\n') {
      safe_set(isblack, !safe_get(isblack, a, b), a, b);
      a = CENTER;
      b = CENTER;
    }
    else if (c == EOF) {
      if (ferror(stdin)) {
        fprintf(stderr, "Input error: %s.\n", strerror(errno));
        return 1;
      }
      break;
    }
    if (c == 'e') {
      a += 1;
    }
    else if (c == 'w') {
      a -= 1;
    }
    else if (c == 'n') {
      b += 1;
      if (getchar() == 'w') {
        a -= 1;
      }
    }
    else if (c == 's') {
      b -= 1;
      if (getchar() == 'e') {
        a += 1;
      }
    }
  }

  /* part1: count */
  size_t cmin = N;
  size_t cmax = 0;
  size_t count = 0;
  for (size_t a = 0; a < N; ++a) {
    for (size_t b = 0; b < N; ++b) {
      if (isblack[flatten(a, b)]) {
        count += 1;
        cmin = min(cmin, a);
        cmin = min(cmin, b);
        cmax = max(cmax, a);
        cmax = max(cmax, b);
      }
    }
  }
  printf("%zu\n", count);

  /* make sure we have enough space to expand */
  --cmin;
  ++cmax;
  if (2 * ((cmax - cmin) + ITERATIONS) + 1 >= N) {
    fprintf(stderr, "Grid too small.\n");
    return 1;
  }

  /* part2: update */
  bool next[N*N] = { 0, };
  for (size_t i = 0; i < 100; ++i) {
    --cmin;
    ++cmax;
    for (size_t a = cmin; a < cmax; ++a) {
      for (size_t b = cmin; b < cmax; ++b) {
        int neighbours = \
            isblack[flatten(a+1, b  )] \
          + isblack[flatten(a,   b+1)] \
          + isblack[flatten(a-1, b+1)] \
          + isblack[flatten(a-1, b  )] \
          + isblack[flatten(a,   b-1)] \
          + isblack[flatten(a+1, b-1)];
        bool black = isblack[flatten(a, b)];
        next[flatten(a, b)] = (neighbours == 2) || (black && neighbours == 1);
      }
    }
    for (size_t i = flatten(cmin, cmin); i < flatten(cmax, cmax); ++i) {
      isblack[i] = next[i];
    }
  }

  count = 0;
  for (size_t i = flatten(cmin, cmin); i < flatten(cmax, cmax); ++i) {
    count += isblack[i];
  }
  printf("%zu\n", count);

  return 0;
}