Programming Archives
There is now a talk forum for these problems, located here.This is a record of some of the more challenging problems I've come across in my years of programming, along with thought processes for solutions and sample codes. All things presented here are given "as is" with no support from me. Basically, its just algorithms and I don't want to do any tech support for algorithms.
If you don't know java and would like to learn, I would recommend using Sun's Java tutorials. I usually use JCreator with JDK Version 1.5 to do my development, but whatever works for you is the best for you to use.
Spiral Matrix (This is actually a fun exercize in finding more than one solution to a problem. You can do this in multiple ways and I'll leave you to find them.)
A Spiral Matrix is a lovely little two-dimensional array consisting of the numbers 1 to the size of the array squared arranged in a pattern such that the numbers increase while spiraling into the center (hence then name). A spiral matrix with a size of 3 starting from the lower left corner is shown below.
3 4 5
2 9 6
1 8 7
Basically, you know where you're starting and which direction you're spiraling to start with. You go in your starting direction filling in numbers until you hit the edge, make a turn, then continue until you hit another edge, make a turn, etc. The only catch is, places already filled in count as edges for deciding where to turn.
Variations on this that you could try include spiraling from low to high, a left spiral instead of a right spiral, spiraling outward instead of inward, spiraling words, or whatever else you want. Try to make your output look pretty using Syatem.out.printf(), its more artistically pleasing and its a good skill to have.
Mazes
This is a big step up from the spiral matrix in that it uses recursion, but its a pretty basic recursive algorithm, so I thought it would be worth mentioning here before we go into more advanced recursion.
The basic idea behind a maze is "pass the buck". Consider the following maze:
S.....
###.##
....##
.#####
......
#E##..
Where 'S' represents the starting position, 'E' represents the ending position desired, '#' represents a space not able to be moved into, and '.' represents a space that can be moved into. For any place that you visit, you check to see if you can move there first. If you can't, theres no reason to try to go down that branch. If you can, check to see if you've been to that position before in that branch. If you have, you're getting caught in an infinite loop and you dont want to do that. If you can move to the position and you haven't been there, you check to see what is in the cell. If it's your starting position or an open cell, you need to keep going and try to go to the places around you, usually only up, down, left and right. If you're on the ending position, you're done. simple, right? you just start this recursive checking on your starting position and you'll find that yes, there is a path to the exit.
Note: This approach is very inefficient, it goes down a lot of unneeded branches in some cases and this could lead to problems in corner cases (ie. a 100 by 100 completely clear maze), so some optimization is needed on these cases. One way to do it is called "pruning", cutting off recursive branches once there is some way of knowing that there is no good to come of following that branch. For example, if you're trying to find the shortest path to the exit, you could keep a record on each location of what the shortest path to that location was. If on any branch you get to that location in more moves than the shortest path to that node, you can stop that branch because you know every path after that will be greater than the shortest path to the other locations, because you've already recursed off that node in more efficient path. I call this "shadowing" the maze because the data sort of sits behind the actual maze creating a shadow copy of the path's movements.
An example of a maze solver with shadowing and a nice data file for demonstrations can be found here.
Expression Solver
The basic idea behind this problem is to take an mathematic infix expression and solve it for a value. This is difficult because unlike humans, computers are not very good at looking at and solving a problem in its entirety. Computers like problems to be broken down into discrete steps without any ambiguity. They can't quite see substitutions or order of operations the way humans can. But, if you can get the data into a form the computer can consider, say like individual elements (numbers, operators, and subexpressions), then there is a way of processing this data that a computer can understand.
Let's start out with an example:
(6+5)*9+4/8*2^2
ok, lets put it into a list that the computer can store and interpret. 6 and 5 are integer values, and the operand is a character, and every subexpression is really just another list like with integers and character and subexpressions, so we can create a list with all of this in it
{ { 6 , '+', 5} , '*', 9 , '+' , 4 , '/ , 8 , '*' , 2 , '^', 2 }
Fantastic. Now we can loop through and apply order of operations
First, find all subexpressions, evaluate them, and replace them with their value
{ 11 , '*', 9 , '+' , 4 , '/ , 8 , '*' , 2 , '^', 2 }
Then, loop through, find all power operators and replace the 3 elements in the list involved
with that operation with the value of the operation (ie 2, '^', 2 turns into 4)
{ 11 , '*', 9 , '+' , 4 , '/ , 8 , '*' , 4 }
Do the same looping process for multiply and divide all at once
{ 99 , '+' , 4 , '/ , 8 , '*' , 4 }
{ 99 , '+' , 2 , '*' , 4 }
{ 99 , '+' , 8 }
Do the same looping process for add and subtract all at once
{107}
At the end, you have a list with one element: the solution, 108.
It's really a logical progression of solving. Note that getting the expression into the processing list involves making sublists and the solving of the processing list involves processing sublists. Yes, this is recursion.
Code and example data files can be found here.