English subtitles

← Subway Planning Solution - Design of Computer Programs

Get Embed Code
1 Language

Showing Revision 3 created 05/25/2016 by Udacity Robot.

  1. Here is my solution.
  2. For subway I decided I'm going to return something that looks
  3. just like the successor function, only it's going to have all possible successors.
  4. It's going to be the dictionary of this form for any station that you ask me for.
  5. Stations are states in this problem.
  6. All you need to represent a state in this problem is what station am I currently at.
  7. Each of those I'm going to give you a dictionary that looks like a successor function.
  8. That is it has a combination of state-action pairs.
  9. The state is just going to be the neighboring station.
  10. Then the action is the line that you take.
  11. For example, if I'm at Bowdoin, then one of the states I can arrive at is government.
  12. The action I take to get there is follow the blue line.
  13. How do I do that?
  14. Well, one thing is I import the collections module.
  15. I use collections.defaultdict.
  16. I'm saying successors is a dictionary,
  17. and by default if there's a value that isn't there, the default is going to be a dictionary.
  18. Here's what successors look like, and the default value--
  19. if I ask for the value of a station and there's nothing there, make it be an empty dictionary.
  20. The line items are a set of line stops pairs.
  21. I'm going to go over those--line, name, and stops.
  22. Then I'm going to look at all the overlapping pairs--Bowdoin-government,
  23. government-state, state-aquarium--that I get by splitting up the stops into a list on spaces.
  24. Then I'm saying a successor of going from a to b, from Bowdoin to government--
  25. you can do that along a linename--and similarly going from government to Bowdoin.
  26. You can do that along the linename here, blue.
  27. Then return the successors.
  28. Overlapping_pairs takes any sequence and just gives me those pairs.
  29. If you give me this sequence of this turned into a list,
  30. the overlapping_pairs are first bowdoin-government, then government and state,
  31. then state and aquarium.
  32. This is useful here, and it's useful in general.
  33. Here's my ride function. It's now very easy.
  34. It's the shortest path search. That makes sense.
  35. I don't need lowest cost search, because there are no costs here.
  36. I'm just going from one station to the next.
  37. I start here. Where am I trying to get to?
  38. Well, the goal is to get to there.
  39. I'm trying to get to someplace where--and I just put the function in-line here
  40. rather than defining it separately.
  41. You could have done it either way.
  42. Because the functions were short, I decided to put them inline.
  43. But naming the function would also be fine.
  44. Lambda s--"s" stands for state or for station or for stop, and we ask "are we there?"
  45. Then the successor function.
  46. Well, we've already built up the successor function in this subway system--Boston--
  47. so we just say looking into boston, that's a dictionary
  48. and look for the station that I'm currently at, and that will give me a list of successors.
  49. Then shortestpathsearch does the rest.
  50. What does longest_ride do?
  51. First, I have to find all the stops, and that's a little bit complicated,
  52. because I've hidden them away in this dictionary for the system,
  53. but I can go through with this generator expression to come up with a set of stops.
  54. Then I just iterate through all possible stations a and b,
  55. look for a in all possible stops and for b in all possible stops,
  56. generate the ride--the shortestpathsearch between them,
  57. and then take the longest out of all those shortest paths,
  58. and that's my longest ride.