# Identical grids

You’re given two $$\r×c\$$ grids. Each cell contains either 0 or 1. What are the minimum number of swaps (between horizontally and vertically adjacent cell elements, no wrapping i.e no swapping between last and first element of a row) are required in the first grid for it to match the second. If the matched arrangement can never be achieved, output -1.

Constraints

$$\1 \leq r \leq 100\$$
$$\1 \leq c \leq 100 \$$

Examples

input:
00
11

01
10
output:
1

input:
00
11

01
00
output:
-1

input:
0011011

0101101
output:
2

• Also, I highly recommend using The Sandbox to get feedback on a challenge. I do think this is an interesting challenge, but you only stand to gain by posting there first, and at worst you lose a day or two. – Giuseppe Aug 19 '19 at 16:59
• What is a swap? Please define it more rigorously. – HyperNeutrino Aug 19 '19 at 17:02
• @HyperNeutrino, by swap I mean exchanging the values of two adjacent cells. – Kiara Dan Aug 19 '19 at 17:07
• Guys, cmon, this challenge is clear enough. Don't make it a clown fiesta. I don't have any problem with understanding the challenge. – Krzysztof Szewczyk Aug 19 '19 at 17:27
• Is this a question from another site? – xnor Aug 19 '19 at 19:35

# Python 3, 383 334 bytes

-6 bytes thanks to @Kevin Cruijssen

-43 bytes thanks to @Jitse

import numpy
z=len
d=lambda a,b,c,d:abs(a-c)+abs(b-d)
def g(l,m):
if z(l)==1:yield d(*l[0],*m[0])
for i in range(z(l)):
for s in g(l[1:],m[:i]+m[i+1:]):yield d(*l[0],*m[i])+s
def c(a,b):
e=a-b;k=z(a);f,*h=[],
for x in range(k*z(a[0])):w=[(x%k,x//k)];v=e[x%k][x//k];f+=w*(v>0);h+=w*(v<0)
return-1 if numpy.sum(e)else min(g(f,h))


Try it online!

Takes input as two numpy arrays.

### Explanation:

First, e=a-b determines which positions change from one grid to the other. The next line finds all of the differences and sorts them into the lists f and h. If the sum of differences is not zero, meaning there are more 1s in one grid than the other, this returns -1, or the minimum of all possible paths found by g.

This is the fun part. Essentially, in order to make this work, a 1 must move from one position to another by swapping. Therefore, the minimum number of swaps for each pair is the manhattan distance between them, found in d. g finds every possible pairing between start and end points and returns a list of the total distances between them. If there is only one start point, it returns the distance between that and the end point. Beyond that, it pairs the first start point with each end point iteratively and adds their distance to the total distance of the rest of the points, calculated recursively.

• -6 bytes with some simple golfs (removed some spaces, and changed !=0 to >0) – Kevin Cruijssen Aug 20 '19 at 7:44
• -43 bytes – Jitse Aug 20 '19 at 9:24
• If I'm understanding this correctly, does it run on O(n!)? Obviously fine for golf, but just out of curiosity do you know if there's a more efficient algorithm? – Jonah Aug 21 '19 at 2:40
• @Jonah Technically it's O(n!!) in the total number of spaces to be swapped minus 1 (1*3*5*7...). I'm nearly certain that a more efficient algorithm exists, since this is brute forcing every possible solution. – Hiatsu Aug 21 '19 at 18:12

# Python 3, 262 bytes

e=enumerate
def f(r,s):
if not r:yield 0
for i,t in e(r):yield abs(t[0]-s[0][0])+abs(t[1]-s[0][1])+min(f(r[:i]+r[i+1:],s[1:]))
def g(x,y):
z=x-y;n=len(x.T);v,*w=[],
for i,p in e(z.flat):t=[(i%n,i//n)];v+=t*(p>0);w+=t*(p<0)
return-1if z.sum()else min(f(v,w))


Try it online!