gistfile1.c

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

#define found UINT_MAX-1
#define notfnd UINT_MAX

#define _DEBUG
#undef  _DEBUG

typedef enum {FALSE = 0, TRUE = -1} BOOL;

struct Node
{
    size_t*         board;
    struct Node**   childs;
    size_t          nchild;
    size_t          hash;
    size_t          cost;
} ;

typedef struct Node Node_t;



size_t  g_SZ,
        g_SZ2,
        g_f,
        g_dbgNode,
        g_dbgIter,
        g_result;

Node_t* g_atree,
      * g_start,
      * g_end;


size_t  (*fpH)(const Node_t*, const Node_t*);

size_t  taxicab     (const Node_t* n, const Node_t* e);
size_t  ham         (const Node_t* n, const Node_t* e);
size_t  mixit       (const Node_t* n, const Node_t* e);


void    init        (const char* fname);
void    do_file     (const char* inf, const char* outf);

Node_t* alnode      (void);
void    delnode     (Node_t* node);
Node_t* mktree      (const Node_t* root);
void    deltree     (Node_t* root);
BOOL    chkdup      (const Node_t* r, const size_t h);
void    expand      (Node_t* node);
void    cpyb        (Node_t* to, const Node_t* from);
BOOL    cmpnode     (const Node_t* a, const Node_t* b);

size_t  ida_star    (const Node_t* root, const Node_t* goal);
size_t  dfs_contour (Node_t* n, const size_t g, const size_t b);
size_t  b_row       (const size_t pos);
size_t  b_col       (const size_t pos);
int     idxOf       (const size_t* b, const size_t c);
void    swap        (size_t* to, size_t* from);
BOOL    valid_move  (const int x, const int y);
BOOL    is_goal     (const Node_t* n);

size_t  hash_djb2   (const size_t* b, const size_t l);

void    start_timer (void);
void    stop_timer  (void);
size_t  get_time_taken_ms(void);
float   get_time_taken_sec(void);

void    ndump       (Node_t* n);

int
main(void)
{
    fpH = &taxicab;
    //fpH = &ham;
    //fpH = &mixit;

    do_file("npdata\\input1.txt", "npdata\\o1.txt");
    do_file("npdata\\input2.txt", "npdata\\o2.txt");
    do_file("npdata\\input3.txt", "npdata\\o3.txt");
    do_file("npdata\\input4.txt", "npdata\\o4.txt");

    return 0;
}

void
do_file(const char* inf, const char* outf)
{
    init(inf);

    g_dbgIter = 0;

    start_timer();
    ida_star(g_start, g_end);
    stop_timer();

    printf("\n %s took %u ms", inf, get_time_taken_ms());


    FILE* ofp;
    if((ofp = fopen(outf, "w")) == 0)
    {
        printf("\nCouldn't open file. result = %d\n", g_result);
    }
    else
    {
        fprintf(ofp, "result = %d", g_result);
        fclose(ofp);
    }

    delnode(g_start);
    delnode(g_end);
}

void
init(const char* fname)
{
    FILE* fp;

    if((fp = fopen(fname, "r")) == 0)
        return;

    char* p;
    char buf[64];

    fgets(buf, 64, fp);
    g_SZ = strtol(buf, &p, 10);
    g_SZ2 = g_SZ * g_SZ;

    g_start = alnode();
    g_end   = alnode();

    int i, j;
    for(i = 0; i < g_SZ; i++)
    {
        size_t n;

        memset(buf, 0, 64);
        fgets(buf, 64, fp);
        p = buf;
        for(j = 0; j < g_SZ; j++)
        {
            n = strtol(p, &p, 10);
            g_start->board[j + i * g_SZ] = n;
        }
    }

    for(i = 0; i < g_SZ; i++)
    {
        size_t n;

        memset(buf, 0, 64);
        fgets(buf, 64, fp);
        p = buf;
        for(j = 0; j < g_SZ; j++)
        {
            n = strtol(p, &p, 10);
            g_end->board[j + i * g_SZ] = n;
        }
    }

    g_start->hash   = hash_djb2(g_start->board, g_SZ2);
    g_end->hash     = hash_djb2(g_end->board, g_SZ2);

    ndump(g_start);
    ndump(g_end);
    fclose(fp);
}

