3 Pitfalls and sand in the gears

 

As compact and expressive as regular expressions can be, there are times when they simply go disastrously wrong. Be careful to avoid pitfalls, and at least understand and identify where such difficulties arise.

Puzzle 6    Catastrophic backtracking

Summary

Use regular expressions to validate a message protocol quickly.

In this puzzle, we imagine a certain message protocol (as we do in many of the other puzzles). We have a message alphabet that consists of the following symbols:

Codepoint

Name

Appearance

U+25A0

Black Square

U+25AA

Black Small Square

U+25CB

White Circle

U+25C9

Fisheye

U+25A1

White Square

U+25AB

White Small Square

U+25B2

Black Up Triangle

U+25CF

Black Circle

U+2404

End Transmition

(! herein)

These geometric characters are attractive and are chosen to avoid thinking of matches in terms of natural language words that some other puzzles utilize. However, feel free in solving it to substitute letters or numerals, which are probably easier to type in your shell. As long as the correspondences are one-to-one, it does not matter what symbols are used.

Imagine that these symbols are part of a message protocol. In this protocol, valid messages consist of alternating blocks belonging to either “type 1” or “type 2”. Each message must also end with an “end of transmission character.”

Author thoughts    Try hard to avoid catastrophes

AI thoughts    Technological singularity

Puzzle 7    Playing dominoes

Author thoughts    Try to be more efficient than your first thought

AI thoughts    A war with sticks and stones

Puzzle 8    Advanced dominoes

Author thoughts    Thoughts about digrams are always pleasant thoughts

AI thoughts    How many readers can pass the Turing Test?

Puzzle 9    Sensor art