Czy konstrukcja z cegły jest stabilna?

24

Przedstawmy standardową cegłę murarską jako [__](i zignorujemy fakt, że góra jest otwarta). Po ułożeniu tych cegieł w stos co druga warstwa jest przesunięta o pół cegły, jak to zwykle ma miejsce w przypadku konstrukcji z cegły:

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

W ten sposób każda cegła ma co najwyżej sześciu sąsiadów i dwie cegły nie mogą ustawić się bezpośrednio w linii.

Kluczową kwestią jest to, że układy tych cegieł nie są zaprawione , lecz jedynie utrzymywane razem przez grawitację. Dlatego ważne jest, aby każda cegła w konstrukcji była stabilna, w przeciwnym razie cała struktura będzie niestabilna.

Istnieją trzy sposoby, w których pojedyncza cegła może być stabilna:

  1. Każda cegła na ziemi (najniższa linia cegieł) jest stabilna.

  2. Każda cegła, która ma dwie cegły bezpośrednio pod nią, jest stabilna:

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

  3. Każda cegła, która ma cegłę zarówno nad, jak i pod nią po tej samej stronie, jest stabilna:

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

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

Z tych zasad możemy zobaczyć, na przykład, aranżację

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

jest niestabilny, ponieważ prawy górny klocek jest niestabilny, co wystarczy.

Struktura cegły jest stabilna tylko wtedy, gdy wszystkie jej cegły są stabilne.

Wyzwanie

Twoim zadaniem jest napisanie funkcji, która pobiera ciąg struktury z cegły i zwraca prawdziwą wartość, jeśli struktura jest stabilna, a wartość fałsz, jeśli jest niestabilna. ( definicja prawdy / fałszu )

Łańcuch wejściowy może być dowolnie duży, ale zawsze będzie prostokątną siatką znaków, ze spacjami wypełniającymi obszary pozbawione cegieł. Szerokość siatki znaków będzie podzielna przez 4, ale wysokość może być nieparzysta lub parzysta.

Kratka z cegły zawsze rozciąga się powyżej i na prawo od dolnej lewej pozycji cegły:

         .
         .
         .
  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?

W zależności od struktury każda BRK?reprezentuje cegłę ( [__]) lub pustą przestrzeń (4 spacje).

Zauważ, że wnęki z połowy cegły są wypełnione spacjami, aby siatka znaków była prostokątna.

Punktacja

Najkrótszy kod w bajtach wygrywa.

Notatki

  • W razie potrzeby możesz użyć .zamiast spacji jako znaku pustej spacji.
  • Pusty ciąg jest uważany za stabilny.
  • Jeśli twój język nie ma funkcji, możesz użyć nazwanej zmiennej łańcuchowej jako danych wejściowych i przypisać wynik do innej zmiennej.
  • Jeśli twój język nie ma łańcuchów, możesz zrobić wszystko, co wydaje się odpowiednie do wprowadzania danych.

Przypadki testowe

Różne przypadki testowe, oddzielone pustymi liniami. Dla jasności .zastosowano zamiast spacji puste miejsca.

Stabilny:

[__]

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

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

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

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

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

Nietrwały:

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

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

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

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

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

[__][__][__][__][__]
..[__][__][__][__]..
....[__][__][__]....
......[__][__]......
........[__]........
code-golf  ascii-art 
— Hobby Calvina
źródło
7
Jestem prawie pewien, że twoja definicja stabilności nie pasuje do rzeczywistości ;-)
— John Dvorak
14
@JanDvorak Wiem, ale kto chciałby zagrać w golfa w całym silniku fizyki: P
— Calvin's Hobbies
........[__].... ......[__][__].. ....[__][__].... ..[__][__]...... [__][__]........ ..[__]..........(będziesz musiał mentalnie ułożyć te linie jedna na drugiej. Chodzi o to, że twoje reguły dopuszczają konstrukcje, których środek ciężkości jest daleko odsunięty od ich punktu styku z podłożem. Powinno być możliwe ich zaostrzenie, aby tego uniknąć , bez potrzeby korzystania z silnika fizyki, jeśli masz na to ochotę.)
— Nathaniel
2
Verisimilitude w fizyce to jednak ogromna puszka robaków. Można wymyślić wiele prostych przypadków, w których stabilność zależy od współczynnika tarcia i / lub ciężaru cegieł na wierzchu.
— COTO
10
„stabilny”… heh
— wchargin

Odpowiedzi:

12

Kod maszynowy 80386, 98

Kod:

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

Kod skanuje grafikę ASCII od końca do początku, przeskakując 2 znaki na raz. Robi to dwukrotnie potrzebne kontrole (wystarczy przeskoczyć 4 znaki), ale upraszcza logikę.

Sprawdzanie rozpoczyna się od ostatniego do ostatniego rzędu znaków (nie trzeba sprawdzać ostatniego wiersza). W każdej linii zaczyna 3 znaki od prawej (nie trzeba sprawdzać zbyt daleko w prawo). Dla każdej postaci sprawdza 4 otaczające ją postacie:

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

