The Government has a Limited Supply of Walls

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

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!


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

Tags:

Code Golf

Recent Posts