The challenge

You live in the city of Cartesia where all roads are laid out in a perfect grid. You arrived ten minutes too early to an appointment, so you decided to take the opportunity to go for a short walk. The city provides its citizens with a Walk Generating App on their phones — everytime you press the button it sends you an array of one-letter strings representing directions to walk (eg. [‘n’, ‘s’, ‘w’, ‘e’]). You always walk only a single block for each letter (direction) and you know it takes you one minute to traverse one city block, so create a function that will return true if the walk the app gives you will take you exactly ten minutes (you don’t want to be early or late!) and will, of course, return you to your starting point. Return false otherwise.

Note: you will always receive a valid array containing a random assortment of direction letters (‘n’, ‘s’, ‘e’, or ‘w’ only). It will never give you an empty array (that’s not a walk, that’s standing still!).

The solution in C

Option 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#include <stdbool.h>

bool isValidWalk(const char *walk) {
  if (strlen(walk) != 10) return 0;
  
  int h = 0, v = 0;
  while(*walk) {
    switch(*walk) {
      case 'n': ++v; break;
      case 's': --v; break;
      case 'e': ++h; break;
      case 'w': --h; break;
    }
    ++walk;
  }
  return h == 0 && v == 0;
}

Option 2:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

#include <stdbool.h>

bool isValidWalk(const char *walk) {
     int i=0, north_south=0, vest_est=0; 
     for(; i< walk[i]; i++){
       if(walk[i] == 'n' ) north_south++;
       if(walk[i] == 's' ) north_south--;
       if(walk[i] == 'e' ) vest_est++;
       if(walk[i] == 'w' ) vest_est--;
        
     }
     if(i==10 && north_south==0 && vest_est==0) return true; else return false;
}

Option 3:

 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

#include <stdbool.h>

bool isValidWalk(const char *walk) {

   char* c = walk;
   int up, right, count;
   up = right = count = 0;
   while( *c !='\0' ){
     switch(*c){
       case 'n':
         count++;
         up++;
         break;
       case 's':
         count++;
         up--;
         break;
       case 'e':
         count++;
         right++;
         break;
       case 'w':
         count++;
         right--;
         break;
     
     }
     c++;    
   }
   return up == 0 && right == 0 && count == 10;
}

Test cases to validate our solution

 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

#include <criterion/criterion.h>
#include <stdbool.h>
#include <stdlib.h>
#include <time.h>

void tester(char *twalk, bool expected);

Test(Fixed_Tests, should_return_true_for_a_valid_walk) {
  tester("nsnsnsnsns", true);
  tester("ewewnsnsew", true);
  tester("nsewnsewns", true);
  tester("sewnnsewns", true);
}

Test(Fixed_Tests, should_return_false_if_walk_is_too_short) {
  tester("n", false);
  tester("ns", false);
}

Test(Fixed_Tests, should_return_false_if_walk_is_too_long) {
  tester("nsnsnsnsnsns", false);
  tester("nsewnsewnsewnsew", false);
  tester("nsnsnsnsnsewewewewew", false);
}

Test(Fixed_Tests, should_return_false_if_walk_does_not_bring_you_back_to_start) {
  tester("nsnsnsnsnn", false);
  tester("eeewnsnsew", false);
}

static bool solution(const char *swalk) {
    int i=0, n=0, e=0, w=0, s=0;
    while(*swalk) {
        char current = *swalk++;
        if(current == 'n') n++; else
        if(current == 'e') e++; else
        if(current == 'w') w++; else
        if(current == 's') s++; i++;
    }
    return i == 10 && n == s && w == e;
}

static char* getWalk(size_t steps) {
    char *gwalk = (char*) malloc((steps + 1) * sizeof(char));
    if(steps == 10) {
        const char* valid[6] = {"nnnnnsssss", "nnnnewssss", "nnneewwsss",
                                "nneeewwwss", "neeeewwwws", "eeeeewwwww"};
        const char news[4] = {'n', 'e', 'w', 's'};
        strcpy(gwalk, valid[rand() % 6]);
        if(rand() % 2) {
            gwalk[rand() % 10] = news[rand() % 4];
        }
    }
    else {
        size_t i = 0;
        char n_e[2] = {'n', 'e'};
        char w_s[2] = {'w', 's'};
        for(; i<steps; i++) {
            if(rand() % 2) {
                gwalk[i] = n_e[rand() % 2];
            }
            else {
                gwalk[i] = w_s[rand() % 2];
            }
        }
        gwalk[i] = '\0';
    }
    return gwalk;
}

Test(Random_Tests, should_pass_all_the_tests_provided) {
    srand(time(NULL));

    int count = 100;
    while(count--) {
        int minutes[25] = {10,10,10,8,10,10,10,1,10,10,10,2,10,
                           10,10,9,10,10,10,11,10,10,10,100,10};
        int rand_mins = minutes[rand() % 25];
        char *rand_walk = getWalk(rand_mins);
        int answer = solution(rand_walk);
        tester(rand_walk, answer);
        free(rand_walk); rand_walk = NULL;
    }
}