Created
October 5, 2014 03:25
-
-
Save keyboardspecialist/6973726a36d58d42d214 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
#include <time.h> | |
#include <limits.h> | |
#include <string.h> | |
#define found UINT_MAX-1 | |
#define notfnd UINT_MAX-2 | |
#define _DEBUG | |
#undef _DEBUG | |
#define _CHKDUP | |
#undef _CHKDUP | |
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\\test.txt", "npdata\\ot.txt"); | |
// 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 ms", 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); | |
} | |
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); | |
} | |
//slow | |
BOOL | |
chkdup(const Node_t* r, const size_t h) | |
{ | |
#ifdef _CHKDUP | |
if(r->hash == h) | |
return TRUE; | |
if(r->nchild > 0) | |
{ | |
size_t i = 0; | |
for(; i < r->nchild; i++) | |
{ | |
chkdup(r->childs[i], h); | |
} | |
} | |
#endif | |
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;//cmpnode(n, g_end); | |
} | |
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 = 1; | |
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(nx - ex) + abs(ny - ey)); | |
} | |
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 | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment