The subway routes

Problem

Ximena takes the subway from home to work, and she is tired of always riding the same way. She wants to know how many different routes she has, so she can mix it up. The stations are numbered from 0: her home is next to station 0 and her work is next to the last one.

Write a function that takes links, a list with one entry per station (there is at least one and at most 12): links[i] is the list of stations you can reach directly from station i. Links always go forward, to a station with a higher number, so you never go back, and no station is repeated within the same list. Return a whole number: how many different routes go from station 0 to the last one. Two routes are different if the list of stations they pass through is not the same. With [[1, 2], [3], [3], []] she can go through 0, 1, 3 or through 0, 2, 3: it returns 2. With [[1, 2, 3], [2, 3], [3], []] there are 4 routes: 0, 3; 0, 1, 3; 0, 2, 3 and 0, 1, 2, 3. If there is no way to get there, return 0. If there is only one station, home and work are next to the same one, and that counts as one route: it returns 1.

Examples

• Two ways

  [[1, 2], [3], [3], []] → 2

• Four routes

  [[1, 2, 3], [2, 3], [3], []] → 4

• A dead-end station

  [[1, 2], [], [3], []] → 1

Besides these, the challenge has hidden tests that are revealed when you submit your solution.

You start with this

def subway_routes(links):
    pass

function subwayRoutes(links) {
}