~quf/computers-are-fast-2020

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

typedef struct {
  bool departure;
  unsigned min1;
  unsigned max1;
  unsigned min2;
  unsigned max2;
  bool may_fit_field[25];
} rule_t;

bool is_between(unsigned min, unsigned i, unsigned max) {
  return (min <= i) && (i <= max);
}

bool rule_applies_to_field(rule_t *r, unsigned field) {
  return is_between(r->min1, field, r->max1) || is_between(r->min2, field, r->max2);
}

bool any_rule_applies(rule_t *r, size_t n, unsigned f) {
  for (size_t i = 0; i < n; ++i) {
    if (rule_applies_to_field(r + i, f)) {
      return true;
    }
  }
  return false;
}

int main(void) {
  rule_t rules[25] = { 0, };
  unsigned my_ticket[25] = { 0, };

  /* read rules */
  char buf[100] = { 0, };
  size_t n_rules = 0;
  for (; fgets(buf, sizeof buf, stdin) != 0 && buf[0] && buf[0] != '\n'; ++n_rules) {
    if (n_rules >= sizeof rules / sizeof *rules) {
      fprintf(stderr, "Error: Too many rules.\n");
      return 1;
    }
    rule_t *r = rules + n_rules;
    const char *departure = "departure";
    if (strncmp(buf, departure, (sizeof departure) - 1) == 0) {
      r->departure = true;
    }
    else {
      r->departure = false;
    }
    char *b = buf;
    for (; *b && *b != ':'; ++b);

  if (sscanf(b, ": %u-%u or %u-%u\n", &r->min1, &r->max1, &r->min2, &r->max2) != 4) {
      fprintf(stderr, "Error parsing rule:\n%s", buf);
      return 1;
    }
    memset(r->may_fit_field, 1, sizeof r->may_fit_field);
  }

  /* read my ticket */
  (void) fgets(buf, sizeof buf, stdin); /* "your ticket:\n" */
  for (size_t i_f = 0; i_f < n_rules; ++i_f) {
    (void) scanf("%u", my_ticket + i_f); /* error? meh. */
    (void) getchar(); /* ',' or line feed */
  }

  /* read other tickets, validate them, check which rules may correspond to which fields */
  (void) getchar(); /* line feed */
  (void) fgets(buf, sizeof buf, stdin); /* "nearby tickets:\n" */

  int sum_of_invalid_fields = 0;
  unsigned fields[25] = { 0, };
  size_t i_f = 0;
  while (scanf("%u", fields + i_f) > 0) {
    ++i_f;
    if (getchar() != ',') {
      /* part 1 filter */
      bool is_valid = true;
      for (size_t i_f = 0; i_f < n_rules; ++i_f) {
        if (!any_rule_applies(rules, n_rules, fields[i_f])) {
          is_valid = false;
          sum_of_invalid_fields += fields[i_f];
        }
      }
      /* part 2 filter */
      if (is_valid) {
        for (size_t i_f = 0; i_f < n_rules; ++i_f) {
          unsigned f = fields[i_f];
          for (size_t i_r = 0; i_r < n_rules; ++i_r) {
            rule_t *r = rules + i_r;
            if (!rule_applies_to_field(r, f)) {
              r->may_fit_field[i_f] = false;
            }
          }
        }
      }
      i_f = 0;
    }
    if (i_f > n_rules) {
      fprintf(stderr, "Too many fields.\n");
      return 1;
    }
  }
  if (ferror(stdin)) {
    fprintf(stderr, "Input error: %s\n", strerror(errno));
    return 1;
  }

  printf("%lld\n", (long long) sum_of_invalid_fields);

  /* part 2 solution */
  unsigned assigned_fields[25] = { 0, }; /* given a rule index, get the assigned field */
  for (size_t k = 0; k < n_rules; ++k) {
    /* find a rule for which only one field fits */
    for (size_t i_r = 0; i_r < n_rules; ++i_r) {
      unsigned number_of_possible_fields = 0;
      size_t field = 0;
      for (size_t i_f = 0; i_f < n_rules && number_of_possible_fields < 2; ++i_f) {
        if (rules[i_r].may_fit_field[i_f]) {
          ++number_of_possible_fields;
          field = i_f;
        }
      }
      if (number_of_possible_fields == 1) {
        assigned_fields[i_r] = field;
        for (size_t i_r = 0; i_r < n_rules; ++i_r) {
          rules[i_r].may_fit_field[field] = false;
        }
        break;
      }
    }
  }
  unsigned long long prod = 1;
  for (size_t i = 0; i < n_rules; ++i) {
    if (rules[i].departure) {
      prod *= (unsigned long long) my_ticket[assigned_fields[i]];
    }
  }
  printf("%llu\n", prod);

  return 0;
}