9
\$\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\$
13
  • 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, 2019 at 16:59
  • 2
    \$\begingroup\$ What is a swap? Please define it more rigorously. \$\endgroup\$
    – hyper-neutrino
    Aug 19, 2019 at 17:02
  • 2
    \$\begingroup\$ @HyperNeutrino, by swap I mean exchanging the values of two adjacent cells. \$\endgroup\$
    – Kiara Dan
    Aug 19, 2019 at 17:07
  • 4
    \$\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\$ Aug 19, 2019 at 17:27
  • 2
    \$\begingroup\$ Is this a question from another site? \$\endgroup\$
    – xnor
    Aug 19, 2019 at 19:35

3 Answers 3

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\$
4
  • 1
    \$\begingroup\$ -6 bytes with some simple golfs (removed some spaces, and changed !=0 to >0) \$\endgroup\$ Aug 20, 2019 at 7:44
  • \$\begingroup\$ -43 bytes \$\endgroup\$
    – Jitse
    Aug 20, 2019 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, 2019 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, 2019 at 18:12
4
+200
\$\begingroup\$

APL (Dyalog Extended), 35 bytes

{⍺≠⍥≢⍵:¯1⋄⌊/⍺[⌂pmat≢⍺]+.(1⊥∘|-)⍵}⍥⍸

Try it online!

A function that takes two Boolean matrices as left and right arguments.

Uses Hiatsu's algorithm. One additional thing to point out is that, while moving a 1 from some position to another, it may freely step over some ones and still take the same steps. Therefore, the pairwise Manhattan distances can be summed without interfering each other. (This doesn't invalidate the previous answers; rather, it covers a hole in the proof that the algorithm is indeed correct.)

Moving the one at the start to the end:
1 0 0 0 0 1 1 1 0 0 0
^------->              Move the 1 four steps forward
0 0 0 0 1 1 1 1 0 0 0
        <-------^      Move the 0 four steps backwards
0 0 0 0 0 1 1 1 1 0 0  (See that the target 1 has moved 4 steps forward as net effect)
                ^--->  Finally move the 1 to the destination
0 0 0 0 0 1 1 1 0 0 1
So the 1 has travelled the distance of 10 in 10 steps, stepping over ones

How it works: the code

{⍺≠⍥≢⍵:¯1⋄⌊/⍺[⌂pmat≢⍺]+.(1⊥∘|-)⍵}⍥⍸  ⍝ Main function
{                               }⍥⍸  ⍝ Extract coordinates of ones from both args
 ⍺≠⍥≢⍵:     ⍝ If the lengths (count of ones) do not match,
       ¯1   ⍝ Return minus 1
         ⋄  ⍝ Otherwise,
            ⍺[⌂pmat≢⍺]            ⍝ All permutations of coordinates of left arg
                      +.(1⊥∘|-)⍵  ⍝ Inner product with ⍵ to get Manhattan distance sum:
                        (1⊥∘|-)   ⍝ sum the absolute differences of coords point-wise
                      +.          ⍝ and sum all the distances
          ⌊/                      ⍝ Pick the minimum value
\$\endgroup\$
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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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