4
\$\begingroup\$

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 
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Giuseppe Aug 19 at 16:59
  • 2
    \$\begingroup\$ What is a swap? Please define it more rigorously. \$\endgroup\$ – HyperNeutrino Aug 19 at 17:02
  • 2
    \$\begingroup\$ @HyperNeutrino, by swap I mean exchanging the values of two adjacent cells. \$\endgroup\$ – Kiara Dan Aug 19 at 17:07
  • 3
    \$\begingroup\$ Guys, cmon, this challenge is clear enough. Don't make it a clown fiesta. I don't have any problem with understanding the challenge. \$\endgroup\$ – Krzysztof Szewczyk Aug 19 at 17:27
  • 2
    \$\begingroup\$ Is this a question from another site? \$\endgroup\$ – xnor Aug 19 at 19:35
5
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ -6 bytes with some simple golfs (removed some spaces, and changed !=0 to >0) \$\endgroup\$ – Kevin Cruijssen Aug 20 at 7:44
  • \$\begingroup\$ -43 bytes \$\endgroup\$ – Jitse Aug 20 at 9:24
  • \$\begingroup\$ 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? \$\endgroup\$ – Jonah Aug 21 at 2:40
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Hiatsu Aug 21 at 18:12
1
\$\begingroup\$

Based on @Hiatsu's answer.

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.