Skip to content

Instantly share code, notes, and snippets.

@torchlight torchlight/loopover.py
Last active Sep 15, 2019

Embed
What would you like to do?
Loopover O(n log^2 n) solver
"""
Loopover solver for arbitrary sizes; asymptotically optimal in STM up to log factors.
Let N be the total number of cells.
This solver uses Shell sort with 3-smooth gaps to sort all of the pieces. For a specific gap, the
swaps performed are all "disjoint" and we apply O(N) setup moves so that all the swaps can be
performed in O(N) moves. Since there are only O(log^2 N) gaps, this leads to an O(N log^2 N) solving
algorithm.
There are some technical details relating to permutation parity, which makes the naive idea not
quite work, but these can be worked around.
"""
import itertools
import math
import random
def remainder(x, y):
fudge = y - y//2 - 1
return (x + fudge) % y - fudge
def move_row(board, row_index, amount):
amount %= len(board[0])
if amount == 0:
return
board[row_index] = board[row_index][-amount:] + board[row_index][:-amount]
def move_col(board, col_index, amount):
amount %= len(board)
if amount == 0:
return
col = [row[col_index] for row in board]
col = col[-amount:] + col[:-amount]
for (row, x) in zip(board, col):
row[col_index] = x
def invert_move_sequence(seq):
return tuple((dir, index, -amount) for (dir, index, amount) in seq[::-1])
def apply_move_sequence(board, seq):
move_funs = {'r': move_row, 'c': move_col}
for (dir, index, amount) in seq:
move_funs[dir](board, index, amount)
def normalise_move_sequence(rows, cols, seq):
return tuple(filter(lambda x: x[2] != 0, ((d, i, remainder(a, rows if d == 'c' else cols)) for (d, i, a) in seq)))
def transpose_move_sequence(seq):
switch = {'r': 'c', 'c': 'r'}
return tuple((switch[d], i, a) for (d, i, a) in seq)
def len_move_sequence(seq):
return sum(abs(a) for (d, i, a) in seq if a != 0)
def create_board(rows, cols):
# note that rows = height, cols = width
return [[c + cols*r for c in range(cols)] for r in range(rows)]
def create_random_board(rows, cols, random=random):
if rows > 1 or cols > 1:
l = list(range(rows * cols))
random.shuffle(l)
if rows % 2 == cols % 2 == 1 and permutation_parity(l) == 1:
l[0], l[1] = l[1], l[0]
else:
n = rows * cols
r = random.randrange(n)
l = [(i+r)%n for i in range(n)]
return [l[cols*r:cols*(r+1)] for r in range(rows)]
def copy_board(board):
return [row[:] for row in board]
def flatten_board(board):
flattened = []
for row in board:
flattened.extend(row)
return flattened
def prettyprint(board):
print('\n'.join('\t'.join(map(str, row)) for row in board))
def decompose_inverse_permutation(perm):
"""
Given a permutation (given as a list of integers), decompose its inverse into a product of
involutions $\pi^{-1} = \pi_0 \pi_1 \pi_2 \dots$ (given as a list of lists of swaps) such that
each $\pi_i$ has "uniform-distance" swaps, i.e. it is of the form
$\pi_i = (a_0, a_0+d) (a_1, a_1+d) \dots$
(We can obtain a decomposition for the input permutation $\pi$ itself by reversing the
decomposition, since the decomposition consists solely of transpositions. However, we have no
use for this.)
This is currently done with Shellsort with 3-smooth gaps; see:
http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/shell/shellen.htm
Odd-even merge sort would also work, and I believe bitonic merge sort (in its bitonic,
non-monotonised form) should also work, but those are more complicated and only get us (maybe)
a constant factor improvement in the number of swaps.
"""
if len(perm) == 1:
return []
perm = list(perm) # make a copy that we can mess around with
n = len(perm)
decomposition = []
gap = 1
# determine the initial gap
while 3*gap < n:
gap *= 3
if 2*gap < n:
gap *= 2
# loop over the 3-smooth numbers
while True:
stage = []
# while the *comparisons* with 3-smooth Shell sort aren't disjoint, the resulting *swaps*
# always are because an element can't move more than once for each gap.
for i in range(n-gap):
if perm[i] > perm[i+gap]:
perm[i], perm[i+gap] = perm[i+gap], perm[i]
stage.append((i, i+gap))
if stage:
decomposition.append(tuple(stage))
# if the gap is 1, we're done
if gap == 1:
break
# if not, update the gap
elif gap % 2 == 0:
gap //= 2
else:
gap = gap // 3
while 2*gap < n:
gap *= 2
# note that the gaps are not monotonically decreasing; the gap sequence we use is
# the reverse of:
# 1, 2, 4, 8, ..., 3, 6, 12, 24, ..., 9, 18, 36, 72, ..., ...
# this still works for Shell sort because every time we hit a gap g, we've already sorted by
# 2g and by 3g.
return tuple(decomposition)
def permutation_parity(perm):
return sum(map(len, decompose_inverse_permutation(perm))) % 2
"""
These solving functions are *in-place* and return the move sequence used.
We assume the dimensions are at least 2 on each side. Silly/weird things can happen on 1xn or nx1
boards, so don't do that.
"""
def solve_piece_in_first_row(board, index):
"""
Solve a piece that belongs in the first row.
Constraints:
- index < cols
- all pieces before index in the first row are already solved
Maximum move count:
floor(rows/2) + floor(cols/2) + 1
"""
rows, cols = len(board), len(board[0])
((r, c), ) = ((r, c) for (r, row) in enumerate(board) for (c, x) in enumerate(row) if x == index)
if r == 0 and c == index:
return ()
if index == 0:
# first piece; don't need to care about preserving anything
move_row(board, r, -c)
move_col(board, 0, -r)
if r == 0:
return (('r', r, -c), )
if c == 0:
return (('c', 0, -r), )
return (('r', r, -c), ('c', 0, -r))
sol = []
if r == 0:
# not the first piece, and it's stuck in the first row at the wrong position
move_col(board, c, 1)
sol.append(('c', c, 1))
r += 1
# slide the piece to the correct column
if c != index:
move_row(board, r, index-c)
sol.append(('r', r, index-c))
# then slide it to the top row
move_col(board, index, -r)
sol.append(('c', index, -r))
return tuple(sol)
def solve_phase1(board):
"""
Solve the first two pieces of the first row and parity.
Maximum move count:
rows + cols + 2
"""
solution = solve_piece_in_first_row(board, 0)
solution += solve_piece_in_first_row(board, 1)
if permutation_parity(flatten_board(board)) == 1:
# if we have odd parity, at least one of the two dimensions must be even
# (otherwise every board state would have even parity)
rows = len(board)
cols = len(board[0])
if cols % 2 == 0:
solution += (('r', 1, 1), )
move_row(board, 1, 1)
else:
# if cols is odd, then it must be at least 3 so moving column 2 won't affect the two
# pieces we just solved.
solution += (('c', 2, 1), )
move_col(board, 2, 1)
return solution
def solve_phase2(board):
"""
Solve the rest of the pieces once the first two pieces and parity are solved.
Maximum move count:
<= 19.25/((log 2)(log 3)) * N * log(N)^2 * (1+o(1)) if rows = O(1) or cols = O(1)
or 11/ ... if rows, cols = o(N)
"""
rows, cols = len(board), len(board[0])
stages = decompose_inverse_permutation(flatten_board(board))
sol = []
for stage in stages:
diff = stage[0][1]-stage[0][0] # the gap (must be the same for all stage[i][1]-stage[i][0])
stage_coords = tuple((divmod(a, cols), divmod(b, cols)) for (a, b) in stage)
swaps_nooverflow = tuple((a, b) for (a, b) in stage_coords if b[0]-a[0] == diff // cols)
swaps_overflow = tuple((a, b) for (a, b) in stage_coords if b[0]-a[0] == diff // cols + 1)
assert len(swaps_nooverflow) + len(swaps_overflow) == len(stage_coords)
seq = get_uniform_swaps_move_sequence(rows, cols, swaps_nooverflow)
apply_move_sequence(board, seq)
sol.extend(seq)
seq = get_uniform_swaps_move_sequence(rows, cols, swaps_overflow)
apply_move_sequence(board, seq)
sol.extend(seq)
return tuple(sol)
def solve(board):
rows, cols = len(board), len(board[0])
return normalise_move_sequence(rows, cols, solve_phase1(board) + solve_phase2(board))
def get_3cycle_move_sequence(rows, cols, a, b, c):
"""
Apply a 3-cycle moving the piece at position a to position b to position c to position a. The
positions are specified as (row, column) coordinates.
Maximum move count:
||a-b|| + ||b-c|| + ||c-a|| + 2 for non-general-position
<= 3/2 (||a-b|| + ||b-c|| + ||c-a||)
<= 3/2 (rows + cols)
3/2 (||a-b|| + ||b-c|| + ||c-a||) for general position
<= 3/2 (rows + cols)
"""
if a[0] == b[0] == c[0]:
# all in the same row; move one piece into a separate row
return (('c', c[1], 1), ) + get_3cycle_move_sequence_row_interchange(a, b, ((c[0]+1) % rows, c[1])) + (('c', c[1], -1), )
# check if two points are in the same row; if so, then cycle the points so that the first two
# are in the same row
if a[0] == b[0]:
return get_3cycle_move_sequence_row_interchange(a, b, c)
if b[0] == c[0]:
return get_3cycle_move_sequence_row_interchange(b, c, a)
if c[0] == a[0]:
return get_3cycle_move_sequence_row_interchange(c, a, b)
if a[1] == b[1] or b[1] == c[1] or c[1] == a[1]:
# two pieces in the same column; transpose and call into the above
return transpose_move_sequence(get_3cycle_move_sequence(cols, rows, a[::-1], b[::-1], c[::-1]))
# otherwise, the pieces are "in general position" (all rows distinct, all columns distinct)
# if the sum of vertical distances is smaller than the sum of horizontal distances, move b to
# the same row as a, then do a standard 3-cycle; otherwise, transpose first, then do that.
sum_rowdist = sum(abs(remainder(x, rows)) for x in (a[0]-b[0], b[0]-c[0], c[0]-a[0]))
sum_coldist = sum(abs(remainder(x, cols)) for x in (a[1]-b[1], b[1]-c[1], c[1]-a[1]))
if sum_rowdist <= sum_coldist:
return (('c', b[1], a[0]-b[0]), ) + get_3cycle_move_sequence_row_interchange(a, (a[0], b[1]), c) + (('c', b[1], b[0]-a[0]), )
return (('r', b[0], a[1]-b[1]), ) + transpose_move_sequence(get_3cycle_move_sequence_row_interchange(a[::-1], (a[1], b[0]), c[::-1])) + (('r', b[0], b[1]-a[1]), )
def get_3cycle_move_sequence_row_interchange(a, b, c):
"""
Assume a[0] == b[0] != c[0].
Maximum move count:
||a-b|| + ||b-c|| + ||c-a||
<= rows + cols
(since the sum of horizontal distances <= cols and likewise in the other direction)
"""
seq = (
('r', a[0], c[1]-a[1]), # move A to same col as C
('c', c[1], a[0]-c[0]), # move C to take A's place
('r', a[0], a[1]-b[1]), # move B to where C is now
('c', c[1], c[0]-a[0]), # move B to C's initial position
('r', a[0], b[1]-c[1]), # move A and C to B's and A's initial positions
)
return tuple((d, i, a) for (d, i, a) in seq if a != 0)
def check_3cycles(rows=5, cols=6):
coordinates = ((r, c) for r in range(rows) for c in range(cols))
for (a, b, c) in itertools.permutations(coordinates, 3):
board = [[(r, c) for c in range(cols)] for r in range(rows)]
seq = get_3cycle_move_sequence(rows, cols, a, b, c)
apply_move_sequence(board, seq)
if board[a[0]][a[1]] != c or board[b[0]][b[1]] != a or board[c[0]][c[1]] != b:
prettyprint(board)
print(a, b, c)
return False
return True
def get_2_2cycle_move_sequence(rows, cols, a, b, c, d):
"""
Swap a <-> b and c <-> d by using two 3-cycles.
Maximum move count:
3/2 (||a-b|| + ||c-d|| + 2||a-c|| + ||b-c|| + ||a-d||)
<= 3||a-b|| + 3||c-d|| + 6||a-c||
"""
return get_3cycle_move_sequence(rows, cols, a, b, c) + get_3cycle_move_sequence(rows, cols, a, d, c)
def check_2_2cycles(rows=5, cols=5):
coordinates = ((r, c) for r in range(rows) for c in range(cols))
for (a, b, c, d) in itertools.permutations(coordinates, 4):
board = [[(r, c) for c in range(cols)] for r in range(rows)]
seq = get_2_2cycle_move_sequence(rows, cols, a, b, c, d)
apply_move_sequence(board, seq)
if board[a[0]][a[1]] != b or board[b[0]][b[1]] != a or board[c[0]][c[1]] != d or board[d[0]][d[1]] != c:
prettyprint(board)
print(a, b, c, d)
return False
return True
def get_uniform_swaps_move_sequence(rows, cols, swaps):
"""
Assume the displacement for each swap is equal.
If there is an even number of swaps, we pair them up and apply them one by one.
If there is an odd number of swaps, we pair up the first swap with ((0,0), (0,1)), and pair up
the rest as usual.
Naively applying the swaps leads to O(max(rows,cols)) moves per swap and O(max(rows,cols)*N) for
the whole thing, so we use O(N) setup moves to force most swaps (except possibly the first one)
to be of displacement (1, 1) (i.e. each swap is of a piece and the one to its bottom-right). As
long as we pair up the swaps in a reasonable manner (e.g. raster scan (= lexicographic order) or
serpentine scan), we can do all of the swaps in O(N) moves.
If rows = cols, then the shearing procedure used here will convert every swap to a (1,1) swap,
but in general there can be either O(rows) swaps of distance O(cols), or O(cols) swaps of
distance O(rows), because of boundary-related weirdness. We handle all of the (1,1) swaps first,
then repeat the shearing procedure to convert the stragglers to (1,1) swaps as well.
(We could also do minimum-weight matchings, but the algorithms for that are kinda non-trivial
and it's not super important anyway.)
Maximum move count:
Initial swap to handle parity:
At most 4 + 4.5*(rows+cols) moves.
The swaps that get set up to (1,1) displacement:
At most N/4 pairs of swaps, each taking at most 12 + 6*dist moves where sum(dist) <= N.
This gives (N/4) * 12 + 6 * N <= 9 * N.
The remaining swaps:
All such swaps are either in the leftmost and rightmost columns, or in the top and bottom rows.
This leaves at most max(rows, cols)/2 pairs of swaps, each taking at most 12 + 6*dist' moves
where sum(dist') <= max(rows, cols). This gives max(rows, cols)/2 * 12 + 6 * max(rows, cols)
<= 12 * max(rows, cols).
Setup moves:
Each row is moved by at most cols/2 and each column is moved by at most rows/2, for a total of N
moves. (The setup moves also have to be undone at the end, so this really contributes 2*N.)
Adding everything together: 3 + 4.5*(rows+cols) + 9*N + 12*max(rows, cols) + 2*N
= 3 + 4.5*rows + 4.5*cols + 12*max(rows, cols) + 11*N
"""
if len(swaps) == 0:
return ()
seq = []
if len(swaps) % 2 == 1:
# if we have an odd number of swaps, combine the first swap with a swap of (0,1);
# this is not necessarily uniform, but it doesn't matter because we do this at most once.
# this costs <= 3 + 4.5*rows + 4.5*cols moves.
seq.extend(get_2_2cycle_move_sequence(rows, cols, (0, 0), (0, 1), *swaps[0]))
swaps = swaps[1:]
if len(swaps) == 0:
return tuple(seq)
# the displacement of each swap
dr, dc = swaps[0][1][0]-swaps[0][0][0], swaps[0][1][1]-swaps[0][0][1]
#print(dr, dc)
setup_moves = []
swaps = [(list(a), list(b)) for (a, b) in swaps]
if dr != 0:
# the swaps are not purely horizontal
if dc != 1:
block_size = abs(dr)
adjust = 1 - dc
# shear the whole board along blocks of rows to make it so that the horizontal
# displacement is +1 for every swap (without affecting vertical displacement)
for row_base in range(0, rows, block_size):
shift_amount = ((row_base // block_size) * adjust) % cols
for row_index in range(row_base, min(rows, row_base+block_size)):
setup_moves.append(('r', row_index, shift_amount))
for swap in swaps:
for coords in swap:
coords[1] += (coords[0] // block_size) * adjust
coords[1] %= cols
assert (swap[1][1] - swap[0][1]) % cols == 1
if dr != 1:
# then shear along columns to make it so that the vertical displacement is +1, except
# possibly for the swaps that wrap around horizontally.
for col_index in range(cols):
setup_moves.append(('c', col_index, col_index*(1-dr)))
for swap in swaps:
for coords in swap:
coords[0] += coords[1]*(1-dr)
coords[0] %= rows
if swap[1][1] != 0:
# check if the swap straddles the left/right border; if it does, then the
# following assert can fail so we ignore that.
assert (swap[1][0] - swap[0][0]) % rows == 1
else:
# otherwise, the swaps are horizontal; essentially just do the above but transposed
block_size = abs(dc)
adjust = 1 # 1-dr = 1 since dr = 0
# shear along blocks of columns
for col_base in range(0, cols, block_size):
shift_amount = ((col_base // block_size) * adjust) % rows
for col_index in range(col_base, min(col_base+block_size, cols)):
setup_moves.append(('c', col_index, shift_amount))
for swap in swaps:
for coords in swap:
coords[0] += (coords[1] // block_size) * adjust
coords[0] %= rows
assert (swap[1][0] - swap[0][0]) % rows == 1
if dc != 1:
# then shear along rows
for row_index in range(rows):
setup_moves.append(('r', row_index, row_index*(1-dc)))
for swap in swaps:
for coords in swap:
coords[1] += coords[0]*(1-dc)
coords[1] %= cols
if swap[1][0] != 0:
assert (swap[1][1] - swap[0][1]) % cols == 1
seq.extend(setup_moves)
#print(setup_moves)
swaps_11 = [(a, b) for (a, b) in swaps if (b[0]-a[0])%rows == (b[1]-a[1])%cols == 1]
swaps_rest = [(a, b) for (a, b) in swaps if not ((b[0]-a[0])%rows == (b[1]-a[1])%cols == 1)]
if len(swaps_11) % 2 == 1:
# if we have an odd number of exceptional swaps (which also means an odd number of (1,1)
# swaps), then we pull one out from each list and apply those swaps first, then pair up
# the rest.
# this costs <= 8 + 3*(rows+cols)
seq.extend(get_2_2cycle_move_sequence(rows, cols, *(swaps_11[-1] + swaps_rest[-1])))
swaps_11 = swaps_11[:-1]
swaps_rest = swaps_rest[:-1]
# the shearing might leave the swaps in a weird order, so we just sort them to ensure that when
# we pair up the swaps, they're "not too far apart". while we can't bound the distance between
# the swaps in each pair, we can bound the *sum* of those distances if we use serpentine scan.
swaps_11.sort(key=lambda swap: (swap[0][0], swap[0][1]*(-1)**swap[0][0]))
# actually do the swaps (in pairs, because we can't just do one swap with only 3-cycles)
for (swap0, swap1) in zip(swaps_11[0::2], swaps_11[1::2]):
seq.extend(get_2_2cycle_move_sequence(rows, cols, *(swap0 + swap1)))
if len(swaps_rest) > 0:
#print(swaps_rest)
# there should be only one possible displacement among the exceptional swaps
assert len(set(((b[0]-a[0])%rows, (b[1]-a[1])%cols) for (a, b) in swaps_rest)) == 1
dr_ex = (swaps_rest[0][1][0]-swaps_rest[0][0][0])%rows
dc_ex = (swaps_rest[0][1][1]-swaps_rest[0][0][1])%cols
if dr_ex == 1:
# shear horizontally to bring horizontal displacement to +1
assert len(set(b[0] for (a, b) in swaps_rest)) == 1 # check that they're all in the same row
row_index = swaps_rest[0][1][0]
move = ('r', row_index, 1-dc_ex)
seq.append(move)
setup_moves.append(move)
else:
# dc_ex = 1
# shear vertically to bring vertical displacement to +1
assert len(set(b[1] for (a, b) in swaps_rest)) == 1 # check that they're all in the same column
col_index = swaps_rest[0][1][1]
move = ('c', col_index, 1-dr_ex)
seq.append(move)
setup_moves.append(move)
# this setup takes at most max(rows/2,cols/2) moves
swaps_rest.sort()
for (swap0, swap1) in zip(swaps_rest[0::2], swaps_rest[1::2]):
swap0[1][0] = (swap0[0][0] + 1) % rows
swap0[1][1] = (swap0[0][1] + 1) % cols
swap1[1][0] = (swap1[0][0] + 1) % rows
swap1[1][1] = (swap1[0][1] + 1) % cols
seq.extend(get_2_2cycle_move_sequence(rows, cols, *(swap0 + swap1)))
# each pair of swaps here takes at most 8+4*dist where sum(dist) < max(rows,cols)
# then undo the setup moves
seq.extend(invert_move_sequence(setup_moves))
return tuple(seq)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.