Are you in the biggest room?

Question

Introduction

You have recently accepted a job offer at a Pretty Good Software Company. You're pretty content with the size of your office, but do you have the biggest office? Its kinda hard to tell from just eyeballing your co-workers' offices when you stop by. The only way to figure this out is to examine the blueprints for the building...

Your Task

Write a program, script, or function that takes a floor plan for your building and indicates whether your office is the largest. The floor plan is easy to read because the building is an n by n square.

The input will consist of n+1 \n-delimited lines. The first line will have the number n on it. The next n lines will be the floorplan for the building. A simple example input:

6
......
.  . .
.X . .
.  . .
.  . .
......

The rules for the floorplan are as follows:

• . (ASCII 46) Will be used to represent walls. (Space [ASCII 32]) will be used to represent open space.
• You are represented by an X (ASCII 88). You are in your office.
• The floorplan will be n lines, each with n characters.
• The building is totally surrounded by walls on all sides. This implies that the 2nd line of input (the first line of the floorplan) and the last line of input will be all .s. It also implies that the first and last characters of every floorplan line will be .s.
• An office size is defined as the sum of adjacent spaces (contiguous by moving in 4 directions, N, S, E, W, without going through a wall).
• For the purpose of office size, the X representing you counts as a (open space)
• 4 <= n <= 80

You should output whether or not your office is strictly bigger than all the other offices. The output can be anything that unambiguously signifies True or False in your programming language of choice and adheres to standard conventions of zero, null, and empty signifying False. True implies your office is strictly the biggest.

Sample output for above input:

1

Because your office is 8 square feet, and the only other office is 4 square feet.

I/O Guidelines

• The input may be read from stdin, and answer output to stdout.

Or

• The input may be a single string argument to a function, and answer be the return value of that function.

FAQ

• The entire building consists of walls and offices.
• The building is only one floor
• There is guaranteed to be an X in the input, but there are not guaranteed to be any spaces. You could have a 1x1 office and the rest of the building is walls (You have the biggest office! hooray!).

Other Example

10
..........
.   .  . .
.  .   . .
.  .   . .
. ..   . .
..       .
..........
.      X .
.        .
..........

Here there are 3 offices, your south office is rectangular, the northwest office is a triangle(ish) and the northeast office is strangely misshapen, yet bigger than yours. The output should be False.

This is a challenge to write the shortest code, happy code-golfing!

Answer 1

Ruby 2.0, 133 characters

A collaboration with @Ventero. Always a good sign when it starts breaking the syntax highlighter!

This is a recursive flood-fill solution. Reads from STDIN and outputs to STDOUT:

f=->*a{a.product([~n=$_.to_i,-1,1,n+1]){|p,d|a|=[p]if$_[p+=d]<?.}!=a ?f[*a]:a.size}
gets(p).scan(/ /){$*<<f[$`.size]}
p$*.max<f[~/X/]

See it running on Ideone.

Answer 2

GolfScript (85 bytes)

n/(~.*:N:^;{{5%[0.^(:^N]=}/]}%{{{.2$*!!{[\]$-1=.}*}*]}%zip}N*[]*0-:A{.N=A@-,2*+}$0=N=

Online demo

This has three sections:

1. An initial input transformation which produces a 2D array using 0 to represent a wall, N (the total number of cells) to represent my starting position, and a distinct number between those for each other open space.

   n/(~.*:N:^;{{5%[0.^(:^N]=}/]}%
   

2. A flood-fill.

   {{{.2$*!!{[\]$-1=.}*}*]}%zip}N*
   

3. The final counting. This uses a variant on the tip for most common element in an array, adding a tie-breaker which biases against N.

   []*0-:A{.N=A@-,2*+}$0=N=
   

Answer 3

Javascript (E6) 155 292

F=(a,n=parseInt(a)+1,x,y)=>[...a].map((t,p,b,e=0,f=p=>b[p]==' '|(b[p]=='X'&&(e=1))&&(b[p]=1,1+f(p+n)+f(p-n)+f(p+1)+f(p-1)))=>(t=f(p))&&e?y=t:t<x?0:x=t)|y>x

Ungolfed base version

F=a=>
{
  var k, max=0, my=0, k=1, t, n = parseInt(a)+1;
  [...a].forEach( 
    (e,p,b) =>
    {
       x=0;
       F=p=>
       {
          var r = 1;
          if (b[p] == 'X') x = 1;
          else if (b[p] != ' ') return 0;
          b[p] = k;
          [n,1,-n,-1].forEach(q => r+=F(q+p));
          return r;
       }
       t = F(p);
       if (t) {
          if (x) my = t;
          if (t > max) max = t;
          k++;
          console.log(b.join(''));
       }    
    }
  )
  return my >= max
}

Test

Javascript console in firefox

F('6\n......\n. . .\n.X . .\n. . .\n. . .\n......')

1

F('10\n..........\n. . . .\n. . . .\n. . . .\n. .. . .\n.. .\n..........\n. X .\n. .\n..........\n')

0

Answer 4

C#, 444 372/(342 thanks HackerCow)bytes

Rather poor score and late to the party, but seems to work. Outputs 1 when you have the single biggest office, 0 when you do not. I've not been very intricate with the golfing yet. Works by building up disjoint sets from the input (first loop), tallying the size of each set (second loop) and then looking to see if my set is the largest (third loop).

Two versions are provided, one is a compilable program tat accepts the input from the command line, the other is just a function that expects a string as input and returns an int as the result (and is just a reworked copy of the first) - it does not need any using clauses or the like, should be able to put it anywhere and it will work.

Program 372bytes:

using System;class P{static void Main(){int s=int.Parse(Console.ReadLine()),e=0,d=s*s,a=d;int[]t=new int[d],r=new int[d];Func<int,int>T=null,k=v=>t[T(v)]=t[v]>0?a:0;T=v=>t[v]!=v?T(t[v]):v;for(;a>0;)foreach(var m in Console.ReadLine()){a--;if(m!=46){t[a]=a;e=m>46?a:e;k(a+s);k(a+1);}}for(a=d;a-->2;)r[T(a)]++;for(;d-->1;)a=d!=T(e)&&r[d]>=r[T(e)]?0:a;Console.WriteLine(a);}}

Function 342bytes:

static int F(string g){var b=g.Split('\n');int s=int.Parse(b[0]),e=0,d=s*s,a=d;int[]t=new int[d],r=new int[d];System.Func<int,int>T=null,k=v=>t[T(v)]=t[v]>0?a:0;T=v=>t[v]!=v?T(t[v]):v;for(;a>0;)foreach(var m in b[a/s]){a--;if(m!=46){t[a]=a;e=m>46?a:e;k(a+s);k(a+1);}}for(a=d;a-->2;)r[T(a)]++;for(;d-->1;)a=d!=T(e)&&r[d]>=r[T(e)]?0:a;return a;

Less golfed:

using System;

class P
{
    static int F(string g)
    {
        var b=g.Split('\n');
        int s=int.Parse(b[0]),e=0,d=s*s,a=d;
        int[]t=new int[d],r=new int[d];
        System.Func<int,int>T=null,k=v=>t[T(v)]=t[v]>0?a:0;
        T=v=>t[v]!=v?T(t[v]):v;

        for(;a>0;)
            foreach(var m in b[a/s])
            {
                a--;
                if(m!=46)
                {
                    t[a]=a;
                    e=m>46?a:e;
                    k(a+s);
                    k(a+1);
                }
            }
        for(a=d;a-->2;)
            r[T(a)]++;
        for(;d-->1;)
            a=d!=T(e)&&r[d]>=r[T(e)]?0:a;
        return a;
    }

    static void Main()
    {
        /* F() test
        var s=Console.ReadLine();
        int i=int.Parse(s);
        for(;i-->0;)
        {
            s+="\n"+Console.ReadLine();
        }
        Console.WriteLine(F(s));*/


        int s=int.Parse(Console.ReadLine()),e=0,d=s*s,a=d;
        int[]t=new int[d],r=new int[d];
        Func<int,int>T=null,k=v=>t[T(v)]=t[v]>0?a:0;
        T=v=>t[v]!=v?T(t[v]):v;

        for(;a>0;)
            foreach(var m in Console.ReadLine())
            {
                a--;
                if(m!=46)
                {
                    t[a]=a;
                    e=m>46?a:e;
                    k(a+s);
                    k(a+1);
                }
            }
        for(a=d;a-->2;)
            r[T(a)]++;
        for(;d-->1;)
            a=d!=T(e)&&r[d]>=r[T(e)]?0:a;
        Console.WriteLine(a);
    }
}

Answer 5

CJam, 106 bytes

A different approach to flood fill. Although, makes it longer ...

liqN-'Xs0aer\_:L*{_A=' ={[AAL-A(]1$f=$:D1=Sc<{D2<(aer}*D0=_' ={T):T}@?A\t}*}fAT),\f{\a/,}_$W%_2<~>@@0=#0=&

Try it here

Answer 6

Python 2 - 258 bytes

r=range;h=input();m="".join(raw_input()for x in r(h))
w=len(m)/h;n=0;f=[x!='.'for x in m]
for i in r(w*h):
 if f[i]:
    a=[i];M=s=0
    while a:
     i=a.pop();s+=1;M|=m[i]=='X';f[i]=0
     for j in(i-1,i+1,i-w,i+w):a+=[[],[j]][f[j]]
    n=max(s,n)
    if M:A=s
print A==n

uses stdin for input

Note: first if is indented by a single space, other indented lines are either using a single tab char or a tab and a space.

Answer 7

J : 150 121 bytes

(({~[:($<@#:I.@,)p=1:)=([:({.@#~(=>./))/@|:@}.({.,#)/.~@,))(>./**@{.)@(((,|."1)0,.0 _1 1)&|.)^:_[(*i.@:$)2>p=:' X'i.];._2

Edit: id and comp were ridiculously complicated and slow. Now it works shifting the map 4 times, instead of scanning it with a 3x3 window using cut (;.).

Takes as argument the blueprint as string. Explained below:

    s =: 0 :0
..........
.   .  . .
.  .   . .
.  .   . .
. ..   . .
..       .
..........
.      X .
.        .
..........
)
p=:' X' i. ];._2 s                NB. 0 where space, 1 where X, 2 where wall
id=:*i.@:$2>p                     NB. Give indices (>0) to each space
comp =: (>./ * *@{.)@shift^:_@id  NB. 4 connected neighbor using shift
  shift =: ((,|."1)0,.0 _1 1)&|.  NB. generate 4 shifts
size=:|:}.({.,#)/.~ , comp        NB. compute sizes of all components
NB. (consider that wall is always the first, so ditch the wall surface with }.)
NB. is the component where X is the one with the maximal size?
i=: $<@#:I.@,                     NB. find index where argument is 1
(comp {~ i p=1:) = {.((=>./)@{: # {.) size

NB. golfed:
(({~[:($<@#:I.@,)p=1:)=([:({.@#~(=>./))/@|:@}.({.,#)/.~@,))(>./**@{.)@(((,|."1)0,.0 _1 1)&|.)^:_[(*i.@:$)2>p=:' X'i.];._2 s
0

Answer 8

Python 2 - 378 bytes

Wow. I'm out of practice.

def t(l,x,y,m,c=' '):
 if l[y][x]==c:l[y][x]=m;l=t(l,x-1,y,m);l=t(l,x+1,y,m);l=t(l,x,y-1,m);l=t(l,x,y+1,m)
 return l
def f(s):
 l=s.split('\n');r=range(int(l.pop(0)));l=map(list,l);n=1
 for y in r:
    for x in r:l=t(l,x,y,*'0X')
 for y in r:
  for x in r:
    if l[y][x]==' ':l=t(l,x,y,`n`);n+=1
 u=sum(l,[]).count;o=sorted(map(u,map(str,range(n))));return n<2or u('0')==o[-1]!=o[-2]

This is a function answer, but it pollutes the global namespace. If this is unacceptable, it can be fixed at the cost of 1 byte:

• Add a space to the beginning of line 1 (+1)
• Replace the space at the beginning of lines 2 and 3 with a tab character (+0)
• Move line 4 to the beginning (+0)

I had a whole long explanation written out, but apparently it didn't save properly and I'm not doing that again l m a o