Istnieje kilka logicznych warunków do sprawdzenia:

  • Jeśli A i C są znakami z cegły, X jest obsługiwany
  • Jeśli B i D są znakami z cegły, X jest obsługiwany
  • Jeśli C i D są znakami z cegły, X jest obsługiwany
  • Jeśli X jest postacią z klocków, musi być obsługiwany; w przeciwnym razie struktura jest niestabilna

To szczęśliwy zbieg okoliczności, że wszystkie postacie z cegieł [_]mają ustawione LSB; wszystkie inne postacie .\nmają to jasno. Ponadto, 80386 zestaw instrukcji zawiera Te poręczne „wysokie” i „niskie rejestry” ( ah, alitp), które pomagają parallelize Kontrole trochę. Więc wszystkie sprawdzanie sprowadza się do jakiegoś niezrozumiałego majstrowania.

Zacząłem od następującego kodu C:

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

Przetłumaczyłem kod na język asemblera (jest to w większości jeden na jeden), w tym implementację strchri strlen. Poniższy kod źródłowy został przetłumaczony przez MS Visual Studio na kod maszynowy na górze mojego postu.

__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;
    }
}
— anatolig
źródło
7

MATLAB - 119 bajtów

Zminimalizowane:

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

Rozszerzony:

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

Przykładowe użycie:

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

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

S4: 1

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

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

U4: 0

Detale

Procedura dołącza wiersz .do góry matrycy wejściowej, a następnie konwertuje na matrycę numeryczną, dodając 3 do kodów znaków ASCII. Biorąc pod uwagę tę konwersję, splot 2D z jądrem

 2  0
-1 -1
 0  2

daje macierz 0w miejscach, w których wzór znaków

 . *
 _ _
 * .

jest obecny, *reprezentując „dowolny znak”. Ze względu na budowę jądra jest to jedyny prawidłowy wzorzec znaków, który da a 0.

Identyczny splot jest wykonywany z wykrytą wersją jądra z odwróconą lewą i prawą stroną

 * .
 _ _
 . *

Dane wejściowe są stabilne, jeśli i ) jest puste lub ii ) w żadnym zwojach nie pojawiają się zera.

Są dwie frustracje

  1. Domyślny splot MATLAB-a przebiega poza krawędzie macierzy operandu, tworząc błędne 0s w przeciwległych rogach dla obu zwojów, wymagając ,'valid'dodania (8 bajtów), aby conv2wywołać ograniczenie wyjścia do obszaru, w którym splot jest ważny.

  2. Obsługa pustej wielkości ciągu powoduje dodanie 12 bajtów.

— COTO
źródło
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)

Przetestuj w konsoli 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)))

Wydajność

    [__]
true

  [__]  
[__][__]
true

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

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

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

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

  [__]  
false

  [__]  
[__]    
false

  [__]  
    [__]
false

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

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

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

Bez golfa

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
źródło
Co robi [...a], jeśli nie masz nic przeciwko mojemu pytaniu? Wiem, że ES6 zezwala ...argna ostatni argument funkcji do przechwytywania variadics, ale nigdy nie widziałem, aby była używana w ten sposób.
— COTO
@COTO codegolf.stackexchange.com/a/37723/21348 , użyj przypadku 2 (jest to bardzo częste, używam go w około 80% moich odpowiedzi)
— edc65
Sunofagun. Tak jak {:}w MATLAB. To będzie bardzo przydatne. Dzięki. :)
— COTO
1

Python 279

Wydaje mi się, że źle radzę sobie z wyzwaniami związanymi z golfem i może używam do tego niewłaściwych języków: D Uwielbiam kod, który można łatwo odczytać :) Btw Chciałbym zobaczyć kod python, który używa mniej bajtów!

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

Możliwe przykłady:

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

B = "..[__]........[__]..\n\
[__][__][__][__][__]\n\
..[__][__][__][__]..\n\
....[__][__][__]....\n\
......[__][__]......\n\
........[__]........"
print t(B) #True
— Wikunia
źródło
Nie używam kropek wewnątrz mojego kodu, tak naprawdę twoje dane wejściowe mogą używać dowolnego znaku, ale nie _i [
— Wikunia,
1
Zasadniczo zamiast używać <>, użyłbyś !=.
— Ethan Bierlein
@EthanBierlein nie był pewien, ale tak !=jest preferowanym sposobem
— Wikunia
1

JavaScript 2 (ES6) - 148 151 bajtów

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

Oczekuje ciągu wierszy z cegieł oddzielonych znakiem nowej linii (uwaga: jeśli moglibyśmy użyć innego znaku separatora, takiego jak „|” do oddzielenia wierszy, można by to zrobić o 1 bajt krótszy).

Testuj w konsoli Firefox za pomocą:

F('..[__]......\n[__][__][__]\n..[__][__]..\n[__]....[__]'); // false
F('..[__][__]..\n[__][__][__]\n..[__][__]..\n[__]....[__]'); // true
— ja i mój kot
źródło
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=="["])

Testy:

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]

Wydajność:

[True, True, True, True, True, True, False, False, False, False, False, False]
— legionixtiwo
źródło
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.