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
|
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
struct num {
long val;
long ord;
};
// Proper mathematical modulo, which returns a value in the range 0 <= n < m
// Even if n is negative.
// Warning, evaluates `m` multiple times (but `n` only once)
#define modulo(n, m) ((((n) % (m)) + (m)) % (m))
int
main(int argc, char ** argv)
{
long key = 1, rounds = 1;
char buf[BUFSIZ];
struct num * nums = NULL;
int nnums = 0, numsize = 0, r, i, pos;
// Parse options
while ((i = getopt(argc, argv, "p:k:r:")) != -1) {
switch (i) {
case 'p':
switch (atoi(optarg)) {
case 1:
key = 1;
rounds = 1;
break;
case 2:
key = 811589153;
rounds = 10;
break;
default:
fprintf(stderr, "Invalid part %s\n", optarg);
return -1;
}
break;
case 'k':
key = atoi(optarg);
if (!key) {
fprintf(stderr, "Invalid key %s\n", optarg);
return -1;
}
break;
case 'r':
rounds = atoi(optarg);
if (rounds < 0) {
fprintf(stderr, "Invalid rounds %s\n", optarg);
return -1;
}
break;
default:
return -1;
}
}
// Read file.
while (fgets(buf, sizeof(buf), stdin)) {
char * end;
if (nnums == numsize) {
void * p;
numsize += BUFSIZ;
if ((p = realloc(nums, numsize * sizeof(struct num))) == NULL) {
fprintf(stderr, "Bad realloc(%zu)\n", numsize * sizeof(struct num));
free(nums);
return -1;
}
nums = p;
}
if ((nums[nnums].val = strtol(buf, &end, 10)) == 0
&& end == buf)
{
fprintf(stderr, "Invalid entry: %s\n", buf);
free(nums);
return -1;
}
nums[nnums].val *= key;
nums[nnums].ord = nnums;
++nnums;
}
// Mix file.
for (r = 0; r < rounds; ++r) {
for (i = 0, pos = 0; i < nnums; ++i) {
int newpos;
struct num tmp;
// Look for the num whose ordinal is i, starting from the
// position of the last num we looked at.
while (nums[pos].ord != i)
pos = modulo(pos + 1, nnums);
if (nums[pos].val == 0)
continue;
// Move this.
tmp = nums[pos];
newpos = modulo(pos + nums[pos].val, nnums - 1); // Buffer of nums does not include moving num
if (newpos > pos)
memmove(nums + pos, nums + pos + 1, (newpos - pos) * sizeof(struct num));
else
memmove(nums + newpos + 1, nums + newpos, (pos - newpos) * sizeof(struct num));
nums[newpos] = tmp;
}
}
// Find zero.
for (i = 0; i < nnums; ++i)
if (nums[i].val == 0)
break;
if (i == nnums) {
fprintf(stderr, "No zero found!\n");
free(nums);
return -1;
}
printf("Coords: %ld,%ld,%ld; sum %ld\n",
nums[modulo(i + 1000, nnums)].val,
nums[modulo(i + 2000, nnums)].val,
nums[modulo(i + 3000, nnums)].val,
nums[modulo(i + 1000, nnums)].val
+ nums[modulo(i + 2000, nnums)].val
+ nums[modulo(i + 3000, nnums)].val);
free(nums);
return 0;
}
|
