Last active
October 29, 2023 06:39
-
-
Save maksmakuta/941eee6b00b451b24033232d989a58fa 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
| /** | |
| * You can use https://play.kotlinlang.org/ to test this code | |
| */ | |
| import kotlin.random.Random | |
| import kotlin.random.nextInt | |
| import kotlin.time.measureTime | |
| data class Edge( | |
| val a : Int, | |
| val b : Int, | |
| val w : Int | |
| ){ | |
| fun print(){ | |
| println("$a -{$w}- $b") | |
| } | |
| } | |
| class Graph(val size : Int){ | |
| private val data = arrayListOf<Edge>() | |
| fun add(edge: Edge){ | |
| if(data.find { it.a == edge.a && it.b == edge.b } == null && | |
| data.find { it.a == edge.b && it.b == edge.a } == null) | |
| data.add(edge) | |
| } | |
| fun neighbours(i : Int) : List<Edge>{ | |
| val t = data.filter { it.b == i }.map { Edge(it.b,it.a,it.w) } | |
| return data.filter { it.a == i } + t | |
| } | |
| fun print(){ | |
| println("size -> $size") | |
| println("cons -> ${data.size}") | |
| println("cons : ") | |
| data.forEach { | |
| it.print() | |
| } | |
| } | |
| } | |
| fun gen(size : Int,poss : Int,weights : IntRange,seed : Long = 0L) : Graph{ | |
| val rand = Random(seed) | |
| fun newEdge(i : Int) : Edge{ | |
| val dest = rand.nextInt(1..size) | |
| val w = rand.nextInt(weights) | |
| return if(dest != i){ | |
| Edge(i,dest,w) | |
| }else{ | |
| newEdge(i) | |
| } | |
| } | |
| val graph = Graph(size) | |
| for(i in 1..size) { | |
| var count = 0 | |
| for (j in 1..size) { | |
| if(rand.nextInt(1,101) < poss && i != j){ | |
| val w = rand.nextInt(weights) | |
| graph.add(Edge(i,j,w)) | |
| count++ | |
| } | |
| } | |
| if(count == 0){ | |
| graph.add(newEdge(i)) | |
| } | |
| } | |
| return graph | |
| } | |
| fun walker(graph: Graph,start : Int, end : Int){ | |
| println() | |
| if (start in 0..graph.size && end in 0..graph.size && start != end) { | |
| val list = mutableListOf<Int>() | |
| var total = 0 | |
| var curr = start | |
| var comps = 0 | |
| val t = measureTime { | |
| while (true) { | |
| if (curr !in list) { | |
| list.add(curr) | |
| val neighbours = graph.neighbours(curr) | |
| if (neighbours.isNotEmpty()) { | |
| var dist = Int.MAX_VALUE | |
| var t = 0 | |
| for (n in neighbours) { | |
| if ((n.b == end || n.w < dist) && t != end) { | |
| println(" ${n.a} -[${n.w}]- ${n.b} ") | |
| comps++ | |
| t = n.b | |
| dist = n.w | |
| } | |
| } | |
| curr = t | |
| if (dist != Int.MAX_VALUE) | |
| total += dist | |
| } | |
| if (curr == end) { | |
| list.add(end) | |
| println("found path") | |
| break | |
| } | |
| } else { | |
| println("limit") | |
| break | |
| } | |
| } | |
| println() | |
| println(list.joinToString("-") { it.toString() }) | |
| println("distance : $total") | |
| println("moves : ${list.size - 1}") | |
| println("comps : $comps") | |
| } | |
| println("time : ${t.inWholeMilliseconds} ms") | |
| println("time : ${t.inWholeNanoseconds} ns") | |
| } else { | |
| when (start) { | |
| end -> println("Error: start == end") | |
| !in 0..<graph.size -> println("Error: start is out of graph") | |
| else -> println("Error: end is out of graph") | |
| } | |
| } | |
| } | |
| fun main() { | |
| val seed = Random.nextLong() | |
| println("seed : $seed") | |
| val graph = gen(50,15,100..1000,seed) | |
| //graph.print() | |
| walker(graph,1,50) | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment