如何创建一个函数来帮助查找给定距离内的所有地铁站？

Question

地铁路线图在下面。它由3个不同列表组成，每个列表代表不同的地铁线。但是，有两个连接桩号可以连接到另一条线。这两个站是牛顿和小印度。

subway_map = [ ['Botanic Gardens', 'Stevens', 'Newton', 'Little India', 'Rochor'], ['Newton', 'Novena', 'Toa Payoh', 'Braddell', 'Bishan'], ['Dhoby Ghaut', 'Little India', 'Farrer Park', 'Boon Keng']]

因此，我想实现一个函数来查找给定距离内的所有站点。例如：

eg_1 = find_station_within_distance(subway_map, origin = 'Botanic Gardens', dist = 3)
eg_2 = find_station_within_distance(subway_map, origin = 'Little India', dist = 1)
eg_3 = find_station_within_distance(subway_map, origin = 'Dhoby Ghaut', dist = 3) 

#function should return either list below

print(eg_1) 
['Stevens', 'Newton'] 
#or 
['Newton', 'Stevens']

print(eg_2)
['Farrer Park', 'Newton', 'Rochor', 'Dhoby Ghaut']

print(eg_3)
['Little India', 'Farrer Park', 'Boon Keng', 'Rochor', 'Newton', 'Stevens', 'Novena']

到目前为止，我只能得到原点所在线路上给定距离内的桩号。

def find_stations_within_distance(subway_map, orig, dist):

    result = []

    for lines in subway_map:
    
        if orig in lines:
        
            orig_idx = lines.index(orig)
            max_idx = dist + orig_idx
        
                if max_idx >= len(lines):
            
                    result += lines[orig_idx+1:]
            
                elif max_idx < len(lines):
            
                    result += lines[orig_idx+1:max_idx+1]
            
    return result 

Answer 1

我试图一次在一个距离内获得上一个和下一个站点，递归地直到距离= 0。

subway_map = [
    ['Botanic Gardens', 'Stevens', 'Newton', 'Little India', 'Rochor'],
    ['Newton', 'Novena', 'Toa Payoh', 'Braddell', 'Bishan'],
    ['Dhoby Ghaut', 'Little India', 'Farrer Park', 'Boon Keng']
]

def find_stations_within_distance(subway_map, orig, dist):
    result = []
    to_find_next = [orig]
    while dist > 0:
        now_finding = to_find_next[:]
        to_find_next.clear()
        while now_finding:
            current_station = now_finding.pop()
            for lines in subway_map:
                if current_station in lines:
                    current_idx = lines.index(current_station)
                    pre_idx = current_idx - 1
                    next_idx = current_idx + 1
                    if pre_idx >= 0:
                        pre_station = lines[pre_idx]
                        if pre_station not in result:
                            to_find_next.append(pre_station)
                            result.append(lines[pre_idx])
                    if next_idx < len(lines):
                        next_station = lines[next_idx]
                        if next_station not in result:
                            to_find_next.append(next_station)
                            result.append(next_station)

        dist -= 1
    if orig in result:
        result.remove(orig)
    return result

# Output: ['Stevens', 'Newton']
print(find_stations_within_distance(subway_map, 'Botanic Gardens', 2))
# Output: ['Newton', 'Rochor', 'Dhoby Ghaut', 'Farrer Park']
print(find_stations_within_distance(subway_map, 'Little India', 1))
# Output: ['Little India', 'Newton', 'Rochor', 'Farrer Park', 'Boon Keng', 'Stevens', 'Novena']
print(find_stations_within_distance(subway_map, 'Dhoby Ghaut', 3))

Answer 2

虽然这可能不是最优雅或最高效的代码，但这里有一种解决问题的方法：

subway_map = [ ['Botanic Gardens', 'Stevens', 'Newton', 'Little India', 'Rochor'], 
              ['Newton', 'Novena', 'Toa Payoh', 'Braddell', 'Bishan'], 
              ['Dhoby Ghaut', 'Little India', 'Farrer Park', 'Boon Keng']]