Node_t*
alnode(void)
{
    Node_t* node;

    node            = malloc(sizeof(Node_t));
    node->board     = malloc(sizeof(*node->board) * g_SZ2);
    node->childs    = NULL;
    node->nchild    = 0;
    node->hash      = 0;
    node->cost      = 0;

    return node;
}

void
delnode(Node_t* node)
{
    free(node->board);
    free(node->childs);
    free(node);
}

Node_t*
mktree(const Node_t* root)
{
    Node_t* node = alnode();

    cpyb(node, root);
    node->hash = root->hash;

    return node;
}

void
deltree(Node_t* root)
{
    if(root->nchild > 0)
    {
        size_t i = 0;
        for(; i < root->nchild; i++)
            deltree(root->childs[i]);
    }
    delnode(root);
}

BOOL
chkdup(const Node_t* r, const size_t h)
{
    if(r->hash == h)
        return TRUE;

    if(r->nchild > 0)
    {
        size_t i = 0;
        for(; i < r->nchild; i++)
        {
            chkdup(r->childs[i], h);
        }
    }

    return FALSE;
}

void
expand(Node_t* node)
{
    size_t zx, zy, idx;
    size_t c = 0;

    size_t zdx = idxOf(node->board, 0);
    Node_t* t[4];

    Node_t* n;

    zx = b_row(zdx);
    zy = b_col(zdx);

    if(valid_move(zx-1, zy))
    {
        idx = (zx-1) * g_SZ + zy;
        n = alnode();

        cpyb(n, node);
        swap(&n->board[idx], &n->board[zdx]);
        n->hash = hash_djb2(n->board, g_SZ2);

        if(!chkdup(g_atree, n->hash))
            t[c++] = n;
        else
            delnode(n);
    }

    if(valid_move(zx+1, zy))
    {
        idx = (zx+1) * g_SZ + zy;
        n = alnode();

        cpyb(n, node);
        swap(&n->board[idx], &n->board[zdx]);
        n->hash = hash_djb2(n->board, g_SZ2);

        if(!chkdup(g_atree, n->hash))
            t[c++] = n;
        else
            delnode(n);
    }

    if(valid_move(zx, zy-1))
    {
        idx = zx * g_SZ + (zy-1);
        n = alnode();

        cpyb(n, node);
        swap(&n->board[idx], &n->board[zdx]);
        n->hash = hash_djb2(n->board, g_SZ2);

        if(!chkdup(g_atree, n->hash))
            t[c++] = n;
        else
            delnode(n);
    }

    if(valid_move(zx, zy+1))
    {
        idx = zx * g_SZ + (zy+1);
        n = alnode();

        cpyb(n, node);
        swap(&n->board[idx], &n->board[zdx]);
        n->hash = hash_djb2(n->board, g_SZ2);

        if(!chkdup(g_atree, n->hash))
            t[c++] = n;
        else
            delnode(n);
    }

    g_dbgNode += c;
    node->childs = malloc(sizeof(node->childs) * c);
    node->nchild = c;

    int i = 0;
    for(; i < c; i++)
    {
        node->childs[i] = t[i];
        ndump(node->childs[i]);
    }
}

void
cpyb(Node_t* to, const Node_t* from)
{
    size_t i = 0;
    for(; i < g_SZ2; i++)
        to->board[i] = from->board[i];
}

BOOL
cmpnode(const Node_t* a, const Node_t* b)
{
    size_t i = 0;
    for(; i < g_SZ2; i++)
        if(a->board[i] != b->board[i])
            return FALSE;

    return TRUE;
}

