Created
May 12, 2020 18:35
-
-
Save wibisono/42c121901845bbd2f2651135a184c9dd to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import scala.collection.mutable | |
| import Board._ | |
| case class Board(table: Array[Int], r: Int, c: Int, parent: List[String] = List()) { | |
| def cloneSwap(r: Int, c: Int, rr: Int, cc: Int) = { | |
| val cTable = table.clone | |
| cTable(r * 4 + c) = table(rr * 4 + cc) | |
| cTable(rr * 4 + cc) = table(r * 4 + c) | |
| cTable | |
| } | |
| def up() = | |
| if (r > 0) { Some(Board(cloneSwap(r, c, r - 1, c), r - 1, c, "u" :: parent)) | |
| } else None | |
| def down() = | |
| if (r < 3) { Some(Board(cloneSwap(r, c, r + 1, c), r + 1, c, "d" :: parent)) | |
| } else None | |
| def left() = | |
| if (c > 0) { Some(Board(cloneSwap(r, c, r, c - 1), r, c - 1, "l" :: parent)) | |
| } else None | |
| def right() = | |
| if (c < 3) { Some(Board(cloneSwap(r, c, r, c + 1), r, c + 1, "r" :: parent)) | |
| } else None | |
| def format: String = { | |
| table.sliding(4, 4).toList.map(_.map(i ⇒ f"$i%4d").mkString).mkString("\n") | |
| } | |
| // Manhattan distance | |
| def heuristic() = { | |
| val posF = finalBoard.positionMap | |
| val posT = positionMap | |
| var res = 0; | |
| for (i ← 0 to 15) { | |
| val (x, y) = posF(i) | |
| val (xx, yy) = posT(i) | |
| res += (Math.abs(x - xx) + Math.abs(y - yy)) | |
| } | |
| res | |
| } | |
| def key = table.mkString(",") | |
| def travelled() = parent.length | |
| // Playing with weight of heuristic vs travelled so far. Giving equal weight take too long. | |
| // Heuristic only will converge too fast on a longer than 52 steps solution. | |
| def aStar() = heuristic() * 5 + travelled() * 4 | |
| // Find children/neighbour that is not himself. | |
| def children: List[Board] = List(this.up(), this.down(), this.right(), this.left()).flatten | |
| // Map number to positions | |
| lazy val positionMap: Map[Int, (Int, Int)] = { | |
| val res = mutable.Map[Int, (Int, Int)]() | |
| for (x ← 0 to 3; y ← 0 to 3) { | |
| res(table(x * 4 + y)) = (x, y) | |
| } | |
| res.toMap | |
| } | |
| } | |
| object Board { | |
| val finalBoard = Board(Array(Array(1, 2, 3, 4), Array(5, 6, 7, 8), Array(9, 10, 11, 12), Array(13, 14, 15, 0)).flatten, 3, 3) | |
| val startEasy = Board(Array(Array(15, 14, 1, 6), Array(9, 11, 4, 12), Array(0, 10, 7, 3), Array(13, 8, 5, 2)).flatten, 2, 0) | |
| val startHard = Board(Array(Array(0, 12, 9, 13), Array(15, 11, 10, 14), Array(3, 7, 2, 5), Array(4, 8, 6, 1)).flatten, 0, 0) | |
| } | |
| object Solver extends App { | |
| implicit val ob = new Ordering[Board] { override def compare(x: Board, y: Board) = { y.aStar() - x.aStar() } } | |
| def solve(initBoard: Board) { | |
| val start = System.currentTimeMillis() | |
| var found = false | |
| var head = initBoard | |
| val pq: mutable.PriorityQueue[Board] = new mutable.PriorityQueue() | |
| pq.addOne(head) | |
| val visited = mutable.HashSet[String]() | |
| var explore = 0 | |
| while (pq.nonEmpty && !found) { | |
| head = pq.dequeue() | |
| visited.add(head.key) | |
| if (!head.key.equals(finalBoard.key)) { | |
| val newChildren = head.children.filter(b ⇒ !visited.contains(b.key)) | |
| visited.addAll(newChildren.map(_.key)) | |
| pq.enqueue(newChildren: _*) | |
| if (explore % 10000 == 0) | |
| println(s"# $explore: A* ${head.aStar()} g:${head.travelled()} h:${head.heuristic()} q.size = ${pq.size}") | |
| explore += 1 | |
| } else found = true | |
| } | |
| if (found) { | |
| println(s"Exploring $explore states, found solution with length ${head.parent.length} for board:") | |
| println(initBoard.format) | |
| println(head.parent.mkString.reverse) | |
| } | |
| println("Total time: " + (System.currentTimeMillis() - start) / 1000.0 + " seconds") | |
| } | |
| solve(startEasy) | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment