# Block partition a string

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) -> l (after applying block operation at index i)
[1,2,3,4,5], 1 -> [4,5,1,2,3]
[1,2,3,4,5,6,7], 3 -> [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] -> 
[0,1,0,1,0] -> [1,2,1,1]
[0,0,0,1,1,1,0,0,0] -> 


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

is the main winning criteria, and 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.
• Sandbox post. (note) I have a linear-time linear-space solution, but it has huge constant factor, besides it's not easy to implement. It's possible to reduce the constant factor but then it's even harder to implement. Jun 6, 2018 at 16:22
• (disclaimer: I have solved the linked challenge) Jun 6, 2018 at 16:37
• Just to clarify, the output does not need to be the shortest possible output? Jun 6, 2018 at 16:42
• @JungHwanMin Correct. Jun 6, 2018 at 16:43
• Jun 6, 2018 at 16:52

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


Try it online!

# Python 3, ~179 steps for n=500 (on average)

A heuristic greedy approach. Kinda slow but still works. Uses an optimal solver for small sizes.

def incomplete_groups(l):
r = 0
ones = 0
for x in l:
if x == "1":
ones += 1
else:
if ones % 3:
r += 1
ones = 0
# Ones at the end don't count as an incomplete group.

return r

def move(l, i):
return l[:i] + l[i+3:] + l[i:i+3]

def best_pos(l, hist):
r = []
cleanup = incomplete_groups(l) == 0

candidates = []
for i in range(len(l) - 3):
block = l[i:i+3]
if block == "111" and cleanup:
return i
elif block == "111":
continue

new = move(l, i)
bad_start = i < 3 and "10" in l[:3]
candidates.append((new not in hist, -incomplete_groups(new), bad_start, block != "000", i))

candidates.sort(reverse=True)
return candidates[-1]

def done(l):
return list(l) == sorted(l)

class IDAStar:
def __init__(self, h, neighbours):
""" Iterative-deepening A* search.

h(n) is the heuristic that gives the cost between node n and the goal node. It must be admissable, meaning that h(n) MUST NEVER OVERSTIMATE the true cost. Underestimating is fine.

neighbours(n) is an iterable giving a pair (cost, node, descr) for each node neighbouring n
IN ASCENDING ORDER OF COST. descr is not used in the computation but can be used to
efficiently store information about the path edges (e.g. up/left/right/down for grids).
"""

self.h = h
self.neighbours = neighbours
self.FOUND = object()

def solve(self, root, is_goal, max_cost=None):
""" Returns the shortest path between the root and a given goal, as well as the total cost.
If the cost exceeds a given max_cost, the function returns None. If you do not give a
maximum cost the solver will never return for unsolvable instances."""

self.is_goal = is_goal
self.path = [root]
self.is_in_path = {root}
self.path_descrs = []
self.nodes_evaluated = 0

bound = self.h(root)

while True:
t = self._search(0, bound)
if t is self.FOUND: return self.path, self.path_descrs, bound, self.nodes_evaluated
if t is None: return None
bound = t

def _search(self, g, bound):
self.nodes_evaluated += 1

node = self.path[-1]
f = g + self.h(node)
if f > bound: return f
if self.is_goal(node): return self.FOUND

m = None # Lower bound on cost.
for cost, n, descr in self.neighbours(node):
if n in self.is_in_path: continue

self.path.append(n)
self.path_descrs.append(descr)
t = self._search(g + cost, bound)

if t == self.FOUND: return self.FOUND
if m is None or (t is not None and t < m): m = t

self.path.pop()
self.path_descrs.pop()
self.is_in_path.remove(n)

return m

def h(l):
"""Number of groups of 1 with length <= 3 that come before a zero."""
h = 0
num_ones = 0
complete_groups = 0
incomplete_groups = 0
for x in l:
if x == "1":
num_ones += 1
else:
while num_ones > 3:
num_ones -= 3
h += 1
complete_groups += 1
if num_ones > 0:
h += 1
incomplete_groups += 1
num_ones = 0

return complete_groups + incomplete_groups

def neighbours(l):
inc_groups = incomplete_groups(l)
final = inc_groups == 0

candidates = []
for i in range(len(l) - 3):
left = l[:i]
block = l[i:i+3]
right = l[i+3:]
cand = (1, left + right + block, i)

# Optimal choice.
if final and (block != "111" or i >= len(l.rstrip("1"))):
continue

candidates.append(cand)

candidates.sort(key=lambda c: c, reverse=True)

return candidates

def is_goal(l):
return all(l[i] <= l[i+1] for i in range(len(l)-1))

opt_solver = IDAStar(h, neighbours)

def partite(l):
if isinstance(l, list):
l = "".join(map(str, l))
if len(l) < 10:
return [i + 1 for i in opt_solver.solve(l, is_goal)]
moves = []
hist = [l]
while not done(l):
i = best_pos(l, hist)
l = move(l, i)
moves.append(i+1)
hist.append(l)
return moves