Sessions is temporarily moving to YouTube, check out all our new videos here.

Interview Pro Tip: Travel Through Time

Kris Jenkins speaking at London Functional Programmers in June, 2017
22Views
 
Great talks, fired to your inbox 👌
No junk, no spam, just great talks. Unsubscribe any time.

About this talk

A beautifully coded solution to the tricky interview question "you're given a series of towers and the height of each tower as an array. It's going to rain, and the rain will fall on the buildings and fill up between the towers. How much water will be left when it stops raining?". Credit to Phil Freeman for the answer.


Transcript


Hello everybody. It occurs to me that one of the things that links all the talks tonight is mucking about with control flow. This talk, it starts from something I saw last year that is probably one of the most beautiful pieces of code I've ever seen. And I thought I'd talk about it tonight, partly 'cause not enough people have heard of it. It's not something I wrote, but I just found absolutely marvellous and I wanted to tell people about it. And also because if you ever talk to the guys at Functional Works, and you should, and if they ever set you up with a job interview, and they will, you might actually find this comes in handy for getting you a job. 'cause there's an interview question that's going around at the moment that's quite tricky. And there's a beautiful solution to it. 10, 20 years from now, this solution will be hung in the Tate Modern, and it will be worth seeing. The interview question is this. Imagine you're given a series of towers, the New York skyline rendered in ASCII ART. And you're given the height of each tower as an array. So positive integers. And it's going to rain, and rain not obeying real rules of physics will fall on the buildings and fill up between the towers. It won't fall down the gaps. It will slosh into a little pool like this. Your interview challenge, should you choose to accept it, is to figure out how much water will be left when it stops raining. And the answer looks something like this. It fills up here. It sloshes out this way and falls off, but it fills up in the gaps here. Now I think this is actually quite a tricky interview question. I was given it once and I think I got away with it. But it's a challenging one. And I thought there were no really great solutions, and I was wrong, there is a great solution. I will give you a moment to think about how you might solve this. That's all your time. The algorithm you have to figure out for this is for every tower you want to find the tallest one to your left, and the tallest one to your right. The highest the water can possibly go, if we're here, for instance, the highest it can go is the lower of these two towers. And then the answer for that particular tower is whichever's higher. The high water level, or the tower. Because that accounts for this case. Where it's the tallest thing there so the water can't go on top of it. Once you've had the insight in that you can probably muscle your way through the interview and get that sorted, but there's not, but the way you're probably gonna find thinking on your feet that you implement this, is here's a vanilla implementation done in Python, right. Initialising variables. And then scan from left to right, and pick up the maximum you've seen so far. And then scan from right to left, picking up the maximum you've seen in the other direction. And then one more scan from left to right to go through each of the heights and figure out the value. Now you've got the maximum to your left and the maximum to your right. In scope, you can actually solve the puzzle. So you do three scans through the array and it's answered, but there's nothing... I got this from Vikas Garg off the internet and with all due respect to him there's nothing particularly beautiful about this code. You know. Three scan through the right. But it will do. It will do. You'll get the job, I promise you. I don't promise you, I can't underwrite that. But it will do. Or, a much better solution, is you can use magic. And this is absolute voodoo, let me tell you. I got this from Phil Freeman. Phil Freeman is one of the people I follow in Twitter. And periodically he says something that I cannot possibly understand. And the process of trying to understand what the hell he's talking about sets me in an interesting direction every time. If you don't know him, you should follow him. He's the guy that wrote PureScript, or the guy that started PureScript. And he's great. And he wrote a solution to this which is marvellous, as I have said, but I don't think enough people heard about it 'cause it was a throwaway Tweet and a throw away gist so that's what I want to tell you about. Solving the towers problem is much, much easier if you can travel through time. If you can look into the future and look into the past, it becomes a really simple problem to solve. That's why you need a Tardis. This will solve your problem. If you can stand on one tower and look back into the past for the tallest one you stood on, and look into the future for the tallest one you will stand on, then you can solve the problem trivially. And that's what Haskell will actually let you do. You can write this code that says OK, I'm gonna use a Tardis. And past values are integers, and future values are integers and I'm gonna give you an integer when I'm done, right. Give me the height of the tower. Travel backwards in time, setting the maximum height of the tower to the tallest one we've seen so far or this one. Travel forwards in time, so that in the future when I read what the tallest tower will be it will be the maximum of this one or the tallest tower we will have seen. Once you've done that, you just look into the past to get the leftmost tower, you look into the future to get the rightmost tower, and you run the calculation. You're done. Easy. Except this shouldn't actually be possible. It doesn't make any sense. Setting a value to read later, we do all the time as programmers, so that's very ordinary. But reading a value that we'll set later is weird. It's totally weird. And it's magic of Haskell, and the magic of the Tardis monad. You can actually do this more concisely if you want to get hipster points for using the applicative. I throw that out because Haskell programmers in the audience will want to get hipster points for using the applicative. How many Haskell programmers do we have in the audience, by the way? Yeah. You know what I'm talking about. So, then to run that, we just do this. Which, I want to go through this in a bit more detail. Basically we're saying give me a list of towers. I will start off with the maximum height, each side being zero. And then I'll just run my Tardis over that list of towers. It will look, at each stage, it will look in the past and it will look in the future, and it will calculate out. And this code gives you the right answer. Quick pause in case anyone's got any questions so far. Do stop me for questions if you have them. Let's press on. So I thought I'd explain this a bit more, partly 'cause it seems like a secondary piece of magic. And partly 'cause if you don't do Haskell, this might be something that will help you get a bit of the types. So, the one thing I missed out in this explanation is this is only considering for one tower, right. How do you consider it for all the towers? How do you run a Tardis that works on all the towers in the system? And the answer is use traverse, which will, given the level function, it will turn into something that works in lists events. And it does it like this. When I was first learning Haskell, I liked these diagrams 'cause they helped me step through what's happening. The signature for traverse is, give me a function that takes an A, and returns some container of B. And a different container of A, and I will replummet, so you get one of these wrapped in one of these, right. So if you take that stepwise, if we say that T is a list, then we get this function, 'cause it's gonna be a list of integers. We say that A and B are both integers, and we get this function. We use syntactic sugar to put it that way, so it will fit on a slide. An then reformatting that, we get that, and we substitute in F, as our Tardis, the look backwards for integers and forward to integers, and we get exactly the function we need. Give me a function that takes an integer and return to Tardis the aeons integers, and I will give you a function that takes lists of integers and returns a Tardis that yields lists of integers. Right. Which is cool, 'cause that seems like an incredibly specific function, but because it's that function, I think it's in the core, it's in base. Yeah. Yeah, it's in the core library. So that's the secondary mind-blowing thing to me, that something that general can produce something that specific. I like that. Anyway, pause. Any questions about that bit? That's either good or bad, let's press on. So, how does the Tardis monad work? It's just crazy voodoo. It's actually Haskell crazy voodoo. There are a couple of things you need to know about it. So first, it's just a way of wrapping up double-handed state monad, if that means something to you. It's a way of saying give me a pair of values, which in our case is gonna be zero and zero. Give me a starting value from the past and a starting value in the future, and I'll give you back a pair of how it all ended up, and the thing you're interested in, right. If you know a state monad, it look more like single value, function from a single to a pair of the thing you want and how the state ends up, right. So it's a two-handed state monad with a specially-woven monad instance. First bit's quite dull, but I stick it in for thoroughness. It just says whatever the state is, whatever you give me, I'm just gonna return it with your X involved. That's the easy part. What's cool is this bit, which is how do you bind it all together? And if you squint, it looks a bit like a very boring bind run twice. You've got this structure. You run it with the input, and you get some stuff out. And then you run the function over the result, and run some stuff and you get one of those out. And it seems like vanilla plumbing. What's really interesting to note about this, is that X one comes out here. We plummet into here and we get X two. And then we stick that out. The forward running value, the future value. Sorry, the value that's going in the normal direction, we get one of those, we stick it in here, we get it out here, we stick it in here, we get it our here, and we return it. The flow is going from top to bottom. But the value we're going to try and read from the future, the value that we will read now but set in the future, goes in the opposite direction. We start sticking in here. We get it there, and we go up and up. And then we just spit it out at the bottom. So the way this works, is that there's one value whose control flow is going down, and the other value whose control flow is going up at the same time. Which in many languages would just blow up. But in Haskell, because it's lazily evaluated, you can trade memory for sanity, I think, is the best way to put it. You do need some squiggles, which I'm gonna hand wave my way over. I'm not going to explain the squiggles. But the core of it is this. Because you've got lazy evaluation, you can do this mutually recursive function where two values are going in different directions through time. And you end up with this really cool structure that lets you say, I need a value, there's a value I now I'm gonna be able to set in the future, let me read it now. And equally the other way. And you can solve this problem very elegantly. You might wonder, are there any practical applications to this, if scoring a job doesn't count as practical. I think it does. One obvious one I thought I'd give you is the X of Y problem, which is a real bind. You're rendering a document. You want to do the page count at the bottom that says page X of Y, which is a real pain because you need to know how many pages you've laid out in order to know the Y, right. You're laying out the pages in a document. You can't do that last bit of adding the page count until you know how many documents are laid out. How many pages there are. And you can't know that until you finish laying them out. It's a classic pain and report writing software. With the Tardis monad, you could know the final page count before you've even got there. Which I think is very cool. It's just, it's mind blowing. Let's have one last look at that beautiful piece of code, which I hope I've managed to transmit. This is actual working code, but I still find it mind-blowing that this can work. 'Cause it's reading from the future. And I love it. I think it's beautiful. I would thoroughly encourage you to have a look at the Tardis monad package on Hackage. There is of course a Tardis T if you've ever wanted to mix Dr. Who with Transformers. This is the closest you'll ever get. I'm on Twitter. You should definitely follow Phil, who's brilliant. Questions, please. - [Student] What if the types in this pair are different? - Let me get back to this. So, that's absolutely fine. The parameter's on that. So to give you my page count example, you might have separate types for current page and page total. That would be absolutely fine. - [Student] Can you change them? - I think we should have a look at the docs for the Tardis monad. I don't know if there is, 'cause there's nothing in monad that's gonna let you change that. 'Cause you're fixed in the monad of Tardis and the two specific first parameters. I'm gonna send you to the docs. There might be something in there that lets you change them. I feel I should say that we're a Kleisli category at this point. But I can't get away with that either. - [Student] Is Haskell the only language you can do this in? - I think you could do it in any language that had some form of lazy evaluation. So I think you could do it in Closure. I think you could do it in PureScript. But what makes it easier in Haskell is that because everything's lazy, you don't have to worry about the machinery of lazy evaluation. 'Cause it's already there and built into the language. I don't think any solution in another language would look quite as elegant. But it would still be cool. You get hipster point for that. - [Student] Does this work because it's got the whole cool graph first, and it's substituting values then? - Yeah, basically it's building up the competition as it goes along, right. What's really happening, is a big unevaluated function is being built up, and then right at the end when we call this, it's got some input values. It can actually start going through and figuring out what the result of each function is. So you do trade off some memory, 'cause you're building up a big unevaluated function. But that's a fair price to pay for beauty. I think that's the last question, so let's break for pizza. Thank you.