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
|
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
struct mem_entry {
long address;
long value;
struct mem_entry *next;
};
struct mem_map {
struct mem_entry *head;
struct mem_entry *tail;
};
// THIS FUNCTION IS THE SPEED PROBLEM!
struct mem_entry *get_entry(struct mem_map *mem_map, int address)
{
if (!mem_map || !mem_map->head || !mem_map->tail)
return NULL;
struct mem_entry *iterator = mem_map->head;
while (iterator) {
if (iterator->address == address)
return iterator;
iterator = iterator->next;
}
return NULL;
}
void new_entry(struct mem_map *mem_map, long address, long value)
{
if (!mem_map)
return;
struct mem_entry *override = NULL;
if ((override = get_entry(mem_map, address))) {
override->value = value;
return;
}
struct mem_entry *new = malloc(sizeof(*new));
new->address = address;
new->value = value;
new->next = NULL;
if (mem_map->head && mem_map->tail) {
mem_map->tail->next = new;
mem_map->tail = new;
} else {
mem_map->head = new;
mem_map->tail = mem_map->head;
}
}
long count_doku(struct mem_map *mem_map)
{
if (!mem_map || !mem_map->head || !mem_map->tail)
return 0;
long cnt = 0;
struct mem_entry *iterator = mem_map->head;
while (iterator) {
cnt += iterator->value;
iterator = iterator->next;
}
return cnt;
}
long part_one(FILE *fp)
{
char *line = NULL;
size_t len = 0;
char mask[36] = { 0 };
struct mem_map mem_map = { 0 };
while (getline(&line, &len, fp) != -1) {
if (line[0] == 'm' && line[1] == 'a') {
sscanf(line, "mask = %s\n", &mask[0]);
} else if (line[0] == 'm' && line[1] == 'e') {
int address;
long value;
sscanf(line, "mem[%d] = %lu\n", &address, &value);
for (char *p = mask; *p; p++) {
long shift = 1ul << (35 - (p - mask));
if (*p == '0')
value &= ~shift;
else if (*p == '1')
value |= shift;
}
new_entry(&mem_map, address, value);
}
}
return count_doku(&mem_map);
}
long part_two(FILE *fp)
{
char *line = NULL;
size_t len = 0;
char mask[36] = { 0 };
int floating_bits[64];
struct mem_map mem_map = { 0 };
while (getline(&line, &len, fp) != -1) {
if (line[0] == 'm' && line[1] == 'a') {
sscanf(line, "mask = %s\n", &mask[0]);
} else if (line[0] == 'm' && line[1] == 'e') {
long address = 0, value = 0;
sscanf(line, "mem[%lu] = %lu\n", &address, &value);
int floating = 0;
for (int i = 0; i < 36; i++) {
if (mask[i] == '1') {
address |= 1ul << (36 - i - 1);
} else if (mask[i] == 'X') {
floating_bits[floating] = i;
floating++;
}
}
long masked_addr = address;
for (long perm = 0; perm < (1 << floating); ++perm) {
long address = masked_addr;
for (int j = 0; j < floating; j++)
if (perm & (1ul << j))
address ^= (1ul << (36 - floating_bits[j] - 1));
new_entry(&mem_map, address, value);
}
}
}
return count_doku(&mem_map);
}
int main(int argc, char *argv[])
{
FILE *fp = fopen("input", "r");
if (!fp)
exit(EXIT_FAILURE);
clock_t tic = clock();
printf("%lu\n", part_one(fp));
rewind(fp);
printf("%lu\n", part_two(fp));
clock_t toc = clock();
printf("TIME: %f seconds\n", (double)(toc - tic) / CLOCKS_PER_SEC);
fclose(fp);
return 0;
}
|
