Ugly_Numbers challenge

Question

Here's the challenge:

Once upon a time in a strange situation, people called a number ugly if it was divisible by any of the one-digit primes (\$2\$, \$3\$, \$5\$ or \$7\$). Thus, \$14\$ is ugly, but \$13\$ is fine. \$39\$ is ugly, but \$121\$ is not. Note that \$0\$ is ugly. Also note that negative numbers can also be ugly: \$-14\$ and \$-39\$ are examples of such numbers.

One day on your free time, you are gazing at a string of digits, something like:

123456

You are amused by how many possibilities there are if you are allowed to insert plus or minus signs between the digits. For example you can make:

1 + 234 - 5 + 6 = 236

which is ugly. Or:

123 + 4 - 56 = 71

which is not ugly.

It is easy to count the number of different ways you can play with the digits: Between each two adjacent digits you may choose put a plus sign, a minus sign, or nothing. Therefore, if you start with N digits there are \$3^{N-1}\$ expressions you can make. Note that it is fine to have leading zeros for a number. If the string is '01023', then '01023', '0+1-02+3' and '01-023' are legal expressions.

Your task is simple: Among the \$3^{N-1}\$ expressions, count how many of them evaluate to an ugly number.

Input Sample:

Your program should accept as its first argument a path to a filename. Each line in this file is one test case. Each test case will be a single line containing a non-empty string of decimal digits. The string in each test case will be non-empty and will contain only characters '\$0\$' through '\$9\$'. Each string is no more than 13 characters long. E.g.

1
9
011
12345

Output Sample:

Print out the number of expressions that evaluate to an ugly number for each test case, each one on a new line. E.g.

0
1
6
64

Is the code understandable? How can it be improved?

#include <iostream>
#include <fstream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <bitset>
#include <cmath>
#include <sstream>
#include <numeric>
using namespace std;

const int one_prime[4] = {2,3,5,7};
bool isUgly(int number)
{
    if(number == 0) return true;
    for(int i=0; i<4; i++)
    {
        if(number % one_prime[i] == 0)
                return true;
    }
    return false;
}
vector<string> makeBinary(size_t perm)
{
    vector<string> output;
    size_t eraseLength = bitset<32>(perm).to_string().find_first_of('1');
    while(perm--)
    {
        string binary = bitset<32>(perm).to_string();
        binary.erase(binary.begin(), binary.begin() + eraseLength);
        output.push_back(binary);
    }
    return output;
}
vector<string> getPartitions(const vector<string>& binarySet, const string& input)
{
    vector<string> binOperator;
    for(size_t idx = 0; idx < binarySet.size(); idx++)
    {
        string str(input);
        for(size_t pos = 0,opCount = 1; (pos = binarySet[idx].find('1',pos) )!= string::npos; pos++,opCount++)
                        str.insert(pos+opCount, " ");
        binOperator.push_back(str);
    }
    return binOperator;
}
vector<int> makePartitionsToNum(const string& str)
{
    vector<int> numbers;
    stringstream split(str);
    string buf;
    while(split >> buf)
    {
        int value;
        istringstream toNum(buf);
        toNum >> value;
        numbers.push_back(value);
    }
    return numbers;
}
void getReadyNumbers(vector<int>* readyNumbers, const vector<int> &numbers)
{
    if(numbers.size() == 1)
    {
        (*readyNumbers).push_back(numbers[0]);
    }
    else if(numbers.size() == 2)
    {
        (*readyNumbers).push_back(numbers[0] + numbers[1]);
        (*readyNumbers).push_back(numbers[0] - numbers[1]);
    }
    else
    {
        size_t possiblePerm = pow(2,static_cast<double>(numbers.size() - 1) );
        vector<string> binSet(makeBinary(possiblePerm));
        for(size_t i=0; i<binSet.size(); i++)
        {
            int result = numbers[0];
            for(size_t binCounter=1; binCounter<numbers.size(); binCounter++)
            {
                if(binSet[i][binCounter - 1] == '1')
                {
                    result += numbers[binCounter];
                }
                else
                {
                    result -= numbers[binCounter];
                }
            }
            (*readyNumbers).push_back(result);
        }
    }
}
void PrintSolution(const vector<int>& readyNumbers)
{
    size_t UglyNumberCount = 0;
    for(size_t i=0; i<readyNumbers.size(); i++)
    {
        if(isUgly(readyNumbers[i]))
        {
            UglyNumberCount++;
        }
    }
    cout << UglyNumberCount << endl;
}
int main(int argc, char *argv[])
{
    ifstream stream(argv[1]);
    string input;
    while (getline(stream, input))
    {
        size_t perm = pow(2,static_cast<double>(input.size() - 1) );
        vector<string> binarySet(makeBinary(perm));
        vector<string> partitionSet (getPartitions(binarySet, input));
        vector<int> readyNumbers;
        for(size_t idx=0; idx<partitionSet.size(); idx++)
        {
                vector<int> numbers(makePartitionsToNum(partitionSet[idx]));
                getReadyNumbers(&readyNumbers,numbers);
        }
        PrintSolution(readyNumbers);
    }
    return 0;
}

