Você está na sala maior?

29

Introdução

Você aceitou recentemente uma oferta de emprego em uma empresa de software bastante boa. Você está bastante satisfeito com o tamanho do seu escritório, mas você tem o maior escritório? É meio difícil dizer apenas observando os escritórios de seus colegas de trabalho quando você passa por aqui. A única maneira de descobrir isso é examinar as plantas do edifício ...

Sua tarefa

Escreva um programa, script ou função que tenha uma planta baixa do seu prédio e indique se o seu escritório é o maior. O piso plano é fácil de ler porque o edifício é um n por n quadrado.

A entrada consistirá em linhas delimitadas por n + 1 \n . A primeira linha terá o número n . As próximas n linhas serão a planta baixa do edifício. Um exemplo simples de entrada:

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

As regras para a planta baixa são as seguintes:

  • .(ASCII 46) Será usado para representar paredes. (Espaço [ASCII 32]) será usado para representar o espaço aberto.
  • Você é representado por um X (ASCII 88). Você está no seu escritório.
  • A planta terá n linhas, cada uma com n caracteres.
  • O edifício é totalmente cercado por paredes por todos os lados. Isso implica que a segunda linha de entrada (a primeira linha da planta baixa) e a última linha de entrada serão todas. s. Isso também implica que o primeiro e o último caracteres de cada linha da planta baixa serão .s.
  • Um tamanho de escritório é definido como a soma dos espaços adjacentes (contíguos, movendo-se em 4 direções, N, S, E, W, sem passar por uma parede).
  • Para fins de tamanho de escritório, o X representando você conta como um (espaço aberto)
  • 4 <= n <= 80

Você deve imprimir se seu escritório é estritamente maior que todos os outros escritórios. A saída pode ser qualquer coisa que signifique inequivocamente Verdadeiro ou Falso na sua linguagem de programação preferida e adira às convenções padrão de zero, nulo e vazio, significando Falso. Verdadeiro implica que seu escritório é estritamente o maior.

Saída de amostra para a entrada acima:

1

Porque o seu escritório mede 8 pés quadrados e o único outro escritório mede 4 pés quadrados.

Diretrizes de E / S

  • A entrada pode ser lida em stdin e responder a saída em stdout.

Ou

  • A entrada pode ser um argumento de cadeia única para uma função e resposta é o valor de retorno dessa função.

Perguntas frequentes

  • Todo o edifício é composto por paredes e escritórios.
  • O edifício é apenas um andar
  • É garantido que haja um X na entrada, mas não há espaços garantidos. Você pode ter um escritório 1x1 e o restante do edifício é de paredes (você tem o maior escritório! Viva!).

Outro exemplo

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

Aqui existem três escritórios, seu escritório sul é retangular, o escritório noroeste é um triângulo (ish) e o escritório nordeste é estranhamente deformado, mas maior que o seu. A saída deve ser falsa.

Este é um desafio para escrever o código mais curto, feliz !

turbulencetoo
fonte
Boa especificação do problema, mas você pode adicionar o número máximo Xpermitido na entrada. :)
Greg Hewgill
4
Há apenas um X. O X é "você" e significa que a sala em que se encontra é sua.
turbulencetoo

Respostas:

11

Ruby 2.0, 133 caracteres

Uma colaboração com @Ventero. Sempre um bom sinal quando começa a quebrar o marcador de sintaxe!

Esta é uma solução recursiva de preenchimento de inundação. Lê de STDIN e sai para 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/]

Veja-o rodando no Ideone .

