sys_prog/chess_paths/chess_paths.c

// vim: set ts=4 sw=4 et tw=80:

/*
 * Assignment 3 - Chess paths
 * Claudio Maggioni
 *
 * No external source was used as parts of code or as an inspiration for the
 * overall algorithm.
 *
 * The flag DEBUG, if defined, activates some debug messages printe on stdout.
 * This is disabled to comply with tests.
 */

#include "chess_paths.h"
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>

#define DEBUG 0

#if DEBUG
char* NAMES[] = { "KING", "QUEEN", "ROOK", "BISHOP", "KNIGHT", "PAWN" };

void print_p_position(struct piece_position* p) {
    printf("%s at row: %u col: %u\n", NAMES[p->piece], p->row, p->column);
}

void print_visited(const struct chessboard* ch, bool* v) {
    for (int r = rows(ch) - 1; r >= 0; r--) {
        for (int c = 0; c < columns(ch); c++) {
            printf("%d", v[columns(ch) * c + r]);
        }
        puts("");
    }
}
#endif

/**
 * Code for visited row/column dictionary. Used in simple_path_len
 */

struct row_list {
    unsigned row;
    unsigned column;
    struct row_list* next;
};

typedef struct row_list* visit_table;

#if DEBUG
unsigned long alloc = 0;
#endif

unsigned long table_total_size(const struct chessboard*);
unsigned long table_hash(const struct chessboard*, unsigned, unsigned);

inline unsigned long table_total_size(const struct chessboard* c) {
    return 1000;
}

inline unsigned long table_hash(const struct chessboard* c, unsigned col,
        unsigned row) {
    return (value_at(c, col, row) ^ (('C'|'a') << 24 | ('r'|'z') << 16 |
                ('a'|'n') << 8 | ('i'|'g'|'a')))
        % table_total_size(c);
}

visit_table* table_new(const struct chessboard* c) {
    unsigned long table_size = table_total_size(c);

#if DEBUG
    alloc += sizeof(struct row_list*) * table_size;
#endif

    return calloc(table_size, sizeof(struct row_list*));
}

void table_visit(const struct chessboard* c, visit_table* visited,
        unsigned column, unsigned row) {

    unsigned long hash = table_hash(c, column, row);
    struct row_list* prev = hash[visited];

#if DEBUG
    alloc += sizeof(struct row_list);
#endif

    hash[visited] = malloc(sizeof(struct row_list));
    assert(hash[visited] != NULL);
    hash[visited]->row = row;
    hash[visited]->column = column;
    hash[visited]->next = prev;
}

bool table_visited(const struct chessboard* c, visit_table* visited,
        unsigned column, unsigned row) {

    unsigned long hash = table_hash(c, column, row);
    for (struct row_list* i = hash[visited]; i != NULL; i = i->next) {
        if (i->row == row && i->column == column) return true;
    }
    return false;
}

void table_destroy(const struct chessboard* c, visit_table* visited) {

    unsigned long table_size = table_total_size(c);
    for (unsigned e = 0; e < table_size; e++) {
        for (struct row_list* i = e[visited], *j; i != NULL;) {
            j = i->next;
            free(i);
            i = j;
        }
    }

#if DEBUG
    printf("alloc = %lu\n", alloc);
    alloc = 0;
#endif

    free(visited);
}

/**
 * Code for search_status struct. Used to keep track of the piece to choose in
 * all *_path_len functions and in piece functions
 */

struct search_status {
    unsigned column;
    unsigned row;
    bool found;

    bool (*better)(struct search_status* s, unsigned col, unsigned row);

    const struct chessboard* chessboard;
    visit_table* table;
};

void search_status_init(struct search_status* s, struct piece_position* p,
        bool (*better)(struct search_status*, unsigned, unsigned),
        const struct chessboard* c, visit_table* table) {
    s->column = p->column;
    s->row = p->row;
    s->found = false;
    s->better = better;
    s->chessboard = c;
    s->table = table;
}

/**
 * Consider compares the value at the given position with the current maximum,
 * if "better" (according to the predicate stored in search_status) then it sets
 * the search_status maximum to the given posiition
 */

void consider(struct search_status* s, unsigned column, unsigned row) {
    const bool b = s->better(s, column, row);

#if DEBUG
    printf("consider c=%u r=%u better=%u\n", column, row, b);
#endif

    if (b) {
        s->found = true;
        s->column = column;
        s->row = row;
    }
}

/**
 * Piece postitions. They "consider" every position which is a legal move for
 * the piece
 */

void pawn_positions(struct search_status* s, struct piece_position* p) {
    if (p->row + 1 < rows(s->chessboard)) {
        consider(s, p->column, p->row + 1);
    }
}

void king_positions(struct search_status* s, struct piece_position* p) {
    unsigned cs = columns(s->chessboard) - 1;
    unsigned rs = rows(s->chessboard) - 1;
    unsigned row = p->row, col = p->column;

    if (row > 0 && col > 0)    consider(s, col - 1, row - 1);
    if (row > 0)               consider(s, col,     row - 1);
    if (row > 0 && col < cs)   consider(s, col + 1, row - 1);
    if (col > 0)               consider(s, col - 1, row);
    if (col < cs)              consider(s, col + 1, row);
    if (row < rs && col > 0)   consider(s, col - 1, row + 1);
    if (row < rs)              consider(s, col,     row + 1);
    if (row < rs && col < cs)  consider(s, col + 1, row + 1);
}

