Coding Challenge 162: Self-Avoiding Walk

[@s-sugoi835]

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

[@chakradharcholleti6722]

Wow

[@Haapavuo]

Yeah. Imagine how many have built a successful career or business during your studies - just like this channel. I've been there too (M.Sc.Tech.). Wish you all the best with your ventures!

[@neillunavat]

Whats a freshman... U were, fresh? Fresh man? Just became man? Wow

[@chakradharcholleti6722]

@@neillunavat he's saying coding train released pt 1 in his first year and now releasing pt 2, when he was graduating

[@neillunavat]

@@chakradharcholleti6722 ohh... Yea i know first years and stuff... Lol wierd name tho..

[@davidoiltonante8875]

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

[@TheCodingTrain]

Better late than never!

[@stonedizzleful]

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!!

[@Wecoc1]

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

[@williamdowling7718]

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.

[@CaffeinatedTech]

Also, we can explain our problems and bugs to it.

[@cloyun-hee9564]

@@CaffeinatedTech I use my cat for that. She always seems so confused it's adorable

[@ЭнрикеЧурин]

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

[@mineball6078]

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

[@Plexversal]

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

[@jensBendig]

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.

[@simeon2396]

Yessssss finally another coding challenge 😀

[@DavidPHH]

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.

[@unoriginalpun]

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.

[@williamdowling7718]

function avoidRecursion(){ if (recursion.avoidable) { return true; } else { return avoidRecursion() ; } } avoidRecursion() ;

[@uchihasasuke7436]

@@williamdowling7718 had me until the end LOL

[@elijahbuchanan2368]

I will never get tired of these

[@thegiantguy]

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

[@nilsteichert8861]

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

[@JimSmith-u5g]

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

[@vorpal22]

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!

[@TheCodingTrain]

Thanks for this comprehensive feedback!

[@justavian]

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.

[@wootpile]

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

[@nzhook]

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.

[@r75shell]

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.

[@RolandKontson]

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.

[@zdeneksvaton25]

but how to find which edge it the blocking one. I think one possibility is to run BFS in the "island" and get all border edges. Then from this set identify last added in recursion tree.

[@sachinprabhuk6241]

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

[@FalcoGer]

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.

[@minijimi]

Good Job Dan! Very entertaining.

[@AB-Prince]

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.

[@icecrack4579]

Did you use some kind of library?

[@AB-Prince]

@@icecrack4579 do you mean for graphics? I used the built in terminal. it's done entirely using just the built in features

[@icecrack4579]

@@AB-Prince Yes, how did you get a visual representation? Also I know nothing about c#, so my question was a bit weird.

[@AB-Prince]

@@icecrack4579 the c# compiler comes with a text display, and i used the line graphic characters

[@powerdust015lastname4]

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

[@keineangabe8993]

That is a great suggestion, it would have skipped over everything it tried in the longest shown try in the first 10 frames.

[@korganrivera4659]

I wonder how expensive this check would be.

[@ahmedhassanahmedhassan6495]

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

[@m00t]

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.

[@sharadkumarsingh4802]

I lov coding challenge, hope episodes would be frequent

[@rocksfire4390]

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.

[@RupertBruce]

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.

[@sauliustb]

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.

[@WistrelChianti]

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

[@BinaryDash]

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.

[@wolframstahl1263]

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-

[@wolframstahl1263]

If you want to make it even more convoluted but probably more efficient, you can also keep track of which sections of the path have already been checked for air gaps.

[@ujjwalvinze4059]

Waiting for you to revisit this with the optimisations!!

[@pvic6959]

_four years later..._

[@SanderVermeer]

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.

[@tissuepaper9962]

By minimizing the code you're also minimizing its reusability. Good software doesn't look like a leetcode solution.

[@floydfix420]

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.

[@igotapochahontas]

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

[@DenisovichDev]

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

[@crazyfox55]

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.

[@TheCodingTrain]

Ohh, great suggestion thank you!!

[@kishoreytc]

Who knew Gilfoyl is such a chill dude

[@MrMelonMonkey]

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.

[@sayanghosh2883]

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

[@saelorasinanardiel8983]

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.

[@JoakimKanon]

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

[@kilianlindberg]

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

[@robwatson826]

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!

[@ionursan9291]

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

[@FlameStrykeShadowDark]

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.

[@lThePotatoCrew]

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.

[@kevnar]

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

[@hannokruger8145]

Sadly it won't work because the snake tail is moving, at a given position we can solve the best way to fill the grid but without taking into acount the extra space created by the snake tail moving forward. I dont think there exists an algorithm to play snake optimally, but there are methods that get pretty close

[@vibaj16]

Hanno Kruger actually it’s easy to get the perfect score in snake: just go through a loop that reaches every cell once. It’s similar to this, but it has to be a loop.

[@gamesvrtech6666]

Check out the snake AI example from CodeBullet 👍🏻

[@TheBloodyTalons]

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.

[@cezartorescu]

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

[@lucasmontec]

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.

[@ascrassin]

