Created
December 3, 2017 11:59
-
-
Save saucecode/0d92c93fa394788a635826870ddcc720 to your computer and use it in GitHub Desktop.
my C99 solution to advent of code 2017 day 3 part 2
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdint.h> | |
#include <stdio.h> | |
#include <string.h> | |
// returns the sum of all 8 adjacent cells to element [cy][cx] in a 2D array, with bounds checking | |
uint32_t setdata(uint32_t root_max, uint32_t data[][root_max], uint32_t cx, uint32_t cy){ | |
uint32_t counter = 0; | |
if(cx + 1 < root_max){ | |
counter += data[cy][cx+1]; | |
if(cy - 1 >= 0) | |
counter += data[cy-1][cx+1]; | |
if(cy + 1 < root_max) | |
counter += data[cy+1][cx+1]; | |
} | |
if(cx - 1 >= 0){ | |
counter += data[cy][cx-1]; | |
if(cy - 1 >= 0) | |
counter += data[cy-1][cx-1]; | |
if(cy + 1 < root_max) | |
counter += data[cy+1][cx-1]; | |
} | |
if(cy - 1 >= 0) | |
counter += data[cy-1][cx]; | |
if(cy + 1 < root_max) | |
counter += data[cy+1][cx]; | |
return counter; | |
} | |
uint32_t solve(uint32_t input){ | |
// calculate the side length (root_max) of the square ring 'input' lies on | |
uint32_t root_max = 0, square = 0; | |
while(square < input){ | |
root_max += 1; | |
square = root_max * root_max; | |
} | |
uint32_t data[root_max][root_max]; | |
memset(&data[0][0], '\0', sizeof(data)); | |
uint32_t cx = root_max/2, cy = root_max/2; | |
data[cy][cx] = 1; | |
uint32_t root = 3; | |
uint32_t dim = root - 1; | |
cx += 1; // start on the cell 1-unit left of center | |
// GENERATE THE SPIRAL!!! | |
// up dim-1, right dim, down dim, left dim+1, root += 2, recalculate dim, repeat | |
while(root < root_max){ | |
// traverse up dim-1 | |
for(int i=0; i<dim-1; i+=1){ | |
// set value at cx,cy | |
data[cy][cx] = setdata(root_max, data, cx, cy); | |
if(data[cy][cx] > input) goto WE_FOUND_IT; | |
cy -= 1; | |
} | |
// traverse right dim | |
for(int i=0; i<dim; i+=1){ | |
data[cy][cx] = setdata(root_max, data, cx, cy); | |
if(data[cy][cx] > input) goto WE_FOUND_IT; | |
cx -= 1; | |
} | |
// traverse down dim | |
for(int i=0; i<dim; i+=1){ | |
data[cy][cx] = setdata(root_max, data, cx, cy); | |
if(data[cy][cx] > input) goto WE_FOUND_IT; | |
cy += 1; | |
} | |
// traverse left dim+1 | |
for(int i=0; i<dim+1; i+=1){ | |
data[cy][cx] = setdata(root_max, data, cx, cy); | |
if(data[cy][cx] > input) goto WE_FOUND_IT; | |
cx += 1; | |
} | |
root += 2; | |
dim = root -1; | |
} | |
return -1; | |
WE_FOUND_IT: | |
return data[cy][cx]; | |
} | |
int main(int argc, char **argv){ | |
uint32_t challenge_input = 265149; | |
printf("%i\n", solve(challenge_input)); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment