LeetCode 1041 - Robot Bounded In Circle

https://leetcode.com/problems/robot-bounded-in-circle/

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 degress 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: "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: "GG"
Output: false
Explanation: 
The robot moves north indefinitely.

Example 3:

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

Note:

1. 1 <= instructions.length <= 100
2. instructions[i] is in {'G', 'L', 'R'}

https://leetcode.com/problems/robot-bounded-in-circle/discuss/290856/JavaC%2B%2BPython-Let-Chopper-Help-Explain

Starting at the origin and face north (0,1),
after one sequence of instructions,

1. if chopper return to the origin, he's in an obvious circle.
2. if chopper finishes with face not towards north,
   it will get back to the initial status in another one or three sequences.

Explanation

(x,y) is the location of chopper.
d[i] is the direction he is facing.
i = (i + 1) % 4 will turn right
i = (i + 3) % 4 will turn left
Check the final status after instructions.

Complexity

Time O(N)
Space O(1)

    public boolean isRobotBounded(String ins) {
        int x = 0, y = 0, i = 0, d[][] = {{0, 1}, {1, 0}, {0, -1}, { -1, 0}};
        for (int j = 0; j < ins.length(); ++j)
            if (ins.charAt(j) == 'R')
                i = (i + 1) % 4;
            else if (ins.charAt(j) == 'L')
                i = (i + 3) % 4;
            else {
                x += d[i][0]; y += d[i][1];
            }
        return x == 0 && y == 0 || i > 0;
    }

https://zxi.mytechroad.com/blog/simulation/leetcode-1041-robot-bounded-in-circle/

When instructions end, if the robot is back to (0,0) or is not facing north (which guarantees it will come back to 0, 0 for another 1 or 3 rounds)

https://leetcode.com/problems/robot-bounded-in-circle/discuss/291358/A-bad-problem-although-it-is-easy
This problem is easy. Just return true if the final position does not change or the facing direction is different from the beginning.
However, this problem is tricky. And I don't think a tricky problem can test or improve a developer's programming skill.
I find more and more tricky problems recently. I feel it is not a good trend if LeetCode goes deeper into it.

https://leetcode.com/problems/robot-bounded-in-circle/discuss/291191/ChineseC%2B%2B-O(n)

题意：一个机器人在原点(0,0)，默认方向朝北，按下面三个指令行动。

• G 朝当前方向前进一步
• L 左转90度
• R 右转90度

机器人然后按顺序执行一串指令，并且可以重复执行下去。
问机器人是否会在一个固定路线转圈？

思路：既然机器人是重复执行这串指令，若在固定路线转圈，则肯定是重复若干次后，回到了原点。
否则路线肯定不能固定。

接下来看什么时候可以回到原点。
如果第一次执行完一串指令后，就在原点，则可以保证是固定路线。
否则继续分析。

执行完一串指令后，不在原点，假设此时新的方向是dir。
如果dir不是北方，则一定可以回到原点。

证明如下：

如果dir指向南方，则下一次执行完，机器人就回到原点（方向选择180度，180度镜像）。
如果dir指向东方或西方，则第四次执行完，机器人就回到原点（方向选择90度，90度镜像）。

所以，为了简单起见，只需要让机器人重复执行四次指令串，然后判断是否在原点即可。
当然，也可以直接执行一次，判断方向是不是北方。

代码：https://github.com/tiankonguse/leetcode-solutions/tree/master/contest/136

https://blog.csdn.net/fuxuemingzhu/article/details/92128721
我们一定知道，这个题不能用暴力解法。机器人的路径最终被圆包括的充分条件是机器在一些指令之后回到原点。由于指令是循环的，题目只给出了部分指令。那么对于该部分指令的要求是，机器人回到了原点或者不再原点且不面向北。

回到原点很好理解，那么不再原点且不面向北是什么意思呢？

如果题目中的指令结束之后，机器人不在原点，那么说明它相对原点移动了一个向量v。机器人在指令结束后的位置成为了新的原点，题目说机器人的初始状态时是面向北的，那么如果在新的原点上仍然面向北，那么一定还会继续向第一次一样相对新的原点移动相同的向量v，此时机器人距原点的向量是2v。

那么为什么不面向北就一定能回到原点呢？这是由于在新的原点新的方向上再次接受相同指令后，机器人移动新向量的长度为|向量v|、方向和v成90度或者180度；多次指令的结果叠加就会抵消第一次移动的v。

思路：有2种情况会形成循环

1. 经过一个周期回到原点

