2016 Advent of Code Day 1, Part 1 and Part 2

Question

I've been reading the Rust versions of this, and just because I'm kinda tired, I thought I'd just throw together something in C.

Here's my 15 minute effort to solve the 2016 Advent of Code Day 1, Part 1 problem. The task is to follow some directions (90° turns and steps on a rectilinear grid), then state the rectilinear distance from the origin.

// http://adventofcode.com/2016/day/1
//
// "C:\Program Files (x86)\Microsoft Visual Studio 14.0\VC\bin\x86_amd64\vcvarsx86_amd64.bat" to setup
// cl day01.c to compile
// day01.exe to run

const char * input = "R4, R5, L5, L5, L3, R2, R1, R1, L5, R5, R2, L1, L3, L4, R3, L1, L1, R2, R3, R3, R1, L3, L5, R3, R1, L1, R1, R2, L1, L4, L5, R4, R2, L192, R5, L2, R53, R1, L5, R73, R5, L5, R186, L3, L2, R1, R3, L3, L3, R1, L4, L2, R3, L5, R4, R3, R1, L1, R5, R2, R1, R1, R1, R3, R2, L1, R5, R1, L5, R2, L2, L4, R3, L1, R4, L5, R4, R3, L5, L3, R4, R2, L5, L5, R2, R3, R5, R4, R2, R1, L1, L5, L2, L3, L4, L5, L4, L5, L1, R3, R4, R5, R3, L5, L4, L3, L1, L4, R2, R5, R5, R4, L2, L4, R3, R1, L2, R5, L5, R1, R1, L1, L5, L5, L2, L1, R5, R2, L4, L1, R4, R3, L3, R1, R5, L1, L4, R2, L3, R5, R3, R1, L3";

enum {N,E,S,W} direction = N;
int translate_ns[4] = {1,0,-1,0};
int translate_ew[4] = {0,1,0,-1};

int main()
{
    int ns = 0;
    int ew = 0;
    int pos = 0;
    char digit = 0;
    int walk = 0;
    while (input[pos]!='\0') {
        char turn = input[pos++];
        if (turn=='R') direction = (direction+1) % 4;
        if (turn=='L') direction = (direction+3) % 4; // bwahahah
        walk = 0;
        while ((digit=input[pos++])!='\0' && isdigit(digit)) walk = walk*10+digit-'0';
        ns += walk*translate_ns[direction];
        ew += walk*translate_ew[direction];
        while (input[pos] && (input[pos]==',' || input[pos]==' ')) pos++;
    }
    printf("Distance to Easter Bunny HQ is: %d",abs(ns)+abs(ew));
}

Output is:

C:\Workarea\AdventOfCode\Day01>day01.exe
Distance to Easter Bunny HQ is: 250
C:\Workarea\AdventOfCode\Day01>

I know it's a bit evil, and this isn't how I'd program at work, but it's nice to let my hair down occasionally. Fire away!

And here's part 2! This was harder and I had to iterate a little to get the answer to come out.

I had to add a new routine to detect a crossing over the previous route. Of course the easiest way with the in-place solution for part 1 is just to use the last added position as where we're coming from, then iterate through the previous positions and detect when we cross.

I made the passed positions pointer to int so we can update to the crossing point when needed, and still return 1 to break out of reading the routing instructions.

There's obviously a much better and shorter solution lurking in there somewhere, but at least I have something that works.

// http://adventofcode.com/2016/day/1
//
// "C:\Program Files (x86)\Microsoft Visual Studio 14.0\VC\bin\x86_amd64\vcvarsx86_amd64.bat" to setup
// cl day01.c to compile
// day01.exe to run

const char * input = "R4, R5, L5, L5, L3, R2, R1, R1, L5, R5, R2, L1, L3, L4, R3, L1, L1, R2, R3, R3, R1, L3, L5, R3, R1, L1, R1, R2, L1, L4, L5, R4, R2, L192, R5, L2, R53, R1, L5, R73, R5, L5, R186, L3, L2, R1, R3, L3, L3, R1, L4, L2, R3, L5, R4, R3, R1, L1, R5, R2, R1, R1, R1, R3, R2, L1, R5, R1, L5, R2, L2, L4, R3, L1, R4, L5, R4, R3, L5, L3, R4, R2, L5, L5, R2, R3, R5, R4, R2, R1, L1, L5, L2, L3, L4, L5, L4, L5, L1, R3, R4, R5, R3, L5, L4, L3, L1, L4, R2, R5, R5, R4, L2, L4, R3, R1, L2, R5, L5, R1, R1, L1, L5, L5, L2, L1, R5, R2, L4, L1, R4, R3, L3, R1, R5, L1, L4, R2, L3, R5, R3, R1, L3";

