Generate a Rectangle from a Specification

Question

Introduction

This challenge is inspired by Grime, my 2D pattern matching language. Basically, you are given a "grammar" that describes two-dimensional grids of characters, and your job is to generate a grid according to the grammar. In addition, the grid should be as small as possible in a certain weak sense.

Input

Your input is a string containing lowercase ASCII characters and the symbols | and -. For simplicity, the input does not contain repeated lowercase characters. The string is a specification for a class of rectangular grids of characters, and it is parsed from left to right using a stack as follows.

• Given a lowercase character c, push to the stack an m×n grid of the character c, for any m, n ≥ 1.
• Given a pipe |, pop two grids A and B from the stack (B was on top), and push the grid AB obtained by concatenating B to the right of A. This requires that A and B have equal height.
• Given a hyphen -, pop two grids A and B from the stack (B was on top), and push the grid A/B obtained by concatenating B to the bottom of A. This requires that A and B have equal width.

It is guaranteed that for some choices of m and n made during the parsing process (which may be different for each letter), the input specification correctly describes some rectangle, which is left on the stack at the end.

Output

Your output is a rectangular grid of characters specified by the input. The grid must be minimal in the sense that removing any row or column would make it invalid. You can return a newline-separated string (with or without a trailing newline), a 2D array of characters, or an array of strings, whichever is the most convenient format.

Note that you are not required to process the input exactly as described above; the only important thing is that your output is correct.

Example

Consider the specification

par-s||e-

First, we choose to push a 1×2 rectangle of p, and 1×1 rectangles of a and r (the reason for this will be clear later). Then, we pop the a and r rectangles, and push their vertical concatenation

a
r

Next, we push a 1×2 rectangle of s, pop it and the above rectangle, and push their horizontal concatenation

as
rs

Then we pop that rectangle and the p rectangle, and push their concatenation

pas
prs

Finally, we push a 3×1 rectangle of e, pop it and the above rectangle, and push the vertical concatenation

pas
prs
eee

This is the output of the program, or at least one of the possibilities. Notice that even though

ppas
ppas
pprs
eeee

is also generated by the specification, it is not a valid output, since many of the rows and columns could be removed.

As a more subtle example, consider

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

This specification generates the rectangle

comp
iler

which is a valid output. However, it also generates

commp
iiler

which is valid too, since no single row or column can be removed without invalidating it.

Rules

You can give a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.

Extra Test Cases

You can use these to test your program.

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

• seequ: Where do n and m come from?
• seequ: Can be static or has to be some form of input?
• Zgarb: @Sieg n and m are chosen non-deterministically. It is guaranteed that suitable values for them exist, but it is your program's job to find them.
• seequ: You don't actually define what they are.
• orlp: un|co|p-|yr|i|gh--t-ab|-|le-||- is impossible to be valid. The last - has an arity of 2, while there's only 1 element on the stack.

Answer 1

K, (削除) 123 (削除ここまで) 110 bytes

I used a similar approach to cardboard_box's solution.

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

This program is a series of helper definitions followed by a tacit function which takes a string as a right argument. Reformatting for readability and assigning the final function as 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]}/;

Use example:

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

Tested using Kona, but it will also work in oK if you replace the : in the definition of f with a $- k5 changed the syntax of "cond".

A key point is recognizing that doing a vertical append is the transpose of the horizontal append of the transpose of both matrices. (See definition v.) I think there's still room to squeeze out a few characters here and there. If anyone is interested in a more detailed explanation I can provide one.

edit:

Updated the program at the top of this entry. Ungolfed version:

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

Notable length optimizations include the use of "dot apply" in a, replacing the "cond" with list indexing in f (less efficient, but shorter) and replacing terms of the form a[b;c] into a[b]c where permitted by grouping. Since I'm no longer using "cond" or any primitives which are different between k3 and k5 this version now works in oK without modification.

• Zgarb: Congratulations on winning the bounty!
• JohnE: Thanks! It was an interesting problem that yielded pretty well to K. It would have been interesting to see attempts in J or APL for comparison.

Answer 2

Prolog, 539 bytes

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

Explanation

We start with predicate g, which takes a string, convert it as a list of chars and call the p (parse) predicate with an empty stack as a second argument.

Predicate p calls itself recursively with an appropriately modified stack (look for [H|T] destructuring and constructor patterns). When called on the base case, where the input list is empty, p prints the unique element of the stack. If the stack has less or more than one element at this point, it means that we have an empty input string, a bad input string or a bug (with an emtpy string, the predicate fails (Prolog says No), but nothing is printed, which is ok, since we should not print anything for empty strings).

Solving

The stack contains a description of the constructed rectangles, denoted S:W:H, where S is a symbolic representation of the rectangle, W its width and H its height (note, A:B is syntactic sugar for the :(A,B) tuple with a functor named :; it is just shorter to write than having a tuple with prefix notation).

