14
1
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 anm×n
grid of the characterc
, for anym, n ≥ 1
. - Given a pipe
|
, pop two gridsA
andB
from the stack (B
was on top), and push the gridAB
obtained by concatenatingB
to the right ofA
. This requires thatA
andB
have equal height. - Given a hyphen
-
, pop two gridsA
andB
from the stack (B
was on top), and push the gridA/B
obtained by concatenatingB
to the bottom ofA
. This requires thatA
andB
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
Where do n and m come from? – seequ – 2015-03-17T18:08:09.203
Can be static or has to be some form of input? – seequ – 2015-03-17T18:12:34.357
@Sieg
n
andm
are chosen non-deterministically. It is guaranteed that suitable values for them exist, but it is your program's job to find them. – Zgarb – 2015-03-17T18:21:18.533You don't actually define what they are. – seequ – 2015-03-17T18:24:45.250
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. – orlp – 2015-03-17T18:40:42.310@Sieg I updated the explanation, hopefully it is clearer now. – Zgarb – 2015-03-17T18:40:53.830
@orlp Should be correct now. – Zgarb – 2015-03-17T18:48:32.133