(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

[@dorbie]

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.

[@alessandrotassinari8140]

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?

[@richardstollar4291]

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.

[@elisaresmini7180]

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

[@adityaanand5768]

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

[@JoeX92]

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

[@korganrivera4659]

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.

[@TheFinagle]

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.

[@GodsAutobiography]

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

[@sirjmo]

A spiral is also valid here and hilber only works when starting in a corner.

[@ralphvercauteren9267]

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

[@RicoGalassi]

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!

[@chandlerzhu9735]

I would love to see another challenge about custom shapes

[@Tsharkeye]

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!

[@DJPrice-cc9lg]

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)

[@Hulkeq2]

At some point you should mention the hilbert curve though.

[@ayanavade3742]

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.

[@3zdayz]

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....

[@pvic6959]

i was surprised he didnt mention the stack data structure. I think it would be cool if there was an algorithmic part that checked if it was stuck in a "cave" while there are unvisited parts outside. Like you can see when he makes the resolution 5 at the end. It will check ALL the spots before exiting that cave and trying something else. this will speed it up since it can backtrack to all the way where it entered/made the cave and go from there

[@goo6]

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

[@denerribeiro8710]

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 !!

[@botsjeh]

You revisit points after backtracking and popping the points from the path.

[@stevenryall3186]

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

[@danjones9999]

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

[@nandukrishna8142]

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....

[@amitthakkar22288]

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

[@AlSavant]

Good catch! The less information about the past you keep track in such algorithms, the higher the probability is that you will return to the state that had you backtrack in the first place. In this video, he only keeps track of the previous state so it's inevitable that he will retrace an older path at some point. This is a very common problem in AI research when training neural networks. The less the network knows about the data surrounding it, the more probable it is that it will plateau in a sub-optimal training state. This is called a "local minimum". Here's some further reading on the theory behind this problem. Currently, no solutions exist. vitalflux.com/local-global-maxima-minima-explained-examples/

[@kutay8421]

@@AlSavant maybe an algorithm like : when stuck, stop, no backtracking. Instead try to find a spot near an unvisited one, call this one n, and try to find a sub-route that ends at n+1. This is like cutting a rope at nth position and make a little addition. This methodolgy may result in full exposure more efficiently. But I dont know. Did you get what I have in mind?

[@akshatverma5478]

Why dont you do tutorials in processing anymore :(

[@deathreus]

That 3D visualization is just the 3D Pipes Windows screensaver

[@rezaz7167]

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

[@danteUpbr]

great video!

[@andreasbrendel9160]

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.

[@landsgevaer]

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.

[@CourageousCoos]

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?

[@DJDoena]

Slight criticism on your naming strategies if I may: You say that allOptions, options and option are confusing and yet you let them stand. In the real world when you look at that code in a few months it will be a head-scratcher because you forgot your original intentions. Now you still remember that "options" are your current options to move right now, so at least call it currentOptions or optionsForCurrentMove. We don't live in the 1.44 MB diskette age anymore, variable names are allowed to be self-explanatory. Same is true for your isValid() function. Before that moment you talk about coordinates in a grid with x and y and that's perfectly understandable. And yet when you write that function you fall back to the generic and mean-nothing names i and j. Which you've also used when initializing the grid where you could have used x and y as well. That way all your references to the gird variable always use the same x and y coordinates which makes it much easier to understand for a future reader of that code. The compiler will always understand what you mean, it's the future human debugger we need to be more concerned with. I think the use of i as an indexing variable should be banned from all programming teaching books. It is a specific index for a specific array so it should have a proper name. You didn't call your grid g and your options o.

[@gimeron-db]

Wouldn't it be easier to use recursion? If we are stuck, then if all points are passed, then we will finish. Otherwise, we continue to search. But we can overflow the stack.

[@sidezerk9790]

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!

[@sirjmo]

It would slow it down but make it more efficient in less backtracking. Implementation pseudocode: every new spot checks if it splits its neighbors in two, if so... Reverse As for how you'd check that... Figure it out

[@Fiercesoulking]

if we say this is snake I solved it a long time ago not efficiently but if you want to use all space it is possible.

[@ethanlynch3639]

there's a cool trick for deepcopying an array containing objects. if you do let newArray = JSON.parse(JSON.stringify(oldArray)); so far this is the easiest way to do this that I've found

[@TheCodingTrain]

Thanks for this tip!!

[@cenkakay3506]

Yes, but it's not work always. If u want to copy array that contains object. I mean object array. U should use map function. If u use parse probably class functions will not work.

[@ethanlynch3639]

@@cenkakay3506 ah i didnt think about that. ive only used it for objects that are essentially hashtables (not sure if thats what they are behind the scenes but anyway) without any methods. also map has issues if you use it on arrays containing objects containing arrays (containing objects) without some sort of recursive function to pass in

[@cenkakay3506]

@@ethanlynch3639 Maybe we can try map inside map or just use a another node package :D

[@memespdf]

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.

[@mickyr171]

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

[@random_precision_software]

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

[@rainbowskeppy5292]

Next coding challenge: { Snake AI, Trying python/lua, Marching cubes }

[@proloycodes]

or Rust/C/C++

[@CodeChallengee]

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

[@CTimmerman]

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

[@Leftysrev3nge]

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

[@junuhunuproductions]

Love ur vids 💓💗💖