Puzzling Language
Contest: April Fools Contest 2018
Difficulty rating: 2200
Tags: constructive algorithms

In this problem you will write a simple code generator for a 2D programming language derived from Brainfuck.

The code in this language is a rectangular grid of characters '.' and 'X'. The code is converted to a Brainfuck program as follows: the characters are read in the usual order (top to bottom, left to right), and each 'X' character is converted a Brainfuck instruction to be executed. The instruction is defined by the left, top and right neighbors of the 'X' character using the following conversion table:

You are given a string. Output a program in the described language which prints this string.

You can download the language interpreter used for judging here: https://assets.codeforces.com/rounds/952/puzzling-interpreter.cpp (use C++11 to compile the code). Note several implementation details:

- The first step of the language interpretation is conversion to a Brainfuck program, which is then executed.
- The code must be rectangular, with all lines of the same length. It can have at most 10,000 lines and 10,000 columns, and can have at most 500,000 'X' characters.
- The code has toroidal topology, i.e. the 'X' on the first line will have top neighbor in the last line.
- Brainfuck interpreter has 30000 memory cells which store integers from 0 to 255 with increment/decrement done modulo 256.
- Console input (, command) is allowed in Brainfuck code but has no effect when executed.

Input format:
The input consists of a single string of characters with ASCII codes between 33 ('!') and 122 ('z'), inclusive. The length of the string is between 1 and 10 characters, inclusive.

Output format:
Output a program in the described language which, when executed, will print the given message.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
The example corresponds to the following Brainfuck program:

The triangular block decrements the first memory cell and sets the value of the second memory cell to 36 - the ASCII code of '$' character. The next line after the triangular block moves the memory pointer to the second memory cell, and the next three lines print the '$' character three times.

Example input:
$$$

Example output:
.......X.......
......XXX......
.....XXXXX.....
....XXXXXXX....
...XXXXXXXXX...
..XXXXXXXXXXX..
.XXXXXXXXXXXXX.
...............
X.............X
X..............
X..............
X..............

Editorial:
"Puzzling language" featured in this problem is Orthogonal Puzzlang (a less studied variant of Puzzlang).
There are multiple ways to approach code generation in this language.
The method shown in the example was not the easiest possible, and was chosen quite deliberately :-) But it is possible to develop it further - use triangular blocks of Xs to increment value in a cell and then carefully navigate to the right cell and print its contents. This requires a lot of care when dealing with multiple symbols, increments which are not square numbers (a triangular block of Xs corresponds to an increment by a square number, and yes, $ sign in the example with ASCII code 36 was not a random choice) and so on.
My reference solution used a much easier approach. The simplest command to generate in Puzzlang is decrement - it is just a standalone 'X'. And due to the fact that memory cells in Brainfuck wrap around, you can get any value in a memory cell starting with any other value and decrementing it the right number of times. The generated program can have only 2 columns, with '-' (decrement) instruction implemented as
and '.' (print) instruction implemented as
This approach can be optimized further without adding too much complexity: my actual reference solution still generated 2-column programs but encoded both decrement and print instructions as either ".X" or "X." depending on the previous instruction, so that decrement 'X's formed a chessboard pattern, and print 'X's were right below the 'X's of previous instructions. This reduced the size of the program by a factor of 2.
Another solution I implemented didn't use wrap around of memory cells, but instead relied on torus topology of the program. I used a program with 2 columns again, with the same implementation of decrement and print instructions as in the previous approach. A sequence of 2*N increment instructions could be represented as a block of N+1 "XX" lines. The first line of the block would be interpreted as ",,", but the interpreter is permissive enough to just ignore these instructions. Every line of the block after that is interpreted as "++". This approach typically generates shorter programs but requires a bit more care when implementing it - I got it quite right only on the fourth try :-)