Стабильна ли структура кирпича?

24

Давайте представим стандартный кирпичный кирпич как [__](и проигнорируем тот факт, что вершина открыта). Когда эти кирпичи уложены друг на друга, каждый второй слой смещается на половину кирпича, как обычно в кирпичной конструкции:

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

Таким образом, у каждого кирпича есть не более шести соседей, и два кирпича не могут располагаться вертикально друг над другом.

Ключевым моментом является то, что расположение этих кирпичей не портится , а просто гравитацией. Поэтому важно, чтобы каждый кирпич в структуре был стабильным, иначе вся структура нестабильна.

Существует три способа обеспечения стабильности отдельного кирпича:

  1. Любой кирпич на земле (самая низкая линия кирпичей) является стабильным.

  2. Любой кирпич, который имеет два кирпича прямо под ним, является стабильным:

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

  3. Любой кирпич, имеющий кирпичи как над, так и под ним на одной стороне, является стабильным:

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

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

Из этих правил мы можем видеть, например, расположение

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

нестабилен, потому что верхний правый кирпич нестабилен, и это все, что нужно.

Кирпичная структура является стабильной, только если все ее кирпичи стабильны.

Вызов

Ваша задача - написать функцию, которая принимает строку кирпичной структуры и возвращает истинное значение, если структура стабильна, и ложное значение, если оно нестабильно. ( правдивое / ложное определение )

Входная строка может быть произвольно большой, но она всегда будет прямоугольной сеткой символов с пробелами, заполняющими области, лишенные кирпичей. Ширина сетки символов будет делиться на 4, но высота может быть нечетной или четной.

Сетка кирпича всегда проходит выше и справа от нижнего левого положения кирпича:

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

В зависимости от структуры каждый из BRK?них представляет собой кирпич ( [__]) или пустое пространство (4 пробела).

Обратите внимание на то, что полукринцевые полости заполнены пробелами, чтобы сетка символов была прямоугольной.

счет

Самый короткий код в байтах побеждает.

Заметки

  • При желании вы можете использовать .вместо пробела символ пробела.
  • Пустая строка считается стабильной.
  • Если в вашем языке нет функций, вы можете использовать именованную строковую переменную в качестве входных данных и присвоить результат другой переменной.
  • Если на вашем языке нет строк, вы можете делать все, что кажется подходящим для ввода.

Тестовые случаи

Различные тестовые случаи, разделенные пустыми строками. Для наглядности .используется вместо места для пустых мест.

Стабильная:

[__]

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

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

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

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

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

Нестабильный:

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

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

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

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

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

[__][__][__][__][__]
..[__][__][__][__]..
....[__][__][__]....
......[__][__]......
........[__]........
code-golf ascii-art Кальвин Хобби
источник
7
Я почти уверен, что ваше определение стабильности не соответствует действительности ;-)
Джон Дворжак
14
@JanDvorak Я знаю, но кто хотел бы поиграть в гольф целым физическим движком: P
Увлечения Кэлвина
........[__].... ......[__][__].. ....[__][__].... ..[__][__]...... [__][__]........ ..[__]..........(вам придется мысленно укладывать эти линии друг на друга. Дело в том, что ваши правила допускают сооружения, центр тяжести которых сильно смещен от точки их контакта с землей. Чтобы избежать этого, должна быть возможность затянуть их. без физического движка, если вам так хотелось.)
Натаниэль
2
Однако правдоподобие в физике - это огромная банка червей. Можно придумать много простых случаев, когда устойчивость зависит от коэффициента трения и / или от веса кирпича сверху.
COTO
10
"стабильный" ... хех
wchargin

Ответы:

12

80386 машинный код, 98

Код:

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

Код сканирует искусство ASCII с конца до начала, пропуская по 2 символа за раз. Это делает вдвое больше необходимых проверок (этого будет достаточно, чтобы прыгнуть на 4 символа), но упрощает логику.

Проверка начинается с последней до последней строки символов (нет необходимости проверять последнюю строку). В каждой строке начинается 3 символа справа (нет необходимости проверять слишком далеко вправо). Для каждого символа он проверяет 4 окружающих символа:

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

