Editorial for ECOO '12 R3 P2 - Jewelry Tips
Submitting an official solution before solving the problem yourself is a bannable offence.
Recommended Approach
The best way to solve this is just a top to bottom, left to right sweep of the entire board. For each jewel, simulate swaps in all 4 directions (in order of priority – LT, UP, RT, DN) and check for lines, then undo the swap and continue. Keep track of the first "good" and "excellent" tips found, but quit immediately if you find a "normal" tip and return that. If you get to the end of the board without any normal tips, return the good tip you found, or the excellent tip if there was no good tip, or Game Over if no tips of any kind were found.
I found it helpful to create a special counting method (a.k.a. procedure or function) that takes the board and a location as parameters, then counts the jewels of the same colour vertically and horizontally in both directions. If there is only one line , it returns the length of it. If there are two, it adds their lengths and returns that. If there are none, it returns
. So
means no line,
or
means a single line, and
or more means either more than one line or a line of five.
Some Further Notes
When you swap two jewels, you have to check that the other jewel in the swap doesn't end up creating lines as well. If it does, you've got an excellent tip, so you shouldn't return it as a normal tip.
There are not many situations in which you would return a good tip, since when you one jewel to create a line of , there is always another jewel you could move to make a line of
instead. It is only when this move creates multiple lines (making it excellent rather than normal) that you can return a good tip.
The Test Cases
The test cases were generated automatically by randomly generating thousands of boards. The boards were thrown away if they already contained a line of or more. If not, they were checked using the jewelry tip routine written above to see what kind of tips they contained and kept if they met the criteria I was looking for.
I went with 10 cases because there are so many different kinds of errors you can make in programming this. I thought that the more test cases there were, the more errors I would shake out of the code being tested. But because rule 5 was added at the last minute to cover an ambiguity in the rules, none of the test cases required the use of that rule.
Comments