Block partition a string Inspiration.

Consider a list l, consisting of numbers. Define a block operation at index i on the list l to be the act of moving 3 consecutive elements starting from i in l to the end.

Example:

l, i (1-indexing) -&gt; l (after applying block operation at index i)
[1,2,3,4,5], 1 -&gt; [4,5,1,2,3]
[1,2,3,4,5,6,7], 3 -&gt; [1,2,6,7,3,4,5]


Given a list consisting of only 0 and 1, your challenge is to partition it so that zeros are at the front, and ones are at the back, using only block operations. Output should be the indices in the order they are applied on the list.

Because this is impossible for the list [1,0,1,0], the list length is guaranteed to be at least 5.

Test cases (1-indexing)

(there are other valid outputs)

[1,1,1,0,0] -&gt; [1]
[0,1,0,1,0] -&gt; [1,2,1,1]
[0,0,0,1,1,1,0,0,0] -&gt; [4]


Use this script to generate more test cases. (only input. The rplc ' ';',' part is used to replace spaces with commas in the output)

Winning criteria

code-challenge is the main winning criteria, and fastest-code is the tie-breaker. In particular:


The solution with the shortest output length (least number of block operations) with the test case (n_elem = 500, random_seed = {secret value}) wins. You should be able to run your solution to completion with the test case (n_elem = 500, random_seed = 123456).
In case of ties, the solution that can handles the largest power-of-2 value of n_elem with random_seed = {secret value} within 10 seconds (for me) wins.
In case of ties, the solution that takes less time on that test case wins.
Python 3, (0.397 n + 3.58) steps

1000-point polynomial regression by numpy.polyfit.




Number of steps for version 1: 0.0546 n² + 2.80 n - 221
Number of steps for version 2: 0.0235 n² + 0.965 n - 74
Number of steps for version 3: 0.00965 n² + 2.35 n - 111
Number of steps for version 4: 1.08 n - 36.3
Number of steps for version 5: 0.397 n + 3.58





Secret test case score for version 1: 14468
Secret test case score for version 2: 5349
Secret test case score for version 3: 4143
Secret test case score for version 4: 450
Secret test case score for version 5: 205






