Odd Even Path Puzzle Solver

[Cervantes]

In the attachment are four files (two normal files, two module units). If you want to play OE Path, run "OE Path Play.t". If you want to (sort of) solve a puzzle, run "OE Path Solve.t".

The puzzle works like this: You pick a place on the grid to start at, then move from piece to piece in a path trying to get the highest score possible. You can only move immediately above, below, right, or left of you. No diagonal moves are allowed. If you start on an even number, you can only travel on pieces that have even numbers. Similarly, if you start on an odd number you can only travel on pieces that host an odd number.


This puzzle is more interesting to solve. I haven't quite done it, actually. So far I've made it so that the user picks the starting location. From there, the program will find the best possible path.

To improve this, I'm currently thinking that the user should pick a point on the path that (s)he thinks will be the best in the level. Then the program would search out the best and second best paths with the piece that was picked by the user as the starting position. The two paths would then be joined. Note that something would have to be done to prevent the best and second best paths from overlapping.

Next, the user shouldn't have to pick where to start. The program should automatically scan the level and find the place to start the search at. This would be the most difficult part of the program, I think. My ideas for this are limited to grouping the grid into compartments of odd and even patches. Then, a spot in the compartment with the largest total score would be chosen and the searching begins. This would not, however, take into account the fact that not all pieces in a compartment can be reached (ie. sometimes getting a piece means travelling into a dead end. These pieces shouldn't be included in the compartment).

This idea of compartments could also be used to speed up the current program. Now when I say a compartment, however, I mean a section of the same type (odd or even) that does not go into a bottleneck. Often times in this game you'll go from one large, open section of, say, evens, through a narrow path, into another wider area. Instead of searching every possible pattern, we should find the best path through the first open area (what I referred to as a compartment at the beginning of this paragraph) that will lead to the bottleneck. Then we take the bottleneck to the second compartment and finish it.

Lastly, I'm aware of some bugs, such as you cannot exit the program. Pff, that's not a primary concern! Just click the 'x'. Also, the solver doesn't tell you the current score. Easily fixed, though I don't want to re-zip it.

Anyone have any suggestions as to how to further develop this program, or how to optimize the current program?
Thanks!

[zylum]

again plain recursion with a slight optimization... i loop through each square of the grid and start my path there.. once the path is finished then each consecutive path cannot travel on the first space of any preceding path. this makes my algorithm speed up as it progresses.

code:

setscreen ("offscreenonly,graphics:500;500,nobuttonbar") const N := 12 const gridSize := maxx div (N + 2) var grid : array 1 .. N, 1 .. N of int var travelled : array 0 .. N + 1, 0 .. N + 1 of boolean var font : int := Font.New ("Arial:14") var score : int := 0 type Coords :     record         x : int         y : int     end record var path : flexible array 1 .. 0 of Coords var bestPath : flexible array 1 .. 0 of Coords var bestScore : int := 0 proc drawGrid     locate (1, 1)     put "Best Score: ", bestScore, " Current Score: ", score, " Elapsed Time: ", Time.Elapsed / 1000     for x : 1 .. N         for y : 1 .. N             Draw.FillBox (x * gridSize, y * gridSize, x * gridSize + gridSize, y * gridSize + gridSize, grey)             Draw.Box (x * gridSize, y * gridSize, x * gridSize + gridSize, y * gridSize + gridSize, black)             Draw.Text (intstr (grid (x, y)), x * gridSize + gridSize div 2 - Font.Width (intstr (grid (x, y)), font) div 2,                 y * gridSize + gridSize div 2 - gridSize div 5, font, (grid (x, y) mod 2) * black)         end for     end for     if upper (bestPath) > 1 then         for i : 2 .. upper (bestPath)             Draw.ThickLine (bestPath (i - 1).x * gridSize + gridSize div 2, bestPath (i - 1).y * gridSize + gridSize div 2,                 bestPath (i).x * gridSize + gridSize div 2, bestPath (i).y * gridSize + gridSize div 2, 5, green)         end for     end if     if upper (path) > 1 then         for i : 2 .. upper (path)             Draw.ThickLine (path (i - 1).x * gridSize + gridSize div 2, path (i - 1).y * gridSize + gridSize div 2,                 path (i).x * gridSize + gridSize div 2, path (i).y * gridSize + gridSize div 2, 2, brightred)         end for     end if     View.Update end drawGrid proc fillGrid     for x : 0 .. N + 1         for y : 0 .. N + 1             if x > 0 and x <= N and y > 0 and y <= N then                 grid (x, y) := Rand.Int (1, 10)                 travelled (x, y) := false             else                 travelled (x, y) := true             end if         end for     end for end fillGrid proc travel (x, y, cs, oe : int)     if travelled (x, y) or grid (x, y) mod 2 ~= oe then         if cs > bestScore then             bestScore := cs             new bestPath, upper (path)             for i : 1 .. upper (path)                 bestPath (i).x := path (i).x                 bestPath (i).y := path (i).y             end for         end if         return     end if     new path, upper (path) + 1     path (upper (path)).x := x     path (upper (path)).y := y     %/* <- remove this '%' to comment out drawing     score := cs     drawGrid     %*/     travelled (x, y) := true     travel (x + 1, y, cs + grid (x, y), oe)     travel (x - 1, y, cs + grid (x, y), oe)     travel (x, y + 1, cs + grid (x, y), oe)     travel (x, y - 1, cs + grid (x, y), oe)     new path, upper (path) - 1     travelled (x, y) := false end travel proc Solve     for x : 1 .. N         for y : 1 .. N             new path, 0             travel (x, y, 0, grid (x, y) mod 2)             %travelled (x, y) := true <- THIS IS THE PROBLEM LINE!!! should work now         end for     end for end Solve fillGrid Solve drawGrid

