Programmeringsmetodik: Lösningar till tentamen 2011-11-03

Observera att detta är ett förslag på lösningar. Det finns andra lösningar som också är korrekta. Lösningarna är skrivna i en modernare version av C än vad Visual Studio 2010 klarar av.

1. Uppgift för betyget 3 respektive G

Här kommer tre olika förslag på hur man kan lösa uppgiften.

Först en version som lagrar de unika brädena i en länkad lista. Ladda ner: hitta-unika-braden.c

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

#ifdef _WIN32
    #include <conio.h>
#endif

#define BOARD_SIDE 10

// Ett bräde lagras som en matris av rutor, med 'x', 'o' eller '-'
struct Board {
    char board[BOARD_SIDE][BOARD_SIDE];
};

// De unika brädena lagras i en länkad lista
struct ListLink {
    struct Board board;
    struct ListLink *next;
};

struct ListLink *first_unique_board = NULL;

// Returnerar 1 om de två brädena är lika, annars 0
int equal_boards(struct Board *bp1, struct Board *bp2) {
    int x;
    int y;

    for (x = 0; x < BOARD_SIDE; ++x) {
        for (y = 0; y < BOARD_SIDE; ++y) {
            if (bp1->board[x][y] != bp2->board[x][y])
                return 0;
        }
    }
    return 1;
} // equal_boards

// Returnerar 1 om brädet finns i listan, annars 0
int board_exists(struct Board *bp) {
    struct ListLink *lp = first_unique_board;
    while (lp != NULL) {
        if (equal_boards(bp, &lp->board) == 1)
            return 1;
        lp = lp->next;
    }
    return 0;
} // board_exists

// Lägger in brädet i listan. Vi ska ha kollat först att det inte redan finns!
void save_board(struct Board *bp) {
    struct ListLink *newp = malloc(sizeof(struct ListLink));
    newp->board = *bp;
    newp->next = first_unique_board;
    first_unique_board = newp;
} // save_board

// Returnerar 1 om det gick att läsa ett bräde, 0 vid filslut eller fel
int read_board(FILE *f, struct Board *bp) {
    char word[100 + 1];
    int x;
    int y;

    if (fscanf(f, "%100s", word) != 1 || strcmp(word, "begin") != 0)
        return 0;
    for (x = 0; x < BOARD_SIDE; ++x) {
        for (y = 0; y < BOARD_SIDE; ++y) {
            if (fscanf(f, "%100s", word) != 1)
                return 0;
            else if (strcmp(word, "x") == 0)
                bp->board[x][y] = 'x';
            else if (strcmp(word, "o") == 0)
                bp->board[x][y] = 'o';
            else if (strcmp(word, "-") == 0)
                bp->board[x][y] = '-';
            else
                return 0;
        }
    }
    if (fscanf(f, "%100s", word) != 1 || strcmp(word, "end") != 0)
        return 0;
    return 1;
} // read_board

int main(int argc, char *argv[]) {
    char filename[2000];
    FILE *tsin;
    int nr_boards = 0;
    int nr_unique = 0;
    struct Board board;

    printf("Ange filnamnet: ");
    fgets(filename, sizeof filename, stdin);
    if (filename[strlen(filename) - 1] == '\n')
        filename[strlen(filename) - 1] = '\0';
    tsin = fopen(filename, "r");
    if (tsin == NULL) {
        fprintf(stderr, "Kunde inte läsa filen '%s'\n", filename);
        #ifdef _WIN32
            printf("Tryck en tangent för att avsluta: ");
            _getch();
        #endif
        exit(EXIT_FAILURE);
    }
    while (read_board(tsin, &board) == 1) {
        ++nr_boards;
        if (board_exists(&board) == 0) {
            ++nr_unique;
            save_board(&board);
        }
    }
    fclose(tsin);

    printf("%d bräden, varav %d unika\n", nr_boards, nr_unique);

    #ifdef _WIN32
        printf("Tryck en tangent för att avsluta: ");
        _getch();
    #endif

    return EXIT_SUCCESS;
} // main

Sen en något kortare (och sämre) lösning, som lagrar de unika brädena i en array.

Ladda ner: enklare-hitta-unika-braden.c

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

