Block partition a string
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!