Wprowadzenie

To wyzwanie jest inspirowane przez Grime , mój język dopasowywania wzorów 2D. Zasadniczo otrzymujesz „gramatykę” opisującą dwuwymiarowe siatki znaków, a Twoim zadaniem jest wygenerowanie siatki zgodnie z gramatyką. Ponadto siatka powinna być jak najmniejsza w pewnym słabym znaczeniu.

Wejście

Wpisujesz ciąg zawierający małe znaki ASCII oraz symbole |i -. Dla uproszczenia dane wejściowe nie zawierają powtarzających się małych liter. Ciąg jest specyfikacją klasy prostokątnych siatek znaków i jest analizowany od lewej do prawej za pomocą stosu w następujący sposób.

• Biorąc pod uwagę małą literę c, przesuń na stos m×nsiatkę postaci c, dla dowolnejm, n ≥ 1 .
• Biorąc pod uwagę fajkę |, przebij dwie siatki Ai Bze stosu ( Bbył na górze) i popchnij siatkę ABuzyskaną przez konkatenację Bna prawo od A. Wymaga to Ai Bmają jednakową wysokość.
• Biorąc pod uwagę łącznik -, wysuń dwie siatki Ai Bze stosu ( Bbył na górze) i przesuń siatkę A/Buzyskaną przez konkatenację Bna dół A. Wymaga to Ai Bmają jednakową szerokość.

Jest pewne, że dla niektórych opcji min dokonywanych podczas przetwarzania (które mogą być różne dla każdej litery) specyfikacja wejściowa poprawnie opisuje prostokąt, który pozostaje na stosie na końcu.

Wynik

Twój wynik jest prostokątną siatką znaków określonych przez dane wejściowe. Siatka musi być minimalna w tym sensie, że usunięcie dowolnego wiersza lub kolumny spowoduje, że będzie ona nieważna. Możesz zwrócić ciąg oddzielony znakiem nowej linii (z końcowym znakiem nowej linii lub bez), tablicę znaków 2D lub tablicę ciągów, w zależności od tego, który z nich jest najwygodniejszy.

Pamiętaj, że nie musisz przetwarzać danych wejściowych dokładnie tak, jak opisano powyżej; jedyną ważną rzeczą jest to, że wyniki są prawidłowe.

Przykład

Rozważ specyfikację

par-s||e-

Najpierw wybieramy pchnięcie 1×2prostokąta pi 1×1prostokąty ai r(powód będzie wyjaśniony później). Następnie wyskakujemy ai rprostokąty i przesuwamy ich pionowe połączenie

a
r

Następnie wciskamy 1×2prostokąt s, pop go i powyższy prostokąt, i przesuwamy ich poziomą konkatenację

as
rs

Następnie przebijamy ten prostokąt i pprostokąt i przesuwamy ich konkatenację

pas
prs

Na koniec wciskamy 3×1prostokąt , przesuwamy ego i powyższy prostokąt i przesuwamy pionową konkatenację

pas
prs
eee

To jest wynik programu lub przynajmniej jedna z możliwości. Zauważ, że mimo to

ppas
ppas
pprs
eeee

jest również generowany przez specyfikację, nie jest to poprawny wynik, ponieważ wiele wierszy i kolumn można usunąć.

Rozważ bardziej subtelny przykład

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

Ta specyfikacja generuje prostokąt

comp
iler

który jest prawidłowym wyjściem. Jednak generuje również

commp
iiler

co również jest ważne, ponieważ nie można usunąć pojedynczego wiersza ani kolumny bez unieważnienia go.

Zasady

Możesz podać pełny program lub funkcję. Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone.

Dodatkowe przypadki testowe

Możesz użyć ich do przetestowania swojego programu.

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

K, 123 110 bajtów

Zastosowałem podobne podejście do rozwiązania karton_box.

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

Ten program to seria definicji pomocników, po których następuje ukryta funkcja, która przyjmuje ciąg jako prawidłowy argument. Przeformatowanie pod kątem czytelności i przypisanie końcowej funkcji jako 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]}/;

Użyj przykładu:

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

Testowane przy użyciu Kona, ale będzie działać również w OK, jeśli zastąpisz: w definicji fna$ -k5 zmieniłem składnię „cond”.