#define min(x,y) ((x)<(y) ? (x) : (y))
#define max(x,y) ((x)>(y) ? (x) : (y))

enum {N,E,S,W} direction = N;
int translate_ns[4] = {1,0,-1,0};
int translate_ew[4] = {0,1,0,-1};
int visited[2000];
int visited_count = 1;

int check_add_visited(int* ns, int* ew)
{
    int nsp = visited[(visited_count-1)*2];
    int ewp = visited[(visited_count-1)*2+1];
    // start from 1 so we have a previous entry to check
    int prevns = visited[0];
    int prevew = visited[1];
    for (int i=1;i<visited_count;++i) {
        // get the prev and next ns,ew to check
        int nextns = visited[i*2];
        int nextew = visited[i*2+1];
        if (prevns==nextns && ewp==*ew && min(*ns,nsp)<prevns && max(*ns,nsp)>prevns
                                       && min(prevew,nextew)<*ew && max(prevew,nextew)>*ew) {
            // found a crossing at prevns,ew
            *ns = prevns;
            return 1;
        }
        if (prevew==nextew && nsp==*ns && min(*ew,ewp)<prevew && max(*ew,ewp)>prevew 
                                       && min(prevns,nextns)<*ns && max(prevns,nextns)>*ns ) {
            // found a crossing at ns,prevew
            *ew = prevew;
            return 1;
        }
        prevns = nextns;
        prevew = nextew;
    }
    visited[visited_count*2] = *ns;
    visited[visited_count*2+1] = *ew;
    visited_count++;
    return 0;
}

int main()
{
    int ns = 0;
    int ew = 0;
    int pos = 0;
    char digit = 0;
    int walk = 0;
    visited[0] = visited[1] = 0;
    while (input[pos]!='\0') {
        char turn = input[pos++];
        if (turn=='R') direction = (direction+1) % 4;
        if (turn=='L') direction = (direction+3) % 4; // bwahahah
        walk = 0;
        while ((digit=input[pos++])!='\0' && isdigit(digit)) walk = walk*10+digit-'0';
        ns += walk*translate_ns[direction];
        ew += walk*translate_ew[direction];
        if (check_add_visited(&ns,&ew)) break;
        while (input[pos] && (input[pos]==',' || input[pos]==' ')) pos++;
    }
    printf("Distance to Easter Bunny HQ is: %d",abs(ns)+abs(ew));
}

The output from part 2 is:

C:\Workarea\AdventOfCode\Day01>day01.exe
Distance to Easter Bunny HQ is: 151
C:\Workarea\AdventOfCode\Day01>

Answer 1

Two things to note at the beginning:

1. I'm only reviewing part I in this answer. I'd love to do #2 as well, but I'm a bit pressed for time right now. I might do it later. Also, this has gotten long enough with just one part reviewed.

2. Am I your hair? Because I feel pretty let down. When I read this:

   I know it's a bit evil, and this isn't how I'd program at work, but it's nice to let my hair down occasionally.

   I hadn't read the code yet, and I was expecting the kind of truly awful stuff you get if you tell someone with three days' experience in Java and nothing else to write C. Maybe I just have really, really low (high?) expectations, but your code isn't that bad.

With that said, there are some things that could use improvement, so let's go through them:

• Comments. Please. I mean, everything's understandable once you read through the code, but it's good to give people an understanding of what, say, translate_ns means before it's used. Remember how in math class, your teacher started you on solving for the roots of a parabola before teaching you what it was? No, you don't, because definition before usage is a concept that permeates just about everything for good reason.

  • Personally, I'd recommend at least commenting what ns and ew are, or renaming them to delta_ns and delta_ew so it's clearer that it's the displacement. From there, the other unclear things (mostly the translate_s) are pretty easy to figure out.

• You forgot a few #includes. To get this to compile on my machine, I had to add this to the beginning:

  #include <ctype.h>
  #include <stdlib.h>
  #include <stdio.h>
  

• You don't use E, S, or W, but I like that you defined them anyway, to make it clear what that enum represents.

