Below is a trace of the algorithm acting on a line and
its clue, which are displayed in the first few lines.
Each subsequent section shows the current mode, the
current block (and its length and position), a
recapitulation of the initial state of the line, a scale,
and graphically the positions of all blocks.
mininv
is shown as the trailing
mN number.
The graphical block positions occupy more than one
line when blocks occupy overlapping positions.
# and ! show cells belonging to
the current block. X and ! show
the offset of the first solid covered by the block.
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
rule: 1,5,1,1,1
We start with all blocks on the left, waiting to find
valid positions.
INVALID
Block 0 of 1 at 0
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B0 >#
+++++
+
+
+ < [0) m0
Dot at offset 0
Skipped to 1
(The code [0) m0 shows the current values
of base
, max
and
mininv
.)
We have detected that block 0 covers a dot, so it
cannot stay here. We move it past the dot, and try again…
several times.
INVALID
Block 0 of 1 at 1
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B0 > #
+++++
+
+
+ < [0) m0
Dot at offset 0
Skipped to 2
INVALID
Block 0 of 1 at 2
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B0 > #
+++++
+
+
+ < [0) m0
Dot at offset 0
Skipped to 3
INVALID
Block 0 of 1 at 3
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B0 > #
+++++
+
+
+ < [0) m0
Dot at offset 0
Skipped to 4
INVALID
Block 0 of 1 at 4
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B0 > #
+++++
+
+
+ < [0) m0
Dot at offset 0
Skipped to 5
INVALID
Block 0 of 1 at 5
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B0 > #
+++++
+
+
+ < [0) m0
Valid at 5
At last, there is room for block 0. Consider the next
block, ensuring that it starts after the current one.
INVALID
Block 1 of 5 at 7
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B1 > + #####
+
+
+ < [0) m0
Valid at 7
INVALID
Block 2 of 1 at 13
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B2 > + +++++ #
+
+ < [0) m0
Valid at 13
INVALID
Block 3 of 1 at 15
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B3 > + +++++ + #
+ < [0) m0
Valid at 15
INVALID
Block 4 of 1 at 17
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B4 > + +++++ + + # < [0) m0
Valid at 17
Solid at offset 0
(Additionally, we notice that block 4 covers a solid
at position 17 + 0.)
INVALID
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B5 > + +++++ + + X < [0) m0
Trailing solid at 22
We've placed all the blocks, but still some trailing
solids remain exposed. We'll have to draw up earlier
blocks to release the later blocks to let them cover the
later solids.
DRAWING
Block 4 of 1 at 17
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B4 > + +++++ + + # < [0) m0
Target is 4
New target is 4
Block 3 brought to 17
We have chosen to draw up block 3 to cover the solid
currently covered by block 4
INVALID
Block 3 of 1 at 17
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B3 > + +++++ + #
+ < [0) m0
Valid at 17
Solid at offset 0
INVALID
Block 4 of 1 at 19
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B4 > + +++++ + X # < [0) m0
Dot at offset 0
Skipped to 20
INVALID
Block 4 of 1 at 20
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B4 > + +++++ + X # < [0) m0
Dot at offset 0
Skipped to 21
INVALID
Block 4 of 1 at 21
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B4 > + +++++ + X # < [0) m0
Dot at offset 0
Skipped to 22
INVALID
Block 4 of 1 at 22
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B4 > + +++++ + X # < [0) m0
Valid at 22
Solid at offset 0
INVALID
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B5 > + +++++ + X X < [0) m0
Trailing solid at 35
Still we have trailing solids, so we must draw up
block 2 to release 3 to release 4 to cover the final
solid.
DRAWING
Block 4 of 1 at 22
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B4 > + +++++ + X # < [0) m0
Target is 4
New target is 3
Block 2 brought to 17
The target was 4, which covers a solid. The current
block was also 4, so we looked at 3, and found it
unsuitable because it already had a solid. It became the
new target, then we looked at 2. It was suitable to cover
3's solid, because it does not cover one itself.
INVALID
Block 2 of 1 at 17
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B2 > + +++++ #
+ + < [0) m0
Valid at 17
Solid at offset 0
INVALID
Block 3 of 1 at 19
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B3 > + +++++ X # + < [0) m0
Dot at offset 0
Skipped to 20
INVALID
Block 3 of 1 at 20
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B3 > + +++++ X # + < [0) m0
Dot at offset 0
Skipped to 21
INVALID
Block 3 of 1 at 21
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B3 > + +++++ X #
+ < [0) m0
Dot at offset 0
Skipped to 22
INVALID
Block 3 of 1 at 22
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B3 > + +++++ X #
+ < [0) m0
Valid at 22
Solid at offset 0
INVALID
Block 4 of 1 at 24
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B4 > + +++++ X X # < [0) m0
Valid at 24
INVALID
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B5 > + +++++ X X + < [0) m0
Trailing solid at 35
INVALID
Block 4 of 1 at 35
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B4 > + +++++ X X #< [0) m0
Valid at 35
Solid at offset 0
We eventually have all the blocks in valid positions
with no trailing solids. This arrangement must be merged
into the (so far empty) results, before
SLIDING.
(This should be the same as the left-most arrangement,
as computed by the ‘fast’ algorithm.)
INVALID
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B5 > + +++++ X X X< [0) m0
New valid state found
Accumulate>-----...............................<
Accumulate>.....#..............................<
Accumulate>......-.............................<
Accumulate>.......#####........................<
Accumulate>............-----...................<
Accumulate>.................#..................<
Accumulate>..................----..............<
Accumulate>......................#.............<
Accumulate>.......................------------.<
Accumulate>...................................#<
Accumulate>....................................<
SLIDING
Block 4 of 1 at 35
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B4 > + +++++ X X !< [0) m5
Limit is 36
Right block is right-most
Limit reached; 4 blocks left
SLIDING
Block 3 of 1 at 22
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B3 > + +++++ X ! X< [0) m5
Limit is 34
Limit reached; 3 blocks left
SLIDING
Block 2 of 1 at 17
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B2 > + +++++ ! X X< [0) m5
Limit is 21
Dot obstructs at 18
No space past dot
Limit reached; 2 blocks left
SLIDING
Block 1 of 5 at 7
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B1 > + ##### X X X< [0) m5
Limit is 16
Merging block 1 from 7 to 11
Accumulate>.......++++.........................<
Accumulate>............++++....................<
Limit reached; 1 blocks left
SLIDING
Block 0 of 1 at 5
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B0 > # +++++ X X X< [0) m5
Limit is 10
Merging block 0 from 5 to 9
Accumulate>.....+-++...........................<
Accumulate>......++++..........................<
Limit reached; 0 blocks left
All blocks have slid as far right as they can for the
moment. From the right, we have to seek a block to draw
up.
DRAWING
Block 3 of 1 at 22
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B3 > + +++++ X # +< [0) m5
Target is 3
New target is 2
Block 1 brought to 13
INVALID
Block 1 of 5 at 13
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B1 > + #####
+ + +< [0) m1
Dot at offset 3
Skipped to 17
INVALID
Block 1 of 5 at 17
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B1 > + #####
+ + +< [0) m1
Dot at offset 1
Earlier solid at offset 0
DRAWING
Block 1 of 5 at 17
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B1 > + #####
+ + +< [0) m1
Target is 1
Can't draw any more without restoring
We have drawn a block up which cannot fit. We'll put
everything back, and find an earlier block.
RESTORING
Block 3 of 1 at 22
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B3 > + X++++
X # +< [0) m1
Restoring 3 from 22 to 22
Restoring 2 from 17 to 17
Restoring 1 from 17 to 11
Returned to block 1
DRAWING
Block 1 of 5 at 11
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B1 > + ##### + + +< [0) m5
Target is 2
New target is 2
Block 0 brought to 17
INVALID
Block 0 of 1 at 17
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B0 > #
+++++ + + +< [0) m0
Valid at 17
Solid at offset 0
INVALID
Block 1 of 5 at 19
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B1 > X #####
+ + +< [0) m0
Dot at offset 0
Skipped to 20
INVALID
Block 1 of 5 at 20
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B1 > X #####
+ + +< [0) m0
Dot at offset 0
Skipped to 21
INVALID
Block 1 of 5 at 21
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B1 > X #####
+ + +< [0) m0
Dot at offset 0
Skipped to 22
INVALID
Block 1 of 5 at 22
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B1 > X #####
+ + +< [0) m0
Valid at 22
Solid at offset 0
INVALID
Block 2 of 1 at 28
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B2 > X X++++ #
+ +< [0) m0
Valid at 28
INVALID
Block 3 of 1 at 30
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B3 > X X++++ + # +< [0) m0
Valid at 30
This gives us a new valid arrangement, which must be
recorded.
INVALID
Block 4 of 1 at 35
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B4 > X X++++ + + #< [0) m0
New valid state found
Accumulate>-----+++++++++++-...................<
Accumulate>.................#..................<
Accumulate>..................----..............<
Accumulate>......................#++++.........<
Accumulate>...........................-........<
Accumulate>............................+.......<
Accumulate>.............................-......<
Accumulate>..............................+.....<
Accumulate>...............................----.<
SLIDING
Block 3 of 1 at 30
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B3 > X X++++ + # X< [0) m4
Limit is 34
Dot obstructs at 31
Jumpable
Accumulate>..............................+.....<
Accumulate>.................................+..<
SLIDING
Block 3 of 1 at 33
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B3 > X X++++ + # X< [0) m4
Limit is 34
Right block is right-most
Limit reached; 3 blocks left
SLIDING
Block 2 of 1 at 28
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B2 > X X++++ # + X< [0) m4
Limit is 32
Merging block 2 from 28 to 30
Accumulate>............................+-......<
Accumulate>.............................++.....<
Dot obstructs at 31
No space past dot
Right block is right-most for dot
Limit reached; 2 blocks left
SLIDING
Block 1 of 5 at 22
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B1 > X !#### + + X< [0) m4
Limit is 29
Limit reached; 1 blocks left
SLIDING
Block 0 of 1 at 17
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B0 > ! X++++ + + X< [0) m4
Limit is 21
Dot obstructs at 18
No space past dot
Limit reached; 0 blocks left
We have determined that blocks 2, 3 and 4 have reached
their right-most positions, while 0 and 1 are stuck on
solids. There can be no more valid arrangements.
DRAWING
Block 1 of 5 at 22
X: 36>----- -#----# -- #<
>012345678901234567890123456789012345<
B1 > X ##### + + +< [0) m4
Target is 1
Length: 36
Rule: 1,5,1,1,1
Original: >-----------------#----#####--#---#-#<
Broken: >----- -#----# -- #<
complete>-----+++++++++++-#----#++++-+++--+-#< ( 19) 0.006ms
fast>-----+++++++++++-#----#++++++++--+-#< ( 1) 0.006ms
fcomp>-----+++++++++++-#----#++++-+++--+-#< ( 28) 0.006ms