~quf/computers-are-fast-2020

computers-are-fast-2020/src/19.c -rw-r--r-- 5.6 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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

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

typedef enum {
  NONTERMINAL,
  TERMINAL,
} symbol_type_t;

typedef struct {
  symbol_type_t t;
  union {
    size_t id;
    char terminal;
  } symbol;
} symbol_t;

typedef struct {
  symbol_t symbols[3];
  size_t n_symb;
} sequence_t;

typedef struct {
  sequence_t alternatives[4];
  size_t n_alt;
} alternatives_t;

typedef struct {
  unsigned char s; /* eight bits ought to be enough for anybody */
  size_t len;
} generated_string_t;

typedef struct {
  generated_string_t strings[128];
  size_t n_strings;
} generated_string_set_t;

generated_string_t str_concat(generated_string_t s1, const generated_string_t s2) {
  generated_string_t r;
  r.s = s1.s | (s2.s >> s1.len);
  r.len = s1.len + s2.len;
  return r;
}

void set_union(generated_string_set_t *set1, const generated_string_set_t *set2) {
  for (size_t i = 0; i < set2->n_strings; ++i) {
    generated_string_t s2 = set2->strings[i];
    bool found_it = false;
    for (size_t j = 0; j < set1->n_strings && !found_it; ++j) {
      generated_string_t s1 = set1->strings[j];
      found_it = (s1.len == s2.len && s1.s == s2.s);
    }
    if ((!found_it) && set1->n_strings < LENGTH(set1->strings)) {
      set1->strings[set1->n_strings++] = s2;
    }
  }
}

generated_string_set_t generate(const alternatives_t *rules, size_t id) {
  const alternatives_t *r = rules + id;
  generated_string_set_t ret;
  ret.n_strings = 0;
  if (r->n_alt == 1 && r->alternatives[0].n_symb == 1 && r->alternatives[0].symbols[0].t == TERMINAL) {
    ret.n_strings = 1;
    ret.strings[0].len = 1;
    ret.strings[0].s = (r->alternatives[0].symbols[0].symbol.terminal == 'b') << 7;
  }
  else {
    /* union of generated strings for each alternative */
    for (size_t i = 0; i < r->n_alt; ++i) {
      generated_string_set_t prefixes;
      prefixes.n_strings = 1;
      prefixes.strings[0].len = 0;
      prefixes.strings[0].s = 0;
      for (size_t j = 0; j < r->alternatives[i].n_symb; ++j) {
        /* every combination of generated strings for each symbol in the sequence */
        generated_string_set_t suffixes = generate(rules, r->alternatives[i].symbols[j].symbol.id);
        generated_string_set_t tmp = { .n_strings = 0, };
        for (size_t k = 0; k < prefixes.n_strings; ++k) {
          for (size_t l = 0; l < suffixes.n_strings; ++l) {
            if (tmp.n_strings < LENGTH(tmp.strings)) {
              tmp.strings[tmp.n_strings++] = str_concat(prefixes.strings[k], suffixes.strings[l]);
            }
            else {
              fprintf(stderr, "ERROR: too many strings.\n");
              exit(EXIT_FAILURE);
            }
          }
        }
        prefixes = tmp;
      }
      set_union(&ret, &prefixes);
    }
  }

  return ret;
}

typedef struct {
  unsigned char buf[20];
  size_t len;
} input_string_t;

input_string_t next_message() {
  input_string_t ret;
  memset(&ret, 0, sizeof ret);
  char buf[100] = { 0, };
  if (fgets(buf, sizeof buf, stdin) != NULL) {
    /* convert line to a big endian int */
    char *b = buf;
    size_t i = 0;
    for (; *b && *b != '\n'; ++b, ++i) {
      ret.buf[i >> 3] |= (*b == 'b') << (7 - (i&7));
    }
    ret.len = i >> 3;
  }
  return ret;
}

int main(void) {
  alternatives_t rules[150] = { 0, };
  size_t n_rules = 0;

  char buf[40] = { 0, };
  /* Read rules */
  while (fgets(buf, LENGTH(buf), stdin) != NULL && *buf != '\n') {
    alternatives_t rule;
    memset(&rule, 0, sizeof rule);
    char *b = buf;
    int consumed;
    /* read rule id  */
    size_t id;
    int ret = sscanf(buf, "%zu: %n", &id, &consumed);
    if (ret > 0) {
      b += consumed;
    }
    if (id >= LENGTH(rules)) {
      fprintf(stderr, "Error: rule id #%zu too big.\n", id);
      return EXIT_FAILURE;
    }
    n_rules = (id + 1> n_rules)? (id + 1) : n_rules;
    /* see if we got a terminal */
    char c;
    if (sscanf(b, "\"%c\"\n%n", &c, &consumed) > 0) {
      rule.n_alt = 1;
      rule.alternatives[0].n_symb = 1;
      rule.alternatives[0].symbols[0].t = TERMINAL;
      rule.alternatives[0].symbols[0].symbol.terminal = c;
    }
    else {
      /* parse alternatives (max consecutive nonterminals is 3) */
      for (rule.n_alt = 0; rule.n_alt < LENGTH(rule.alternatives); ++rule.n_alt) {
        sequence_t *s = rule.alternatives + rule.n_alt;
        ret = sscanf(b, "%zu%n %zu%n %zu%n", &s->symbols[0].symbol.id, &consumed, &s->symbols[1].symbol.id, &consumed, &s->symbols[2].symbol.id, &consumed);
        if (ret <= 0) {
          break;
        }
        s->n_symb = ret;
        b += consumed;
        consumed = 0;
        ret = sscanf(b, " | %n", &consumed);
        b += consumed;
      }
      if (*b != '\n') {
        fprintf(stderr, "Error: not end of line: %s.\n", b);
        exit(EXIT_FAILURE);
      }
    }
    rules[id] = rule;
  }

  /* preprocessing: find all strings generated by rule 42. */
  generated_string_set_t set = generate(rules, 42);
  bool generated_by_rule_42[256] = { 0, };
  for (size_t i = 0; i < set.n_strings; ++i) {
    generated_by_rule_42[set.strings[i].s] = true;
  }

  /* read and match inputs */
  size_t match1 = 0;
  size_t match2 = 0;

  while (true) {
    input_string_t s = next_message();
    if (s.len == 0) {
      break;
    }
    size_t m42 = 0;
    size_t m31 = 0;
    size_t i = 0;
    for (; i < s.len &&  generated_by_rule_42[s.buf[i]]; ++i, ++m42);
    for (; i < s.len && !generated_by_rule_42[s.buf[i]]; ++i, ++m31);
    match1 += (i == s.len &&  m42 == 2  &&  m31 == 1);
    match2 += (i == s.len && (m42 >= 2) && (m31 >= 1) && (m31 < m42));
  }

  printf("%zu\n", match1);
  printf("%zu\n", match2);

  return EXIT_SUCCESS;
}