Apakah struktur bata stabil?

24

Mari kita mewakili bata batu standar sebagai [__](dan mengabaikan fakta bahwa bagian atas terbuka). Ketika batu bata ini ditumpuk, setiap lapisan lainnya diimbangi dengan setengah batu bata, seperti biasa dalam konstruksi batu bata:

  [__][__][__][__]
[__][__][__][__]  
  [__][__][__][__]
[__][__][__][__]

Dengan demikian, setiap bata memiliki paling banyak enam tetangga dan tidak mungkin bagi dua batu bata untuk berbaris secara langsung.

Poin kuncinya adalah bahwa pengaturan batu bata ini tidak direkatkan , tetapi hanya disatukan oleh gravitasi. Jadi penting bahwa setiap bata dalam struktur stabil, jika tidak seluruh struktur tidak stabil.

Ada tiga cara batu bata individu menjadi stabil:

  1. Setiap bata di tanah (garis bata terendah) stabil.

  2. Batu bata yang memiliki dua batu bata tepat di bawahnya stabil:

      [__]   <- this brick is stable
[__][__] <- because these bricks hold it up

  3. Setiap bata yang memiliki bata di atas dan di bawahnya di sisi yang sama stabil:

      [__]  [__]
[__]      [__] <- these middle bricks are stable
  [__]  [__]      because the upper and lower bricks clamp them in

[__]          [__]
  [__]      [__]   <- these middle bricks are NOT stable
    [__]  [__]

Dari aturan-aturan ini kita dapat melihat, misalnya, pengaturannya

  [__][__][__][__]
[__][__][__][__]  
  [__][__][__][__]
[__][__][__][__]

tidak stabil karena batu bata kanan atas tidak stabil, hanya itu yang diperlukan.

Struktur bata hanya stabil jika semua batunya stabil.

Tantangan

Tugas Anda adalah menulis fungsi yang mengambil string struktur bata dan mengembalikan nilai kebenaran jika struktur stabil, dan nilai palsu jika tidak stabil. ( definisi benar / salah )

String input mungkin besar secara sewenang-wenang tetapi akan selalu berupa kotak karakter persegi panjang, dengan ruang yang mengisi area yang kosong dari batu bata. Lebar kisi karakter akan habis dibagi 4 tetapi ketinggiannya mungkin ganjil atau genap.

Kotak bata selalu memanjang ke atas dan ke kanan dari posisi bata kiri bawah:

         .
         .
         .
  BRK?BRK?BRK?BRK?  
BRK?BRK?BRK?BRK?BRK?
  BRK?BRK?BRK?BRK?  
BRK?BRK?BRK?BRK?BRK? . . .
  BRK?BRK?BRK?BRK?  
BRK?BRK?BRK?BRK?BRK?

Tergantung pada strukturnya, masing BRK?- masing mewakili batu bata ( [__]) atau ruang kosong (4 spasi).

Perhatikan bahwa rongga setengah bata diisi dengan ruang untuk memastikan bahwa kotak karakter adalah persegi panjang.

Mencetak gol

Kode terpendek dalam byte menang.

Catatan

  • Jika diinginkan, Anda dapat menggunakan .alih-alih ruang sebagai karakter ruang kosong.
  • String kosong dianggap stabil.
  • Jika bahasa Anda tidak memiliki fungsi, Anda dapat menggunakan variabel string bernama sebagai input dan menetapkan hasilnya ke variabel lain.
  • Jika bahasa Anda tidak memiliki string, Anda dapat melakukan apa pun yang tampaknya sesuai untuk input.

Uji Kasus

Berbagai test case, dipisahkan oleh garis kosong. Untuk kejelasan .digunakan bukan ruang untuk ruang kosong.

Stabil:

[__]

..[__]..
[__][__]

........[__]........
......[__][__]......
........[__]........

..[__][__]..
[__][__][__]
..[__][__]..
[__]....[__]

............[__]..
..[__][__][__][__]
[__][__][__][__]..
..[__][__][__][__]
[__][__][__][__]..

..[__]........[__]..
[__][__][__][__][__]
..[__][__][__][__]..
....[__][__][__]....
......[__][__]......
........[__]........

Tidak stabil:

..[__]..
........

