The Lonely Islands

Question

Input:

A 2D array containing two distinct (optional) values. I'll use 0 and 1 when explaining the rules. The input format is of course flexible.

---

Challenge:

Zeros are water, and ones are islands. In order to ensure loneliness, your task is to surround all islands with water by inserting rows and columns of zeros. You don't want to waste water, so you must minimize the amount of water added. In case there are more than one solution that requires the same amount of water added, then you should add columns of water, not rows. I'll show this in the test cases.

---

Output:

The new, modified 2D array. The output format is of course flexible.

---

Test cases:

Input and output are separated by dashes. Added zeros are shown in bold font. Use one of the answers here if you want to convert the test cases to more convenient formats.

1
---
1

---

1 1
---
1 0 1

---

1 1
1 1
---
1 0 1
0 0 0
1 0 1

---

1 0
0 1
---
1 0 0
0 0 1

Note that we added a column of zeros, not a row of zeros. This is because the number of necessary zeros is equal, and columns should be preferred.

---

1 0 0 0 1
0 1 0 1 0
0 0 1 0 0
0 1 0 1 0
---
1 0 0 0 1
0 0 0 0 0
0 1 0 1 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 1 0 1 0

Note that we added rows, not columns, since that requires the least amount of extra zeros.

---

0 0 1 0 0
0 1 1 1 0
---
0 0 0 1 0 0 0
0 0 0 0 0 0 0
0 1 0 1 0 1 0

This required both columns and a row.

---

0 0 1 0 0
0 1 0 1 0
---
0 0 0 1 0 0 0
0 1 0 0 0 1 0

Better to add two columns than one row, since it requires less water.

---

0 0
1 0
0 1
1 0
0 0
---
0 0 
1 0
0 0 
0 1 
0 0 
1 0
0 0

Better to add two rows than one column, since it requires less water.

Answer 1

Python 2, 374 346 340 339 323 317 bytes

R=range;L=len
def f(a):
 w,h=L(a[0]),L(a);W=[]
 for i in R(2**w):
	A=zip(*a)
	for c in R(w):A[-c:-c]=[[0]*h]*(i&1<<c>0)
	for j in R(2**h):
	 B=zip(*A);x=L(B[0])
	 for r in R(h):B[-r:-r]=[(0,)*x]*(j&1<<r>0)
	 y=L(B);W+=[(w*h-x*y,x,B)]*all(sum(B[i][j:j+2]+B[i+1][j:j+2])<2for i in R(y-1)for j in R(x))
 return max(W)[2]

Try it online!

Answer 2

Jelly, 37 bytes

ṫƤ-S€ZƊ⁺FỊẠ
Z_,,WƲ€ŒpẎ€Ʋ⁺€ẎLÞFL$ÞṚÇÞṪ

Try it online!

Function returning a 2D array of integers. Note that naturally in Jelly singleton list displays as its value so G is used to format the output.

---

• Link 1: Return (validity).
• Link 2: Main program.

---

The program runs in exponential time, but so-far I could not think of any polynomial time algorithm. Uses Ƥ on dyadic function, that feature postdates the challenge.