Advertisement
Guest User

Challenge

a guest
Jul 24th, 2015
363
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.73 KB | None | 0 0
  1. Hello, I'm learning C++ programming and I do like to solve any types of challenges/exercises, and since I have huge desire to become better I decided to post some of my solved challenges here, so that I can find out how my coding style is.
  2.  
  3. Is it understandable, how can the code be improved? And anything you think that may be helpful.  
  4. [Here][1] is an example of challenge I try to solve.
  5.  
  6. >Edit: Thanks for advices how to make better description of the challenge.
  7. >I hope that way things seems clearer.  
  8. >The all code is available [here][2].
  9.  
  10. [1]: https://www.codeeval.com/open_challenges/42/
  11. [2]: http://pastebin.com/9m1He65f
  12.  
  13. How code works ?  
  14. When get the input for example "123". Find how many different possible way it can subtract.
  15.  
  16.  
  17.    size_t perm = pow(2,static_cast<double>(input.size() - 1) );
  18.  
  19.  
  20. Originally there are 4 ways for our example. {123} {1 23} {12 3} {1 2 3}
  21. which is the value **perm** hold.
  22.  
  23. >*makeBinary* convert all values from 0 to **perm** into binary.
  24.  
  25. >     vector<string> makeBinary(size_t perm)
  26.    {
  27.         vector<string> output;
  28.         /*Since <bitset> will give me string with length 32
  29.         * but all zeros left than first '1' we met does not participate
  30.         in calculation we just erase them. */
  31.         size_t eraseLength = bitset<32>(perm).to_string().find_first_of('1');
  32.         while(perm--)
  33.         {
  34.             string binary = bitset<32>(perm).to_string();
  35.             binary.erase(binary.begin(), binary.begin() + eraseLength);
  36.             output.push_back(binary);
  37.         }
  38.         return output;
  39.    }
  40.  
  41.  
  42. >The logic behind making **perm** into binary is.
  43. >Every '1' is actually the space
  44. >between input  
  45. >>0 = 00 -> 123  
  46. >>1 = 01 -> 12 3  
  47. >>2 = 10 -> 1 23  
  48. >>3 = 11 -> 1 2 3  
  49.  
  50. And that is the function of *getPartitions* do, it will divide input according to **vector binarySet**, which hold all possible binary values.
  51.  
  52.  
  53.    vector<string> getPartitions(const vector<string>& binarySet,
  54.    const string& input)
  55.    {
  56.         vector<string> binOperator;
  57.         for(size_t idx = 0; idx < binarySet.size(); idx++)
  58.         {
  59.             string str(input);
  60.             for(size_t pos = 0,opCount = 1;
  61.             (pos = binarySet[idx].find('1',pos) )!= string::npos;
  62.             pos++,opCount++)
  63.             {
  64.                str.insert(pos+opCount, " ");
  65.             }
  66.             binOperator.push_back(str);
  67.         }
  68.         return binOperator;
  69.    }
  70.  
  71.  
  72. Then there is simple function that convert strings to integers, so we can add/subtract.
  73.  
  74.  
  75.    vector<int> makePartitionsToNum(const string& str)
  76.    {
  77.         vector<int> numbers;
  78.         stringstream split(str);
  79.         string buf;
  80.         while(split >> buf)
  81.         {
  82.             int value;
  83.             istringstream toNum(buf);
  84.             toNum >> value;
  85.             numbers.push_back(value);
  86.         }
  87.         return numbers;
  88.    }
  89.  
  90.  
  91. This function return numbers that are ready to check if they are **ugly**.
  92.  
  93.  
  94.    void getReadyNumbers(vector<int>* readyNumbers,
  95.    const vector<int> &numbers)
  96.     {
  97.         /*If there is only one number example "123"
  98.         *there is no binary operation so just add the number*/
  99.         if(numbers.size() == 1)
  100.         {
  101.             (*readyNumbers).push_back(numbers[0]);
  102.         }
  103.         /*This is also easy case when we have only two numbers
  104.         *{1,23} or {12,3}*/
  105.         else if(numbers.size() == 2)
  106.         {
  107.             (*readyNumbers).push_back(numbers[0] + numbers[1]);
  108.             (*readyNumbers).push_back(numbers[0] - numbers[1]);
  109.         }
  110.         else
  111.         {
  112.         /*And the third case with more than 2 numbers to add/sub
  113.         *The logic is similar, the only difference is now '0' means subtract
  114.         *and '1' means additions the number who gets here is {1,2,3}
  115.         *with total size(3) it have possiblePerm of 4.
  116.         *   0 = 00 -> 1-2-3 = -6
  117.         *   1 = 01 -> 1-2+3 = 2
  118.         *   2 = 10 -> 1+2-3 = 0
  119.         *   3 = 11 -> 1+2+3 = 6
  120.         */
  121.             size_t possiblePerm = pow(2,static_cast<double>(numbers.size()-1));    
  122.             vector<string> binSet(makeBinary(possiblePerm));
  123.             for(size_t i=0; i<binSet.size(); i++)
  124.             {
  125.                 int result = numbers[0];
  126.                 for(size_t binCounter=1;
  127.                 binCounter<numbers.size();
  128.                 binCounter++)
  129.                 {
  130.                     if(binSet[i][binCounter - 1] == '1')
  131.                     {
  132.                         result += numbers[binCounter];
  133.                     }
  134.                     else
  135.                     {
  136.                         result -= numbers[binCounter];
  137.                     }
  138.                 }
  139.                 (*readyNumbers).push_back(result);
  140.             }
  141.         }
  142.    }
  143.  
  144.  
  145. And the final step is to find total ugly's count of given input.
  146. >Ugly number is divisible by any of the one-digit primes (2, 3, 5 or 7) or equal to '0'
  147.  
  148.  
  149.     const int one_prime[4] = {2,3,5,7};
  150.     bool isUgly(int number)
  151.     {
  152.           if(number == 0) return true;
  153.           for(int i=0; i<4; i++)
  154.           {
  155.               if(number % one_prime[i] == 0)
  156.                       return true;
  157.           }
  158.           return false;
  159.     }
  160.  
  161.  
  162. I do really hope this code now look easier to understand, and I'm very excited to get some feedback. Thank you guys :)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement