API tools faq
paste
Advertisement
Guest User

AI Hw2

a guest
Mar 4th, 2013
52
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 13.24 KB | None | 0 0
raw download clone embed print report
  1. //
  2. // main.cpp
  3. // hw2
  4. //
  5. // Created by Spencer Moran on 2/25/13.
  6. // Copyright (c) 2013 Spencer Moran. All rights reserved.
  7. //
  8.  
  9. #include <iostream>
  10. #include <fstream>
  11. #include <vector>
  12. #include <queue>
  13. #include <iostream>
  14. #include <algorithm>
  15. #include <cstdlib>
  16.  
  17. struct treeNode {
  18. int manDistance;
  19. int outOfPlace;
  20. int fOfX;
  21. std::vector<int> moves;
  22. int board[3][4];
  23.  
  24. treeNode() : manDistance(-1), outOfPlace(-1) {
  25. board[0][0] = -1;
  26. board[0][1] = -1;
  27. board[0][2] = -1;
  28. board[0][3] = -1;
  29. board[1][0] = -1;
  30. board[1][1] = -1;
  31. board[1][2] = -1;
  32. board[1][3] = -1;
  33. board[2][0] = -1;
  34. board[2][1] = -1;
  35. board[2][2] = -1;
  36. board[2][3] = -1;
  37. }
  38. };
  39.  
  40. class compareMD {
  41. public:
  42. bool operator()(treeNode* a, treeNode* b) {
  43. return ((a->moves.size() + a->manDistance) > (b->moves.size() + b->manDistance));
  44. }
  45. };
  46.  
  47. class compareOOP {
  48. public:
  49. bool operator()(treeNode* a, treeNode* b) {
  50. return ((a->moves.size() + a->outOfPlace) > (b->moves.size() + b->outOfPlace));
  51. }
  52. };
  53.  
  54. void createTree(treeNode*);
  55. void getBoard(std::ifstream&, treeNode*);
  56. void setOutOfPlace(treeNode*);
  57. void setManDistance(treeNode*);
  58. void copyNode(treeNode*, treeNode*);
  59. bool nextToZero(int, int, int, int);
  60. bool notInQueueMD(treeNode*, std::priority_queue<treeNode*, std::vector<treeNode*>, compareMD>);
  61. bool notInQueueOOP(treeNode*, std::priority_queue<treeNode*, std::vector<treeNode*>, compareOOP>);
  62.  
  63. int main(int argc, const char * argv[])
  64. {
  65. if (argc != 2) {
  66. std::cout << "Sorry, wrong number of arguments passed!" << std::endl;
  67. }
  68. std::ifstream fin;
  69. std::ofstream fout;
  70. fin.open(argv[1]);
  71.  
  72. treeNode* initialState = new treeNode;
  73.  
  74. getBoard(fin, initialState);
  75. setManDistance(initialState);
  76. setOutOfPlace(initialState);
  77. createTree(initialState);
  78.  
  79.  
  80. return 0;
  81. }
  82.  
  83. void getBoard(std::ifstream& fin, treeNode* initialState) {
  84.  
  85. int startingBoard[3][4];
  86.  
  87. fin >> startingBoard[0][0];
  88. fin >> startingBoard[0][1];
  89. fin >> startingBoard[0][2];
  90. fin >> startingBoard[1][0];
  91. fin >> startingBoard[1][1];
  92. fin >> startingBoard[1][2];
  93. fin >> startingBoard[1][3];
  94. fin >> startingBoard[2][1];
  95. fin >> startingBoard[2][2];
  96. fin >> startingBoard[2][3];
  97. startingBoard[0][3] = -1;
  98. startingBoard[2][0] = -1;
  99.  
  100. for (int i = 0; i < 3; i++) {
  101. for (int j = 0; j < 4; j++) {
  102. initialState->board[i][j] = startingBoard[i][j];
  103. }
  104. }
  105.  
  106. }
  107.  
  108. void createTree(treeNode* initial) {
  109.  
  110. std::priority_queue<treeNode*, std::vector<treeNode*>, compareMD> pqMD;
  111. std::priority_queue<treeNode*, std::vector<treeNode*>, compareOOP> pqOOP;
  112. int emptyR = 0, emptyC = 0;
  113.  
  114. pqMD.push(initial);
  115. treeNode* current = pqMD.top();
  116. pqMD.pop();
  117.  
  118. while (current->manDistance != 0) {
  119.  
  120. if (!pqMD.empty()) {
  121. pqMD.pop();
  122. }
  123.  
  124. //find the empty space
  125. for (int i = 0; i < 3; i++) {
  126. for (int j = 0; j < 4; j++) {
  127. if (current->board[i][j] == 0) {
  128. emptyR = i;
  129. emptyC = j;
  130. }
  131. }
  132. }
  133.  
  134. //add all possible swaps to the priority queue
  135. for (int i = 0; i < 3; i++) {
  136. for (int j = 0; j < 4; j++) {
  137. if (nextToZero(i, j, emptyR, emptyC) && !(i == 0 && j == 3) && !(i == 2 && j == 0)) {
  138. treeNode* addToQueue = new treeNode;
  139. copyNode(addToQueue, current);
  140. addToQueue->board[emptyR][emptyC] = current->board[i][j];
  141. addToQueue->board[i][j] = 0;
  142. setManDistance(addToQueue);
  143. if (addToQueue->moves.empty()) {
  144. addToQueue->moves.push_back(current->board[i][j]);
  145. addToQueue->fOfX = int(addToQueue->moves.size()) + addToQueue->manDistance;
  146. pqMD.push(addToQueue);
  147. }
  148. else {
  149. if (addToQueue->moves.back() != current->board[i][j]) {
  150. addToQueue->moves.push_back(current->board[i][j]);
  151. addToQueue->fOfX = int(addToQueue->moves.size()) + addToQueue->manDistance;
  152. if (notInQueueMD(addToQueue, pqMD) ) {
  153. pqMD.push(addToQueue);
  154. }
  155. }
  156. }
  157.  
  158. }
  159. }
  160. }
  161.  
  162. current = pqMD.top();
  163.  
  164. }
  165.  
  166.  
  167. std::cout << "Manhattan Distance: " << std::endl;
  168. std::cout << "Sequence of tiles to be moved : " ;
  169. for (int i = 0; i < current->moves.size(); i++) {
  170. std::cout << current->moves[i] << " " ;
  171. }
  172. std::cout << std::endl;
  173. std::cout << "Number of moves: " << current->moves.size() << std::endl << std::endl;
  174.  
  175. pqOOP.push(initial);
  176. current = pqOOP.top();
  177. pqOOP.pop();
  178.  
  179. while (current->outOfPlace != 0) {
  180.  
  181. if (!pqOOP.empty()) {
  182. pqOOP.pop();
  183. }
  184.  
  185. //find the empty space
  186. for (int i = 0; i < 3; i++) {
  187. for (int j = 0; j < 4; j++) {
  188. if (current->board[i][j] == 0) {
  189. emptyR = i;
  190. emptyC = j;
  191. }
  192. }
  193. }
  194.  
  195. //add all possible swaps to the priority queue
  196. for (int i = 0; i < 3; i++) {
  197. for (int j = 0; j < 4; j++) {
  198. if (nextToZero(i, j, emptyR, emptyC) && !(i == 0 && j == 3) && !(i == 2 && j == 0)) {
  199. treeNode* addToQueue = new treeNode;
  200. copyNode(addToQueue, current);
  201. addToQueue->board[emptyR][emptyC] = current->board[i][j];
  202. addToQueue->board[i][j] = 0;
  203. setOutOfPlace(addToQueue);
  204. if (addToQueue->moves.empty()) {
  205. addToQueue->moves.push_back(current->board[i][j]);
  206. addToQueue->fOfX = int(addToQueue->moves.size()) + addToQueue->outOfPlace;
  207. pqOOP.push(addToQueue);
  208. }
  209. else {
  210. if (addToQueue->moves.back() != current->board[i][j]) {
  211. addToQueue->moves.push_back(current->board[i][j]);
  212. addToQueue->fOfX = int(addToQueue->moves.size()) + addToQueue->outOfPlace;
  213. if (notInQueueOOP(addToQueue, pqOOP)) {
  214. pqOOP.push(addToQueue);
  215. }
  216. }
  217. }
  218.  
  219. }
  220. }
  221. }
  222.  
  223. current = pqOOP.top();
  224.  
  225. }
  226.  
  227.  
  228. std::cout << "Number of misplaced tiles: " << std::endl;
  229. std::cout << "Sequence of tiles to be moved : " ;
  230. for (int i = 0; i < current->moves.size(); i++) {
  231. std::cout << current->moves[i] << " " ;
  232. }
  233. std::cout << std::endl;
  234. std::cout << "Number of moves: " << current->moves.size() << std::endl << std::endl;
  235.  
  236.  
  237. }
  238.  
  239. void setOutOfPlace(treeNode* current) {
  240.  
  241. current->outOfPlace = 0;
  242.  
  243. if (current->board[0][0] != 1) {
  244. current->outOfPlace++;
  245. }
  246.  
  247. if (current->board[0][1] != 2) {
  248. current->outOfPlace++;
  249. }
  250.  
  251. if (current->board[0][2] != 3) {
  252. current->outOfPlace++;
  253. }
  254.  
  255. if (current->board[1][0] != 4) {
  256. current->outOfPlace++;
  257. }
  258.  
  259. if (current->board[1][1] != 5) {
  260. current->outOfPlace++;
  261. }
  262.  
  263. if (current->board[1][2] != 6) {
  264. current->outOfPlace++;
  265. }
  266.  
  267. if (current->board[1][3] != 7) {
  268. current->outOfPlace++;
  269. }
  270.  
  271. if (current->board[2][1] != 8) {
  272. current->outOfPlace++;
  273. }
  274.  
  275. if (current->board[2][2] != 9) {
  276. current->outOfPlace++;
  277. }
  278. }
  279.  
  280. void setManDistance(treeNode* current) {
  281.  
  282. current->manDistance = 0;
  283.  
  284. for (int i = 0; i < 3; i++) {
  285. for (int j = 0; j < 4; j++) {
  286.  
  287. if (current->board[i][j] == 1) {
  288. current->manDistance += std::max(std::max(abs(i-0), abs(j-0)), abs((i-0)-(j-0)));
  289. }
  290.  
  291. if (current->board[i][j] == 2) {
  292. current->manDistance += std::max(std::max(abs(i-0), abs(j-1)), abs((i-0)-(j-1)));
  293. }
  294.  
  295. if (current->board[i][j] == 3) {
  296. current->manDistance += std::max(std::max(abs(i-0), abs(j-2)), abs((i-0)-(j-2)));
  297. }
  298.  
  299. if (current->board[i][j] == 4) {
  300. current->manDistance += std::max(std::max(abs(i-1), abs(j-0)), abs((i-1)-(j-0)));
  301. }
  302.  
  303. if (current->board[i][j] == 5) {
  304. current->manDistance += std::max(std::max(abs(i-1), abs(j-1)), abs((i-1)-(j-1)));
  305. }
  306.  
  307. if (current->board[i][j] == 6) {
  308. current->manDistance += std::max(std::max(abs(i-1), abs(j-2)), abs((i-1)-(j-2)));
  309. }
  310.  
  311. if (current->board[i][j] == 7) {
  312. current->manDistance += std::max(std::max(abs(i-1), abs(j-3)), abs((i-1)-(j-3)));
  313. }
  314.  
  315. if (current->board[i][j] == 8) {
  316. current->manDistance += std::max(std::max(abs(i-2), abs(j-1)), abs((i-2)-(j-1)));
  317. }
  318.  
  319. if (current->board[i][j] == 9) {
  320. current->manDistance += std::max(std::max(abs(i-2), abs(j-2)), abs((i-2)-(j-2)));
  321. }
  322. }
  323. }
  324. }
  325.  
  326.  
  327. void copyNode(treeNode* addToQueue, treeNode* current) {
  328.  
  329. addToQueue->manDistance = current->manDistance;
  330. addToQueue->fOfX = current->fOfX;
  331. for (int i =0; i < 3; i++) {
  332. for (int j = 0; j < 4; j++) {
  333. addToQueue->board[i][j] = current->board[i][j];
  334. }
  335. }
  336. for (int i = 0; i < current->moves.size(); i++) {
  337. addToQueue->moves.push_back(current->moves[i]);
  338. }
  339. }
  340.  
  341. bool nextToZero(int r, int c, int eR, int eC) {
  342.  
  343.  
  344. if (eR - r == 0 && eC - c == 0) {
  345. return false;
  346. }
  347.  
  348. else if (eR - r == 1 && eC - c == 0) {
  349. return true;
  350. }
  351.  
  352. else if (eR - r == 1 && eC - c == 1) {
  353. return true;
  354. }
  355.  
  356. else if (eR - r == 0 && eC - c == 1) {
  357. return true;
  358. }
  359.  
  360. else if (eR - r == -1 && eC - c == 0) {
  361. return true;
  362. }
  363.  
  364. else if (eR - r == -1 && eC - c == -1) {
  365. return true;
  366. }
  367.  
  368. else if (eR - r == 0 && eC - c == -1) {
  369. return true;
  370. }
  371.  
  372. else {
  373. return false;
  374. }
  375. }
  376.  
  377. bool notInQueueMD(treeNode* current, std::priority_queue<treeNode*, std::vector<treeNode*>, compareMD> pqMD) {
  378.  
  379. std::priority_queue<treeNode*, std::vector<treeNode*>, compareMD> tempQueue;
  380.  
  381. while (!pqMD.empty()) {
  382.  
  383. tempQueue.push(pqMD.top());
  384. treeNode* tempNode = pqMD.top();
  385. pqMD.pop();
  386.  
  387. for (int j = 0; j < 3; j++) {
  388. for (int k = 0; k < 4; k++) {
  389. if (current->board[j][k] != tempNode->board[j][k]) {
  390. while (!tempQueue.empty()) {
  391. pqMD.push(tempQueue.top());
  392. tempQueue.pop();
  393. }
  394. return true;
  395. }
  396. }
  397. }
  398. if (current->fOfX < tempNode->fOfX) {
  399. tempQueue.pop();
  400. while (!tempQueue.empty()){
  401. pqMD.push(tempQueue.top());
  402. tempQueue.pop();
  403. }
  404. return true;
  405. }
  406. }
  407. while (!tempQueue.empty()) {
  408. pqMD.push(tempQueue.top());
  409. tempQueue.pop();
  410. }
  411. return false;
  412. }
  413.  
  414. bool notInQueueOOP(treeNode* current, std::priority_queue<treeNode*, std::vector<treeNode*>, compareOOP> pqOOP) {
  415.  
  416. std::priority_queue<treeNode*, std::vector<treeNode*>, compareOOP> tempQueue;
  417.  
  418. while (!pqOOP.empty()) {
  419.  
  420. tempQueue.push(pqOOP.top());
  421. treeNode* tempNode = pqOOP.top();
  422. pqOOP.pop();
  423.  
  424. for (int j = 0; j < 3; j++) {
  425. for (int k = 0; k < 4; k++) {
  426. if (current->board[j][k] != tempNode->board[j][k]) {
  427. while (!tempQueue.empty()) {
  428. pqOOP.push(tempQueue.top());
  429. tempQueue.pop();
  430. }
  431. return true;
  432. }
  433. }
  434. }
  435. if (current->fOfX < tempNode->fOfX) {
  436. tempQueue.pop();
  437. while (!tempQueue.empty()){
  438. pqOOP.push(tempQueue.top());
  439. tempQueue.pop();
  440. }
  441. return true;
  442. }
  443. }
  444. while (!tempQueue.empty()) {
  445. pqOOP.push(tempQueue.top());
  446. tempQueue.pop();
  447. }
  448. return false;
  449.  
  450.  
  451. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!