Programming Problem #6 - Maze Traversal (Advanced)

Key Takeaways

hey guys and welcome back so in today's video I am bringing you another programming problem and solution now I do these once a week so make sure you guys are staying tuned for those I typically try to release them on like Monday or Tuesday but at least once a week I'm trying to get one out now it's a new thing that I've kind of been starting so essentially the problem we're doing today is call is a biscuit maze traversal problem now I'll go through the exact specifications but I'm not gonna read this entire thing so if you want to read this it'll be on my website there'll be a link in the description you can go there and I'll have the PDF and you have a look at it also I don't make these I just find I got this off of the Waterloo website they do some programming competitions for high school students and I believe University as well they have a bunch of really complicated and good programs or problems on there and they also have the solutions and the test files so that's typically where I take my problems from now anyways so essentially what we're gonna be doing here is we're defining a maze and we have to find a way given any start room so starting in like room so there's a maze of a bunch of different rooms a bunch of different corridors that connect those rooms given a starting room we have to figure out how long it could possibly take us by traversing the maze to get back to our starting room so essentially taking any path throughout the maze how long is the maximum time like if we took the longest path how long would it take us to get back to that starting room and we're gonna do this in a certain way which you'll see in a second so the main kind of constraints on this maze are that we have n rooms connected by different corridors each room is in the shape of a circle now each corridor forms connection between two distinct rooms so no corridor goes into the same room there's no like big loop that goes into the same room which is actually really nice for us no two quarters will connect the same pair of rooms which again is also very nice which means that there's not two pathways going from like room 1 to room 2 there's only one way to go from room 1 to room 2 now each room will have at least one corridor that connects to it so that's not really that important but essentially it means we don't have any floating rooms that are inaccessible that we can't get to or like we start in a room and there's no way to get out of it something like that okay so is essentially the way that it's saying to navigate through this maze is since the lights are out that's what like the problem is the lights are out in this maze what we're gonna do is we're gonna in our starting room place our right hand on one of the somewhere on the wall so since it's a circle obviously it's one wall but somewhere on that wall we'll place our right hand now determining where we where we put our right hand will take us in two different corridors so we could place our right hand like maybe near corridor one or corridor two and we'll just keep following that in a counterclockwise direction until eventually we end up back into our original room if you don't know this is a thing with mazes if you're ever stuck in a maze you put your hand on the right wall and you just follow that right wall until eventually you end up at the exit or what do you call it like back where you started or something like that I don't know how this works mathematically but it does but it is shouldn't be noted that this could take you a very long time and that's what this is asking for how long could it take us so that's how that kind of works so yeah now there's a bunch of input specifications and output specifications and whatnot I mean if you guys are going to attempt to solve this problem I assume you'll be able to figure out how these work by just reading through them so I'm not really gonna bother but what I'll do is quickly go through an example of how the steps that we should take to solve this talk about the algorithm I'm gonna use and then go into the solution I will note this is a very complicated problem if you're not in university I don't expect you to be able to solve this even for myself like we haven't learned how to do this in class I had to do a bit of a research to kind of figure out the best way to approach this and my solution is far from perfect I'll tell you that so what I'm gonna do is just load up a little drawing thing here and let's do an example starting room at one so essentially the input right it gives us a maze and our main look something like this so it's saying like one is connected to three three is connected to one two connects to five 5 to 4 4 to 6 2 to 4 that's what this our maze layout now note that this is the same maze I know that one like these are not connected in any way but that's perfectly fine you can have kind of floating components now let's say we start in room 1 what is the maximum amount of corridors we have to pass through before we get back to room 1 well we got to go so we'll pick up we'll put our hand on any place on the wall let's say we choose here ok and we're gonna go counterclockwise like this and keep our hand on that right wall so that'll mean it'll bring us to here and then we'll go to here and then we'll come back so we kind of went like that which means that we passed through this corridor not one but two times so the maximum amount of time is to get back to room one starting in room one is two now obviously this is very simple because there's only one room that can external one so obviously that would be the only way this works but say three branched out like this and three went into another room well if we put our hands here and we go and we go well we're on this right wall which means that we now have to go into here and then we go here and then we go back back back so it would take us what do you call it four steps to do this because we had to go through this corridor twice so two like that then we had to go through this corridor twice so it took us four steps to do that so just another example now down here let's say we start in room two well we're gonna place our Wolf's place our hands summer on the wall but here's the thing we can place our hand somewhere on kind of like this section of the wall or we could place it right here now do you know why this makes a difference where we place our hands like if we place it somewhere here or if we place it somewhere here why will this make a difference well let's think about this for a second if we decide to place our hand on the wall here where I'm making the red dot what we're gonna go counterclockwise rooms we're gonna go this way I'm going to follow this right wall so we're gonna do something that looks like this until we end back up in the room which means we've gone through one to three corridors and we ended back up in room number two now that's fine that works but let's contrast that if we put our hand here same process we put our hand here now we're gonna go counterclockwise what we're gonna do though is we're gonna follow this path right and now we're gonna go into six which we didn't go into before we're gonna come back up into five and loop back in to here now that is one two three because we had to go through this corridor first or twice right four five so as opposed to the first solution we got which was three now we have five which means five is the maximum to get back into this room starting in this room I mean I can show you examples for all the other ones but I think you guys probably get the point now this is actually a really simple example of the maze I know this might seem a bit confusing because you have like paths connecting like that but now imagine that this goes on and it looks something like this okay and then these are connected and then there's one connected here and then this one connects to this room and then that connects to this right like geometrically this doesn't have to make sense the maze that it gives you it just gives you connections right so I mean like let's say we start here we going to five well we could go back like that but if we come into five on this angle right so if we come from four to five and we keep our hand on that right wall now we're gonna go into here and then we're gonna go into this and then we're gonna go into this and then right wall we're gonna go here and then we gonna go here now we're in six and now we're back right wall and now we're back into five right and then we go into this again so that's not a possible solution right so like that is a somewhere that we can run into an issue so we're gonna go through the kind of my solution and how this works but let's quickly talk about something called a queue based algorithm which is what I'm gonna use to solve this problem now essentially what I want to do is I want to try every single path that I can because I need to find the maximum distance to get into this like Inc back into this room so for this room we'll just stick with example two what I did was I said well what are the neighbors of this room well the neighbors I'm saying are gonna be four and they're gonna be five now these are the two rooms that I could possibly these are my options right when I start in room two I can go into room five or I can go into room for those are the two options I have so what I'm gonna do is I'm gonna say okay so these are our options well we start in room two now we can go into room five or we can start in room two and we can go into room for those are my two options now let's think about this though okay let's go back there if I start in room two so now let's say I decided let's cross this one out let's say I decided to go into room five okay that's the one I picked well what are my options now let's think about it we have to determine how we came into room five to figure out what room we're gonna go into next because well let's think about this if I come in from this way and I'm on the right wall I need to go into room before right but if I came in from corridor for I would have to go into court or two right I'd have to go to room two so we have to determine how we came in to pick the next room we're gonna go to so what we'll do is we'll look at this and we'll say okay so we from room to room 5 so that corridor is located here right so what's the next corridor counterclockwise that's closest to us well that's this corridor as opposed to let's pretend there was another one here okay that went into a room like that okay so we need to go into this corridor so we say okay so we went into five now since we went into five and we use that specific corridor which was two to five well that means that now we'll change this and rather than going from two to five we're gonna go from two to five and then the next one we have to go to is four so we'll put four like that we continue this process so what we do now is we say okay well let's see here so now we've we've essentially the path we've done is we've done two to five and now we're back to for now from four where do we go well again it matters how we came in to four because there's three ways to get into four you can go in from six to or five so we came in from five so we're on this right wall right so now we have to look and find the corridor that's the most counterclockwise the closest counterclockwise to us that's gonna be this quarter which goes from four to two which means that now the next room we have to go into is to okay sweet so we've done this we've now the first one is the same as the last one which means that we've reached the original room and how long did it take us we'll one two three corridors right because I mean you just count the the connections between the rooms really calm okay so that's how that worked now that's one possible solution right so we've exhausted this we've created this and we said okay so this leads to to a value of three but what was the other solution that we decided not to determine or not to go on yet well that was two and four so let's try two and four now let's clear all this and let's do two and four well two and four is like this right so we go here and remember we're on this kind of outside wall like that alright so if we come into for now we came in from corridor two to four so what's the next room we have to go into well since we're on this right wall and we're following that that means we got to go into the next most counterclockwise thing which is six so now we go from four to room six now let's look at this so six let's find the most counterclockwise room corridor 2 for like from coming in on four well that's actually for itself and that work that works fine we can go through the same corridor twice because it only has one corridor connecting to it so that's kind of a case is if you go into a room and only as one corridor connecting into it and it's not the same room that we started in just go back the other way but that still counts as a traversal because that's what we had to do right so we go six and then we go back to four like that so now let's let's look at this right so now what our path looks like is we've gone from two to four into six and now we're back into four but this time when we come in four what side do we come in we don't come from two anymore we're coming from six which means that we go to the next most counterclockwise thing which is five and then we go in five okay so it's odd five here and then from five what do we do well most counterclockwise which is two so we go into two and then obviously well we found our solution and now it takes one two three four five to do that so that is our answer and that's how the solution works and what we do to kind of simulate this right is well we start with a few different paths we start with two five two four and then we extend out and just kind of follow and loop through the maze and then get a list of a certain size and once eventually we have the start and the end the same we've gone back into that room which means that we're done we found a solution we're good to go awesome all right so my solution I'm gonna show you now is it does exactly what I just showed you except in code form now it's a bit confusing obviously reading someone else's code is not that easy but I'm gonna try to walk you guys through it and show you exactly how it works so just stay tuned for one second okay so what I'm gonna do for you guys now is run my script and show you it working and point out some kind of the flaws and then why the solution is not amazing but works so essentially the solution that I'm about to show you is exactly what I talked about it works in the exact same way it follows that procedure now it uses what's known as a breadth first search algorithm which essentially is what I showed you just creating a bunch of different paths and then kind of finishing those paths using what's known as a queue now this is a queue based algorithm I'm not really gonna talk exactly but what that is I have a video on my channel that explains that I if you need to link to that let me know and I'll send one in the description or whatever but anyways these are all of the test files that we have so essentially you can see we have these in files and these out files now the in files obviously like the number in number out correspond to some sample input and the expected output now what I did is just wrote a nice script that automated this process of testing all the in files and out files on my solution and then determining how many I got correct how many took too long or how many I got wrong now since you can see that some of these files are quite large for example let's look at mais 18 or even let's look at this one may is 25 if I edit this um you can see that this goes on for a long time in fact we have two hundred thousand lines of input so simply even reading this input and alone takes a long time let alone processing the information so we have a hundred thousand rooms and then for every single one of those rooms we have to determine how long it's gonna take so you can imagine that like a slow solution which is something that I have will not really work for this because it takes so long so there's obviously something that could be improved for my solution and I want you guys to help me if you have a better solution please like show it to me comment it down below because I've been trying to find a way to optimize this and I can't figure it out yet so anyways that's kind of like some what the input looks like I'll show you an output file so you get an idea this is not the corresponding one but I output right like like that's what an expected output is so anyways let's run this and I'll show you kind of how this this works so I time all my solutions just to see how long they actually take and I can give so I can see if I'm improving them when I'm making modifications but the timeouts are I time out ever after half a second so essentially if it takes more than half a second to find the solution I just say timeout because I really don't wanna sit here for a long time like technically if I ran this for a day it would get all the solutions but I don't want to do that especially not for the video so anyways you can see here so there's 28 problems I got 11 correct 17 timed out zero we're incorrect well I mean if you consider the timed out ones no answer and then it just gives me kind of an outline of the pound sign means I got it correct tea means time out and then so you can see all the different ones so I just wrote the script that does this for me it's not really a part of the solution it just automates the testing so anyways let's get into the code now and talk about all this so this would I'm about to highlight is the automated tester so what it does is essentially just opens all the in files and the out files in the directory and then just calls the function run to get an answer for the given for given input and then based on that answer compares it to the expected answer and then it'll tell you if you got it correct incorrect keep track and then you know give you a nice little output at the end I think it's a really easy way to test your programs really quickly now the actual solution is down here now essentially right like I'll read through this but it is kind of complicated how it works uh-huh and you're gonna have to look at it on your own if you really want to understand it but essentially given some kind of input what we're gonna start by doing is we'll create a blank maze dictionary what this is gonna represent is kind of the data structure of our maze so it's gonna store a bunch of keys which are between 0 and the amount of rooms and each of those keys will be corresponding to a node now those nodes are what is here now this node simply is just an object that stores all of the neighbors of a given way codes like room so for example all the connections to that room that's what we're storing I mean I didn't really need to do this as a class but I just felt like doing it as a class and that's all it's storing here so that's how we kind of are storing things in here now when I get the input I got to split it up into the different parts which is obviously the the actual room layout and then the rooms that I need to be count doing calculations are doing the solution for so I do that I just get the time before we start running the solution so that I can see you know how long it took to do something then I'm converting each line of input into integers because I need everything an int and then just what do you call it setting up this data structure of the maze with the key I which is the room I and then all the given neighbors now this is the actual real solution that's kind of just setting things up and since we're gonna have to do a certain amount of queries which is like however many they asked us to do calculations for we need to do the solution for each room so I do this this is gonna be the current max value of the solution we're looking for it's essentially how long so far has it taken us to get back to the same room pretty straightforward now I used a cue just simply import it out from Python import cue really standard and then what I'm doing is I'm initially starting off by setting up the past that we could take now those paths right and that's what this for loops doing are the ones that I talked about before like starting in room - we could go to room 4 we go to room 5 good room 7 right that's what we start off with there and then I add those into a queue and we constantly strip off one of the possible solutions from the queue and then just keep trying essentially is what we do so while the queue is not empty so while we haven't looked at every single possible solution we have keep trying now this is just responsible for the timeout it's simply saying if it takes more than half a second just just quit we're done this is gonna DQ which means get whatever solution we should be working on next so either adding to it checking if it's finished we're moving into a new room because each time we run this loop we for a given solution we go into like a different room that's that's how it works then we'll check based on whatever the current solution is we'll say well if the last element in that solution is equal to whatever room were in like the way that I showed you that means we've successfully gone back to our room so we'll check if this the length of that solution is greater than our current max if it is will simply say MX is equal to so our max the length of current otherwise what we do is we're gonna copy the solution and we're gonna add to it we're gonna add to it the next room we need to go into so what I'm doing here is simply just checking if there's only one neighbor we just need to go back into the previous room so that's what this if statement does but down here we're simply just gonna go to the next clockwise room and that's what all this is doing just making sure that we're going into them like the next room that's we should be going into and then I'm just checking here and saying you know what well if at this point we already gotten in this is meant to speed things up a bit if we've already reached that room that we to be in then just add one because well it would be one more solution to get in one more step to get in and then add that to the queue now I'm storing all these in the output and then we're simply returning at the end and this is how this solution works now again this is very slow because it's a queue based algorithm so there's a ton of different steps and it's running through like millions of times tons of operations you guys have a better solution this please don't hesitate to let me know really interesting problem if you're able to solve this give yourself a pat on the back because it is complicated and with that being said I'd love to hear you guys feedback on this I know this was a difficult problem but I want to give some of you more advanced people on something to look into and to challenge yourself with so that being said I guess I will wrap up the video here and I'll see you again in another one [Music]