#include "testlib.h"

#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <utility>

/*
 * Colours are:
 *   RED, ORANGE, YELLOW, GREEN, BLUE, VIOLET
 * Whitespace in the image is a dot symbol for formatting purposes.
 * So, counting holes in letters, the sequences are:
 *   RED: 101
 *   ORANGE: 111000
 *   YELLOW: 000010
 *   GREEN: 01000
 *   BLUE: 2000
 *   VIOLET: 001000
 * and we have three colours with unique lengths and three more colours with length 6
 * but with different hole count sequences.
 *
 * The answer is correct if:
 * - all lines are of the same length
 * - this length does not exceed 100
 * - the number of lines does not exceed 10
 * - all non-dot symbols are capital English letters
 * - letters come left to right (their bounding boxes along the X axis do not intersect or touch)
 * - the hole count sequence match the first colour requested in the test
 * - there is one or more substring matching the second colour requested in the test, with dots around
 * - for any other colour, including the first requested, it does not appear as a substring
 *   (even with extra symbols on the ends)
 */

std::map<char, unsigned> holes {
    std::make_pair('A', 1), std::make_pair('B', 2), std::make_pair('C', 0), std::make_pair('D', 1),
    std::make_pair('E', 0), std::make_pair('F', 0), std::make_pair('G', 0), std::make_pair('H', 0),
    std::make_pair('I', 0), std::make_pair('J', 0), std::make_pair('K', 0), std::make_pair('L', 0),
    std::make_pair('M', 0), std::make_pair('N', 0), std::make_pair('O', 1), std::make_pair('P', 1),
    std::make_pair('Q', 1), std::make_pair('R', 1), std::make_pair('S', 0), std::make_pair('T', 0),
    std::make_pair('U', 0), std::make_pair('V', 0), std::make_pair('W', 0), std::make_pair('X', 0),
    std::make_pair('Y', 0), std::make_pair('Z', 0)
};

std::set<std::string> colours {
    "RED",
    "ORANGE",
    "YELLOW",
    "GREEN",
    "BLUE",
    "VIOLET"
};

std::string read_colour(InStream &str) {
    std::string rv = str.readLine();
    if (colours.find(rv) == colours.end()) {
        quitf(_fail, "Unexpected colour: '%s'", rv.c_str());
    }
    return rv;
}

int DR[] = {1, 0, -1, 0};
int DC[] = {0, 1, 0, -1};

unsigned flood_fill(std::vector<std::string> &lines, unsigned row, unsigned col, char from, char to) {
    if (row >= lines.size() || col >= lines[row].length() || lines[row][col] != from) {
        quitf(_fail, "Assert: flood fill failed, unexpected char");
    }
    lines[row][col] = to;
    unsigned max_col = col;

    for (int i = 0; i < 4; ++i) {
        int dr = DR[i];
        int dc = DC[i];
        if (dr == -1 && row == 0) continue;
        if (dc == -1 && col == 0) continue;
        if (dr == +1 && row + 1 == lines.size()) continue;
        if (dc == +1 && col + 1 == lines[0].length()) continue;
        if (lines[row + dr][col + dc] != from) continue;
        unsigned rv = flood_fill(lines, row + dr, col + dc, from, to);
        max_col = std::max(max_col, rv);
    }
    return max_col;
}

