June 20, 2018 TCO18 Marathon Round 2: An Analysis

A task CrystalLighting was used in the second round of TCO18 Marathon Match selection. It was written by Nickolas and tested by t-mac and Round 1 winner wleite, who already qualified to the finals. The task allowed a variety of approaches, but Simulated Annealing technique proved to be the best again. The match was won by nika, with eldidou and hakomo rounding the top-3. There are only minor changes in the final standings, compared to the provisional.

Color Mix

The scoring method of the task implies that for some input data it is more profitable to lit the crystals of secondary colors as good as possible, while when the cost of a lantern is high, it is better to concentrate on lighting the primary-colored crystals.
This idea could guide us somewhere, but not to the best solutions found during the match.
It turns out that instead of concentrating on exploring different approaches this time it was more profitable to optimize the elementary operations of the Simulated Annealing, in an effort to run as many loop iterations of this metaheuristic, as possible.

Basic Steps

As usual with the Simulated Annealing, the simpler and faster the basic steps you use in it, the better. The reason for this is that a million of dumb but fast operations yields a better combination than single slow but clever operation.
The very elementary steps to start with could be:

• Add a lantern, a mirror, or an obstacle into a cell.
• Clear the cell.

These operations can be implemented efficiently, run in O(1) time, and give good results, once your cooling schedule is correct.

Constant-Time Modification

The simplest possible way of maintaining the board state in the Simulated Annealing routine is to store a character per cell – the object currently placed into that cell, or dot for empty cell, plus 3 numbers in range 0..4 answering the question “from how many sides a crystal is lighten by a color X?”, where X is 1, 2, or 4. The later is needed in order to simplify (or make more complex – depending on what we are going to achieve) the process of maintaining the correct current score each of the crystals yields on-line. The current color a crystal is emitting can be calculated as follows then:

Let result = 0
If SidesLightenByBlueLanterns > 0
	Result += 1
If SidesLightenByYellowLanterns > 0
	Result += 2
If SidesLightenByRedLanterns > 0
	Result += 4

Note that we ignore the actual amount of sides lighten by lanterns of each of the 3 main colors, we are interested only if there is at least one lantern of that color that lightens the crystal. So, we add 1 for any positive amount of blue lanterns lighting the crystal (be it 1, 2, 3, or 4 blue lanterns lighting it from different sides). I will provide an image to make the idea more clear:

Here, the result for the blue crystal is still 1, but the SidesLightenByBlueLanterns is equal to 3.
The question “why cannot we just store a boolean for each primary color?” is valid, but to answer it we need to investigate the updating of the data structure mentioned first.

Maintaining The State

I would like to introduce several main internal operations:

• Validate a placement of a lantern into a cell.
• Validate a placement of a mirror into a cell.
• Validate a removal of a mirror from a cell.
• Validate a removal of an obstacle from a cell.
• Place an object into an empty cell.
• Change a lantern of color X to a lantern of a color Y.
• Clear a cell with an object, making it empty.

Additionally, we need an extra efficient way of determining the cell we will arrive if we go in a certain direction from some starting cell. A natural way to solve this subtask is to maintain an array answering exactly this question. We will need an extra array answering a similar question, but if we can stop not only at the borders, crystals, lanterns, and obstacles, but also at the mirrors.

It is clear that the query will be instant now. What about the update? Now we will use a well-known property of the Simulated Annealing saying that the update is much less frequent operation, and thus can be a little heavier than query. Thus, amortized cost of the update is still small enough.

Other Metaheuristics

The alternative solutions are possible. I used Tabu Search as the main metaheuristic, JacoCronje described in the post-match forum discussion his greedy lighting of crystals plus reordering the sequence the crystals are lighten. It can give results that are comparable with the Simulated Annealing described above.