Google Interview Question
Software DevelopersCountry: United States
Interview Type: In-Person
This solution calculates the bot path for as many iterations as needed for its orientation to go back to zero degrees. Once there, return whether the bot is at the origin or not.
An error margin (arbitrarily chosen) is considered to account for rounding.
import math
def check_path(commands):
orientation = 0
x, y = 0, 0
epsilon = 0.01
while True:
for command in commands:
if command[0] == 'rotate':
orientation = (orientation + command[1]) % 360
elif command[0] == 'move':
x += command[1]*math.cos(math.radians(orientation))
y += command[1]*math.sin(math.radians(orientation))
else:
print "Invalid Command"
if orientation == 0:
# Verify that both is back to origin
return ((x < epsilon and x > -1 * epsilon) and
(y < epsilon and y > -1 * epsilon))
print check_path([('move', 10), ('rotate', 45), ('move', 10), ('rotate', -45),
('move', 10), ('rotate', -45), ('move', 10), ('rotate', 45),
('move', 10), ('rotate', 180)])
First, transform the list of commands into a single command. (E.g. go forward 1, turn around, go back one turns into "turn around")
If this command has 0 movement, then we can build a wall. If the command has nonzero movement and the bearing changes, then we can also build a wall. (Draw some pictures to see why this is. For example, if the bearing changes 90 degrees, the robot will draw a box. If it changes 60 degrees, it draws a triangle. It creates more complicated shapes for bearing changes that do not divide 360, but it will still create a contained shape. It may never even reach its original point).
If the command has nonzero movement and no bearing change, it will draw a straight line to infinity and thus no box can contain it.
On a theoretical level the problem is quite simple.
Take the list of commands. When repeated over and over the list can be simplified to a single translation t followed by a single rotation r.
The only way we can't build a wall that contains the robot is if it will travel in a single direction infinitely, e.g. r == 0 && t > 0.
So run through the list of commands updating the robots position and as long as it faces in a different direction than it started OR ends its travel in the start position the wall is possible.
If this problem is about how to do accurate 2d plane traversal using integer coordinates and angles that is a much harder problem to solve and I would be interested to see solutions.
I saw this question at Hackerrank. It's called "Encircular". So this begs the questions: does Google copy questions from Hackerank ? or is this not a real interview question ?
To me this seems to be a horrible interview question. It requires some Aha moment which beats the purpose of the interview. But I might be wrong.
I think the missing part in the question is the fact that the series of commands can be repeated infinite times. (That is what the python code shows you).
The solution is probably simple.
Point p1 = getStartingPoint();
Point p2 = getPointAfterIteration(commands,1);
Point p3 = getPointAfterIteration(commands,2);
Point p4 = getPointAfterIteration(commands,3);
Circle c = new Circle(p1,p2,p3);
if(p1==p2==p3 || c.contains(p4)){
return true;
}
return false;
Assumption - Imaging X & Y axis dimensions. Robot will start at degree & (X,Y)=(0,0).
So at start robot is pointing towards positive X axis.
if output is (0,0) i..e final co-ordinates of robot then there is a wall.
import java.lang.Math;
import java.text.DecimalFormat;
public class RoboticWall {
static double X = 0.00d;
static double Y = 0.00d;
static double currentAngle = 0.0d;
static DecimalFormat numberFormat = new DecimalFormat("#.##");
public static void main(String[] s){
//System.out.println(Math.cos(180/57.2958));
isWall();
}
public static void isWall(){
move(10);
rotate(90);
move(10);
rotate(90);
move(10);
rotate(90);
move(10);
System.out.println("X="+numberFormat.format(X)+"Y="+numberFormat.format(Y));
}
private static void rotate(double i) {
currentAngle = currentAngle + i;
}
private static void move(double i) {
X = X + i*Math.cos(currentAngle/57.29);
Y = Y + i*Math.sin(currentAngle/57.29);
}
}
output: X=0 Y=0
Assumption - Imaging X & Y axis dimensions. Robot will start at degree 0 & (X,Y)=(0,0).
So at start robot is pointing towards positive X axis.
if output is (0,0) i..e final co-ordinates of robot then there is a wall.
import java.lang.Math;
import java.text.DecimalFormat;
public class RoboticWall {
static double X = 0.00d;
static double Y = 0.00d;
static double currentAngle = 0.0d;
static DecimalFormat numberFormat = new DecimalFormat("#.##");
public static void main(String[] s){
//System.out.println(Math.cos(180/57.2958));
isWall();
}
public static void isWall(){
move(10);
rotate(90);
move(10);
rotate(90);
move(10);
rotate(90);
move(10);
System.out.println("X="+numberFormat.format(X)+"Y="+numberFormat.format(Y));
}
private static void rotate(double i) {
currentAngle = currentAngle + i;
}
private static void move(double i) {
X = X + i*Math.cos(currentAngle/57.29);
Y = Y + i*Math.sin(currentAngle/57.29);
}
}
Observe that the path p1 {(r0) m10, r-90, m10} has a mirror symmetry along a bisecting vector of 45 degrees (NE)
_.
|
Observe also that p1^2 has the same mirror symmetry:
.__.
| |
Extending this to P1^4 the path executes such that it forms a circuit around a center point.
A given path Px can be contained if for some number of executions of commands {C1, C2...} it circles some center point. Specifically if the start point s of execution1, the endpoint e of execution2, and common point c shared between execution1 and execution2 are all on the circumference of some circle of a given radius then this path carves out some
subsection of the curve of that circle.
Algorithm:
- Given P, execute Pn1 and Pn2, calculating the Start point, endpoint and the common point.
- Use 3 points formula to attempt to solve for a circle whose circumference contains the three. If no such solution exists return false else return true.
For the trivial case of P(r0, m10, r180, m10), all three points {s, e, c} are the same point and any arbitrary circle can contain any 1 point along it's circumference.
/*
A robot on a plane has 2 types of commands:
1. move forward by X units (X is integer 0 <= X <= 10000 )
2. rotate by X degrees (X is integer in range [-180, 180] )
A robot looks like
def robot(commands):
while True:
for command in commands:
execute(command)
Given a list of commands (of size <= 10000) tell if it's possible to build a wall around the robot such that he will never touch it.
Example:
[move(10), rotate(180), move(10)] -> answer is yes
[move(10), rotate(45), move(10), rotate(-45), move(10), r
*/
#include "stdafx.h"
#include <iostream>
#include <cmath>
using namespace std;
class Command
{
public:
char commandType;
double value;
Command(char type, double v)
{
commandType = type;
value = v;
}
};
const double PI = atan(1) * 4;
#define NUMBER_OF_COMMANDS 3
int _tmain(int argc, _TCHAR* argv[])
{
Command set[NUMBER_OF_COMMANDS]={Command('m',10), Command('r',180), Command('m',10)}; //input 1
//Command set[NUMBER_OF_COMMANDS]={Command('m',10), Command('r',45), Command('m',10), Command('r',-45), Command('m',10), Command('r',45)}; //input 2
// Command set[NUMBER_OF_COMMANDS]={Command('m',10), Command('r',120), Command('m',10)}; //test input 1
double x_coordinate = 0;
double y_coordinate = 0;
int angle = 0;
//Step1: Find the resultant angle after first iteration.If the angle is 0 the boundry is not possible
int resultantAngle = 0;
for (int i = 0 ; i < NUMBER_OF_COMMANDS; i++)
{
if (set[i].commandType == 'r')
{
resultantAngle += set[i].value;
}
}
resultantAngle = resultantAngle % 360;
if (resultantAngle == 0)
{
cout << " Wall is not possible.";
return 0;
}
if ( resultantAngle < 0)
{
resultantAngle = 360 + resultantAngle;
}
if (resultantAngle > 180)
{
resultantAngle = 360 - resultantAngle;
}
int numberOfIterations = 360 / resultantAngle;
for (int i = 0; i < numberOfIterations; i++)
{
for (int j = 0 ; j < NUMBER_OF_COMMANDS; j++)
{
if (set[j].commandType == 'r')
{
angle += set[j].value;
}
else if (set[j].commandType == 'm')
{
x_coordinate = x_coordinate + set[j].value * cos(angle *PI/180);
y_coordinate = y_coordinate + set[j].value * sin(angle *PI/180);
}
}
}
if ((x_coordinate == 0) && (y_coordinate == 0))
{
cout << " Wall is possible.";
}
else
{
cout << " Wall is not possible.";
}
int l;
cin >> l;
return 0;
}
Here's a hacked out solution in Haskell.
import Data.List
data Pos = Pos Int Int deriving (Eq, Show)
data State = State Pos Int deriving (Eq, Show)
initialState :: State
initialState = State (Pos 0 0) 0
degToRad :: Int -> Float
degToRad deg = (fromIntegral deg) / 360 * (2 * pi)
degCos :: Int -> Float
degCos = cos . degToRad
degSin :: Int -> Float
degSin = sin . degToRad
rotate :: Int -> State -> State
rotate rotation (State pos angle) = State pos ((angle + rotation) `mod` 360)
move :: Int -> State -> State
move distance (State (Pos x y) angle) =
let dx = round ((degCos angle) * (fromIntegral distance))
dy = round ((degSin angle) * (fromIntegral distance)) in
State (Pos (x + dx) (y + dy)) angle
runCommands :: [State -> State] -> State -> State
runCommands commands state = foldl (flip ($)) state commands
containable :: [State -> State] -> Bool
containable commands = find (== initialState) (take 10000 (iterate (runCommands commands) initialState)) /= Nothing
main :: IO ()
main = do
let commands1 = [move 10, rotate 180, move 10]
let commands2 = [move 10, rotate 45, move 10, rotate (-45), move 10, rotate 45]
putStrLn (show (containable commands1))
putStrLn (show (containable commands2))
- guilhebl June 07, 2016