-
Notifications
You must be signed in to change notification settings - Fork 0
/
aoc14.c
155 lines (143 loc) · 4.44 KB
/
aoc14.c
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
#include <stdio.h>
#include <string.h>
#include <inttypes.h>
#include <stdbool.h>
char map[128][128] = {0};
void tilt_north( int width, int height) {
for( int y=0; y<height; y++ ) {
for( int x=0; x<width; x++ ) {
if( map[y][x] == 'O') {
int dest = y;
for( int yd=y-1; yd>=0; yd-- ) {
if( map[yd][x] !='.' )break;
dest = yd;
}
if( dest!= y) {
map[dest][x] = 'O';
map[y][x] = '.';
}
}
}
}
}
void tilt_south( int width, int height) {
for( int y=height-1; y>=0; y-- ) {
for( int x=0; x<width; x++ ) {
if( map[y][x] == 'O') {
int dest = y;
for( int yd=y+1; yd<height; yd++ ) {
if( map[yd][x] !='.' )break;
dest = yd;
}
if( dest!= y) {
map[dest][x] = 'O';
map[y][x] = '.';
}
}
}
}
}
void tilt_west( int width, int height) {
for( int x=0; x<width; x++ ) {
for( int y=0; y<height; y++ ) {
if( map[y][x] == 'O') {
int dest = x;
for( int xd=x-1; xd>=0; xd-- ) {
if( map[y][xd] !='.' )break;
dest = xd;
}
if( dest!= x) {
map[y][dest] = 'O';
map[y][x] = '.';
}
}
}
}
}
void tilt_east( int width, int height) {
for( int x=width-1; x>=0; x-- ) {
for( int y=0; y<height; y++ ) {
if( map[y][x] == 'O') {
int dest = x;
for( int xd=x+1; xd<width; xd++ ) {
if( map[y][xd] !='.' )break;
dest = xd;
}
if( dest!= x) {
map[y][dest] = 'O';
map[y][x] = '.';
}
}
}
}
}
uint64_t calc_weight( int width, int height ) {
uint64_t total_weight = 0;
for( int y=0; y<height; y++ ) {
for( int x=0; x<width; x++ ) {
if( map[y][x] == 'O') total_weight += height-y;
}
}
return total_weight;
}
int detect_loop( uint64_t* weights, int num_weights, uint64_t target_cycles) {
// The loop detector just uses the weights. This could in theory find false loops where the weights just happen
// to match the chances of an entire loop of false matches seems extremely small
for( int loop_size=2; loop_size<10000; loop_size++ ) {
if( num_weights > loop_size*2 ) {
bool is_looping = true;
for (int loop = 0; loop < loop_size; loop++) {
int idx = num_weights - 1 - loop;
int idx2 = idx-loop_size;
if (weights[idx] != weights[idx2]) {
is_looping = false;
break;
}
}
if (is_looping) {
uint64_t remaining_loops = (target_cycles-num_weights) / loop_size;
uint64_t skip = remaining_loops * loop_size;
uint64_t skipped_pos = num_weights + skip;
int idx = num_weights - loop_size + (target_cycles - skipped_pos)-1;
return weights[ idx ];
}
}
}
return 0;
}
void read_map(int* pwidth, int* pheight ) {
FILE *fp = fopen("input14.txt", "r");
int width;
int height = -1;
while( fgets(map[++height], 128, fp));
fclose( fp );
*pwidth = strlen(map[height-1]);
*pheight = height;
}
int main(void) {
FILE *fp = fopen("input14.txt", "r");
int width;
int height;
read_map( &width, &height);
// Part1
tilt_north( width, height);
uint64_t weight = calc_weight( width, height );
printf( "Part1, weight %"PRIu64" \n", weight);
// Part 2
uint64_t weights[ 10000 ] ={0};
read_map( &width, &height);
int num_weights = 0;
for( ;; ) {
tilt_north(width,height);
tilt_west(width,height);
tilt_south(width,height);
tilt_east(width,height);
uint64_t weight = calc_weight( width, height );
weights [ num_weights++] = weight;
int solution = detect_loop( weights, num_weights, 1000000000 );
if( solution > 0 ) {
printf( "Part2, solution %"PRIu64" \n", solution);
break;
}
}
}