Unidirectional TSP Puzzles

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. 

2 thoughts on “Unidirectional TSP Puzzles”

  1. It just occurred to me that if you want to elanimite the bias (happening when there is more than one line with the minimal random value) by using the iterative process I described above, you can actually do that in one pass over the file.Instead of keeping 1 line and 1 number (the minimum so far) in memory, keep 1 line and an array of numbers in memory. The length of the array is the maximum number of iterations, it can also be an unbounded linked list. Don’t expect many iterations to be necessary, especially if RAND_MAX is big.So, when random() returns the same value as the minimal value so far, call random() twice again. Store the minimum of the two values in the second item of the array. If the first call returns the smallest of the two values, keep the old line. If the second call returns the smallest of the two values, keep the new one. If both are the same, call random() twice again, and store it in the third value of the array. And so on.For later lines, continue to compare the random() return value with the first item in the array first. When it is smaller, keep that line and drop all the further values in the array.

Leave a Reply

Your email address will not be published. Required fields are marked *