• For the translate_s, good idea to make it a four-element array, so you can just use direction as an index. It simplifies the code by a good amount.

• This isn't C90; you don't need to declare every variable at the top of its scope. All that does is make things less clear. Move variable declarations to right before they're used.

• pos should be a size_t, not an int. size_t is guaranteed to be able to hold the largest possible index in an array, so you can be sure it'll never overflow. On the other hand, int has no such guarantee.

• You might consider using a char *pos over size_t pos, and sidestep the whole issue above. You never use the index for anything but getting the position of the character you're at, and you never do anything but go forward one position and get the character at the current index. You could just as easily move a pointer into the string, rather than keep track of an index. Either way works; I prefer the latter because I get to show off my understanding of pointers.

• This is mostly a style thing, but put spaces around binary operators, and use parentheses liberally. It's almost always better to be explicit than implicit, and GCC will produce the same bytecode either way (assuming the parens follow order of operations, at least).

• Again, mostly a style thing, but I always have brackets with my control statements. It's easier for me to read, encourages me to have a little vertical spacing, and makes it easier for me to modify the code later -- I can just add the code in wherever it makes sense, without worrying about braces.

• Instead of char turn = input[pos++];, which is clear, well-defined, and more than a little confusing, I'd suggest char turn = input[pos]; ++pos;, which is all of those and less confusing. That way, it's clearer what you're doing. You do this in a couple of places; I'd change it everywhere.

• I don't get it:

  // bwahahah
  

  I mean, all you're doing is an addition with modulo. What's so funny? Is it that 3 mod 4 is equivalent to -1 mod 4?

• It's generally considered good form to put a \n after each printf, especially if it's the last one in your program. It's always annoying to get this:

  > ./a.out
  Distance to Easter Bunny HQ is: 250> 
  

With each of those applied (including the optional style changes I recommended, because my IDE automatically applies those), some documenting comments added and your confusing comment left in, this is your code:

#include <ctype.h>
#include <stdlib.h>
#include <stdio.h>

const char * input = "R4, R5, L5, L5, L3, R2, R1, R1, L5, R5, R2, L1, L3, L4, R3, L1, L1, R2, R3, R3, R1, L3, L5, R3, R1, L1, R1, R2, L1, L4, L5, R4, R2, L192, R5, L2, R53, R1, L5, R73, R5, L5, R186, L3, L2, R1, R3, L3, L3, R1, L4, L2, R3, L5, R4, R3, R1, L1, R5, R2, R1, R1, R1, R3, R2, L1, R5, R1, L5, R2, L2, L4, R3, L1, R4, L5, R4, R3, L5, L3, R4, R2, L5, L5, R2, R3, R5, R4, R2, R1, L1, L5, L2, L3, L4, L5, L4, L5, L1, R3, R4, R5, R3, L5, L4, L3, L1, L4, R2, R5, R5, R4, L2, L4, R3, R1, L2, R5, L5, R1, R1, L1, L5, L5, L2, L1, R5, R2, L4, L1, R4, R3, L3, R1, R5, L1, L4, R2, L3, R5, R3, R1, L3";

enum { N, E, S, W } direction = N;
// how much to change delta_ns by for each direction
int translate_ns[4] = {1,0,-1,0};
// ditto for delta_ew
int translate_ew[4] = {0,1,0,-1};

int main()
{
    // the vertical (north-south) displacement
    int delta_ns = 0;
    // the horizontal (east-west) displacement
    int delta_ew = 0;
    // our current position in the string
    char *pos = (char *)input;
    while (*pos != '\0') {
        char turn = *pos;
        ++pos;
        if (turn=='R') {
            direction = (direction+1) % 4;
        }
        if (turn=='L') {
            // bwahahah
            direction = (direction+3) % 4;
        }

        char digit = 0;
        int walk = 0;
        while ((digit = *pos) != '\0' && isdigit(digit)) {
            ++pos;
            walk = (walk * 10) + (digit - '0');
        }

        delta_ns += walk * translate_ns[direction];
        delta_ew += walk * translate_ew[direction];
        while (*pos && (*pos == ',' || *pos == ' ')) ++pos;
    }
    printf("Distance to Easter Bunny HQ is: %d\n", abs(delta_ns) + abs(delta_ew));
}

^{...wow, input is a long string. I didn't realize that before.}

And running it still gives the same output:

Distance to Easter Bunny HQ is: 250