Answer 1

• Your isUgly function can be improved greatly.

  For example, if the input begins with 0, 2, 4, 6, 8, a number is divisible by 2, hence an important execution time can be skipped by this trick:

  bool isUgly(int number)
  {
      if ((number&1)==0) return true;
      //...
  }
  

  Therefore, with the divisibility by 5 (the case a number begins by 5 or 10), you can expel larger ranges of multiples of 5 from the division process. Just check out occurrence of the sequences 101 in a binary-formatted number.

  See this piece of code I made. About divisibility by 3, see my answer.

• Why are you checking the divisibility of any number by 2 after summing up (or subtracting) an even number of odd sub-values?

  For instance, (3+51)+(-7+11) or (3+5-1)+(-7+1+1) is always even, which means it's divisible by 2 because the sum of an even number of odd numbers is always even.

  int odd_digits=0,even_digits=strlen(argv[1]), j=0,borderdigit=0;
  
  for (int i=0;i<strlen(argv[1]);i++) 
  
  if((atoi(argv[1][i])&1)==1) 
  {
      if (i==strlen(argv[1])-1) borderdigit+=1;
      if (i==0) borderdigit-=2;  
      odd_digits++;
  }
  
  even_digits-=odd_digits;
  

  Any number xyz....XYZT... where all letters are odd and last numbers are necessarily even (odd_digits = 7, borderdigit = -2)

  or

  xyz....XYZT, where the last numbers are necessarily odd (borderdigit = 1)

  or

  xyz....XYZT, where the last and first numbers are necessarily odd (borderdigit = -1)

  would be manipulated automatically without the pain of calculating each combinatory readynumber, according to many variants:

  • Number of odd sub-numbers
  • Number of odd inner digits of any odd sub-number
  • Number of even digits
  • Last digit in the number

  • First digit in the number

    • If number of odd digits \$n\$ = odd_digits is even

      • If an odd digit is not the last in whole number (borderdigit=/=(+/-)1)

        • UglyNumberCount is multiplied by \$(4^{0/2}\binom{0}{n}+4^{2/2}\binom{2}{n}+...+4^{n/2}\binom{n}{n})\$

      • If an odd digit is last one in whole number (borderdigit==(+/-)1)

        • UglyNumberCount *= \$(4^{0/2}\binom{0}{(n-1)}+4^{2/2}\binom{2}{(n-1)}+...+4^{(n-2)/2}\binom{(n-2)}{(n-1)})\$

  • If number of odd digits \$n\$ is odd

    • If an odd digit is not last one in whole number (borderdigit=/=(+/-)1)

      • UglyNumberCount is multiplied by \$(4^{0/2}\binom{0}{n}+4^{2/2}\binom{2}{n}+...+4^{(n-1)/2}\binom{n-1}{n})\$

    • If an odd digit is last one in whole number (borderdigit==(+/-)1)

      • UglyNumberCount *= \$(4^{0/2}\binom{0}{(n-1)}+4^{2/2}\binom{2}{(n-1)}+...+4^{(n-1)/2}\binom{(n-1)}{(n-1)})\$

• About even digits multiplication is done by \$2^k\$ instead of \$4^k\$

  Number of digits is fix \$n\$ = even_digits

  • If an even digit is not last one in whole number (borderdigit==(+/-)1)

    • UglyNumberCount is multiplied by \$(2^{0}\binom{0}{n}+2^{1}\binom{1}{n}+...+2^{n}\binom{n}{n})=3^{n}\$

  • If an even digit is last one in whole number (borderdigit=/=(+/-)1)

    • UglyNumberCount *= \$(2^{0}\binom{0}{n-1}+2^{1}\binom{1}{n-1}+...+2^{n-1}\binom{n-1}{n-1})=3^{n-1}\$

---

• Note: The same procedure can be applied with multiples of 5. Just replace (even, odd) selections by (5 or 0, x) where x is any digit else.
• Note 2: divisibility-check by 3 and 7 doesn't encompass combinations where both two previous cases occur because they are already ugly, I wont claim to have any magical trick but until here a large number of possibilities would have been got rid of.