#ifdef _WIN32
    #include <conio.h>
#endif

#define MAX_LINE_LENGTH 30
#define BOARD_SIDE 10
#define MAX_UNIQUE_BOARDS 1000

// Vi lagrar brädet i form av raderna direkt från filen
struct Board {
    char rows[BOARD_SIDE][MAX_LINE_LENGTH + 1 + 1];
};

// De unika brädena lagras i en array
struct Board unique_boards[MAX_UNIQUE_BOARDS];
int nr_unique_boards = 0;

// Returnerar 1 om de två brädena är lika, annars 0
int equal_boards(struct Board board1, struct Board board2) {
    int i;

    for (i = 0; i < BOARD_SIDE; ++i) {
        if (strcmp(board1.rows[i], board2.rows[i]) != 0)
            return 0;
    }
    return 1;
} // equal_boards

// Returnerar 1 om brädet finns i arrayen, annars 0
int board_exists(struct Board board) {
    int i;

    for (i = 0; i < nr_unique_boards; ++i) {
        if (equal_boards(board, unique_boards[i]) == 1)
            return 1;
    }
    return 0;
} // board_exists

// Lägger in brädet i arrayen. Vi ska ha kollat först att det inte redan finns!
void save_board(struct Board board) {
    unique_boards[nr_unique_boards++] = board;
} // save_board

// Returnerar 1 om det gick att läsa ett bräde, 0 vid filslut eller fel
int read_board(FILE *f, struct Board *boardp) {
    char line[MAX_LINE_LENGTH + 1 + 1];
    int i;

    if (fgets(line, sizeof line, f) == NULL) // Raden med "begin"
        return 0;
    for (i = 0; i < BOARD_SIDE; ++i)
        fgets(boardp->rows[i], sizeof(boardp->rows[i]), f);
    fgets(line, sizeof line, f); // Raden med "end"
    return 1;
} // read_board

int main(int argc, char *argv[]) {
    char filnamn[2000];
    FILE *tsin;
    int antal = 0;
    int antal_unika = 0;
    struct Board board;

    printf("Ange filnamnet: ");
    fgets(filnamn, sizeof filnamn, stdin);
    if (filnamn[strlen(filnamn) - 1] == '\n')
        filnamn[strlen(filnamn) - 1] = '\0';

    tsin = fopen(filnamn, "r");
    while (read_board(tsin, &board) == 1) {
        ++antal;
        if (board_exists(board) == 0) {
            ++antal_unika;
            save_board(board);
        }
    }
    fclose(tsin);

    printf("%d bräden, varav %d unika\n", antal, antal_unika);

    #ifdef _WIN32
        printf("Tryck en tangent för att avsluta: ");
        _getch();
    #endif

    return EXIT_SUCCESS;
} // main

Till sist en version uppdelad i tre moduler: Main, Board och SetOfBoards. Den innehåller filerna Main.c, Board.h, Board.c, SetOfBoards.h och SetOfBoards.c

Ladda ner: Main.c

// Main.c

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "Board.h"
#include "SetOfBoards.h"

#ifdef _WIN32
    #include <conio.h>
#endif


int main(int argc, char *argv[]) {
    char filename[2000];
    FILE *tsin;
    int nr_boards = 0;
    int nr_unique = 0;
    struct Board board;
    struct BoardListLink *first_unique_board = NULL;

    printf("Ange filnamnet: ");
    fgets(filename, sizeof filename, stdin);
    if (filename[strlen(filename) - 1] == '\n')
        filename[strlen(filename) - 1] = '\0';
    tsin = fopen(filename, "r");
    if (tsin == NULL) {
        fprintf(stderr, "Kunde inte läsa filen '%s'\n", filename);
        #ifdef _WIN32
            printf("Tryck en tangent för att avsluta: ");
            _getch();
        #endif
        exit(EXIT_FAILURE);
    }
    while (read_board(tsin, &board) == 1) {
        ++nr_boards;
        if (board_exists(first_unique_board, &board) == 0) {
            ++nr_unique;
            save_board(&first_unique_board, &board);
        }
    }
    fclose(tsin);

    printf("%d bräden, varav %d unika\n", nr_boards, nr_unique);

    #ifdef _WIN32
        printf("Tryck en tangent för att avsluta: ");
        _getch();
    #endif

    return EXIT_SUCCESS;
} // main