Kluczowym punktem jest uznanie, że wykonanie dołączenia pionowego jest transpozycją dołączenia poziomego transpozycji obu macierzy. (Zobacz definicję v.) Myślę, że wciąż jest miejsce na wyciśnięcie kilku znaków tu i tam. Jeśli ktoś jest zainteresowany bardziej szczegółowym wyjaśnieniem, mogę je przedstawić.

edytować:

Zaktualizowano program u góry tego wpisu. Wersja bez golfa:

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

Znaczące optymalizacje długości obejmują użycie „kropki zastosuj” w a, zastąpienie „cond” indeksowaniem listy w f(mniej wydajne, ale krótsze) i zastąpienie warunków formularza a[b;c]na, a[b]ctam gdzie jest to dozwolone przez grupowanie. Ponieważ nie używam już „cond” ani żadnych prymitywów, które różnią się między k3 i k5, ta wersja działa teraz w ok bez modyfikacji.

Prolog, 539 bajtów

:-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]).

Wyjaśnienie

Zaczynamy od predykatu g, który pobiera ciąg, konwertuje go jako listę znaków i wywołuje ppredykat (parsuj) z pustym stosem jako drugim argumentem.

Predykat pwywołuje się rekurencyjnie z odpowiednio zmodyfikowanym stosem (poszukaj [H|T]wzorów destrukcyjnych i konstruktorskich). Po wywołaniu w przypadku podstawowym, gdzie lista wejściowa jest pusta, pdrukuje unikalny element stosu. Jeśli stos zawiera mniej niż jeden element w tym momencie, oznacza to, że mamy pusty ciąg wejściowy, zły ciąg wejściowy lub błąd (z pustym ciągiem predykat kończy się niepowodzeniem (mówi Prolog No), ale nic nie jest drukowane, co jest w porządku, ponieważ nie powinniśmy nic drukować dla pustych ciągów).

Rozwiązywanie

Stos zawiera opis zbudowanych prostokątów, oznaczony S:W:H, gdzieS jest symboliczną reprezentacją prostokąta, Wjego szerokości i Hwysokości (uwaga, A:Bto cukier składniowy dla :(A,B)krotki z nazwanym funktorem :; jest tylko krótszy niż napisać krotkę z notacją przedrostkową).

Z AB specyfikacjami i pod-prostokątami Smogą być:

• h(A,B) : concat poziomy A i B
• v(A,B) : concat pionowy A i B
• f(C) : wypełnij C, gdzie C jest kodem znakowym

Szerokości i wysokości siatek są zmiennymi programującymi ograniczenia: podczas konkatenacji pionowej (odpowiednio. Poziomej) szerokość (odpowiednio. Wysokość) manipulowanych prostokątów jest ujednolicona, podczas gdy uzyskana wysokość (odpowiednio. Szerokość) jest ograniczona do sumy wysokość każdego podsiatki (lub szerokość).

Etap etykietowania na końcu procesu inicjuje zmienne przy jednoczesnym przestrzeganiu ograniczeń, przy użyciu minimalnych możliwych wartości (jest to właściwość kolejności, w której rozwiązania są wypróbowywane).

Mogłem uzyskać krótszą odpowiedź przy użyciu tego samego rozumowania, co w innych odpowiedziach, bez ograniczeń, ale teraz jest już za późno.

Zauważ również, że ponieważ domyślną domeną dla zmiennych jest ustawione 1..100, istnieje ograniczenie co do możliwych rozmiarów siatek. W razie potrzeby górna granica może zostać zmieniona. Wpływ tego na wydajność polega na tym, że ustalenie, czy dane rozwiązanie nie dopuszcza żadnego rozwiązania, może zająć dużo czasu. Powiedziałem „ mógłbym ”, ponieważ ograniczenia prawdopodobnie drastycznie przycinają wyszukiwanie wykładnicze. Jeśli znajdziesz ciąg wejściowy, który jest trudny / kosztowny do odrzucenia, udostępnij.

Druk

Część drukująca jest interesująca, ponieważ istnieje pewien algorytm rzutowania promieni nad strukturą: iteruję każdą komórkę wynikowej siatki, od punktu (1,1)do punktu (W,H)i wwywołuję predykat, aby wydrukować zawartość siatki w głównym drzewie, w ta lokalizacja (oczywiście nowa linia jest drukowana po przetworzeniu każdej linii).

W w, pozycje są względem bieżącej siatki (siatka główna określa współrzędne bezwzględne).

Podczas drukowania h(A,B)struktury w punkcie (X,Y)bezwarunkowo drukuję w obu gałęziach:

• w siatce Aw punkcie (X,Y)oraz
• w siatce Bw punkcie (H,Y), gdzie Hjest Xminus szerokość A.

Gałęzie liści drzewa siatki f(C), w końcu albo wydrukują znak C, jeśli względna lokalizacja znajduje się wewnątrz siatki, albo nic nie robią. W ten sposób mogę wydrukować zawartość siatki do strumienia wyjściowego, od góry do dołu, od lewej do prawej. Nie są generowane żadne rzeczywiste tablice.

Testy

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.

Uruchamianie testu:

[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]

gjest funkcją, która przyjmuje specyfikację i daje tablicę znaków 2D. Jeśli chcesz wersji bardziej przyjaznej dla użytkownika, dodaj ten wiersz, aby pobrać specyfikację ze standardowego wejścia i wydrukować tabelę:

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

Przypadki testowe

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

Wyjaśnienie

Strategia jest prosta: jeśli siatka G jest poprawna dla specyfikacji S, to powtórzenie kolumny z prawej strony Grównież daje poprawną specyfikację S, i to samo dotyczy powtórzenia dolnego rzędu (dowodem na to jest włączenie indukcji strukturalnej S). Dlatego, gdy chcemy połączyć dwa prostokąty, możemy po prostu dołączyć ostatnią kolumnę / wiersz mniejszego, dopóki nie dopasują wielkości (to właśnie robi funkcja p).

Haskell, 388 367 352 bajtów

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.(#[])

Zastosowanie: f "par-s||e-"->["pas","prs","eee"]

Uruchomienie testowe z ładnym drukiem:

> 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

Jak to działa: funkcja #analizuje ciąg wejściowy w strukturę drzewa, Cktóra jest liściem Lzawierającym znak do wydrukowania lub węzłem N. Nmoże być a) łączeniem obok siebie ( t==2), b) łączeniem góra-dół (t==1 ) lub c) kwadratem z pojedynczą literą ( t==0). Wszystkie węzły mają pole szerokości i wysokości oraz lewe i prawe dziecko. Po analizie pdrukuje pozostały węzeł główny, rekurencyjnie dostosowując rozmiar (szerokość x wysokość) jego węzłów potomnych i łącząc je.

Edycja: wyjście jako lista linii zamiast ładnego drukowania

JavaScript (ES6), 283 295

Edytuj Teraz to (mocno golfowe) rozwiązanie JS jest co najmniej krótsze niż referencyjne (dość golfowe) rozwiązanie Python.

Podobnie jak w przypadku karton_powtarzania, wystarczy powtórzyć lewą kolumnę lub najwyższy rząd.

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

Niegolfowane To moje pierwsze, niegolfowane rozwiązanie.

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

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

Wynik

pas
prs
eee

comp
iler

cccoy
mmply
exify

jronze
aronze
ggoidd

uuuuuuun
coyriggl
coyrihhl
coyrittl
ppyriabe

Python 3, 251 bajtów

Oto obiecana odpowiedź, trochę dalej grałem w golfa.

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

Jest to pełny program, który pobiera ciąg ze STDIN i drukuje do STDOUT. Podejście jest takie samo, jak w przypadku karton_boksa: wciśnij tablicę 1x1 dla znaku i duplikuj wiersze, jeśli to konieczne do konkatenacji.

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

Szczegółowe wyjaśnienie

• Ttransponuje podaną listę list. Większość pracy polega zip(*m)na zamianie wierszy na kolumny, reszta po prostu konwertuje wynik na listę list, ponieważ zipzwraca generator krotek.
• E(a,b)zwraca az pierwszym elementem powtórzonym tyle razy, aby dopasować długość b. Zauważ, że pomnożenie listy przez liczbę ujemną daje pustą listę, więc jeśli bjest krótsza niż a, to zwraca a.
• H(a,b)zwraca łączenie w poziomie ai b, w Erazie potrzeby , krótsze jest przedłużane .
• s to stos.
• W forpętli iterujemy ciąg wejściowy i zastępujemy sgo nową wartością: jeśli jest |(większa niż z), wstawiamy dwie wartości i wypychamy ich H, jeśli jest -(mniejsza niż a), wstawiamy dwie wartości, transponujemy, przesyłamy do H, transponuj ponownie i wypchnij wynik, a w przeciwnym razie wypchnij tablicę 1x1 z literą.
• Na koniec drukujemy pierwszy element s.