With A and B sub-rectangle specifications, S can be either:

• h(A,B) : horizontal concat of A and B
• v(A,B) : vertical concat of A and B
• f(C) : fill with C, where C is a character code

Widths and heights of grids are constraint-programming variables: during vertical (resp. horizontal) concatenation, the width (resp. height) of the manipulated rectangles are unified, whereas the resulting height (resp. width) is constrained to be the sum of each subgrid's height (resp. width).

The labeling step at the end of the process instanciates variables while respecting constraints, using the minimal possible values (this is a property of the order by which solutions are tried).

I might have obtained a shorter answer using the same reasonning that is done in other answers, without constraints, but this is too late now.

Note also that because the default domain for variables is set to 1..100, there is a limitation over the possible sizes of grids. The upper-bound could be changed if needed. The performance implications of this are that it could take a lot of time to determine that a particular solution admits no solution. I said "could" because constraints are likely to drastically prune the exponential search. If you find an input string that is hard/costly to reject, please share.

Printing

The printing part is interesting because there is a kind of ray-casting algorithm over the structure: I iterate over each cell of the resulting grid, from point (1,1) to point (W,H) and call the w predicate to print the content of the grid in the main tree, at this location (of course, a newline is printed after processing each line).

In w, positions are relative to current grid (the root grid defines absolute coordinates).

When printing a h(A,B) structure at point (X,Y), I unconditionnaly print in both branches:

• in grid A at point (X,Y), and
• in grid B at point (H,Y), where H is X minus the width of A.

The leaf branches of the grid-tree, f(C), finally either print the character C, if the relative location is inside the grid, or do nothing. This is how I can print the content of grid to the output stream, from top to bottom, from left to right. No actual arrays are produced.

Tests

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.

Running test:

[eclipse] tt.
jronze
aronze
ggoidd
uuuuuuun
coyriggl
coyrihhl
coyrittl
ppyriabe
cccoy
mmply
exify
a
Yes (0.00s cpu)

• edc65: +1 No actual arrays are produced. that's how it should be done. Overkill in this case, as the grammar is so simple and there are shortcuts.
• coredump: @edc65 Yes, it's overkill. But since it is codegolf, I tried to minimize size, and manipulating arrays would have been too verbose.

Answer 3

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 is a function which takes a specification and gives a 2D array of characters. If you want a more user-friendly version, add this line to make it take a specification from stdin and print out the grid:

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

Test Cases

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

Explanation

The strategy is simple: if a grid G is valid for a specification S, then repeating the rightmost column of G also gives a valid specification for S, and the same is true with repeating the bottom row (the proof of this is by structural induction on S). Therefore, when we want to concatenate two rectangles, we can simply append the last column/row of the smaller one until they match in size (this is what the function p does).

Answer 4

Haskell, (削除) 388 (削除ここまで) (削除) 367 (削除ここまで) 352 bytes

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

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

Test run with pretty printing:

> 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

How it works: the function # parses the input string into the tree structure C which is either a leaf L holding the character to print or a node N. N can be a) a side-by-side join (t==2), b) a top-bottom join (t==1) or c) a single letter square (t==0). All nodes have a width and height field and a left and right child. After parsing, p prints the remaining root node by recursively adjusting the size (width x height) of it's child nodes and joining them.

Edit: output as a list of lines instead of pretty printing

Answer 5

JavaScript (ES6), 283 (削除) 295 (削除ここまで)

Edit Now this (heavily golfed) JS solution is at least shorter than the reference (quite golfable) Python solution.

Similar to cardboard_box, just repeating the leftmost column or the topmost row.

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 This is my first, ungolfed solution.

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

Test In Firefox/FireBug console

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

Output

pas
prs
eee
comp
iler
cccoy
mmply
exify
jronze
aronze
ggoidd
uuuuuuun
coyriggl
coyrihhl
coyrittl
ppyriabe

Answer 6

Python 3, 251 bytes

Here's the reference answer I promised, golfed a bit further.

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

This is a full program that takes the string from STDIN and prints to STDOUT. The approach is the same as that of cardboard_box: push a 1x1 array for a character, and duplicate rows if needed for concatenation.

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

Detailed explanation

• T transposes a given list of lists. The majority of the work is done by zip(*m) which swaps rows to columns, the rest is just converting the result into a list of lists, since zip returns a generator of tuples.
• E(a,b) returns a with its first element repeated enough times to match the length of b. Note that multiplying a list by a negative number gives the empty list, so if b is shorter than a, this returns a.
• H(a,b) returns the horizontal concatenation of a and b, the shorter one being lengthened by E if necessary.
• s is the stack.
• In the for loop, we iterate over the input string, and replace s by a new value: if it's | (greater than z), we pop two values and push their H, if it's - (lower than a), we pop two values, transpose, feed to H, transpose again and push the result, and otherwise push a 1x1 array with the letter.
• Finally, we print the first element of s.