Coding Challenge 162: Self-Avoiding Walk

Links discussed in this video:

Other videos mentioned in this video:

Timestamps:
0:00 Choo choo! Welcome!
1:05 Explain! How can we go about this?
2:29 Code! Let's add a visited grid.
6:25 Code! What are the options for movement now?
10:34 Code! Let's check the edges.
12:34 I could stop here but wait.
13:30 Explain! How can we think about backtracking?
15:15 Code! Let's make a spot class and a path variable.
24:23 Code! Now backtracking!
29:38 Whoops! Copying allOptions was a mistake.
31:19 Code! Maybe we need an end condition.
32:09 Yay! It worked.
32:22 This could take awhile. Could it be improved?

[s-sugoi]

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

[davidoiltonante]

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

[williamdowling]

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.

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

[Wecoc]

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

[rrhclsn]

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

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

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

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

[mineball]

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

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

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

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

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

[rshell]

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.

[nilsteichert]

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

[crazyfox]

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.

[powerdustlastname]

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

[WistrelChianti]

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

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