Neighborhood Problem
Given a list of houses and roads connecting them, write a function to find all of the houses accessable by road from any arbitrary house.
For example, given the following neighborhood:
We can represent the roads in this neighborhood with the following array of arrays:
And we expect that for the input "A", our function will return ["B", "C", "E", "F"] in some order. For input "D" our function will return ["G", "H"] in some order.
Here is a more complicated neighborhood to test your processing on:
Which is described by
Specifically, make sure:
- The function works for any number of connected roads. Ensure that in the second example, "A" is connected to "G". What would happen if you made the chain even longer?
- Each connected house is only represented in the output array one time.
The code that we wrote together in class is below. But this only works for the first example! Can you think of a more general solution?
def getRoadsForEachHouse(roads, house):
connected = []
for r in roads:
if r[0] == house:
connected.append(r[1])
else if r[1] == house:
connected.append(r[0])
return connected
def getConnectedHouses(roads, startHouse):
houses = getRoadsForEachHouse(roads, startHouse)
for h in houses:
houses2 = getRoadsForEachHouse(roads, h)
for h2 in houses2:
if h2 not in houses:
houses.append(h2)