Coding Challenge 162: Self-Avoiding Walk

[Applause] hello welcome to a new coding challenge video this is part two not really or maybe it's part three or four of a video that i made four years ago in 2017 the random walker you're seeing the code for it right over there and every time i've ever demonstrated this example i've mentioned how one thing you could consider trying to do is something known as a self-avoiding walk a self-avoiding walk looks like this here's the wikipedia page for it it's a random walk where a random decision is made to move up down left or right but if that spot has already been stepped into then it can't be stepped into again and the walker has to choose a different direction and in theory it can create a path that fills an entire 2d space and i'm going to try to take this code example and change it to that today in this video if i have succeeded then in the magic of post-production the final results will be appearing next to me right over here if i have not succeeded then maybe nobody will ever be watching this ever again in the future we'll see let me first just review what is a random walker so this dot here is my random walker every frame of animation it can choose to go one of four directions up down left right once again here we see this is the visual result that we get from the random walker in order to do a self-avoiding walk i'm going to need some other data structure to keep track of all of the spots inside of this 2d world by the way we should really try someone should try maybe i will making a 3d version of this if i get this done but we'll come back to that another time if i think about a very small 2d space that's five by five and let's say i start the random walker in the middle as usual now if it randomly decides to go up it can go there maybe it decides to go to the right maybe it decides to go up again maybe it decides to go to the left now if it were to try to go this way down to this spot that's already taken it can't it can't choose that anymore instead it should choose to go here so i need some type of data structure to keep track of whether a spot has been hit or not and so that could be a 2d array and i can just put the boolean value false in all of the cells and then if it's been there i could put the volume i can flip the boolean value it'll true and i can use that as a way of checking whether it can go there or not i'll try that in code now getting started i'm just going to add one variable i'm going to call it grid that variable grid will hold the two-dimensional array for every spot in the canvas so i need to make a two-dimensional array which is kind of a wonky thing in javascript fortunately this is something that i've tackled numerous times i think the first time was in my mind sweeper coding challenge not the first time i ever made a 2d array but kind of talked about it in a video and in the code for that example i have this make 2d array function i'm going to grab it copy it over here to my new self-avoiding walk i'm going to change this to let and then i'm going to say grid equals make 2d array and have one spot in the array for every pixel do i really want to do that i think so that i can sort of see what's going on more easily i'm actually going to start coding this by thinking of the 2d canvas as much lower resolution so i'm not going to i'll make it 10 by 10. in other words i want a variable called spacing knowing it's a 400 by 400 canvas i'm going to make it 40 and then i need to have columns and rows all right so i've changed this so that instead of just having the random walker walk along every individual pixel i now have a set of columns and rows based on a cell size a spacing valve variable and then my xy position of the walker is going to be in the middle and so when i go to draw the walker instead of i'll just leave it as a point but i'm going to make it uh the stroke weight uh this half of the spacing let's just see that and then the walker should move instead of one pixel according uh according to the spacing i'm not sure what i just did there oh whoops i got a major error i still made the grid with height so the grid needs to be based on the columns and rows oh and of course the point then isn't just x y it needs to be x times spacing y times spacing oh and it can still go by one i see i can have it changed by one i need to have it move according to spacing i'm just going to uh draw it it's still moving one column and one row i'm just going to draw it by multiplying spacing got it there we go there's my random walker now just to be sure that this is working the way that i think it is i'm going to make the spacing 5 and then we can see yes so already by the way this is kind of an interesting uh different visualization of the random walker you can see that since i'm drawing it with alpha you can see how many times it's been in a certain spot based on how bright that spot is getting but the point of what i wanted to do here is i want it never to be able to return to the same spot again it needs to avoid itself a self-avoiding walk back to 10 by 10 with uh no alpha first thing i want to do is fill the grid with the value false so a nested loop to hit every column in row set to false then wherever the walker is that spot should be set to true because the walker has been there and as it moves the new spot every time in draw should be set to true ah what happened ah there's an infinite loop problem i forgot to change that i to j oh what a nightmare let me fix that and see if i can run it now okay great oh we just went straight down why is that was that just a coincidence yes that was just a coincidence so i've got an error as soon as i fall off the canvas now i think i need to rethink the way i'm doing this right because now i can't go every possibility i can't go one of all four options if i'm here i can only go one of three because i can't go down to where i've already been so before i pick which way to go i should check all of the possibilities so checking to the right as long as to the right is false and i'm going to make an array called options i'm going to put all of the options in there options dot push and i'm going to make a little object that says uh oh oh oh i i have an idea i have a better idea of how to do this this is a little bit weird but just just bear with me for a second i'm going to just make a global variable called options this is all the ways i could always possibly possibly go and it's going to have four objects in it each object should represent to the right down to the left up and i'll call those dx as in delta x delta y so the first option is to the right delta x is one d y is zero so i've now very obsessively made an array of objects each object storing an element that indicates a direction right left down up so then right here in draw i can just check all of those and see can i go in those directions let every option of options new x the next x spot is x plus option dot x so this is the new spot if the grid if that spot on the grid has the value false then it's a it's a perfectly fine option for me to take and i'm going to call this variable all options i'm realizing i could use in a very clever way the higher order array function filter i'll leave that to you as an exercise i have a video about the filter function maybe i'll come back and do that later myself but i want to just write it out the very long-winded way just to really understand what's going on so i'm going to create a a separate array called options and if it's a valid option then i will add add it to this options array now i realize i'm making this kind of confusing because i'm saying options i'm saying option and i'm saying all options let me just explain that for a second all options is all the possibilities no matter what like it's a global variable it's never going to change now i need to know which options are valid in this particular circumstance that's going to be my array options so i'm going to look at every option in all of the options check to see if it's valid and if it is put it in this new options array so that i can say like step equals a random option then x plus equals step dot x y plus equal step dot y and i've moved to the next one so this is just checking which ways can i go and moving forward cannot read property and not a number of undefined sketch line 52 oh i called it dx so this is dx this is dy and this is dx and this is y there we go perfect you can see and i think it would be helpful for me to draw a line between the two i'm going to use begin shape and end shape to do that this is i think this will work what did i get so by the way what i'm trying to do here is say begin shape and end shape draw a line between two vertices the vertices the vertex xy then move to the next place and then set the next vertex why didn't that work oh i forgot about multiplying it by spacing oh i'm always forgetting this time spacing there we go so we can see the self-avoiding walk now i'm getting an error when it reaches the edge so i also need the uh it to be invalid if it's not a proper spot in the grid so as long as new x i'm gonna i'm gonna write a separate function i'm gonna say as long as is valid new x new y and it's not and the grid spot is false so i need to write a new function here let's say function is valid i j let's just say it's oh i could actually do both of these in the function let me do this so if i is less than zero return false so it's not valid if i is off the edge so i is less than 0 or i is greater than columns greater than or equal to columns j is less than zero or j is greater than equal to rows so if it's off just that's false otherwise return grid i j this could be consolidated into one simple line of code but i'm just basically checking is this a spot that i can go oh return not grid because it's taken if it's true i should not fill them all with true and then i can't go there if it's false whatever you work that out how do you think about this i was thinking about it's taken i flip it to true so it's valid if it's not true if it's false oh boy i really made a i really made a mess of that but there we go ah so when do i get an error here if there are no options so i can say if options dot length is greater than zero do all of that otherwise console log i'm stuck and stop the program from looping let's change the spacing down back to like 10. and there we go we have a self-avoiding walk we're done are we done in a manner of speaking i'm done if a wise person would stop right here and say now as an exercise to the viewer can you figure out how to if you get stuck go back and try a different direction so that's what i mean i could make that a part two but i'm just gonna plow forward so if you want pause make something out of this i think there's a lot of possibilities of things you could create if you want to stick with me i'm going to keep going and work on what's known i think it's what's commonly known as a backtracking algorithm so i have tackled this before all of my maze generation videos i think it's a four-part series about generating mazes those involve a backtracking algorithm where i'm keeping track of everywhere i'm going and if i get stuck i can go back and try a different way i get stuck again go back and try a different way so to do this i need a couple uh key things one is i will need definitely need like a variable i'll call it path which is an empty array and that will sort of keep track of where what's my current path that i'm on so that at any point i can like back up and keep go try a different way so i need that let me make a simpler a three by three grid i think will help us understand this better okay i'm gonna go to the right i'm gonna go down i'm going to go down i'm going to go to the left i'm going to go up i mean it's to the right but i turned left and then i'm going to go up and realize like nope no more options so i need to then go back to this one i already and i need to remember that i already tried to go this way so now there's still no more options i need to go back down here back down here and then i see i remember that i tried to go this way so don't go that way but i can see i can go this way oh that's going to get me stuck eventually i'm going to realize i have to go over here from here so uh how did i thought that diagramming this would really help probably if i had like a very clever animation to explain it that would really help but i think the way to make this make sense to you the viewer right now in the context of this video is i need an object i think i need a cell class let's call it spot so these are all of the spots a class spot and the spot will have that array of options but the options have not just dx and dy they also have a uh like a variable called like taken was it taken already was it tried maybe i call that tried and it would be false at the beginning so i'm keeping track of what was tried and what wasn't tried is that a grammatically correct sentence i am not sure but i'm just gonna keep going first step let me make the spacing 100 so we can really see this very clearly oh and you know i'm realizing everything has shifted a little bit up and to the left i need to just like translate the whole world down a tiny bit uh translate spacing by half of spacing oh i put that in setup how silly me that has to be in draw there we go oh look i did it perfectly that actually hit every spot what a lucky coincidence but most cases that won't happen all right so now it's drawn correctly but i need to change it to say background zero so now that i'm erasing the background i don't see the full path so let me add this variable called path and then every time oh every time i go well i want to keep track of where i was so i could make an object to keep track of where i was but i think this is where i need that spot class so i created a javascript file called spot.js and added it to index.html and i just want each spot to keep track of all of the options but i how do i copy an array matter how many years i've been programming i have to google how to copy an array in javascript it's just the way it is for me for you for everybody we all do it amazingly though i forgot that is this called the spread operator right here thanks to this webpage that i just found from samanthaming.com how to clone an array i forgot i need to make a video about that spread operator i will do that i will do that mental note remind me in the comments and by the way i can't just use equal because i need to make a copy because i want to manipulate it and i want the original array to stay the same i'm going to use slice right now because i know slice will work and eventually i'll learn this other dot dot operator but also i want the options now to each have with them a variable that keeps track of whether it was tried or not so this is really becoming like a template by the way if you're wondering why it looks like this now i used the auto format which then got rid of all my perfect spacing oh so now each spot has its xy position oh you know what i should do i have an idea i have a really good idea this should actually be the xy position should be its actual pixel location and i'm going to call its index into the columns and rows i and j that way whenever i want to draw it i can just grab the x y and whenever i want to like look up where it is in the array i'm going to give it the i ij so now essentially here this grid instead of the grid just having false or true in it i can put a new obj spot object to keep track of all the metadata associated with that spot there oh and i guess the spot itself should know whether it was visited and that would be false so what whether the spot was visited so there's two i'm not only keeping track of which directions out of that spot have been checked but whether that spot has even been visited at all and so i would say grid x y visited equals true also path push grid x i should put that spot into the path i see maybe i don't actually want that x and y variable at all maybe i do i'm not sure but i definitely need a variable called spot so that's the current spot so the current spot will be grid x y e you know what i've got it i've got it i'm going to get rid of this x y entirely this makes total sense now i don't need this x y the whatever the current spot is that's the current x y but it's i j in there so this will be grid and i'm just going to start at 0 0 that's going to be simpler i'll just start in the top left and then that spot has been visited and it goes in the path then this code that picks the next spot that should actually be in the spot object except itself like spot should have a function called next spot and there i'll do this code i'm just going to paste that there for a second i'm noticing this will now be spot.x spot dot y and all of this i'm not going to worry about drawing it right now let's just take all of this that should also be here so i want and i'm going to make this i'm going to it'll be a longer name but it'll help valid options let valid options of this dot options check for the new x and this is this dot i this dot j if it's valid i still need that function push it into the valid options if the valid option is greater than zero do all this i kind of want to take the drawing out for a second because i think that's going to be important to not have that in here but definitely pick the next step from the valid options and then return i know i should just return the next spot in the grid this dot i plus step dot dx this dot j plus step dot d y and then if i get to the end and there are no valid spots return undefined is this really right find all the valid options for this particular object and i'm also going to check whether was it tried already but i'm going to get to that right now i'm not going to worry about that why do i have an error here not a comma this is a two dimensional array that's the next spot in the grid is this dot i plus the step this dot j plus the step so back in sketch let next spot equal spot dot step and actually the spot i'm just moving to the next spot is it is it called step next spot spot dot next spot but i could really use some naming help here if there is no spot console log i'm stuck i don't know why i'm saying i'm there is no it's not a person it's not an eye it's a thing i'm just gonna say stuck there's almost zero chance that i haven't made a mistake here but in theory this should be exactly what i had before option is not defined spot line 14. oh my goodness this is let option that should not have changed to valid options [Music] that was the option of all the options check every option see if it's valid put it in the valid options one mistake stuck interesting did it go anywhere i didn't even know it going anywhere hmm all right i gotta debug this console log spot okay the very first spot was undefined let's see did i get some valid options for that spot no oh my is valid function is no longer uh correct it is valid if it hasn't been visited so if grid not visited i forgot that i made each spot in the grid an object so i have to explicitly check the visited boolean variable there let's see what happens now it seems to be having a fine time going forever oh i'm not setting the thing visited when i got there so right here this setting of the spot to visit it in setup i should be doing that for every new spot every time in draw so i'll just put that right at the beginning of draw and let's try this again all right then it gets stuck i can get rid of this console log valid options um i want to put back in the line well actually what i want to do ah before i put back in the line the whole point is i have that path variable so every time i get a new spot i'm going to put this also in draw i'm going to push the spot into the array and then i can draw everything so now this should be drawing the line through all the spots perfect so i could keep drawing circles and lines or whatever but i kind of like the way this is visualized right now so i'm just going to keep it getting really close i mean i've left the most difficult i think what is the most difficult part to the end but hopefully i've built a pretty good foundation for doing this i need to backtrack so if there are no spots left and i'm stuck instead of just stopping what do i need to do i need to go back to the previous spot let me just save previous i'm going to like temporarily save the previous one so that if i'm stuck i can say spot equals previous and i can try another way let's just see what happens if i do this well there aren't other ways for it to try every time it's stuck i can't tell if it's trying going back and trying a different way oh that's the spot that's stuck i can't try a different way in the spot that's stuck i have to remove it and go back to the previous previous one oh that's easy i have it in an array never mind i don't need this because i have it in an array if there's no spot path dot let's get rid of one pop stuck equals pat take that spot off i'm stuck so pop that spot off the path and then the spot is now the last one in the array now can i is there something called pop that i could do without removing it from the array i'll just say path path dot length minus one so i'm just getting rid of that spot and going back one i can't tell yeah yeah did you see it went ahead and then it went back i think that's still stuck so something is kind of working here but i'm missing so many important steps that i can't tell if i've really got this right the thing that i haven't implemented at all is whether whether a direction has been tried or not remember with all the ways that the walker could go i set all of those possibilities as tried false to start with so that i don't try them again so right here if i am going to pick this particular option this step i need to set that it's been tried then as long as it's a valid option and that option was not tried already then it is a valid option options is not defined oh and and option.tried getting stuck pretty fast oh well certainly one thing that i need to do is once i'm removing it it's cleared like it's not part of the path anymore any ways that i tried i could be coming at it from a different way so i should clear all of that meaning i'm gonna i'm gonna call function called clear and definitely say it hasn't been visited like i haven't been visited and reset all of its options okay i'm very close i think there's now this is going to be really challenging to debug i'm not really sure how i'm going to do it because obviously it's kind of working but it gets stuck immediately i think maybe there's an issue with the fact that i'm adding it to the i think i should only add it to the path if it's valid so i think if there's no spot otherwise yeah yeah i shouldn't be i'm always adding it it's just getting added back in so i should only add it to the path if it's the next spot that's valid and then in that sense and say that it is visited and in that sense maybe i will go back and just do a one-time ad in setup for the first spot i think i got a little bit closer there but it's really not working oh boy i'm gonna try setting the frame rate to 1. okay let me set the option the spacing back to 100. so the point is always one point behind and then oh it gets off that so visually there i mean there might be a better way to debug this but visually i'm seeing something quite off in that the end is like lagging behind and then all of a sudden it skips ahead and then that's lagging behind so something's really wrong oh well this is it has to do with drawing this here what if i draw it down here it shouldn't make any difference oh yeah now it's at the end oh it's backing up it definitely is backing up but it's not able to try a different way i'm just gonna shut off this step dot tried for a second aha okay this is right now in that it is going back and trying other ways i think i'm realizing that this is a major error right here all options dot slice i am making a copy of this array but inside the array are four objects and i didn't copy each and one of those four objects i really should make this into a class like i should make a step class but i was trying to like get cut corners by just using some object literals and i think i let myself into a big problem i led myself down into a major error there oh boy so i'm going to add another class here i'm going to call it a step every single step has a direction it's either left right up and down and whether it was tried or not and instead of just copying from a global array here let me write a function called all options and i'm going to return i'm going to manually make a new array with new objects in it everything's brand new it's a new array with new objects new step 1 comma 0 comma so now this function all options will make an entirely new array of new objects all with visited set to false because i was setting visited on one and it would set them then then every single spot everywhere had thought it had visited everybody to the right and left and i was a mess not visited tried tried visit it is for when you've been there try this when you tried to go there this is very dramatic because i set the frame rate to one while i was debugging yeah yeah oh it's going it's going it's trying it let's set that frame rate up back to 60 frames per second everybody it's trying all the possibilities it's gonna get it eventually oh i'm not sure i uh set any condition to stop when it gets it it might have gotten it already yeah all right let's set a condition for when it needs to stop so when is it done if it's hit every point alright so if the path has as many spots in it as every spot on the grid it should be done i'm going to try running this again it'll take a little while but hopefully it's going to stop and we'll see console log solved right there in the content i'll wait oh i got there let's pump up the resolution a little bit i should point out that this is a brute force solution so i don't actually know if this is ever going to end i'm going to wait a little bit longer while this is running i'll also point out that i probably should have used recursion for this so i will include in this video's description a link to a version of the code with recursion a function that calls itself maybe that would have made it easier more elegant more beautiful i'm not entirely sure i can come back and revisit that in another video but for now i i kind of like the way that i had to work it out this way okay i'm much too impatient i want to know that this really works so if i look here at the draw loop i do see that this right here is me checking for the next spot so there's no reason why i couldn't just ask to do that multiple times per frame which won't make the algorithm go any faster but i will do multiple times through the algorithm per frame of animation which will let us experience it in a faster way so let's just try saying uh four let i equal zero i is less than let's just try it a thousand times each frame and then also if it's solved not only do i want to say no loop i want to break out of that loop and let's see what happens here yeah so you can see i'm already you could sort of see the speed at which it's getting through all the possibilities now a thousand probably isn't even enough for me to make any significant progress here let's let's try a hundred thousand i am much too impatient i'm going to go up to 500 000. oh you can see the frame rate is starting to dip now so at a certain point it's sort of diminishing returns here i might be able to get more checks through one cycle of draw but if the animation is going too slow then what's the point right i'm going to hope that this actually ends at some point in the next somebody probably calculate the number of possibilities and the probability that it would that i would have uh get it within a certain amount of time well this doesn't seem to be finishing anytime soon i'm trying to think about what the big o notation of this algorithm this is a brute force method doing a little research about this while i'm waiting for this also it should be clear how this is highly this is a graph theory problem i have a graph in other words i have a system a 2d grid each one of these spots is known as a node the nodes are connected via edges and i've done several problems uh other coding challenges i'll put links and all the stuff flying around to those previously in the video's description but essentially here um you know i have the algorithm that i'm using to find a self-avoiding walk that hits every spot even in just an eight by eight right so it's n squared for sure in the sense that if n is 8 there are 64 spots but then for every spot i need to check every other remaining spot i think this is going to be like n squared factorial or something insane oh that's a big number i did a quick calculation here um that's what i got for 64 factorial meaning uh it's a one with 89 zeros so um i don't think this is finishing anytime soon so definitely i will need to revisit this with a more efficient optimized algorithm i could probably find one just to point you the audience to very quickly so first of all look at this calculating the number of self-avoiding walks in any given lattice is a common computational problem there is currently no known formula although there are rigorous methods of approximation i see here that there's a pivot algorithm to try randomly choosing a point and then applying symmetrical transformations well as we can see here i'm finding a lot of interesting papers about self-avoiding walks and i realize i'm definitely gonna have to do some more research into what are some known optimized methods or techniques for approximating a solution to a self-forwarding walk this kind of reminds me of the traveling sales uh sales person problem which there's like i'm sure some relationships here as well maybe i could use a genetic algorithm and try to evolve an optimal uh self-avoiding walk i have no idea uh i hate to stop this because someday it's gonna end but i actually what i want i'm curious to do right now is just go back to uh it doing it just once per frame and upping the resolution quite high to something like five i'm going to hit save i think you know you might find that this even on its own is quite beautiful just the process of trying every possibility in a space so vast is really quite delightful to look at and experience and i think there are probably many unique visual outcomes that could come from this one i suggested is try extending this into a 3d space what would happen if you did that i'm sure you can think of ways of playing with color and other kinds of generative visuals or tying this to something else i look forward to seeing what you make of this code um i will certainly revisit this in a live stream at some point after this is released so at some point hopefully you'll see a link in this video's description to a live stream where maybe i look at some other examples and make some further improvements to this but if there is a kind of uh optimal a better algorithm that i can investigate and come back and do a video on um i definitely will so um let me know in the comments i'm sure i made countless errors here in this video in terms of talking about um the big o notation of this particular brute force methodology but i hope that you enjoyed this video and i did actually make a self-avoiding walk um and i'll see you sometime else on the coding train goodbye [Music] you

Channel: The Coding Train

Views: 57,203

Rating: 4.9573822 out of 5

Keywords:

Id: m6-cm6GZ1iw

Length: 38min 26sec (2306 seconds)

Published: Thu Jun 10 2021