[Cervantes]

A good thought zylum. But, sadly, it's wrong. This is most clearly illuminated with an example. Try using a 6x6 grid and set the value of the grid to be x * y, like this:

code:

grid (x, y) := x * y %Rand.Int (1, 10)

It takes my computer a little over seven and a half seconds to find the "best" solution, with a score of 300. But this is not the best solution. A better solution looks like this:

I'm a little unsure how your travelled grid works, but I know it is the problem. Here's my first guess: the real best path (score 312) starts on the number 18. It then moves down, then left, then up again. Your code will prevent a path from moving down and left, because by your two for loops, the searching sweeps columns from their base to their top and from left to right.
Then I added this code inside the drawing part:

code:

for ix : 0 .. upper (travelled, 1)         for iy : 0 .. upper (travelled, 2)             if travelled (ix, iy) then                 put "t " ..             else                 put "f " ..             end if         end for         put ""     end for

This told me some strange things. It seems that the travelled array is much different than I imagined...

Anyways, I took your idea and modified it a bit. I said that you should not be able to start a search inside the best path, because that would just be truncating the best path and clearly not what we want. Then I further developed this to create an array of best paths. We don't know which is the real best path until we finish. The array records the best path for each starting point. This seems to work better, as the program runs much faster, but the code I've got here is still not correct. It works for the 6x6 set grid, but when I expand it to 8x8 it fails. Here is the output it produces on the 8x8 grid:

For one, it shouldn't start at the four but rather it should start at the twelve. It seems as though it's still prevented from travelling on a best path, though it should only be prevented from starting on a best path. The real solution looks like this:

I'm not sure why my program fails at this. I think one of the arrays of Coords is messed up. This could be currentPath, or it could be one of the bestPaths. Actually, I know the bestPaths are messed up, because I'm sometimes getting the lengthBestPath function telling me the path is 160 or more pieces long, and this is on a 13x13 grid. It crashed after that (it exceeded 169 [13x13] the max I have it set to be [since I can't use flexible arrays within records]). Though this crash was not in the same program. This crash occured when I tried to tweak the program for more optimization.
What I tried doing this time (in addition to the previous tweak) was make it so that any time a path entered onto one of the best paths, they would coalesce to form a new best path. I placed a restriction so that the current path could not overlap the second position of the best path (right after the starting spot). Though now that I think of it, I didn't check any other parts, which I suppose I should have. But that should not make the program crash...

Attached are two source code files. "Cervantes OE Path Solver.t" does not have this final tweak and is the one I used on the 6x6 grid, and the one that produced the bad output on the 8x8 grid. "Cervantes OE Path Solver work on adding to best path.t" is the one that does include this final tweak, and is the one that crashes. (You may need to run it a few times to generate a situation where it will try to coalesce.)

[zylum]

bah youre right... i was thinking about it last night and i realised that not allowing the path to go on previous starting points would not work. that was just an improvement i was trying to make but as you can see doesnt work. a simple example of a failing case would be one where the start is the top right corner and the finish is the bottom right and the path goes around the border of the grid... with my algorithm, the path would not be allowed to go any further left than the right most column since all the spaces to the left of that had already been starting points... to fix this problem i sipmly removed the line where it permanently lables that square as travelled. it should work now although i did not test it... also since its pure recursion with no optimizations, it wil run SLOW...