| Bytes | Lang | Time | Link |
|---|---|---|---|
| 320 | Python3 | 250310T214044Z | Ajax1234 |
| 121 | J | 141023T115221Z | jpjacobs |
| 258 | Python 2 | 141024T122327Z | 6502 |
| 106 | CJam | 141023T135224Z | Optimize |
| 378 | Python 2 | 141023T144440Z | undergro |
| 085 | GolfScript | 141023T093052Z | Peter Ta |
| nan | C# | 140720T230151Z | VisualMe |
| 133 | Ruby 2.0 | 140619T045533Z | Paul Pre |
| nan | 140619T084719Z | edc65 |
Python3, 320 bytes
E=enumerate
def f(b):
d={}
for x,r in E(b):
for y,v in E(r):d[v]=d.get(v,[])+[(x,y)]
U={*d['X'],*d[' ']}
q,R=U,[]
while q:
v,*q=q
T,L=[v],[v]
for x,y in T:
for X,Y in[(0,1),(0,-1),(1,0),(-1,0)]:
if(N:=(x+X,y+Y))in U and N not in L:L+=[N];T+=[N]
R+=[L];q={*q}-{*L}
return{*d['X']}&{*max(R,key=len)}
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
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.
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=&
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
GolfScript (85 bytes)
n/(~.*:N:^;{{5%[0.^(:^N]=}/]}%{{{.2$*!!{[\]$-1=.}*}*]}%zip}N*[]*0-:A{.N=A@-,2*+}$0=N=
This has three sections:
An initial input transformation which produces a 2D array using
0to 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]=}/]}%A flood-fill.
{{{.2$*!!{[\]$-1=.}*}*]}%zip}N*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=
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);
}
}
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.
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