# Make a Bit Continent

Let's imagine we have a matrix of bits (which contains at least one 1):

0 1 0 1 1 0 1 0 0 1 0
0 1 0 1 0 0 1 0 1 1 0
0 0 1 0 1 1 0 1 0 1 0
1 1 0 0 1 0 0 1 1 0 1
0 0 0 1 0 1 1 0 0 1 0


We want to set some of the bits in this matrix such that it forms a contiguous blob of 1s, in which every 1 is directly or indirectly connected to every other 1 through orthogonal movement:

0 1 1 1 1 1 1 0 0 1 0
0 1 0 1 0 0 1 0 1 1 0
0 1 1 0 1 1 1 1 0 1 0
1 1 0 0 1 0 0 1 1 1 1
0 0 0 1 1 1 1 0 0 1 0


(You can see this more clearly by searching for 1 with your browser's "find" feature.)

However, we also want to minimize the number of bits that we set.

Given a matrix (or array of arrays) of bits or booleans, return the minimum number of bits that need to be set to create a contiguous continent of 1s. It should be possible to get from one set bit in the matrix to another by only traveling in an orthogonal direction to other set bits.

This is , so the shortest valid submission (measured in bytes) wins.

## Test Cases

0 1 0 1 1 0 1 0 0 1 0
0 1 0 1 0 0 1 0 1 1 0
0 0 1 0 1 1 0 1 0 1 0
1 1 0 0 1 0 0 1 1 0 1
0 0 0 1 0 1 1 0 0 1 0
=> 6

1 0 0 0 0 0 1 0 0
1 1 0 0 1 1 1 0 0
1 1 1 0 1 1 1 1 1
0 1 0 0 0 0 0 0 0
0 0 0 0 0 1 1 1 1
0 1 0 0 0 0 1 1 0
1 0 0 0 0 0 1 0 0
=> 4

0 0 0 1 1 1 0 1 1
0 0 1 0 0 0 0 1 0
0 0 1 1 1 1 1 1 0
1 1 0 0 1 1 0 0 0
0 0 1 1 1 0 0 1 1
0 1 1 1 0 0 0 0 0
1 1 1 0 0 1 1 1 0
1 1 1 0 1 1 0 1 1
0 0 0 0 1 0 0 0 1
1 1 0 0 1 1 0 1 1
0 0 0 0 0 0 0 1 0
0 1 1 1 1 0 0 0 0
0 0 0 1 1 0 0 0 1
0 1 0 0 1 0 1 1 0
0 1 1 1 0 0 0 0 1
=> 8

1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
=> 0

• This needs a bit more explaining. What is a "contiguous blob" in a matrix? Oct 6, 2017 at 5:59
• Since the problem is known to be NP-hard it's not a good problem for fastest-algorithm. Oct 6, 2017 at 7:24
• @Peter Taylor and esolangingfruit NP-Hardness
– qqq
Dec 12, 2017 at 3:24
• In light of Peter Taylor and HyperNeutrino's comments, and the fact that the question currently has no answers, I'm changing the scoring method to code-golf. Dec 12, 2017 at 3:31
• What should we do if there's no 1 in the matrix? Dec 12, 2017 at 8:04

# C (gcc), 308 306 bytes

Function f receives (height, width, flattened array, pointer to ans), and returns answer by pointer.

If there's no 1 in the matrix, it will return 0.

#define v A[i]
N,M,K,R,C,T,i,*A;s(x,y){i=x*M+y;if(!(x<0|y<0|x>=N|y>=M|v^1))v=2,s(x,y+1),s(x,y-1),s(x+1,y),s(x-1,y);}g(i){if(C<R){if(i^K){g(i+1);if(!v)C+=v=1,g(i+1),v=0,C--;}else{T=1;for(i=0;i<K&&!v;i++);s(i/M,i%M);for(i=0;i<K;i++)T&=v^1,v=!!v;if(T)R=C;}}}f(n,m,a,b)int*a,*b;{K=R=(N=n)*(M=m),A=a;g(0);*b=R;}


Try it online!

Ungolfed:

N,M,R,C,T,i,*A; // height, width, result, recursion depth

s(x,y)
{ // depth first search: replace all 1 in the same connected component with 2
i=x*M+y;
if(!(x<0|y<0|x>=N|y>=M|A[i]^1)) { // check if out of boundary
A[i]=2;
s(x, y+1),s(x, y-1),s(x+1, y),s(x-1, y);
}
}

g(i)
{ // enumerate all posible solutions
if(C<R) {
if(i!=N*M) {
g(i+1);      // nothing change for this entry
if (!A[i]) { // set the entry to 1
C++, A[i]=1;
g(i+1);
C--, A[i]=0;
}
}
else {
T=1;
for (i=0; i<N*M && !A[i]; i++); // find first non-zero entry
s(i/M, i%M);     // replace the connected component
for (i=0; i<N*M; i++) {
T&=A[i]!=1;   // check if no other components
A[i]=!!A[i]; // change 2s back to 1
}
if (T) R=C;      // update answer
}
}
}

f(n,m,a,b)int*a,*b;{
R=(N=n)*(M=m), A=a;
g(0);
*b=R;
}


# Python 2, 611 bytes

A full program that takes a list of lists through user input. The functions I and d count the number of islands in the array. The for loop at the end enumerates through all possibilities of where you can change 0s to 1s then if there is one island left stores the number of 1s added to the list C. The minimum of that list is the minimum number of bit flips required to connect any islands. It is a very slow algorithm so it doesn't run the test cases given in under 60s (I didn't try longer) but I tried a few smaller (~5x5) test cases and it seems to be working correctly. I got the island counting algorithm from this page.

from itertools import*
def d(g,i,j,v):
v[i][j],R,C=1,[-1,1,0,0],[0,0,-1,1]
for k in range(4):
if len(g)>i+R[k]>=0<=j+C[k]<len(g[0]):
if v[i+R[k]][j+C[k]]<1and g[i+R[k]][j+C[k]]:v=d(g,i+R[k],j+C[k],v)
return v
def I(g):
w=len(g[0])
v,c=[w*[0]for r in g],0
for i in range(len(g)*w):
if v[i/w][i%w]<1and g[i/w][i%w]>0:v=d(g,i/w,i%w,v);c+=1
return c
g=input()
C=[]
for p in [list(t)for t in product([0,1],repeat=sum(r.count(0)for r in g))]:
h,G,x=0,[r[:]for r in g],len(g[0])
for i in range(x*len(G)):
if G[i/x][i%x]<1:h+=p[0];G[i/x][i%x]=p[0];del p[0]
if I(G)<2:
C.append(h)
print min(C)


Try it online!

Pregolfed version before I optimized a few things:

from itertools import*
def d(g,i,j,v):
v[i][j]=1
R=[-1,1,0,0]
C=[0,0,-1,1]
for k in range(4):
if len(g)>i+R[k]>=0<=j+C[k]<len(g[0]):
if v[i+R[k]][j+C[k]]<1:
if g[i+R[k]][j+C[k]]:
v=d(g,i+R[k],j+C[k],v)
return v
def I(g):
w=len(g[0])
v=[[0]*w for r in g]
c=0
for i in range(len(g)):
for j in range(w):
if v[i][j]<1and g[i][j]>0:
v=d(g,i,j,v)
c+=1
return c
g=input()
z=sum(r.count(0)for r in g)
f=[list(t)for t in product('01',repeat=z)]
C=[]
for p in f:
h=0
G=[r[:]for r in g]
x=len(G[0])
for i in range(x*len(G)):
exec('h+=int(p[0]);G[i/x][i%x]=int(p[0]);del p[0]'*(G[i/x][i%x]<1))
if I(G)<2:
C.append(h)
print min(C)