Ladda ner: Board.h

// Board.h

#ifndef BOARD_H
#define BOARD_H

#define BOARD_SIDE 10

// Ett bräde lagras som en matris av rutor, med 'x', 'o' eller '-'
struct Board {
    char board[BOARD_SIDE][BOARD_SIDE];
};

// Returnerar 1 om de två brädena är lika, annars 0
extern int equal_boards(struct Board *bp1, struct Board *bp2);

// Returnerar 1 om det gick att läsa ett bräde, 0 vid filslut eller fel
extern int read_board(FILE *f, struct Board *bp);

#endif

Ladda ner: Board.c

// Board.c

#include <stdio.h>
#include <string.h>
#include "Board.h"

// Returnerar 1 om de två brädena är lika, annars 0
int equal_boards(struct Board *bp1, struct Board *bp2) {
    int x;
    int y;

    for (x = 0; x < BOARD_SIDE; ++x) {
        for (y = 0; y < BOARD_SIDE; ++y) {
            if (bp1->board[x][y] != bp2->board[x][y])
                return 0;
        }
    }
    return 1;
} // equal_boards

// Returnerar 1 om det gick att läsa ett bräde, 0 vid filslut eller fel
int read_board(FILE *f, struct Board *bp) {
    char word[100 + 1];
    int x;
    int y;

    if (fscanf(f, "%100s", word) != 1 || strcmp(word, "begin") != 0)
        return 0;
    for (x = 0; x < BOARD_SIDE; ++x) {
        for (y = 0; y < BOARD_SIDE; ++y) {
            if (fscanf(f, "%100s", word) != 1)
                return 0;
            else if (strcmp(word, "x") == 0)
                bp->board[x][y] = 'x';
            else if (strcmp(word, "o") == 0)
                bp->board[x][y] = 'o';
            else if (strcmp(word, "-") == 0)
                bp->board[x][y] = '-';
            else
                return 0;
        }
    }
    if (fscanf(f, "%100s", word) != 1 || strcmp(word, "end") != 0)
        return 0;
    return 1;
} // read_board

Ladda ner: SetOfBoards.h

// SetOfBoards.h

#ifndef SET_OF_BOARDS_H
#define SET_OF_BOARDS_H

#include "Board.h"

// De unika brädena lagras i en länkad lista
struct BoardListLink {
    struct Board board;
    struct BoardListLink *next;
};

// Returnerar 1 om brädet finns i listan, annars 0
extern int board_exists(struct BoardListLink *firstp, struct Board *bp);

// Lägger in brädet i listan. Vi ska ha kollat först att det inte redan finns!
extern void save_board(struct BoardListLink **firstpp, struct Board *bp);

#endif

Ladda ner: SetOfBoards.c

// SetOfBoards.c

#include <stdlib.h>
#include <stdio.h>
#include "Board.h"
#include "SetOfBoards.h"

// Returnerar 1 om brädet finns i listan, annars 0
int board_exists(struct BoardListLink *firstp, struct Board *bp) {
    struct BoardListLink *lp = firstp;
    while (lp != NULL) {
        if (equal_boards(bp, &lp->board) == 1)
            return 1;
        lp = lp->next;
    }
    return 0;
} // board_exists

// Lägger in brädet i listan. Vi ska ha kollat först att det inte redan finns!
void save_board(struct BoardListLink **firstpp, struct Board *bp) {
    struct BoardListLink *newp = malloc(sizeof(struct BoardListLink));
    newp->board = *bp;
    newp->next = *firstpp;
    *firstpp = newp;
} // save_board

2. Uppgift för betyget 4 respektive VG

Ladda ner: hitta-unika-braden-snabbare.c

Programmet tar 5-10 sekunder att köra med exempelfilen braden-1M-843222.txt, som innehåller en miljon bräden.

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

#ifdef _WIN32
    #include <conio.h>
#endif

#define BOARD_SIDE 10
#define HASH_TABLE_SIZE 1000003

// Ett bräde lagras som en matris av rutor, med 'x', 'o' eller '-'
struct Board {
    char board[BOARD_SIDE][BOARD_SIDE];
};

