The Government has a Limited Supply of Walls

Question

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!

Answer 1

Mathematica, 257 253 chars

d="city.txt"~Import~"Table";g=EdgeAdd[#,∞<->Tr@#&/@Position[VertexDegree@#,2|3]]&@GridGraph@d[[1,{2,1}]];{o,x,s}=Tr/@Position[Join@@d[[2;;]],#]&/@{"o","x","."};Catch@Do[If[Min[GraphDistance[VertexDelete[g,x⋃w],∞,#]&/@o]==∞,Throw@Length@w],{w,Subsets@s}]

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.

g=EdgeAdd[#,∞<->Tr@#&/@Position[VertexDegree@#,2|3]]&@GridGraph@d[[1,{2,1}]];

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}]

Answer 2

Python, 553 525 512 449 414 404 387 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'
    q.add(a)
    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:

Reads from city.txt:

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!

Answer 3

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[16][16];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[1]);w=atoi(v[2]);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

"Readable":

#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[16][16];
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[1]);
    w=atoi(v[2]);
    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

Answer 4

Groovy : 841 805 754

i=new File("city.txt").getText()
x=i[2] as int
y=i[0] 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]='!'}}
def g(m){v=[];m.eachWithIndex{t,i->if(t=='.'){n=[];n.addAll(m);n[i]='W';v<<n}};return v}

Ungolfed:

def i = new File("city.txt").getText()
x=i[2].toInteger()
y=i[0].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 = []
    t.addAll(m)
    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.addAll(m)
            newList[i]='W'
            moves << newList
        }
    }
    return moves
}

Much more golfing to come...

Returns 2E9 if no solution.

Answer 5

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?