void rook_positions(struct search_status* s, struct piece_position* p) {
    unsigned c_cols = columns(s->chessboard);
    unsigned c_rows = rows(s->chessboard);

    for (unsigned col = 0; col < c_cols; col++) {
        if (col == p->column) continue;
        consider(s, col, p->row);
    }

    for (unsigned row = 0; row < c_rows; row++) {
        if (row == p->row) continue;
        consider(s, p->column, row);
    }
}

void knight_positions(struct search_status* s, struct piece_position* p) {
    unsigned cs = columns(s->chessboard) - 1;
    unsigned rs = rows(s->chessboard) - 1;
    unsigned row = p->row, col = p->column;

    if (row >= 1 && col >= 2)            consider(s, col - 2, row - 1);
    if (row >= 2 && col >= 1)            consider(s, col - 1, row - 2);
    if (row >= 2 && col + 1 <= cs)       consider(s, col + 1, row - 2);
    if (row >= 1 && col + 2 <= cs)       consider(s, col + 2, row - 1);
    if (row + 1 <= rs && col + 2 <= cs)  consider(s, col + 2, row + 1);
    if (row + 2 <= rs && col + 1 <= cs)  consider(s, col + 1, row + 2);
    if (row + 2 <= rs && col >= 1)       consider(s, col - 1, row + 2);
    if (row + 1 <= rs && col >= 2)       consider(s, col - 2, row + 1);
}

void bishop_positions(struct search_status* s, struct piece_position* p) {
    unsigned cs = columns(s->chessboard);
    unsigned rs = rows(s->chessboard);
    unsigned r, c;

    for (r = p->row, c = p->column; r >= 1 && c >= 1; r--, c--) {
        consider(s, c - 1, r - 1);
    }

    for (r = p->row + 1, c = p->column + 1; r < rs && c < cs; r++, c++) {
        consider(s, c, r);
    }

    for (r = p->row, c = p->column + 1; r >= 1 && c < cs; r--, c++) {
        consider(s, c, r - 1);
    }

    for (r = p->row + 1, c = p->column; r < rs && c >= 1; r++, c--) {
        consider(s, c - 1, r);
    }
}

void queen_positions(struct search_status* canotaggio,
        struct piece_position* p) {

    bishop_positions(canotaggio, p);
    rook_positions(canotaggio, p);
}

void consider_positions(struct search_status* s, struct piece_position* p) {
    switch (p->piece) {
        case PAWN: pawn_positions(s, p); break;
        case KING: king_positions(s, p); break;
        case ROOK: rook_positions(s, p); break;
        case KNIGHT: knight_positions(s, p); break;
        case BISHOP: bishop_positions(s, p); break;
        case QUEEN: queen_positions(s, p); break;
    }
}

unsigned int path_len(const struct chessboard* c,
        struct piece_position* p,
        bool (*better)(struct search_status*, unsigned, unsigned),
        visit_table* table) {

    unsigned int hops = 0;

#if DEBUG
    printf("board r=%u c=%u\n", rows(c), columns(c));
#endif

    struct search_status status;
    search_status_init(&status, p, better, c, table);

    while (true) {
        status.found = false;
        consider_positions(&status, p);

#if DEBUG
        printf("consideration c=%u r=%u\n", status.column, status.row);
        print_p_position(p);
#endif

        if (status.column == p->column && status.row == p->row) {
            break;
        }

        p->column = status.column;
        p->row = status.row;

        if (status.table != NULL) {
            table_visit(c, table, p->column, p->row);
        }

#if DEBUG
        print_p_position(p);
#endif

        hops++;
    }

    return hops;
}


bool better_inc(struct search_status* s, unsigned column, unsigned row) {
    return value_at(s->chessboard, column, row) >
        value_at(s->chessboard, s->column, s->row);
}

bool better_dec(struct search_status* s, unsigned column, unsigned row) {
    return value_at(s->chessboard, column, row) <
        value_at(s->chessboard, s->column, s->row);
}

bool better_simple(struct search_status* s, unsigned column, unsigned row) {
    return !table_visited(s->chessboard, s->table, column, row) &&
        (!s->found || value_at(s->chessboard, column, row) >
         value_at(s->chessboard, s->column, s->row));
}

unsigned int increasing_path_len(const struct chessboard* c,
        struct piece_position* p) {
    return path_len(c, p, better_inc, NULL);
}

unsigned int decreasing_path_len(const struct chessboard* c,
        struct piece_position* p) {
    return path_len(c, p, better_dec, NULL);
}

unsigned int simple_path_len(const struct chessboard* c,
        struct piece_position* p) {
    visit_table* v = table_new(c);
    table_visit(c, v, p->column, p->row);

    unsigned int len = path_len(c, p, better_simple, v);

    table_destroy(c, v);
    return len;
}