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
|
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#if 0
#define PART part1
#else
#define PART part2
#endif
#if 0
#define FILENAME "sample.txt"
#define TARGET_Y 10
#define UPPER 20
#else
#define FILENAME "input.txt"
#define TARGET_Y 2000000
#define UPPER 2000000
#endif
#define LOWER 1000000
#define ENTRIES_CAP 30
#define CAP 10000000
#define OFFSET (CAP/2)
int sensors[CAP][2];
int beacons[CAP][2];
size_t entries = 0;
int obj[CAP];
int row[CAP];
size_t sum = 0;
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
int taxi_distance(int x1, int y1, int x2, int y2)
{
return abs(x1 - x2) + abs(y1 - y2);
}
void analyze(int target_y)
{
memset(obj, 0, sizeof(obj));
memset(row, 0, sizeof(row));
for(size_t i = 0; i < entries; i++)
{
int x1 = sensors[i][0]; int x2 = beacons[i][0];
int y1 = sensors[i][1]; int y2 = beacons[i][1];
int r = taxi_distance(x1, y1, x2, y2);
int diff = abs(target_y - y1);
for(int i = x1 - (r - diff); i <= x1 + (r - diff); i++) {
row[i + OFFSET] = 1;
}
if(y2 == target_y) obj[x2 + OFFSET] = 1;
}
}
void part1()
{
analyze(TARGET_Y);
for(size_t i = 0; i < CAP; i++)
if(row[i] - obj[i] > 0) sum++;
}
void part2()
{
for(int y = LOWER; y <= UPPER; y++)
{
printf("%d\n", y);
analyze(y);
for(int x = LOWER; x <= UPPER; x++)
if(row[x + OFFSET] == 0 && obj[x + OFFSET] == 0) {
sum = (x * 4000000) + y;
return;
}
}
exit(1);
}
void parse_xy(char *str, int *x, int *y, int nth)
{
char *s, *sx;
char *y_str, *x_str;
x_str = strtok_r(strtok_r(str, ",", &s), " ", &sx);
y_str = strtok_r(NULL, ",", &s);
for(int i = 1; i < nth; i++)
x_str = strtok_r(NULL, " ", &sx);
assert(x_str != NULL);
assert(y_str != NULL);
*x = atoi(&(x_str[2]));
*y = atoi(&(y_str[3]));
}
void parse()
{
FILE *fp = fopen(FILENAME, "r");
if(!fp) {
fprintf(stderr, "ERROR: Could not open file: %s\n", FILENAME);
exit(1);
}
char line[512];
while(fgets(line, sizeof(line), fp))
{
size_t len = strlen(line);
if(line[len-1] == '\n') line[len-1] = 0;
parse_xy(strtok(line, ":"), &sensors[entries][0], &sensors[entries][1], 3);
parse_xy(strtok(NULL, ":"), &beacons[entries][0], &beacons[entries][1], 5);
entries++;
}
fclose(fp);
}
int main(void)
{
parse();
PART();
printf("%ld\n", sum);
return 0;
}
|
