Trying to get a grip on recursion and linked structures

My quest to solve the Colossal Cue Aventure’s third puzzle is taking me to the edge of my knowledge.

The puzzle is basically all about finding a path through a set of rooms. I’m writing a test program to see if I can programmatically traverse all potential paths through this array. I  start at 0,0 and then see where I can go from there: North, East, South, or West. I check first if it’s possible (within the bounds of the array) and second I check if I’ve been there before (which I’m currently doing all wrong…. but I’m working on that).

I think I know all the reasons why it’s not working, BUT I’m not sure how much I should cheat with extra data structures storing things like where I’ve already been. I feel like the “correct” way would be to make the primary walking routine take care of itself but I’m struggling to figure it out.

Anyways, warts and all here’s what I have so far. It does a lot of unexpected things, and the way I’m checking to see if I’ve been in a location is completely wrong. Oh, and I’m not freeing any allocated memory. And it runs until a stack overflow happens.

I’m pushing my knowledge of recursion and (what I assume are) graph data structures. I think it’s a graph I’m making. The vertices are the array locations, and the edges are pointers to the locations around it(?). Maybe I’m just making a quadruply linked list and graphs are something else.

Ok, so I’ll swallow my pride and make an array of already visited locations in the array. I can also make an array of all the created node addresses so that I can free them.

This entry was posted in Programming. Bookmark the permalink.

One Response to Trying to get a grip on recursion and linked structures

  1. sebrenauld says:

    You’re indeed making a graph, and an algorithm like Djikstra is usable. A* is NOT usable,as you’ll notice if you use it – it will not find a path. The reason for this is because the only solution requires you to backtrack.

    The way I went about on this was functional programming. On every step, branch the program into four possible states, keeping their internal state current. Every time a path runs out of chips, call back to the main thread going “hey, I’m here!”. If it’s on (X,Y), bingo. This also keeps the moves for every path so I can verify (and input) the solution.
    Code is available if you want to see it, though I wrote it in PHP, not python. Source: https://gist.github.com/srenauld/a081c157563415494fdb . As you can guess from the current run, there’s a second path in the bonus stage – 11×11 grid, variable map, 444 tokens. If you’d like to run the old one, use TrollMap rather than TrollMap2 and the old triggers.

    Memory clears itself as it goes, too!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s