[LeetCode] 1041. Robot Bounded In Circle
===
###### tags: `LeetCode`

## 題目
On an infinite plane, a robot initially stands at `(0, 0)` and faces north. The robot can receive one of three instructions:

- `"G"`: go straight 1 unit;
- `"L"`: turn 90 degrees to the left;
- `"R"`: turn 90 degrees to the right.

The robot performs the `instructions` given in order, and repeats them forever.

Return `true` if and only if there exists a circle in the plane such that the robot never leaves the circle.

**Example 1:**

Input: instructions = "GGLLGG"
Output: true
Explanation: The robot moves from (0,0) to (0,2), turns 180 degrees, and then returns to (0,0).
When repeating these instructions, the robot remains in the circle of radius 2 centered at the origin.

**Example 2:**

Input: instructions = "GG"
Output: false
Explanation: The robot moves north indefinitely.

**Example 3:**

Input: instructions = "GL"
Output: true
Explanation: The robot moves from (0, 0) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (0, 0) -> ...

**Constraints:**

- `1 <= instructions.length <= 100`
- `instructions[i]` is `'G'`, `'L'` or, `'R'`.

### 第一版
做法：
先想辦法走到底，再判斷是否能走回原點

class Solution {
    enum class Direction(val face: Int, val x: Int, val y: Int){
				// face 為面向的方位
				// 方位順序：N(0) -> E(1) -> S(2) -> W(3) -> N(0) -> ...
				// 右轉('R') = 方位 + 1，左轉('L') = 方位 - 1
        NORTH(0, 0, 1),
        EAST(1, 1, 0),
        SOUTH(2, 0, -1),
        WEST(3, -1, 0)
    }
    companion object {
        private const val STRAIGHT = 'G'
        private const val LEFT = 'L'
        private const val RIGHT = 'R'
				private const val DIRECTION_COUNT = 4
    }
    
    fun isRobotBounded(instructions: String): Boolean {
        // 初始位置
        var tmpFace = Direction.NORTH
        var tmpX = 0
        var tmpY = 0
        // TODO 可以先移除 "RRRR" & "LLLL"
        // 先想辦法走到底
        // 再判斷是否能走回原點
        
        // 先走完整個 instructions
        instructions.forEach {
            when (it) {
                STRAIGHT -> {
                    tmpX += tmpFace.x
                    tmpY += tmpFace.y
                }
                LEFT -> {
                    // 新的方向
                    var newFace = tmpFace.face - 1
                    if (newFace < 0) {
                        newFace += DIRECTION_COUNT
                    }
                    tmpFace = transToDirection(newFace)
                }
                RIGHT -> {
                    var newFace = tmpFace.face + 1
                    if (newFace >= DIRECTION_COUNT) {
                        newFace -= DIRECTION_COUNT
                    }
                    tmpFace = transToDirection(newFace)
                }
            }
        }
        // println(tmpFace.face)
        // println("x: $tmpX, y: $tmpY")
        
        // 判斷是否能回到原點
        // 回到原點
        if (tmpX == 0 && tmpY == 0) {
            return true
        }
        
        if (tmpFace == Direction.NORTH) {
            return false
        }
        
        return true
    }

    fun transToDirection(currentFace: Int): Direction {
        return when (currentFace) {
            Direction.NORTH.face -> Direction.NORTH
            Direction.EAST.face -> Direction.EAST
            Direction.SOUTH.face -> Direction.SOUTH
            else -> Direction.WEST
        }
    }
}

**Success**

[Details](https://leetcode.com/submissions/detail/621408508/)

Runtime: 224 ms, faster than 43.24% of Kotlin online submissions for Robot Bounded In Circle.

Memory Usage: 33.8 MB, less than 70.95% of Kotlin online submissions for Robot Bounded In Circle.

---

### 第二版
試圖縮短時間
若遇到連續轉方向，一併判斷

class Solution {
    enum class Direction(val face: Int, val x: Int, val y: Int){
        NORTH(0, 0, 1),
        EAST(1, 1, 0),
        SOUTH(2, 0, -1),
        WEST(3, -1, 0)
    }
    companion object {
        private const val STRAIGHT = 'G'
        private const val LEFT = 'L'
        private const val RIGHT = 'R'
        private const val DIRECTION_COUNT = 4
    }
    
    fun isRobotBounded(instructions: String): Boolean {
        // 初始位置
        var tmpFace = Direction.NORTH
        var tmpX = 0
        var tmpY = 0
        // 先想辦法走到底
        // 再判斷是否能走回原點
        
        // 先走完整個 instructions
        
        // note:
        // for (i in 0 until instructions.length) {}
        // 因為 i cannot be reassigned
        // 所以改成 var i 的方式
        // end note
        
        var i = 0
        while (i < instructions.length) {
            // 計算有連續幾個直走
            var count = 0
            for (j in i until instructions.length) {
                if (instructions[j] == STRAIGHT) {
                    count++
                } else {
                    break
                }
            }
            if (count != 0) {
                tmpX += tmpFace.x * count
                tmpY += tmpFace.y * count
                i += count
                continue
            }
            
            // 計算有連續幾個轉向
            count = 0
            for (j in i until instructions.length) {
                if (instructions[j] != STRAIGHT) {
                    count++
                } else {
                    break
                }
            }
            var faceSum = 0
            for (j in i until i + count) {
                if (instructions[j] == LEFT) {
                    faceSum--
                } else {
                    faceSum++
                }
            }
            
            i += count
            if (faceSum % DIRECTION_COUNT == 0) {// 沒旋轉
                continue
            }
            // 旋轉目前的方位
            var newFace = (tmpFace.face + faceSum) % DIRECTION_COUNT
            if (newFace < 0) {
                newFace += DIRECTION_COUNT
            }
            tmpFace = transToDirection(newFace)
        }
        // println("f: ${tmpFace.face} ($tmpX, $tmpY)")
        
        // 判斷是否能回到原點
        // 回到原點
        if (tmpX == 0 && tmpY == 0) {
            return true
        }
        
        if (tmpFace == Direction.NORTH) {
            return false
        }
        
        return true
    }

    fun transToDirection(currentFace: Int): Direction {
        return when (currentFace) {
            Direction.NORTH.face -> Direction.NORTH
            Direction.EAST.face -> Direction.EAST
            Direction.SOUTH.face -> Direction.SOUTH
            else -> Direction.WEST
        }
    }
}

**Success**

[Details](https://leetcode.com/submissions/detail/621445613/)

Runtime: 200 ms, faster than 60.13% of Kotlin online submissions for Robot Bounded In Circle.

Memory Usage: 34.5 MB, less than 29.73% of Kotlin online submissions for Robot Bounded In Circle.