Sane

I coded Dijkstra's Algorithm purely in Excel today! No Macros or Visual Basic either.

I did this in Data Management class out of boredom.

There is a maze that you can change by replacing the cells with 1 or nothing, and moving around "Start" and "Exit". It will calculate the shortest path to the exit by running Dijkstra's Algorithm on 7 worksheets, and displaying the path back on the original worksheet. Even though the edges are of uniform weight, I decided not to use a BFS because I figured implementing a priority queue in Excel is easier than a normal queue.

The maze is limited to 6x6 because this was just a couple hours of work. Didn't want to get too out of hand by making it dynamic.

I've zipped and attached the complete .xls file if anyone's interested. To delete a wall, click the block and hit "Delete". To add a wall, click an empty square and type "1" then "Enter". To change the Start and Exit, it should be obvious what to do. Remember it's limited to 6x6.

Below is a screenshot of it in action on two separate mazes:

Attached Files

Dijkstras_Algorithm.zip (106.5 KB, 8 views)

__________________
Waterloo's Canadian Computing Competition (CCC) - Stage 2 Problems, Solutions, and Test Data

OpenLoop

Impressive. How long did it take you to make this?

Excel can come in handy in day to day work. The actuarial department where I work uses Excel to calculate thousands of values for insurance policies. Each spreadsheet is about 30mb worth of formulas, binary solves, and a few macros to calculate the monthly premiums, cash value, interest, fees, and many other values over the life of a policy (~90 years). Luckily, I only have to look at the values and match them to the real thing on the admin system to fix values issues.

Sane

It took me an hour during school and about an hour more when I got home.

__________________
Waterloo's Canadian Computing Competition (CCC) - Stage 2 Problems, Solutions, and Test Data

Sane

I found that 6x6 is too small, so I extended it to handle 12x12 and it still works lightning fast (thanks to Dijkstra).

Unfortunately, the .xls file is 11MB so I can't attach it to this post.

But here's a screen shot for what it's worth:

__________________
Waterloo's Canadian Computing Competition (CCC) - Stage 2 Problems, Solutions, and Test Data

BstrucT

Very impressive!

Never knew one could program in Excel :-)

>BstrucT

__________________
The more the human race tries to change everything, when not needed, the less will they be able to change themselves when they need to.

Wizard1988

Awesome job Sane. Suprisingly Excel can be used for a bunch of stuff. For example you can have it render 3D objects http://www.gamasutra.com/view/featur...ionary_3d_.php I'm not sure how usefully doing something like this is, but it might be effective against boredom.

__________________
JG-Webdesign

iEngage

impressive!

I may try to recreate that from scratch next time I'm bored in class

__________________
iEngage

Sane

I've managed to zip and attach the 12x12.

Here's one more screenshot if you're interested to see what the tables look like.

It's simply 1 row for each iteration of the algorithm. Each iteration fills in the current state of all of the variables in 1 array. Likewise, there is 1 worksheet for each array.



And another maze for kicks:

Attached Files

Dijkstras_Algorithm_Bigger.zip (1.47 MB, 3 views)

__________________
Waterloo's Canadian Computing Competition (CCC) - Stage 2 Problems, Solutions, and Test Data

MiKuS

yeah thats pretty cool sane, should be interesting to see if this will work in Numbers