COMP1511 17s1 Introduction to Programming

Objectives

In this Lab, you will practice:

Preparation

Before the lab you should re-read the relevant lecture slides and their accompanying examples. You should also have read the lab assessment guidelines.

Getting Started

One member of your programming pair should login and run the following commands inside a Linux terminal

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

mkdir lab05
Change to this directory by typing:
cd lab05

Farnarkle

This lab revolves around the Scandinavian game of Farnarkle, which you will have discussed in the tutorial.

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.

Hidden Sequence4 2 7 7
Turn GuessFarnarklesArkles
11 2 3 411
23 5 5 800
34 3 2 111
47 7 7 720
57 6 5 402
67 7 4 204
74 2 7 740

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

Exercise: Farnarkle Input/Output

Write a function read_tiles which reads a sequence of tiles with scanf, and a function print_tiles which prints a sequence of tiles with printf.

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]);
Create a file named farnarkle_io.c which includes farnarkle.h and defines read_tiles and print_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");
    }
}

Compile farnarkle_io.c with io_test.c to test your functions.
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
As usual, autotest is available to help you test farnarkle_io.c.
 ~cs1511/bin/autotest lab05 farnarkle_io.c
Sample solution for 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

Write a function count_farnarkles which, given two tile sequences, counts the number of 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]);
Create a file named count_farnarkles.c which includes farnarkle.h and defines count_farnarkles.

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
}

Do not add a main function to count_farnarkle.c; instead create a separate file count_test.c containing these contents:
#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;
}

Compile count_farnarkles.c with count_test.c and farnarkle_io.c to test your count_farnarkles function.
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
As usual autotest is available to help you test count_farnarkles.c.
 ~cs1511/bin/autotest lab05 count_farnarkles.c
Sample solution for 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

Write a function count_arkles which, given two tile sequences, counts the number of 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]);
Create a file named count_arkles.c which includes farnarkle.h and defines count_arkles

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
}

Do not add a main function to count_arkles.c instead modify count_test.c from the last question to also call count_arkles Compile count_arkles.c with count_farnarkles.c, count_test.c and farnarkle_io.c and to test your count_arkles function.
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
As usual autotest is available to help you test count_arkles.c.
 ~cs1511/bin/autotest lab05 count_arkles.c
Hint: don't change the array elements in sequence1 or sequence2 when you are counting arkles - the contents of those arrays may be needed after your function returns.

Sample solution for 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

You will have discussed creation of pseudo-random numbers in C during the tutorial.

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]);
And create a file named create_random_tiles.c with these contents:
#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;
    }
}

Now create a file named play_farnarkle.c with a main function that uses the create_random_tiles function to create the hiddent tiles and then allows a user to play the game of Farnakle.

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
}

Compile play_farnarkle.c with count_arkles.c count_farnarkles.c create_random_tiles.c and farnarkle_io.c to test your main function.

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
As usual autotest is available to help you test play_farnarkle.c.
 ~cs1511/bin/autotest lab05 play_farnarkle.c
Note the autotest depends on you using a function named create_random_tiles to create the guess (it replaces this with a non-random function).
Sample solution for 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

Write a function farnarkle_player which plays Farnarkle.

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]);
Now create a file named farnarkle_player.c which defines farnarkle_player

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
}

Your farnarkle_player only makes a single guess. It is called each time a guess needs to be made - and it is given information about all previous guesses.

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.
A simple autotest is available to check your farnarkle player.

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
Sample solution for farnarkle_player.c
#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

Make your farnarkle player optimal - make it take, on average, the smallest number of turns possible to guess a code.

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

When you are satisfied with your work, ask your tutor to assess it. You also need to submit your work electronically by typing (run this command in the lab05 directory):
give cs1511 lab05 farnarkle_io.c count_farnarkles.c count_arkles.c play_farnarkle.c farnarkle_player.c
Submit the challenge exercises only if you attempt them.

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).