Apakah Anda di kamar terbesar?

29

pengantar

Anda baru saja menerima tawaran pekerjaan di Perusahaan Perangkat Lunak Pretty Good. Anda cukup puas dengan ukuran kantor Anda, tetapi apakah Anda memiliki kantor terbesar ? Agak sulit untuk mengatakan dari hanya melihat kantor rekan kerja Anda ketika Anda mampir. Satu-satunya cara untuk mencari tahu ini adalah dengan memeriksa cetak biru untuk bangunan ...

Tugas Anda

Tulis program, skrip, atau fungsi yang membutuhkan denah lantai untuk bangunan Anda dan tunjukkan apakah kantor Anda yang terbesar. Denah mudah dibaca karena bangunan adalah n oleh n persegi.

Input akan terdiri dari n + 1 \n -disvisi baris. Baris pertama akan memiliki nomor n di atasnya. N baris berikutnya akan menjadi denah bangunan. Contoh input sederhana:

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

Aturan untuk denah adalah sebagai berikut:

  • .(ASCII 46) Akan digunakan untuk mewakili dinding. (Spasi [ASCII 32]) akan digunakan untuk mewakili ruang terbuka.
  • Anda diwakili oleh X(ASCII 88). Anda berada di kantor Anda.
  • Denah lantai akan menjadi n baris, masing-masing dengan n karakter.
  • Bangunan ini benar-benar dikelilingi oleh dinding di semua sisi. Ini menyiratkan bahwa input baris ke-2 (baris pertama denah lantai) dan baris input terakhir adalah semua .s. Ini juga menyiratkan bahwa karakter pertama dan terakhir dari setiap garis denah akan menjadi. s.
  • Ukuran kantor didefinisikan sebagai jumlah ruang yang berdekatan (berdekatan dengan bergerak dalam 4 arah, N, S, E, W, tanpa melalui dinding).
  • Untuk keperluan ukuran kantor, X yang mewakili Anda dianggap sebagai (ruang terbuka)
  • 4 <= n <= 80

Anda harus memberi tahu apakah kantor Anda benar-benar lebih besar daripada semua kantor lainnya. Keluaran dapat berupa apa saja yang secara jelas menandakan Benar atau Salah dalam bahasa pemrograman pilihan Anda dan mematuhi konvensi standar nol, nol, dan kosong yang menandakan False. Benar menyiratkan kantor Anda benar-benar yang terbesar.

Contoh output untuk input di atas:

1

Karena kantor Anda 8 kaki persegi, dan satu-satunya kantor lainnya adalah 4 kaki persegi.

Pedoman I / O

  • Input dapat dibaca dari stdin, dan jawab output ke stdout.

Atau

  • Input mungkin berupa argumen string tunggal ke suatu fungsi, dan jawabannya adalah nilai balik dari fungsi itu.

Faq

  • Seluruh bangunan terdiri dari dinding dan kantor.
  • Bangunannya hanya satu lantai
  • Ada yang dijamin sebagai X dalam input, tetapi tidak ada spasi. Anda dapat memiliki kantor 1x1 dan sisa bangunan adalah dinding (Anda memiliki kantor terbesar! Hore!).

Contoh lain

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

Di sini ada 3 kantor, kantor selatan Anda berbentuk persegi panjang, kantor barat laut adalah segitiga (ish) dan kantor timur laut anehnya cacat, namun lebih besar dari milik Anda. Outputnya harus False.

Ini adalah tantangan untuk menulis kode terpendek, senang !

turbulencetoo
sumber
Spesifikasi masalah yang bagus, tetapi Anda dapat menambahkan jumlah maksimum yang Xdiizinkan dalam input. :)
Greg Hewgill
4
Hanya ada satu X. X adalah "kamu" dan menandakan bahwa ruangan itu adalah milikmu.
turbulencetoo

Jawaban:

11

Ruby 2.0, 133 karakter

Kolaborasi dengan @Ventero. Selalu pertanda baik ketika mulai memecah stabilo sintaks!

Ini adalah solusi pengisian banjir rekursif. Membaca dari STDIN dan output ke 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/]

Lihat itu berjalan di Ideone .

