Learn You a Haskell for Great Good! - Miran Lipovaca [93]
50
10
30
5
90
20
40
2
25
10
8
0
To mentally parse the input file, read it in threes and mentally split the road system into sections. Each section is composed of road A, road B, and a crossing road. To have it neatly fit into threes, we say that there’s a last crossing section that takes 0 minutes to drive over. That’s because we don’t care where we arrive in London, as long as we’re in London, mate!
Just as we did when considering the RPN calculator problem, we’ll solve this problem in three steps:
Forget Haskell for a minute and think about how to solve the problem by hand. In the RPN calculator section, we first figured out that when calculating an expression by hand, we keep a sort of stack in our minds and then go over the expression one item at a time..
Think about how we’re going to represent our data in Haskell. For our RPN calculator, we decided to use a list of strings to represent our expression..
Figure out how to operate on that data in Haskell so that we produce a solution. For the calculator, we used a left fold to walk over the list of strings, while keeping a stack to produce a solution.
Calculating the Quickest Path
So how do we figure out the quickest path from Heathrow to London by hand? Well, we can just look at the whole picture and try to guess what the quickest path is and hope our guess is correct. That solution works for very small inputs, but what if we have a road that has 10,000 sections? Yikes! We also won’t be able to say for certain that our solution is the optimal one; we can just say that we’re pretty sure. So, that’s not a good solution.
Here’s a simplified picture of our road system:
Can we figure out the quickest path to the first crossroads (the first dot on A, marked A1) on road A? That’s pretty trivial. We just see if it’s faster to go directly forward on A or to go forward on B and then cross over. Obviously, it’s faster to go forward via B and then cross over, because that takes 40 minutes, whereas going directly via A takes 50 minutes. What about crossroads B1? We see that it’s a lot faster to just go directly via B (incurring a cost of 10 minutes), because going via A and then crossing over would take us 80 minutes!
Now we know the quickest path to A1: Go via B and then cross over. We’ll say that’s path B, C with a cost of 40 minutes. We also know the quickest path to B1: Go directly via B. So that’s a path consisting just of B for 10 minutes. Does this knowledge help us at all if we want to know the quickest path to the next crossroads on both main roads? Gee golly, it sure does!
Let’s see what the quickest path to A2 would be. To get to A2, we’ll either go directly to A2 from A1 or we’ll go forward from B1 and then cross over (remember that we can only move forward or cross to the other side). And because we know the cost to A1 and B1, we can easily figure out the best path to A2. It takes us 40 minutes to get to A1 and then 5 minutes to get from A1 to A2, so that’s path B, C, A, for a cost of 45. It takes us only 10 minutes to get to B1, but then it would take an additional 110 minutes to go to B2 and then cross over! So obviously, the quickest path to A2 is B, C, A. In the same way, the quickest way to B2 is to go forward from A1 and then cross over.
Note
Maybe you’re asking yourself, “But what about getting to A2 by first crossing over at B1 and then going forward?” Well, we already covered crossing from B1 to A1 when we were looking for the best way to A1, so we don’t need to take that into account in the next step as well.
Now that we have the best path to A2 and B2, we can repeat this until we reach the end. Once we have calculated the best paths for A4 and B4, the one that takes less time is the optimal path.
So in essence, for the second section, we just repeat the step we did at first, but we take into account the previous best paths on A and B. We could say that we also took into account the best paths