gistfile1.c

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

#define found UINT_MAX-1
#define notfnd UINT_MAX-2

typedef enum {kLeft, kRight, kUp, kDown, kNone} Direction;

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

typedef uint64_t State_t;


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

State_t g_start,
        g_end;


uint8_t (*fpH)(const State_t, const State_t);

uint8_t  taxicab     (const State_t n, const State_t e);
uint8_t  ham         (const State_t n, const State_t e);
uint8_t  mixit       (const State_t n, const State_t e);


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


size_t  ida_star    (const State_t root, const State_t goal);
size_t  dfs_contour (State_t n, const uint8_t g, const uint8_t b, Direction d);

BOOL    valid_move  (const uint8_t x, const uint8_t y);

uint8_t idx         (const State_t s, const uint8_t i);
uint8_t row         (const uint8_t i);
uint8_t col         (const uint8_t i);

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


int
main(void)
{
    fpH = &taxicab;
    //fpH = &taxicablin;
    //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 %f seconds", inf, get_time_taken_sec());


    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);
    }
}

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 = g_end = 0;

    int i, j;
    for(i = 0; i < g_SZ; i++)
    {
        State_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 |= n << ((j + i * g_SZ) * 4);
        }
    }

    for(i = 0; i < g_SZ; i++)
    {
        State_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 |= n << ((j + i * g_SZ) * 4);
        }
    }
    fclose(fp);
}


size_t
ida_star(const State_t root, const State_t goal)
{
    uint8_t bound   = fpH(root, goal);
    size_t  t       = 0;
    State_t start   = root;

    while(TRUE)
    {
        g_dbgState  = 1;
        t           = dfs_contour(start, 0, bound, kNone);

        g_dbgIter++;
        printf("\nIteration [%d] Bound [%d] States [%d]...", g_dbgIter, bound, g_dbgState);

        if(t == found)
            return found;

        if(t == notfnd)
            return notfnd;

        bound = t;
    }
}

size_t
dfs_contour(State_t st, const uint8_t g, const uint8_t b, Direction d)
{
    size_t min, t;
    g_f = g + fpH(st, g_end);

    if(g_f > b)
        return g_f;

    if(st == g_end)
    {
        g_result = g;
        return found;
    }

    min = UINT_MAX;

    uint8_t zx  = col(idx(st, 0));
    uint8_t zy  = row(idx(st, 0));
    uint8_t idx, zdx;

    State_t tmp;
    uint8_t tv;

    if(d != kRight && valid_move(zx-1, zy))
    {
        idx = ((zx-1) + zy * g_SZ) * 4;
        zdx = (zx + zy * g_SZ) * 4;
        tmp = st;
        tv = (tmp & ((State_t)0xF<<idx)) >> idx;
        tmp ^= (((State_t)tv) << idx);
        tmp |= (((State_t)tv) << zdx);

        g_dbgState++;

        t   = dfs_contour(tmp, g + 1, b, kLeft);

        if(t == found)
            return found;

        if(t < min)
            min = t;
    }

    if(d != kLeft && valid_move(zx+1, zy))
    {
        idx = ((zx+1) + zy * g_SZ) * 4;
        zdx = (zx + zy * g_SZ) * 4;
        tmp = st;
        tv = (tmp & ((State_t)0xF<<idx)) >> idx;
        tmp ^= (((State_t)tv) << idx);
        tmp |= (((State_t)tv) << zdx);

        g_dbgState++;

        t   = dfs_contour(tmp, g + 1, b, kRight);

        if(t == found)
            return found;

        if(t < min)
            min = t;
    }

    if(d != kDown && valid_move(zx, zy-1))
    {
        idx = (zx + (zy-1)*g_SZ) * 4;
        zdx = (zx + zy*g_SZ) * 4;
        tmp = st;
        tv = (tmp & ((State_t)0xF<<idx)) >> idx;
        tmp ^= (((State_t)tv) << idx);
        tmp |= (((State_t)tv) << zdx);

        g_dbgState++;

        t   = dfs_contour(tmp, g + 1, b, kUp);

        if(t == found)
            return found;

        if(t < min)
            min = t;
    }

    if(d != kUp && valid_move(zx, zy+1))
    {
        idx = (zx + (zy+1) * g_SZ) * 4;
        zdx = (zx + zy * g_SZ) * 4;
        tmp = st;
        tv = (tmp & ((State_t)0xF<<idx)) >> idx;
        tmp ^= (((State_t)tv) << idx);
        tmp |= (((State_t)tv) << zdx);

        g_dbgState++;

        t   = dfs_contour(tmp, g + 1, b, kDown);

        if(t == found)
            return found;

        if(t < min)
            min = t;
    }

    return min;
}


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

uint8_t idx(const State_t s, const uint8_t i)
{
    uint8_t it = 0;
    for(; it < g_SZ2; it++)
    {
        uint8_t t = (s >> (it * 4)) & 0xF;
        if(t == i)
            return it;
    }
    return -1;
}

uint8_t row(const uint8_t i)
{
    return i / g_SZ;
}

uint8_t col(const uint8_t i)
{
    return i % g_SZ;
}

uint8_t
taxicab(const State_t n, const State_t e)
{
    uint8_t m = 0, i = 1;
    for(; i < g_SZ2; i++)
    {
        uint8_t nx, ny, ex, ey;

        nx = col(idx(n, i));
        ny = row(idx(n, i));

        ex = col(idx(e, i));
        ey = row(idx(e, i));

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

uint8_t
ham(const State_t n, const State_t e)
{
    size_t h = 0, i = 1;
    for(; i < g_SZ2; i++)
        if( ((n>>(i*4)) & 0xF) != ((e>>(i*4)) & 0xF) )
            h++;

    return h;
}

uint8_t
mixit(const State_t n, const State_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;
}