..[__]..
[__]....

..[__]..
....[__]

..[__][__]..
[__]....[__]
..[__][__]..
[__]....[__]

..[__][__][__][__]
[__][__][__][__]..
..[__][__][__][__]
[__][__][__][__]..

[__][__][__][__][__]
..[__][__][__][__]..
....[__][__][__]....
......[__][__]......
........[__]........
code-golf ascii-art Hobi Calvin
sumber
7
Saya cukup yakin definisi stabilitas Anda tidak sesuai dengan kenyataan ;-)
John Dvorak
14
@ JanDvorak Saya tahu tetapi siapa yang ingin bermain golf seluruh mesin fisika: P
Calvin's Hobbies
........[__].... ......[__][__].. ....[__][__].... ..[__][__]...... [__][__]........ ..[__]..........(Anda harus menumpuk mental garis-garis itu di atas satu sama lain. Intinya adalah bahwa aturan Anda memungkinkan struktur yang pusat gravitasinya jauh diimbangi dari titik kontak dengan tanah. Seharusnya mungkin untuk mengencangkannya untuk menghindari hal ini. , tanpa memerlukan mesin fisika, jika Anda menginginkannya.)
Nathaniel
2
Ketepatan dalam fisika adalah sekaleng cacing. Satu dapat datang dengan banyak kasus sederhana di mana stabilitas tergantung pada koefisien gesekan dan / atau pada berat batu bata di atas.
COTO
10
"stable" ... heh
wchargin

Jawaban:

12

80386 kode mesin, 98

Kode:

60 8b f1 8b f9 b0 0a f2 ae 8b ef 2b ee b0 00 f2
ae 2b fe 83 ef 02 2b fd 72 41 03 f7 2b f5 33 c9
8a 7c 6e fc 8a 1c 6e b1 02 33 d2 8b c7 f7 f5 83
fa 02 75 03 b7 00 41 8a 66 fc 8a 06 3b fd 7d 02
33 c0 23 c3 0a c4 22 df 0b c3 f6 44 2e fe 01 74
04 d1 e8 73 06 2b f1 2b f9 73 c5 61 d1 d0 83 e0
01 c3

Kode memindai seni ASCII dari akhir hingga awal, melompati 2 karakter sekaligus. Ini melakukan dua kali pemeriksaan yang diperlukan (itu akan cukup untuk melompat 4 karakter), tetapi menyederhanakan logika.

Memeriksa dimulai pada baris karakter berikutnya-ke-terakhir (tidak perlu memeriksa baris terakhir). Di setiap baris, dimulai 3 karakter dari kanan (tidak perlu memeriksa terlalu jauh ke kanan). Untuk setiap karakter, ia memeriksa 4 karakter di sekitarnya:

A...B
..X..
C...D

Ada banyak kondisi logis untuk diperiksa:

  • Jika A dan C adalah karakter bata, X didukung
  • Jika B dan D adalah karakter bata, X didukung
  • Jika C dan D adalah karakter bata, X didukung
  • Jika X adalah karakter bata, itu harus didukung; kalau tidak strukturnya tidak stabil

Ini kebetulan kebetulan bahwa semua karakter bata [_]memiliki set LSB mereka; semua karakter lain .\nsudah jelas. Selain itu, 80.386 set instruksi memiliki ini berguna "tinggi" dan "rendah" register ( ah, al, dll), yang membantu memparalelkan cek sedikit. Jadi semua jumlah pengecekan sedikit mengotak-atik.

Saya mulai dari kode C berikut:

int check(const char* ptr)
{
    int width, result = 0, pos;

    width = strchr(ptr, '\n') - ptr + 1;
    pos = strlen(ptr) - 1 - width; // pos points to the B character
    ptr += pos - width;

    while (pos >= 0)
    {
        int a = ptr[-4];
        int c = ptr[-4 + 2 * width];
        int b = ptr[0];
        int d = ptr[0 + 2 * width];
        int ab = a << 8 | b;
        int cd = c << 8 | d;
        if (pos < width)
            ab = 0; // A and B don't exist; set them to 0
        int jump = 2; // distance to next brick
        if (pos % width == 2) // leftmost brick?
        {
            cd &= 0xff; // C doesn't exist; set it to 0
            ++jump;
        }
        int support_v = ab & cd;
        support_v = support_v | support_v >> 8; // data in LSB
        int support_h = cd & cd >> 8; // data in LSB
        int support = (support_v | support_h) & 1;
        if (!support & ptr[-2 + width])
            goto UNSTABLE;
        ptr -= jump;
        pos -= jump;
    }
    return 1;
UNSTABLE:
    return 0;
}

