Peg Solitaire is the 15th MATLAB Online Programming Contest.
Naturally our version is a little more complicated. In this contest, your goal is to jump pegs in such a way that you make your score as low as possible. This may not mean removing all the pegs.
Here's how it works. Each peg has a value, or weight. A move consists of one peg jumping over and thereby removing another peg. A "jump" is a horizontal or vertical move in which one peg passes over exactly one other peg and comes to rest on an empty space. Diagonal jumps are not permitted. You are rewarded for every peg that you remove from the board according to its weight, BUT you pay for each jump according to the weight of the jumping peg. Thus you want to harvest the high value pegs by jumping over them with low value pegs. The bigger the difference between the value of the two pegs, the better your score. If, however, you jump over a low value peg with a high value peg, the situation is reversed: your score will get worse.
In the picture above, a peg with weight 1 jumps over a peg with weight 3. The reward is 3, but the penalty is 1, so the total value of the move is 2. If you can arrange to make several jumps in a row using the same peg, however, you only have to pay the penalty once.
Here are the details.
The initial score for this board is 31, or the sum of all the weights on the board. The removal bonus for this move is 8, but we have to pay a lifting penalty of 2, so the value of the move is (8 - 2) or 6 points. The score after this move is 31 - 6 = 25 points.
In move 2 there is no lifting penalty because we are still using the same peg. The score after this move is 25 - 7 = 18 points.
At this point there is no jump that will improve the score. We could jump the 4 peg over the 3 peg, but this would only make our result worse, since the lifting penalty would be worse than the removal bonus. Final score for this game: 31 - 6 - 7 = 18 points.
Here is an alternative, and slightly better, series of moves. Starting from the same initial configuration as shown above, the 4 peg can be used to jump the 3, 7, and 8 pegs in succession. Despite the fact that the first jump is disadvantageous, the overall result is better. Final score: 31 - 14 = 17 points.
These three factors are passed to our scoring algorithm to produce a final score, according to the equation
score = k1*result + k2*e(k3*runtime) + k4*max(complexity-10,0)
All three of these are to be minimized and the lowest overall score at the end of the contest wins. We don't publish the values k1-k4, but they aren't hard to figure out.
Your entry will time out and be disqualified if it takes more than 180 seconds (three minutes).
Since a file can contain multiple functions, the complexity for any given file is defined as the MAXIMUM complexity of any functions contained in it. A good practice is to keep the complexity for each function below 10, so for this contest your overall score will increase according to the complexity in excess of 10. So there is no complexity penalty for submissions in which all functions have a complexity of 10 or less.
You can measure the cyclomatic (or McCabe) complexity of any function in MATLAB using the "cyc" switch for mlint. Try this, for example:
>> mlint -cyc magic.mWe have also included a getComplexity.m function with the contest distribution to make it easier to find the complexity for your entry.
moves = solver(board)The solution is a four column matrix in which the moves are reported as rows. This matrix can have any number of rows between 0 and (numpegs-1). Every move is a four-element row vector with the format [from_row from_column to_row to_column].
Keep in mind that these functions must have the right signature. Variable names are unimportant. To test this function with the test suite in the ZIP-file, run runcontest.m.
We also encourage you to discuss your solutions and strategies with others. You can do this by posting to the thread that we've started from our newsreader.
Because of the realities of modern computing, running the same code twice will result in different timings. If a winning entry is functionally identical to an existing entry, the submitter of the original will be named the winner.
The following are prohibited:
Entries that compromise the contest machinery are no longer allowed. We've all learned some interesting MATLAB tricks in the past by contestants figuring out how to pass information from one entry to the next, or finding clever ways to execute disallowed functions, but it's too hard for the few of us running the contest to keep ahead of the group intelligence. Until we can find a more secure system, we're running up the white flag. In short, no Welching, please.
Extraction of puzzles in the test suite by manipulating the score, runtime, or error conditions is also forbidden. In the small scale, this has been an element of many past contests, but in the Blockbuster Contest, Alan Chalker turned this into a science. Tuning the entry to the contest test suite via tweak bombing or other techniques is still allowed, but we ask that you not overwhelm the queue.
Contests are divided into segments where some or all of the scores and code may be hidden for some users. Here are the segments for this contest: