kthGrammar.cpp

#include <vector>
#include <iostream>
#include <unordered_map>

using namespace std;

class Solution {
public:
    int kthGrammar(int N, int K) {
        if (N == 1)
            return 0;

        auto p = route(N - 1, K - 1);

        int current = 0;

        auto iterator = p->begin();

        while(iterator != p->end()) {
            if (*iterator == 0) {
                if (current == 0) {
                    current = 0;
                } else {
                    current = 1;
                }
            } else {
                if (current == 0) {
                    current = 1;
                } else {
                    current = 0;
                }
            }
            iterator++;
        }
        return current;
    }

    // N will be an integer in the range [1, 30].
    // K will be an integer in the range [1, 2^(N-1)].
    vector<int> *route(int N, int K) {
        // assert(N >= 1);
        // assert(N <= 30);
        // assert(K >= 1);
        // assert(K <= (int)pow(2, (N-1)));

        vector<int> *p = new vector<int>();

        for (int i = N - 1; i >= 0; i--) {
            int basis = (int)pow(2, i);
            if (K >= basis) {
                p->push_back(1);
                K -= basis;
            } else {
                p->push_back(0);
            }
        }
        
        return p;
    }

};

void test(int N, int K, int truth) {
    auto obj = Solution();
    auto p = obj.kthGrammar(N, K);
    assert(p == truth);
}

void test_route() {
    auto obj = Solution();

    for (int i = 1; i < 6; i++) {
        for (int j = 0; j < (int)pow(2, i); j++) {
            cout << "(i,j) = " << "(" << i << "," << j << ")" << endl;
            auto p = obj.route(i, j);
            auto iterator = p->begin();

            while(iterator != p->end()) {
                cout << *iterator;
                iterator++;
            }

            cout << " -> ";
            
            iterator = p->begin();
            int result = 0;
            for (int k = 0; k < p->size(); k++) {
                result += ((*iterator++) * (int)pow(2, p->size() - 1 - k));
            }

            cout << result << endl;

            assert(j == result);
        }
    }
}

int main(int argc, char**argv) {
    auto obj = Solution();
    test_route();
    
    test(1, 1, 0);
    test(2, 1, 0);
    test(2, 2, 1);
    
    test(4, 1, 0);
    test(4, 2, 1);
    test(4, 3, 1);
    test(4, 4, 0);
    test(4, 5, 1);
    test(4, 6, 0);
    test(4, 7, 0);
    test(4, 8, 1);

    return 0;
}