Saya menerjemahkan kode ke bahasa assembly (sebagian besar satu-ke-satu), termasuk implementasi golf strchrdan strlen. Kode sumber berikut diterjemahkan oleh MS Visual Studio ke kode mesin di bagian atas posting saya.

__declspec(naked) int __fastcall check(const char* ptr) // MS Visual Studio syntax
{
    _asm
    {
        pushad;

        // ecx = ptr
        mov esi, ecx; // esi = ptr
        mov edi, ecx
        mov al, 10;
        repne scasb;
        mov ebp, edi;
        sub ebp, esi; // ebp = width

        mov al, 0;
        repne scasb;
        sub edi, esi;
        sub edi, 2;
        sub edi, ebp; // edi = pos
        jc DONE;

        add esi, edi;
        sub esi, ebp;

        xor ecx, ecx; // ecx = jump

    LOOP1:
        mov bh, [esi - 4 + 2 * ebp]; // bh = C
        mov bl, [esi + 2 * ebp]; // bl = D
        // bx = CD
        mov cl, 2;
        xor edx, edx
        mov eax, edi
        div ebp;
        cmp edx, 2;
        jne LABEL2;
        mov bh, 0
        inc ecx;
    LABEL2:

        mov ah, [esi - 4]; // ah = A
        mov al, [esi]; // al = B
        // ax = AB
        cmp edi, ebp;
        jge LABEL3;
        xor eax, eax;
    LABEL3:

        and eax, ebx; // ax = support_v
        or al, ah; // al = support_v
        and bl, bh; // bl = support_h
        or eax, ebx; // eax = support
        test byte ptr[esi - 2 + ebp], 1;
        jz LABEL4; // not a brick character - nothing to check
        shr eax, 1; // shift the LSB into the carry flag
        jnc DONE;
    LABEL4:
        sub esi, ecx;
        sub edi, ecx;
        jnc LOOP1;

    DONE:
        // here, the result is in the carry flag; copy it to eax
        popad;
        rcl eax, 1;
        and eax, 1;
        ret;
    }
}
anatolyg
sumber
7

MATLAB - 119 byte

Diperkecil:

function c=S(B),f=@(m)conv2([(0&B(1,:))+46;B]+3,m,'valid');M=[2 0;-1 -1;0 2];c=isempty(B)||all(all(f(M)&f(fliplr(M))));

Diperluas:

function c = isstable( B )

f = @(m) conv2( [(0&B(1,:))+46; B] + 3, m, 'valid' );
M = [2 0;-1 -1;0 2];
c = isempty( B ) || all(all( f( M ) & f(fliplr( M )) ));

Penggunaan sampel:

S4 = [  '..[__][__]..'; ...
        '[__][__][__]'; ...
        '..[__][__]..'; ...
        '[__]....[__]'];

fprintf( 'S4: %d\n', isstable( S4 ) );

S4: 1

U4 = [  '..[__][__]..'; ...
        '[__]....[__]'; ...
        '..[__][__]..'; ...
        '[__]....[__]'];

fprintf( 'U4: %d\n', isstable( U4 ) );

U4: 0

Detail

Rutin menambahkan baris .ke atas matriks input, kemudian mengkonversi ke matriks numerik dengan menambahkan 3 ke kode karakter ASCII. Diberikan konversi ini, konvolusi 2D dengan kernel

 2  0
-1 -1
 0  2

menghasilkan matriks dengan 0di lokasi tempat pola karakter

 . *
 _ _
 * .

hadir, dengan *mewakili "karakter apa saja". Karena konstruksi kernel, ini adalah satu-satunya pola karakter yang valid yang akan menghasilkan a 0.

Konvolusi identik dilakukan dengan kernel versi kiri-kanan yang terdeteksi

 * .
 _ _
 . *

