Programming
Copyright © 2019 Jiri Kriz, www.nosco.ch
Snippet math_se74338
Back to Overview

Arranging a 30 character word with letters x, y, z


/* 
 * Problem: http://math.stackexchange.com/q/70829/12741
 * Author: Jiri @ http://math.stackexchange.com/users/12741/jiri
 * Created: 22-Oct-2011
 */

#include <iostream>
using namespace std;   

int increase(int* a, int len) {
    int carry = 1;
    int i = 0;
    while (i < len && carry == 1) {
        a[i] += 1;
        if (i < len - 1) {
            if ((a[i] == a[i+1]) && (a[i] == 1 || a[i] == 2)) {
                a[i] += 1;
            }
        }
        if (a[i] > 2) {
            a[i] = 0;
            carry = 1;
            ++i;
        }
        else {
            carry = 0;
        }
    }
    return carry;
} 

void generate(int len) {
    cout << "Length: " << len << endl;
    int* a = new int[len];
    for (int i = 0; i < len; ++i) a[i] = 0;
    int carry = 0;
    long long count = 0;
    do {
        ++count;
        cout << count << ": ";
        for (int i = len-1; i >= 0; --i) {
            char c = 'X' + a[i];
            cout << c;
        }
        cout << endl;
        carry = increase(a, len);
        
    } while (carry == 0);
    // cout << "Count: " << count << endl;
    delete[] a;
}

long long count(int len) {
    long long x = 1;
    long long y = 1;
    for (int i = 2; i <= len; ++i) {
        long long x2 = x + 2 * y;
        y = x + y;
        x = x2;
    }
    long long all = x + y + y;
    cout << "Length " << len << ". Number of combinations: " << all << endl;
    //cout << "- ending with X: " << x << endl; 
    //cout << "- ending with Y: " << y << endl; 
    //cout << "- ending with Z: " << y << endl;
    //cout << "- all          : " << all << endl; 
    return all;
}

void test() {
    generate(3);
    long long last = 0;
    for (int n = 3; n <= 30; ++n) {
        // generate(n);
        long long c = count(n);
        if (c <= last) {
            cout << "ERROR Overflow" << endl;
            return;
        }
        last = c;
    }
} 

int main(int argc, char** argv) {
    test();
    return 0; 
}