Czy jesteś w największym pokoju?

29

Wprowadzenie

Niedawno zaakceptowałeś ofertę pracy w Pretty Good Software Company. Jesteś całkiem zadowolony z wielkości swojego biura, ale czy masz największe biuro? Trudno to odróżnić od spojrzenia na biura współpracowników, kiedy wpadniesz. Jedynym sposobem na rozwiązanie tego problemu jest sprawdzenie planów budynku ...

Twoje zadanie

Napisz program, skrypt lub funkcję, która bierze plan piętra dla twojego budynku i wskazuje, czy twoje biuro jest największe. Plan piętra jest łatwy do odczytania, ponieważ budynek ma kwadrat n na n .

Dane wejściowe będą składały się z n + 1 \n -niepełnionych linii. Pierwszy wiersz będzie miał na sobie liczbę n . Kolejne n wierszy będzie planem budynku. Prosty przykładowy wpis:

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

Zasady dotyczące planu piętra są następujące:

  • .(ASCII 46) Będzie używany do reprezentowania ścian. (Spacja [ASCII 32]) zostanie użyta do przedstawienia otwartej przestrzeni.
  • Jesteś reprezentowany przez X(ASCII 88). Jesteś w swoim biurze
  • Plansem będzie n linii, każda z n znakami.
  • Budynek jest całkowicie otoczony ścianami ze wszystkich stron. Oznacza to, że drugi wiersz danych wejściowych (pierwszy wiersz planu piętra) i ostatni wiersz danych wejściowych będą .s. Oznacza to również, że pierwszymi i ostatnimi znakami każdej linii planu piętra będą litery .s.
  • Wielkość biura jest definiowana jako suma sąsiadujących ze sobą przestrzeni (sąsiadujących, przesuwając się w 4 kierunkach, N, S, E, W, bez przechodzenia przez ścianę).
  • Dla celów wielkości biura X reprezentujący cię liczy się jako (otwarta przestrzeń)
  • 4 <= n <= 80

Powinieneś wypisać, czy twoje biuro jest ściśle większe niż wszystkie inne biura. Wynikiem może być wszystko, co jednoznacznie oznacza Prawdę lub Fałsz w wybranym języku programowania i jest zgodne ze standardowymi konwencjami zero, zero i puste, oznaczające fałsz. Prawda oznacza, że ​​twoje biuro jest ściśle największe.

Przykładowe dane wyjściowe dla powyższego wejścia:

1

Ponieważ twoje biuro ma 8 stóp kwadratowych, a jedyne inne biuro ma 4 stopy kwadratowe.

Wytyczne I / O

  • Dane wejściowe można odczytać ze standardowego wejścia, a odpowiedź na standardowe wyjście.

Lub

  • Dane wejściowe mogą być argumentem pojedynczego ciągu funkcji, a odpowiedzią może być wartość zwracana przez tę funkcję.

FAQ

  • Cały budynek składa się ze ścian i biur.
  • Budynek ma tylko jedno piętro
  • Na wejściu jest gwarantowane X, ale nie ma żadnych spacji. Możesz mieć biuro 1x1, a reszta budynku to ściany (masz największe biuro! Hura!).

Inny przykład

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

Tutaj są 3 biura, twoje biuro południowe jest prostokątne, biuro północno-zachodnie to trójkąt (ish), a biuro północno-wschodnie jest dziwnie zniekształcone, ale większe niż twoje. Wynik powinien być fałszywy.

Wyzwanie polega na napisaniu najkrótszego kodu, udanej !

turbulencetoo
źródło
Dobra specyfikacja problemu, ale możesz dodać maksymalną liczbę Xdozwolonych danych wejściowych. :)
Greg Hewgill
4
Jest tylko jeden X. X jest „ty” i oznacza, że ​​pokój, w którym się znajduje, jest twój.
turbulencetoo

Odpowiedzi:

11

Ruby 2.0, 133 znaki

Współpraca z @Ventero. Zawsze dobry znak, gdy zaczyna łamać zakreślacz składni!

Jest to rekurencyjne rozwiązanie wypełniania powodzi. Odczytuje ze STDIN i wysyła do 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/]

Zobacz, jak działa na Ideone .

