// Updated for this challenge: // https://www.sololearn.com/post/163999 // This challenge wants you to challenge // yourself. Think of any coding challenge // but use ONLY the A* algorithm to solve it. // https://googleweblight.com/i?u=https://en.m.wikipedia.org/wiki/A*_search_algorithm&hl=en-de // A* algoritm // starting with this code: // https://rosettacode.org/wiki/A*_search_algorithm#Kotlin // Method to extend the Int class with an // absolute value. fun Int.abs() = Math.abs(this) // Data class to hold a point in the matrix. data class Point(val row: Int, val column: Int) { // Method to generate a display string. override fun toString() = "($row, $column)" } // Point // Class to handle a matrix with a A* search // of a path. Properties are the set of // blocked points, a score beyond any we // might find, the range of rows, the range // of columns, a list of point offsets for // any move, and the final path found. class Matrix(width: Int, height: Int, private val barriers: Set) { private val MAXIMUM = 99999999 private val rows = 0 until height private val columns = 0 until width private val moves = listOf( Point(1, 0), Point(-1, 0), Point(0, 1), Point(0, -1), Point(1, 1), Point(-1, 1), Point(1, -1), Point(-1, -1)) private val path = mutableListOf() // Method to test a point for being blocked. private fun blocked(position: Point) = barriers.contains(position) // Method to return the cost of making the // step. If blocked, huge, else cheap. private fun cost(from: Point, to: Point) = if (blocked(to)) MAXIMUM else 1 // Method to calculate the distance between // two points. private fun distance( start: Point, finish: Point): Int { val row = (start.row-finish.row).abs() val column = (start.column- finish.column).abs() return row+column-2*minOf(row, column) } // distance // Method to generate all neighbors of // our point. Take our offsets, add our // starting point, and filter out those // beyond the matrix. private fun neighbors(position: Point) = moves.map { Point(position.row+it.row, position.column+it.column) }. filter { valid(it) } // Method to test a point for being within // the matrix. private fun valid(it: Point) = it.row in rows && it.column in columns // Method to search a path through the // matrix using the A* algorithm. fun search(start: Point, finish: Point): Pair, Int> { // Function to generate the path selected. // Start at the end and backtrack to the // start stuffing the current point at // the front of our list. fun paths(position: Point, from: Map): List { var current = position path.add(0, current) while (from.containsKey(current)) { current = from.getValue(current) path.add(0, current) } // while return path.toList() } // paths // Clear our path incase this is not // our first attempt. The starting // point is in the opened set. The // closed set is empty. The cost to // our start is free placed in our // actual cost map. The estimate the // cost to the finish map gets our // start. A map of steps on the path // is empty. path.clear() val opened = mutableSetOf(start) val closed = mutableSetOf() val actual = mutableMapOf(start to 0) val estimated = mutableMapOf( start to distance(start, finish)) val from = mutableMapOf() // While there are points to process, // do so. while (opened.size > 0) { // Find the cheapest next step. // If we have reached the end, // generate the path we took and // it's cost to return. val position = opened.minBy { estimated.getValue(it) }!! if (position == finish) return Pair(paths(position, from), estimated.getValue(finish)) // Remove the point from opened and // put it into closed. opened.remove(position) closed.add(position) // Get the neighbors of our point. // Toss those already closed. For // all the remaining neighbors, // see if this path is cheaper than // any seen so far. neighbors(position).filterNot { closed.contains(it) }.forEach { neighbor -> // Get the cost to this neighbor // via this path. If it is cheaper // than the previous path, use it. // Add the neighbor, if needed, to // our opened set. Add or update // the neighbor in our maps to be // from the point, with the actual // cost, and with the estimated cost. val score = actual.getValue( position)+cost( position, neighbor) if (score < actual. getOrDefault(neighbor, MAXIMUM)) { if (!opened.contains(neighbor)) opened.add(neighbor) from.put(neighbor, position) actual.put(neighbor, score) estimated.put(neighbor, score+distance( neighbor, finish)) } // if } // forEach } // while // On failure to find a valid path, cause // an exception. throw IllegalStateException("No Path "+ "from Start $start to Finish $finish") } // search // Method to generate the matrix for // display. override fun toString(): String { var result = "" for (row in rows) { for (column in columns) result += when (Point(row, column)) { path[0] -> "s" path[path.size-1] -> "e" in path -> "." in barriers -> "X" else -> "-" } // when result += "\n" } // for return result } // toString } // Matrix // Main function for this challenge. Create // our matrix, search a path, and display // the result. Search second path and display. fun main(args: Array) { val matrix = Matrix(8, 8, setOf(Point(2, 4), Point(2, 5), Point(2, 6), Point(3, 6), Point(4, 6), Point(5, 6), Point(5, 5), Point(5, 4), Point(5, 3), Point(5, 2), Point(4, 2), Point(3, 2))) val (path1, cost1) = matrix.search( Point(0, 0), Point(7, 7)) println("Cost: $cost1; Path: $path1; The "+ "path shown by periods from start (s)"+ " to end (e), with dashes open, while"+ " X is blocked.") println(matrix) val (path2, cost2) = matrix.search( Point(7, 0), Point(0, 7)) println("Cost: $cost2; Path: $path2.") println(matrix) } // main

A* ch