def partite(L):
&#9;endgame5 = [9,9,1,9,0,0,1,9,
&#9;&#9;0,1,0,1,0,1,1,9,
&#9;&#9;0,0,1,0,0,0,1,0,
&#9;&#9;0,0,0,1,0,0,0,9]
&#9;endgame6 = [9,9,2,9,1,1,2,9,0,2,0,0,1,2,2,9,
&#9;&#9;0,1,2,1,0,1,2,1,0,1,0,2,1,1,0,9,
&#9;&#9;0,0,1,0,1,0,1,1,0,0,0,0,1,1,1,1,
&#9;&#9;0,0,2,2,0,0,2,2,0,0,0,0,0,0,0,9]
&#9;endgame = [9,9,3,9,2,2,3,9,1,0,3,0,2,0,3,9,0,1,3,3,2,2,3,0,1,0,1,0,2,1,0,9,
&#9;&#9;0,0,2,1,0,0,2,2,1,0,1,2,0,0,0,2,0,1,3,3,3,3,3,0,1,1,1,1,1,3,0,9,
&#9;&#9;0,0,0,0,1,0,1,1,1,0,3,0,1,0,1,0,0,1,0,0,1,1,0,0,1,0,0,0,2,0,1,0,
&#9;&#9;0,0,2,0,0,0,2,0,0,0,2,0,0,0,2,0,0,0,3,0,3,0,3,0,3,0,2,3,3,0,0,9]
&#9;offset = 1
&#9;steps = []
&#9;def update(L,steps,ind):
&#9;&#9;steps.append(offset + ind)
&#9;&#9;if 0 &lt;= ind and ind+3 &lt; len(L):
&#9;&#9;&#9;return (steps,L[:ind]+L[ind+3:]+L[ind:ind+3])
&#9;&#9;else:
&#9;&#9;&#9;print(offset,ind,L)
&#9;&#9;&#9;raise
&#9;if len(L) == 5:
&#9;&#9;while endgame5[L[0]*16+L[1]*8+L[2]*4+L[3]*2+L[4]] != 9:
&#9;&#9;&#9;steps, L = update(L,steps,endgame5[L[0]*16+L[1]*8+L[2]*4+L[3]*2+L[4]])
&#9;&#9;return steps
&#9;if len(L) == 6:
&#9;&#9;while endgame6[L[0]*32+L[1]*16+L[2]*8+L[3]*4+L[4]*2+L[5]] != 9:
&#9;&#9;&#9;steps, L = update(L,steps,endgame6[L[0]*32+L[1]*16+L[2]*8+L[3]*4+L[4]*2+L[5]])
&#9;&#9;return steps
&#9;if 1 not in L:
&#9;&#9;return []
&#9;while len(L) &gt; 7 and 0 in L:
&#9;&#9;wf_check = len(L)
&#9;&#9;while L[0] != 0:
&#9;&#9;&#9;pos = [-1]
&#9;&#9;&#9;wf_check2 = -1
&#9;&#9;&#9;while True:
&#9;&#9;&#9;&#9;i = pos[-1]+1
&#9;&#9;&#9;&#9;while i &lt; len(L):
&#9;&#9;&#9;&#9;&#9;if L[i] == 0:
&#9;&#9;&#9;&#9;&#9;&#9;pos.append(i)
&#9;&#9;&#9;&#9;&#9;&#9;i += 1
&#9;&#9;&#9;&#9;&#9;else:
&#9;&#9;&#9;&#9;&#9;&#9;i += 3
&#9;&#9;&#9;&#9;assert len(pos) &gt; wf_check2
&#9;&#9;&#9;&#9;wf_check2 = len(pos)
&#9;&#9;&#9;&#9;space = (pos[-1]-len(L)+1)%3
&#9;&#9;&#9;&#9;ind = -1
&#9;&#9;&#9;&#9;tail = pos.pop()
&#9;&#9;&#9;&#9;i = len(L)-1
&#9;&#9;&#9;&#9;while i &gt;= 0:
&#9;&#9;&#9;&#9;&#9;if tail == i:
&#9;&#9;&#9;&#9;&#9;&#9;while tail == i:
&#9;&#9;&#9;&#9;&#9;&#9;&#9;i -= 1
&#9;&#9;&#9;&#9;&#9;&#9;&#9;tail = pos.pop() if pos else -1
&#9;&#9;&#9;&#9;&#9;&#9;i -= 2
&#9;&#9;&#9;&#9;&#9;elif i &lt; len(L)-3 and L[i+space] == 0:
&#9;&#9;&#9;&#9;&#9;&#9;ind = i
&#9;&#9;&#9;&#9;&#9;&#9;break
&#9;&#9;&#9;&#9;&#9;else:
&#9;&#9;&#9;&#9;&#9;&#9;i -= 1
&#9;&#9;&#9;&#9;if ind == -1:
&#9;&#9;&#9;&#9;&#9;break
&#9;&#9;&#9;&#9;steps, L = update(L, steps, ind)
&#9;&#9;&#9;&#9;pos = pos or [-1]
&#9;&#9;&#9;if L[0] == 0:
&#9;&#9;&#9;&#9;break
&#9;&#9;&#9;pos = [-1]
&#9;&#9;&#9;while L[0] != 0:
&#9;&#9;&#9;&#9;pos = [-1]
&#9;&#9;&#9;&#9;found = False
&#9;&#9;&#9;&#9;for i in range(1,len(L)):
&#9;&#9;&#9;&#9;&#9;if L[i] == 0:
&#9;&#9;&#9;&#9;&#9;&#9;if i%3 == (pos[-1]+1)%3:
&#9;&#9;&#9;&#9;&#9;&#9;&#9;pos.append(i)
&#9;&#9;&#9;&#9;&#9;&#9;else:
&#9;&#9;&#9;&#9;&#9;&#9;&#9;found = found or i
&#9;&#9;&#9;&#9;if found &gt; len(L)-4:
&#9;&#9;&#9;&#9;&#9;found = False
&#9;&#9;&#9;&#9;if not found:
&#9;&#9;&#9;&#9;&#9;break
&#9;&#9;&#9;&#9;triple = []
&#9;&#9;&#9;&#9;for i in range(1,len(L)-1):
&#9;&#9;&#9;&#9;&#9;if L[i-1] == 1 and L[i] == 1 and L[i+1] == 1:
&#9;&#9;&#9;&#9;&#9;&#9;triple.append(i)
&#9;&#9;&#9;&#9;&#9;if len(triple) &gt; 3:
&#9;&#9;&#9;&#9;&#9;&#9;break
&#9;&#9;&#9;&#9;space = (pos[-1]-len(L)+1)%3
&#9;&#9;&#9;&#9;if space == 0:
&#9;&#9;&#9;&#9;&#9;if found &gt;= 2 and found-2 not in pos and found-1 not in pos:
&#9;&#9;&#9;&#9;&#9;&#9;# ... _ 1 _ [0] 0 ...
&#9;&#9;&#9;&#9;&#9;&#9;if found-2 in triple:
&#9;&#9;&#9;&#9;&#9;&#9;&#9;triple.remove(found-2)
&#9;&#9;&#9;&#9;&#9;&#9;if found-3 in triple:
&#9;&#9;&#9;&#9;&#9;&#9;&#9;triple.remove(found-3)
&#9;&#9;&#9;&#9;&#9;&#9;if L[-1] == 1:
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, found-2)
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, len(L)-4)
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, len(L)-4)
&#9;&#9;&#9;&#9;&#9;&#9;elif triple:
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, found-2)
&#9;&#9;&#9;&#9;&#9;&#9;&#9;if found &lt; triple[0]:
&#9;&#9;&#9;&#9;&#9;&#9;&#9;&#9;triple[0] -= 3
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, triple[0]-1)
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, len(L)-4)
&#9;&#9;&#9;&#9;&#9;&#9;else:
&#9;&#9;&#9;&#9;&#9;&#9;&#9;break
&#9;&#9;&#9;&#9;&#9;&#9;assert L[-3] == 0
&#9;&#9;&#9;&#9;&#9;elif found &gt;= 1 and found-1 not in pos and found+1 not in pos:
&#9;&#9;&#9;&#9;&#9;&#9;# ... _ 1 [0] _ 0 ...
&#9;&#9;&#9;&#9;&#9;&#9;if found-2 in triple:
&#9;&#9;&#9;&#9;&#9;&#9;&#9;triple.remove(found-2)
&#9;&#9;&#9;&#9;&#9;&#9;if L[-2] == 1 and L[-1] == 1:
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, found-1)
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, len(L)-5)
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, len(L)-5)
&#9;&#9;&#9;&#9;&#9;&#9;elif triple:
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, found-1)
&#9;&#9;&#9;&#9;&#9;&#9;&#9;if found &lt; triple[0]:
&#9;&#9;&#9;&#9;&#9;&#9;&#9;&#9;triple[0] -= 3
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, triple[0]-1)
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, len(L)-5)
&#9;&#9;&#9;&#9;&#9;&#9;elif L[-1] == 1:
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, found-1)
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, len(L)-4)
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, len(L)-4)
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, len(L)-4)
&#9;&#9;&#9;&#9;&#9;&#9;else:
&#9;&#9;&#9;&#9;&#9;&#9;&#9;break
&#9;&#9;&#9;&#9;&#9;&#9;assert L[-3] == 0
&#9;&#9;&#9;&#9;&#9;else:
&#9;&#9;&#9;&#9;&#9;&#9;break
&#9;&#9;&#9;&#9;elif space == 1:
&#9;&#9;&#9;&#9;&#9;# ... 1 1 [0] 0 ...
&#9;&#9;&#9;&#9;&#9;if found &gt;= 2 and found-2 not in pos and found-1 not in pos:
&#9;&#9;&#9;&#9;&#9;&#9;if found-2 in triple:
&#9;&#9;&#9;&#9;&#9;&#9;&#9;triple.remove(found-2)
&#9;&#9;&#9;&#9;&#9;&#9;if found-3 in triple:
&#9;&#9;&#9;&#9;&#9;&#9;&#9;triple.remove(found-3)
&#9;&#9;&#9;&#9;&#9;&#9;if triple:
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, found-2)
&#9;&#9;&#9;&#9;&#9;&#9;&#9;if found &lt; triple[0]:
&#9;&#9;&#9;&#9;&#9;&#9;&#9;&#9;triple[0] -= 3
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, triple[0]-1)
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, len(L)-5)
&#9;&#9;&#9;&#9;&#9;&#9;elif L[-2] == 1 and L[-1] == 1:
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, found-2)
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, len(L)-4)
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, len(L)-5)
&#9;&#9;&#9;&#9;&#9;&#9;else:
&#9;&#9;&#9;&#9;&#9;&#9;&#9;break
&#9;&#9;&#9;&#9;&#9;&#9;assert L[-2] == 0
&#9;&#9;&#9;&#9;&#9;else:
&#9;&#9;&#9;&#9;&#9;&#9;break
&#9;&#9;&#9;&#9;else:
&#9;&#9;&#9;&#9;&#9;if found+1 not in pos and found+2 not in pos:
&#9;&#9;&#9;&#9;&#9;&#9;# ... 0 [0] _ 1 _ ...
&#9;&#9;&#9;&#9;&#9;&#9;if found+2 in triple:
&#9;&#9;&#9;&#9;&#9;&#9;&#9;triple.remove(found+2)
&#9;&#9;&#9;&#9;&#9;&#9;if found+3 in triple:
&#9;&#9;&#9;&#9;&#9;&#9;&#9;triple.remove(found+3)
&#9;&#9;&#9;&#9;&#9;&#9;if L[-2] == 1 and L[-1] == 1:
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, found)
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, len(L)-5)
&#9;&#9;&#9;&#9;&#9;&#9;elif L[-1] == 1:
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, found)
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, len(L)-4)
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, len(L)-4)
&#9;&#9;&#9;&#9;&#9;&#9;elif triple:
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, triple[0]-1)
&#9;&#9;&#9;&#9;&#9;&#9;&#9;if triple[0] &lt; found:
&#9;&#9;&#9;&#9;&#9;&#9;&#9;&#9;found -= 3
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, found)
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, len(L)-5)
&#9;&#9;&#9;&#9;&#9;&#9;else:
&#9;&#9;&#9;&#9;&#9;&#9;&#9;break
&#9;&#9;&#9;&#9;&#9;&#9;assert L[-1] == 0
&#9;&#9;&#9;&#9;&#9;elif found &gt;= 1 and found-1 not in pos and found+1 not in pos:
&#9;&#9;&#9;&#9;&#9;&#9;# ... 0 _ [0] 1 _ ...
&#9;&#9;&#9;&#9;&#9;&#9;if found+2 in triple:
&#9;&#9;&#9;&#9;&#9;&#9;&#9;triple.remove(found+2)
&#9;&#9;&#9;&#9;&#9;&#9;if L[-1] == 1:
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, found-1)
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, len(L)-4)
&#9;&#9;&#9;&#9;&#9;&#9;elif triple:
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, triple[0]-1)
&#9;&#9;&#9;&#9;&#9;&#9;&#9;if triple[0] &lt; found:
&#9;&#9;&#9;&#9;&#9;&#9;&#9;&#9;found -= 3
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, found-1)
&#9;&#9;&#9;&#9;&#9;&#9;&#9;steps, L = update(L, steps, len(L)-4)
&#9;&#9;&#9;&#9;&#9;&#9;else:
&#9;&#9;&#9;&#9;&#9;&#9;&#9;break
&#9;&#9;&#9;&#9;&#9;&#9;assert L[-1] == 0
&#9;&#9;&#9;&#9;&#9;else:
&#9;&#9;&#9;&#9;&#9;&#9;break
&#9;&#9;&#9;if L[0] == 0:
&#9;&#9;&#9;&#9;break
&#9;&#9;&#9;if 0 in L[::3]:
&#9;&#9;&#9;&#9;assert L[::3].index(0) &lt; wf_check
&#9;&#9;&#9;&#9;wf_check = L[::3].index(0)
&#9;&#9;&#9;steps, L = update(L, steps, 0)
&#9;&#9;assert L[0] == 0
&#9;&#9;offset += L.index(1)
&#9;&#9;del L[:L.index(1)]
&#9;&#9;continue
&#9;if 0 in L:
&#9;&#9;offset -= 7-len(L)
&#9;&#9;L = [0]*(7-len(L))+L
&#9;&#9;assert(len(L) == 7)
&#9;&#9;while endgame[L[0]*64+L[1]*32+L[2]*16+L[3]*8+L[4]*4+L[5]*2+L[6]] != 9:
&#9;&#9;&#9;steps, L = update(L,steps,endgame[L[0]*64+L[1]*32+L[2]*16+L[3]*8+L[4]*4+L[5]*2+L[6]])
&#9;return steps


Try it online!