A estrutura de tijolos é estável?

24

Vamos representar um tijolo de alvenaria padrão como [__](e ignorar o fato de que a parte superior está aberta). Quando esses tijolos são empilhados, todas as outras camadas são compensadas por meio tijolo, como é habitual na construção de tijolos:

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

Assim, cada tijolo tem no máximo seis vizinhos e é impossível que dois tijolos se alinhem diretamente na vertical.

O ponto principal é que os arranjos desses tijolos não são argamassados , mas apenas mantidos juntos pela gravidade. Portanto, é importante que cada tijolo na estrutura seja estável, caso contrário, toda a estrutura é instável.

Existem três maneiras pelas quais um tijolo individual pode ser estável:

  1. Qualquer tijolo no chão (a linha mais baixa de tijolos) é estável.

  2. Qualquer tijolo que tenha dois tijolos diretamente abaixo é estável:

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

  3. Qualquer tijolo que tenha um tijolo acima e abaixo do mesmo lado é estável:

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

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

A partir dessas regras, podemos ver, por exemplo, o arranjo

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

é instável porque o tijolo superior direito é instável, o que é suficiente.

Uma estrutura de tijolos é estável apenas se todos os seus tijolos forem estáveis.

Desafio

Sua tarefa é escrever uma função que receba uma sequência de estrutura de tijolo e retorne um valor verdadeiro, se a estrutura for estável, e um valor falso, se instável. ( definição de verdade / falsidade )

A sequência de entrada pode ser arbitrariamente grande, mas sempre será uma grade retangular de caracteres, com espaços preenchendo áreas sem tijolos. A largura da grade de caracteres será divisível por 4, mas a altura pode ser ímpar ou par.

A grade do tijolo sempre se estende acima e à direita da posição inferior esquerda do tijolo:

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

Dependendo da estrutura, cada BRK?um representa um tijolo ( [__]) ou um espaço vazio (4 espaços).

Observe que as cavidades de meio tijolo são preenchidas com espaços para garantir que a grade de caracteres seja retangular.

Pontuação

O código mais curto em bytes vence.

Notas

  • Se desejar, você pode usar em .vez do espaço como o caractere de espaço vazio.
  • A cadeia vazia é considerada estável.
  • Se seu idioma não possui funções, você pode usar uma variável de string nomeada como entrada e atribuir o resultado a outra variável.
  • Se o seu idioma não tiver strings, você poderá fazer o que parecer apropriado para a entrada.

Casos de teste

Vários casos de teste, separados por linhas vazias. Para maior clareza, .é usado em vez de espaço para espaços vazios.

Estável:

[__]

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

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

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

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

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

Instável:

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

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

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

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

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

[__][__][__][__][__]
..[__][__][__][__]..
....[__][__][__]....
......[__][__]......
........[__]........
code-golf ascii-art Passatempos de Calvin
fonte
7
Tenho certeza de que a sua definição de estabilidade não corresponde à realidade ;-)
John Dvorak
14
@JanDvorak eu sei, mas quem gostaria de jogar golfe em um motor de física inteiro: P
Calvin's Hobbies
........[__].... ......[__][__].. ....[__][__].... ..[__][__]...... [__][__]........ ..[__]..........(você terá que empilhar mentalmente essas linhas umas sobre as outras. O ponto é que suas regras permitem estruturas cujo centro de gravidade está muito distante do ponto de contato com o solo. Deve ser possível apertá-las para evitar isso. , sem precisar de um motor de física, se você sentiu como ele).
Nathaniel
2
A verossimilhança na física é uma enorme lata de minhocas, no entanto. Pode-se chegar a muitos casos simples em que a estabilidade depende do coeficiente de atrito e / ou do peso dos tijolos no topo.
COTO
10
"estável"… heh
wchargin 05/10

Respostas:

12

Código da máquina 80386, 98

O código:

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

O código varre a arte ASCII do fim ao começo, saltando 2 caracteres por vez. Isso faz o dobro das verificações necessárias (seria suficiente pular 4 caracteres), mas simplifica a lógica.

A verificação começa na penúltima linha de caracteres (não é necessário verificar a última linha). Em cada linha, ele inicia três caracteres da direita (não é necessário verificar muito à direita). Para cada personagem, ele verifica quatro caracteres ao redor:

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

