As we’ve entered the late spring into early summer season, I’ve found myself wanting to go out more to sit and enjoy the weather. One of these days recently I sat in the park with a good book. On this occurrence, I decided not to go with a novel as I had just finished “Incarceron“, “The Archer’s Tale“, and “14 Stones” – all of which were good reads, but I felt like taking a break from the novels.

Just as a side note, 14 Stones is a free book available on smashwords.com and I’ve now read about 6 books from smashwords.com and haven’t been disappointed yet. My favorite is still probably “The Hero’s Chamber” because of the imagery of the book, but there are some well written ebooks available there by some good up and coming writers for a reasonable price, with some being free.

So with the desire to read, but not being in the mood for novels I decided to pick up one of my non-text but still educational books that make me think. This day it was “Programming Challenges“. I browsed through the book until I found one that I could lay back, look at the water, and think about how to solve it.

The programming puzzle the peaked my interest was called “Unidirectional TSP”. We are given a grid with m rows and n columns, with each cell showing the cost of using that cell. The user is allowed to begin in any cell in the first column and is asked to reach any cell in the last column using some minimum cost path. There is an additional constraint that once a cell is selected in a column, a cell in the next column can only be chosen from the row directly above, the same row, or the row directly below. There is a javascript version of this puzzle available here.

Fundamentally, the problem is asking for a path of shortest length. Many shortest length problems have a greedy structure, but this one gained my interest because the greedy solution is not always optimal in this case. So I took a moment to figure out the strategy behind these problems. Once I had that solution, I decided that it would be a good program to write up as a puzzle.

In this puzzle version, users will click the cells they wish to travel in each column in which case they will turn green (clicking again will turn them white again). Once the user clicks on a cell in the last column, they will be notified of whether or not they have chosen the minimum path. Or if users are unable to solve a puzzle, the “Solution” button can be pressed to show the optimal path and its cost.