size_t
ida_star(const Node_t* root, const Node_t* goal)
{
    size_t bound    = fpH(root, goal);
    size_t t        = 0;

    while(TRUE)
    {
        g_atree     = mktree(g_start);
        g_dbgNode   = 1;
        t           = dfs_contour(g_atree, 0, bound);

        deltree(g_atree);

        if(t == found)
            return found;

        if(t == notfnd)
            return notfnd;

        bound = t;

        g_dbgIter++;
        printf("\nIteration [%d] Bound [%d] Nodes [%d]...", g_dbgIter, bound, g_dbgNode);
    }
}

size_t
dfs_contour(Node_t* n, const size_t g, const size_t b)
{
    size_t min, i = 0, t;
    g_f = g + fpH(n, g_end);

    if(g_f > b)
        return g_f;

    if(is_goal(n))
    {
        g_result = n->cost;
        return found;
    }

    min = UINT_MAX;
    expand(n);
    for(; i < n->nchild; i++)
    {
        n->childs[i]->cost = n->cost + 1;
        t = dfs_contour(n->childs[i], g + n->childs[i]->cost, b);

        if(t == found)
            return found;

        if(t < min)
            min = t;
    }
    return min;
}

BOOL
is_goal(const Node_t* n)
{
    return n->hash == g_end->hash ? TRUE : FALSE;
}

size_t
b_row(const size_t pos)
{
    return pos / g_SZ;
}

size_t
b_col(const size_t pos)
{
    return pos % g_SZ;
}

int
idxOf(const size_t* b, const size_t c)
{
    int i = 0;
    for(; i < g_SZ2; i++)
        if(b[i] == c)
            return i;

    return -1;
}

void
swap(size_t* to, size_t* from)
{
    size_t t = *to;
    *to = *from;
    *from = t;
}

BOOL
valid_move(const int x, const int y)
{
    return x >= 0 && x < g_SZ && y >= 0 && y < g_SZ ? TRUE : FALSE;
}

size_t
taxicab(const Node_t* n, const Node_t* e)
{
    size_t m = 0, i = 0;
    for(; i < g_SZ2; i++)
    {
        size_t nx, ny, ex, ey;

        nx = b_row(idxOf(n->board, i));
        ny = b_col(idxOf(n->board, i));

        ex = b_row(idxOf(e->board, i));
        ey = b_col(idxOf(e->board, i));

        m += (abs(ex - nx) + abs(ey - ny));
    }
    return m;
}

size_t
ham(const Node_t* n, const Node_t* e)
{
    size_t h = 0, i = 0;
    for(; i < g_SZ2; i++)
        if(n->board[i] != e->board[i])
            h++;

    return h;
}

size_t
mixit(const Node_t* n, const Node_t* e)
{
    return taxicab(n, e) + ham(n, e);
}


clock_t g_start_time;
clock_t g_stop_time;


void
start_timer(void)
{
    g_start_time = clock();
}

void
stop_timer(void)
{
    g_stop_time = clock();
}

size_t
get_time_taken_ms(void)
{
    return g_stop_time - g_start_time;
}

float
get_time_taken_sec(void)
{
    return ((float)(g_stop_time - g_start_time)) / CLOCKS_PER_SEC;
}

size_t
hash_djb2(const size_t* b, const size_t l)
{
    size_t h = 5381;
    size_t i = 0;
    for(; i < l; i++)
        h = ((h << 5) + h) + b[i];

    return h;
}

void
ndump(Node_t* n)
{
#ifdef _DEBUG
    printf("\n*******************************\n\
NODE PTR    %d\n\
NODE HASH   %x\n\
NODE COST   %d\n\
NODE NCHILD %d\n\
NODE BOARD  ", n, n->hash, n->cost, n->nchild);

    int i = 0;
    for(; i < g_SZ2; i++)
        printf("%d ", n->board[i]);

    puts("\n*******************************");
#endif
}