Bist du im größten Raum?

29

Einführung

Sie haben kürzlich ein Stellenangebot bei einer Pretty Good Software Company angenommen. Sie sind ziemlich zufrieden mit der Größe Ihres Büros, aber haben Sie das größte Büro? Es ist schwer zu sagen, wenn man nur die Büros seiner Kollegen ansieht, wenn man vorbeischaut. Der einzige Weg, dies herauszufinden, ist die Überprüfung der Baupläne für das Gebäude ...

Deine Aufgabe

Schreiben Sie ein Programm, ein Skript oder eine Funktion, die einen Grundriss für Ihr Gebäude erstellt und angibt, ob Ihr Büro das größte ist. Der Grundriss ist leicht zu lesen , weil das Gebäude ist eine n von n Platz.

Die Eingabe besteht aus n + 1- \n begrenzten Zeilen. In der ersten Zeile steht die Nummer n . Die nächsten n Zeilen sind der Grundriss des Gebäudes. Ein einfaches Eingabebeispiel:

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

Die Regeln für den Grundriss lauten wie folgt:

  • .(ASCII 46) Wird zur Darstellung von Wänden verwendet. (Leerzeichen [ASCII 32]) wird verwendet, um den offenen Raum darzustellen.
  • Sie werden durch ein X(ASCII 88) dargestellt. Sie sind in Ihrem Büro.
  • Der Grundriss besteht aus n Zeilen mit jeweils n Zeichen.
  • Das Gebäude ist rundum von Mauern umgeben. Dies impliziert, dass die 2. Eingabezeile (die erste Zeile des Grundrisses) und die letzte Eingabezeile alle .s sind. Dies impliziert auch, dass das erste und das letzte Zeichen jeder Grundrisslinie .s sind.
  • Eine Bürogröße ist definiert als die Summe benachbarter Räume (zusammenhängend durch Bewegen in 4 Richtungen, N, S, E, W, ohne durch eine Wand zu gehen).
  • Für die Bürogröße gilt das X, das Sie darstellt, als (offener Bereich).
  • 4 <= n <= 80

Sie sollten ausgeben, ob Ihr Büro streng größer ist als alle anderen Büros. Die Ausgabe kann alles sein, was in der Programmiersprache Ihrer Wahl eindeutig Wahr oder Falsch bedeutet und den Standardkonventionen Null, Null und Leer entspricht, was Falsch bedeutet. Richtig bedeutet, dass Ihr Büro das größte ist.

Beispielausgabe für obige Eingabe:

1

Weil Ihr Büro 8 Quadratmeter groß ist und das einzige andere Büro 4 Quadratmeter groß ist.

I / O-Richtlinien

  • Die Eingabe kann von stdin gelesen und die Ausgabe auf stdout beantwortet werden.

Oder

  • Die Eingabe kann ein einzelnes Zeichenfolgenargument für eine Funktion sein und answer der Rückgabewert dieser Funktion.

FAQ

  • Das gesamte Gebäude besteht aus Mauern und Büros.
  • Das Gebäude ist nur eine Etage
  • In der Eingabe ist ein X garantiert, es sind jedoch keine Leerzeichen garantiert. Sie könnten ein 1x1 Büro haben und der Rest des Gebäudes sind Wände (Sie haben das größte Büro! Hurra!).

Anderes Beispiel

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

Hier gibt es 3 Büros, Ihr Südbüro ist rechteckig, das Nordwestbüro ist ein Dreieck (ish) und das Nordostbüro ist merkwürdig unförmig, aber größer als deins. Die Ausgabe sollte False sein.

Dies ist eine Herausforderung, um den kürzesten Code zu schreiben, glückliches !

turbulencetoo
quelle
Nizza Problemspezifikation, aber Sie könnten die maximale Anzahl der Xzulässigen in der Eingabe hinzufügen . :)
Greg Hewgill
4
Es gibt nur ein X. Das X ist "Sie" und bedeutet, dass der Raum, in dem es sich befindet, Ihnen gehört.
turbulencetoo

Antworten:

11

Ruby 2.0, 133 Zeichen

Eine Zusammenarbeit mit @Ventero. Immer ein gutes Zeichen, wenn es anfängt, den Syntax-Textmarker zu brechen!

Dies ist eine rekursive Flood-Fill-Lösung. Liest von STDIN und gibt an STDOUT aus:

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/]

Sehen Sie , wie es auf Ideone läuft .

