Skip to content

Instantly share code, notes, and snippets.

@maksmakuta

maksmakuta/pathwalker.kt

Last active October 29, 2023 06:39
Show Gist options
  • Save maksmakuta/941eee6b00b451b24033232d989a58fa to your computer and use it in GitHub Desktop.
Save maksmakuta/941eee6b00b451b24033232d989a58fa to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. maksmakuta revised this gist Oct 29, 2023. 1 changed file with 4 additions and 0 deletions.
    4 changes: 4 additions & 0 deletions pathwalker.kt
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,7 @@
    /**
    * You can use https://play.kotlinlang.org/ to test this code
    */

    import kotlin.random.Random
    import kotlin.random.nextInt
    import kotlin.time.measureTime
  2. maksmakuta created this gist Oct 29, 2023.
    130 changes: 130 additions & 0 deletions pathwalker.kt
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,130 @@
    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)
    }