Station Coding Exercise from Brent Ozar

Station Coding Exercise from Brent Ozar

Brent Ozar recently posted a coding exercise on his site which looked fun: Query Exercise: Return Routes in the Right Order – Brent Ozar Unlimited®

As usual with Brent, the setup code worked perfectly, leaving us with the problem to solve.

First step – can we work out the next station based on the normal and override routing? Turns out we can pretty easily with a left join:

SELECT		Stations.StationName	AS FromStationName,
		NextStation.StationName AS NextStationName
FROM		Stations
LEFT JOIN	StationRoutingOverride
	   ON	StationRoutingOverride.StationFromName = Stations.StationName
LEFT JOIN	Stations AS NextStation
	   ON	(
			StationRoutingOverride.StationToName IS NOT NULL
		 AND	StationRoutingOverride.StationToName = NextStation.StationName
		)
		OR
		(
			StationRoutingOverride.StationRoutingOverrideId IS NULL
		  AND	NextStation.StationId = Stations.StationId + 1
		)

That gives us a nice simple list with all the stations and where they go next, with both the normal operation for anything without an override, and heading to the override for anything with it. I’m assuming that the StationId is always sequential, otherwise we could edit the Stations.StationId + 1 to be predictable

Next, how do we recurse the whole list to find the right places to go? A recursive CTE!
I was just going to put the above into the recursive CTE, but due to something I don’t understand in SQL, you can’t have a recursive CTE with a left join. I’m sure there’s a good reason for that, but we can easily solve it by putting it into its own CTE. You could also just dump it into a temp table for the same result – probably better performance if there was a non-trivial number of rows as you can index it.

WITH NextStation AS
(
	SELECT		Stations.StationName	AS FromStationName,
				NextStation.StationName AS NextStationName
	FROM		Stations
	LEFT JOIN	StationRoutingOverride
		   ON	StationRoutingOverride.StationFromName = Stations.StationName

   LEFT JOIN	Stations AS NextStation
		   ON	(
					StationRoutingOverride.StationToName IS NOT NULL
			  AND	StationRoutingOverride.StationToName = NextStation.StationName
				)
		   OR
				(
					StationRoutingOverride.StationRoutingOverrideId IS NULL
			  AND	NextStation.StationId = Stations.StationId + 1
				)
),
	 uglyStations AS
(
	SELECT	CAST(null AS VARCHAR(50)) AS FromStationName,
		Stations.StationName AS NextStationName
	FROM	Stations
	WHERE	Stations.StationName = 'A'
	UNION ALL
	SELECT	NextStation.FromStationName,
		NextStation.NextStationName
	FROM	NextStation
   INNER JOIN	uglyStations
	   ON	uglyStations.NextStationName = NextStation.FromStationName
)
SELECT	uglyStations.FromStationName
FROM	uglyStations
WHERE	uglyStations.FromStationName IS NOT NULL

I don’t know why I called it uglyStations, probably because I couldn’t do a left join and that annoyed me.

There’s a bunch of ways I could’ve started the recursive CTE, I went with a dummy row that said to travel from ‘null’ to start at ‘A’. There’s plenty of other ways to get this started. SQL decided to make me cast the null in first part of the union to make the data types the same.
Next up, union the first result with the CTE to make it recursive, and then finally select the answer from uglyStations. This could have used the FromStationName or the NextStationName, just change the where clause to be the same.

Full gist can be found here: gist

That was good fun, and nice to see other answers come through on Brent’s blog as well. What do you think of my approach? What would you do differently?