Objectives

• creating functions
• creating a multi-file C program
• manipulating arrays
• using a while loop for repetition
• input and output of numerical values

Preparation

Getting Started

Create a new directory for this lab called lab05 by typing:

mkdir lab05

cd lab05

Farnarkle

The standard exercises for this lab are to write functions which together form a program which allow a user to play Farnarkle.

The challenge exercises are to write a program which itself plays Farnarkle.

Farnarkle is thought to have been invented in Iceland during the Little Ice Age. It is played with numbered tiles, originally made from sections of Narwhal tusks. Each tile is inscribed with a single postive integer. Traditionally the integers on the tiles are from the range 1..8 (the number 8 is significant in Norse mythology).

In modern Farnarkle variants the integers on the tiles may be from the range 1..10, 1..12, or another range.

Farnarkle starts with with the Arkle Master choosing a hidden sequence of tiles. Traditionally this sequence is of 4 tiles, but there are modern variants with 5 or 8 tiles in this sequence.

The player then attempts to guess the hidden sequence in a series of turns. Each turn they lay out a sequence of tiles. The Arkle Master then gives them information about how well their sequence of tiles matches the hidden sequence of tiles.

This information is given as two integers: the number of Arkles and the number of Farnarkles.

A tile is counted as an Farnarkle if it has the same number as the tile in the same position in the hidden sequence.

A tile is counted as an Arkle if it has the same number as a tile in another position in the hidden sequence.

A tile that is counted as a Farnarkle is not counted in an Arkle.

A tile can only be counted once in an Arkle.

The scoring of this example Farnarkle game should clarify the definition of Farnarkles and Arkles.

Note: the game is complete when the player guess the hidden sequence.

Exercise: Farnarkle Input/Output

First, create a file named farnarkle.h with these contents:

#define N_TILES 4
#define MAX_TILE 8

int read_tiles(int tiles[N_TILES]);
void print_tiles(int tiles[N_TILES]);

Here is some code to get you started:

#include <stdio.h>
#include "farnarkle.h"

// read N_TILES tiles into array tiles
// return 1 if successful, 0 otherwise
int read_tiles(int tiles[N_TILES]) {
    return 0; // replace with your code
}

// print tiles on a single line
void print_tiles(int tiles[N_TILES]) {
    // replace with your code
}

Your code should use the constant N_TILES for the number of tiles in the sequence.

Your code should use the constant MAX_TILE for the largest number that may appear on a tile.

Your code should work if the constants N_TILES or MAX_TILE are changed.

Do not add a main function to farnarkle_io.c; instead create a separate file io_test.c containing these contents:

#include <stdio.h>
#include "farnarkle.h"

int main(void) {
    int tiles[N_TILES];

    printf("Enter sequence: ");
    if (read_tiles(tiles) == 1) {
        printf("Sequence read was: ");
        print_tiles(tiles);
    } else {
        printf("Could not read tiles\n");
    }
}

dcc farnarkle_io.c io_test.c -o io_test
./io_test
Enter sequence: 4 2 7 7
Sequence read was: 4 2 7 7
./io_test
Enter sequence: 1 2 three four
Could not read tiles

 ~cs1511/bin/autotest lab05 farnarkle_io.c

#include <stdio.h>
#include "farnarkle.h"

// read N_TILES tiles into array tiles
// return 1 if successful, 0 otherwise
int read_tiles(int tiles[N_TILES]) {
    int i;

    i = 0;
    while (i < N_TILES) {
        if (scanf("%d", &tiles[i]) != 1) {
            return 0;
        }
        if (tiles[i] < 1 || tiles[i] > MAX_TILE) {
            return 0;
        }
        i = i + 1;
    }
    return 1;
}

// print tiles on a single line
void print_tiles(int tiles[N_TILES]) {
    int i;

    i = 0;
    while (i < N_TILES) {
        printf("%d", tiles[i]);
        if (i < N_TILES - 1) {
            printf(" ");
        }
        i = i + 1;
    }
    printf("\n");
}

Exercise: Counting Farnarkles

Note: it doesn't matter which sequence is the hidden sequence and which is the guess.

First, add this prototype to farnarkle.h

int count_farnarkles(int sequence1[N_TILES], int sequence2[N_TILES]);

Here is some code to get you started:

#include <stdio.h>
#include "farnarkle.h"

// return number of farnarkles
int count_farnarkles(int sequence1[N_TILES], int sequence2[N_TILES]) {
    return 42; // replace with your code
}

#include <stdio.h>
#include "farnarkle.h"

int main(void) {
    int hidden_sequence[N_TILES];
    int guess[N_TILES];

    printf("Enter hidden sequence: ");
    if (read_tiles(hidden_sequence) != 1) {
        printf("Could not read hidden sequence\n");
        return 1;
    }
    printf("Enter guess: ");
    if (read_tiles(guess) != 1) {
        printf("Could not read guess\n");
        return 1;
    }
    printf("%d farnarkles\n", count_farnarkles(hidden_sequence, guess));

    return 0;
}

