11
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Related. \$\endgroup\$ – Stewie Griffin Apr 10 '18 at 9:00
  • \$\begingroup\$ Damnit, Stewie, now I've got "Jack Sparrow" stuck in my head again! \$\endgroup\$ – Shaggy Apr 10 '18 at 10:21
  • \$\begingroup\$ This problem is equivalent to the vertex cover problem on bipartite graph, and according to Wikipedia it can be solved in polynomial time. \$\endgroup\$ – user202729 Apr 10 '18 at 11:13
  • \$\begingroup\$ I changed my mind... it may be weighted. Anyway for sufficiently large square matrix it's (hopefully) equivalent. So if your algorithm is "too simple", be careful. \$\endgroup\$ – user202729 Apr 10 '18 at 15:40
  • \$\begingroup\$ I think I have a polynomial time algorithm. \$\endgroup\$ – user202729 Apr 13 '18 at 16:31
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ I think the first [:] can be removed without affecting the output. \$\endgroup\$ – user202729 Apr 11 '18 at 12:10
  • \$\begingroup\$ @user202729, Thanks, I think it can. I'd changed it in the meantime though :) \$\endgroup\$ – TFeld Apr 11 '18 at 12:45

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.