Paul Prestidge
sumber
1
Sangat bagus! Saya pikir Anda dapat menyimpan dua karakter lainnya menata ulang percikan di fsedikit: 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}. Dan koreksi saya jika saya salah, tetapi sepertinya tidak masalah jika baris pertama yang berisi panjangnya dibiarkan $_, yang akan memungkinkan Anda untuk mempersingkat penguraian input kegets$e;n=$_.to_i
Ventero
1
Ah, bahkan lebih baik. :) Satu lagi perbaikan atas edit terakhir Anda:, gets(p)seperti ptidak melakukan apa pun dan kembali niljika dipanggil tanpa argumen.
Ventero
1
Sebenarnya, saya mengambil kembali apa yang saya katakan sebelumnya. Menggunakan pengaturan percikan awal Anda, kami dapat menggunakan fakta yang productmengembalikan receiver untuk menghilangkan lsepenuhnya: f=->*a{a.product([~n,-1,1,n+1]){|p,d|a|=[p+d]if$_[p+d]<?.}!=a ?f[*a]:a.size}- sayangnya kami tidak dapat mengganti lhs dan rhs !=untuk menghilangkan spasi, karena jika tidak kedua belah pihak menunjuk ke larik yang tidak dimodifikasi.
Ventero
1
Satu peningkatan terakhir: Dengan menyalahgunakan String#scandan ARGV, menemukan kamar terbesar dapat dipersingkat sedikit: $_.scan(/ /){$*<<f[$.ukuran]}; p $ *. Maks <f [~ / X /] `
Ventero
1
Maaf telah mengganggumu lagi, tapi aku benar-benar menemukan peningkatan lain ... :) Dengan menguraikan tugas nmenjadi fsesuatu dengan [~n=$_.to_i,...], Anda kemudian dapat menggabungkan baris pertama dan ketiga menjadi gets(p).scan(...total 134 karakter.
Ventero
7

GolfScript (85 byte)

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

Demo online

Ini memiliki tiga bagian:

  1. Transformasi input awal yang menghasilkan array 2D yang digunakan 0untuk mewakili dinding, N(jumlah total sel) untuk mewakili posisi awal saya, dan angka yang berbeda di antara mereka untuk setiap ruang terbuka lainnya.

    n/(~.*:N:^;{{5%[0.^(:^N]=}/]}%
    
  2. Isi banjir.

    {{{.2$*!!{[\]$-1=.}*}*]}%zip}N*
    
  3. Penghitungan akhir. Ini menggunakan varian di ujung untuk elemen yang paling umum dalam sebuah array , menambahkan tie-breaker yang bias terhadapnya N.

    []*0-:A{.N=A@-,2*+}$0=N=
    
Peter Taylor
sumber
Terima kasih atas kiriman Anda! Sebuah CJam terjemahan: 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

Versi dasar tidak digabungkan

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
}

Uji

Konsol Javascript di 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
sumber
Yang kedua memberi 1saya juga (di Firefox 30.0)
Christoph Böhmwalder
@ HackCow Saya tidak tahu mengapa, tetapi jika Anda cat & paste dari kode pengujian saya, spasi putih dikompresi. Setiap baris harus 10 karakter.
edc65
3

C #, 444 372 / (342 terima kasih HackerCow) byte

Skor agak buruk dan terlambat ke pesta, tetapi tampaknya berhasil. Output 1 ketika Anda memiliki kantor tunggal terbesar, 0 ketika Anda tidak. Saya belum terlalu rumit dengan golf. Bekerja dengan membangun set terpisah dari input (loop pertama), menghitung ukuran setiap set (loop kedua) dan kemudian mencari untuk melihat apakah set saya adalah yang terbesar (loop ketiga).

Dua versi disediakan, satu adalah program yang dapat dikompilasi dan menerima input dari baris perintah, yang lain hanya fungsi yang mengharapkan string sebagai input dan mengembalikan int sebagai hasilnya (dan hanya salinan ulang dari yang pertama) - tidak perlu menggunakan klausa atau sejenisnya, harus bisa meletakkannya di mana saja dan itu akan berfungsi.

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

Fungsi 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;

Kurang bermain golf:

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
sumber
1
Cara saya memahaminya Anda tidak harus benar-benar menulis program kerja, fungsi sudah cukup. Jadi, jika Anda membuang semua barang sebelum Mainfungsi dan mengganti fungsi dengan, katakan int f(string s)Anda bisa menggunakan s.Split('\n')[0]alih-alih Console.ReadLine()dan mengembalikan 1atau 0. Ini akan menghemat banyak kode
Christoph Böhmwalder
@HackerCow terima kasih, saya benar-benar merindukan klausa itu! Saya akan memasukkan versi fungsi di edit saya berikutnya.
VisualMelon
2

CJam, 106 byte

Pendekatan berbeda untuk mengisi banjir. Meskipun, membuatnya lebih lama ...

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

Coba di sini

Pengoptimal
sumber
Terima kasih atas kiriman Anda. Tetapi program Anda melempar pengecualian dengan input ini: pastebin.com/v989KhWq
jimmy23013
@ user23013 diperbaiki.
Pengoptimal
Coba ini: pastebin.com/WyRESLWE
jimmy23013
2

Python 2 - 258 byte

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

menggunakan stdin untuk input

Catatan: pertama ifindentasi oleh spasi tunggal, baris indentasi lainnya menggunakan char tab tunggal atau tab dan spasi.

6502
sumber
1

J: 150 121 byte

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

Sunting : iddan compsangat rumit dan lambat. Sekarang berfungsi menggeser peta 4 kali, alih-alih memindai dengan jendela 3x3 menggunakan cut(;. ).

Dipertimbangkan sebagai cetak biru sebagai string. Dijelaskan di bawah ini:

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

Python 2 - 378 byte

Wow. Saya kehabisan latihan.

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]

Ini adalah jawaban fungsi, tetapi mencemari namespace global. Jika ini tidak dapat diterima, dapat diperbaiki dengan biaya 1 byte:

  • Tambahkan spasi ke awal baris 1 (+1)
  • Ganti spasi di awal baris 2 dan 3 dengan karakter tab (+0)
  • Pindahkan baris 4 ke awal (+0)

Saya memiliki seluruh penjelasan panjang yang ditulis, tetapi ternyata itu tidak menyelamatkan dengan benar dan saya tidak melakukan itu lagi lmao

monmon bawah tanah
sumber