stairclimber.cpp

/*******************************************************************************
 * Name        : stairclimber.cpp
 * Author      :
 * Date        :
 * Description : Lists the number of ways to climb n stairs.
 * Pledge      :
 ******************************************************************************/
#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <string>

using namespace std;

vector< vector<int> > get_ways(int num_stairs) {
    if (num_stairs == 1) {
        vector <vector <int> > outer;
        vector <int> inner;
        inner.push_back(1);
        outer.push_back(inner);
        return outer;
    }
    if (num_stairs == 2) {
        vector <vector <int> > outer;
        vector <int> inner1, inner2;
        inner1.push_back(1);
        inner1.push_back(1);
        outer.push_back(inner1);
        inner2.push_back(2);
        outer.push_back(inner2);
        return outer;
    }
    if (num_stairs == 3) {
        vector <vector <int> > outer;
        vector <int> inner1, inner2, inner3, inner4;
        inner1.push_back(1);
        inner1.push_back(1);
        inner1.push_back(1);
        outer.push_back(inner1);
        inner2.push_back(1);
        inner2.push_back(2);
        outer.push_back(inner2);
        inner3.push_back(2);
        inner3.push_back(1);
        outer.push_back(inner3);
        inner4.push_back(3);
        outer.push_back(inner4);
        return outer;
    }
    
    vector< vector<int> > ways_1 = get_ways(num_stairs - 1);
    for(std::vector<int>::size_type i = 0; i != ways_1.size(); i++) {
        ways_1[i].insert(ways_1[i].begin(), 1);
    }
    
    vector< vector<int> > ways_2 = get_ways(num_stairs - 2);
    for(std::vector<int>::size_type i = 0; i != ways_2.size(); i++) {
        ways_2[i].insert(ways_2[i].begin(), 2);
    }
    
    vector< vector<int> > ways_3 = get_ways(num_stairs - 3);
    for(std::vector<int>::size_type i = 0; i != ways_3.size(); i++) {
        ways_3[i].insert(ways_3[i].begin(), 3);
    }
    
    vector< vector<int> > combined_ways;
    
    combined_ways.reserve(ways_1.size() + ways_2.size() + ways_3.size());
    combined_ways.insert(combined_ways.end(), ways_1.begin(), ways_1.end());
    combined_ways.insert(combined_ways.end(), ways_2.begin(), ways_2.end());
    combined_ways.insert(combined_ways.end(), ways_3.begin(), ways_3.end());
    return combined_ways;
}

void display_ways(const vector< vector<int> > &ways) {
    // TODO: Display the ways to climb stairs by iterating over
    // the vector of vectors and printing each combination.
    int count = 1;
    for(vector<int>::size_type i = 0; i != ways.size(); i++) {
        vector<int> v = ways[i];
        if (ways.size() >= 10) {
            cout << setw(2) <<count++ << ". " << "[";
        } else {
            cout << setw(1) <<count++ << ". " << "[";
        }
        for(vector<int>::size_type i = 0; i != v.size(); i++) {
            if (i == 0) {
                cout << v[i];
            } else {
                cout << ", " << v[i];
            }
        }
        cout << "]" << endl;
    }
}

int main(int argc, char * const argv[]) {
    if (argc != 2) {
        cerr << "Usage: " << argv[0] << " <number of stairs>" << endl;
        return 1;
    }
    istringstream iss_arg1;
    iss_arg1.str(argv[1]);
    int arg1;
    
    if (!(iss_arg1 >> arg1)) {
        cerr << "Error: Number of stairs must be a positive integer." << endl;
        return 1;
    }
    
    if (arg1 <= 0) {
        cerr << "Error: Number of stairs must be a positive integer." << endl;
        return 1;
    }
    
    vector< vector<int> > combined_ways = get_ways(arg1);
    std::string w = combined_ways.size() == 1 ? " way" : " ways";
    std::string s = combined_ways.size() == 1 ? " stair." : " stairs.";
    cout << combined_ways.size() << w << " to climb " << arg1 << s << endl;
    display_ways(combined_ways);
}