座標がループを作成するかチェックする

Question

ウォーカーのx/y座標のタプルを配列ArrayBuffet((Int, Int))に格納します。 (0,0)と(2,1)との間の旅を表し

手順((0,0), (0,1), (1,1), (2,1))、((0,0), (1,1), (2,1))、とすることができる等

トラブルは、私は歩行者がサークルに移動しているかどうかをテストするための方法が必要です。

など。 (0,0)から(0,1)への歩行を考えてください。歩行者のパスは((0,0), (1,0), (1,-1), (0,0), (0,1))です。歩行者は円で移動します。

def hasLoop(path: ArrayBuffer[(Int,Int)]): Boolean = { 
    if (path.length < 3) return false 
    else { 
     for i <- 0 to path.length - 1 { 
     val temp = path 
     temp.remove(i) 
     if (temp.contains(i)) return true 
     } 
     return false 
    } 
    } 

歩行者が単一の旅に複数回訪問座標場合、方法。しかし、歩行者が(0,0)から(0,1)、さらには(0,2)に移動した後、同じパスを(0,1)経由で返しても、それはループとして見なすべきではありません。

誰も私のisLoop方法の解決策を提供できますか？

Answer 1

私が正しく理解していれば、コレクションが同じ値を2回以上持っているかどうかを調べるだけです。

@annotation.tailrec 
def hasLoop(path: Seq[(Int, Int)]): Boolean = 
    if (path.size < 2) false 
    else if (path.tail.contains(path.head)) true 
    else hasLoop(path.tail) 

println(hasLoop(Array((0, 0), (0, 1)))) 
println(hasLoop(Array((0, 0), (1, 0), (1, -1), (0, 0), (0, 1)))) 

Answer 2

わからない、それは最もエレガントな解決策ですが、私はそれは何が必要ないと思う：

// some type aliases to make this more readable, can do without them too 
type Vertex = (Int,Int) 
type Edge = (Vertex, Vertex) 

def hasLoop(path: Array[Vertex]): Boolean = { 
    // create all edges - connections between one vertex and the next one in path 
    val edges: Array[Edge] = path.zip(path.drop(1)) 

    // fold right searching for PREVIOUS edges for which SRC equals current edge's DESTINATION, 
    // but DESTINATION does not equal current edge's SOURCE 
    val foldResult: (Seq[Edge], Boolean) = edges.foldLeft((Seq[Edge](), false)) { 
    case ((visited, found), e) => 
     (visited :+ e, found || visited.exists(oldE => oldE._1 == e._2 && oldE._2 != e._1)) 
    } 

    foldResult._2 // return the boolean result 
} 

println(hasLoop(Array((0,0), (1,0), (1,-1), (0,0), (0,1)))) // true 
println(hasLoop(Array((0,0), (1,0), (1,-1), (0,0)))) // true 
println(hasLoop(Array((0,0), (1,0), (1,-1), (1,0), (0,0)))) // false 
println(hasLoop(Array((0,0), (1,0), (1,-1)))) // false