Paul Prestidge
quelle
1
Sehr schön! Ich denke , man kann durch Neuanordnung des splats in zwei weitere Zeichen speichert fein 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}. Und korrigieren Sie mich, wenn ich falsch liege, aber es scheint eigentlich egal zu sein, ob die erste Zeile, die die Länge enthält, noch vorhanden ist $_, gets$e;n=$_.to_i
sodass
1
Ah, noch besser. :) Eine weitere Verbesserung gegenüber der letzten edit: gets(p)wie ptut nichts und kehrt , nilwenn ohne Argument aufgerufen.
Ventero
1
Eigentlich nehme ich zurück, was ich vorher gesagt habe. Mit Ihrer ursprünglichen Splat-Anordnung können wir die Tatsache, dass productder Empfänger zurückgegeben wird, lvollständig eliminieren : f=->*a{a.product([~n,-1,1,n+1]){|p,d|a|=[p+d]if$_[p+d]<?.}!=a ?f[*a]:a.size}- Leider können wir die Links und Rechts nicht umschalten !=, um das Leerzeichen zu entfernen, da ansonsten beide Seiten auf das unveränderte Array zeigen.
Ventero
1
Eine letzte Verbesserung: Durch Missbrauch von String#scanund ARGVkann die Suche nach dem größten Raum etwas verkürzt werden: $_.scan(/ /){$*<<f[$.size]}; p $ *. Max <f [~ / X /] `
Ventero
1
Tut mir leid, dass ich Sie wieder nervt habe, aber ich habe tatsächlich eine weitere Verbesserung gefunden ... :) Durch Inlinieren der Zuweisung zu nin fmit so etwas [~n=$_.to_i,...]können Sie dann die erste und dritte Zeile in gets(p).scan(...für insgesamt 134 Zeichen kombinieren .
Ventero
7

GolfScript (85 Bytes)

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

Online-Demo

Dies hat drei Abschnitte:

  1. Eine anfängliche Eingabetransformation, die ein 2D-Array erzeugt, mit 0dem eine Wand dargestellt wird N(die Gesamtzahl der Zellen), um meine Startposition darzustellen, und eine eindeutige Zahl zwischen diesen für den jeweils anderen offenen Raum.

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

    {{{.2$*!!{[\]$-1=.}*}*]}%zip}N*
    
  3. Die endgültige Zählung. Dies nutzt eine Variante auf der Spitze für am häufigsten verwendete Element in einem Array verwendet , wobei ein Verbindungsunterbrecher hinzugefügt wird, gegen den eine Vorspannung vorliegt N.

    []*0-:A{.N=A@-,2*+}$0=N=
    
Peter Taylor
quelle
Vielen Dank für Ihren Beitrag! Eine CJam Übersetzung: 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

Ungolfed Basisversion

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
}

Prüfung

Javascript-Konsole 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
edc65
quelle
Das zweite gibt es auch 1für mich (in Firefox
30.0
@HackerCow Ich weiß nicht warum, aber wenn Sie aus meinem Testcode "cat & paste" auswählen, werden die Leerzeichen komprimiert. Jede Zeile sollte 10 Zeichen lang sein.
EDC65
3

C #, 444 372 / (342 danke HackerCow) Bytes

Ziemlich schlecht und spät zur Party, scheint aber zu funktionieren. Gibt 1 aus, wenn Sie das größte Einzelbüro haben, und 0, wenn Sie dies nicht tun. Ich war noch nicht sehr kompliziert mit dem Golfen. Bildet disjunkte Mengen aus der Eingabe (erste Schleife), zählt die Größe jeder Menge (zweite Schleife) und prüft dann, ob meine Menge die größte ist (dritte Schleife).

Es werden zwei Versionen bereitgestellt, eine ist ein kompilierbares Programm, das die Eingabe von der Befehlszeile akzeptiert, die andere ist nur eine Funktion, die eine Zeichenfolge als Eingabe erwartet und ein int als Ergebnis zurückgibt (und nur eine überarbeitete Kopie der ersten ist). es braucht keine using-Klauseln oder ähnliches, sollte es irgendwo ablegen können und es wird funktionieren.

Programm 372 Bytes :

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

Funktion 342 Bytes :

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;

Weniger golfen:

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
quelle
1
So wie ich es verstanden habe, muss man eigentlich kein Arbeitsprogramm schreiben, eine Funktion reicht aus. Wenn Sie also das gesamte Zeug vor der MainFunktion ablegen und die Funktion durch ersetzen, sagen int f(string s)Sie , Sie könnten s.Split('\n')[0]anstelle von Console.ReadLine()und return 1oder verwenden 0. Dies sollte Ihnen viel Code sparen
Christoph Böhmwalder
@HackerCow danke, ich habe diese Klausel komplett verpasst! Ich werde bei meiner nächsten Bearbeitung eine Funktionsversion einfügen.
VisualMelon
2

CJam, 106 Bytes

Ein anderer Ansatz zum Füllen von Fluten. Obwohl, macht es länger ...

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

Probieren Sie es hier aus

Optimierer
quelle
Vielen Dank für Ihren Beitrag. Aber Ihr Programm löst eine Ausnahme mit diesem Eingang: pastebin.com/v989KhWq
jimmy23013
@ user23013 behoben.
Optimierer
Versuchen Sie diese: 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

Verwendet stdin für die Eingabe

Hinweis: Zunächst ifwird ein einzelnes Leerzeichen eingerückt, für andere eingerückte Zeilen wird entweder ein einzelnes Tabulatorzeichen oder ein Tabulatorzeichen und ein Leerzeichen verwendet.

6502
quelle
1

J: 150 121 Bytes

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

Edit : idund compwaren lächerlich kompliziert und langsam. Jetzt können Sie die Karte viermal verschieben, anstatt sie mit cut( ;.) in einem 3x3-Fenster zu scannen .

Nimmt als Argument die Blaupause als String. Erklärt unten:

    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
quelle
0

Python 2 - 378 Bytes

Wow. Ich bin aus der Übung.

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]

Dies ist eine Funktionsantwort, die jedoch den globalen Namespace verschmutzt. Wenn dies nicht akzeptabel ist, kann es auf Kosten von 1 Byte behoben werden:

  • Fügen Sie ein Leerzeichen am Anfang von Zeile 1 ein (+1)
  • Ersetzen Sie das Leerzeichen am Anfang der Zeilen 2 und 3 durch ein Tabulatorzeichen (+0)
  • Zeile 4 an den Anfang setzen (+0)

Ich hatte eine lange Erklärung geschrieben, aber anscheinend hat sie nicht richtig gespeichert und ich mache das nicht noch einmal, lmao

untergrundbahn
quelle