// Written by Hodor (cboard cprogramming forum)

#include <iostream>
#include <vector>
#include <string>
#include <stdlib.h>

struct EncounteredState {
    std::string pattern;
    long offset;
    long t;
};

void padState(std::string &s, long *offset)
{
    s = "...." + s + "....";
    *offset -= 4;
}

std::string &trimState(std::string &s, long *offset)
{
    size_t pos;

    // strip trailing
    while(!s.empty() && s.back() == '.') {
        s.pop_back();
    }
    if (s.empty()) {
        std::cout << "Aborting: Empty state (all sitting)" << std::endl;
        exit(1);
    }

    // strip leading
    pos = s.find_first_of("#");
    if (pos != std::string::npos) {
        s = s.substr(pos);
        *offset += pos;
    } else {
        std::cout << "Aborting: Empty state (all sitting)" << std::endl;
        exit(1);
    }
    return s;
}

long makePass(const std::string &state, long offset)
{
    long index = offset;
    long pass = 0;
    for (char ch: state) {
        if (ch == '#') pass += index;
        index++;
    }
    return pass;
}

// ########## FIXME
/* Wrap all this code -- the entire program -- in a class so we don't have
 * these global vars hanging around just for calcPassUsingEquation() to use (once they're set)
 */
bool is_cycling = false;
long cycle_line_slope, cycle_t_start, cycle_line_intercept;

long calcPassUsingEquation(long t)
{
    // y = mx + c
    long pass = cycle_line_slope * (t - cycle_t_start) + cycle_line_intercept;

    return pass;
}
// ######## End FIXME


void step(std::string &state, long t, long *offset,
          const std::string patterns[], size_t num_patterns,
          std::vector<EncounteredState> &found_states
          )
{
    /* We will be adding "...." to the start and end of the state, so
     * add 8. Shouldn't be hardcoding this but this is throw away code
     * anyhow
     */
    std::string new_state(state.length() + 8, '.');
    padState(state, offset);

    for (size_t i = 0; i < num_patterns; i++) {
        size_t idx = 0;
        while ((idx = state.find(patterns[i], idx)) != std::string::npos) {
            new_state[idx + 2] = '#';
            idx++;
        }
    }

    state = trimState(new_state, offset);

    if (!is_cycling) {
        bool found = false;
        for (auto &stored_state: found_states) {
            if (stored_state.pattern == state) {
                /* Cycle detected
                 * Get what we need for linear equation
                 *
                 * We also need to keep handy the 't' of the first match so
                 * because we need to subtract it from the value of t we're
                 * going to calculate using the linear equation; i.e.
                 * shift t left so that it's on the y-axis (x=0). The line
                 * starts at stored_state_t in other words
                 *
                 * using y = m*x + c
                 *      y is the passcode
                 *      x is t adjusted as described above
                 *      c is the password when cycle started
                 */
                cycle_t_start = stored_state.t;
                cycle_line_intercept = makePass(stored_state.pattern, stored_state.offset);
                cycle_line_slope = makePass(state, *offset) - cycle_line_intercept;  // m = dy/dx = (pass(t) - pass(t-1)) / 1

                if (t - stored_state.t > 1) {   // If cycle length > 1
                    /* Not worth doing; sub-cycle might be linear, might not be.
                     * It is possible that a vector of slopes etc for each
                     * line within the sub-cycle could be created and then
                     * use those and t % cycle_length to work do it, but the
                     * problem doesn't seem to want that and I CBF
                     */
                    std::cout << "Cycle length > 1. Giving up :) " << std::endl;
                    exit(1);
                }

                is_cycling = true;
                found = true;
                break;
            }
        }
        if (!found) {
            EncounteredState ss;
            ss.pattern = state;
            ss.t = t;
            ss.offset = *offset;
            found_states.push_back(ss);
        }
    }
}

int main()
{

//FROM: prob29.txt
    std::string state = "###..##.#.#.##.##.#####..####.#.##.....#..#.#.#...###..#..###.##.#..##.#.#.....##..#####.#.#.##....#";
    const std::string patterns[] = {
        ".###.",
        "..##.",
        "#.###",
        ".#..#",
        ".#.##",
        ".####",
        "####.",
        "##...",
        "###..",
        "#.##.",
        "#..##",
        "...#.",
        "..#.#",
        "..#..",
        ".#.#."
    };

    /* Originally I wanted to handle cycle lengths > 1 so this was needed.
     * Now I've given up on dealing with that, because the problem
     * doesn't seem to care about those cases, this vector isn't necessary;
     * it would be sufficient to just store the previous t and previous passcode
     * throughout the brute forcing. I'm leaving it here though because it's
     * handy for calculating cycle lengths even if we don't do anything
     * apart from maybe graph them in an external program
     */
    std::vector<EncounteredState> found_states;

    long offset = 0;
    const int MAX_BRUTEFORCE_LEN = 10000;
    int t;
    for (t = 1; t < MAX_BRUTEFORCE_LEN; t++) {
        step(state, t, &offset, patterns, sizeof patterns / sizeof (patterns[0]), found_states);

        if (t == 12 || t == 1001)
                std::cout << makePass(state, offset) << std::endl;

        /* Brute forcing until 1000 has been printed. If the state goes linear
         * before 1001 then it doesn't matter... just being over cautious here
         * in case it doesn't go linear until some value > 1000 then at least
         * 1001 has already been printed above
         */
        if (is_cycling && t > 1001) {
            /* Don't have to brute force now... calculate for 50 billion and
             * break the loop
             */
            std::cout << calcPassUsingEquation(50000000000) << std::endl;
            break;
        }
    }
    if (t == MAX_BRUTEFORCE_LEN) {
        std::cout << "State didn't repeat." << std::endl;
    }

    return 0;
}