Shortest path algorithm

import org.junit.Test import kotlin.coroutines.* import kotlinx.coroutines.* import kotlin.test.* import java.util.Date import org.junit.Before import java.lang.Math.pow import java.lang.Math.sqrt import java.util.* import kotlin.test.assertEquals class MarkingWayOnMapTests { @Test fun `Markes start and end as part of way`() { val mapString = """ .................... .........XS......... .................... """.trimIndent() val marked = """ .................... .........**......... .................... """.trimIndent() assertEquals(marked, addPath(mapString)) } @Test fun `Straight way is straight`() { val mapString = """ .................... .....X..........S... .................... """.trimIndent() val marked = """ .................... .....************... .................... """.trimIndent() assertEquals(marked, addPath(mapString)) } @Test fun `Use cross moves`() { val mapString = """ ........... .......S... ........... ........... ........... ........... ..X........ """.trimIndent() val marked = """ ........... .......*... ......*.... .....*..... ....*...... ...*....... ..*........ """.trimIndent() assertEquals(marked, addPath(mapString)) } @Test fun `Mark way around wall`() { val mapString = """ .................... ......X...B......... ..........B......... ........BBB....S.... .................... """.trimIndent() val marked = """ ........***......... ......**..B*........ ..........B.*....... ........BBB..***.... .................... """.trimIndent() assertEquals(marked, addPath(mapString)) } @Test fun `Mark way around wall 2`() { val mapString = """ ..........B......... ......X...B......... ..........B......... ........BBB....S.... .................... """.trimIndent() val marked = """ ..........B......... ......*...B......... ......*...B......... .......*BBB*****.... ........***......... """.trimIndent() assertEquals(marked, addPath(mapString)) } @Test fun `Mark way on labirynth`() { val mapString = """ BB..B...B...BBBBB... ....B.X.BBB.B...B.B. ..BBB.B.B.B.B.B.B.B. ....B.BBB.B.B.BS..B. BBB.B...B.B.BBBBBBB. ..B...B............. """.trimIndent() val marked = """ BB..B...B...BBBBB.*. ....B.*.BBB.B...B*B* ..BBB*B.B.B.B.B.B*B* ....B*BBB.B.B.B**.B* BBB.B.**B.B.BBBBBBB* ..B...B.***********. """.trimIndent() assertEquals(marked, addPath(mapString)) } @Test fun `Navigate on forest`() { val mapString = """ ..B....B..B.....BB.BBB......B..B.......B....BBB.....BB.B....BB.BB..BB.......BBB...BBBBB.....B...B..B ....BB.....B.B.B....BBB..........BBB.B....BB..B.B..B...BBBBBBBB..BB.B..........B..B.......B.BB..B..B B.......S.B.B.....B.........B.B..B...B...BB.BB.B...B.B.B...B..BB.BB.....BB..B........BB.B..B......BB .......B..BBBB.B.....B....B...B.B..B...B...BB.B.BBB..BBB....B......B....B..B.B.BB......BB....BB....B ......B.BB.B.B......B..BBBB.B..BBBBB..B.B.BB.BBBBBB.BB.B..B.BBB..B......B......B....B........B.B..B. B.....B......BB..BBB..B.B....BB.BBBBB.....BB..B..B..BB..BB..BB.BB......BB....B.BB.B...B..B......B... B.B.B.................BB.B.B....BB.....BB.BB...BB.BB..B.B.......B......BB...BB.BB...BB...BB..B...B.. BB...BB.......BBBB........BBB..BBB.B.B...B..B....B...BBB..........B..B..B..BB..BB...BB..B...BBBBB..B ....B..B....B...B.B.B...B.BB........B....BBB..........B...B.BB.B..BB..B.......BB...B.B..B...B..B.... .........B.....BB.B.....B...BB.B.B.BBBB....B.....B.......BBBBB....B.B............BB.....B........B.. .B..B.B.B...............B..B.B.....B.BB.BB.B...B.BBB....BB.......BB...B.B.BBBB......B...B.....B..... .B..B.....B.B..BB....BB.......B.B.BBB.B.....B..BB.B...B.....B..B...B..B.B..B.BB......B..B..B.....B.B .......B.BBB.BB.......B.BBB....B...BB...B..........B.......B...B.....BBBB.B....B..B..BB.B.B.B...B.B. B.B..BB.........BB.......BB.....B.BB..BB..BBB..B...BB....B.BBB..B....B.B....B.BBBB..B..BB.B......... .B..BB......B...B..BB..BBB.B.B.B.BB.B.B..BBB.BBBB.B..B......BB.....BB.....B....BB....B..BB.......... B.B..B...B.B.B..B.B..B......B.B.B.BBB.B.B.B....B........BB..B....BB....BBB.BB.B....B...B....BBB..... .B..BB...B.....B.B.B.BBB.B.........B...B..B.B...BBBBB....B.BBB..BB...........B.....BBBB....B.....BB. .B......BB...BB.......B..B.B....B.BBB...BB.B......B.BBB..B....BB....BB....B.........B.B.B...BB....B. B..B...B...B......B.....B......B..B..B....B.B.B.........B.BBB.B..B..BB..B..BB..B.....B..BB.BB.B....B B.BB...B..BB..B.BB.B........B.BB......B...B.B..BB.BB.B.B......B...B..B.B...BBB...BBB.........X..B..B .B.B.B.....B.BB..BB...BB.....B.BB.....B...BB...BBB..B..BBB..B.B.....B......B.....BB.....B..B.B..B... BB...B.B..BB..B.B......B.....B....BBB...BBB.B...B.....B..BBBB.B..B..BBBBBB....BB.BB.B....BB.BB.BBB.. ..B....B..BB........B..BB..BB..B...B.B..BB.B....BBB..B.....B......B...........BBBB.......B.BB....B.. BB....BBB...B.B...B.....B.B..B.B....B.B.B...B.B..BBBBBB.B....B...BB..BBB...B.BB....B.........BB..B.. """.trimIndent() val marked = """ ..B....B..B.....BB.BBB......B..B.......B....BBB.....BB.B....BB.BB..BB.......BBB...BBBBB.....B...B..B ....BB.....B.B.B....BBB..........BBB.B....BB..B.B..B...BBBBBBBB..BB.B..........B..B.......B.BB..B..B B.......*.B.B.....B.........B.B..B...B...BB.BB.B...B.B.B...B..BB.BB.....BB..B........BB.B..B......BB .......B.*BBBB.B.....B....B...B.B..B...B...BB.B.BBB..BBB....B......B....B..B.B.BB......BB....BB....B ......B.BB*B.B......B..BBBB.B..BBBBB..B.B.BB.BBBBBB.BB.B..B.BBB..B......B......B....B........B.B..B. B.....B....**BB..BBB..B.B....BB.BBBBB.....BB..B..B..BB..BB..BB.BB......BB....B.BB.B...B..B......B... B.B.B........*********BB.B.B....BB.....BB.BB...BB.BB..B.B.......B......BB...BB.BB...BB...BB..B...B.. BB...BB.......BBBB....***.BBB..BBB.B*B...B..B....B...BBB..........B..B..B..BB..BB...BB..B...BBBBB..B ....B..B....B...B.B.B...B*BB********B****BBB..........B...B.BB.B..BB..B.......BB...B.B..B...B..B.... .........B.....BB.B.....B.**BB.B.B.BBBB..*.B.....B.......BBBBB....B.B............BB.....B........B.. .B..B.B.B...............B..B.B.....B.BB.BB*B...B.BBB....BB.......BB...B.B.BBBB......B...B.....B..... .B..B.....B.B..BB....BB.......B.B.BBB.B....*B..BB.B***B....*B..B...B..B.B..B.BB......B..B..B.....B.B .......B.BBB.BB.......B.BBB....B...BB...B...*******B..*****B***B.....BBBB.B....B..B..BB.B.B.B...B.B. B.B..BB.........BB.......BB.....B.BB..BB..BBB..B...BB....B.BBB.*B....B.B....B.BBBB..B..BB.B......... .B..BB......B...B..BB..BBB.B.B.B.BB.B.B..BBB.BBBB.B..B......BB..***BB.....B....BB....B..BB.......... B.B..B...B.B.B..B.B..B......B.B.B.BBB.B.B.B....B........BB..B....BB****BBB.BB.B....B...B....BBB..... .B..BB...B.....B.B.B.BBB.B.........B...B..B.B...BBBBB....B.BBB..BB.....******B.....BBBB....B.....BB. .B......BB...BB.......B..B.B....B.BBB...BB.B......B.BBB..B....BB....BB....B..*******B.B.B...BB....B. B..B...B...B......B.....B......B..B..B....B.B.B.........B.BBB.B..B..BB..B..BB..B....*B..BB.BB.B....B B.BB...B..BB..B.BB.B........B.BB......B...B.B..BB.BB.B.B......B...B..B.B...BBB...BBB.*********..B..B .B.B.B.....B.BB..BB...BB.....B.BB.....B...BB...BBB..B..BBB..B.B.....B......B.....BB.....B..B.B..B... BB...B.B..BB..B.B......B.....B....BBB...BBB.B...B.....B..BBBB.B..B..BBBBBB....BB.BB.B....BB.BB.BBB.. ..B....B..BB........B..BB..BB..B...B.B..BB.B....BBB..B.....B......B...........BBBB.......B.BB....B.. BB....BBB...B.B...B.....B.B..B.B....B.B.B...B.B..BBBBBB.B....B...BB..BBB...B.BB....B.........BB..B.. """.trimIndent() assertEquals(marked, addPath(mapString)) } } // Your code starts here //sampleStart fun addPath(mapString: String): String { TODO() } //sampleEnd
Save Restore Add own tests Switch to main Feedback

Your task is to write an algorithm to find the best way on a map and to return this map with marked best way. The starting point is marked by S, end by X. You can only move on dots ., and you cannot go outside of the map. B is an obstacle. Suppose that weight of straight step is 1, and of diagonal step is 1.5. When you find the best way, you should mark it on the map by replacing all nodes that should be visited with *. For example, your function for the following map:

...........
.......S...
...........
...........
...........
...........
..X........

Should return the following result:

...........
.......*...
......*....
.....*.....
....*......
...*.......
..*........

In case of obstacles, it should go around:

....................
......X...B.........
..........B.........
........BBB....S....
....................
.......****.........
......*...B*........
..........B.*.......
........BBB..***....
....................

But it should not go outside of the map:

......X...B.........
..........B.........
........BBB....S....
....................
......*...B.........
.......*..B.........
.......*BBB*****....
........***.........

You can choose any algorithm you want, but performance will be taken into account. Though you don’t need to use any more advanced algorithm then A*. Your algorithm should always give the correct result, and it should not be random. If a way chosen by your algorithm is optimal but different then in a unit test, it is fine. You can adjust this unit test. Though if you decided to implement A*, the chosen way should always be the same as in unit tests.

Find more instructions how to solve it here.


Next