Вступление

Этот вызов вдохновлен Grime , моим языком сопоставления двухмерных паттернов. По сути, вам предоставляется «грамматика», описывающая двумерные сетки символов, и ваша задача - создать сетку в соответствии с грамматикой. Кроме того, сетка должна быть как можно меньше в определенном слабом смысле.

вход

Ваш ввод - это строка, содержащая строчные ASCII-символы, а также символы |и -. Для простоты ввод не содержит повторяющихся строчных букв. Строка является спецификацией для класса прямоугольных сеток символов и анализируется слева направо, используя стек следующим образом.

• Если задан строчный символ c, поместите в стек m×nсетку символа cдля любого m, n ≥ 1.
• Получив трубу |, вытолкните две сетки Aи Bиз стека ( Bбыл сверху), и протолкните сетку, ABполученную путем объединения, Bсправа от A. Для этого требуется Aи Bодинаковая высота.
• Получив дефис -, извлеките две сетки Aи Bиз стека ( Bбыл сверху) и вставьте сетку, A/Bполученную путем объединения, Bв нижнюю часть A. Это требует того Aи Bиметь равную ширину.

Гарантируется, что для некоторых вариантов mи nсделанных в процессе анализа (которые могут отличаться для каждой буквы) спецификация ввода правильно описывает некоторый прямоугольник, который остается в стеке в конце.

Выход

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

Обратите внимание, что вы не обязаны обрабатывать ввод точно так, как описано выше; единственная важная вещь - то, что Ваш вывод правильный.

пример

Рассмотрим спецификацию

par-s||e-

Во-первых, мы решили нажать 1×2прямоугольник pи 1×1прямоугольники aи r(причина этого будет ясна позже). Затем мы совать aи rпрямоугольники, и толкать их по вертикали конкатенации

a
r

Затем мы нажимаем 1×2прямоугольник , выталкиваем sего и вышеупомянутый прямоугольник и выдвигаем их горизонтальную конкатенацию

as
rs

Затем мы pвыталкиваем этот прямоугольник и прямоугольник и выдвигаем их конкатенацию

pas
prs

Наконец, мы нажимаем 3×1прямоугольник , выталкиваем eего и вышеупомянутый прямоугольник и выдвигаем вертикальную конкатенацию

pas
prs
eee

Это вывод программы или хотя бы одна из возможностей. Обратите внимание, что хотя

ppas
ppas
pprs
eeee

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

В качестве более тонкого примера рассмотрим

co|m|p|il|e|r|-

Эта спецификация генерирует прямоугольник

comp
iler

который является действительным выводом. Тем не менее, он также генерирует

commp
iiler

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

правила

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

Дополнительные тестовые случаи

Вы можете использовать их для проверки вашей программы.

Input:
a
Output:
a

Input:
co|mp|l|-ex|i|f|-y|
Example output:
cccoy
mplly
exify

Input:
ja-r|g-o|ni-|ze|d-|
Example output:
jronze
arondd
ggoidd

Input:
un|co|p-yr|i|gh-t-ab|-|le-||-
Example output:
unnnnnnn
coyriggl
ppyrihhe
ppyritte
ppyriabe

К, 123 110 байт

Я использовал похожий подход к решению картона.

