API tools faq
paste
Guest User

C++ Segmentation Fault

a guest
Feb 23rd, 2013
243
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 13.21 KB | None | 0 0
raw download clone embed print report
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <string>
  4. using namespace std;
  5.  
  6. void swap(int&, int&);
  7. int left(int[][4], int[][4], int, int);
  8. int right(int[][4], int[][4], int, int);
  9. int up(int[][4], int[][4], int, int);
  10. int down(int[][4], int[][4], int, int);
  11. int calc(int[][4], int[][4]);
  12. int lowest(int[][4], int[][4], int, int, int, int, int, int);
  13. int zero(int [][4], int[][4], int[4], int, int, int, int, int, int);
  14. int count(int[][4], int[][4], int[4], int, int, int, int, int, int);
  15. void print(int[][4], int, string);
  16.  
  17. int main()
  18. {
  19. int cur[4][4]; // used to track the initial and current states
  20. int goal[4][4] = // Goal State
  21. {
  22. {1, 2, 3, 4}, // Row 0
  23. {5, 6, 7, 8}, // Row 1
  24. {9, 10, 11, 12}, // Row 2
  25. {13, 14, 15, 0} // Row 3
  26. };
  27. int i, j; // looping variables
  28. int row, col; // used for the location of the blank
  29. int h; // value obtained with the heuristic function
  30. int L, R, U, D; // operators
  31. string op; // stores last operator used
  32. int op_used; // represents an operator
  33. //int n=0; // number of nodes generated
  34. int len=1; // length of solution path
  35.  
  36. cout << "Please input your initial state. Input the numbers from left to right with a space between each one, representing the blank space with the number 0." << endl;
  37. cout << endl;
  38.  
  39. cin >> cur[0][0] >> cur[0][1] >> cur[0][2] >> cur[0][3];
  40. cin >> cur[1][0] >> cur[1][1] >> cur[1][2] >> cur[1][3];
  41. cin >> cur[2][0] >> cur[2][1] >> cur[2][2] >> cur[2][3];
  42. cin >> cur[3][0] >> cur[3][1] >> cur[3][2] >> cur[3][3];
  43. cout << endl;
  44.  
  45. int cc[16] = {cur[0][0], cur[0][1], cur[0][2], cur[0][3], cur[1][0], cur[1][1], cur[1][2], cur[1][3], cur[2][0], cur[2][1], cur[2][2], cur[2][3], cur[3][0], cur[3][1], cur[3][2], cur[3][3]};
  46. int gg[16] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0};
  47. int final=0;
  48.  
  49. for (i=0; i<=3; i++)
  50. {
  51. if (cc[i] == gg[i])
  52. final++;
  53. }
  54.  
  55. // Obtain the current location of the blank space.
  56.  
  57. for (i=0; i<=4; i++)
  58. {
  59. for (j=0; j<=4; j++)
  60. {
  61. if (cur[i][j] == 0)
  62. {
  63. row = i;
  64. col = j;
  65. }
  66. }
  67. }
  68.  
  69. // Calculate h(IS)
  70.  
  71. h = calc(cur, goal);
  72.  
  73. // Print out the initial state.
  74.  
  75. //cout << right << setw(2) << cur[0][0] << " " << setw(2) << cur[0][1] << " " << setw(2) << cur[0][2] << " " << setw(2) << cur[0][3] << endl;
  76. //cout << setw(2) << cur[1][0] << " " << setw(2) << cur[1][1] << " " << setw(2) << cur[1][2] << " " << setw(2) << cur[1][3] << endl;
  77. //cout << setw(2) << cur[2][0] << " " << setw(2) << cur[2][1] << " " << setw(2) << cur[2][2] << " " << setw(2) << cur[2][3] << endl;
  78. //cout << setw(2) << cur[3][0] << " " << setw(2) << cur[3][1] << " " << setw(2) << cur[3][2] << " " << setw(2) << cur[3][3] << endl;
  79. //cout << endl;
  80. //cout << "h(IS) = " << h << endl << endl;
  81. do
  82. {
  83. cout << "made it in the loop";
  84. L = left(cur, goal, row, col);
  85. R = right(cur, goal, row, col);
  86. U = up(cur, goal, row, col);
  87. D = down(cur, goal, row, col);
  88.  
  89. cout << "went through first functions";
  90.  
  91. if (L < R && L < U && L < D)
  92. {
  93. swap(cur[row][col], cur[row][col-1]);
  94. col = col - 1;
  95. op = "Left";
  96. print(cur, L, op);
  97. }
  98. else if (R < L && R < U && R < D)
  99. {
  100. swap(cur[row][col], cur[row][col+1]);
  101. col = col + 1;
  102. op = "Right";
  103. print(cur, R, op);
  104. }
  105. else if (U < L && U < R && U < D)
  106. {
  107. swap(cur[row][col], cur[row-1][col]);
  108. row = row - 1;
  109. op = "Up";
  110. print(cur, U, op);
  111. }
  112. else if (D < L && D < R && D < U)
  113. {
  114. swap(cur[row][col], cur[row+1][col]);
  115. row = row + 1;
  116. op = "Down";
  117. print(cur, D, op);
  118. }
  119. // If there is no lowest operator, find the lowest matching ones.
  120. // From there, we will find the number of rows and columns the blank is away from the right space
  121. // If this isn't right, then just count the TOTAL NUMBER.
  122. // this can be very difficult, because we would need to recreate these.....UGH......
  123. else
  124. {
  125. op_used = lowest(goal, cur, L, R, U, D, row, col);
  126. if (op_used == 1)
  127. {
  128. op = "Left";
  129. swap(cur[row][col], cur[row][col-1]);
  130. col = col - 1;
  131. print(cur, L, op);
  132. }
  133. else if (op_used == 2)
  134. {
  135. op = "Right";
  136. swap(cur[row][col], cur[row][col+1]);
  137. col = col + 1;
  138. print(cur, R, op);
  139. }
  140. else if (op_used == 3)
  141. {
  142. op = "Up";
  143. swap(cur[row][col], cur[row-1][col]);
  144. row = row - 1;
  145. print(cur, U, op);
  146. }
  147. else
  148. {
  149. op = "Down";
  150. swap(cur[row][col], cur[row+1][col]);
  151. row = row + 1;
  152. print(cur, D, op);
  153. }
  154. }
  155.  
  156. int cc[16] = {cur[0][0], cur[0][1], cur[0][2], cur[0][3], cur[1][0], cur[1][1], cur[1][2], cur[1][3], cur[2][0], cur[2][1], cur[2][2], cur[2][3], cur[3][0], cur[3][1], cur[3][2], cur[3][3]};
  157. final = 0;
  158.  
  159. for (i=0; i<=3; i++)
  160. {
  161. if (cc[i] == gg[i])
  162. final++;
  163. }
  164. } while (final < 16);
  165.  
  166. // We can now assume that the goal state has been reached, and print it out.
  167.  
  168. cout << "Operator: " << op << endl << endl;
  169. cout << right << setw(2) << cur[0][0] << " " << setw(2) << cur[0][1] << " " << setw(2) << cur[0][2] << " " << setw(2) << cur[0][3] << endl;
  170. cout << setw(2) << cur[1][0] << " " << setw(2) << cur[1][1] << " " << setw(2) << cur[1][2] << " " << setw(2) << cur[1][3] << endl;
  171. cout << setw(2) << cur[2][0] << " " << setw(2) << cur[2][1] << " " << setw(2) << cur[2][2] << " " << setw(2) << cur[2][3] << endl;
  172. cout << setw(2) << cur[3][0] << " " << setw(2) << cur[3][1] << " " << setw(2) << cur[3][2] << " " << setw(2) << cur[3][3];
  173. cout << endl << endl;
  174.  
  175. // print out all the additional information
  176.  
  177. //cout << "The total number of nodes generated is: " << n << endl;
  178. //cout << "The length of the solution path is: " << len;
  179.  
  180. return 0;
  181.  
  182. }
  183.  
  184. void swap(int& a, int& b)
  185. {
  186. int temp; // used to hold value
  187. temp = a;
  188. a = b;
  189. b = temp;
  190. }
  191.  
  192. // LEFT FUNCTION
  193. int left (int cur[][4], int g[][4], int row, int col)
  194. {
  195. int h;
  196. int c[4][4] = // copy of current state
  197. {
  198. {cur[0][0], cur[0][1], cur[0][2], cur[0][3]}, // Row 0
  199. {cur[1][0], cur[1][1], cur[1][2], cur[1][3]}, // Row 1
  200. {cur[2][0], cur[2][1], cur[2][2], cur[2][3]}, // Row 2
  201. {cur[3][0], cur[3][1], cur[3][2], cur[3][3]} // Row 3
  202. };
  203.  
  204. if (col == 0)
  205. return 100;
  206. else
  207. swap(c[row][col], c[row][col-1]);
  208.  
  209. // n++;
  210. h = calc(c, g);
  211. return h;
  212. }
  213.  
  214. // RIGHT FUNCTION
  215. int right (int cur[][4], int g[][4], int row, int col)
  216. {
  217. int h;
  218. int c[4][4] = // copy of current state
  219. {
  220. {cur[0][0], cur[0][1], cur[0][2], cur[0][3]}, // Row 0
  221. {cur[1][0], cur[1][1], cur[1][2], cur[1][3]}, // Row 1
  222. {cur[2][0], cur[2][1], cur[2][2], cur[2][3]}, // Row 2
  223. {cur[3][0], cur[3][1], cur[3][2], cur[3][3]} // Row 3
  224. };
  225.  
  226. if (col == 3)
  227. return 100;
  228. else
  229. swap(c[row][col], c[row][col+1]);
  230.  
  231. //n++;
  232. h = calc(c, g);
  233. return h;
  234. }
  235.  
  236. // UP FUNCTION
  237. int up (int cur[][4], int g[][4], int row, int col)
  238. {
  239. int h;
  240. int c[4][4] = // copy of current state
  241. {
  242. {cur[0][0], cur[0][1], cur[0][2], cur[0][3]}, // Row 0
  243. {cur[1][0], cur[1][1], cur[1][2], cur[1][3]}, // Row 1
  244. {cur[2][0], cur[2][1], cur[2][2], cur[2][3]}, // Row 2
  245. {cur[3][0], cur[3][1], cur[3][2], cur[3][3]} // Row 3
  246. };
  247.  
  248. if (row == 0)
  249. return 100;
  250. else
  251. swap(c[row][col], c[row-1][col]);
  252.  
  253. // n++;
  254. h = calc(c, g);
  255. return h;
  256. }
  257.  
  258. // DOWN FUNCTION
  259. int down (int cur[][4], int g[][4], int row, int col)
  260. {
  261. int h;
  262. int c[4][4] = // copy of current state
  263. {
  264. {cur[0][0], cur[0][1], cur[0][2], cur[0][3]}, // Row 0
  265. {cur[1][0], cur[1][1], cur[1][2], cur[1][3]}, // Row 1
  266. {cur[2][0], cur[2][1], cur[2][2], cur[2][3]}, // Row 2
  267. {cur[3][0], cur[3][1], cur[3][2], cur[3][3]} // Row 3
  268. };
  269.  
  270. if (row == 3)
  271. return 100;
  272. else
  273. swap(c[row][col], c[row+1][col]);
  274.  
  275. // n++;
  276. h = calc(c, g);
  277. return h;
  278. }
  279.  
  280. // CALCULATION FUNCTION
  281. int calc(int c[][4], int g[][4])
  282. {
  283. int i, j; // looping variables
  284. int h = 0; // value for heuristic function
  285.  
  286. for (i=0; i<=3; i++)
  287. {
  288. for (j=0; j<=3; j++)
  289. {
  290. if (c[i][j] != g[i][0] && c[i][j] != g[i][1] && c[i][j] != g[i][2] && c[i][j] != g[i][3])
  291. h++;
  292. }
  293. }
  294.  
  295. for (j=0; j<=3; j++)
  296. {
  297. for (i=0; i<=3; i++)
  298. {
  299. if (c[i][j] != g[0][j] && c[i][j] != g[1][j] && c[i][j] != g[2][j] && c[i][j] != g[3][j])
  300. h++;
  301. }
  302. }
  303.  
  304. return h;
  305. }
  306.  
  307. // LOWEST FUNCTION
  308. int lowest(int g[][4], int cur[][4], int L, int R, int U, int D, int row, int col)
  309. {
  310. int a[4] = {L, R, U, D}; // keeps track of the lowest values
  311. int op; // operator used
  312.  
  313. if (L < R) // if left is less than right - we must TOSS right.
  314. {
  315. int a[4] = {L, U, D, 200};
  316. if (L < U) // if left is less than up, we must TOSS up.
  317. {
  318. int a[4] = {L, D, 200, 200};
  319. }
  320. else if (L > U) // must toss l
  321. {
  322. int a[4] = {U, D, 200, 200};
  323. }
  324. else
  325. {
  326. // assume that L = U
  327. if (L < D)
  328. int a[4] = {L, U, 200, 200};
  329. else
  330. int a[4] = {L, U, D, 200};
  331. }
  332. }
  333. else if (L > R) // but if left is greater, then we must toss left!
  334. {
  335. int a[4] = {R, U, D, 200};
  336. if (R < U) // if left is less than up, we must TOSS up.
  337. {
  338. int a[4] = {R, D, 200, 200};
  339. }
  340. else if (R > U) // must toss l
  341. {
  342. int a[4] = {U, D, 200, 200};
  343. }
  344. else
  345. {
  346. // assume that R = U
  347. if (R < D)
  348. int a[4] = {R, U, 200, 200};
  349. else
  350. int a[4] = {R, U, D, 200};
  351. }
  352. }
  353.  
  354. op = zero(g, cur, a, L, R, U, D, row, col);
  355. return op;
  356. }
  357.  
  358. int zero(int g[][4], int cur[][4], int a[], int L, int R, int U, int D, int row, int col)
  359. {
  360. int hL, hR, hU, hD;
  361. int i, temp;
  362.  
  363. for (i=0; i<=3; i++)
  364. {
  365. if (a[i] == L)
  366. {
  367. col = col - 1;
  368. hL = (3 - row) + (3 - col);
  369. }
  370. else if (a[i] == R)
  371. {
  372. col = col + 1;
  373. hR = (3 - row) + (3 - col);
  374. }
  375. else if (a[i] == U)
  376. {
  377. row = row - 1;
  378. hR = (3 - row) + (3 - col);
  379. }
  380. else if (a[i] == D)
  381. {
  382. row = row + 1;
  383. hR = (3 - row) + (3 - col);
  384. }
  385. }
  386.  
  387. if (a[0] != L && a[1] != L && a[2] != L && a[3] != L)
  388. {
  389. hL = 100;
  390. }
  391. else if (a[0] != R && a[1] != R && a[2] != R && a[3] != R)
  392. {
  393. hR = 100;
  394. }
  395. else if (a[0] != U && a[1] != U && a[2] != U && a[3] != U)
  396. {
  397. hU = 100;
  398. }
  399. else if (a[0] != D && a[1] != D && a[2] != D && a[3] != D)
  400. {
  401. hD = 100;
  402. }
  403.  
  404. // now that all the proper values should be assigned, do proper checking
  405.  
  406. if (hL < hR && hL < hU && hL < hD)
  407. {
  408. return 1;
  409. }
  410. else if (hR < hL && hR < hU && hR < hD)
  411. {
  412. return 2;
  413. }
  414. else if (hU < hL && hU < hR && hU < hD)
  415. {
  416. return 3;
  417. }
  418. else if (hD < hL && hD < hR && hD < hU)
  419. {
  420. return 4;
  421. }
  422. else
  423. {
  424. temp = count(g, cur, a, L, R, U, D, row, col);
  425. return temp;
  426. }
  427.  
  428. }
  429.  
  430. int count(int g[][4], int cur[][4], int a[], int L, int R, int U, int D, int row, int col)
  431. {
  432. int i, j, k; // looping variables
  433. int wL = 0;
  434. int wR = 0;
  435. int wU = 0;
  436. int wD = 0;
  437. int c[4][4] = // copy of current state
  438. {
  439. {cur[0][0], cur[0][1], cur[0][2], cur[0][3]}, // Row 0
  440. {cur[1][0], cur[1][1], cur[1][2], cur[1][3]}, // Row 1
  441. {cur[2][0], cur[2][1], cur[2][2], cur[2][3]}, // Row 2
  442. {cur[3][0], cur[3][1], cur[3][2], cur[3][3]} // Row 3
  443. };
  444.  
  445. // loop through both the current and goal. save the number! the lowest one will get worked on.
  446. for (i=0; i<=3; i++)
  447. {
  448. if (a[i] == L)
  449. {
  450. swap(c[row][col], c[row][col-1]);
  451. for (j=0; j<=3; j++)
  452. {
  453. for (k=0; k<=3; k++)
  454. {
  455. if (c[j][k] != g[j][k])
  456. wL++;
  457. }
  458. }
  459. }
  460. else if (a[i] == R)
  461. {
  462. swap(c[row][col], c[row][col+1]);
  463. for (j=0; j<=3; j++)
  464. {
  465. for (k=0; k<=3; k++)
  466. {
  467. if (c[j][k] != g[j][k])
  468. wR++;
  469. }
  470. }
  471. }
  472. else if (a[i] == U)
  473. {
  474. swap(c[row][col], c[row-1][col]);
  475. for (j=0; j<=3; j++)
  476. {
  477. for (k=0; k<=3; k++)
  478. {
  479. if (c[j][k] != g[j][k])
  480. wU++;
  481. }
  482. }
  483. }
  484. else if (a[i] == D)
  485. {
  486. swap(c[row][col], c[row+1][col]);
  487. for (j=0; j<=3; j++)
  488. {
  489. for (k=0; k<=3; k++)
  490. {
  491. if (c[j][k] != g[j][k])
  492. wD++;
  493. }
  494. }
  495. }
  496. }
  497.  
  498. if (a[0] != L && a[1] != L && a[2] != L && a[3] != L)
  499. {
  500. wL = 100;
  501. }
  502. else if (a[0] != R && a[1] != R && a[2] != R && a[3] != R)
  503. {
  504. wR = 100;
  505. }
  506. else if (a[0] != U && a[1] != U && a[2] != U && a[3] != U)
  507. {
  508. wU = 100;
  509. }
  510. else if (a[0] != D && a[1] != D && a[2] != D && a[3] != D)
  511. {
  512. wD = 100;
  513. }
  514.  
  515. if (wL < wR && wL < wU && wL < wD)
  516. {
  517. return 1;
  518. }
  519. else if (wR < wL && wR < wU && wR < wD)
  520. {
  521. return 2;
  522. }
  523. else if (wU < wL && wU < wR && wU < wD)
  524. {
  525. return 3;
  526. }
  527. else if (wD < wL && wD < wR && wD < wU)
  528. {
  529. return 4;
  530. }
  531.  
  532. }
  533.  
  534. // PRINT FUNCTION
  535.  
  536. void print(int c[][4], int h, string op)
  537. {
  538. cout << "Operator: " << op << endl << endl;
  539. cout << right << setw(2) << c[0][0] << " " << setw(2) << c[0][1] << " " << setw(2) << c[0][2] << " " << setw(2) << c[0][3] << endl;
  540. cout << setw(2) << c[1][0] << " " << setw(2) << c[1][1] << " " << setw(2) << c[1][2] << " " << setw(2) << c[1][3] << endl;
  541. cout << setw(2) << c[2][0] << " " << setw(2) << c[2][1] << " " << setw(2) << c[2][2] << " " << setw(2) << c[2][3] << endl;
  542. cout << setw(2) << c[3][0] << " " << setw(2) << c[3][1] << " " << setw(2) << c[3][2] << " " << setw(2) << c[3][3];
  543. cout << endl << endl << "h(S) = " << h << endl;
  544. //len++;
  545. }
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
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!