This is a Google interview question for software develop engineer from careercup. Here is the original thread,
"
Given a rectangle with top-left(a,b) and bottom-right(c,d) coordinates. Also given some coordinates (m,n) of sensors inside the rectangle. All sensors can sense in a circular region of radius r about their centre (m,n). Total N sensors are given. A player has to reach from left side of rectangle to its right side (i.e. he can start his journey from any point whose y coordinate is b and x coordinate is a<=x<=c. He has to end his journey to any point whose y coordinate is d and x coordinate is a<=x<=c).
Write an algorithm to find path (possibly shortest but not necessary) from start to end as described above.
Note: all coordinates are real numbers
(a,b)
|----------------------------------------------|
|.............................................................|end
|.............................................................|
|start......................................................|
|.............................................................|
|----------------------------------------------|(c,d)
Edit: You have to avoid sensors.
Also u can move in any direction any time.
".
2. Data Structure and Algorithm
Please refer to my C++ post.
3. Python Implementation
# ********************************************************************************
# Implementation
# ********************************************************************************
# Locaiton.py
import math
class Location(object):
"""Location"""
def __init__(self):
self.x = -1.0
self.y = -1.0
def __init__(self, x, y):
self.x = x
self.y = y
@staticmethod
def GetDistance(l1, l2):
deltaX = l1.x - l2.x
deltaY = l1.y - l2.y
return math.sqrt(deltaX*deltaX + deltaY*deltaY)
def __str__(self):
return str(self.__dict__)
# implement the following 2 function to enable Location as key of sorted container
def __eq__(self, rhs):
return self.__dict__ == rhs.__dict__
def __cmp__(self, rhs):
return self.__dict__ == rhs.__dict__
# implement the 3 following function to enable it as key of dictionary or sorted container
class EdgeCrosses(object):
#SensorRange.py
from EdgeCross import EdgeCross
from EdgeCross import EdgeCrosses
from Sensor import Sensor
class SensorRange(object):
"""SensorRange class"""
def __init__(self, *args, **kwargs):
self.edgeCrosses = EdgeCrosses()
self.sensors = list()
def MergeEdgeCross(self, ecs):
for idx in range(0, EdgeCross.MAX()):
self.edgeCrosses.ecs[idx].MergeBounds(ecs.ecs[idx])
def Merge(self, sr):
self.MergeEdgeCross(sr.edgeCrosses)
self.sensors.extend(sr.sensors)
#FindPathBetweenSensors_Google.py
from EdgeCross import EdgeCross
from EdgeCross import EdgeCrosses
from Location import Location
from Rectangle import Rectangle
from Sensor import Sensor
from SensorRange import SensorRange
import sortedcontainers
from exceptions import AttributeError
import sys
class FindPathBetweenSensors_Google(object):
"""FindPathBetweenSensors of class"""
def __init__(self, *args, **kwargs):
return super(FindPathBetweenSensors_Google, self).__init__(*args, **kwargs)
@staticmethod
def __FindCrossBetweenSensorAndRect(sensor, rect, edgeCrosses):
for edge in range(0, EdgeCross.MAX()) :
if edge & 1:
sensor.CrossedWithHLine(rect.edges[edge], edgeCrosses.ecs[edge])
else:
sensor.CrossedWithVLine(rect.edges[edge], edgeCrosses.ecs[edge])
@staticmethod
# merege sensors into sensor ranges
def __GenerateSensorRangeMap(sensors, rect, breakIfNoPath, vPath, sensorRanges):
for sensor in sensors:
toMerge = []
CUR_SIZE = len(sensorRanges)
# populate all crossed sensor ranges with this sensor
for idx in range(0, CUR_SIZE):
for s in sensorRanges[idx].sensors:
if s.Crossed(sensor) :
toMerge.append(idx)
break
workingSR = None
if len(toMerge) == 0:
# create a new sensor range
sr = SensorRange()
sr.sensors.append(sensor)
FindPathBetweenSensors_Google.__FindCrossBetweenSensorAndRect( \
sensor, rect, sr.edgeCrosses)
sensorRanges.append(sr)
workingSR = sr
else:
# merge all existing sensor range
# 1. merge the rest into the first senror range
# 2. erase the sensor ranges except the very first
for idx in range(len(toMerge) - 1, 0, -1):
sRangeToKeep = sensorRanges[toMerge[0]]
sRangeToMerge = sensorRanges[toMerge[idx]]
sRangeToKeep.Merge(sRangeToMerge)
del sensorRanges[toMerge[idx]]
# merge with the sensor
edgeCrosses = EdgeCrosses()
FindPathBetweenSensors_Google.__FindCrossBetweenSensorAndRect(\
sensor, rect, edgeCrosses)
sRangeToKeep= sensorRanges[toMerge[0]]
sRangeToKeep.MergeEdgeCross(edgeCrosses)
sRangeToKeep.sensors.append(sensor)
workingSR = sRangeToKeep
if workingSR is not None and breakIfNoPath:
if (vPath and workingSR.edgeCrosses.ecs[EdgeCross.LEFT()].IsValid() \
and workingSR.edgeCrosses.ecs[EdgeCross.RIGHT()].IsValid())
or (not vPath and workingSR.edgeCrosses.ecs[EdgeCross.TOP()].IsValid()
and workingSR.edgeCrosses.ecs[EdgeCross.BOTTOM()].IsValid()):
return False
return True
@staticmethod
def __ProcessCornerCase(vPath, edgeCrosses, rect, edge):
if edge.IsValid():
if vPath:
# left corner
if edgeCrosses.ecs[EdgeCross.LEFT()].IsValid():
edge.SetLowerBound(rect.edges[EdgeCross.LEFT()])
# right corner
if edgeCrosses.ecs[EdgeCross.RIGHT()].IsValid():
edge.SetUpperBound(rect.edges[EdgeCross.RIGHT()])
else:
# top corner
if edgeCrosses.ecs[EdgeCross.TOP()].IsValid():
edge.SetUpperBound(rect.edges[EdgeCross.TOP()])
# bottom corner
if edgeCrosses.ecs[EdgeCross.BOTTOM()].IsValid():
edge.SetLowerBound(rect.edges[EdgeCross.BOTTOM()])
return True
return False
@staticmethod
def __GetMidPointOfFirstGap(ecs, rect, vPath, val):
lowerBound = rect.edges[EdgeCross.BOTTOM()]
upperBound = rect.edges[EdgeCross.TOP()]
if vPath:
lowerBound = rect.edges[EdgeCross.LEFT()]
upperBound = rect.edges[EdgeCross.RIGHT()]
if len(ecs) == 0:
val[0] = (lowerBound + upperBound)/2
return True
if ecs[0].lowerBound > lowerBound:
val[0] = (ecs[0].lowerBound + lowerBound)/2
return True
if len(ecs) == 1:
if ecs[0].upperBound < upperBOund:
val[0] = (ecs[0].upperBound + upperBound)/2
return True
return False
if ecs[0].upperBound < ecs[1].lowerBound:
val[0] = (ecs[0].upperBound + ecs[1].lowerBound)/2
return True
return False
@staticmethod
def FindPath(sensors, rect, vPath, path):
try:
sensorRanges = list()
if len(sensors) != 0:
if not FindPathBetweenSensors_Google.__GenerateSensorRangeMap(\
sensors, rect, True, vPath, sensorRanges):
return False
if len(sensorRanges) == 0:
if vPath:
path.append(Location(rect.edges[EdgeCross.LEFT()], \
rect.edges[EdgeCross.TOP()]))
path.append(Location(rect.edges[EdgeCross.LEFT()], \ rect.edges[EdgeCross.BOTTOM()]))
else:
path.append(Location(rect.edges[EdgeCross.LEFT()], \
rect.edges[EdgeCross.TOP()]))
path.append(Location(rect.edges[EdgeCross.RIGHT()], \
rect.edges[EdgeCross.TOP()]))
return True
ecsFrom = sortedcontainers.SortedSet([])
ecsTo = sortedcontainers.SortedSet([])
for sr in sensorRanges:
if vPath and FindPathBetweenSensors_Google.__ProcessCornerCase(\
vPath, sr.edgeCrosses, rect, sr.edgeCrosses.ecs[EdgeCross.TOP()]):
ecsFrom.add(sr.edgeCrosses.ecs[EdgeCross.TOP()])
if vPath and FindPathBetweenSensors_Google.__ProcessCornerCase(\
vPath, sr.edgeCrosses, rect, sr.edgeCrosses.ecs[EdgeCross.BOTTOM()]):
ecsTo.add(sr.edgeCrosses.ecs[EdgeCross.BOTTOM()])
if (not vPath) and FindPathBetweenSensors_Google.__ProcessCornerCase(\
vPath, sr.edgeCrosses, rect, sr.edgeCrosses.ecs[EdgeCross.LEFT()]):
ecsFrom.add(sr.edgeCrosses.ecs[EdgeCross.LEFT()])
if (not vPath) and FindPathBetweenSensors_Google.__ProcessCornerCase(\
vPath, sr.edgeCrosses, rect, sr.edgeCrosses.ecs[EdgeCross.RIGHT()]):
ecsTo.add(sr.edgeCrosses.ecs[EdgeCross.RIGHT()])
valFrom = [0.0]
valTo = [0.0]
if FindPathBetweenSensors_Google.__GetMidPointOfFirstGap(\
ecsFrom, rect, vPath, valFrom) \
and FindPathBetweenSensors_Google.__GetMidPointOfFirstGap(\
ecsTo, rect, vPath, valTo) :
if vPath:
path.append(Location(valFrom[0], rect.edges[EdgeCross.TOP()]))
path.append(Location(valTo[0], rect.edges[EdgeCross.BOTTOM()]))
else:
path.append(Location(rect.edges[EdgeCross.LEFT()], valFrom[0]))
path.append(Location(rect.edges[EdgeCross.RIGHT()], valTo[0]))
return True
except AttributeError() as e:
print ("AttributeError: {0}".format(e))
except:
print ("Unexpected error: ", sys.exc_info()[0])
return False
# ********************************************************************************
# Test
# ********************************************************************************
from FindPathBetweenSensors_Google import FindPathBetweenSensors_Google
from Location import Location
from Rectangle import Rectangle
from Sensor import Sensor
import unittest
class Test_Test_FindPathBetweenSensors(unittest.TestCase):
def test_A(self):
path = []
rect = Rectangle(1.0, 9.0, 8.0, 1.0)
sensors = [ Sensor(Location(2.0, 3.0), 1.0), \
Sensor(Location(4.0, 3.0), 1.0), \
Sensor(Location(6.0, 3.0), 1.0), \
Sensor(Location(8.0, 3.0), 1.0) ]
self.assertFalse(FindPathBetweenSensors_Google.FindPath(sensors, rect, True, path))
self.assertTrue(FindPathBetweenSensors_Google.FindPath(sensors, rect, False, path))
self.assertEqual(path[0], Location(1.0, 2.0))
self.assertEqual(path[1], Location(9.0, 2.0))
def test_B(self):
path = []
rect = Rectangle(1.0, 9.0, 8.0, 1.0)
sensors = [ Sensor(Location(2.0, 3.0), 1.0), \
Sensor(Location(4.0, 3.0), 1.0), \
Sensor(Location(6.0, 3.0), 1.0), \
Sensor(Location(8.0, 3.0), 1.0), \
Sensor(Location(8.0, 8.0), 1.0), \
Sensor(Location(7.0, 7.0), 1.0) ]
self.assertFalse(FindPathBetweenSensors_Google.FindPath(sensors, rect, True, path))
self.assertTrue(FindPathBetweenSensors_Google.FindPath(sensors, rect, False, path))
self.assertEqual(path[0], Location(1.0, 2.0))
self.assertEqual(path[1], Location(9.0, 2.0))
def test_C(self):
path = []
rect = Rectangle(1.0, 9.0, 8.0, 1.0)
sensors = [ Sensor(Location(2.0, 7.2), 1.0), \
Sensor(Location(3.0, 6.0), 1.0), \
Sensor(Location(4.0, 4.5), 1.0), \
Sensor(Location(8.0, 7.2), 1.0), \
Sensor(Location(7.0, 6.2), 1.0), \
Sensor(Location(2.0, 3.0), 1.0), \
Sensor(Location(3.0, 4.0), 1.0), \
Sensor(Location(9.0, 1.0), 1.0) ]
self.assertTrue(FindPathBetweenSensors_Google.FindPath(sensors, rect, True, path))
self.assertEqual(path[0], Location(5.0, 8.0))
self.assertEqual(path[1], Location(4.5, 1.0))
path = []
self.assertTrue(FindPathBetweenSensors_Google.FindPath(sensors, rect, False, path))
self.assertEqual(path[0], Location(1.0, 2.0))
self.assertEqual(path[1], Location(9.0, 4.6))
if __name__ == '__main__':
unittest.main()
# Implementation
# ********************************************************************************
# Locaiton.py
import math
class Location(object):
"""Location"""
def __init__(self):
self.x = -1.0
self.y = -1.0
def __init__(self, x, y):
self.x = x
self.y = y
@staticmethod
def GetDistance(l1, l2):
deltaX = l1.x - l2.x
deltaY = l1.y - l2.y
return math.sqrt(deltaX*deltaX + deltaY*deltaY)
def __str__(self):
return str(self.__dict__)
# implement the following 2 function to enable Location as key of sorted container
def __eq__(self, rhs):
return self.__dict__ == rhs.__dict__
def __cmp__(self, rhs):
return self.__dict__ == rhs.__dict__
#EdgeCross.py
import sys
class EdgeCross(object):
"""EdgeCross class"""
@staticmethod
def LEFT():
return 0
@staticmethod
def TOP() :
return 1
@staticmethod
def RIGHT():
return 2
@staticmethod
def BOTTOM():
return 3
@staticmethod
def MAX():
return 4
def __init__(self, lb = sys.float_info.max, ub = sys.float_info.min):
self.lowerBound = lb
self.upperBound = ub
# implement the 3 following function to enable it as key of dictionary or sorted container
def __hash__(self):
return hash((self.lowerBound, self.upperBound))
def __eq__(self, rhs):
return self.lowerBound == rhs.lowBound and self.upperBound == rhs.upperBound
def __lt__(self, rhs):
return self.upperBound < rhs.lowerBound
def SetBounds(self, lb, ub):
self.lowerBound = lb
self.upperBound = ub
def SetLowerBound(self, lb):
self.lowerBound = lb
def SetUpperBound(self, ub):
self.upperBound = ub
def IsValid(self):
return self.lowerBound != sys.float_info.max and self.upperBound != sys.float_info.min
def MergeBounds(self, rhs):
self.SetBounds(min(self.lowerBound, rhs.lowerBound), \
max(self.upperBound, rhs.upperBound))
max(self.upperBound, rhs.upperBound))
class EdgeCrosses(object):
def __init__(self):
self.ecs = []
for idx in range(0, EdgeCross.MAX()):
self.ecs.append(EdgeCross())
#Rectangle.py
from EdgeCross import EdgeCross
import array
class Rectangle(object):
"""Rectangle class"""
def __init__(self, l, r, t, b):
self.edges = array.array('d', [0, 0, 0, 0])
self.edges[EdgeCross.LEFT()] = l
self.edges[EdgeCross.RIGHT()] = r
self.edges[EdgeCross.TOP()] = t
self.edges[EdgeCross.BOTTOM()] = b
#Sensor.py
from EdgeCross import EdgeCross
from EdgeCross import EdgeCrosses
from Location import Location
import math
class Sensor(object):
"""Sensor class"""
def __init__(self):
self.center = Location()
self.radius = 0.0
def __init__(self, center, radius):
self.center = center
self.radius = radius
assert(radius > 0)
def Crossed(self, rhs):
distance = Location.GetDistance(self.center, rhs.center)
return distance <= math.fabs(self.radius + rhs.radius)
def CrossedWithHLine(self, Y, ec):
if Y >= (self.center.y - self.radius) and Y <= (self.center.y + self.radius):
deltaY = self.center.y - Y;
deltaX = math.sqrt(self.radius*self.radius - deltaY*deltaY)
ec.SetBounds(self.center.x - deltaX, self.center.x + deltaX)
return True
return False
def CrossedWithVLine(self, X, ec):
if X >= (self.center.x - self.radius) and X <= (self.center.x + self.radius):
deltaX = self.center.x - X;
deltaY = math.sqrt(self.radius*self.radius - deltaX*deltaX)
ec.SetBounds(self.center.y - deltaY, self.center.y + deltaY)
return True
return False
from EdgeCross import EdgeCross
from EdgeCross import EdgeCrosses
from Sensor import Sensor
class SensorRange(object):
"""SensorRange class"""
def __init__(self, *args, **kwargs):
self.edgeCrosses = EdgeCrosses()
self.sensors = list()
def MergeEdgeCross(self, ecs):
for idx in range(0, EdgeCross.MAX()):
self.edgeCrosses.ecs[idx].MergeBounds(ecs.ecs[idx])
def Merge(self, sr):
self.MergeEdgeCross(sr.edgeCrosses)
self.sensors.extend(sr.sensors)
#FindPathBetweenSensors_Google.py
from EdgeCross import EdgeCross
from EdgeCross import EdgeCrosses
from Location import Location
from Rectangle import Rectangle
from Sensor import Sensor
from SensorRange import SensorRange
import sortedcontainers
from exceptions import AttributeError
import sys
class FindPathBetweenSensors_Google(object):
"""FindPathBetweenSensors of class"""
def __init__(self, *args, **kwargs):
return super(FindPathBetweenSensors_Google, self).__init__(*args, **kwargs)
@staticmethod
def __FindCrossBetweenSensorAndRect(sensor, rect, edgeCrosses):
for edge in range(0, EdgeCross.MAX()) :
if edge & 1:
sensor.CrossedWithHLine(rect.edges[edge], edgeCrosses.ecs[edge])
else:
sensor.CrossedWithVLine(rect.edges[edge], edgeCrosses.ecs[edge])
@staticmethod
# merege sensors into sensor ranges
def __GenerateSensorRangeMap(sensors, rect, breakIfNoPath, vPath, sensorRanges):
for sensor in sensors:
toMerge = []
CUR_SIZE = len(sensorRanges)
# populate all crossed sensor ranges with this sensor
for idx in range(0, CUR_SIZE):
for s in sensorRanges[idx].sensors:
if s.Crossed(sensor) :
toMerge.append(idx)
break
workingSR = None
if len(toMerge) == 0:
# create a new sensor range
sr = SensorRange()
sr.sensors.append(sensor)
FindPathBetweenSensors_Google.__FindCrossBetweenSensorAndRect( \
sensor, rect, sr.edgeCrosses)
sensorRanges.append(sr)
workingSR = sr
else:
# merge all existing sensor range
# 1. merge the rest into the first senror range
# 2. erase the sensor ranges except the very first
for idx in range(len(toMerge) - 1, 0, -1):
sRangeToKeep = sensorRanges[toMerge[0]]
sRangeToMerge = sensorRanges[toMerge[idx]]
sRangeToKeep.Merge(sRangeToMerge)
del sensorRanges[toMerge[idx]]
# merge with the sensor
edgeCrosses = EdgeCrosses()
FindPathBetweenSensors_Google.__FindCrossBetweenSensorAndRect(\
sensor, rect, edgeCrosses)
sRangeToKeep= sensorRanges[toMerge[0]]
sRangeToKeep.MergeEdgeCross(edgeCrosses)
sRangeToKeep.sensors.append(sensor)
workingSR = sRangeToKeep
if workingSR is not None and breakIfNoPath:
if (vPath and workingSR.edgeCrosses.ecs[EdgeCross.LEFT()].IsValid() \
and workingSR.edgeCrosses.ecs[EdgeCross.RIGHT()].IsValid())
or (not vPath and workingSR.edgeCrosses.ecs[EdgeCross.TOP()].IsValid()
and workingSR.edgeCrosses.ecs[EdgeCross.BOTTOM()].IsValid()):
return False
return True
@staticmethod
def __ProcessCornerCase(vPath, edgeCrosses, rect, edge):
if edge.IsValid():
if vPath:
# left corner
if edgeCrosses.ecs[EdgeCross.LEFT()].IsValid():
edge.SetLowerBound(rect.edges[EdgeCross.LEFT()])
# right corner
if edgeCrosses.ecs[EdgeCross.RIGHT()].IsValid():
edge.SetUpperBound(rect.edges[EdgeCross.RIGHT()])
else:
# top corner
if edgeCrosses.ecs[EdgeCross.TOP()].IsValid():
edge.SetUpperBound(rect.edges[EdgeCross.TOP()])
# bottom corner
if edgeCrosses.ecs[EdgeCross.BOTTOM()].IsValid():
edge.SetLowerBound(rect.edges[EdgeCross.BOTTOM()])
return True
return False
@staticmethod
def __GetMidPointOfFirstGap(ecs, rect, vPath, val):
lowerBound = rect.edges[EdgeCross.BOTTOM()]
upperBound = rect.edges[EdgeCross.TOP()]
if vPath:
lowerBound = rect.edges[EdgeCross.LEFT()]
upperBound = rect.edges[EdgeCross.RIGHT()]
if len(ecs) == 0:
val[0] = (lowerBound + upperBound)/2
return True
if ecs[0].lowerBound > lowerBound:
val[0] = (ecs[0].lowerBound + lowerBound)/2
return True
if len(ecs) == 1:
if ecs[0].upperBound < upperBOund:
val[0] = (ecs[0].upperBound + upperBound)/2
return True
return False
if ecs[0].upperBound < ecs[1].lowerBound:
val[0] = (ecs[0].upperBound + ecs[1].lowerBound)/2
return True
return False
@staticmethod
def FindPath(sensors, rect, vPath, path):
try:
sensorRanges = list()
if len(sensors) != 0:
if not FindPathBetweenSensors_Google.__GenerateSensorRangeMap(\
sensors, rect, True, vPath, sensorRanges):
return False
if len(sensorRanges) == 0:
if vPath:
path.append(Location(rect.edges[EdgeCross.LEFT()], \
rect.edges[EdgeCross.TOP()]))
path.append(Location(rect.edges[EdgeCross.LEFT()], \ rect.edges[EdgeCross.BOTTOM()]))
else:
path.append(Location(rect.edges[EdgeCross.LEFT()], \
rect.edges[EdgeCross.TOP()]))
path.append(Location(rect.edges[EdgeCross.RIGHT()], \
rect.edges[EdgeCross.TOP()]))
return True
ecsFrom = sortedcontainers.SortedSet([])
ecsTo = sortedcontainers.SortedSet([])
for sr in sensorRanges:
if vPath and FindPathBetweenSensors_Google.__ProcessCornerCase(\
vPath, sr.edgeCrosses, rect, sr.edgeCrosses.ecs[EdgeCross.TOP()]):
ecsFrom.add(sr.edgeCrosses.ecs[EdgeCross.TOP()])
if vPath and FindPathBetweenSensors_Google.__ProcessCornerCase(\
vPath, sr.edgeCrosses, rect, sr.edgeCrosses.ecs[EdgeCross.BOTTOM()]):
ecsTo.add(sr.edgeCrosses.ecs[EdgeCross.BOTTOM()])
if (not vPath) and FindPathBetweenSensors_Google.__ProcessCornerCase(\
vPath, sr.edgeCrosses, rect, sr.edgeCrosses.ecs[EdgeCross.LEFT()]):
ecsFrom.add(sr.edgeCrosses.ecs[EdgeCross.LEFT()])
if (not vPath) and FindPathBetweenSensors_Google.__ProcessCornerCase(\
vPath, sr.edgeCrosses, rect, sr.edgeCrosses.ecs[EdgeCross.RIGHT()]):
ecsTo.add(sr.edgeCrosses.ecs[EdgeCross.RIGHT()])
valFrom = [0.0]
valTo = [0.0]
if FindPathBetweenSensors_Google.__GetMidPointOfFirstGap(\
ecsFrom, rect, vPath, valFrom) \
and FindPathBetweenSensors_Google.__GetMidPointOfFirstGap(\
ecsTo, rect, vPath, valTo) :
if vPath:
path.append(Location(valFrom[0], rect.edges[EdgeCross.TOP()]))
path.append(Location(valTo[0], rect.edges[EdgeCross.BOTTOM()]))
else:
path.append(Location(rect.edges[EdgeCross.LEFT()], valFrom[0]))
path.append(Location(rect.edges[EdgeCross.RIGHT()], valTo[0]))
return True
except AttributeError() as e:
print ("AttributeError: {0}".format(e))
except:
print ("Unexpected error: ", sys.exc_info()[0])
return False
# ********************************************************************************
# Test
# ********************************************************************************
from FindPathBetweenSensors_Google import FindPathBetweenSensors_Google
from Location import Location
from Rectangle import Rectangle
from Sensor import Sensor
import unittest
class Test_Test_FindPathBetweenSensors(unittest.TestCase):
def test_A(self):
path = []
rect = Rectangle(1.0, 9.0, 8.0, 1.0)
sensors = [ Sensor(Location(2.0, 3.0), 1.0), \
Sensor(Location(4.0, 3.0), 1.0), \
Sensor(Location(6.0, 3.0), 1.0), \
Sensor(Location(8.0, 3.0), 1.0) ]
self.assertFalse(FindPathBetweenSensors_Google.FindPath(sensors, rect, True, path))
self.assertTrue(FindPathBetweenSensors_Google.FindPath(sensors, rect, False, path))
self.assertEqual(path[0], Location(1.0, 2.0))
self.assertEqual(path[1], Location(9.0, 2.0))
def test_B(self):
path = []
rect = Rectangle(1.0, 9.0, 8.0, 1.0)
sensors = [ Sensor(Location(2.0, 3.0), 1.0), \
Sensor(Location(4.0, 3.0), 1.0), \
Sensor(Location(6.0, 3.0), 1.0), \
Sensor(Location(8.0, 3.0), 1.0), \
Sensor(Location(8.0, 8.0), 1.0), \
Sensor(Location(7.0, 7.0), 1.0) ]
self.assertFalse(FindPathBetweenSensors_Google.FindPath(sensors, rect, True, path))
self.assertTrue(FindPathBetweenSensors_Google.FindPath(sensors, rect, False, path))
self.assertEqual(path[0], Location(1.0, 2.0))
self.assertEqual(path[1], Location(9.0, 2.0))
def test_C(self):
path = []
rect = Rectangle(1.0, 9.0, 8.0, 1.0)
sensors = [ Sensor(Location(2.0, 7.2), 1.0), \
Sensor(Location(3.0, 6.0), 1.0), \
Sensor(Location(4.0, 4.5), 1.0), \
Sensor(Location(8.0, 7.2), 1.0), \
Sensor(Location(7.0, 6.2), 1.0), \
Sensor(Location(2.0, 3.0), 1.0), \
Sensor(Location(3.0, 4.0), 1.0), \
Sensor(Location(9.0, 1.0), 1.0) ]
self.assertTrue(FindPathBetweenSensors_Google.FindPath(sensors, rect, True, path))
self.assertEqual(path[0], Location(5.0, 8.0))
self.assertEqual(path[1], Location(4.5, 1.0))
path = []
self.assertTrue(FindPathBetweenSensors_Google.FindPath(sensors, rect, False, path))
self.assertEqual(path[0], Location(1.0, 2.0))
self.assertEqual(path[1], Location(9.0, 4.6))
if __name__ == '__main__':
unittest.main()
No comments:
Post a Comment