4
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Hello guys i try to edit the post but i constantly get errors for wrong code formating so i would ask if someone edit it for me, this is the edit i try to do : pastebin.com/9meTRuKe \$\endgroup\$ – Newbie Jul 24 '15 at 7:35
1
\$\begingroup\$
  • 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.
\$\endgroup\$
  • 1
    \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – Mathieu Guindon Jul 24 '15 at 13:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.