Your friend wanted to send you a sequence of digits (possibly starting with some leading zeros). As the network may be faulty, you asked him to use an error correction code.
Because your friend is a prankster, they sent each digit as an image of the English word for that digit.
Unfortunately, the network did indeed introduce some noise, and you now have to decode the original sequence of digits.
The bitmaps that originally represented the digits are available for download here: D_digits.txt
The bitmaps represent the digits from 0 to 9 in this order. Each bitmap is a rectangle of periods and hashes (‘.’ and ‘#’).
There is a blank line between consecutive bitmaps. These blank lines are present just for clarity, they are not a part of the individual images.
The bitmaps can also be viewed here:
.............................
.............................
.............................
.............................
.............................
.######.######.######.######.
....##..#....#.#....#.#....#.
...##...######.#......#....#.
..##....#......#......#....#.
.######.######.#......######.
.............................
.............................
.............................
.............................
.............................
......................
......................
......................
......................
......................
.######.######.######.
.#....#.#....#.#....#.
.#....#.#....#.######.
.#....#.#....#.#......
.######.#....#.######.
......................
......................
......................
......................
......................
............................
....#.......................
....#.......................
.#######....................
....#.......................
....#....#....#....#.######.
....#....#....#....#.#....#.
....#....##..###..##.#....#.
....#.....####.####..#....#.
....#......##...##...######.
............................
............................
............................
............................
............................
.....................................
....#....#...........................
....#....#...........................
.#######.#...........................
....#....#...........................
....#....######.######.######.######.
....#....#....#.#....#.#....#.#....#.
....#....#....#.#......######.######.
....#....#....#.#......#......#......
....#....#....#.#......######.######.
.....................................
.....................................
.....................................
.....................................
.....................................
............................
.#####......................
.#...#......................
.#...#......................
.#..........................
.###...######.#....#.######.
.#.....#....#.#....#.#....#.
.#.....#....#.#....#.#......
.#.....#....#.#....#.#......
.#.....######.######.#......
............................
............................
............................
............................
............................
.......................
.#####.................
.#...#.................
.#...#.#...............
.#.....................
.###...#.#....#.######.
.#.....#.#....#.#....#.
.#.....#.##..##.######.
.#.....#..####..#......
.#.....#...##...######.
.......................
.......................
.......................
.......................
.......................
.................
.................
.................
........#........
.................
.######.#.#....#.
.#......#.##..##.
.######.#..####..
......#.#.##..##.
.######.#.#....#.
.................
.................
.................
.................
.................
....................................
....................................
....................................
....................................
....................................
.######.######.#....#.######.######.
.#......#....#.#....#.#....#.#....#.
.######.######.##..##.######.#....#.
......#.#.......####..#......#....#.
.######.######...##...######.#....#.
....................................
....................................
....................................
....................................
....................................
................................
.................#.........#....
.................#.........#....
........#........#......#######.
.................#.........#....
.######.#.######.######....#....
.#....#.#.#....#.#....#....#....
.######.#.#....#.#....#....#....
.#......#.#....#.#....#....#....
.######.#.######.#....#....#....
...............#................
...............#................
..........#....#................
..........######................
................................
........................
........................
........................
........#...............
........................
.######.#.######.######.
.#....#.#.#....#.#....#.
.#....#.#.#....#.######.
.#....#.#.#....#.#......
.#....#.#.#....#.######.
........................
........................
........................
........................
........................The noise introduced during the transmission can be described as a series of operations performed on the original image. There are three types of operations.
The image is rotated counter-clockwise by 90 degrees. Below you can see the image for “one” rotated zero to four times.
...................... ............... ...................... ............... ......................
...................... .....###.#..... ...................... .....#####..... ......................
...................... .....#.#.#..... ...................... .....#...#..... ......................
...................... .....#.#.#..... ...................... .....#...#..... ......................
...................... .....#.#.#..... ...................... .....#...#..... ......................
.######.######.######. .....#.#.#..... .######.#....#.######. .....#...#..... .######.######.######.
.#....#.#....#.#....#. .....#####..... ......#.#....#.#....#. .....#####..... .#....#.#....#.#....#.
.#....#.#....#.######. ............... .######.#....#.#....#. ............... .#....#.#....#.######.
.#....#.#....#.#...... .....#####..... .#....#.#....#.#....#. .....#####..... .#....#.#....#.#......
.######.#....#.######. .....#......... .######.######.######. .........#..... .######.#....#.######.
...................... .....#......... ...................... .........#..... ......................
...................... .....#......... ...................... .........#..... ......................
...................... .....#......... ...................... .........#..... ......................
...................... .....#####..... ...................... .....#####..... ......................
...................... ............... ...................... ............... ......................
.....#####..... .....#####.....
.....#...#..... .....#.#.#.....
.....#...#..... .....#.#.#.....
.....#...#..... .....#.#.#.....
.....#...#..... .....#.#.#.....
.....#####..... .....#.###.....
............... ............... Each row of the image is reversed. Below you can see the image for “four” flipped.
............................ ............................
.#####...................... ......................#####.
.#...#...................... ......................#...#.
.#...#...................... ......................#...#.
.#.......................... ..........................#.
.###...######.#....#.######. .######.#....#.######...###.
.#.....#....#.#....#.#....#. .#....#.#....#.#....#.....#.
.#.....#....#.#....#.#...... ......#.#....#.#....#.....#.
.#.....#....#.#....#.#...... ......#.#....#.#....#.....#.
.#.....######.######.#...... ......#.######.######.....#.
............................ ............................
............................ ............................
............................ ............................
............................ ............................
............................ ............................Two adjacent rows are chosen, and a new row is inserted between them. For each column, the character in the newly inserted row will be the same as one of the characters of the original two chosen rows. In other words, each character of the newly inserted row will be equal to the one above it, or the one below it (or to both, if they are the same).
Here is an example distortion, where we choose rows 7 and 8 (numbered from 1 from the top) in the image for “seven”, and insert a new row between them:
.................................... ....................................
.................................... ....................................
.................................... ....................................
.................................... ....................................
.................................... ....................................
.######.######.#....#.######.######. .######.######.#....#.######.######.
.#......#....#.#....#.#....#.#....#. .#......#....#.#....#.#....#.#....#.
.######.######.##..##.######.#....#. .#.#....#.#..#.#....#.######.#....#.
......#.#.......####..#......#....#. .######.######.##..##.######.#....#.
.######.######...##...######.#....#. ......#.#.......####..#......#....#.
.................................... .######.######...##...######.#....#.
.................................... ....................................
.................................... ....................................
.................................... ....................................
.................................... ....................................
....................................You will be given a series of images. It is guaranteed that each one started as one of the original ten bitmaps shown above and then it was distorted by applying zero or more operations described above, one after another.
For each image, find out which digit it represents. It is guaranteed that for the given original images of the digits and the types of operations performed, this can always be determined.
The first line of each input file contains the number \(t\): the number of digits that were being transmitted. A description of each digit follows.
The first line of the description contains the numbers \(r\) and \(c\): the number of rows and columns of the received image.
Then, \(r\) lines of \(c\) characters follow. Each character is
either . or #.
It is guaranteed that the image can be obtained by starting with one of the original images of a digit, and applying zero or more operations described in the section “Noise”.
Output \(t\) lines. In the \(i\)-th line, output the digit which the \(i\)-th image represents.
Input file: D1.in
Constraints: \(1 \leq t \leq 100\), \(15 \leq r,c \leq 38\), and it is guaranteed that the operation “Row distortion” was never applied. (I.e., each bitmap in this input file has only been rotated and/or flipped arbitrarily many times.)
Input file: D2.in
Constraints: \(1 \leq t \leq 10\), \(15 \leq r,c \leq 80\).
Input file: D3.in
Constraints: \(1 \leq t \leq 4\,000\), \(15 \leq r,c \leq 180\), the sum of \(r \cdot c\) across the entire input file is not greater than \(10^7\), and each image represents an even digit (zero is even).
Input file: D4.in
Constraints: \(1 \leq t \leq 4\,000\), \(15 \leq r,c \leq 180\), the sum of \(r \cdot c\) across the entire input file is not greater than \(10^7\).
input3 32 45 ............................................. .....................##.#.###................ ....................#########................ ....................#########................ ....................#########................ ....................####.####................ ....................###..###................. ....................###..###................. ....................###..###................. ....................##....##................. ....................##....................... ....................#........................ ....................##....................... ......#......#....#.#########.#.############. ......#......#....#.##....###.#............#. ......#......#....#.##....###.#.#.##########. ......##.....#....#.##....###.#.#.##########. ......#......#....#.##....###.#.############. ......##.....#....#.##....###.#.#..........#. ......##.....######.#########.#.############. ......##..........#.......................... ..#..###.###......#.......................... .##..#######......#.......................... .##..#######......#.......................... .###########......#...........#.............. .###########......#...........#.............. ......#...........#.......................... ......#...........#.......................... ......#...........#.......................... ......#...........#.......................... ......##..................................... ............................................. 15 22 ...................... ...................... ...................... ...................... ...................... .######.######.######. .#....#.#....#.#....#. .#....#.#....#.######. .#....#.#....#.#...... .######.#....#.######. ...................... ...................... ...................... ...................... ...................... 39 30 .............................. ............#########......... ............#................. ............##................ ............#................. ............##................ ............##................ ............##................ ............###.##.##......... ............#########......... .............#####............ .............#####............ .............................. ..........#.#########......... ..........#.#########......... ..........#......##........... ..........#......##........... .................##........... .............................. ............#########......... ............##................ ............##................ ............##................ ............##................ ............##................ ............##................ ............##................ ............##................ ............#########......... ............##..####.......... .............................. ............######..#......... ............#########......... ............#...#.###......... ............##.##.###......... ............##.##.###......... ............##.##...#......... ............#####.###......... .............................. | output8 1 9 |