3
\$\begingroup\$

I'm teaching myself C, with an older edition of K. N. King's C Programming: A Modern Approach. I come from a Python and JavaScript background as far as programming goes, but not a strong foundation in theoretical CS concepts. I'm currently up to Chapter 8 of the book, which introduces one- and multi-dimensional arrays in C. The final exercise of the chapter is to write a program that takes a 10x10 grid and prints the letters of the alphabet in sequence, but picking one of the open adjacent squares to the last-placed character in order to place the next character in sequence. The result resembles a "random walk" through the grid. The program must terminate early if it reaches a point with no open spaces to continue the sequence. My attempt is below. I'm looking for general feedback. I know that there are almost certainly better data structures I could be using, but bear in mind that I haven't even started reading the chapter on functions: so I've only been exposed to elementary types, arrays, some operators, conditional expressions, etc. Bear those constraints in mind if you can.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define N 10
#define TRUE 1
#define FALSE 0
#define START 'A'
#define END 'Z'

typedef int Bool;

int main() {
  char grid[N][N] = {};
  int i = 0;
  int j = 0;
  int next_j = 0;
  int next_i = 0;
  int move, open_spaces;
  Bool placed = FALSE;
  Bool examined_spaces[4] = {};
  // Initialise a random number generator using current time,
  // to ensure it's different each loop
  srand((unsigned) time(NULL));
  // Loop alphabet
  for (char c = START; c <= END; c++) {
    open_spaces = 4;
    memset(examined_spaces, 0, sizeof(Bool)*4); // Empty examined spaces array

    grid[i][j] = c;
    // Determine the next position
    if (c == END) {
      // end of iteration
      placed = TRUE;
    } else {
      // Need to determine the position of the next character
      placed = FALSE;
    }
    // Placed, calculating position of next character
    while ((!placed) && (open_spaces > 0)) {
      next_i = i;
      next_j = j;
      move = rand() % 4;
      if (examined_spaces[move] == TRUE) {
        // Already examined this move
        continue;
      }
      if (examined_spaces[move] == FALSE) {
        // A new move
        open_spaces--;
        examined_spaces[move] = TRUE;
      }
      switch (move) {
        case 0: next_j--; break; // up
        case 1: next_i++; break; // right
        case 2: next_j++; break; // down
        case 3: next_i--; break; // left
      }
      if (next_j + 1 > N || next_j < 0 || next_i + 1 > N || next_i < 0) {
        // Out of bounds
        continue;
      } else if (grid[next_i][next_j] != 0) {
        // Already occupied by a character
        continue;
      } else {
        // Successful placement
        placed = TRUE;
        i = next_i;
        j = next_j;
      }
    }
    if (open_spaces <= 0 && !placed) {
      // No more empty spaces
      break;
    }
  }
  for (i = 0; i < N; i++) {
    for (j = 0; j < N; j++) {
      if (grid[i][j] == 0) {
        printf(". ");
      } else {
        printf("%c ", grid[i][j]);
      }
      if (!((j + 1) % 10)) {
        printf("\n");
      }
    }
  }
  return 0;
}
\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

Only Use Conditions When It Is Necessary
In the for loop that displays the grid the condition

if (!((j + 1) % 10)) {

is unnecessary. Move the new line printf outside the inner loop and it will execute when the inner loop ends.

Algorithm
The algorithm doesn't seem to be using the diagonals which means there are 4 additional spots a character might go to.

It's not clear that the program works completely when I ran the program it went up to H and then quit so the grid was mostly ..

Variable and Symbolic Constant Names
There are some pretty good names such as open_spaces, examined_spaces, placed, grid, TRUE, FALSE, START, END and then there are names such as N, i, j, next_j and next_i. In particular i and j seem to indicate directions so horizontal and vertical might be better names. N might be better called GRID_SIZE.

There also seems to be a missing symbolic constant for 4 (OPEN_SPACES_SIZE).

Functions
Just because you haven't read the chapter on functions doesn't mean you shouldn't use them if you are accustomed to writing code using functions. It definitely would help the code.

\$\endgroup\$
1
  • \$\begingroup\$ Thank you for your feedback. The exercise mandated an early termination if the sequence cannot be completed ("the snake gets trapped"), which would be why yours ended at H. Diagonal movement was out of scope for the exercise. I plan to revisit some exercises once I've learned about using functions and other relevant concepts in C. One thing I don't like about my code is that it wastes time randomly selecting potential moves that have already been considered and thrown away. \$\endgroup\$ Commented May 28, 2017 at 22:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.