2. 经过一个周期没有回到原点，但是方向变了（经过若干个循环后一定会回到原点）

Leetcode 573 - Squirrel Simulation

http://bookshadow.com/weblog/2017/05/07/leetcode-squirrel-simulation/

There's a tree, a squirrel, and several nuts. Positions are represented by the cells in a 2D grid. Your goal is to find the minimal distance for the squirrel to collect all the nuts and put them under the tree one by one. The squirrel can only take at most one nut at one time and can move in four directions - up, down, left and right, to the adjacent cell. The distance is represented by the number of moves.

Example 1:

Input: 
Height : 5
Width : 7
Tree position : [2,2]
Squirrel : [4,4]
Nuts : [[3,0], [2,5]]
Output: 12
Explanation:

Note:

1. All given positions won't overlap.
2. The squirrel can take at most one nut at one time.
3. The given positions of nuts have no order.
4. Height and width are positive integers. 3 <= height * width <= 10,000.
5. The given positions contain at least one nut, only one tree and one squirrel.

解题思路：

求所有坚果到树的曼哈顿距离之和的2倍，记为total

求松鼠到坚果的曼哈顿距离 - 树到坚果曼哈顿距离的最小值， 该值与total之和即为最终答案

https://blog.csdn.net/magicbean2/article/details/78899934
松鼠的行为可以分为两个步骤：1）走到某个坚果i那里，然后把坚果i移动到树下；2）依次走到其它坚果那里，带上坚果之后返回来。所以松鼠的最短行程只取决于第一次选择哪个坚果，这是因为选择坚果i之后，松鼠需要额外走从它当前位置到坚果i的距离，但是却可以省下从树到坚果i之间的距离，所以我们的目标就是找到i，使得distance(squireel, nuts[i]) - distance(tree, nuts[i])最小。确定i之后，再按照松鼠的移动轨迹计算路程即可。

    int minDistance(int height, int width, vector<int>& tree, vector<int>& squirrel, vector<vector<int>>& nuts) {
        int min_dist = INT_MAX, min_index = -1, ret = 0, dist;
        for (int i = 0; i < nuts.size(); ++i) {
            dist = distance(squirrel, nuts[i]) - distance(nuts[i], tree);
            if (dist < min_dist) {
                min_dist = dist;
                min_index = i;
            }
        }
        ret += min_dist;
        for (int i = 0; i < nuts.size(); ++i) {
            ret += 2 * distance(nuts[i], tree);
        }
        return ret;
    }
private:
    int distance(vector<int> &from, vector<int> &to) {
        return abs(from[0] - to[0]) + abs(from[1] - to[1]);
    }

http://www.cnblogs.com/grandyang/p/6919923.html
本题说有一只小松鼠，一堆在不同位置的粟子，还有一棵树，小松鼠目标是把所有的粟子都运到树的位置，问怎样的顺序可以使用最少的步数。那么我们这么想，如果小松鼠本身就在树的位置，那么把所有的栗子运回树的步数就是一个定值，为每个粟子距树的距离总和乘以2。那么只有当小松鼠不在树的位置时候，它首先要走到一个粟子的位置，然后再去树那儿。而且一旦小松鼠到了树那，再出发，之后的步数就是定值了。所以关键就在于决定小松鼠首先去哪个粟子那。博主最开始犯了一个这道题很容易犯的一个错误，就是在选起始粟子的时候的判定条件是松鼠到该粟子的距离加上该粟子到树的距离之和最小当作判定条件，其实这样是不对的。举个简单的反例，比如此时有两个粟子A和B，小松鼠到粟子A的距离为2，粟子A到树的距离为1，小松鼠到粟子B的距离为2，粟子B到树的距离为2。那么按照博主之前的选择方法，会选先去粟子A，因为小松鼠到粟子A再到树的距离之和为3，小于先去粟子B再去树的距离之和(为4)。然而小松鼠先去粟子A的话，总距离就是7，而如果先去粟子B的话，总距离为6，这就说明之前的判定条件不对。那么正确思路应该是，假设小松树最先应该去粟子i，那么我们假设粟子i到树的距离为x，小松鼠到粟子i的距离为y，那么如果小松鼠不去粟子i，累加步数就是2x，如果小松鼠去粟子i，累加步数就是x+y，我们希望x+y尽可能的小于2x，那么就是y尽可能小于x，即x-y越大越好。这样我们遍历每个粟子，找出x-y最大的那个，让小松鼠先去捡就好了

https://discuss.leetcode.com/topic/88490/java-5-liner-o-nuts-time-o-1-space

