Stellen wir uns einen normalen Mauerziegel als vor [__](und ignorieren Sie die Tatsache, dass die Oberseite offen ist). Wenn diese Steine ​​gestapelt werden, wird jede zweite Schicht um einen halben Stein versetzt, wie es im Ziegelbau üblich ist:

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

Somit hat jeder Ziegel höchstens sechs Nachbarn und es ist unmöglich, dass zwei Ziegel direkt vertikal ausgerichtet werden.

Der entscheidende Punkt ist, dass die Anordnungen dieser Steine ​​nicht gemörtelt werden , sondern lediglich durch die Schwerkraft zusammengehalten werden. Daher ist es wichtig, dass jeder Stein in der Struktur stabil ist, da sonst die gesamte Struktur instabil ist.

Es gibt drei Möglichkeiten, wie ein einzelner Ziegelstein stabil sein kann:

1. Jeder Ziegel auf dem Boden (die unterste Ziegelreihe) ist stabil.

2. Jeder Stein, der zwei Steine ​​direkt darunter hat, ist stabil:

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

3. Jeder Stein, auf dessen Seite sich oben und unten ein Stein befindet, ist stabil:

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

Aus diesen Regeln können wir zum Beispiel die Anordnung ersehen

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

ist instabil, weil der obere rechte Ziegel instabil ist, was alles ist, was es braucht.

Eine Ziegelkonstruktion ist nur dann stabil, wenn alle Ziegel stabil sind.

Herausforderung

Ihre Aufgabe ist es, eine Funktion zu schreiben, die eine Brick-Strukturzeichenfolge aufnimmt und einen Wahrheitswert zurückgibt, wenn die Struktur stabil ist, und einen falschen Wert, wenn sie instabil ist. ( wahrheitsgemäße / falsche Definition )

Die Eingabezeichenfolge kann beliebig groß sein, es handelt sich jedoch immer um ein rechteckiges Zeichenraster mit Leerzeichen, die Bereiche ohne Ziegel füllen. Die Zeichenrasterbreite ist durch 4 teilbar, die Höhe kann jedoch ungerade oder gerade sein.

Das Ziegelgitter erstreckt sich immer über und rechts von der unteren linken Ziegelposition:

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

Je nach Struktur steht jeder BRK?für einen Stein ( [__]) oder einen leeren Raum (4 Räume).

Beachten Sie, dass die Hohlräume aus halben Ziegeln mit Leerzeichen gefüllt sind, um sicherzustellen, dass das Zeichenraster rechteckig ist.

Wertung

Der kürzeste Code in Bytes gewinnt.

Anmerkungen

• Falls gewünscht, können Sie .anstelle des Leerzeichens ein Leerzeichen verwenden.
• Die leere Zeichenfolge wird als stabil betrachtet.
• Wenn Ihre Sprache keine Funktionen hat, können Sie eine benannte Zeichenfolgenvariable als Eingabe verwenden und das Ergebnis einer anderen Variablen zuweisen.
• Wenn Ihre Sprache keine Zeichenketten enthält, können Sie alles tun, was für die Eingabe angemessen erscheint.

Testfälle

Verschiedene Testfälle, durch Leerzeilen getrennt. Aus Gründen der Übersichtlichkeit .wird anstelle von Leerzeichen Leerzeichen verwendet.

Stabil:

[__]

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

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

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

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

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

Instabil:

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

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

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

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

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

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

80386 Maschinencode, 98

Der Code:

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

Der Code scannt die ASCII-Grafik vom Ende bis zum Anfang, wobei jeweils 2 Zeichen übersprungen werden. Dies führt zweimal die erforderlichen Überprüfungen durch (es würde ausreichen, um 4 Zeichen zu springen), vereinfacht jedoch die Logik.

Die Prüfung beginnt mit der vorletzten Zeichenreihe (es ist nicht erforderlich, die letzte Zeile zu prüfen). In jeder Zeile beginnen 3 Zeichen von rechts (es ist nicht erforderlich, zu weit rechts zu prüfen). Für jedes Zeichen werden 4 umgebende Zeichen überprüft:

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

Es gibt eine Reihe von logischen Bedingungen zu prüfen:

• Wenn A und C Bausteinzeichen sind, wird X unterstützt
• Wenn B und D Bausteinzeichen sind, wird X unterstützt
• Wenn C und D Bausteinzeichen sind, wird X unterstützt
• Wenn X ein Brick-Zeichen ist, muss es unterstützt werden. ansonsten ist die Struktur instabil

Es ist ein glücklicher Zufall, dass alle Brick-Charaktere [_]ihr LSB-Set haben. Alle anderen Zeichen .\nhaben es klar. Darüber hinaus hat der 80386 - Befehlssatz die praktischen „high“ und „low“ Register ( ah, alusw.), die dazu beitragen , die Kontrollen etwas parallelisieren. Alle Überprüfungen laufen also auf etwas dunkles Geigen hinaus.

Ich habe mit dem folgenden C-Code begonnen:

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

Ich habe den Code in die Assembler-Sprache übersetzt (meistens eins zu eins), einschließlich einer Implementierung von strchrund strlen. Der folgende Quellcode wird von MS Visual Studio in den Computercode oben in meinem Beitrag übersetzt.

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

MATLAB - 119 Bytes

Minimiert:

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

Erweitert:

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

Beispielnutzung:

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

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

S4: 1

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

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

U4: 0

Einzelheiten

Die Routine fügt eine Zeile von .an den Anfang der Eingabematrix an und konvertiert dann in eine numerische Matrix, indem 3 zu den ASCII-Zeichencodes hinzugefügt wird. Bei dieser Konvertierung entsteht eine 2D-Faltung mit dem Kernel

 2  0
-1 -1
 0  2

ergibt eine Matrix mit 0an Stellen, an denen sich das Zeichenmuster befindet

 . *
 _ _
 * .

vorhanden ist, mit der *Darstellung "beliebiger Zeichen". Aufgrund der Konstruktion des Kernels ist dies das einzige gültige Zeichenmuster, das a ergibt 0.

Eine identische Faltung wird mit der von links nach rechts gekippten Version des Kernels durchgeführt, um dies zu erkennen

 * .
 _ _
 . *

Eine Eingabe ist stabil, wenn entweder i ) sie leer ist oder ii ) in keiner Faltung Nullen auftreten.

Zwei Frustrationen sind

1. Die Standardfaltung von MATLAB läuft an den Kanten der Operandenmatrix vorbei und erzeugt fehlerhafte 0s in gegenüberliegenden Ecken für beide Faltungen, zu denen ,'valid'(8 Bytes) hinzugefügt werden müssenconv2 Aufruf müssen , um die Ausgabe auf den Bereich zu beschränken, in dem die Faltung gültig ist.

2. Die Behandlung des leeren String-Falls fügt 12 Bytes hinzu.

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)

Test in der FireFox / FireBug-Konsole

;['[__]', '  [__]  \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)))

Ausgabe

    [__]
true

  [__]  
[__][__]
true

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

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

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

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

  [__]  
false

  [__]  
[__]    
false

  [__]  
    [__]
false

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

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

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

Ungolfed

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] != '.'
    )  
  )
)

Python 279

Ich denke, ich bin ziemlich schlecht in Code-Golf-Herausforderungen, und vielleicht verwende ich dafür die falschen Sprachen: D Aber ich liebe Code, der sich leicht lesen lässt :) Übrigens, ich würde gerne einen Python-Code sehen, der weniger Bytes verwendet!

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

Mögliche Beispiele:

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

B = "..[__]........[__]..\n\
[__][__][__][__][__]\n\
..[__][__][__][__]..\n\
....[__][__][__]....\n\
......[__][__]......\n\
........[__]........"
print t(B) #True

JavaScript 2 (ES6) - 148 151 Bytes

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

Gibt eine Zeichenfolge aus Zeilen mit Zeilenumbrüchen als Trennzeichen aus (Anmerkung: Wenn wir ein anderes Trennzeichen wie "|" zum Trennen von Zeilen verwenden könnten, könnte dies um 1 Byte kürzer gemacht werden).

Testen Sie in der Firefox-Konsole mit:

F('..[__]......\n[__][__][__]\n..[__][__]..\n[__]....[__]'); // false
F('..[__][__]..\n[__][__][__]\n..[__][__]..\n[__]....[__]'); // true

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=="["])

Tests:

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]

Ausgabe:

[True, True, True, True, True, True, False, False, False, False, False, False]