Posted by admin June 26th 2018 at 20:06

An out-of-control robot is placed on a plane, and it takes N random steps.
At each step, the robot chooses one of four directions randomly and moves one unit in that direction.
The probabliities of the robot choosing north, south, east or west are north, south, east and west percent, respectively.
the robot's path is considered simple if it never visits the same point more than once.
(The robot's starting point is always the first visited point.)
Return a double contatining the probablity that the robot's path is simple.
For example, "EENE" and "ENW" are simple, but "ENWS" and "WWWWSNE" are not('E', 'W', 'N' and 'S' represent east, west, north and south, respectively).

var n : Int = 2

var east : Int = 25

var west : Int = 25

var south : Int = 25

var north : Int = 25


var directions : [Character] = ["E", "W", "S", "N"]


var allTrace = [[Character]]()

var trace : [Character] = [Character](repeating: "0", count: n)


func addArray(_ move : Int, _ round : Int) {

    var nCount : Int = round

    let index : Int = n - nCount

    trace[index] = directions[move]

    if round == 1 {

        allTrace.append(trace)

    }else{

        nCount = nCount - 1

        depthFirst(nCount)

    }

}


func depthFirst(_ round : Int) {

    

    for move in 0...3 {

        if move == 0 {

            addArray(move, round)

        }else if move == 1 {

            addArray(move, round)

        }else if move == 2 {

            addArray(move, round)

        }else{

            addArray(move, round)

        }

    }

}

depthFirst(n)


var allPoint : [[Int]] = [[Int]]()

var percent : Double = 0.0


var percentE : Double = Double(east)/Double(100)

var percentW : Double = Double(west)/Double(100)

var percentS : Double = Double(south)/Double(100)

var percentN : Double = Double(north)/Double(100)


for aTrace in allTrace {

    var point : [Int] = [Int](repeating: 0, count: 2)

    var flag : Bool = true


    for char in aTrace {

        

        if char == "E" {

            point[0] = point[0] + 1

        }else if char == "W"{

            point[0] = point[0] - 1

        }else if char == "S"{

            point[1] = point[1] - 1

        }else{

            point[1] = point[1] + 1

        }

        allPoint.append(point)

    }

    

    for i in 0...allPoint.count-2 {

        for j in (i+1)...allPoint.count-1 {

            if allPoint[i] == allPoint[j] || allPoint[i] == [0,0] || allPoint[j] == [0,0] {

                flag = false

            }

        }

    }

    

    if(flag){

        

        var countE : Int = 0

        var countW : Int = 0

        var countS : Int = 0

        var countN : Int = 0

        

        for ch in aTrace {

            if ch == "E" {

                countE = countE + 1

            }else if ch == "W"{

                countW = countW + 1

            }else if ch == "S"{

                countS = countS + 1

            }else{

                countN = countN + 1

            }

        }


        percent = percent + (pow(percentE, Double(countE))) * pow(percentW, Double(countW)) * pow(percentS, Double(countS)) * pow(percentN, Double(countN))

    }

    allPoint.removeAll()   

}

print(percent)