Sebuah input stabil jika i ) kosong, atau ii ) tidak ada nol muncul di kedua lilitan.

Dua frustrasi adalah

  1. Konvolusi standar MATLAB berjalan melewati tepi matriks operan, menghasilkan kesalahan 0pada sudut yang berlawanan untuk kedua konvolusi, yang membutuhkan ,'valid'(8 byte) yang ditambahkan untuk conv2memanggil untuk membatasi output ke area di mana konvolusi valid.

  2. Menangani case string kosong menambahkan 12 byte.

COTO
sumber
6

JavaScript (E6) 131 261

F=a=>
  [...a].every((e,p)=>
    !(d={']':-3,'[':3}[e])
     |a[p-r]=='_'&(x=a[p+r]!=' ')
     |a[p-r+d]=='_'&(y=a[p+r+d]!=' ')
     |x&y
  ,r=a.search(/\n/)+1)

Tes di konsol FireFox / FireBug

;['[__]', '  [__]  \n[__][__]', '        [__]        \n      [__][__]      \n        [__]        ',
 '  [__][__]  \n[__][__][__]\n  [__][__]  \n[__]    [__]',
 '            [__]  \n  [__][__][__][__]\n[__][__][__][__]  \n  [__][__][__][__]\n[__][__][__][__]  ',
 '  [__]        [__]  \n[__][__][__][__][__]\n  [__][__][__][__]  \n    [__][__][__]    \n      [__][__]      \n        [__]        ']
.forEach(x => console.log(x+'\n'+F(x)))

;['  [__]  \n        ', '  [__]  \n[__]    ' ,'  [__]  \n    [__]',
 '  [__][__]  \n[__]    [__]\n  [__][__]  \n[__]    [__]',
 '  [__][__][__][__]\n[__][__][__][__]  \n  [__][__][__][__]\n[__][__][__][__]  ',
 '[__][__][__][__][__]\n  [__][__][__][__]  \n    [__][__][__]    \n      [__][__]      \n        [__]        ']
.forEach(x => console.log(x+'\n'+F(x)))

Keluaran

    [__]
true

  [__]  
[__][__]
true

        [__]        
      [__][__]      
        [__]        
true

  [__][__]  
[__][__][__]
  [__][__]  
[__]    [__]
true

            [__]  
  [__][__][__][__]
[__][__][__][__]  
  [__][__][__][__]
[__][__][__][__]  
true

  [__]        [__]  
[__][__][__][__][__]
  [__][__][__][__]  
    [__][__][__]    
      [__][__]      
        [__]        
true

  [__]  
false

  [__]  
[__]    
false

  [__]  
    [__]
false

  [__][__]  
[__]    [__]
  [__][__]  
[__]    [__]
false

  [__][__][__][__]
[__][__][__][__]  
  [__][__][__][__]
[__][__][__][__]  
false

[__][__][__][__][__]
  [__][__][__][__]  
    [__][__][__]    
      [__][__]      
        [__]        
false

Tidak disatukan

F=a=>(
  a=a.replace(/__/g,'').replace(/  /g,'.'),
  r=a.search(/\n/)+1,
  [...a].every((e,p)=>
    e < '0' ||
    (e ==']'
    ? // stable right side
     a[p-r]=='[' & a[p+r]!='.' 
     |
     a[p-r-1]==']' & a[p+r-1]!='.' 
     |
     a[p+r]!='.' & a[p+r-1] != '.'
    : // stable left side
     a[p-r]==']' & a[p+r]!='.' 
     |
     a[p-r+1]=='[' & a[p+r+1]!='.' 
     |
     a[p+r]!='.' & a[p+r+1] != '.'
    )  
  )
)
edc65
sumber
Apa yang [...a]dilakukan, jika Anda tidak keberatan dengan pertanyaan saya? Saya tahu ES6 memungkinkan ...argsebagai argumen terakhir dari fungsi untuk menangkap variadics, tapi saya belum pernah melihatnya menggunakan cara ini.
COTO
@COTO codegolf.stackexchange.com/a/37723/21348 , gunakan case 2 (ini sangat umum, saya menggunakannya di mungkin 80% dari jawaban saya)
edc65
Sunofagun. Sama seperti {:}di MATLAB. Itu akan sangat berguna. Terima kasih. :)
COTO
1

