Bounded Cellular Automata

Stephen Wolfram describes one dimensional cellular automata in his book "A New Kind of Science". The squares sit in a row and each square is either black or white. A new row is built from the previous row alone. The next color of a square comes from three squares of the previous row: the square itself and its two neighbors.

Three squares give eight color combinations. Take black as 1 and white as 0, multiply the left square by 4, the middle square by 2 and the right square by 1, then add them to get a position number. Write the rule number in binary. If the bit at that position is 1, the middle square becomes black on the next step, and if it is 0 the middle square becomes white. Rule numbers run from 0 to 255.

254 in binary is 11111110, so rule 254 gives white only when all three squares are white and gives black in the other seven cases. Start from a row whose middle square alone is black and apply rule 254 over and over, and a black triangle grows.

The bounded automata

Unlike the automata in "A New Kind of Science", the automata in this problem move inside a bounded space.

• A row has exactly $n$ squares. The first square and the last square are always white, whatever the rule is. An automaton looks at the first and last squares while deciding the new colors of the second square and the second to last square, but it cannot change the first or last square itself.
• A bounded automaton always starts on a row with an odd number of squares. At step 1 the middle square alone is black and every other square is white.
• $n$ comes from the string being searched for, that is, the length of the second field on the input line.

The program

For every line of input, find every one of the 256 rules that produces that row within the given maximum step number, starting from the standard start state. If no rule produces it, print NONE. If several rules produce it, print all of them in the output format below.

• Each line of input holds two fields separated by one space.
• The first field is the maximum step number max_step for the automata to run. This number can be up to 32 bits. Values are chosen so that the problem is solvable within the given time limit for the given input specifications.
• The second field is a string of characters standing for the squares on a row. It is not longer than 256 characters and can be shorter. The length of this field is $n$.
• The character W stands for a white square and B stands for a black square.
• If the string holds a character other than W or B, or breaks the bounding condition described above, that is, it has even length or a black square at either end, then no automaton can produce that row. The answer for such a line is NONE.
• Every line of input ends with a newline character.
• Input ends with a single line holding END OF INPUT. That line is not part of the search.

• Print one output line for each input line.
• An output line starts with LINE, one space, then the number of the input line. Line numbers start at 1, and a line whose answer is NONE still takes a number.
• After the line number print one space, then the (rule,step) pairs that produced the row, joined with nothing between them. rule is the number of the automaton, from 0 to 255, and step is the first step at which that automaton produced the row, from 1 to max_step.
• If several rules produce the row on or before the maximum step number, print all of them in increasing order of rule number.
• If no rule produces the row on or before the maximum step number, print NONE in place of the pairs.
• An output line looks like LINE 2 (15,8)(158,11) or LINE 4 NONE.