The Government has a Limited Supply of Walls

Introduction

Knowledgeable code golfers prepared us for the doomsday flood. Areas at risk were evacuated, and the population moved to high ground.

We underestimated the flood (or perhaps there was a bug in @user12345's code). Some high-ground areas are rapidly approaching sea level. Walls must be erected in order to ensure the survival of the now densely populated encampments. Sadly, the government has a limited supply of walls.

Problem

Our doomsday scenario is described by two numbers on a single line, n and m. Following that line are n lines with m values per line, separated only by a single space. Each value will be one of four characters.

• x Impassable. Water cannot flow here. Walls cannot be erected here.
• - Unstable. Water can flow through this here. Walls cannot be erected here.
• . Stable. Water can flow through here. Walls can be erected here.
• o Encampment. Water can flow through here. If it does, everyone dies. Walls cannot be built here.

Water will flow from all edges of the map, unless the edge is impassable or a wall is constructed on the tile. Write a program that can output the minimum number of walls required to protect an encampment.

Example Input

6 7
x . . x x x x
x . . x - - x
x . x x - - x
x . o o o - .
x . o o o - .
x x x x x x x

Example Output

3

Assumptions

• Water only flows orthogonally
• Encampments only exist as one orthonagonally contiguous block per scenario
• A solution will always exist (although it may require copious amounts of walls)
• Encampments cannot be located on an edge, as the scenario would then have no solution
• 2 < n < 16
• 2 < m < 16
• Input may be provided from stdin, read from "city.txt", or accepted as a single argument

Shortest code wins!

• Would it be acceptable for the program to be correct, yet take longer than the known universe has existed to provide a solution for certain instances of the problem? – Claudiu Mar 7 '14 at 19:53
• @Claudiu I am somewhat new to Code Golf. My requirement failed to specify a time limit, so one does not exist. The burden falls to the answer to prove that a solution is correct for all instances of the problem. If you have a solution that solves some (but not all) instances in a clever/cool way, I still encourage you to post it just for fun. – Rainbolt Mar 7 '14 at 20:06
• Code golf typically does not require time restrictions. – Hosch250 Mar 7 '14 at 20:37
• Cool! Another Q: is input required to be as you specified or can we put it in another form? – Claudiu Mar 7 '14 at 21:47
• @Claudiu I can't accept anything outside of the requirements. You can, however, suggest an edit to the requirements using the edit button. Seeing as there are no answers yet, I'll probably accept the edit right away. – Rainbolt Mar 7 '14 at 21:54

Mathematica, 257 253 chars

Input is read from "city.txt".

Explanation:

Mathematica has many functions to deal with graphs.

First, I read the data from "city.txt".

d="city.txt"~Import~"Table";

Then I construct a grid graph with 'm'*'n' vertices (GridGraph@d[[1,{2,1}]]), and add to it a "vertex at infinity" which is connected to every vertex on the "edges" of the graph. This vertex is where the water flow from.

And o, x and s denote the positions of "o", "x" and "." respectively.

{o,x,s}=Tr/@Position[Join@@d[[2;;]],#]&/@{"o","x","."};

Then for any subset w of s (the subsets are sorted by length), I delete the vertices in x and w from g (VertexDelete[g,x⋃w]), and find the length of the shortest path from the "vertex at infinity" to the encampment o. If the length is infinity, then the encampment will be safe. So the length of the first such w is the minimum number of walls required to protect an encampment.

Catch@Do[If[Min[GraphDistance[VertexDelete[g,x⋃w],∞,#]&/@o]==∞,Throw@Length@w],{w,Subsets@s}]
• Nice! I figured i'd get scooped by a different approach in a different language. – Claudiu Mar 10 '14 at 15:48
• Upvoting but I would do so more proudly if you would explain your code for the rest of us. – Michael Stern Mar 10 '14 at 18:37
• Can someone vouch that this answer is correct or provide an online intepreter for "Mathematica"? Having trouble finding one. – Rainbolt Mar 10 '14 at 19:02
• @Rusher I've verified it, and it's solid. There's no online interpreter for MM, but there is a downloadable CDF document format which I and a couple others have started experimenting with to share solutions. You can also get Mathematica for free with the Raspberry Pi ARM computer, with the caveat that you're limited by the box's computing power. FWIW, we MM users do our best to keep each other honest and we're working on making our submissions more accessible (a problem also faced by Matlab, Maple, MS languages that don't work on Mono, etc.) – Jonathan Van Matre Mar 10 '14 at 22:23

C, 827 799 522

Golfed:

#define N for(
#define F(W,X,Y,Z) N i= W;i X Y;i Z)
#define C(A,B,C) if(c[A][B]==C)
#define S(W,X,Y,Z,A,B) p=1;F(W,X,Y,Z)C(A,B,120)p=0;if(p){F(W,X,Y,Z){C(A,B,46){c[A][B]='x';z++;Q();break;}}}else{F(W,X,Y,Z){C(A,B,120)break;else c[A][B]='o';}}
p,m,z,w,h,o,i,u,l,x,y;char c;Q(){N u=0;u<h;u++)N l=0;l<w;l++)if(c[u][l]=='o'){x=u;y=l;S(x,>,m,--,i,y)S(y,>,m,--,x,i)S(y,<,w,++,x,i)S(x,<,h,++,i,y)}}main(int a, char **v){h=atoi(v);w=atoi(v);N m=-1;o<h;o++)N i=0;i<w;i++)scanf("%c",&c[o][i]);Q();printf("%d",z);}

Input is given with the height and with as command line arguments, and then the grid is read as a single string on stdin like so: ./a.out 6 7 < input where input is in this form (left to right, top to bottom):

x..xxxxx..x--xx.xx--xx.ooo-.x.ooo-.xxxxxxx

#define F(W,X,Y,Z) for(i= W;i X Y;i Z)
#define C(A,B,C) if(c[A][B]==C)
#define S(W,X,Y,Z,A,B) p=1;F(W,X,Y,Z)C(A,B,120)p=0;if(p){F(W,X,Y,Z){C(A,B,46){c[A][B]='x';z++;Q();break;}}}else{F(W,X,Y,Z){C(A,B,120)break;else c[A][B]='o';}}

/*Example of an expanded "S" macro:
p=1;
for(i=x;i>m;i--) if(c[i][y]==120) p=0;
if(p)
{
for(i=x;i>m;i--)
{
if(c[i][y]==46)
{
c[i][y]='x';
z++;
Q();
break;
}
}
}
else
{
for(i= x;i > m;i --)
{
if(c[i][y]==120) break;
else c[i][y]='o';
}
}
*/

p,m,z,w,h,o,i,u,l,x,y;
char c;
Q(){
for(u=0;u<h;u++)
for(l=0;l<w;l++)
if(c[u][l]=='o')
{
x=u;y=l;
S(x,>,m,--,i,y)
S(y,>,m,--,x,i)
S(y,<,w,++,x,i)
S(x,<,h,++,i,y)
}
}

main(int a, char **v)
{
h=atoi(v);
w=atoi(v);
for(m=-1;o<h;o++)
for(i=0;i<w;i++)
scanf("%c",&c[o][i]);
P();
Q();
printf("%d\n",z);
P();
}

//Omitted in golfed version, prints the map.
P()
{
for(o=0;o<h;o++)
{
for (i=0;i<w;i++) printf("%c",c[o][i]);
printf("\n");
}
}

Nowhere near as short as the solution by @Claudiu, but it runs blazingly fast. Instead of flood filling from the edges, it finds the encampment and works outward from the 'o' tokens.

• If it encounters any unstable ground next to the encampment, it expands the encampment onto it.
• If any encampment on the grid doesn't have at least one wall in each direction, it moves in that direction until it can build a wall.
• After each new wall section is placed, it recurses to find the next wall section to place.

Sample wall placements:

x..xxxx                           x..xxxx
x..x--x                           x..xoox
x.xx--x                           x3xxoox
x.ooo-.  <-- results in this -->  xooooo1
x.ooo-.                           xooooo2
xxxxxxx                           xxxxxxx
• Oh interesting approach! Does it always give shortest answer? e.g. what answer does it give for this map? It should be 3 (marked where new walls go with @). I tried running your code myself but it didn't seem to work – Claudiu Mar 8 '14 at 21:15
• Oops, seems that golfing and alcohol don't mix very well... I golfed in some undefined behavior. Should be fixed now along with the 277 unnecessary characters. – Comintern Mar 9 '14 at 0:48
• @Claudiu - See my comment above, results for the map you posted are at pastebin.com/r9fv7tC5. This should always give the shortest answer, but I've only tested it with 10 or 15 maps that I thought might present corner cases. I'd be curious to see if anyone can identify maps that it fails for. – Comintern Mar 9 '14 at 1:09

Python, 553525512449414404387 368 characters (+4? for invocation)

I had way too much fun golfing this. It's 82 bytes bigger if you try to compress it! Now that's a measure of compactness and lack of repetition.

R=range;import itertools as I
f=map(str.split,open('city.txt'))[1:]
S=[]
def D(q):
q=set(q)
def C(*a):
r,c=a
try:p=(f[r][c],'x')[a in q]
except:p='x'
if'.'==p:S[:0]=[a]
return p<'/'and C(r+1,c)|C(r-1,c)|C(r,c+1)|C(r,c-1)or'o'==p
if sum(C(j,0)|C(j,-1)|C(0,j)|C(-1,j)for j in R(16))<1:print n;B
D(S);Z=S[:]
for n in R(len(Z)):map(D,I.combinations(Z,n))

Indentation levels are space, tab.

Usage:

6 7
x . . x x x x
x . . x - - x
x . x x - - x
x . o o o - .
x . o o o - .
x x x x x x x

Invoke as follows:

\$ python floodfill_golf.py 2>X
3

The 2>X is to hide stderr since program exits by raising an exception. If this is considered unfair feel free to add 4 characters for the invocation.

Explanation:

Simple brute force. C does a flood-fill and returns true if it hit an encampment. No extra padding since it took too much space to set the padding up properly. D, given a set of walls to fill in, calls C from every point on the edge such that C accounts for those walls, and prints length and exits if none of them reached the encampment. The list of walls is also used to keep track of the flood-fill, so no copying of the board is required! Trickily, C also appends any empty spots it finds to a list, S, so the function D is also used to first construct the list of empty spots. For this reason, I use sum instead of any, to ensure all the .s are collected on the first run-through.

I invoke D once, then copy the list of empty spots into Z since S will keep being appended to (inefficient, but cheaper on character count). Then I use itertools.combinations to select each combo of empty spots, from 0 spots up. I run each combo through D and it prints the length of the first one that works, raising an exception to exit the program. If no answer is found then nothing is printed.

Note that currently, the program doesn't work if no walls are needed. It'd be +3 characters to take care of this case; not sure if it's necessary.

Also note that this is an O(2^n) algorithm, where n is the number of empty spots. So, for a 15x15 completely empty board with one encampment in the middle, this will take 2^(15*15-1) = 2.6959947e+67 iterations to complete, which is going to be a very long time indeed!

Groovy : 841805 754

i=new File("city.txt").getText()
x=i as int
y=i as int
m=i[4..i.length()-1].replaceAll('\n','').toList()
print r(m,0)
def r(m,n){if(f(m))return n;c=2e9;g(m).each{p=r(it,n+1);if(p<c)c=p;};return c;}
def f(m){u=[];u.addAll(m);for(i in 0..(x*y)){for(l in 0..m.size()-1){n(l,u);s(l,u);e(l,u);w(l,u);}};m.count('o')==u.count('o')}
def n(i,m){q=i-x;if((((q>=0)&(m[q]=='!'))|(q<0))&m[i]!='x'&m[i]!='W'){m[i]='!'}}
def s(i,m){q=i+x;if((((q>=0)&(m[q]=='!'))|(q<0))&m[i]!='x'&m[i]!='W'){m[i]='!'}}
def e(i,m){q=i+1;if((((q%x!=0)&(m[q]=='!'))|(q%x==0))&m[i]!='x'&m[i]!='W'){m[i]='!'}}
def w(i,m){q=i-1;if((((i%x!=0)&(m[q]=='!'))|(i%x==0))&m[i]!='x'&m[i]!='W'){m[i]='!'}}

Ungolfed:

def i = new File("city.txt").getText()
x=i.toInteger()
y=i.toInteger()
def m=i[4..i.length()-1].replaceAll('\n','').toList()
println r(m, 0)

def r(m, n){
if(f(m)) return n
def c = Integer.MAX_VALUE

getAllMoves(m).each{ it ->
def r = r(it, n+1)
if(r < c) c = r
}
return c;
}

def f(m){
def t = []
for(i in 0..(x*y)){
for(l in 0..m.size()-1){
n(l,t);s(l,t);e(l,t);w(l,t);
}
}
m.count('o')==t.count('o')
}

def n(i,m){
def t = i-x;
if( ( ( (t >= 0) && (m[t]=='!') ) || (t < 0)) && m[i]!='x' && m[i]!='W'){
m[i]='!'
}
}

def s(i,m){
def t = i+x;
if( ( ( (t >= 0) && (m[t]=='!') ) || (t < 0)) && m[i]!='x' && m[i]!='W'){
m[i]='!'
}
}

def e(i,m){
def t = i+1;
if( ( ( (t%x!=0) && (m[t]=='!') ) || (t%x==0)) && m[i]!='x' && m[i]!='W'){
m[i]='!'
}
}

def w(i,m){
def t = i-1;
if( ( ( (i%x!=0) && (m[t]=='!') ) || (i%x==0)) && m[i]!='x' && m[i]!='W'){
m[i]='!'
}
}

def getAllMoves(m){
def moves = []
m.eachWithIndex { t, i ->
if(t=='.'){
def newList = []
newList[i]='W'
moves << newList
}
}
return moves
}

Much more golfing to come...

Returns 2E9 if no solution.

Dyalog APL, 91 bytes

⊃∊{1∊a[⍸×{(×d)∧s 3∨/3∨⌿⍵}⍣≡4=d←0@⍵⊢a]:⍬⋄≢⍵}¨c[⍋≢¨c←(,⍳2⊣¨b)/¨⊂b←⍸2=a←(s←(4,4,⍨⍉)⍣2)'xo.'⍳⎕]

assumes ⎕IO=0, uses features from v16.0 (@ and ), running time is exponential in the number of .-s

is evaluated input, must be a matrix of characters

'xo.'⍳ replace x with 0, o with 1, . with 2, and all others with 3

s←(4,4,⍨⍉)⍣2 a function that surrounds a matrix with 4s

a← assign the numeric matrix surrounded with 4s to a variable a

b←⍸2= b is the list of coord pairs where the 2s (i.e. the .-s) are

(,⍳2⊣¨b)/¨⊂b generate all combinations of elements of b

c[⍋≢¨c←...] sort them by size

{... :⍬⋄≢⍵}¨ for each combination, check something and return either its length or an empty list

⊃∊ the first non-empty result

d←0@⍵⊢a d is a with some elements replaced with 0

4= create boolean matrix - where are the 4s? i.e. the border we added

{...}⍣≡ keep on applying the function in {} until the result stabilizes

3∨/3∨⌿⍵ "boolean or" each element with its neighbours

s the result will be smaller, so let's re-create the border

(×d)∧ apply the non-zero elements of d (the non-walls) as a boolean mask

a[⍸× ...] what in a corresponds to the 1s in our boolean matrix?

1∊ are there any 1s, i.e. o, encampments?