SHARE
TWEET

Untitled

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