SHARE
TWEET

Untitled

a guest Aug 13th, 2017 51 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //TODO
  2. //add sizeof() to show memory usage -- graph it
  3. //add Table::next()
  4. //destructor for Node
  5. //add end pointer to Table
  6.  
  7. #include <iostream>
  8. #include <string>
  9. #include <stdlib.h>
  10. #include <stdio.h>
  11.  
  12. //#include <ext/hash_map> -- too cool for STL
  13.  
  14. using std::cout;    using std::endl;
  15. using std::string;
  16.  
  17. struct Board;
  18. struct Table;
  19.  
  20. typedef enum Direction{Down=0,Right,Up,Left} Direction;
  21. typedef enum Algorithm{AS=0,BFS,DFS} Algorithm;
  22.  
  23. const int N = 3;
  24. static int (*heur_f)(int**) = NULL;//for A* only
  25. static int (*hash_f)(Board*) = NULL;//for A* only
  26. static int **goal_state;
  27. static Algorithm alg;
  28.  
  29. //pass a string with error message and then terminates
  30. void die_with_error(string s);
  31. //swaps (i,j) with (x,y) on tile map
  32. void swap_tiles(int **b,int i,int j,int x,int y);
  33. //returns false if the empty tile can move up; otherwise true;
  34. //CHANGES change state of board if it is a valid move; you must specify
  35. //where the empty tile is (i,j) where both variables range from [0,N)
  36. bool empty_up(int **board,int i,int j);
  37. //similar logic as empty_up() but for down
  38. bool empty_down(int **board,int i,int j);
  39. bool empty_left(int **board,int i,int j);
  40. bool empty_right(int **board,int i,int j);
  41. //checks where a given tile map is solvable
  42. bool solvable(int**);
  43.  
  44. //adds a child, a single Board* node, to parent; DFS adds it to front of
  45. //list otherwise adds it at the end; if A*, then the function assumes parent
  46. //list is already sorted with descending f()
  47. Board* add_node(Board* list, Board* node);
  48. //for all Boards in a and b, it will remove any matching nodes from b in a
  49. //and return new b; a and b are lists
  50. Board* filter(Board* a, Board* b);
  51. //same as filter but find_me is a single node
  52. Board* remove_node(Board* find_me,Board* list);
  53. //prints a Board* linked list
  54. void print_list(Board* b);
  55. //prints the path followed from a Board; pass the terminal Board!
  56. //b is the found goal state with direction, g is the initial state, c is the closed list.
  57. void print_path(Board* b, Board* g, Table* c);
  58.  
  59.  
  60. int heuristic_func(int** state){
  61.     int cnt=0;
  62.  
  63.     for(int i=0;i<N;i++)
  64.         for(int j=0;j<N;j++){
  65.             if(goal_state[i][j] != state[i][j]) cnt++;
  66.         }
  67.  
  68.     return cnt;
  69. }
  70.  
  71. //returns hash value for table from a given board state
  72. int hash_func(Board*);
  73.  
  74. struct Board{
  75.     Board(int**,int,Direction);
  76.     //returns the f() value in f = g+h
  77.     int f();
  78.     //returns the g() value in f = g+h
  79.     int g();
  80.     //returns the h() value in f = g+h
  81.     int h();
  82.     //returns the direction the move was made to arrive to this state
  83.     Direction direction();
  84.     //prints the state and f,g,h,path values
  85.     void print();
  86.     //returns the array of the state, not f,g,h,path
  87.     //remember to free after use
  88.     int** array();
  89.     //files in the variables passed on the coordinates where a tile T is;
  90.     //both x and y are in [0,N); returns (-1,-1) if not found
  91.     void tile_pos(int T,int* x,int* y);
  92.     //returns pointer(Board*) to Board* element pointed by the current one
  93.     Board* next();
  94.     //allows you to update what next() returns which is a pointer to a Board
  95.     void next(Board*);
  96.     //returns true if both nodes have the same tile configuration; it does
  97.     //not compare f,g,h, or path; otherwise, false
  98.     bool same(Board*);
  99.     //Returns the state in string form
  100.     string deconstruct_state();
  101.  
  102.     friend int hash_func(Board* b);
  103.  
  104.     private:
  105.     int x,y;
  106.     Board* _next;
  107. };
  108.  
  109. struct Table{
  110.     //returns how many nodes there are
  111.     int count;
  112.     //prints all entries of a hash table
  113.     //size of hash table is passed as parameter
  114.     Table(int);
  115.     //valid only for BFS DFS
  116.     Table();
  117.     //inserts a SINGLE board into the table
  118.     void insert(Board*);
  119.     //returns the next Board* element; NULL if none exists; automatically
  120.     //returns appropriate Board* depending on whether BFS, DFS, or A*
  121.     Board* next();
  122.     //returns true if a given Board exists
  123.     Board* exists(Board*);
  124.     private:
  125.     Board** t;
  126.     int _n;
  127. };
  128.  
  129. Board* Table::exists(Board* b){
  130.     Board* iter;
  131.  
  132.     if(_n != -1)
  133.         iter = t[hash_f(b)%_n];
  134.     else
  135.         iter = t[0];
  136.  
  137.     while(iter != NULL){
  138.         if(iter->same(b))
  139.             return iter;
  140.         else
  141.             iter = iter->next();
  142.     }
  143.  
  144.  
  145.     return NULL;
  146. }
  147.  
  148. bool Board::same(Board* b){
  149.     if(b == NULL) return false;
  150.  
  151.     if(x == b->x && ((y&0xF0000000) == (b->y&0xF0000000)))
  152.             return true;
  153.  
  154.     return false;
  155. }
  156.  
  157. Board* Table::next(){
  158.     Board* b = NULL;//most legible node per algorithm
  159.  
  160.     if(_n != -1){
  161.         int min = -1; //min. not yet found if it is == -1
  162.  
  163.         for(int i=0;i<_n;i++){
  164.             Board* iter = t[i];
  165.  
  166.             //assuming list is in decreasing order
  167.             if(iter != NULL){
  168.                 while(iter->next() != NULL) iter = iter->next();
  169.  
  170.                 int f = iter->f();
  171.                 if(min == -1 || f < min){
  172.                     min = f;
  173.                     b = iter;
  174.                 }
  175.             }
  176.  
  177.         }
  178.         //remove the node from the t[i] list
  179.         if(b != NULL){//a smallest node exists
  180.             Board* n = new Board(*b);
  181.             int hash_val = hash_f(b)%_n;
  182.             t[hash_val] = remove_node(n,t[hash_val]);
  183.             n->next(NULL);
  184.             b = n;
  185.         }
  186.     }
  187.     else{
  188.         //whether BFS or DFS, first node is located at t[0] because insert()
  189.         //inserts at front
  190.         b = t[0];
  191.  
  192.         if(b == NULL)
  193.             return NULL;
  194.         else
  195.             t[0] = t[0]->next();
  196.  
  197.         b->next(NULL);
  198.     }
  199.  
  200.     if(b != NULL) count--;
  201.  
  202.     return b;
  203. }
  204.  
  205. Table::Table(){
  206.     _n = -1;
  207.     t = new Board*[1];
  208.     t[0] = NULL;
  209. }
  210.  
  211. void Table::insert(Board *b){
  212.     if(b == NULL) return;
  213.    
  214.     b->next(NULL);
  215.     count++;
  216.     if(_n != -1){
  217.         int h = hash_f(b)%_n;
  218.         t[h] = add_node(t[h],b);
  219.     }
  220.     else{
  221.         t[0] = add_node(t[0],b);
  222.     }
  223. }
  224.  
  225. Table::Table(int n) : _n(n){
  226.     t = new Board*[_n];
  227.  
  228.     for(int i=0;i<_n;i++)
  229.         t[i] = NULL;
  230. }
  231.  
  232. Board* Board::next(){return _next;}
  233. void Board::next(Board* b){_next    =   b;}
  234.  
  235. void Board::tile_pos(int tile,int* x,int* y){
  236.     int** state = this->array();
  237.  
  238.     for(int i=0;i<N;i++)
  239.         for(int j=0;j<N;j++)
  240.             if(state[i][j] == tile){
  241.                 *x = i;
  242.                 *y = j;
  243.                 return;
  244.             }
  245.  
  246.     for(int i=0;i<N;i++)
  247.         delete [] state[i];
  248.     delete [] state;
  249. }
  250.  
  251. Direction Board::direction(){
  252.  
  253.     switch(0x3&y){
  254.         case Down: return Down; break;
  255.         case Up: return Up; break;
  256.         case Left: return Left; break;
  257.         default: return Right;
  258.     }
  259.  
  260. }
  261.  
  262. int Board::f(){
  263.     return g()+h();
  264. }
  265.  
  266. int Board::g(){
  267.     return 0x1FFF&(y>>15);
  268. }
  269.  
  270. int Board::h(){
  271.     return 0x1FFF&(y>>2);
  272. }
  273.  
  274. //print the state along with the f,g,h,path values
  275. void Board::print(){
  276.     int** state = this->array();
  277.  
  278.     cout << endl;
  279.     for(int i=0;i<N;i++){
  280.         for(int j=0;j<N;j++){
  281.             cout << state[i][j];
  282.  
  283.             if(state[i][j] < 10) cout << "  ";
  284.             else cout << " ";
  285.         }
  286.         cout << endl;
  287.     }
  288.  
  289.     if(alg == AS)
  290.         cout << "f(" << f() << ") g(" << g() << ") h(" << h() << ") ";
  291.  
  292.     switch(direction()){
  293.         case Up: cout << "Up"; break;
  294.         case Down: cout << "Down"; break;
  295.         case Left: cout << "Left"; break;
  296.         case Right: cout << "Right"; break;
  297.     }
  298.  
  299.     cout << endl;
  300.  
  301.     for(int i=0;i<N;i++)
  302.         delete [] state[i];
  303.     delete [] state;
  304. }
  305.  
  306. string Board::deconstruct_state(){
  307.     int** b = this->array();
  308.     char* num;
  309.     string state = "";
  310.  
  311.     for(int i = 0; i < N; i++){
  312.         for(int j = 0; j < N; j++){
  313.             if (i > 0 || j > 0) state += " ";
  314.             sprintf(num,"%d",b[i][j]);
  315.             state += num;
  316.         }
  317.     }
  318.     return state;
  319. }
  320.  
  321.  
  322. //don't forget to delete array after finished with it
  323. //returns NxN array
  324. //contains hardcoded values
  325. int** Board::array(){
  326.     int **state;
  327.  
  328.     state = new int*[N];
  329.     for(int i=0;i<3;i++)
  330.         state[i] = new int[N];
  331.  
  332.     //first 8 numbers go into the first integer; 8 segements of 4-bits
  333.     for(int i=0;i<8;i++)
  334.         state[i/N][i%N] = (x>>(4*(7-i)))&0xF;
  335.  
  336.     //last number and g,h,path go into second integer
  337.     state[2][2] = 0xF&(y>>28);
  338.  
  339.     return state;
  340. }
  341.  
  342. //contains hardcoded values
  343. Board::Board(int** state,int g,Direction path){
  344.     next(NULL);
  345.     int j;
  346.  
  347.     //first 8 numbers go into the first integer; 8 segements of 4-bits
  348.     j=0;
  349.     for(int i=0;i<8;i++)
  350.         j = (j<<4)|(state[i/3][i%3]&0xF);
  351.  
  352.     x = j;
  353.  
  354.     //last number and f,g,h,path go into second integer
  355.     j=0;
  356.     int heur = heur_f(state);
  357.     j = 0xF&state[2][2]; //last integer in array 4-bits
  358.     j = (j<<13)|(0x1FFF&g); // g 8-bits
  359.     j = (j<<13)|(0x1FFF&heur); // h 8-bits
  360.     j = (j<<2)|(0x3&path); //path 2-bits
  361.  
  362.     y=j;
  363. }
  364.  
  365. bool empty_up(int **board,int i,int j){
  366.     if(i-1<0) return true;
  367.     else swap_tiles(board,i-1,j,i,j);
  368.  
  369.     return false;
  370. }
  371.  
  372. bool empty_down(int **board,int i,int j){
  373.     if(i+1>=N) return true;
  374.     else swap_tiles(board,i+1,j,i,j);
  375.  
  376.     return false;
  377. }
  378.  
  379. bool empty_left(int **board,int i,int j){
  380.     if(j-1<0) return true;
  381.     else swap_tiles(board,i,j,i,j-1);
  382.        
  383.     return false;
  384. }
  385.  
  386. bool empty_right(int **board,int i,int j){
  387.     if(j+1>=N) return true;
  388.     else swap_tiles(board,i,j+1,i,j);
  389.  
  390.     return false;
  391. }
  392.  
  393. //psedo function
  394. Board* expand(Board *p){
  395.     Board* list = NULL;
  396.     int x,y,cnt;//for coords for empty tile
  397.  
  398.     if(p == NULL) return NULL;
  399.  
  400.     //find the position of empty tile on parent board
  401.     p->tile_pos(0,&x,&y);
  402.     if(x == -1 || y == -1)
  403.         die_with_error("tile_pos() returned values out of bounds");
  404.  
  405.     //copy parent state for use by a max of four children
  406.     int*** state = new int**[4];
  407.     for(int i=0;i<4;i++)
  408.         state[i] = p->array();
  409.  
  410.     cnt = 0;
  411.     //attempt to move empty tile for all four children; these functions
  412.     //autmatically update the board if it is a valid move
  413.     if(!empty_up(state[0],x,y))
  414.         list = add_node(list,new Board(state[0],p->g()+1,Up));
  415.     if(!empty_down(state[1],x,y))
  416.         list = add_node(list,new Board(state[1],p->g()+1,Down));
  417.     if(!empty_left(state[2],x,y))
  418.         list = add_node(list,new Board(state[2],p->g()+1,Left));
  419.     if(!empty_right(state[3],x,y))
  420.         list = add_node(list,new Board(state[3],p->g()+1,Right));
  421.  
  422.  
  423.     //free the 3d state array
  424.     for(int i=0;i<N;i++)
  425.         for(int j=0;j<N;j++)
  426.             delete [] state[i][j];
  427.  
  428.     for(int i=0;i<N;i++)
  429.         delete [] state[i];
  430.  
  431.     delete [] state;
  432.  
  433.     return list;
  434. }
  435.  
  436. Board* add_node(Board* p, Board* c){
  437.     if(p == NULL) return c;
  438.     else if(c == NULL) return p;
  439.  
  440.  
  441.     c->next(NULL);
  442.  
  443.     if(alg == DFS){
  444.         c->next(p);
  445.         return c;
  446.     }
  447.     else if(alg == AS){
  448.         //only check f() for first node only because we don't know whether
  449.         //to return c or p
  450.         Board *b = p;
  451.         if(b->f() <= c->f()){
  452.             c->next(b);
  453.             return c;
  454.         }
  455.         else{
  456.             while(b->next() != NULL && b->f() >= c->f())
  457.                 b = b->next();
  458.  
  459.             c->next(b->next());
  460.             b->next(c);
  461.             return p;
  462.         }
  463.     }
  464.     else{
  465.         Board *b = p;
  466.         while(b->next() != NULL) b = b->next();
  467.         b->next(c);
  468.     }
  469.  
  470.     return p;
  471. }
  472.  
  473. void swap_tiles(int **b,int i,int j,int x,int y){
  474.     int t = b[x][y];
  475.     b[x][y] = b[i][j];
  476.     b[i][j] = t;
  477. }
  478.  
  479. void die_with_error(string s){
  480.     cout << "\nError: " << s << ". Terminating..." << endl;
  481.     exit(1);
  482. }
  483.  
  484. int hash_func(Board* b){
  485.     int h = b->x;
  486.     h = (h<<4)&((b->y&0xF0000000)>>28);
  487.     return h;
  488. }
  489.  
  490. Board* remove_node(Board* find_me,Board* list){
  491.     Board *pp = NULL, *cp = list;
  492.     //pp = previous pointer from list, cp = current pointer from list
  493.  
  494.     if(find_me == NULL || list == NULL) return list;
  495.  
  496.     while(cp != NULL){
  497.         if(cp->same(find_me)){
  498.             if(pp != NULL){
  499.                 pp->next(cp->next());
  500.                 delete cp;
  501.                 cp = pp->next();
  502.             }
  503.             else{
  504.                 Board* t = cp;
  505.                 list = list->next();
  506.                 delete t;
  507.                 cp = list;
  508.             }
  509.         }
  510.         else{
  511.             pp = cp;
  512.             cp = cp->next();
  513.         }
  514.     }
  515.  
  516.     return list;
  517. }
  518.  
  519. Board *filter(Board *hp,Board *succ){
  520.     Board* pp = NULL, *cp = succ, *p = hp;
  521.     //pp = previous pointer from succ list, cp = current pointer from succ
  522.     //list , p = working pointer from hp list
  523.  
  524.     if(hp == NULL || succ == NULL) return succ;
  525.  
  526.     while(p != NULL){
  527.         cp = succ;
  528.         pp = NULL;
  529.  
  530.         while(cp != NULL){
  531.  
  532.             if(p->same(cp)){
  533.                
  534.                 if(pp != NULL){//has a previous pointer
  535.                     pp->next(cp->next());
  536.                     delete cp;
  537.                     cp = pp->next();
  538.                 }
  539.                 else{
  540.                     Board* t = succ;
  541.                     succ = succ->next();
  542.                     delete t;
  543.                     cp = succ;
  544.                 }
  545.             }
  546.             else{
  547.                 pp = cp;
  548.                 cp = cp->next();
  549.             }
  550.  
  551.         }
  552.  
  553.         p = p->next();
  554.     }
  555.        
  556.  
  557.     return succ;
  558. }
  559.  
  560. bool solvable(int** state){
  561.     if(state == NULL) return false;
  562.  
  563.     int cnt,agg[N*N];
  564.  
  565.     //aggregate into one a 1-d array
  566.     cnt=0;
  567.     for(int i=0;i<N;i++)
  568.         for(int j=0;j<N;j++){
  569.             if(state[i][j] == 0)
  570.                 continue;
  571.  
  572.             agg[cnt++] = state[i][j];
  573.         }
  574.  
  575.     //count number of inversions
  576.     cnt=0;
  577.     for(int i=0;i<N*N-1;i++)
  578.         for(int j=i+1;j<N*N-1;j++){
  579.             if(agg[j]<agg[i])
  580.                 cnt++;
  581.         }
  582.    
  583. //If the grid width is odd, then the number of inversions in a solvable situation is even.
  584. //If the grid width is even, and the blank is on an even row counting from the bottom (second-last, fourth-last etc), then the number of inversions in a solvable situation is odd.
  585. //If the grid width is even, and the blank is on an odd row counting from the bottom (last, third-last, fifth-last etc) then the number of inversions in a solvable situation is even.
  586.  
  587.     //we know N is odd
  588.     if(cnt % 2 == 0) return true;
  589.  
  590.     return false;
  591. }
  592.  
  593. void print_list(Board* b){
  594.     while(b != NULL){
  595.         b->print();
  596.         b = b->next();
  597.     }
  598. }
  599.  
  600. void print_path(Board* b, Board* g, Table* c){ 
  601.     int x, y;
  602.     Direction d;
  603.     string state;
  604.     int** state_array;
  605. //  FILE* solution;
  606. //  solution = fopen ("solution.txt","w");
  607.     while (!b->same(g)){
  608.         state_array = b->array();
  609.         state = b->deconstruct_state();
  610. //      state += "\n";
  611. //      fwrite(state.c_str(), 1, sizeof(state.c_str()), solution);
  612. //      rewind(solution);
  613.         cout<<"\n"<<state<<endl;
  614.         d = b->direction();
  615.         b->tile_pos(0, &x, &y);
  616.         switch(d){
  617.             case Down: empty_up(state_array, x, y); break;
  618.             case Up: empty_down(state_array, x, y); break;
  619.             case Left: empty_right(state_array, x, y); break;
  620.             default: empty_left(state_array, x, y);
  621.         }
  622.         b = new Board(state_array, b->g() - 1, d);
  623.         b->print();
  624.         cout<<"\nhash: "<<hash_func(b)<<endl;
  625.         printf("-------------------");
  626.         b = c->exists(b);
  627.         if (b == NULL) cout<<"b is NULL"<<endl;
  628.     }
  629. //      fclose(solution);
  630. }
  631.  
  632. int main(int argc, char *argv[]){
  633.     int** g= new int*[N];
  634.     int** s= new int*[N];
  635.     goal_state = g;
  636.  
  637.     for(int i=0;i<N;i++){
  638.         g[i] = new int[N];
  639.         s[i] = new int[N];
  640.     }
  641.  
  642.     for(int i=0;i<N;i++)
  643.         for(int j=0;j<N;j++){
  644.             g[i][j] = i*N+j;
  645.             s[i][j] = i*N+j;
  646.         }
  647.  
  648.  
  649.     s[0][0] = 1;
  650.     s[0][1] = 2;
  651.     s[0][2] = 3;
  652.     s[1][0] = 4;
  653.     s[1][1] = 5;
  654.     s[1][2] = 6;
  655.     s[2][0] = 0;
  656.     s[2][1] = 7;
  657.     s[2][2] = 8;
  658.  
  659.     heur_f = &heuristic_func;
  660.     hash_f = &hash_func;
  661.     alg = AS;
  662.  
  663.     Board *goal = new Board(g,0,Down);
  664.     Board *start = new Board(s,0,Down);
  665.  
  666.     //check solvability of both goal and start states
  667.     if(!solvable(s) || !solvable(g))
  668.         die_with_error("goal or initial state is unsolvable");
  669.  
  670.     Table* open = new Table(7919);
  671. //  Table* open = new Table;
  672.     Table* closed = new Table(7919);
  673.     open->count = 0;
  674.     closed->count = 0;
  675.  
  676.     open->insert(start);
  677.  
  678.     int iter=0;
  679.     for(Board* i = open->next(); ; i = open->next()){
  680.         if(i == NULL){
  681.             if(open->exists(goal)){
  682.                 cout << "goal exists in open";
  683.             }
  684.             if(closed->exists(goal)){
  685.                 cout << "goal exists in closed";
  686.             }
  687.             die_with_error("no nodes remaining! BAD!");
  688.             //insert this above into for loop
  689.         }
  690.         //expand node i; generates a linked list of successors
  691.         Board* successors = expand(i);
  692.  
  693.         //for each Board in successor, check that it does not exist; if
  694.         //it does, remove it from the successor list
  695.         for(Board* j = successors; j != NULL; j = j->next()){
  696.             if(open->exists(j)){
  697.                 Board* temp = new Board(*j);
  698.                 temp->next(NULL);
  699.                 successors = remove_node(temp, successors);
  700.                 delete temp;
  701.             }
  702.  
  703.             if(closed->exists(j)){
  704.                 Board* temp = new Board(*j);
  705.                 temp->next(NULL);
  706.                 successors = remove_node(temp, successors);
  707.                 delete temp;
  708.             }
  709.         }
  710.  
  711. //      if(iter % 10000 == 0 || (closed->count+open->count) == 181420){
  712.             cout << "/" <<string(20,'-') << endl;
  713.             cout << "Iter : " << iter << " clos(" << closed->count
  714.                 << ") open(" << open->count << ")" << endl;
  715.             i->print();
  716.             cout << string(20,'-') << endl;
  717.             print_list(successors);
  718.             cout << "\\" << string(20,'-') << endl;
  719. //      }
  720.  
  721.  
  722.         Board* k = successors;
  723.         closed->insert(i);
  724.         //for each of the remaining successors, insert them into open table
  725.         while(k != NULL){
  726.  
  727.             if(goal->same(k)){
  728.                 print_path(k ,start, closed);
  729.                 cout << iter << endl;
  730.                 die_with_error("GOAL FOUND");
  731.             }
  732.  
  733.             Board* n = k;
  734.             k = k->next();
  735.             n->next(NULL);
  736.             open->insert(n);
  737.         }
  738.  
  739.         //closed->insert(i);
  740.         iter++;
  741.     }
  742.    
  743.     return 0;
  744. }
RAW Paste Data
Top