Skip to content

Instantly share code, notes, and snippets.

@saucecode
Created December 3, 2017 11:59
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save saucecode/0d92c93fa394788a635826870ddcc720 to your computer and use it in GitHub Desktop.
Save saucecode/0d92c93fa394788a635826870ddcc720 to your computer and use it in GitHub Desktop.
my C99 solution to advent of code 2017 day 3 part 2
#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