int main(int argc, char *argv[]) {
    setName("Checker for 'Colourful Captcha'");
    registerTestlibCmd(argc, argv);

    std::string big_colour = read_colour(inf);
    std::string small_colour = read_colour(inf);

    // 1. Read all input lines
    std::vector<std::string> lines;
    while (!ouf.eof()) {
        lines.push_back(ouf.readLine());
        unsigned length = lines.back().length();
        if (length > 100) {
            quitf(_pe, "Output has a too long line (%u chars, max 100 allowed)", length);
        }
        if (lines.size() > 100) {
            quitf(_pe, "Output has way too many lines (>100, max 10 allowed)");
        }
    }

    // 2. Get rid of possible empty lines at the end
    while (lines.size() && lines.back().length() == 0) {
        lines.pop_back();
    }

    // 3. Check the total number of lines
    if (lines.size() > 10) {
        quitf(_pe, "Output has too many lines (%u, max 10 allowed)", (unsigned) (lines.size()));
    }
    if (lines.size() == 0) {
        quitf(_pe, "Output seems empty");
    }

    // 4. Check that all lines have the same length. Note that there is at least 1 non-empty line
    for (unsigned i = 1; i < lines.size(); ++i) {
        if (lines[0].length() != lines[i].length()) {
            quitf(_pe, "Line %u has length %u different from the first line (length %u)",
                    i + 1, (unsigned) lines[i].length(), (unsigned) lines[0].length());
        }
    }

    // 5. Check characters
    for (unsigned i = 0; i < lines.size(); ++i) {
        for (char ch : lines[i]) {
            if (ch != '.' && !('A' <= ch && ch <= 'Z')) {
                quitf(_pe, "Line %u contains an illegal character ('%c', code %u)",
                    i + 1, ch, (unsigned) (ch));
            }
        }
    }

    // 6. Post-process lines by padding with '.' from all sides
    unsigned new_length = 2 + lines[0].length();
    for (auto &line : lines) {
        line.insert(0, 1, '.');
        line.push_back('.');
    }
    std::string empty_line;
    empty_line.insert(0, new_length, '.');
    lines.insert(lines.begin(), empty_line);
    lines.push_back(empty_line);

    // 7. Check all colours for (not) being substrings
    for (auto const &col : colours) {
        if (col == small_colour) {
            std::string pattern = ".";
            pattern.append(col);
            pattern.push_back('.');
            bool exists = std::any_of(lines.begin(), lines.end(), [&] (auto const &line) {
                return line.find(pattern) != std::string::npos;
            });
            if (!exists) {
                quitf(_wa, "Second colour is not contained as a word");
            }
        } else {
            bool exists = std::any_of(lines.begin(), lines.end(), [&] (auto const &line) {
                return line.find(col) != std::string::npos;
            });
            if (exists) {
                quitf(_wa, "A wrong colour (%s) is contained as a substring", col.c_str());
            }
        }
    }

    // 8. Erase letters to 'A'
    for (auto &line : lines) {
        for (unsigned i = 0; i < line.length(); ++i) {
            if (line[i] != '.') {
                line[i] = 'A';
            }
        }
    }

    // 8. Fill the outer perimeter from dots to spaces.
    flood_fill(lines, 0, 0, '.', ' ');

    // 9. Check bounding boxes by refilling all letters from A to B
    unsigned last_letter_end = 0;
    for (unsigned col = 1; col < lines[0].length(); ++col) {
        for (unsigned row = 0; row < lines.size(); ++row) {
            if (lines[row][col] == 'A') {
                if (col <= last_letter_end) {
                    quitf(_wa, "Bounding boxes of letters intersect or touch along the X axis");
                }
                last_letter_end = flood_fill(lines, row, col, 'A', 'B');
            }
        }
    }

    // 10. Scan all letters again, but this time also count holes
    //     by filling letters from B into space, then counting components of dots.
    unsigned letter_idx = 0;
    for (unsigned col = 1; col < lines[0].length(); ++col) {
        for (unsigned row = 0; row < lines.size(); ++row) {
            if (lines[row][col] == 'B') {
                if (letter_idx >= big_colour.length()) {
                    quitf(_wa, "Too many letters detected");
                }
                unsigned last = flood_fill(lines, row, col, 'B', ' ');

                unsigned n_holes = 0;
                for (unsigned r1 = 0; r1 < lines.size(); ++r1) {
                    for (unsigned c1 = col; c1 <= last; ++c1) {
                        if (lines[r1][c1] == '.') {
                            ++n_holes;
                            flood_fill(lines, r1, c1, '.', ' ');
                        }
                    }
                }
                if (n_holes != holes[big_colour[letter_idx]]) {
                    quitf(_wa, "Expected %u holes at position %u, found %u",
                        holes[big_colour[letter_idx]], letter_idx + 1, n_holes);
                }
                ++letter_idx;
            }
        }
    }

    quitf(_ok, "Both colours found");
}