dcc farnarkle_io.c count_farnarkles.c count_test.c -o count_test
./
Enter hidden sequence: 6 3 6 1
Enter guess: 1 2 3 4
0 farnarkles
./count_test
Enter hidden sequence: 6 3 6 1
Enter guess: 6 1 1 1
2 farnarkles

 ~cs1511/bin/autotest lab05 count_farnarkles.c

#include <stdio.h>
#include "farnarkle.h"

// return number of farnarkles
int count_farnarkles(int sequence1[N_TILES], int sequence2[N_TILES]) {
    int i, n_farnarkles;

    n_farnarkles = 0;
    i = 0;
    while(i < N_TILES) {
        if (sequence1[i] == sequence2[i]) {
            n_farnarkles = n_farnarkles + 1;
        }
        i = i + 1;
    }
    return n_farnarkles;
}

Exercise: Counting Arkles

Note: it doesn't matter which sequence is the hidden sequence and which is the guess.

First, add this line to farnarkle.h

int count_arkles(int sequence1[N_TILES], int sequence2[N_TILES]);

Here is some code to get you started:

#include <stdio.h>
#include "farnarkle.h"

// return number of arkles
int count_arkles(int sequence1[N_TILES], int sequence2[N_TILES]) {
        return 42; // replace with your code
}

dcc farnarkle_io.c count_farnarkles.c count_arkles.c count_test.c -o count_test
./count_test
Enter hidden sequence: 6 3 6 1
Enter guess: 1 2 3 4
0 farnarkles
2 arkles
./count_test
Enter hidden sequence: 6 3 6 1
Enter guess: 1 3 4 5
1 farnarkles
1 arkles

 ~cs1511/bin/autotest lab05 count_arkles.c

#include <stdio.h>
#include "farnarkle.h"

// return number of arkles
int count_arkles(int sequence1[N_TILES], int sequence2[N_TILES]) {
    int i, j, n_arkles;
    int tile_used1[N_TILES] = {0};
    int tile_used2[N_TILES] = {0};

    // note tiles used in a farnarkle
    i = 0;
    while (i < N_TILES) {
        if (sequence1[i] == sequence2[i]) {
            tile_used1[i] = 1;
            tile_used2[i] = 1;
        }
        i = i + 1;
    }
    n_arkles = 0;
    i = 0;
    while (i < N_TILES) {
        j = 0;
        while (j < N_TILES) {

            // if the tiles in positions i and j are an arnakle
            // and the tiles have not been used in an arkle or farnarkle

            if ((sequence1[i] == sequence2[j]) && (tile_used1[i] == 0) && (tile_used2[j] == 0)) {
                n_arkles = n_arkles + 1;
                tile_used1[i] = 1;
                tile_used2[j] = 1;
            }
            j = j + 1;
        }
        i = i + 1;
    }
    return n_arkles;
}

Exercise: Playing Farnarkle

Write a function create_random_tiles which create a pseudo-random sequence of tiles.

First, add this prototype to farnarkle.h

void create_random_tiles(int tiles[N_TILES]);

#include <stdlib.h>
#include <time.h>
#include "farnarkle.h"

// set tiles to pseudo-random values
void create_random_tiles(int tiles[N_TILES]) {
    int i;

    // seed (initialize) pseudo-random number generate with current time in seconds
    srand(time(NULL));

    i = 0;
    while (i < N_TILES) {
        // rand() returns a pseudo-random integer in ranger 0 to RAND_MAX inclusive
        // convert to an integer in the range 1..MAX_TILE_template
        tiles[i] = rand() % MAX_TILE + 1;
        i = i + 1;
    }
}

Here is some code to get you started:

#include <stdio.h>
#include "farnarkle.h"

int main(void) {
    int hidden_sequence[N_TILES];

    create_random_tiles(hidden_sequence);
    // put your code here
}

Match the behaviour shown in this example::

dcc farnarkle_io.c count_farnarkles.c count_arkles.c create_random_tiles.c play_farnarkle.c -o play_farnarkle
./play_farnarkle
Enter guess for turn 1: 2 8 6 4
0 farnarkles 1 arkles
Enter guess for turn 2: 7 5 3 1
1 farnarkles 1 arkles
Enter guess for turn 3: 4 4 5 5
1 farnarkles 2 arkles
Enter guess for turn 4: 5 5 5 5
2 farnarkles 0 arkles
Enter guess for turn 5: 8 5 4 5
3 farnarkles 0 arkles
Enter guess for turn 6: 3 5 4 5
4 farnarkles 0 arkles
You win

 ~cs1511/bin/autotest lab05 play_farnarkle.c

#include <stdio.h>
#include "farnarkle.h"