Paul Prestidge
fonte
11
Muito agradável! Eu acho que você pode economizar mais dois personagens, reorganizando os splats em fum pouco: 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}. E me corrija se eu estiver errado, mas parece que ele realmente não importa se a primeira linha contendo o comprimento é deixado no $_, que lhe permitiria encurtar a análise de entrada paragets$e;n=$_.to_i
Ventero
11
Ah, melhor ainda. :) Mais uma melhoria em sua última edição:, assim gets(p)como pnada e retorna nilse chamado sem argumento.
Ventero
11
Na verdade, retiro o que disse anteriormente. Usando seu arranjo inicial de splat, podemos usar o fato de productretornar o receptor para eliminar lcompletamente: f=->*a{a.product([~n,-1,1,n+1]){|p,d|a|=[p+d]if$_[p+d]<?.}!=a ?f[*a]:a.size}- infelizmente não podemos mudar o lhs e o rhs !=para remover o espaço, caso contrário os dois lados apontam para o array não modificado.
Ventero
11
Uma última melhoria: ao abusar String#scane ARGV, encontrar a maior sala pode ser reduzido um pouco: $_.scan(/ /){$*<<f[$.size]}; p $ *. Max <f [~ / X /] `#
#
11
Desculpe por incomodá-lo novamente, mas na verdade encontrei outra melhoria ... :) Ao incluir a tarefa nem fcom algo como [~n=$_.to_i,...], você pode combinar a primeira e a terceira linha em gets(p).scan(...um total de 134 caracteres.
Ventero
7

GolfScript (85 bytes)

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

Demonstração online

Isso tem três seções:

  1. Uma transformação de entrada inicial que produz uma matriz 2D usando 0para representar uma parede N(o número total de células) para representar minha posição inicial e um número distinto entre os espaços um do outro.

    n/(~.*:N:^;{{5%[0.^(:^N]=}/]}%
    
  2. Uma inundação.

    {{{.2$*!!{[\]$-1=.}*}*]}%zip}N*
    
  3. A contagem final. Isso usa uma variante na ponta para o elemento mais comum em uma matriz , adicionando um desempatador contra o qual se inclina N.

    []*0-:A{.N=A@-,2*+}$0=N=
    
Peter Taylor
fonte
Obrigado por se inscrever! A CJam tradução: qN/(~_*:T:U;{[{i5%[0_U(:UT] =}/]}%{{[{_2$*!!{[\]$W=_}*}*]}%z}T*:+0-:A{_T=A@-,2*+}$0=T=.
jimmy23013
3

Javascript (E6) 155292

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

Versão base ungolfed

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
}

Teste

Console Javascript no 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
edc65
fonte
O segundo 1também é
válido
@ HackerCow Não sei por que, mas se você colar e colar no meu código de teste, os espaços em branco serão compactados. Cada linha deve ter 10 caracteres.
Edc65
3

C #, 444 372 / (342 graças HackerCow) bytes

Pontuação bastante pobre e atrasado para a festa, mas parece funcionar. Produz 1 quando você tem o maior escritório único, 0 quando não possui. Ainda não fui muito complicado com o golfe. Funciona criando conjuntos disjuntos a partir da entrada (primeiro loop), calculando o tamanho de cada conjunto (segundo loop) e procurando ver se meu conjunto é o maior (terceiro loop).

São fornecidas duas versões, uma é um programa compilável que aceita a entrada da linha de comando, a outra é apenas uma função que espera uma string como entrada e retorna um int como resultado (e é apenas uma cópia retrabalhada da primeira) - ele não precisa de cláusulas de uso ou similares, deve poder colocá-lo em qualquer lugar e funcionará.

Programa 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);}}

Função 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;

Menos golfe:

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);
    }
}
VisualMelon
fonte
11
Do jeito que eu entendi, você não precisa escrever um programa de trabalho, uma função é suficiente. Portanto, se você soltar todas as coisas antes da Mainfunção e substituí-la por, diga que int f(string s)você poderia usar em s.Split('\n')[0]vez de Console.ReadLine()e retornar 1ou 0. Isso deve economizar muito código
Christoph Böhmwalder
@HackerCow obrigado, perdi completamente essa cláusula! Vou colocar uma versão da função na minha próxima edição.
VisualMelon
2

CJam, 106 bytes

Uma abordagem diferente para preenchimento de inundação. Embora, torna mais longo ...

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

Experimente aqui

Optimizer
fonte
Obrigado por se inscrever. Mas seu programa lança uma exceção com esta entrada: pastebin.com/v989KhWq
jimmy23013
@ user23013 corrigido.
Otimizador
Tente estas: pastebin.com/WyRESLWE
jimmy23013
2

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

usa stdin para entrada

Nota: primeiro ifé recuado por um único espaço, outras linhas recuadas estão usando um único caractere de tabulação ou uma tabulação e um espaço.

6502
fonte
1

J: 150 121 bytes

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

Edit : ide comperam ridiculamente complicados e lentos. Agora ele funciona deslocando o mapa 4 vezes, em vez de digitalizá-lo com uma janela 3x3 usando cut( ;.).

Toma como argumento o blueprint como string. Explicado abaixo:

    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
jpjacobs
fonte
0

Python 2 - 378 bytes

Uau. Estou sem prática.

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]

Esta é uma resposta de função, mas polui o espaço para nome global. Se isso for inaceitável, poderá ser corrigido ao custo de 1 byte:

  • Adicione um espaço ao início da linha 1 (+1)
  • Substitua o espaço no início das linhas 2 e 3 por um caractere de tabulação (+0)
  • Mova a linha 4 para o início (+0)

Eu tinha uma explicação longa e extensa, mas aparentemente ela não foi salva corretamente e não vou fazer isso de novo.

undergroundmonorail
fonte