r:{y,x#,*|y};h:{t:(#x)|#y;r[t-#x;x],'r[t-#y]y};a:{(,x .|2#y),2_ y};*(){(a[{+h[+x;+y]}]x;a[h]x;(,,y),x)"-|"?y}/

Эта программа представляет собой серию вспомогательных определений, за которыми следует скрытая функция, которая принимает строку в качестве правильного аргумента. Переформатирование для удобочитаемости и назначение конечной функции как f:

r: {y,x#,*|y};                           / repeat last row x times
h: {t:(#x)|#y;r[t-#x;x],'r[t-#y;y]};     / append horizontal
v: {+h[+x;+y]};                          / append vertical
a: {(,x[y@1;y@0]),2_ y};                 / pop two values, concat

f: *(){:[y="-";a[v;x]; y="|";a[h;x]; (,,y),x]}/;

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

  f "ja-r|g-o|ni-|ze|d-|"
("jronze"
 "aroidd"
 "ggoidd")

Протестировано с использованием Kona, но оно также будет работать в порядке, если вы замените: в определении fна $- k5, изменив синтаксис "cond".

Ключевым моментом является признание того, что вертикальное добавление является транспонированием горизонтального добавления транспонирования обеих матриц. (См. Определение v.) Я думаю, что еще есть место, чтобы выжать несколько символов здесь и там. Если кого-то интересует более подробное объяснение, я могу его предоставить.

редактировать:

Обновлена ​​программа вверху этой записи. Безголовая версия:

r: {y,x#,*|y};                           / repeat row x times
h: {t:(#x)|#y;r[t-#x;x],'r[t-#y;y]};     / append horizontal
v: {+h[+x;+y]};                          / append vertical
a: {(,x .|2#y),2_ y};                    / apply a concat
f: *(){(a[v]x;a[h]x;(,,y),x)"-|"?y}/;

Заметные оптимизации длины включают в себя использование «точка применить» в a, заменив «Cond» со списком индексации f(менее эффективным, но короче) и замещающие члены вида a[b;c]в a[b]cкоторых допускается группировка. Так как я больше не использую "cond" или любые другие примитивы, которые отличаются между k3 и k5, эта версия теперь работает в ОК без изменений.

Пролог, 539 байт

:-lib(ic).
:-lib(util).
b(A,B,C):-between(A,B,C).
g(S):-string_list(S,L),p(L,[]).
w(h(L,R):_:_,I,J):-w(L,I,J);L=_:W:_,X is I-W,w(R,X,J).
w(v(U,D):_:_,I,J):-w(U,I,J);U=_:_:H,Y is J-H,w(D,I,Y).
w(f(C):W:H,I,J):-b(1,W,I),b(1,H,J),char_code(S,C),put_char(S).
p([],[S]):-term_variables(S,V),S=_:X:Y,labeling(V),!,b(1,Y,J),(b(1,X,I),w(S,I,J);nl),fail.
p([124|T],[Q,Z|R]):-!,Q=_:WA:H,Z=_:WB:H,W #= WA+WB,p(T,[h(Z,Q):W:H|R]).
p([45|T],[Q,Z|R]):-!,Q=_:W:HA,Z=_:W:HB,H #= HA+HB,p(T,[v(Z,Q):W:H|R]).
p([C|T],R):-!,[H,W] #:: 1..100,p(T,[f(C):W:H|R]).

объяснение

Мы начинаем с предиката g, который принимает строку, преобразует ее в список символов и вызываетp качестве второго аргумента предикат (parse) с пустым стеком.

Предикат pвызывает себя рекурсивно с соответствующим образом измененным стеком (ищите [H|T]шаблоны деструктуризации и конструктора). При вызове в базовом случае, когда список ввода пуст, pпечатается уникальный элемент стека. Если в стеке на данный момент меньше или больше одного элемента, это означает, что у нас есть пустая строка ввода, неверная строка ввода или ошибка (со строкой emtpy, предикат завершается ошибкой (говорит Пролог No), но ничего не печатается, это нормально, так как мы не должны ничего печатать для пустых строк).

решение

Стек содержит описание построенных прямоугольников, обозначенных S:W:HгдеS это символическое представление прямоугольника, Wего ширину и Hвысоту (примечание, A:Bэто синтаксический сахар для :(A,B)кортежа с функтором именем: , это просто короче , чтобы писать , чем иметь кортеж с префиксной нотацией).

С A и Bспецификации прямоугольника, Sможет быть:

• h(A,B) : горизонтальный конкат А и В
• v(A,B) : вертикальный конкат A и B
• f(C) : заполните C, где C - код символа

Ширина и высота сетки являются переменными программирования ограничений: во время вертикальной (соответственно горизонтальной) конкатенации ширина (соответственно высота) управляемых прямоугольников унифицируется, тогда как результирующая высота (соответственно ширина) ограничена суммой высота каждой подсетки (соответственно ширина).

Шаг маркировки в конце процесса создает переменные, соблюдая при этом ограничения, используя минимально возможные значения (это свойство порядка, в котором пробуются решения).

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

Также обратите внимание, что, поскольку домен по умолчанию для переменных установлен на 1..100, существует ограничение на возможные размеры сеток. Верхняя граница может быть изменена при необходимости. Это влияет на производительность, так как может потребоваться много времени, чтобы определить, что конкретное решение не допускает решения. Я сказал « мог », потому что ограничения могут резко сократить экспоненциальный поиск. Если вы нашли входную строку, которую трудно / дорого отклонить, пожалуйста, поделитесь.

печать

Печатная часть интересна тем, что в структуре есть своего рода алгоритм приведения лучей : я перебираю каждую ячейку результирующей сетки, от точки (1,1)к точке, (W,H)и вызываю wпредикат для печати содержимого сетки в главном дереве, в это местоположение (конечно, новая строка печатается после обработки каждой строки).

В wпозициях относительно текущей сетки (корневая сетка определяет абсолютные координаты).

При печати h(A,B)структуры в точке (X,Y), я безоговорочно печатаю в обеих ветках:

• в сетке Aв точке (X,Y), и
• в сетке Bв точке (H,Y), где Hнаходится Xминус ширина A.

Листовые ветви дерева сетки, f(C)наконец, либо печатают символ C, если относительное местоположение находится внутри сетки, либо ничего не делают. Так я могу печатать содержимое сетки в выходной поток сверху вниз, слева направо. Фактические массивы не создаются.

тесты

t("ja-r|g-o|ni-|ze|d-|").
t("un|co|p-yr|i|gh-t-ab|-|le-||-").
t("co|mp|l|-ex|i|f|-y|").
t("a").

tt :- t(X),nl,g(X).
tt.

Выполнение теста:

[eclipse] tt.

jronze
aronze
ggoidd

uuuuuuun
coyriggl
coyrihhl
coyrittl
ppyriabe

cccoy
mmply
exify

a

Yes (0.00s cpu)

Python 2.7, 259

z=zip
def p(a,b):
 s,l=sorted([a,b],key=len)
 s+=([s[-1]]*(len(l)-len(s)))
 return z(*(z(*a)+z(*b)))
g=lambda s,t=[]:s and(s[0]=='-'and g(s[1:],t[:-2]+[z(*p(z(*t[-2]),z(*t[-1])))])or(s[0]=='|'and g(s[1:],t[:-2]+[p(t[-2],t[-1])])or g(s[1:],t+[[s[0]]])))or t[0]

gэто функция, которая принимает спецификацию и выдает двумерный массив символов. Если вы хотите более удобную для пользователя версию, добавьте эту строку, чтобы она взяла спецификацию из stdin и распечатала сетку:

print'\n'.join(''.join(s)for s in g(raw_input()))

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

Input:
a
Output:
a
==========
Input:
co|mp|l|-ex|i|f|-y|
Output:
coooy
mplly
exify
==========
Input:
ja-r|g-o|ni-|ze|d-|
Output:
jronze
aroidd
ggoidd
==========
Input:
un|co|p-yr|i|gh-t-ab|-|le-||-
Output:
unnnnnnn
coyriggl
ppyrihhe
ppyritte
ppyriabe

объяснение

Стратегия проста: если сетка G действительна для спецификации S, то повторение самого правого столбца Gтакже дает действительную спецификацию S, и то же самое верно и для повторения нижней строки (доказательство этого - структурная индукция S). Поэтому, когда мы хотим объединить два прямоугольника, мы можем просто добавить последний столбец / строку меньшего, пока они не совпадут по размеру (это то, что делает функция p).

Haskell, 388 367 352 байта

data C=L{c::Char}|N{t::Int,w::Int,h::Int,l::C,r::C}
q=replicate
[]#[x]=x
(c:i)#(b:a:s)|c=='-'=i#(N 1(max(w a)$w b)(h a+h b)a b:s)|c=='|'=i#(N 2(w a+w b)(max(h a)$h b)a b:s)
(c:i)#s=i#(N 0 1 1(L c)(L c):s)
p i|t i==0=q(h i)$q(w i)$c$l i|t i==2=zipWith(++)(p(l i){h=h i})$p(r i){h=h i,w=w i-w(l i)}|1<2=p(l i){w=w i}++p(r i){w=w i,h=h i-h(l i)}
f=p.(#[])

Использование: f "par-s||e-"->["pas","prs","eee"]

Тестовый запуск с красивой печатью:

> putStr $ unlines $ f "par-s||e-"
pas
prs
eee

> putStr $ unlines $ f "co|m|p|il|e|r|-"
comp
iler

> putStr $ unlines $ f "a"
a

> putStr $ unlines $ f "co|mp|l|-ex|i|f|-y|"
coooy
mplly
exify

> putStr $ unlines $ f "ja-r|g-o|ni-|ze|d-|"
jronze
aroidd
ggoidd

> putStr $ unlines $ f "un|co|p-yr|i|gh-t-ab|-|le-||-"
unnnnnnn
coyriggl
ppyrihhe
ppyritte
ppyriabe

Как это работает: функция #разбирает входную строку в древовидную структуру, Cкоторая является либо листом, Lсодержащим символ для печати, либо узлом N. Nможет быть а) соединение бок о бок (t==2 ), б) соединение сверху вниз ( t==1) или в) квадрат с одной буквой ( t==0). Все узлы имеют поле ширины и высоты и левый и правый дочерний элемент. После анализа pпечатает оставшийся корневой узел, рекурсивно корректируя размер (ширина х высота) его дочерних узлов и соединяя их.

Редактировать: вывод в виде списка строк вместо красивой печати

JavaScript (ES6), 283 295

редактировать Теперь это (в значительной степени игра в гольф) решение JS по крайней мере короче, чем эталонное (вполне пригодное для игры в гольф) решение Python.

Аналогично картону, просто повторяет самый левый столбец или самый верхний ряд.

F=w=>(
s=[t=1,l='length'],
[for(c of w)(
  b=s[t],a=s[--t],
  c>'z'?
    s[t]=(G=(a,b,m=b[l]-a[l])=>m?m>0?G([a[0],...a],b):G(a,[b[0],...b]):a.map((r,i)=>r+b[i]))(a,b)
  :c<'a'?
    s[t]=a.map(r=>r[m=b[0][l]-r[l],0].repeat(m>0&&m)+r).concat(b.map(r=>r[0].repeat(m<0&&-m)+r))
  :s[t+=2]=[c]
)],
s[t].join('\n'))

Ungolfed Это мое первое, не Golphed решение.

F=sp=>{
  s=[]
  for(c of sp){
    a=s.pop(b=s.pop())
    if (c > 'z')
    {
      l = a.length
      m = b.length
      for(; l-m ;)
        l < m ? l = a.unshift(a[0]) : m = b.unshift(b[0])
      s.push(a.map((r,i) => r + b[i]))
    }
    else if (c < 'a')
    {
      l = a[0].length
      m = b[0].length
      s.push(
        a.map(r => r[0].repeat(l < m ? m-l : 0) + r)
        .concat(b.map( r => r[0].repeat( l > m ? l-m : 0) + r))
      )
    }
    else 
    {
      s.push(a,b,[c])
    }
  }
  return s.pop().join('\n')
}

Тест в консоли Firefox / FireBug

;['par-s||e-','co|m|p|il|e|r|-','co|mp|l|-ex|i|f|-y|',
 'ja-r|g-o|ni-|ze|d-|','un|co|p-yr|i|gh-t-ab|-|le-||-']
.forEach(w=>console.log(F(w)))

Выход

pas
prs
eee

comp
iler

cccoy
mmply
exify

jronze
aronze
ggoidd

uuuuuuun
coyriggl
coyrihhl
coyrittl
ppyriabe

Python 3, 251 байт

Вот эталонный ответ, который я обещал, сыграв немного дальше.

T=lambda m:list(map(list,zip(*m)))
E=lambda a,b:a[:1]*(len(b)-len(a))+a
H=lambda a,b:[d+c for c,d in zip(E(a,b),E(b,a))]
s=[]
for k in input():s=k>"z"and[H(*s[:2])]+s[2:]or k<"a"and[T(H(*map(T,s[:2])))]+s[2:]or[[[k]]]+s
for r in s[0]:print("".join(r))

Это полная программа, которая берет строку из STDIN и печатает в STDOUT. Подход такой же, как и дляboard_box: выдвинуть массив 1x1 для символа и дублировать строки, если это необходимо для объединения.

$ echo "par-s||e-" | python3 gr.py
pas
prs
eee

Детальное объяснение

• Tтранспонирует заданный список списков. Большая часть работы выполняется путем zip(*m)обмена строк на столбцы, а остальная часть просто конвертирует результат в список списков, поскольку zipвозвращает генератор кортежей.
• E(a,b)возвращается aс первым элементом, повторенным достаточно раз, чтобы соответствовать длине b. Обратите внимание, что умножение списка на отрицательное число дает пустой список, поэтому, если bоно меньше a, возвращается a.
• H(a,b)возвращает горизонтальное сцепление aи b, при необходимости, более короткое удлиняется E.
• s это стек.
• В forцикле мы перебираем входную строку и заменяем sее новым значением: если оно |(больше чем z), мы выталкиваем два значения и толкаем их H, если оно -(меньше чем a), мы выталкиваем два значения, транспонируем, передаем H, транспонировать снова и выдвинуть результат, а в противном случае передать массив 1x1 с буквой.
• Наконец, мы печатаем первый элемент s.