int main(void) {
    int hidden_sequence[N_TILES];
    int guess[N_TILES];
    int n_farnarkles, n_arkles, turn;
    create_random_tiles(hidden_sequence);
    turn = 1;
    while (1) {
        printf("Enter guess for turn %d: ", turn);
        if (read_tiles(guess) != 1) {
            printf("Could not read guess\n");
            return 1;
        }
        n_farnarkles = count_farnarkles(hidden_sequence, guess);
        n_arkles = count_arkles(hidden_sequence, guess);
        printf("%d farnarkles %d arkles\n", n_farnarkles, n_arkles);
        if (n_farnarkles == N_TILES) {
            printf("You win\n");
            return 0;
        }
        turn = turn + 1;
    }
}

Challenge Exercise: A Farnarkle Player

First, add these lines to farnarkle.h

#define MAX_TURNS 100

void farnarkle_player(int turn, int previous_guesses[MAX_TURNS][N_TILES], int farnarkles[MAX_TURNS], int arkles[MAX_TURNS], int guess[N_TILES]);

Here is some code to get you started:

#include <stdio.h>
#include "farnarkle.h"

// an automated farnarkle_player
// given all previous guesses and their farnarkles and arkle counts
// make a new guess
//
// inputs:
// turn - which turn this is
// previous_guesses contains the turn - 1 previous_guesses
// farnarkles[i] contains the number of farnarkles for previous_guess[i]
// arkles[i] contains the number of arkles for previous_guess[i]
//
// output:
// guess - the next guess

void farnarkle_player(int turn, int previous_guesses[MAX_TURNS][N_TILES], int farnarkles[MAX_TURNS], int arkles[MAX_TURNS], int guess[N_TILES]) {
    // put your code here
}

Don't include a main function in farnarkle_player.c instead create a file player_test.c with a suitable main function to test your farnarkle_player function. For example:

dcc farnarkle_io.c count_farnarkles.c count_arkles.c create_random_tiles.c farnarkle_player.c player_test.c -o player_test
./player_test
Hidden guess is: 3 5 4 5
Player guess for turn 1: 2 8 6 4
0 farnarkles 1 arkles
Player guess for turn 2: 7 5 3 1
1 farnarkles 1 arkles
Player guess for turn 3: 4 4 5 5
1 farnarkles 2 arkles
Player guess for turn 4: 5 5 5 5
2 farnarkles 0 arkles
Player guess for turn 5: 8 5 4 5
3 farnarkles 0 arkles
Player guess for turn 6: 3 5 4 5
4 farnarkles 0 arkles
Player took 6 turns to guess code.

It provides inputs such that the hidden tiles can be inferred from the previous guesses. In other words, only one guess is consistent with the farnarkles and arkles scores for previous guesses.

 ~cs1511/bin/autotest lab05 count_farnarkles.c count_arkles.c farnarkle_player.c

A farnarkle player tournament will be announced on the class web page at the end of the week.

Please include a comment in your farnarkle_player.c specifying the zids of your lab pair in EXACTLY this format:

// lab pair: z1234567  z5555555

#include <stdio.h>
#include "farnarkle.h"

// naive stragey
// count up integers 0..MAX_TILE^N_TILES converting each int to a guess
// return first guess which fits farnarkles & arkles for all previous guesses
// smarter strategy would partition search space

void farnarkle_player(int turn, int previous_guesses[MAX_TURNS][N_TILES], int farnarkles[MAX_TURNS], int arkles[MAX_TURNS], int guess[N_TILES]) {
    int guess_as_int, i, g, previous_turn, matches_previous_guesses;

    guess_as_int = 0;
    matches_previous_guesses = 0;
    while (matches_previous_guesses == 0) {
        // convert int to tiles
        i = 0;
        g = guess_as_int;
        while (i < N_TILES) {
            guess[i] = g % MAX_TILE + 1;
            g = g / MAX_TILE;
            i = i + 1;
        }
        if (g > 0) {
            printf("error: no possible guess found\n");            // should not be reached
            return;
        }
        previous_turn = 0;
        matches_previous_guesses = 1;
        while (previous_turn < turn - 1 && matches_previous_guesses) {
            if (count_farnarkles(guess, previous_guesses[previous_turn]) != farnarkles[previous_turn] ||
                count_arkles(guess, previous_guesses[previous_turn]) != arkles[previous_turn]) {
                matches_previous_guesses = 0;
            }
            previous_turn = previous_turn + 1;
        }
        guess_as_int = guess_as_int + 1;
    }
}

Challenge Exercise: Optimal Farnarkle

Prove that your farnarkle player is optimal.

If you can not construct a proof and/or an optimal player, construct a logical argument as to why your player is close to optimal.

Submission/Assessment

give cs1511 lab05 farnarkle_io.c count_farnarkles.c count_arkles.c play_farnarkle.c farnarkle_player.c

If you are working at home, you may find it more convenient to upload your work via give's web interface.

Remember the lab assessment guidelines - if you don't finish the exercises you can finish them in your own time, submit them by Monday 11:00am using give and ask your tutor to assess them at the start of the following lab.

Either or both members of a programming pair can submit the work (make sure each program lists both of you as authors in the header comment).