class Network:
    def __init__(self):
        self._stations = dict()
    
    def add_station(self, sta_name, nxt_sta= None):
        """Adds or updates sta_name and nxt_sta """
        if sta_name in self._stations.keys():
            sta = self._stations[sta_name]
            if nxt_sta:
                sta.add_link(nxt_sta)
        else:
            sta = Station(sta_name, nxt_sta)
            self._stations[sta_name] = sta
        if nxt_sta:
            if nxt_sta in self._stations.keys():
                nxsta = self._stations[nxt_sta]
                nxsta.add_link(sta_name)
            else:
                nxsta = Station(nxt_sta, sta_name)
                self._stations[nxt_sta] = nxsta
    
    @property
    def station(self, sta_name):
        """returns the station node for named station
           throws a key error if station doesn't exist """
        return self._stations[sta_name]
    
    @property
    def size(self):
        """returns size of network in terms of stations"""
        return len(self._stations)
    
    def __repr__(self):
        """return string representation of network"""
        s = ""
        for k, sta in self._stations.items():
            s += f'{sta}\n'           
        return s
        
    def find_all_stations(self, origin, link_count):
        """find list of all stations within link_count of origin
           conforms to breadth first search """
        nodes = set()            #keeps track of stations visited
        stations_found = set()   #keeps track of stations found within range
        level = 0
        sch_list = []            #creates a simple queue for FIFO processing
        if origin in self._stations.keys():
            nodes.add(origin)
            sch_list.append(self._stations[origin])
            while True:
                added_stas = []
                while sch_list:
                    cur_sta = sch_list.pop()
                    sta_lnks = cur_sta.links
                    for lnk in sta_lnks:
                        if lnk not in nodes:
                            added_stas.append(self._stations[lnk])
                if level >= link_count:
                    break
                else:
                    level += 1
                    for s in added_stas:
                        sch_list.append(s)
                        nodes.add(s.name)
                        stations_found.add(s.name)
        return list(stations_found)
    
""" simple class to define data structure for identifying stations 
     add keeping track of neighboring stations"""
class Station:   
    def __init__(self, sta_name, nxt_sta = None):
        self._name = sta_name
        self._lnks = set()
        if nxt_sta:
            self._lnks.add(nxt_sta)   
    @property
    def links(self):
        return list(self._lnks)   
    @property
    def name(self):
        return self._name
    
    def add_link(self, lnk_name):
        self._lnks.add(lnk_name)
        
    def __repr__(self):
        s = f"{self._name} has [ {', '.join(list(self._lnks))} ] neighbors"
        return s

执行以下命令：

subGrph = Network()
for line in subway_map:
    for s in range(1, len(line)):
        subGrph.add_station(line[s-1], line[s])       
subGrph.find_all_stations('Stevens', 3)        

收益率：

['Novena',
 'Dhoby Ghaut',
 'Farrer Park',
 'Toa Payoh',
 'Little India',
 'Newton',
 'Botanic Gardens',
 'Rochor']

Answer 3

def get_stns_dict(mrt_map):
    stations_dict = {}

    for line in mrt_map:
      
        for index, station in enumerate(line):
            # print(station)
            if station not in stations_dict:
                stations_dict[station] = []

            if index == 0: 
                stations_dict[station] += [line[index + 1]]
            elif index == len(line) -1:
                stations_dict[station] += [line[index - 1]]
            else :
                stations_dict[station] += [line[index -1 ]]
                stations_dict[station] += [line[index + 1]]
    return stations_dict

def find_stations_within_distance(mrt_map, orig, dist):
    # Modify the code below
    stations_dict = get_stns_dict(mrt_map)
                
    output = [] 
    possible_stns = stations_dict[orig]  
    past_stns = set()  
    current_distance = 1

    while current_distance <= dist:
        current_distance += 1
        for element in possible_stns:
            past_stns.add(element)
  

        for current_possible_stn in possible_stns:
            next_possible_stns = stations_dict[current_possible_stn]

            for next_stn in next_possible_stns:
                if next_stn not in past_stns and next_stn != orig:
                    output.append(next_stn)

        possible_stns = output
        output = []

    return past_stns