Proof: Let the minimum distance from each nut to the tree be a_1, ..., a_n and let the minimum distance from each nut to the initial squirrel position be b_1, ..., b_n. Note that the minimum distance between two positions in the matrix is determined by their Manhattan distance.

Then, if the squirrel were to start at the tree, then the minimum total distance required to collect all the nuts is 2a_1 + ... + 2a_n. However, since the squirrel starts elsewhere, we just need to substitute one of the 2a_i terms with a_i + b_i. Or equivalently, we replace one of the a_i terms in the sum with b_i. To minimize the total sum value at the end, we choose i that maximizes a_i - b_i.

public int minDistance(int height, int width, int[] tree, int[] squirrel, int[][] nuts) {
    int sum = 0, maxDiff = Integer.MIN_VALUE;
    for (int[] nut : nuts) {
        int dist = Math.abs(tree[0] - nut[0]) + Math.abs(tree[1] - nut[1]);
        sum += 2*dist;
        maxDiff = Math.max(maxDiff, dist - Math.abs(squirrel[0] - nut[0]) - Math.abs(squirrel[1] - nut[1]));
    }
    return sum - maxDiff;
}

https://discuss.leetcode.com/topic/88512/java-solution-o-n-manhattan-distance

    public int minDistance(int height, int width, int[] tree, int[] squirrel, int[][] nuts) {
        int n = nuts.length;
        int[] nutToTree = new int[n];
        int[] nutToSquirrel = new int[n];
        
        int sum = 0;
        for (int i = 0; i < n; i++) {
            nutToTree[i] = Math.abs(nuts[i][0] - tree[0]) + Math.abs(nuts[i][1] - tree[1]);
            sum += nutToTree[i] * 2;
            nutToSquirrel[i] = Math.abs(nuts[i][0] - squirrel[0]) + Math.abs(nuts[i][1] - squirrel[1]);
        }
        
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int dist = sum + nutToSquirrel[i] - nutToTree[i];
            min = Math.min(min, dist);
        }
        
        return min;
    }

https://discuss.leetcode.com/topic/88511/easy-to-understand-concise-o-n-solution-with-explanation

Since squirel needs to travel to the tree every time after picking a nut, it needs to travel to the first nut, get it to the tree and then visit other nuts one by one. So total distance would be
dist(squirrel,first_nut) + dist(fist_nut, tree) + 2 * sum(dist(nut,tree)) - 2 * dist(fist_nut, tree) = dist(squirrel,first_nut) - dist(fist_nut, tree) + 2 * sum(dist(nut,tree))
2 * sum(dist(nut,tree)) is constant, so we just need to minimize dist(squirrel,first_nut) - dist(fist_nut, tree) to select the first nut.

Check if the door is open or closed - GeeksforGeeks

Check if the door is open or closed - GeeksforGeeks
Given n doors and n persons. The doors are numbered 1 to n and persons are given id's numbered 1 to n. Each door can have only 2 status open and closed. Initially all the doors have status closed. Find the final status of all the doors if a person changes the current status of all the doors, i.e. if status open then change to status closed and vice versa, for which he is authorized. A person with id 'i' is authorized to change the status of door numbered 'j' if 'j' is a multiple of 'i'.
Note:
– A person has to change the current status of all the doors for which he is authorized exactly once.
– There can be a situation that before a person changes the status of the door, another person who is also authorized for the same door changes the status of the door.

Approach: It is mathematical and logical approach. If we observe it properly, then we find that the final status of a door numbered i is open if ‘i’ has odd number of factors and status is closed if ‘i’ has even number of factors. It does not depend in which sequence the status of doors are changed. To find whether count of divisors of number is even or odd, we can see Check if count of divisors is even or odd post.

// Function to check whether 'n'

// has even number of factors or not

bool hasEvenNumberOfFactors(int n)

{

    int root_n = sqrt(n);

 

    // if 'n' is a perfect square

    // it has odd number of factors

    if ((root_n*root_n) == n)

        return false;

 

    // else 'n' has even

    // number of factors

    return true;

}

 

// Function to find and print

// status of each door

void printStatusOfDoors(int n)

{

    for (int i=1; i<=n; i++)

    {

        // If even number of factors

        // final status is closed

        if (hasEvenNumberOfFactors(i))

            cout << "closed" << " ";

 

        // else odd number of factors

        // final status is open

        else

            cout << "open" << " ";

    }

}

Read full article from Check if the door is open or closed - GeeksforGeeks