SHARE
TWEET

Untitled

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