it's funny how in the first video you say "this is just the first of a series about random walk" and now after just 4 years out of nowhere the second part

ohhh I was a freshman when pt.1 came out. Now I'm graduating this July. Good times. I learned so much from Dan.

Daniel. Might I recommend that you market a coding train stress ball with a face on it. We'll call it "This Dot" and we can all use it to calm down after tracking down yet another "this." omission. Then, perhaps by virtue of having This Dot on our desks, we'll be reminded to watch for those "this."s and begin to avoid those errors all together.

This is my favorite series in this channel, I always learn a lot with these

This video is so great. Starts of what appears to be a pretty simple problem and turns into this whole thing that has research papers behind it. Love that!!

Aaaaaaah CODING CHALLENGE! Finally. So many memories, it’s like going back to a place where you haven’t been for so long.

The relation to the mathematical complexity shown at the end was really insightful and always great to see in your videos!

I love it. It brings me back to the days, where I started coding on a vic20. I don't care much about the specific IDE or programming language, although I am a big Fan of Processing/Java. When I was 16 there was no internet, I never heard about backtracking and the teachers had no idea, too. But everybody was excited to try everything out. The Main Topic here is depth-first-search plus backtracking, right? Thats a power-combination for a lot of interesting applications.

I love the new edit style, a nice way to avoid viewer frustration with the this. Haha! love all your videos!

Your video quality is really top tier here damn:D all this editing really surprised me because ive been watching some older videos

This is excellent. The whole channel is. Many thanks!

Yessssss finally another coding challenge 😀

I will never get tired of these

I really enjoy your channel I’m glad you’re there for beginners like me

Happy to see your videos again :) Love your work :)

it is always fun to learn from you. Thanks alot.

This self avoiding walk reminds me of the "Knight's Tour" problem, where you have to find a sequence of moves so that a knight visits every square in the chessboard just once. Prob impossible to brute force it, but there's a few neat algorithms you can use to solve it. I'd love to see you tackle the Knight's Tour, but if not I'm sure some of the ways to solve it are probably applicable to this.

the pacing of his videos is so perfect not to fast to not understand but also not slow enough to get boring and sit through boring commentary

I do love this series when you post them, couple of things I noticed which might help improve the algo. 1. pick a random direction and then see if it's valid. You have a one in four chance the random is valid, but determining before hand means you hit all of them before even trying 2. If the goal is to fill the space and not just walk, you could eliminate options that are not worth trying again as entering at the same point and doing the same path multiple times when nothing has changed is expensive. One option might be to calculate some form of hash of the outline of the available spaces ahead and store it in the grid space as the last tested hash, the next time it goes to that spot if the hash has not changed the spot can be excluded.

Good Job Dan! Very entertaining.

Man I was so waiting a part two. It was quite a long wait.

For the past week I've been working with AStar search using two different languages. The idea that you're backing up and trying a different route is very similar to how AStar is structured.

Love to see the applications of graphs, dfs and hamiltonian paths ❤️😉

I like the post production animations in the last few videos! Also, personally, I’m glad you did it the non-recursive way. Everyday I try to avoid recursion everyday.

I lov coding challenge, hope episodes would be frequent

I really do enjoy these little code challenges - would like to see some notes on Memoisation (memoization to you, I suppose). Not sure if I've heard you mention that before. It would certainly speed up your algorithm as at a certain point you'd know the remaining moves are already solved. Thanks for sharing!

Thanks a million! You are so funny! 😂😂😂 You made it easy!

I actually created something like a self-avoiding walk, where I generated a maze of rooms. Every room had at most 4 exits, and at least one. The entire floor(4x4 rooms) would always be fillable. The rooms were generated the moment you would go through the corresponding door.

First time here, I really enjoyed watching! I guess the problem in the end with the program not finishing in a reasonable time is it trying to solve the problem from the wrong end of the path. This may be a complicated spaghetti code suggestion, but it should be way more efficient than a brute force approach. Whenever you check for valid options and find that your current position is next to an earlier position, you should check for "air gaps", any spots that are enclosed by the path but not visited, and if there are air gaps found, make it "stuck", so it will recognize way earlier whenever its current path is in a state that can't lead to a solution-

