SHARE
TWEET

Stairclimber

a guest Feb 21st, 2020 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. vector< vector<int> > get_ways(int num_stairs) {
  2.     /* Returns a vector of vectors of ints representing
  3.     the different combinations of ways to climb num_stairs
  4.     stairs, moving up either 1, 2, or 3 stairs at a time.
  5.     Optimized to use a modified integer partition algorithm. */
  6.     vector<vector<int>> all_ways;
  7.     vector<int> p(num_stairs, 0);
  8.     if (num_stairs < 4) {
  9.         all_ways.push_back(vector<int>{num_stairs});
  10.     }
  11.     int k = 0;
  12.     p[k] = num_stairs;
  13.     while (true) {
  14.         // Generate next partition
  15.         // Find the rightmost non - one value in p[].
  16.         // Also, update the rem_val so that we know
  17.         // how much value can be accommodated
  18.         int rem_val = 0;
  19.         while (k >= 0 && p[k] == 1) {
  20.             rem_val += p[k];
  21.             k -= 1;
  22.         }
  23.         // if k < 0, all the values are 1 so
  24.         // there are no more partitions
  25.         if (k < 0) return all_ways;
  26.         // Decrease the p[k] found above and adjust the rem_val
  27.         p[k] -= 1;
  28.         rem_val += 1;
  29.         // Ensure values are below or equal to 3 before increment
  30.         while (p[k] > 3) {
  31.             p[k] -= 1;
  32.             rem_val += 1;
  33.         }
  34.         // Copy rem_val to next position
  35.         // and increment position
  36.         p[k + 1] = rem_val;
  37.         k += 1;
  38.         // Keep values only if they at most 3
  39.         if (rem_val > 3) continue;
  40.         vector<int> valid_p;
  41.         // Add non-zero values (everything before k + 1)
  42.         for (int i=0; i < k + 1; i++) {
  43.             valid_p.push_back(p[i]);
  44.         }
  45.         all_ways.push_back(valid_p);
  46.     }
  47. }
  48.  
  49. void display_ways(const vector< vector<int> > &ways) {
  50.     /* Iterates through the ways to climb the stairs and displays them
  51.     **Must be printed in reverse for the partition algorithm */
  52.     int width = ways.size() == 0 ? 1 : log10(abs(long(ways.size()))) + 1;
  53.     // for (unsigned int i=0; i < ways.size(); i++) {
  54.     for (unsigned int i=ways.size() - 1; i >= 0; i--) {
  55.         cout << setw(width) << ways.size() - i << ". [";
  56.         for (unsigned int j=0; j < ways[i].size(); j++) {
  57.             cout << ways[i][j];
  58.             if (j < ways[i].size() - 1) {
  59.                 cout << ", ";
  60.             }
  61.         }
  62.         cout << "]" << endl;
  63.     }
  64. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top