Há várias condições lógicas para verificar:

  • Se A e C são caracteres em tijolo, X é suportado
  • Se B e D são caracteres em tijolo, X é suportado
  • Se C e D são caracteres em tijolo, X é suportado
  • Se X é um caractere de bloco, ele precisa ser suportado; caso contrário, a estrutura é instável

É uma coincidência de sorte que todos os personagens de tijolos [_]tenham seu conjunto LSB; todos os outros personagens .\ntêm isso claro. Além disso, o conjunto de instruções 80386 tem estes acessível "alta" e "baixa" registros ( ah, al, etc.), que ajuda paralelizar as verificações um pouco. Portanto, toda a verificação equivale a um pouco obscuro.

Comecei a partir do seguinte código 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;
}

Traduzi o código para a linguagem assembly (geralmente é individual), incluindo uma implementação de strchre strlen. O seguinte código-fonte é traduzido pelo MS Visual Studio para o código de máquina na parte superior da minha postagem.

__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
fonte
7

MATLAB - 119 bytes

Minificado:

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

Expandido:

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

Uso da amostra:

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

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

S4: 1

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

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

U4: 0

Detalhes

A rotina anexa uma linha .ao topo da matriz de entrada e depois converte em uma matriz numérica adicionando 3 aos códigos de caracteres ASCII. Dada essa conversão, uma convolução 2D com o kernel

 2  0
-1 -1
 0  2

produz uma matriz com 0em locais onde o padrão de caracteres

 . *
 _ _
 * .

está presente, *representando "qualquer caractere". Devido à construção do kernel, este é o único padrão de caractere válido que produzirá a 0.

Uma convolução idêntica é realizada com a versão invertida esquerda-direita do kernel para detectar

 * .
 _ _
 . *

Uma entrada é estável se i ) estiver vazia ou ii ) nenhum zeros aparecer em qualquer convolução.

Duas frustrações são

  1. A convolução padrão do MATLAB passa pelas bordas da matriz do operando, produzindo 0s errados nos cantos opostos para ambas as convoluções, exigindo que ,'valid'(8 bytes) sejam adicionados para conv2chamar para limitar a saída à área em que a convolução é válida.

  2. Manipular o caso de cadeia vazia adiciona 12 bytes.

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

Teste no console do 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)))

Saída

    [__]
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] != '.'
    )  
  )
)
edc65
fonte
O que [...a]faz, se você não se importa que eu pergunte? Eu sei que o ES6 permite ...argcomo o último argumento de uma função capturar variáveis, mas nunca o vi usado dessa maneira.
COTO
@COTO codegolf.stackexchange.com/a/37723/21348 , use case 2 (é muito comum, eu usá-lo em talvez 80% das minhas respostas)
edc65
Sunofagun. Assim como {:}no MATLAB. Isso vai ser muito útil. Obrigado. :)
COTO
1

Python 279

Eu acho que sou muito ruim em desafios de código de golfe e talvez eu use as linguagens erradas para isso: D Mas eu amo código que pode ser facilmente lido :) Btw Gostaria de ver um código python que use menos bytes!

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

Exemplos possíveis:

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

B = "..[__]........[__]..\n\
[__][__][__][__][__]\n\
..[__][__][__][__]..\n\
....[__][__][__]....\n\
......[__][__]......\n\
........[__]........"
print t(B) #True
Wikunia
fonte
Eu não uso os pontos dentro do meu código, na verdade, sua lata de entrada usa qualquer caractere, mas não _e [
Wikunia
11
Geralmente, em vez de usar <>, você usaria !=.
Ethan Bierlein
@EthanBierlein não tinha certeza, mas sim !=é tge maneira preferida
Wikunia
1

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

Espera uma sequência de linhas de tijolos separadas por nova linha (nota: se pudéssemos usar um caractere separador diferente como "|" para separar linhas, isso poderia tornar 1 byte mais curto).

Teste no console do Firefox com:

F('..[__]......\n[__][__][__]\n..[__][__]..\n[__]....[__]'); // false
F('..[__][__]..\n[__][__][__]\n..[__][__]..\n[__]....[__]'); // true
eu e meu gato
fonte
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=="["])

Testes:

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]

Saída:

[True, True, True, True, True, True, False, False, False, False, False, False]
legionixtiwo
fonte