10
\$\begingroup\$

Challenge

Find all possible moves for a knight on an empty chessboard.

Specifications

  1. The first argument is a path to a file.
  2. The file contains multiple lines.
  3. Each line is a test case representing the position of the knight in CN form.
    • C is a letter from “a” to “h” and denotes a column.
    • N is a number from 1 to 8 and denotes a row.
  4. For each test case, print all positions for the next move of the knight ordered alphabetically.

                                            enter image description here

Sample Input

g2
a1
d6
e5
b1

Sample Output

e1 e3 f4 h4
b3 c2
b5 b7 c4 c8 e4 e8 f5 f7
c4 c6 d3 d7 f3 f7 g4 g6
a3 c3 d2

Source

My Solution

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

#define LINE_LENGTH 5
#define BOARD_LENGTH 8
#define MOVE_BUFFER 24

int rows[] = {1, 2, 3, 4, 5, 6, 7, 8};
char cols[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'};
char moves[MOVE_BUFFER];
int move_iter = 0;

char num_convert(int *n) {
    for (int i = 0; i < BOARD_LENGTH; i++) {
        if (*n == rows[i]) {
            return cols[i];
        }
    }
}

int alpha_convert(char *c) {
    for (int i = 0; i < BOARD_LENGTH; i++) {
        if (*c == cols[i]) {
            return rows[i];
        }
    }
}

void add_moves(int c, int n1, int n2) {
    if (c >= 1 && c <= 8) {
        if (n1 >= 1) {
            moves[move_iter++] = num_convert(&c);
            moves[move_iter++] = n1 + '0';
            moves[move_iter++] = ' ';
        }
        if (n2 <= 8) {
            moves[move_iter++] = num_convert(&c);
            moves[move_iter++] = n2 + '0';
            moves[move_iter++] = ' ';
        }
    }
}

char* valid_moves(char position[]) {
    int C = alpha_convert(&position[0]);
    int N = atoi(&position[1]);

    add_moves(C - 2, N - 1, N + 1);
    add_moves(C - 1, N - 2, N + 2);
    add_moves(C + 1, N - 2, N + 2);
    add_moves(C + 2, N - 1, N + 1);

    moves[move_iter - 1] = '\0';
    move_iter = 0;
    return moves;
 }

int main(int argc, char *args[]) {
    if (argc < 2) {
        fprintf(stderr, "File path not provided. Exiting...\n");
        return 1;
    }

    if (argc > 2) {
        puts("Excessive arguments, only the first will be considered.");
    }

    FILE *file = fopen(args[1], "r");
    if (file == NULL) {
        perror("Error");
        return 1;
    }

    char position[LINE_LENGTH];
    while (fgets(position, LINE_LENGTH, file)) {
        puts(valid_moves(position));
    }

    fclose(file);
}
\$\endgroup\$
13
\$\begingroup\$

Joshua: What's the difference?

Computers sometimes have a hard time to differentiate between things that are apples and oranges to us, some examples are:

  • if this is a game or if this is real
  • thermonuclear war and a game of chess
  • char and int

You have two functions converting from char to int and back:

char num_convert(int *n) {
    for (int i = 0; i < BOARD_LENGTH; i++) {
        if (*n == rows[i]) {
            return cols[i];
        }
    }
}

int alpha_convert(char *c) {
    for (int i = 0; i < BOARD_LENGTH; i++) {
        if (*c == cols[i]) {
            return rows[i];
        }
    }
}

This is not necessary in C, because char and int are kind of the same thing. You can do regular calculations with characters just like you do with integers. Once in character, stay in character.

So when it comes to playing the game of converting between both types, I'd have to say the only winning move is not to play.

the mysterious void add_moves()

I have no idea what this function does.

void add_moves(int c, int n1, int n2) {
    if (c >= 1 && c <= 8) {
        if (n1 >= 1) {
            moves[move_iter++] = num_convert(&c);
            moves[move_iter++] = n1 + '0';
            moves[move_iter++] = ' ';
        }
        if (n2 <= 8) {
            moves[move_iter++] = num_convert(&c);
            moves[move_iter++] = n2 + '0';
            moves[move_iter++] = ' ';
        }
    }
}

Why are there two n but only a single c? What do those values represent? They are apparently boundary checked, too. Then there's this code block that's pretty much duplicated for both n, which is bad.

        if (n1 >= 1) {
            moves[move_iter++] = num_convert(&c);
            moves[move_iter++] = n1 + '0';
            moves[move_iter++] = ' ';
        }

After all, something is somehow added to moves, which justifies the name add_moves(). But it's not immediately clear to me what's going on in that function and I feel like too much is going on.

a hint in char* valid_moves()

This function takes away a bit of the mystery from what add_moves() is doing. As it calls it with different possible moves of the knight.

add_moves(C - 2, N - 1, N + 1);
add_moves(C - 1, N - 2, N + 2);
add_moves(C + 1, N - 2, N + 2);
add_moves(C + 2, N - 1, N + 1);

This is not very intuitive. Why do I only see 4 lines here? The knight can do 8 moves in general. Now it is clear why add_moves() takes two n values as parameters, but only one c.

This distribution of logic doesn't appear to be plausible. It's like some part of the movement is calculated in one place while the other happens later. If the concerns of the functions were more clearly separated, it would be easier to understand them.


I gave it a try myself. Here's how I did it:

Position type

This is all about positions, so let's create a type for that.

typedef struct 
{
    signed char column;
    int row;
}
Position;

We're not in oop land, but we still group data together if it belongs together. This helps a lot when passing it around.

disclaimer: I often see type names like position_t and I absolutely hate that, which is why I'm not using it. Your naming convention may vary.

relative knight moves as positions

Is 5 meters an absolute position or a difference between two positions? It can very well be both! In the same idea, let's create an array of Position that represent the relative movements a knight can perform.

Position allKnightMovesInAlphabeticalOrder[] = 
{
    {-2, -1}, 
    {-2, +1}, 
    {-1, -2}, 
    {-1, +2}, 
    {+1, -2}, 
    {+1, +2}, 
    {+2, -1}, 
    {+2, +1} 
};

#define numberOfKnightMoves 8

As you can see, -2 is a perfectly fine signed char value. 1

If you are uncomfortable reusing the Position type which from its name might suggest to be an absolute position, you can always typedef it to a Move type, which makes the intention more clear.

position check

A handy helper function could solve the sub-problem of whether a certain position is on the board or not.

bool positionIsInChessboard(Position *position)
{
    return 
        position->column >= 'a' &&
        position->column <= 'h' &&
        position->row >= 1 &&
        position->row <= 8;
}

You need to #include <stdbool.h> for bool. If you don't want that, you should be able to use _Bool as a return type.

making a move

Another helper function that simply adds two positions together.

void addTwoPositions(Position *a, Position *b, Position *result)
{
    result->column = a->column + b->column;
    result->row = a->row + b->row;
}

Again, as a Position might represent a relative movement, this starts to make sense I hope. If not, recall how a 2D vector in math might represent a fixed point or the difference between two points. This is the same idea.

putting it all together

#include <stdio.h>
#include <stdbool.h>

typedef struct 
{
    signed char column;
    int row;
}
Position;

Position allKnightMovesInAlphabeticalOrder[] = 
{
    {-2, -1}, 
    {-2, +1}, 
    {-1, -2}, 
    {-1, +2}, 
    {+1, -2}, 
    {+1, +2}, 
    {+2, -1}, 
    {+2, +1} 
};

#define numberOfKnightMoves 8

bool positionIsInChessboard(Position *position)
{
    return 
        position->column >= 'a' &&
        position->column <= 'h' &&
        position->row >= 1 &&
        position->row <= 8;
}

void addTwoPositions(Position *a, Position *b, Position *result)
{
    result->column = a->column + b->column;
    result->row = a->row + b->row;
}

int main ()
{
    Position testPositions[] = 
    {
        {'g', 2},
        {'a', 1},
        {'d', 6},
        {'e', 5},
        {'b', 1}
    };

    int numberOfTestPositions = sizeof(testPositions)/sizeof(Position);

    Position result;

    for(int testPositionIndex = 0; testPositionIndex < numberOfTestPositions; testPositionIndex++)
    {
        printf("%c%d:\t", testPositions[testPositionIndex].column, testPositions[testPositionIndex].row);

        for(int moveIndex = 0; moveIndex < numberOfKnightMoves; moveIndex++)
        {
            addTwoPositions(&testPositions[testPositionIndex], &allKnightMovesInAlphabeticalOrder[moveIndex], &result);

            if(positionIsInChessboard(&result))
            {
                printf("%c%d ", result.column, result.row);
            }
        }

        printf("\r\n");
    }
}

I hard coded the test positions into main() for brevity. the basic idea for every test case is to iterate over all the possible knight moves, perform them via addTwoPositions() and then check the validity of the result with positionIsInChessboard().

I do not build up a buffer as you do in your code simply because that isn't necessary.

Here's what I get as a result in terminal:

$ ./chess 
g2: e1 e3 f4 h4 
a1: b3 c2 
d6: b5 b7 c4 c8 e4 e8 f5 f7 
e5: c4 c6 d3 d7 f3 f7 g4 g6 
b1: a3 c3 d2 

1 thanks @Daniel Jour for pointing out that plain char has an unspecified signedness, which may vary across platforms and compilers.

For me, I get the same output for any of the three versions char, signed char or unsigned char. It's still good practice to use signed char as it makes it more obvious that a Position might be a relative position.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I have much to learn and a fantastic answer to learn from! I'm with you on Position's naming. \$\endgroup\$ – Legato Sep 18 '16 at 14:03
  • \$\begingroup\$ I hope you earn a "Nice Answer" on this one. \$\endgroup\$ – pacmaninbw Sep 18 '16 at 14:08
  • \$\begingroup\$ Wow, what a wealth of useful advice here. This is almost a miniature C tutorial. :) (Okay, not really, but it's still great.) \$\endgroup\$ – Wildcard Sep 18 '16 at 14:51
  • 1
    \$\begingroup\$ One note: char may be unsigned, which will lead to implementation defined behavior (at best) with your negative offsets. Better play safe and use signed char. \$\endgroup\$ – Daniel Jour Sep 18 '16 at 15:22
  • \$\begingroup\$ @DanielJour didn't know that, thanks for the comment. I tried all 3 versions and I get the same result for all of them. I still think it improves the code to explicitly declare it to be a signed char. See edit. \$\endgroup\$ – I'll add comments tomorrow Sep 18 '16 at 15:59
5
\$\begingroup\$

@I'll add comments tomorrow has covered most of the main points, but I'd also suggest that you consider error scenarios. With most programming challenges, you can rely on good input however outside of the challenges you need to start thinking about what happens if the input isn't what's expected.

Consider this function:

char num_convert(int *n) {
    for (int i = 0; i < BOARD_LENGTH; i++) {
        if (*n == rows[i]) {
            return cols[i];
        }
    }
    // What happens here?!?
}

If the target value isn't found in rows before you get to the end of it, then you fall out of the for loop at which point the code will return an unspecified value to the caller (you have a similar issue in alpha_convert).

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Well spotted. I was just compiling with make which just invokes cc (aka gcc) without -Wall (specifically, without -Wreturn-type), so I missed that. \$\endgroup\$ – I'll add comments tomorrow Sep 18 '16 at 14:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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