Walking Robot Simulation

-

Latest problem from Leetcode is this one: https://leetcode.com/problems/walking-robot-simulation/description/ Now the description of the problem doesn’t seem super accurate since in reality what the author is asking is: as the robot walks, for each step there will be an Euclidean distance from that position to the origin. Return the maximum Euclidean distance to the origin as the robot walks the course. Also, it wasn’t clear that one could have duplicated obstacle. I want to believe that many Leetcoders must have been confused and that might be the reason that there are more thumb downs than ups. I failed submission few times because of these misunderstandings:


The problem is a simple traversal (some attention to details required) with usage of a hash table for a quick lookup into the obstacles. To quickly access the hash table, use the following trick to build the key: suppose that you want to build a key for index (a,b) with the following constraints:

0<=a<=N
0<=b<=N

All you need to generate a unique key is the following formula: key = a*SEED + b, and as long as SEED is a number greater than N (SEED > N), you’re guaranteed to generate a unique number based on any (a,b) - you can prove it mathematically.

After you add all the obstacles to the hash table using the above technique, just traverse the commands. Use a flag to determine the proper direction (some minor calculation needed), and as you “walk” the robot, decide whether it is an obstacle or not that you’re stepping on, and handle the situation accordingly. At each step, calculate the Euclidian distance to the origin, and keep track of the max. And that’s it! Code is down below, cheers, Boris.


       public class Solution
       {
             public int RobotSim(int[] commands, int[][] obstacles)
             {
                    Hashtable htObs = new Hashtable();
                    long seed = 40000L;
                    int retVal = 0;

                    for (int i = 0; i < obstacles.Length; i++)
                    {
                           long key = obstacles[i][0] * seed + obstacles[i][1];
                           if (!htObs.ContainsKey(key)) htObs.Add(key, true);
                    }

                    int x = 0;
                    int y = 0;
                    int direction = 0; //0 north, 1 west, 2 south, 3 east
                    for (int i = 0; i < commands.Length; i++)
                    {
                           if (commands[i] == -2)
                           {
                                  direction = (direction + 1) % 4;
                           }
                           else if (commands[i] == -1)
                           {
                                  direction--;
                                 if (direction < 0) direction = 3;
                           }
                           else
                           {
                                 int count = commands[i];
                                 while (count > 0)
                                 {
                                        if (x * x + y * y > retVal) retVal = x * x + y * y;

                                        int tx = x;
                                        int ty = y;
                                        switch (direction)
                                        {
                                              case 0:
                                                     y++;
                                                     break;
                                              case 1:
                                                     x--;
                                                     break;
                                              case 2:
                                                     y--;
                                                     break;
                                              case 3:
                                                     x++;
                                                     break;
                                        }

                                        long key = x * seed + y;
                                        if (htObs.ContainsKey(key))
                                        {
                                              //Revert back
                                              x = tx;
                                              y = ty;
                                              break;
                                        }

                                        if (x * x + y * y > retVal) retVal = x * x + y * y;

                                        count--;
                                 }
                           }
                    }

                    return retVal;
             }
       }

Comments

Post a Comment

Popular posts from this blog

Count Binary Substrings

-
Image
Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
Read more

Count Vowels Permutation: Standard DP

-
Image
Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
Read more

Maximum Number of Balloons

-
Image
#431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
Read more