SHARE
TWEET

Untitled

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