C++

Forum

 
 
loop with bigNo

Pages: 12
xgeutzu (25)
is about this problem:

Given this scheme below:

ABCDE / FGHI = 9
How many solutions are there to the puzzle for the digits 1 to 9 being use once and only once in a particular set of numbers?

where ABCDEFGHI = {1,2,3,4,5,6,7,8,9}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
 

int main()
{
    int a, b=1234, cont = 0;

    while(b<9877)
    {
        for(a=12345;a<98765;a++)
            if(valid(a,b) && a%b==0 && a/b==9) cont = cont + 1;
        ++b;
    }

    cout << cont;

note: valid is a function that calculate if two numbers ( a& b) are valid (each digit from 1 to 9, just once used) ; it works fine.

my program works fine for a=1234 to 9876 & 123 < b < 987. (execution time 23s)

but with this values (12345 to 98765 & 1234 to 9876) it seems to not respond to me.

anybody, any idea ?

10x
And G (4)
The program looks fine to me. However, since you're going from 7 digits to 9 digits, I would expect runtime to increase by a factor of roughly 100. 23 seconds * 100 = ~40 minutes. So there's possibly your problem.

I would suggest adding a line cout << b; into the while loop. That way you can monitor more closely what your program is doing, and also estimate the remaining time.

Edit: As a side note, your program could be sped up by checking for the validity of b separately (before entering the for loop). For example, 2222 is not a valid value for b and thus the for loop can be skipped. There are other ways how you can make your program more efficient, but it looks to me like this is intended as part of the problem so I'm not going to give you any more hints.
Last edited on
JLBorges (13770)
Brute force, using the standard library (brute force is all that is needed for 9! ):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
#include <iostream>
#include <algorithm>
#include <string>
#include <utility>

bool quotient_is_9( std::pair<int,int> numbers ) { return numbers.first == ( numbers.second * 9 ) ; }

// invariant: str contains decimal digits, str.size() == 9
std::pair<int,int> split54( std::string str ) 
{ return { std::stoi( str.substr(0,5) ), std::stoi( str.substr(5) ) }; }

int main()
{
    std::string digits = "123456789" ;
    int cnt = 0 ;
    
    do if( quotient_is_9( split54(digits) ) ) ++cnt ; 
    while( std::next_permutation( std::begin(digits), std::end(digits) ) ) ;

    std::cout << cnt << '\n' ;
}

http://coliru.stacked-crooked.com/a/f214bc555cafa72f

EDIT: misread the problem; rem_is_9() changed to quotient_is_9()
Last edited on
JLBorges (13770)
Faster version of the above:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
#include <iostream>
#include <algorithm>
#include <utility>

bool quotient_is_9( std::pair<int,int> numbers ) { return numbers.first == ( numbers.second * 9 ) ; }

std::pair<int,int> split54( int digits[] ) // size == 8, contains decimal digits
{
    return { digits[0]*10000 + digits[1]*1000 + digits[2]*100 + digits[3]*10 + digits[4],
                               digits[5]*1000 + digits[6]*100 + digits[7]*10 + digits[8] };
}

// size == 8, contains decimal digits, 5-4 split of digits
bool may_be_divisible_by_9( int digits[] ) { return ( digits[8] * 9 ) % 10 == digits[4] ; }

int main()
{
    int digits[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 } ;
    int cnt = 0 ;

    do if( may_be_divisible_by_9(digits) && quotient_is_9( split54(digits) ) ) ++cnt ;
    while( std::next_permutation( std::begin(digits), std::end(digits) ) ) ;

    std::cout << cnt << '\n' ;
}

http://coliru.stacked-crooked.com/a/0ca7bf975fd82234
PCrumley48 (173)
JLBorges:

You have a great solution there. . .the results are rather disappointing, though!!!

ONLY THREE??? and two are permutations of each other. . .who knew?

I tried it a little differently, using 

1
2
3
4
5
6
 
bool is_mod_nine (digits)
int sum = 0;
// if the loop is slower, could just do int sum = digits[5] + digits[6] + digits[7] + digits[8];
for (i = 5, i < 9, i++) sum += digits[i];

return sum % 9 == 0;


instead of may_be_divisible_by_9, since all eligible numbers and divisors must be divisible by nine. Using the divisor which is only four digits long mod 9 confirms that it must not may, be in the set of eligible divisors. This should reduce the number of calls to split 54 and quotient_is_nine.

I didn't do a timing study on either version but both are quite quick.
Last edited on
anup30 (968)
its a problem of permutation and combination.
you have to find all 5 digit permutation and divide each of them by permutation of remaining 4 digits.
possible divide operations: 9P5 times 4P4 = 362,880
PCrumley48 (173)
But if you remove each of the five and four digit elements that are not already divisible by nine, the division operations come to 40,320.

And out of 40,320 possible sets - only three meet the specification. I would have thought there would be a lot more than that.

Incidentally, there are only 14 pairs of 5/4 digit numbers using all nine digits having one or both numbers (actually it's always both) divisible by 9, so it's the same - 14 * 60 * 24 = 40320 possibilities.
Last edited on
anup30 (968)
But if you remove each of the five and four digit elements that are not already divisible by nine, the division operations come to 40,320.
Can you please explain it
JLBorges (13770)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
#include <iostream>
#include <algorithm>
#include <utility>

int num_div_ops = 0 ;

bool quotient_is_9( std::pair<int,int> numbers ) { ++num_div_ops ; return numbers.first == ( numbers.second * 9 ) ; }

std::pair<int,int> split54( int digits[] ) // size == 8, contains decimal digits
{
    return { digits[0]*10000 + digits[1]*1000 + digits[2]*100 + digits[3]*10 + digits[4],
                               digits[5]*1000 + digits[6]*100 + digits[7]*10 + digits[8] };
}

// size == 8, contains decimal digits, 5-4 split of digits
bool may_be_divisible_by_9( int digits[] ) { return ( digits[8] * 9 ) % 10 == digits[4] ; ++num_div_ops ; }

// size == 8, contains decimal digits, 5-4 split of digits
bool is_mod_9( int digits[] ) { return ( digits[5] + digits[6] + digits[7] + digits[8] ) % 9 == 0 ; ++num_div_ops ; }

int main()
{
    int digits[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 } ;
    int cnt = 0 ;

    do if( is_mod_9(digits) && may_be_divisible_by_9(digits) && quotient_is_9( split54(digits) ) ) ++cnt ;
    while( std::next_permutation( std::begin(digits), std::end(digits) ) ) ;
    std::cout << "is_mod_9 && may_be_divisible_by_9: #num_div_ops:  " << num_div_ops << "   cnt: " << cnt << '\n' ;
    
    cnt = num_div_ops = 0 ;
    do if( may_be_divisible_by_9(digits) && quotient_is_9( split54(digits) ) ) ++cnt ;
    while( std::next_permutation( std::begin(digits), std::end(digits) ) ) ;
    std::cout << "            may_be_divisible_by_9: #num_div_ops: " << num_div_ops << "   cnt: " << cnt << '\n' ;
    
    cnt = num_div_ops = 0 ;
    do if( is_mod_9(digits) && quotient_is_9( split54(digits) ) ) ++cnt ;
    while( std::next_permutation( std::begin(digits), std::end(digits) ) ) ;
    std::cout << "                         is_mod_9: #num_div_ops: " << num_div_ops << "   cnt: " << cnt << '\n' ;
}

is_mod_9 && may_be_divisible_by_9: #num_div_ops:  4608   cnt: 3
            may_be_divisible_by_9: #num_div_ops: 40320   cnt: 3
                         is_mod_9: #num_div_ops: 40320   cnt: 3

http://coliru.stacked-crooked.com/a/23a1394c6a725bac
PCrumley48 (173)
But if you remove each of the five and four digit elements that are not already divisible by nine, the division operations come to 40,320.

By definition of the problem, the larger five-digit operand must always be divisible by 9 to be included.

Using nines-complement principles, it can be proved that the divisor must also be divisible by 9, since the sum of set {1,2,3,. . . ,9} is 45, divisible by 9. Any multiple of 9 subtracted from 45 will leave a remainder that is also divisible by 9.

Actually the sum of set {a,b,c,d} must equal (45 - sum of set {e,f,g,h,i}), and because sum of set {1,2,3,4} can never be 9, one sum must be at least 18, the other sum not more than 27.

So there is no reason to divide any pair of numbers whose digit-sum isn't 18 and 27, or whose divisor is not mod 9.


What intrigues me is the ( is_mod && may_be. . .) eliminating so many division operations!
Last edited on
anup30 (968)
i found the three divisions :)
58239 / 6471
57429 / 6381
75249 / 8361

i did without <utility>(i don't know) and my code become 100+ line!

EDIT: it has much easier method. today i done it with 20 lines.
Last edited on
PCrumley48 (173)
Interesting problem!

Both sets { is_mod_9 } and { may_be_divisible } are the same size and include different elements, but both must include the solution pair.

{ is_mod_9 } requires all dividends and divisors to be multiples of 9.

{ may_be_divisible } requires the last digit of the possible quotient to be 9.

Their intersection results in a set of 4608 pairs in which the quotient ends in 9, and both the dividend and divisor are multiples of 9.

There may be an additional set that could intersect with this one to reduce the number even more.

I used an old database program (VFP) to create a table having all the 362880 permutations, using about 60 lines of FoxPro code. . .it created the table of permutations, marked each record with the results of the two condition sets, found the three solutions and created some other information I wanted to see, all in 5 seconds. . .not bad for an interpreter-based program. If I don't create the table and stuff it finds the three solutions in two seconds. Got it down to 1 second using string 123456789 and using substrings of that.

This could be optimized a bit:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
 
set procedure to permutations
? time()
set talk off
set safety off
use permutations
zap
n = 9
permutations = 0
dimension A(9)
for ncount = 1 to n
	A(ncount) = ncount
next
GENERATE(n)
? time()

procedure generate(n)
private i,j,ncount,temp
if n = 1 then
	append blank
	gather from A
	m.val5 = 0
	m.sum5 = 0
	m.val4 = 0
	m.sum4 = 0
	for lCount = 1 to 5
		m.val5 = m.val5 + (a(lcount)* 10^(5 - lcount))
		m.sum5 = m.sum5+a(lcount)
	next 
	for lCount = 6 to 9
		m.val4 = m.val4 + (a(lcount) * 10^(9 - lcount))
		m.sum4 = m.sum4+a(lcount)
	next
	gather memvar fields val4, sum4, val5, sum5
	replace mod9 with ismod9(val4)
	replace maybe9 with maybe(a5, a9)
	replace solution with val5/val4 = 9
	replace val4_9 with val4/9, val5_9 with val5/9
else
	for i = 1 to  n
		generate(n - 1)
		if mod(n, 2) = 1
			j = 1
		else
			j = i
		endif
		temp = a(j)
		a(j) = a(n)
		a(n) = temp
	next
endif
return

function ismod9(Value)
return mod(value,9) = 0

function maybe( c4, c8)
return mod(c8 * 9 ,10) = c4


My VS2012 translation of the string version of this takes less than a second in the exe version. In debug mode it takes 9 to 10 seconds.
Last edited on
anup30 (968)
you remind me a horse race @PCrumley48
PCrumley48 (173)
Well, actually, I used to work for a guy who is in the NHRA drag racing hall of fame. . .
xgeutzu (25)
thank you all 4 ur responses.

i've tried JLBorges code, but my compiler returns me

/home/gheorghita/Desktop/scoala/a_math_puzzle/main.cpp||In function ‘std::pair<int, int> split54(int*)’:|

/home/gheorghita/Desktop/scoala/a_math_puzzle/main.cpp|20|warning: extended initializer lists only available with -std=c++0x or -std=gnu++0x [enabled by default]|

/home/gheorghita/Desktop/scoala/a_math_puzzle/main.cpp||In function ‘int main()’:|

/home/gheorghita/Desktop/scoala/a_math_puzzle/main.cpp|36|error: ‘begin’ is not a member of ‘std’|

/home/gheorghita/Desktop/scoala/a_math_puzzle/main.cpp|36|error: ‘end’ is not a member of ‘std’|

/home/gheorghita/Desktop/scoala/a_math_puzzle/main.cpp|41|error: ‘begin’ is not a member of ‘std’|

/home/gheorghita/Desktop/scoala/a_math_puzzle/main.cpp|41|error: ‘end’ is not a member of ‘std’|

/home/gheorghita/Desktop/scoala/a_math_puzzle/main.cpp|46|error: ‘begin’ is not a member of ‘std’|

/home/gheorghita/Desktop/scoala/a_math_puzzle/main.cpp|46|error: ‘end’ is not a member of ‘std’|


||=== Build finished: 6 errors, 1 warnings ===|


i'ved searched on the internet but I didn't get exactly what it means.

10x 1 more time for your responses guys !
JLBorges (13770)
> i'ved searched on the internet but I didn't get exactly what it means.


See: http://en.cppreference.com/w/cpp/iterator/begin
http://en.cppreference.com/w/cpp/iterator/end


This should compile cleanly with the version of g++ that you have:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
#include <iostream>
#include <algorithm>
#include <utility>

int num_div_ops = 0 ;

bool quotient_is_9( std::pair<int,int> numbers ) { ++num_div_ops ; return numbers.first == ( numbers.second * 9 ) ; }

std::pair<int,int> split54( int digits[] ) // size == 8, contains decimal digits
{
    return std::make_pair( digits[0]*10000 + digits[1]*1000 + digits[2]*100 + digits[3]*10 + digits[4],
                              digits[5]*1000 + digits[6]*100 + digits[7]*10 + digits[8] );
}

// size == 8, contains decimal digits, 5-4 split of digits
bool may_be_divisible_by_9( int digits[] ) { return ( digits[8] * 9 ) % 10 == digits[4] ; ++num_div_ops ; }

// size == 8, contains decimal digits, 5-4 split of digits
bool is_mod_9( int digits[] ) { return ( digits[5] + digits[6] + digits[7] + digits[8] ) % 9 == 0 ; ++num_div_ops ; }

int main()
{
    const int NDIGITS = 9 ;
    int digits[NDIGITS] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 } ;
    int cnt = 0 ;

    do if( is_mod_9(digits) && may_be_divisible_by_9(digits) && quotient_is_9( split54(digits) ) ) ++cnt ;
    while( std::next_permutation( digits, digits+NDIGITS ) ) ;
    std::cout << "is_mod_9 && may_be_divisible_by_9: #num_div_ops:  " << num_div_ops << "   cnt: " << cnt << '\n' ;
    
    cnt = num_div_ops = 0 ;
    do if( may_be_divisible_by_9(digits) && quotient_is_9( split54(digits) ) ) ++cnt ;
    while( std::next_permutation( digits, digits+NDIGITS ) ) ;
    std::cout << "            may_be_divisible_by_9: #num_div_ops: " << num_div_ops << "   cnt: " << cnt << '\n' ;
    
    cnt = num_div_ops = 0 ;
    do if( is_mod_9(digits) && quotient_is_9( split54(digits) ) ) ++cnt ;
    while( std::next_permutation(digits, digits+NDIGITS ) ) ;
    std::cout << "                         is_mod_9: #num_div_ops: " << num_div_ops << "   cnt: " << cnt << '\n' ;
}

http://coliru.stacked-crooked.com/a/12469e90ad0e09b6
PCrumley48 (173)
I don't remember the error message, but my compiler didn't like that function either. I didn't take time to see if there was an #include issue or not, so I just modified it to declare a local pair<int,int> variable, set the two elements of that variable to the calculated values and return the pair. 

1
2
3
4
5
6
7
8
9
10
 
std::pair<int,int> split54( int digits[] ) // size == 8, contains decimal digits
{
    std::pair<int,int> lpair;
    lpair.first = digits[0]*10000 + digits[1]*1000 + digits[2]*100 + digits[3]*10 + digits[4];
    lpair.second = digits[5]*1000 + digits[6]*100 + digits[7]*10 + digits[8];
    return lpair;
    
    // return { digits[0]*10000 + digits[1]*1000 + digits[2]*100 + digits[3]*10 + digits[4],
                              //  digits[5]*1000 + digits[6]*100 + digits[7]*10 + digits[8] };
}


My compiler didn't complain about std::begin or std::end, so I don't know what to tell you. Maybe in your version you need to #include one of the headers in the reference?

These function templates are defined in multiple headers: Each of these headers includes the generic templates for all container and array types and not simply a specific overload. The headers are: <iterator>, <array>, <deque>, <forward_list>, <list>, map, <regex>, <set>, <string>, <unordered_map>, <unordered_set> and <vector>.


Here is my FoxPro to C++ translation (because FoxPro doesn't include a built-in iterator, this does the permutations without the C++ function):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
#include "stdafx.h"
#include <string>
#include <iostream>
#include <ctime>

std::string a="123456789";
int permutations = 0;

void generate(int n);

int main()
{
	std::cout << time(0) << std::endl;
	int n = 8;

	generate(n);
	std::cout << time(0) << std::endl;
	std::cout << a << "    " << permutations << std::endl;
	system("Pause");
	return 0;
}



void generate(int n)
{
	int i,j;
	std::string temp;
	int val4,val5;
	if (n == 0)
	{
		val5 = std::stoi(a.substr (0,5));
		val4 = std::stoi(a.substr(5,4));
		if (val4 * 9 == val5 )
		{
			std::cout << val5 << "\t" << val4<< "\t" << val5/val4 << std::endl;
		}
	}
	else
	{
		for (i = 0; i <= n; i++)
		{
			generate(n - 1);
			if( n % 2 == 1) j = 0;
			else j = i;
			temp = a.substr(j,1);
			a.replace(j,1,a.substr(n,1));
			a.replace(n,1,temp);
		}
	}
}
xgeutzu (25)
guys, you're awsome !

thank you alot. I hope, one day, to be half good as you are !
anup30 (968)
cheers to 15 lines!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
#include <iostream>
#include <algorithm>
using namespace std;
int main () {
	double n, d, r;  
	int ar[9] ={1,2,3,4,5,6,7,8,9};
	do {
		n = ar[0]*10000 + ar[1]*1000 + ar[2]*100 + ar[3]*10 + ar[4]*1;
		d = ar[5]*1000 + ar[6]*100 + ar[7]*10 + ar[8]*1;
		r = n/d;
		if(r==9)		
			cout << n << " / " << d << " = 9 \n";    		
	} while ( std::next_permutation( ar, ar+9 ) );
return 0;
}
PCrumley48 (173)
How about 11 lines?
( I know, line 8 is cheating just a little. . . , so 12 if I don't cheat;)

1
2
3
4
5
6
7
8
9
10
11
 
#include <iostream>
#include <algorithm>
int main () {
	int n,d, ar[9] ={1,2,3,4,5,6,7,8,9};
	do {
		n = ar[0]*10000 + ar[1]*1000 + ar[2]*100 + ar[3]*10 + ar[4]*1;
		d = ar[5]*1000 + ar[6]*100 + ar[7]*10 + ar[8]*1;
		if(d * 9 == n) std::cout << n << " / " << d << " = 9 \n";    		
	} while ( std::next_permutation( ar, ar+9 ) );
return 0;
}


( I can "Name That Tune" in 1 note. . . .) (http://en.wikipedia.org/wiki/Name_That_Tune if you don't understand. . .)
Last edited on
Pages: 12