ant.c

Jonas Altrock ew20b126@technikum-wien.at

To overview.

The whole source file ant.c.

/* compile with `clang -std=c99 -Wall -o ant ant.c` */

Include C-libraries for input/output, allocation of memory, and the bool type.

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

Task

In this exercise we want to simulate Langton’s ant. Langton’s ant moves on a board divided in colored squares (similar to a chessboard). In our case this surface consists of 10x10 squares. Every square on this field is initially colored white (represented by a single dot.). Langton’s ant is located on a square on this board and it is facing west (left).

One step of the ant consists of the following procedure:

• First, the ant checks the color of the square on which it currently sits.
• If the square is white (.) it turns right (i.e., if it was facing west/left, it is now facing north/up).
• It then leaves its pheromones by flipping the color of the square, i.e., the square’s color changes to black (represented by #).
• It then advances one step into the current direction.
• If the square is black (#), it turns left (i.e., if it was facing south, it is now facing east/right), flips the color of the square (which hence becomes white) and advances by one step.
• If the ant leaves the board it dies.

Write a program that reads how many steps the ant should make, then reads an initial position (first x - horizontal, then y - vertical position) where in the best tradition of array indices 0 represents the left/topmost coordinate.

Your program should show the state of the surface after any one of the following conditions is satisfied:

• Either the ant has completed the entered number of steps, or
• It fell off the board and died.

If the ant is still on the board and hence alive its position should be marked by

• a if it is on a white square or
• A if it is on a black square.

If the ant died because it fell of the board before completing all steps there is no ant on the board.

In your solution you should store the position and the direction of the ant in a struct. For the direction you can pick any data structure.

Solution

First we define all our data structures and function prototypes.

/* */

A square of the board can be either white or black.

typedef enum square {
    white, // = 0
    black
} square_t;

A board has width, height, and its array of width*height squares.

typedef struct board {
    int width;
    int height;
    square_t *squares;
} board_t;

The orientation of the ant can be west, north, east, or south.

typedef enum direction {
    west, // = 0
    north,
    east,
    south
} direction_t;

The ant has a x and y coordinates, an orientation, and is alive or not.

typedef struct ant {
    int x, y;
    direction_t orientation;
    bool alive;
} ant_t;

We split all the things that happen into functions that have sensible names. They take pointers to the structs as parameters to make it easier to modify the state of the board and ant.

/* */

Print a board with an ant on it.

void print_board(board_t *b, ant_t *a);

Convert a single square of the board to a printable character.

char print_square(square_t s, bool has_ant);

Get the square of the board at coordinates x, y.

square_t get_square(board_t *b, int x, int y);

Set the square of the board at coordinates x, y, and return the old square.

square_t set_square(board_t *b, int x, int y, square_t s);

Flip square’s color, returns the new square.

square_t flip_square(square_t s);

Check whether the ant is still on the board.

bool is_on_board(board_t *b, ant_t *a);

Do one step of the ant.

void ant_step(board_t *b, ant_t *a);

Do a left turn and return the new direction.

direction_t ant_turn_left(ant_t *a);

Do a right turn and return the new direction.

direction_t ant_turn_right(ant_t *a);

Move the ant one square forward in its current direction.

void ant_move(ant_t *a);

main()

int main() {

The board, squares, and ant are allocated on the stack, local to main(). This way we don’t have to free() the memory at the end of the function.

Unfortunately, the syntax to statically initialize an array of things is to write all its values between {}. We don’t want to do that for 100 values, so we split the declaration of the board in two parts. The { 0 } initializes all array elements to 0, which is incidentally the white state of a square.

The syntax {.field = x} allows us to initialize a struct and its fields at the same time. To turn it into a pointer to the struct, we take the address with &, but the compiler cannot infer the correct pointer type if we use the static initialization. Thus we cast the struct value to the correct type with (type_t) and take the address of that.

    square_t squares[10][10] = { 0 };
    board_t *board = &(board_t){
        .squares = (square_t *) &squares,
        .width = 10,
        .height = 10
    };
    ant_t *ant = &(ant_t){
        .alive = true,
        .x = 0, .y = 0,
        .orientation = west
    };

Keep track of how many steps have to be made and how many the ant took already.

    int steps_total;
    int steps = 0;

First read in how many turns/steps to run the simulation.

    printf("Enter number of turns: ");
    scanf("%i", &steps_total);

Next read in the initial coordinates of the ant.

    printf("Enter start position: ");
    scanf("%i %i", &ant->x, &ant->y);

As long as the maximum of steps has not been reached and the ant is still alive, do one step of the simulation.

    while (steps < steps_total && ant->alive) {
        ant_step(board, ant);
        steps += 1;
    }

Finally, print out the board.

    print_board(board, ant);

    return 0;
}

ant_step()

One step of the ant consists of the following procedure:

void ant_step(board_t *board, ant_t *ant) {

First, the ant checks the color of the square on which it currently sits.

    square_t current = get_square(board, ant->x, ant->y);

If the square is white

    if (current == white) {

it turns right,

        ant_turn_right(ant);
    }

If the square is black

    if (current == black) {

it turns left.

        ant_turn_left(ant);
    }

The ant then flips the color of the square

    set_square(board, ant->x, ant->y, flip_square(current));

and advances by one step.

    ant_move(ant);

If the ant leaves the board it dies.

    if (!is_on_board(board, ant)) {
        ant->alive = false;
    }
}

ant_turn_left()

Reminder: the “result” of an assignment a = x is the assigned value x. We can use this to return the new direction in one go.

direction_t ant_turn_left(ant_t *a) {
    if (a->orientation == west) return a->orientation = south;
    if (a->orientation == north) return a->orientation = west;
    if (a->orientation == east) return a->orientation = north;
    return a->orientation = east;
}

ant_turn_right()

direction_t ant_turn_right(ant_t *a) {
    if (a->orientation == west) return a->orientation = north;
    if (a->orientation == north) return a->orientation = east;
    if (a->orientation == east) return a->orientation = south;
    return a->orientation = west;
}

ant_move()

Moving the ant forward depends on the direction the ant is facing. The coordinates are traditionally x for the horizontal component and y for the vertical component, with positive values being right and down respectively.

void ant_move(ant_t *a) {
    if (a->orientation == west) a->x -= 1;
    if (a->orientation == north) a->y -= 1;
    if (a->orientation == east) a->x += 1;
    if (a->orientation == south) a->y += 1;
}

is_on_board()

The board has the top-left square at (0, 0) and the bottom-right square at (width - 1, height - 1). The ant is alive, if its coordinates are not outside of that rectangle.

bool is_on_board(board_t *board, ant_t *ant) {
    return !(ant->x < 0 || ant->x >= board->width ||
             ant->y < 0 || ant->y >= board->height);
}

flip_square()

If a square is white, turn it black. Turn it white otherwise.

square_t flip_square(square_t s) {
    if (s == white) return black;
    return white;
}

print_square

Turn a square into its printed representation.

char print_square(square_t square, bool has_ant) {
    if (square == white && has_ant) return 'a';
    if (square == black && has_ant) return 'A';
    if (square == black) return '#';
    return '.';
}

get_square

Get the square of the board at the coordinates (x, y). The field is width * height squares, which we have to address linearly.

square_t get_square(board_t *b, int x, int y) {
    return b->squares[b->width * y + x];
}

set_square

Set the square on the board at coordinates (x, y). Returning the old value is not strictly necessary here, but is a useful habit to train early.

square_t set_square(board_t *b, int x, int y, square_t s) {
    square_t old = b->squares[b->width * y + x];
    b->squares[b->width * y + x] = s;
    return old;
}

print_board

Print the board on stdout. This function creates a dynamic memory allocation for one big string and then fills the string with the board state. Alternatively, one could call printf for each square separately, but calling a function that performs a (relatively) expensive operation many times instead of once takes more time. The difference for 100 calls would be negligible here, as this is not an exercise where performance is the the focus.

void print_board(board_t *board, ant_t *ant) {

Make space for the board lines, each with a newline at the end.

    int line_length = board->width + 1;
    char *printed = calloc(line_length * board->height + 1, sizeof(char));

Iterate over the two-dimensional squares array.

    for (int y = 0; y < board->height; y++) {
        for (int x = 0; x < board->width; x++) {

Print square: look up the color and check if the ant sits here.

            printed[y * line_length + x] = print_square(
                get_square(board, x, y),
                ant->x == x && ant->y == y
            );
        }
        printed[y * line_length + board->width] = '\n';
    }

Print the string representation of the board and free the dynamic memory.

    printf("%s", printed);
    free(printed);
}