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;
}

• Newbie: 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

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.

• Mathieu Guindon: Comments are not for extended discussion; this conversation has been moved to chat.