Background: Mazezam's complexity

See previous pieces and other links for the background:

Aaron's simpler exponential level family

Malcolm and I exchanged further emails with Aaron and his colleagues, with the result that Aaron simplified the exponential level family construction. His approach is illustrated by the animation below.

As before, a light row in its leftward position means that bit is '0'; in its rightwards position means '1'. The lowest light row represents the least-significant bit, b0, with higher rows representing more-significant bits. All rows therefore start off in their leftward position.

The level consists of six vertical 'gadgets', of increasing height as you work from left to right in the level. Each gadget allows the adjustment of one bit, provided that the requirements are met for that bit to be adjustable with the Gray code counter having the value represented by the current state of the puzzle. Finally, there is an escape route at the right of the level, which can only be traversed when the Gray code is in its final state of 100000.

Call a bit 'fixed' if you aren't allowed to change it with the counter in its current state. E.g., with the counter as 101000, we are allowed to change b0 and b4, so the 'fixed' bits are b1, b2, b3, and b5. Because it's always permissible to adjust the b0 bit, b0 is never fixed.

In my previous version, you cannot pass vertically through a 'fixed' row without leaving that row in the state it was before you entered it. In the Gray counter level family, we only need a weaker constraint, namely that the state of all 'fixed' rows in one gadget are in the same state on leaving the gadget as when you entered the gadget. I.e., my design enforced the correctness of the representation whenever the player was not in a bit-representing row, but Aaron's simplification weakens this to 'the puzzle state represents a valid Gray counter value whenever the player is not in a gadget'. The weaker constraint is still sufficient to require the player to step through the Gray counter.

This gives a bit more freedom in the row design, which Aaron's simplification exploits. To adjust b4, say, we require that b3.b2.b1.b0 is 1000, so that the gap in each of those light rows aligns with the gap in the dark row below it. On passing up the gadget, b2 is temporarily moved to its 1 state, but by the time the player passes downwards through that row, b2 must be moved back to 0, restoring the correct representation. While in the gadget, the player can also change, say, b3, but, again, it has to be restored to its original state (1) for the player to get back out of the gadget.

Counter value: 0 0 0 0 0 0
Number of moves: 0
Slow Fast

The 'Counter value' display here is bold and black when the puzzle represents a valid state. It is shown non-bold and lighter when the puzzle is temporarily not representing the true Gray counter value.

(Thanks to Oliver Nash for the suggestion to use CSS3 transitions in the animation.)

Solution lengths

This version needs 981 moves to solve the 6-bit level; the previous version needed 6730.

Source code

Available on github: bennorth/simpler-exponential-mazezam.