29
\$\begingroup\$

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 ing!

\$\endgroup\$
  • \$\begingroup\$ Nice problem specification, but you could add the maximum number of X allowed in the input. :) \$\endgroup\$ – Greg Hewgill Jun 19 '14 at 0:25
  • 4
    \$\begingroup\$ There's only one X. The X is "you" and signifies that the room it is in is yours. \$\endgroup\$ – turbulencetoo Jun 19 '14 at 4:40
11
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Very nice! I think you can save two more characters by rearranging the splats in f a bit: f=->l{a=[*l];a.product([~n,-1,1,n+1]){|p,d|a|=[p+d]if$_[p+d]<?.};a!=l ?f[a]:l.size}. And correct me if I'm wrong, but it seems like it doesn't actually matter if the first line containing the length is left in $_, which would allow you to shorten the input parsing to gets$e;n=$_.to_i \$\endgroup\$ – Ventero Jun 19 '14 at 7:38
  • 1
    \$\begingroup\$ Ah, even better. :) One more improvement over your last edit: gets(p), as p does nothing and returns nil if called with no argument. \$\endgroup\$ – Ventero Jun 19 '14 at 7:47
  • 1
    \$\begingroup\$ Actually, I take back what I said earlier. Using your initial splat arrangement, we can use the fact that product returns the receiver to eliminate l completely: f=->*a{a.product([~n,-1,1,n+1]){|p,d|a|=[p+d]if$_[p+d]<?.}!=a ?f[*a]:a.size} - unfortunately we can't switch the lhs and rhs of != to remove the space, as otherwise both sides point to the unmodified array. \$\endgroup\$ – Ventero Jun 19 '14 at 8:18
  • 1
    \$\begingroup\$ One last improvement: By abusing String#scan and ARGV, finding the largest room can be shortened a bit: $_.scan(/ /){$*<<f[$.size]};p$*.max<f[~/X/]` \$\endgroup\$ – Ventero Jun 19 '14 at 8:30
  • 1
    \$\begingroup\$ Sorry for bugging you again, but I actually found another improvement... :) By inlining the assignment to n into f with something like [~n=$_.to_i,...], you can then combine the first and third line into gets(p).scan(... for a total of 134 characters. \$\endgroup\$ – Ventero Jun 19 '14 at 19:06
7
+100
\$\begingroup\$

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=
    
\$\endgroup\$
  • \$\begingroup\$ Thanks for your submission! A CJam translation: qN/(~_*:T:U;{[{i5%[0_U(:UT] =}/]}%{{[{_2$*!!{[\]$W=_}*}*]}%z}T*:+0-:A{_T=A@-,2*+}$0=T=. \$\endgroup\$ – jimmy23013 Oct 23 '14 at 10:59
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ The second one gives 1 for me too (in Firefox 30.0) \$\endgroup\$ – Christoph Böhmwalder Jul 21 '14 at 11:09
  • \$\begingroup\$ @HackerCow I don't know why, but if you cat & paste from my test code, the white spaces are compressed. Each lines should be 10 chars. \$\endgroup\$ – edc65 Jul 21 '14 at 12:33
3
\$\begingroup\$

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);
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ The way I understood it you don't have to actually write a working program, a function is sufficient. So if you drop all the stuff before the Main function and replace the function with, say int f(string s) you could use s.Split('\n')[0] instead of Console.ReadLine() and return 1 or 0. This should save you a lot of code \$\endgroup\$ – Christoph Böhmwalder Jul 21 '14 at 5:59
  • \$\begingroup\$ @HackerCow thanks, I completely missed that clause! I'll put a function version in my next edit. \$\endgroup\$ – VisualMelon Jul 21 '14 at 8:51
2
\$\begingroup\$

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

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

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

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.