maksmakuta · October 29, 2023 07:03 · Oct 29, 2023
diff --git a/pathwalker_v2.kt b/pathwalker_v2.kt
@@ -0,0 +1,135 @@
+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)
+    val subList = mutableListOf<Edge>()
+    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)
+                subList.add(Edge(i,j,w))
+                count++
+            }
+        }
+        if(count == 0){
+            subList.add(newEdge(i))
+        }
+        subList.sortedBy { it.w }.forEach {
+            graph.add(it)
+        }
+        subList.clear()
+    }
+    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) {
+                list.add(curr)
+                val neighbours = graph.neighbours(curr)
+                if (neighbours.isNotEmpty()) {
+                    var dist = Int.MAX_VALUE
+                    var t = 0
+                    for (i in neighbours.indices) {
+                        val n = neighbours[i]
+                        comps++
+                        if(n.b !in list) {
+                            if ((n.b == end || n.w < dist) && t != end) {
+                                println(" ${n.a} -[${n.w}]- ${n.b} ")
+                                t = n.b
+                                dist = n.w
+                            }else{
+                                break
+                            }
+                        }
+                    }
+                    curr = t
+                    if (dist != Int.MAX_VALUE)
+                        total += dist
+                }
+                if (curr == end) {
+                    list.add(end)
+                    println("found path")
+                    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 = 8714362708517061972L//Random.nextLong()
+    println("seed : $seed")
+    val graph = gen(50,5,100..1000,seed)
+    //graph.print()
+    walker(graph,1,50)
+}