Paul Prestidge
źródło
1
Bardzo dobrze! Myślę, że można zaoszczędzić dwa kolejne znaki przez rozmieszczanie ikonami w fkawałku: 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}. I popraw mnie, jeśli się mylę, ale wygląda na to, że tak naprawdę nie ma znaczenia, czy pozostanie pierwszy wiersz zawierający długość $_, co pozwoliłoby ci skrócić parsowanie danych wejściowych dogets$e;n=$_.to_i
Ventero
1
Ach, nawet lepiej. :) Jeszcze jedno ulepszenie w stosunku do twojej ostatniej edycji:, gets(p)ponieważ pnic nie robi i zwraca, niljeśli zostanie wywołane bez argumentu.
Ventero,
1
Właściwie cofam to, co powiedziałem wcześniej. Korzystając z twojego początkowego ustawienia splat, możemy wykorzystać fakt, że productzwraca on odbiornik, aby lcałkowicie wyeliminować : f=->*a{a.product([~n,-1,1,n+1]){|p,d|a|=[p+d]if$_[p+d]<?.}!=a ?f[*a]:a.size}- niestety nie możemy zmienić lhs i rhs, !=aby usunąć przestrzeń, ponieważ w przeciwnym razie obie strony wskazują na niezmodyfikowaną tablicę.
Ventero,
1
Ostatnia poprawa: Nadużywając String#scani ARGVznajdując największy pokój można nieco skrócić: $_.scan(/ /){$*<<f[$.size]}; p $ *. Max <f [~ / X /] `
Ventero
1
Przepraszam, że znowu cię wkurzyłem, ale tak naprawdę znalazłem kolejne ulepszenie ... :) Wprowadzając przypisanie do nw fcoś w rodzaju [~n=$_.to_i,...], możesz następnie połączyć pierwszą i trzecią linię w gets(p).scan(...sumie w 134 znakach.
Ventero
7

GolfScript (85 bajtów)

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

Demo online

Zawiera trzy sekcje:

  1. Początkowa transformacja wejściowa, która tworzy tablicę 2D przy użyciu 0do reprezentowania ściany N(całkowitej liczby komórek) do reprezentowania mojej pozycji początkowej i wyraźnej liczby między nimi dla każdej otwartej przestrzeni.

    n/(~.*:N:^;{{5%[0.^(:^N]=}/]}%
    
  2. Wypełnienie powodziowe.

    {{{.2$*!!{[\]$-1=.}*}*]}%zip}N*
    
  3. Ostateczne liczenie. Wykorzystuje wariant na końcówce dla najbardziej powszechnego elementu w tablicy , dodając przerywacz remisu, który jest tendencyjny N.

    []*0-:A{.N=A@-,2*+}$0=N=
    
Peter Taylor
źródło
Dziękujemy za przesłanie! CJam tłumaczenie: qN/(~_*:T:U;{[{i5%[0_U(:UT] =}/]}%{{[{_2$*!!{[\]$W=_}*}*]}%z}T*:+0-:A{_T=A@-,2*+}$0=T=.
jimmy23013
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

Wersja podstawowa bez golfisty

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

Konsola JavaScript w Firefoksie

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
źródło
Drugi też 1dla mnie daje (w przeglądarce Firefox 30.0)
Christoph Böhmwalder
@HackerCow Nie wiem dlaczego, ale jeśli wybierzesz i wkleisz mój kod testowy, białe znaki zostaną skompresowane. Każda linia powinna mieć 10 znaków.
edc65
3

C #, 444 372 / (342 dzięki HackerCow) bajtów

Raczej kiepski wynik i spóźniony na imprezę, ale wydaje się, że działa. Wyjście 1, gdy masz jedno największe biuro, 0, gdy nie. Nie byłem jeszcze zbyt skomplikowany w golfa. Działa poprzez budowanie rozłącznych zestawów z wejścia (pierwsza pętla), obliczanie wielkości każdego zestawu (druga pętla), a następnie sprawdzanie, czy mój zestaw jest największy (trzecia pętla).

Dostępne są dwie wersje, jedna to program, który można skompilować, tat przyjmuje dane z wiersza poleceń, druga to tylko funkcja, która oczekuje ciągu jako danych wejściowych i zwraca wartość int jako wynik (i jest tylko przerobioną kopią pierwszej) - nie potrzebuje żadnych klauzul używających itp., powinien być w stanie umieścić go w dowolnym miejscu i będzie działać.

Program 372 bajtów :

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

Funkcja 342 bajtów :

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;

Mniej golfa:

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
źródło
1
Zrozumiałem, że tak naprawdę nie musisz pisać działającego programu, funkcja jest wystarczająca. Więc jeśli upuścisz wszystkie rzeczy przed Mainfunkcją i zamienisz funkcję na, powiedz, że int f(string s)możesz użyć s.Split('\n')[0]zamiast Console.ReadLine()i zwróć 1lub 0. To powinno zaoszczędzić sporo kodu
Christoph Böhmwalder
@ HackerCow dzięki, całkowicie przegapiłem tę klauzulę! W następnej edycji wstawię wersję funkcji.
VisualMelon,
2

CJam, 106 bajtów

Inne podejście do wypełniania powodziowego. Chociaż sprawia, że ​​dłużej ...

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

Wypróbuj tutaj

Optymalizator
źródło
Dziękujemy za przesłanie. Ale twój program zgłasza wyjątek z tym wejściem: pastebin.com/v989KhWq
jimmy23013
@ user23013 naprawiony.
Optymalizator
Spróbuj tych: pastebin.com/WyRESLWE
jimmy23013
2

Python 2 - 258 bajtów

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

używa wejściowego stdin

Uwaga: pierwsze ifjest wcięte pojedynczą spacją, inne wcięte linie albo używają pojedynczego znaku tabulacji, albo tabulacji i spacji.

6502
źródło
1

J: 150 121 bajtów

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

Edycja : idi compbyły absurdalnie skomplikowane i powolne. Teraz przesuwa mapę 4 razy, zamiast skanować ją za pomocą okna 3x3 za pomocą cut( ;.).

Bierze jako argument plan jako ciąg znaków. Wyjaśniono poniżej:

    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
źródło
0

Python 2 - 378 bajtów

Łał. Jestem poza treningiem.

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]

To jest odpowiedź funkcji, ale zanieczyszcza globalną przestrzeń nazw. Jeśli jest to nie do przyjęcia, można to naprawić kosztem 1 bajtu:

  • Dodaj spację na początku wiersza 1 (+1)
  • Zastąp spację na początku wiersza 2 i 3 znakiem tabulacji (+0)
  • Przenieś linię 4 na początek (+0)

Napisałem całe długie wyjaśnienie, ale najwyraźniej nie zapisało się to właściwie i nie robię tego ponownie, Lmao

podziemny monorail
źródło