Return to Answer

Grime is based on Boolean grammars. The basic idea is to construct rectangular patterns from smaller components, and check whether they are found in the input matrix. So far, Grime only supports rectangular matches, and solves at least 10 problems more or less elegantly.

EDIT: options can now be specified within the grammar, by inserting them before any line and adding a comma , (see below for examples).

• Any character escaped with \ matches any 1x1 rectangle containing that character.
• . matches any single character.
• $ matches a 1x1 rectangle outside the character matrix.
• _ matches any rectangle of zero width or height.
• The pre-defined character groups are digit, uppercase, lowercase, alphabetic, alphanumeric, and symbol.
• New character classes can be defined by the syntax [a-prt-w,d-gu]. The letters on the left are included, and those on the right are excluded, so this matches exactly the letters abchijklmnoprtvw. If the left side is empty, it is taken to contain all characters. The comma can be omitted if the right side is empty. The characters [],-\ must be escaped with \.
• An unescaped uppercase letter is a nonterminal, and matches the expression it is assigned.
• If P and Q are expressions, then PQ is just their horizontal concatenation, and P/Q is their vertical concatenation, with P on top.
• P+ is one or more Ps aligned horizontally, and P/+ is the same aligned vertically.
• The Boolean operations are denoted P|Q, P&Q and P!.
• P? is shorthand for P|_, P* for P+|_, and P/* for P/+|_.
• P# matches any rectangle that contains a match of P.

• Faster matching. Currently, the interpreter does not take into account the fact that, for example, . can only match 1x1 rectangles. Until it finds a match, it tries all rectangles of all sizes in order, instantly failing for each of them.

• Operations to constrain the size of expressions. Nether portals is very hard without it.

• Rotation and reflection operations, for the word search and glider challenges.

• Non-rectangular matches using contexts, which would be helpful in the Boggle board challenge. For example, Pv(Q>R) means P with bottom context (Q with right context R). It would match the L-shaped patterns

    PPP
    PPP
    QQQRRRR
    QQQRRRR
    QQQRRRR
  

dd+/(dd+)/+

This is simple: two or more rows of two or more digits.

A=[,qQ]
B=AAAA
B/B/B/B

I think I forgot to put this here earlier, even though it was very simple even without the character classes. Anyway, here we have two nonterminals A and B (basically just for shortening the grammar). A matches any character that is not q or Q, which is achieved by a newly implemented character class. B is just four As in a row, and the toplevel nonterminal is four Bs on top of each other.

S=[#_]
B=SSS+
(\#\#|\#/\#|\_\_|\_/\_)#!&B/B/B/+

I'm using S and B as auxiliary nonterminals to make the grammar shorter. The right-hand side B/B/B/+ matches any 3x3 or larger rectangle of #s and _s, while the left-hand side guarantees that it does not contain two adjacent #s or _s. Note the character class in the definition of S.

This is basically the same as above, except that we can match any non-empty rectangle.

Grime is based on Boolean grammars. The basic idea is to construct rectangular patterns from smaller components, and check whether they are found in the input matrix. So far, Grime only supports rectangular matches, and solves at least 11 problems more or less elegantly.

EDIT3: Implemented size constraints, and added the Nether portals problem.

Options can also be specified within the grammar, by inserting them before any line and adding a comma , (see below for examples).

• Any character escaped with \ matches any 1x1 rectangle containing that character.
• . matches any single character.
• $ matches a 1x1 rectangle outside the character matrix.
• _ matches any rectangle of zero width or height.
• The pre-defined character groups are digit, uppercase, lowercase, alphabetic, alphanumeric, and symbol.
• New character classes can be defined by the syntax [a-prt-w,d-gu]. The letters on the left are included, and those on the right are excluded, so this matches exactly the letters abchijklmnoprtvw. If the left side is empty, it is taken to contain all characters. The comma can be omitted if the right side is empty. The characters [],-\ must be escaped with \.
• An unescaped uppercase letter is a nonterminal, and matches the expression it is assigned.
• If P and Q are expressions, then PQ is just their horizontal concatenation, and P/Q is their vertical concatenation, with P on top.
• P+ is one or more Ps aligned horizontally, and P/+ is the same aligned vertically.
• The Boolean operations are denoted P|Q, P&Q and P!.
• P? is shorthand for P|_, P* for P+|_, and P/* for P/+|_.
• P# matches any rectangle that contains a match of P.
• P{a-b,c-d}, where abcd are nonnegative integers, is a size constraint on P. If P is a character class, then the expression matches any mxn rectangle containing only those characters, provided that m is between a and b inclusive, and n is between c and d inclusive. In other cases, the expression matches any rectangle that has the correct size and that P also matches. If a or c are omitted, they are taken to be 0, and if b or d are omitted, they are infinite. If the hyphen between a and b is omitted, then we use the same number for both ends of the interval. If the entire c-d part is omitted, both axes are constrained. To clarify, {-b} is equivalent to {0-b,0-b}, and {a-,c} is equivalent to {a-infinity,c-c}.

• Faster matching. Currently, the interpreter does not take into account the fact that, for example, . can only match 1x1 rectangles. Until it finds a match, it tries all rectangles of all sizes in order, instantly failing for each of them.

• Rotation and reflection operations, for the word search and glider challenges.

• Non-rectangular matches using contexts, which would be helpful in the Boggle board challenge. For example, Pv(Q>R) means P with bottom context (Q with right context R). It would match the L-shaped patterns

    PPP
    PPP
    QQQRRRR
    QQQRRRR
    QQQRRRR
  

d{2-}

This is simple: a rectangle of digits of size at least 2x2.

[,qQ]{4}

This is almost as simple as the first one; now we have a more restricted size and a custom character class.

Nether Portals

.\X+./\X/+\.{2-22,3-22}\X/+/.\X+.

With the size restriction operator, this one's not that hard. The middle part \.{2-22,3-22} matches any rectangle of . of the correct sizes, and then we just add columns of Xs on both sides, and tack rows of Xs with ignored ends on the top and bottom of that.

(\#\#|\#/\#|\_\_|\_/\_)#!&[#_]{3-}

The right-hand side [#_]{3-} matches any 3x3 or larger rectangle of #s and _s, while the left-hand side guarantees that it does not contain two adjacent #s or _s.

This is basically the same as above, except that we can match any non-empty rectangle, but need to use the e flag for entire input verification.

EDIT2: Added character classes, inspired by those of Slip. Also changed the syntax of option flags and improved the expression parser.

EDIT2: Added character classes, inspired by those of Slip. Also changed the syntax of option flags, improved the expression parser, and added the no-Q problem.

EDIT: options can now be specified within the grammar, by inserting them before any line and adding a backtick (see below for examples).

• Any character escaped with \ matches any 1x1 rectangle containing that character.
• . matches any single character.
• $ matches a 1x1 rectangle outside the character matrix.
• _ matches any rectangle of zero width or height.
• The pre-defined character groups are digit, uppercase, lowercase, alphabetic, alphanumeric, and symbol.
• An unescaped uppercase letter is a nonterminal, and matches the expression it is assigned.
• If P and Q are expressions, then PQ is just their horizontal concatenation, and P/Q is their vertical concatenation, with P on top.
• P+ is one or more Ps aligned horizontally, and P/+ is the same aligned vertically.
• The Boolean operations are denoted P|Q, P&Q and P!.
• P? is shorthand for P|_, P* for P+|_, and P/* for P/+|_.
• P# matches any rectangle that contains a match of P.

Grime does allow paradoxical definitions of the form A=A! with undefined behavior. However, they will not cause crashes or infinite loops.

My parser is not as smart as I would like it to be. In particular, it cannot handle espressions of the type A#!, so I have to insert parentheses: (A#)!. This can be seen in the chessboard examples. Use the debug flag to check your expressions, if you notice anything strange.

• Faster matching. Currently, the interpreter does not take into account the fact that, for example, . can only match 1x1 rectangles. Until it finds a match, it tries all rectangles of all sizes in order, instantly failing for each of them.

• Regex-like character ranges, like [a-dm-s] for matching any character in abcdmnopqrs.

• Operations to constrain the size of expressions. Nether portals is very hard without it.

• Rotation and reflection operations, for the word search and glider challenges.

• Non-rectangular matches using contexts, which would be helpful in the Boggle board challenge. For example, Pv(Q>R) means P with bottom context (Q with right context R). It would match the L-shaped patterns

    PPP
    PPP
    QQQRRRR
    QQQRRRR
    QQQRRRR
  

S=.|S./+/.+
e`S

Here we have our first nonterminal, S. This grammar is very simple, it basically defines that a square is either a 1x1 rectangle, or a smaller square with one column tacked on its right edge, and one row tacked to the bottom of that. Note also the e option before the toplevel nonterminal, which toggles entire-input verification.

S=\#|\_
B=SSS+
((\#\#|\#/\#|\_\_|\_/\_)#)!&B/B/B/+

I'm using S and B as auxiliary nonterminals to make the grammar shorter. The right-hand side B/B/B/+ matches any 3x3 or larger rectangle of #s and _s, while the left-hand side guarantees that it does not contain two adjacent #s or _s.

e`((\#\#|\#/\#|\_\_|\_/\_)#)!&(\#|\_)+/+

A=(.&(\(|\))!)/*
P=A*|P(A/\(/A)P(A/\)/A)P
e`P

EDIT2: Added character classes, inspired by those of Slip. Also changed the syntax of option flags and improved the expression parser.

EDIT: options can now be specified within the grammar, by inserting them before any line and adding a comma , (see below for examples).

• Any character escaped with \ matches any 1x1 rectangle containing that character.
• . matches any single character.
• $ matches a 1x1 rectangle outside the character matrix.
• _ matches any rectangle of zero width or height.
• The pre-defined character groups are digit, uppercase, lowercase, alphabetic, alphanumeric, and symbol.
• New character classes can be defined by the syntax [a-prt-w,d-gu]. The letters on the left are included, and those on the right are excluded, so this matches exactly the letters abchijklmnoprtvw. If the left side is empty, it is taken to contain all characters. The comma can be omitted if the right side is empty. The characters [],-\ must be escaped with \.
• An unescaped uppercase letter is a nonterminal, and matches the expression it is assigned.
• If P and Q are expressions, then PQ is just their horizontal concatenation, and P/Q is their vertical concatenation, with P on top.
• P+ is one or more Ps aligned horizontally, and P/+ is the same aligned vertically.
• The Boolean operations are denoted P|Q, P&Q and P!.
• P? is shorthand for P|_, P* for P+|_, and P/* for P/+|_.
• P# matches any rectangle that contains a match of P.

Grime does allow paradoxical definitions like A=A! with undefined behavior. However, they will not cause crashes or infinite loops.

• Faster matching. Currently, the interpreter does not take into account the fact that, for example, . can only match 1x1 rectangles. Until it finds a match, it tries all rectangles of all sizes in order, instantly failing for each of them.

• Operations to constrain the size of expressions. Nether portals is very hard without it.

• Rotation and reflection operations, for the word search and glider challenges.

• Non-rectangular matches using contexts, which would be helpful in the Boggle board challenge. For example, Pv(Q>R) means P with bottom context (Q with right context R). It would match the L-shaped patterns

    PPP
    PPP
    QQQRRRR
    QQQRRRR
    QQQRRRR
  

No q or Q

A=[,qQ]
B=AAAA
B/B/B/B

I think I forgot to put this here earlier, even though it was very simple even without the character classes. Anyway, here we have two nonterminals A and B (basically just for shortening the grammar). A matches any character that is not q or Q, which is achieved by a newly implemented character class. B is just four As in a row, and the toplevel nonterminal is four Bs on top of each other.

S=.|S./+/.+
e,S

This grammar is very simple, it basically defines that a square is either a 1x1 rectangle, or a smaller square with one column tacked on its right edge, and one row tacked to the bottom of that. Note also the e option before the toplevel nonterminal, which toggles entire-input verification.

S=[#_]
B=SSS+
(\#\#|\#/\#|\_\_|\_/\_)#!&B/B/B/+

I'm using S and B as auxiliary nonterminals to make the grammar shorter. The right-hand side B/B/B/+ matches any 3x3 or larger rectangle of #s and _s, while the left-hand side guarantees that it does not contain two adjacent #s or _s. Note the character class in the definition of S.

e,(\#\#|\#/\#|\_\_|\_/\_)#!&[#_]+/+

A=[,()]/*
P=A*|P(A/\(/A)P(A/\)/A)P
e,P