Not the Chemistry I Remember

Despite the brilliance of Portal 2, I did feel let down by the lack of really difficult puzzles and challenge levels (quickest time/fewest portals). Scouring other thoughts on the matter led me to indie puzzle game SpaceChem. I was promised really difficult puzzles and competition for fastest time/fewest symbols used for each level.

Although the theme of the game is chemistry, reactors where you can manipulate atoms directly indicate that this isn't meant to be a realistic portrayal of the subject. The basic premise is that you need to take molecules (or atoms or radicals) coming into a reactor and convert them into the required molecules (or atoms or radicals). The example below shows a reactor I built to convert a methane molecule (CH₄) into the required CH radical and hydrogen (H) atoms.

Disassembling methane

To accomplish this, you have two waldos, atom-sized "robots" that will follow the track laid down for them and process the instructions in the square they're currently in. The instructions include grab (to pick up an atom), drop (to put down an atom), in (to bring a new molecule into the input area) and out (to flush a molecule out of the output area).

In the example above you can see the red waldo has just dropped off a hydrogen atom and is about to flush it with the out instruction. Meanwhile the blue waldo is rotating a CH radical that it will drop in the upper output area in the next cycle (waldos move 1 square per cycle, the SpaceChem unit of time).

So far I've only played one difficult level and that was optional. I expect there are more challenging levels ahead, but in the meanwhile I'm having great fun trying to optimize my solutions to be among the best for each puzzle.

SpaceChem histograms

As an example of an early level and the optimization I did, I present my solutions for Sernimir IV's Best Left Unanswered. The level comes just as you've learned how to bond atoms together: running the bond+ instruction will cause all atoms on the special bonding tiles to add one bond to each neighbouring atom also on a bonding tile. In this level you have to make a triple bond between a pair of nitrogen (N) atoms to form a nitrogen molecule (N₂). Looking at the histograms before the level shows me that players solutions typically take 200-250 cycles to output 10 nitrogen molecules and use about 22 instruction/direction symbols.

"Best Left Unanswered" - first attempt

My first attempt was fairly simple. The blue waldo grabs a nitrogren atom first (using the sync instruction, the red waldo waits for the blue waldo to have picked up its arom first) and then the red waldo grabs a nitrogen atom. The two waldos then drop off their atoms in the output area (blue's atom to the right to ensure there's no collision between atoms), Then the red waldo runs three bond+ instructions to form the triple bond followed by an out to flush the completed nitrogen molecule.

This first attempt takes 141 cycles and uses 20 symbols, outperforming the typical solution! (Perhaps it's too easy to over-engineer a solution for this one?)

The key step in optimizing here was realizing that the waldos' routes need not be a circuit. A straight line back-and-forth route was the shortest way between the input and output areas. This has the interesting side effect of each instruction (except those at each end) being run twice (once as the waldo moves left along the route and once as it moves right). This can be mitigated (e.g. running a drop instruction while not holding anything will do nothing) and exploited (e.g. we need to in two nitrogen atoms and can now do that with a single instruction symbol). By keeping the route lengths the same and choosing appropriate starting positions, we no longer need the sync instructions. A careful ordering of the instruction symbols gets us the nitrogen molecules we need.

"Best Left Unanswered" - improved attempt

To see how this solution works, we can go through the 12 cycle sequence that then repeats:

Cycle	Blue	Red
0	Start	Start
1	Inputs N
2	Grabs N
3	Inputs N
4		Grabs N
5	(out does nothing
6	(bond+ does nothing
7	(bond+ does nothing
8	Drops N
9	1st bond N-N	Drops N
10	2nd bond N-N	3rd bond N-N
11	Outputs N2	(drop does nothing)

The solution takes 119 cycles (10 sequences) to reach 10 nitrogen molecules and uses 13 symbols. While a significant improvement over my first attempt, the histograms show a sub-100 cycle time is possible and can be solved with as few as 8 symbols (though probably not both in the same solution). Now that's got my brain straining for some inspiration...

An even better solution awaits in Not the Chemistry I Remember (continued).