First thought for optimizing was to check for islands (if there's more than one) from the nearby nodes as early as possible. If there's a node that you can't get to in the very beginning, it will try that part again very late. Also backing up one node might not be enough to have an egress path - island entry path blocking the exit.

For cloning the array, the option to do newArray = [...array]; creates a new array by the square brackets and then file with ...(or explode array values) into that new array. So a true copy, not just one equal to another.

Depending on how much you want to exploit knowledge of the board, you would need to look for isolated pockets. IE, you cannot have two divided sections. All the flailing at the end is pointless until the two areas are made contiguous again. Another optimization (Not sure quite how you would implement it) is that many of the section configurations are repeated with only a tiny change up stream of the section. You could possibly use a cache of some sort to avoid duplicate fills of an area that got stuck. Notably near the end (37:00 for example), it keeps trying to fill that same space with the same last ~12 steps while only making a tiny change (extending the end-13th position slightly). You could subdivide the grid and take hashes of each chunk at different depths and if you're entering a chunk you've already explored all the leaves for you can just skip it altogether. I guess start the grid at the smallest size that you can create a dead-end for. (IE, 2x2 is not useful, but 3x3 is). Further you might have a node above that which hashes the value of the leaves so eventually you can exclude a large number of options from each starting point. There is probably a worst case scenario due to alignment of the grid to the paths that makes this not reliable.

You can try to use vertex cover on a graph (nodes in a grid) to find an approximation of the solution.

I think one of the best ways to make a perfectly space filling self avoiding walk faster would be to use an idea from space filling curves and use smaller chunks of area, where you can have a set start and end location (in the first chunk this can be randomly selected), find the small space filling walk then go to the next chunk and use the end location's mirror as the start location. In the bigger scheme you can have an order of magnitude smaller than the walk you're trying to work out to find out the perfect space filling position for those chunk's end locations to be in. It would be much more restrictive of a walk but still give a similar end result in a much smaller amount of time, just with less availability for giant lengths of single direction movement, which in some cases would be more desirable. I'd imagine you could also work out the math so that the shape of the smaller chunks are variable to add more variation to the walk if desired.

I wrote a pathfinder for playing snake a while ago. Finding the shortest path to the apple works well for a while, but once the snake gets longer i found it worked well to completely flip the metrics for the path finder, so instead of finding the shortest path it would try to find the longest path. Perhaps you could score each new option based on the distance, and pick the one furthest away from some location. In my case i was avoiding the apple, but you could try avoiding the opposite corner from the starting location, the starting location, or even try finding the "center of mass" of all the unvisitid cells, which might make a nice spiral. Adding a random component to the score would also make the path more interesting but still smarter than just full random. You could also try staying as close to the starting location as possible.

There is easy upper boundary of number of variants for backtracking. Any valid walk is starting point + sequence of letters UDLR (up down left right) of length W*H-1 where W and H is width and height respectively. Thus, straight ahead you can say that backtracking will do less than W*H*(4 to the power W*H-1) which is much less than factorial(W*H). Next, it's easy to notice that after each letter there is exactly one forbidden letter: after U you can't have D, after L you can't have R and so on. So, at any place for fixed previous letter there is only 3 options. Therefore, upper bound is W*H*4*(3 to the power W*H-2). Similarly in the end there is exactly one spot missing, and in last two steps exactly 2 spot missing, so upper bound W*H*4*(3 to the power W*H-4)*2.

Hey, you need to backtrack until the spot nearest to the beginning of the path instead of the last one available. This improves the speed on smalled graphs.

Feels like you need a Hilbert curve although boundary alignment would eventually be an issue. I tackled a similar problem trying to maintain cache coherent vertices with triangle strips on a mesh years ago. It's a very computationally complex challenge if seeking to optimize / space fill. The complexity is ~ average available choices at each location raised to the power of how far ahead you want to search * the number moves you need to make to complete, very approximately. Taking an accidental lesson from my coherence requirement, perhaps look for affinity for adjacency to the existing filled path so you space fill without leaving gaps. I ended up building move heuristics to avoid isolating inaccessible regions but that gets expensive too (I was simultaneously optimizing for other things [vertex attribute cache coherency]). One other suggestion, have space filling path segments and link them and mutate / anneal them (genetic algorithm) to simultaneously generate and converge on a complete continuous space filling path rather than grow it from the start.

Nice! A 2D random walker. I just realized that every line in the cosmos could be a 1D random walker 🤩👍

(i have not finished the video yet) For the backtracking I use a variable count and instead of attributing the grid to bools i attributed it to int. So each case you attribute the value 0 and the starting value of count is 1 if the value of a case is

to make the algorithm more efficient you could flood fill the area that lies ahead of the walker and see if the spots contained plus the points already stepped on equal the amount of total spots on the available space. if its less then go back and try a different route. then it wouldnt have to go through all possible steps inside a confined space which it came in through a bottleneck and cant get out to walk on other tiles.

I love your mini games you make on here. Have you considered doing one that makes a farm sim or rpg?

Add a 'heat' integer array keyed on [i, j] to increment each time it is visited persistent between path backtracks. All elements decrement heat each step Use heatmap colours to show increasing 'heat' with the path being randomly modified to a lower heat tolerance (delete back a random number of steps 1 to heat[i, j]) . Aiming for uniform heat/entropy.

each frame you could check if any of the unvisited spots are separated from the others. thats like avoiding to leave gaps in tetris :D

the easiest thing i could think of to speed it up a lot is to do a flood fill at it's current step. then add that flood fill count to it's current path length, if that is less then the total number of spots then you know 100% that it cannot reach all the spots in it's current path/location. you would then backtrack until the flood is bigger then it's last flood, picking another direction.

I'm not sure if this has been said, but you should try Ant Colony Optimization! I wrote a paper on that for one of my graduate course. Could send it to you to give a bare-bones idea of the procedure :) (though it may not be applicable to this problem... it is interesting in general for the Traveling Salesperson Problem)

great video!

It's something i tried myself everyday. Self-avoiding walk. ;)

Right off I'm think a set where the value is an array of length 2. The first position in the array being the row and the second position is the col is the best way to keep track of all of the locations.

Basically it is a dfs traversal on a grid but we choose the adjacent cells randomly.

Waiting for you to revisit this with the optimisations!!

this popped into my head while you began coding and somewhat unrelated but..could you make a video using a similar technique that takes an image and draws it line-by-line using a dot matrix like you've shown, expect only with black/white dots of varying alphas? I feel like I may have seen a video from you like this in the past, but it would be so cool to see it in action!

Great stuff

my first thought was a recursive solution where you gather all valid options, randomize the order and call the function on each. The exit would be when you have walked on rows*cols squares. You might run into a depth limit on very large grids, beware.

an easy optimization would be to check on every step if you are dividing your grid. if there is an area that is cut off completely from any other area, then it's impossible, trying to solve from that point forward is pointless. For example if you take your animation from 36:30, you can see that near the top left there is a pocket that can never be reached, while the algorithm is frantically trying to solve the rest of the space and revisiting that very early decision will occur only after the universe expired. you can use the flood fill algorithm on any empty space and see if it reaches all remaining free spaces. if it does not, a wrong decision has been made. Another easy to see abort condition is if the algorithm creates more than one non visited node with only one way in, because it will need to use that edge to enter that node and then has no way out, in effect forcing the walk to be ending there. Having two such nodes is an abort condition.

Your problem with the grid not being filled is with the random selection method. If it goes right, for example, and gets stuck it backtracks to the left, but right is once again a valid option. Therefore, it's possible to always choose right, get stuck, backtrack to the left, choose right, ad infinitum. You need to have a list of attempts from each point, so when it backtracks it can't try an attempted option again, so it backtracks further once all attempts from that point on the current path are taken, if it reverts and comes to that point again, it's on a new path, therefore all options are once again valid.

I wonder, between this and things like the pseudo Hilbert curve, is there a very easy to generate and reliable way to split the plane into two, with a path that is as long as possible?

Mind blown that random can take an array and return one of the elements @_@ - what a time to be alive!

this inspired me to make a similar program. I've coded it in c# to use the console. rather than backtracking, it resets after 100 unsucessful attempts to move. it's fascinating to watch it go.

I think I have got an idea on how to reduce the computation: After the program senses that there are no more moves that it can move, we could probably move 5 or greter steps back our path then use the random walking....

When your choosing which steps are valid check if flood fill can reach all other spots of the grid. A step should only be valid if a flood fill can reach every location of the grid. This will invalidate steps that block off a section of the grid. On second thought this flood fill is just checking if a spot bisects the remaining graph, so there might be better algorithms than flood fill for such a check.

I would love to see another challenge about custom shapes

Imagine if each cell could remember how often it's been backtracked to. If this number reaches a threshold value, then backtrack again to the previous node. This might eliminate continually returning to the same bad node. If the threshold were set correctly, you could avoid millions of searches inside node islands. This should be cheaper than checking for node islands directly.

Late to the party, but I think this one is a bit overly complex. For this, I would simply create a grid that holds (Enum) values. Like, 0 = empty, 1 = visited. The 'walker' is just a [row ,col] postion, no need for classes or anything. Then just operate on the world state (AKA grid of values). Back tracking might be done by simply going back on "visited valued" cells. If oscillation is an issue, you might to add a third value to the grid 2 = backtrackpath, At each cell simply do: check for empty cells, pick a random one and go there. Otherwise back track. That's all you'd need.

It looks like although its keeping track of whether a next move has been visited, I think it is still randomly creating paths of n length more than once.

Could you check say the surrounding 9 spots to see whether they have been visited, and prefer to head in the direction of the most visited spots? This might avoid traps early on in the path which would increase the number of paths that need to be tried

Another way to solve this problem is to use the wave front collapse function, and you can do this quite nicely for any generic graph. Say you are working with a grid with n dimensions and s_1, s_2, ..., s_n cells in each dimension. As you are moving between the cells of the graph instead of along vertices and edges, if you raise the size of each dimension by 1, then the problem turns into finding a Hamiltonian path on In the case of the slightly larger grid graph / lattice defined by: G = P_{s_1 + 1} □ P_{s_2 + 1} □ ... □ P_{s_n + 1} where P_n s the path graph on n vertices and G □ H is the Cartesian / box operator on graphs. When I was working on the wave front collapse, I made a problem where I used backtracking to find a partitioning of the space of G using wave front collapse. Once the space is partitioned, identifying the connected components is simple and connecting them is just as simple. This results in a Hamiltonian cycle for G, which is also a self-avoiding polygon, and by removing any edge at random, you get a self-avoiding walk. Of course, this limits the problem in some ways, i.e. one of s_n must be odd or it fails (since a Hamiltonian cycle only exists in G if one of the s_n + 1 is even), and it will only give you a specific type of self-avoiding walk (where you start and end one cell apart), but you could probably through some edge flipping get any self-avoiding walk, and the benefit of getting a self-avoiding polygon is a nice extra. In any case, it's just a fun way to connect two of the problems on this channel. I'm really enjoying the problems here and love your enthusiasm and sense of energy and fun. I love working on random problems to increase my GitHub portfolio and it's also a great way to pick a new language and learn it. (I tend to work in Kotlin most of the time as now that I've gone functional, I can't go back to imperative.) I usually watch about three or four minutes of one of your videos and then my brain spins out of control and tries to jump ahead to solve the problem before watching the rest of the video, which didn't quite work for my first attempt at wave front collapse.. I did the ASCII art today, which turned out really well, and I'm not convinced that the symbols given are the best for binning the shades of grey, so I'm working on a font analyzer where, given a font with fixed-width glyphs, the algorithm runs over the extended ASCII characters 32 to 255 and determines the percentage of the cell used by the character glyph, and then sorts them and for an integer b of bins that you want (which was 29 in the original problem), returns n-1 characters (since space is obviously the blank character) evenly spaced characters from the densest character to the least dense character to see if that generates a better gray binning colouration. (ChatGPT helped me write the Kotlin code using the java.awt package to do some of the lifting.) I found for that problem, using the luminance BT.709 gave the best results for combining RGB triples in [0,0xff]^3, which involves mapping the RGB triples to (r, g, b) ∈ [0,1]^3 and then combining them using: 0.2126 * r + 0.7152 * g + 0.0722 * b to get a grayscale value x ∈ [0,1]. It's quite amazing that blue is considered of so little importance.in this rendering and a pixel's green component is vastly more important than the other values. In any case, this channel has been a ton of fun and I think that I'm going to start learning Rust and working on the future problems in that. Thanks for your fantastic videos and all that you do!

So the easiest way to generate a random self avoiding walk is by creating just a simple walk and apply the "backbite" move a couple times. You should look into that!

Who knew Gilfoyl is such a chill dude

Love ur vids 💓💗💖

Amazing

30:47 Me instantly: yeah yeah, but get rid of that extra comma at line 14! xD

00:03 Exploring the concept of self-avoiding walk in a random walker. 01:58 Using 2D array to track visited spots 06:05 Addressing the infinite loop problem with a new approach. 08:29 Using higher order array function filter for processing options. 12:58 Exploring backtracking algorithm 14:39 Implementing a spot class for tracking options and locations 18:40 Updating the variable structure for the current spot 20:43 Finding valid options and moving to the next spot on the grid. 24:44 Implementing backtracking and self-avoiding walk algorithm 26:45 Need to clear visited spots and reset options to avoid getting stuck. 31:05 Coding Challenge 162: Self-Avoiding Walk - Debugging and Refactoring 33:07 Using multiple iterations per frame for faster experience 36:36 Exploring high resolution and further possibilities of self-avoiding walk algorithm. 00:00 The self-avoiding walk algorithm for random path generation

Nice 👍

discovered this two years late, but my thought for an optimisation would be to detect voids and backtrack the moment a void forms, either against the edge or against another part of the path. at that point you already know that the pattern is not solvable.

Why we create the backword point programming.. we can create random point and when it's stuck with any remaining point then it's should loop again until when it's not cover all the point on the canvas.. the it's can show "solved" message

on larger resolutions - when picking a random spot, isn't the probability higher for retracing an older route that is already tried?

you are checking if a spot has been already visited but i think it would be more right to see if a spot has been already visited from the same path. If from (x, y) I'm going up, left, down and get stuck at (x-1, y) and then I go back to (x, y) I should be able to go left to (x-1, y) even if I have already been in that spot previously, because now I could go up. Am I missing something?

When choosing the next spot, it will be invalid it there is more than 1 directions to go and the spot generates a path surrounding some non-visited spots. i.e. your path surrounds one-or-more non-visited spots then you must back-track.

Random Walker? Conan O’Brien had a lever for that. 🤩

Is there a space to include a Hamiltonian cycle into the spot calculations?

Why dont you do tutorials in processing anymore :(

It should backtrack way more when you can calculate that some spots will never be visited, like they're completely isolated 😊

How about walking to a specific point while filling the space? Can anyone provide me with some resource where I can get some information about it?

Path is a stack. You're already recursive :) You cleared tried every time you reset it, so it's not re-trying that direction; but then again, if it gets there another way, then the tried wouldn't be valid anyway. So you have to back up to where you have options left you haven't tried....

Hilber Curves. Not the same as walking/wandering, but I imagine that some sort of space-filling curve is needed here.

Everytime you backtrack theres a chance that the random direction it chooses will be chosen again so couldnt you store which options its tried in the cell class so it wont repeat its mistakes? should make it solve alot faster but im not 100 sure

I like your Videos, i am programming in a different language for plcs. To improve the solutions, Is it possible to avoid a false-area when finish the next step? In your last case, row 1 and 2 in column 2 are a false-area.

Just fill all spots with random neighbor connections, and link them until you have a single path?

whenever i listen to the song Shut Up and Drive by Rihanna, i always think Setup and Draw

ummm, can we all agree that watching Dan typing was wholesome. wondering why editor makes it fast forward. can we please have that back?

I mean by creating that path he basically just implemented a stack himself.. Might as well just have used some recurisve functions / recursive backtracking. That would just mean you have a function do_step that moves 1 step and calls do_step again. If stuck, do_step returns False and the callee can just try a different options and return False as well if all options are exhausted.

You've also created an algorithm to get the ultimate high score in that Snake game.

It could be faster if it could "solve" those unfillable holes. For instance by creating a small side loop in the middle of the existing curve that fills such a hole, or shifting a point on the curve if single enclosed points remain. That way, you could "squeeze away" all these problems.

I go on a lot of self avoiding walks too my dude, and I'm always stuck...

I dont think thats 64 factorial. its is like 4^64 because from every point you can choose (up to) 4 directions to go. but it is still pretty large. amazing video !!

An Optimisation Suggestion : i would say that for every iteration we if there is an inaccessible "spot" then go back one spot from the path and try a new direction!

could you do the scipts in C# please ? or just a few videos every now and again ?

Isn't this trying to find a hamiltonian path through the graph? CodeBullet covered this in his Snake AI video. Random walk seems like shooting oneself in the foot before a race.

At some point you should mention the hilbert curve though.