Afternoon hack, and relearning C. Find all paths of the dummy robot on a nxn grid.

MyRobot.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>

int size;
int size_minus_1;

struct move {
  int x;
  int y;
  struct move *prev;
};
typedef struct move Node;

// O(1)
inline int eqv(Node *a, Node *b) {
  return (a->x == b->x && a->y == b->y);
}
// O(1)
inline int in_bounds(Node *n) {
  return (n->x < size && n->y < size && n->x >= 0 && n->y >= 0);
}
// O(1)
inline int is_target(Node *n) {
  return ((n->x == size_minus_1) && (n->y == size_minus_1));
}
// O(n)
inline int is_valid(Node *new, int len) {
  // check for dups
  Node *cur = new->prev;
  int i = 0;
  while(len-- > 1) {
    if(eqv(cur, new)) {
      return 0;
    }
    cur = cur->prev;
  }
  return 1;
}
int num_paths(Node *tail, int len) {
  int sum = 0;
  int i = 0;
  
  // Check for base case
  if(is_target(tail)) { return 1; }
  Node *n = (Node *) malloc(sizeof(Node));
  int new_len = len + 1;  
  
  // Explore the 4 directions (left unraveled)
  n->x = tail->x;
  n->y = tail->y + 1;
  n->prev = tail;    
  if(in_bounds(n) && is_valid(n, new_len)) {
    sum += num_paths(n, new_len);
  }
  
  n->x = tail->x;
  n->y = tail->y - 1;
  n->prev = tail;    
  if(in_bounds(n) && is_valid(n, new_len)) {
    sum += num_paths(n, new_len);
  }
  
  n->x = tail->x + 1;
  n->y = tail->y;
  n->prev = tail;    
  if(in_bounds(n) && is_valid(n, new_len)) {
    sum += num_paths(n, new_len);
  }
  
  n->x = tail->x - 1;
  n->y = tail->y;
  n->prev = tail;    
  if(in_bounds(n) && is_valid(n, new_len)) {
    sum += num_paths(n, new_len);
  }
  
  free(n);
  return sum;  
}

int main(int argc, char *argv[]) {
  struct timeval start, end;

  gettimeofday(&start, NULL);
  
  Node *head = (Node *) malloc(sizeof(Node));
  head->x = 0;
  head->y = 0;
  head->prev = NULL;
  
  size = (argc == 1) ? 5 : atoi(argv[1]);
  size_minus_1 = size - 1;
  
  printf("Searching for an %ix%i grid\r\n", size, size);  
  int paths = num_paths(head, 1);
  printf("Total paths: %i\r\n", paths);
  
  gettimeofday(&end, NULL);
  printf("Time Elapsed: %f ms\n", ((end.tv_sec * 1000000 + end.tv_usec) - (start.tv_sec * 1000000 + start.tv_usec))/1000.0);  
  return 0;
}

Compile with -O2 for the extra lulz