Python 279

Saya pikir saya sangat buruk dalam tantangan kode golf dan mungkin saya menggunakan bahasa yang salah untuk itu: D Tapi saya suka kode yang dapat dengan mudah dibaca :) Btw Saya ingin melihat kode python yang menggunakan lebih sedikit byte!

def t(b):
    r=b.split()
    l=len(r[0])
    r=['.'*l]+r
    for i in range(len(r)-2,0,-1):
        r[i]+='...'
        for j in range(l):
            if(r[i][j]=='['):
                if(r[i+1][j]<>'_'or(r[i+1][j+3]<>'_'and r[i-1][j]<>'_'))and(r[i+1][j+3]<>'_'or r[i-1][j+3]<>'_'):
                    return False
    return True

Kemungkinan contoh:

A = "..[__][__][__][__]\n\
[__][__][__][__]..\n\
..[__][__][__][__]\n\
[__][__][__][__].."
print t(A) #False

B = "..[__]........[__]..\n\
[__][__][__][__][__]\n\
..[__][__][__][__]..\n\
....[__][__][__]....\n\
......[__][__]......\n\
........[__]........"
print t(B) #True
Wikunia
sumber
Saya tidak menggunakan titik-titik di dalam kode saya, sebenarnya input Anda dapat menggunakan arang apa pun tetapi tidak _dan [
Wikunia
1
Umumnya alih-alih menggunakan <>, Anda akan menggunakan !=.
Ethan Bierlein
@EthanBierlein tidak yakin tapi ya !=cara yang disukai
Wikunia
1

JavaScript 2 (ES6) - 148 151 byte

F=s=>s.split(/\n/).every((b,i,a)=>(r=1,b.replace(/]/g,(m,o)=>(T=z=>(a[i-1+(z&2)]||[])[o-z%2*3]=='_',r&=i>a.length-2?1:T(2)?T(3)|T(0):T(3)&T(1))),r))

Mengecek string baris bata terpisah baris baru (catatan: jika kita bisa menggunakan karakter pemisah yang berbeda seperti "|" untuk memisahkan baris ini bisa dibuat 1 byte lebih pendek).

Tes di konsol Firefox dengan:

F('..[__]......\n[__][__][__]\n..[__][__]..\n[__]....[__]'); // false
F('..[__][__]..\n[__][__][__]\n..[__][__]..\n[__]....[__]'); // true
saya dan kucing saya
sumber
0

Python, 209

def s(b):
 c=b.split("\n");s="".join(c);l=len(c[0]);t=" "*l+s+"]]"*l;a=lambda x,y,z:t[x+l*y+z]=="]"
 return all([(a(i,1,1)&a(i,1,5))or(a(i,-1,1)&a(i,1,1))or(a(i,-1,5)&a(i,1,5))for i,x in enumerate(t)if x=="["])

Tes:

towers=(
"[__]",

"..[__]..\n"
"[__][__]",

"........[__]........\n"
"......[__][__]......\n"
"........[__]........",

"..[__][__]..\n"
"[__][__][__]\n"
"..[__][__]..\n"
"[__]....[__]",

"............[__]..\n"
"..[__][__][__][__]\n"
"[__][__][__][__]..\n"
"..[__][__][__][__]\n"
"[__][__][__][__]..",

"..[__]........[__]..\n"
"[__][__][__][__][__]\n"
"..[__][__][__][__]..\n"
"....[__][__][__]....\n"
"......[__][__]......\n"
"........[__]........",

"..[__]..\n"
"........",

"..[__]..\n"
"[__]....",

"..[__]..\n"
"....[__]",

"..[__][__]..\n"
"[__]....[__]\n"
"..[__][__]..\n"
"[__]....[__]",

"..[__][__][__][__]\n"
"[__][__][__][__]..\n"
"..[__][__][__][__]\n"
"[__][__][__][__]..",

"[__][__][__][__][__]\n"
"..[__][__][__][__]..\n"
"....[__][__][__]....\n"
"......[__][__]......\n"
"........[__]........",
)
[s(x) for x in towers]

Keluaran:

[True, True, True, True, True, True, False, False, False, False, False, False]
legionixtiwo
sumber