advent_of_code_day11_extended_questions.cpp

#include <bits/stdc++.h>
#define foreach(IT,C) for(typeof(C.begin())IT=C.begin();IT!=C.end();IT++)

using namespace std;

typedef long long L;

string alphabet = "abcdefghjkmnpqrstuvwxyz";// alphabet for unmodified problem
//string alphabet = "abcdefghijklmnopqrstuvw"; // Question 3. equivalent to remove i,j, and o
set<string> passwords;

bool is_good(string s) {
    return true; // not sure of > Passwords must contain at least two different, non-overlapping pairs of letters
    set<char> st;
    for (int i = 1; i < 8; i++) {
        if (s[i] == s[i-1]) {
            st.insert(s[i]);
        }
    }
    return st.size() >= 1;
}

// The generator
void f(string s, short repeated, bool consecutive) {
    int mn = max((2 - repeated) * 2 - 1, 0);
    char z = s.size() < 3 ? '@' : s[s.size() - 3];
    char a = s.size() < 2 ? '@' : s[s.size() - 2];
    char b = s.size() < 1 ? '#' : s[s.size() - 1];


    if (!consecutive and a + 1 != b) {
        mn += 2;
    }

    if (s.size() + mn > 8) {
        return;
    }

    if (s.size() == 8) {
        if (repeated >= 2 and consecutive and is_good(s)) {
            passwords.insert(s);
        }
        return;
    }
    for (int i = 0; i < alphabet.size(); i++) {
        char c = alphabet[i];
        f(
            s + c,
            repeated + (b == c and (c != a or c == z) ? 1 : 0),  // if there is a bug, it will be here
            consecutive or (a + 1 == b and b + 1 == c)
        );
    }
}

L to_num(string str) {
    L num = 0;
    L base = 26; // original problem
    //L base = 23; // question 3
    foreach (it, str) {
        num = num * base + (*it - 'a');
    }

    return num;
}

int main() {
    f("", 0, false);

    int xmas_count = 0;
    foreach (it, passwords) {
        if (it->find("xmas") != string::npos) {
            cout << *it << endl;
            xmas_count++;
        }
    }

    printf("total passwords: %d\nContaining xmas: %d\n", (int)passwords.size(), xmas_count);

    L max_dist = 0, dist = 0, current_dist = 1;
    string ans_start, ans_end, last_start;
    foreach (it, passwords) {
        if (it == passwords.begin()) {
            continue;
        }

        set<string>::iterator prev_it = it;
        prev_it--;
        dist = to_num(*it) - to_num(*prev_it);

        //cout << *it << " " << *prev_it << " " << dist << endl;

        if (dist == 1) {
            current_dist++;
            if (current_dist > max_dist) {
                max_dist = current_dist;
                ans_end = *it;
                ans_start = last_start;
            }
        } else {
            current_dist = 1;
            last_start = *it;
        }
    }
    cout << "Largest distance " << ans_start << " ... " << ans_end  << " " << max_dist << endl;

    cout << (int)((passwords.find("aaaaabcc") != passwords.end()) ? 1 : 0) << endl;
}