// De unika brädena lagras i en hashtabell
struct ListLink {
    struct Board board;
    struct ListLink *next;
};

struct ListLink *hash_table[HASH_TABLE_SIZE];

// Returnerar 1 om de två brädena är lika, annars 0
int equal_boards(struct Board *bp1, struct Board *bp2) {
    int x;
    int y;

    for (x = 0; x < BOARD_SIDE; ++x) {
        for (y = 0; y < BOARD_SIDE; ++y) {
            if (bp1->board[x][y] != bp2->board[x][y])
                return 0;
        }
    }
    return 1;
} // equal_boards

// Hashfunktionen låtsas att rutorna är en sträng, och använder en känd hashfunktion för strängar
unsigned int hash(struct Board *bp) {
    unsigned int resultat = 5381;
    for (int x = 0; x < BOARD_SIDE; ++x) {
        for (int y = 0; y < BOARD_SIDE; ++y) {
            resultat = resultat * 33 + bp->board[x][y];
        }
    }
    return resultat % HASH_TABLE_SIZE;
} // hash

// Egentligen onödig om hashtabellen inte är lokal i en funktion
void init_table() {
    for (int bucket = 0; bucket < HASH_TABLE_SIZE; ++bucket)
        hash_table[bucket] = NULL;
}

// Returnerar 1 om brädet finns i hashtabellen, annars 0
int board_exists(struct Board *bp) {
    unsigned int bucket = hash(bp);
    struct ListLink *lp = hash_table[bucket];
    while (lp != NULL) {
        if (equal_boards(bp, &lp->board) == 1)
            return 1;
        lp = lp->next;
    }
    return 0;
} // board_exists

// Lägger in brädet i hashtabellen. Vi ska ha kollat först att det inte redan finns!
void save_board(struct Board *bp) {
    unsigned int bucket = hash(bp);
    struct ListLink *newp = malloc(sizeof(struct ListLink));
    newp->board = *bp;
    newp->next = hash_table[bucket];
    hash_table[bucket] = newp;
} // save_board

// Returnerar 1 om det gick att läsa ett bräde, 0 vid filslut eller fel
int read_board(FILE *f, struct Board *bp) {
    char word[100 + 1];
    int x;
    int y;

    if (fscanf(f, "%100s", word) != 1 || strcmp(word, "begin") != 0)
        return 0;
    for (x = 0; x < BOARD_SIDE; ++x) {
        for (y = 0; y < BOARD_SIDE; ++y) {
            if (fscanf(f, "%100s", word) != 1)
                return 0;
            else if (strcmp(word, "x") == 0)
                bp->board[x][y] = 'x';
            else if (strcmp(word, "o") == 0)
                bp->board[x][y] = 'o';
            else if (strcmp(word, "-") == 0)
                bp->board[x][y] = '-';
            else
                return 0;
        }
    }
    if (fscanf(f, "%100s", word) != 1 || strcmp(word, "end") != 0)
        return 0;
    return 1;
} // read_board

int main(int argc, char *argv[]) {
    char filename[2000];
    FILE *tsin;
    int nr_boards = 0;
    int nr_unique = 0;
    struct Board board;

    printf("Ange filnamnet: ");
    fgets(filename, sizeof filename, stdin);
    if (filename[strlen(filename) - 1] == '\n')
        filename[strlen(filename) - 1] = '\0';
    tsin = fopen(filename, "r");
    if (tsin == NULL) {
        fprintf(stderr, "Kunde inte läsa filen '%s'\n", filename);
        #ifdef _WIN32
            printf("Tryck en tangent för att avsluta: ");
            _getch();
        #endif
        exit(EXIT_FAILURE);
    }
    init_table();
    while (read_board(tsin, &board) == 1) {
        ++nr_boards;
        if (board_exists(&board) == 0) {
            ++nr_unique;
            save_board(&board);
        }
    }
    fclose(tsin);

    printf("%d bräden, varav %d unika\n", nr_boards, nr_unique);

    #ifdef _WIN32
        printf("Tryck en tangent för att avsluta: ");
        _getch();
    #endif

    return EXIT_SUCCESS;
} // main

3. Uppgift för betyget 5

Ingen lösning än.

Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), 4 november 2011