Существует несколько логических условий для проверки:

  • Если A и C - символы кирпича, X поддерживается
  • Если B и D - символы кирпича, X поддерживается
  • Если C и D являются символами кирпича, X поддерживается
  • Если X - символ кирпича, он должен поддерживаться; в противном случае структура нестабильна

Это счастливое совпадение, что все кирпичные персонажи [_]имеют свой набор LSB; все остальные персонажи .\nимеют это ясно. Кроме того, набор команд 80386 имеет эти функции «высокий» и «низкий» регистры ( ah, alи т.д.), которые помогают распараллелить проверяет немного. Таким образом, все проверки составляют какую-то непонятную мелочь.

Я начал со следующего кода 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;
}

Я перевел код на язык ассемблера (в основном это один в один), включая реализацию strchrи strlen. Следующий исходный код переведен MS Visual Studio на машинный код в верхней части моего поста.

__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
источник
7

MATLAB - 119 байт

уменьшенная:

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

Expanded:

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

Пример использования:

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

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

S4: 1

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

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

U4: 0

Детали

Подпрограмма добавляет строку .в начало входной матрицы, а затем преобразует ее в числовую матрицу, добавляя 3 к кодам символов ASCII. Учитывая это преобразование, 2D свертка с ядром

 2  0
-1 -1
 0  2

дает матрицу 0в местах, где шаблон персонажа

 . *
 _ _
 * .

присутствует, с *представлением "любой символ". Из-за конструкции ядра это единственная допустимая комбинация символов, которая выдаст 0.

Идентичная свертка выполняется с перевернутой влево и вправо версией ядра для обнаружения

 * .
 _ _
 . *

Ввод является стабильным, если либо i ) он пустой, либо ii ) никакие нули не появляются ни в одной свертке.

Два разочарования

  1. Свертка по умолчанию в MATLAB проходит за края матрицы операндов, производя ошибочные 0s в противоположных углах для обеих сверток, требуя ,'valid'добавления (8 байт) для conv2вызова, чтобы ограничить вывод областью, где свертка действительна.

  2. Обработка пустого строкового регистра добавляет 12 байтов.

COTO
источник
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)

Тест в консоли 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)))

Выход

    [__]
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
источник
Что [...a]делать, если вы не возражаете против моего запроса? Я знаю, что ES6 позволяет ...argв качестве последнего аргумента функции захватывать переменные, но я никогда не видел, чтобы он использовал этот способ.
COTO
@COTO codegolf.stackexchange.com/a/37723/21348 , вариант использования 2 (это очень часто, я использую его, возможно, в 80% моих ответов)
edc65
Sunofagun. Прямо как {:}в MATLAB. Это будет очень полезно. Спасибо. :)
COTO
1

Python 279

Я думаю, что я довольно плохо справляюсь с задачами в коде и, возможно, я использую не те языки для этого: D Но я люблю код, который легко читается :) Кстати, я хотел бы увидеть код на python, который использует меньше байтов!

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

Возможные примеры:

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

B = "..[__]........[__]..\n\
[__][__][__][__][__]\n\
..[__][__][__][__]..\n\
....[__][__][__]....\n\
......[__][__]......\n\
........[__]........"
print t(B) #True
Wikunia
источник
Я не использую точки внутри моего кода, на самом деле ваш вход может использует любой символ , но не _и [
Wikunia
1
Как правило, вместо того, чтобы использовать <>, вы бы использовали !=.
Итан Бирляйн
@EthanBierlein не был уверен, но да !=- это предпочтительный способ
Wikunia
1

JavaScript 2 (ES6) - 148 151 байт

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

Ожидается строка строк кирпича, разделенных символом новой строки (примечание: если бы мы могли использовать другой символ-разделитель, например "|", для разделения строк это можно было бы сделать на 1 байт короче).

Тест в консоли Firefox с:

F('..[__]......\n[__][__][__]\n..[__][__]..\n[__]....[__]'); // false
F('..[__][__]..\n[__][__][__]\n..[__][__]..\n[__]....[__]'); // true
я и мой кот
источник
0

Питон, 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=="["])

тесты:

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]

Выход:

[True, True, True, True, True, True, False, False, False, False, False, False]
legionixtiwo
источник