This week's book giveaway is in the Artificial Intelligence forum.
We're giving away four copies of Pragmatic AI and have Noah Gift on-line!
See this thread for details.
Win a copy of Pragmatic AI this week in the Artificial Intelligence forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Jeanne Boyarsky
  • Liutauras Vilda
  • Campbell Ritchie
  • Tim Cooke
  • Bear Bibeault
Sheriffs:
  • Paul Clapham
  • Junilu Lacar
  • Knute Snortum
Saloon Keepers:
  • Ron McLeod
  • Ganesh Patekar
  • Tim Moores
  • Pete Letkeman
  • Stephan van Hulst
Bartenders:
  • Carey Brown
  • Tim Holloway
  • Joe Ess

Problem: Digit Products  RSS feed

 
Ranch Hand
Posts: 65
7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello,

I was trying to solve this problem. So I wrote the following code. The code wouldn't be hard to read if BigInteger were not used. When I submitted my code, it passed a few test cases but failed others due to timeout. I'm not entirely sure whether it is BigInteger, the algorithm, or both that make the program inefficient; I suspect both. The heart of the program is in compute() method. Also note that I'm checking whether K is odd for efficiency reasons.



Thank you.
 
Saloon Keeper
Posts: 9145
173
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You're doing a brute force by checking integers between A and B, which can be between 1 and 10^100.

That means that if you had a 10GHz machine, and you could run through your outer loop once per clock cycle, you'd be done in 3*10^82 YEARS.

So no, this has nothing to do with BigInteger. You need a different algorithm, one that reasons about the input values.

My first attempt would be to write a method that given an integer K, returns a list of integers who's digit product is K.

You can then remove integers that are not in the range [A, B] and count them.
 
Marshal
Posts: 59786
188
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:. . . given an integer K, returns a list of integers who's digit product is K. . . .

Does that mean factorisation such that factors are all in the range 1...9?
 
Stephan van Hulst
Saloon Keeper
Posts: 9145
173
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yeah.
 
Stephan van Hulst
Saloon Keeper
Posts: 9145
173
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I realized that's probably too slow as well, but I'm sure it's a much more feasible approach than iterating the range [A, B].
 
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Ramsin Khoshaba wrote:I was trying to solve this problem. So I wrote the following code.


And I suspect that's where your troubles lie.

You don't solve problems like this by writing code; you solve them by thinking about the problem - and understanding it - before you start writing code.

And if I was doing this, the first thing I'd do is look at the constraints, viz:
T ⩽ 10000
1 ⩽ A ⩽ B ⩽ 10¹⁰⁰
1 ⩽ K ⩽ 10¹⁸

And there are quite a few things that scream out at me immediately:
1. If this program is to work for every possible case in a reasonable time, it CANNOT check every value between A and B because, even for a computer, 10¹⁰⁰ (the worst case for the number of values to check) is a very big number.
2. If K is a prime number, the answer will be 0.
3. If K is an exact power of a single digit, the answer will be either 0 or 1.
4. Any value between A and B that contains a 0 can be eliminated immediately. This means that
(a) Any number that divides by 10 can be eliminated.
(b) For any given length of number, you can start at 1111..., since any number of the same length that is less than that will contain at least one 0. And the same also holds true for internal sequences.
5. Digit position is irrelevant, since multiplication is commutative, so all numbers with the same combination of digits will render the same product. Thus '242' == '422' == '224'.
6. The digit '1' is irrelevant, since it makes no difference to the product. Thus the numbers '242' and '1121421' are "equal".
7. Since K has to be <= 10¹⁸, which is < 2⁶³, the number cannot have more than 63 digits > 1, and there will be lower limits for larger digit values.

All of which suggests to me that my "solution" is only concerned with distinct combinations of digits > 1 in the numbers between A and B. Now this may still be a very large number, but it's going to be orders of magnitude less than 10¹⁰⁰.

And I'd care to bet that the best solution (as Campbell and Stephan already suggested) is going to be based around single digit factors of K. Indeed, if K has any prime factor > 9, the answer MUST be 0.

Winston
 
Master Rancher
Posts: 2758
93
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Nice problem, and Winston is right.

I solved the problem (I thinki, haven't sent it in) brute force, but I won''t give the answer. What I can do, is to give a class that, given some number X, gives all the digits of which the product equals X.
The answer comes in a List<List<Integer>> where each List<Integer> is a list of all digits with the right product.
The format is a bit special, to vastly reduce the numer of lists: each digit is at least as big as its predecessor. For instance, when X = 12, then my method gives the following List:

[[2, 2, 3], [2, 6], [3, 4]]

So, there is still some work to do. For each list:

1) determine the number of permutations (take care: digits may not be unique!)
2) given a valid permutation, we have to put in a bunch of '1's, as Winston described. Now, given a List, how do we know how many ones we can insert?
3) and: in how many ways can we divide those ones over the digits that we have?

And these points are far from easy! Some recent knowlegde of combinatorics comes in handy.

But I'm in for a better and easier solution.

Here is the code:

 
Campbell Ritchie
Marshal
Posts: 59786
188
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:. . . 3. If K is an exact power of a single digit, the answer will be either 0 or 1. . . .

Please explain a bit more. What about 4 8 and 9? I think I have misunderstood what you said there.
 
Ramsin Khoshaba
Ranch Hand
Posts: 65
7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:Indeed, if K has any prime factor > 9, the answer MUST be 0.


Wow, I never thought of that.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:

Winston Gutkowski wrote:. . . 3. If K is an exact power of a single digit, the answer will be either 0 or 1. . . .

Please explain a bit more. What about 4 8 and 9? I think I have misunderstood what you said there.


Sorry, my mistake. I was thinking that if K is, say 81, then n can only be 99; but of course that's wrong, because it could also be any number with exactly two nines and the rest '1's.

Winston
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Piet Souris wrote:Nice problem, and Winston is right.


Makes a change.

Thinking about this further, the quickest solution would appear to be basically a prime factorization of K; and since there are only 4 of them below 10 (2, 3, 5 and 7), those are the only ones we need to worry about.

Specifically, in order for there to be any solution, K must be exactly equal to 2ʷ * 3ˣ * 5ʸ * 7ᶻ, where w, x, y, and z are all >= 0.

Therefore, I think my factoring method would look something like this:If the method returns false, then there's no solution; but if it returns true there's a bit more work to do, since each "triplet" of 2s can be satisfied by either 3 '2's, a '2 and a '4', or a single '8'. Similarly, each pair of 3s can be either 2 '3's or or single '9'.

But it just makes working out the digit combinations a bit more involved, that's all.

Best of luck with your solution, Ramsin; and have a cow for a fun question.

Winston
 
Ramsin Khoshaba
Ranch Hand
Posts: 65
7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello,

I learned something new about private access, from §6.6.1. Namely, that access to a private member is permitted iff "it occurs within the body of the top level class that encloses the declaration of the member or constructor." I mention this because I made a new nested static class named Factorizer with the factorize() method Winston provided.

Now if I have the 10 decimal digits and a n-character string, then C(n + 10 - 1, 10) is the number of ways to form a n-digit string with the 10 decimal digits (disregarding order), where C(n, r) = n!/(r!*(n-r)!). Am I correct?

So, if I have a 100-digit decimal number, then C(100 + 10 - 1, 10) = 42634215112710.
And ignoring the 0 digit, I get C(100 + 9 - 1, 9) = 3911395881900.
 
Piet Souris
Master Rancher
Posts: 2758
93
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Winston,

although it is very correct, this factorization is the easy part. I gave a short recursive routine that dealt with that, for those who love a nice recursion.

The real problems begin from this point. To illustrate:

say K = 12. Now, we have the combinations that I mentioned. [2, 2, 3], [2, 6], [3, 4] (for K = 2 ^50, I get 231 different combinations).

Now, what does that mean for the number of solutions when

1) A = 1, B = 10^100
2) A = 35, B = 41
3) A = 27, B = 1225

And to take these limits into account, that was the real hard part. Yesterday evening I discovered a bug in my solution, and although I know how to repair, it is too involved to do. So I will consider some smarter ways to solve this problem (if I can think of any).

@Ramsin
the formulas needed are those of the multinomial distribution. It boils down to: we have R red, G green, B blue and W white balls, how many different permutations are there?

Well, that's it from me.

 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Piet Souris wrote:say K = 12. Now, we have the combinations that I mentioned. [2, 2, 3], [2, 6], [3, 4] (for K = 2 ^50, I get 231 different combinations).


OK, but it seems to me that the problem (once we know that K is a candidate) can be broken down into smaller ones:
1. Work out the number of combinations of factors of K between 2 and 9 - ie 'digits that must be in n'.
2. Apply that result to the limits you've been given, adding '1's if/as necessary.

Taking step 1 in isolation (most of this will probably be obvious to you, but I don't have any advanced Maths to help me ):
There are 4 composite 'digits' we have to consider: 4, 6, 8 and 9, and they involve only two prime factors: 2 and 3; and of those, only one (6) involves both of them.

A number (like 2⁵⁰), which doesn't have both 2 and 3 as factors, should be relatively straightforward, since it's only a problem of working out how many distinct combinations of 2, 4 and 8 there can possibly be; therefore, I suspect that it would be a good idea to divide the problem into values that have both 2 and 3 as factors, and ones that don't.

Another thing it seems to me is that we need to know the length of the shortest possible combination, since if this is longer than our upper limit, there is no solution.
And again, for a number like 2⁵⁰, this is dead easy: the longest is obviously 50, and the shortest is 17 (16 '8's and a '4'). Therefore, if our upper limit is less than 4888... (17 digits), we know there can't be a solution.

Now exactly how you go about determining the shortest combination for numbers with both 2 and 3 as factors I'm not sure. My "gut feel" is that you should
1. Eliminate 9s and 8s (ie, pairs of 3s and triplets of 2s) until you have only a small number left.
2. Pair off any remaining 2s and 3s as '6's
3. Deal with any remaining 4s.
But exactly how "small" that number in Step 1 should be I don't know. I suspect that you can simply eliminate 9s and 8s until you are left with at most only one 3 and two 2s, but I have a slight worry that 6 x 6 is greater than 8 x 4, so I'm not sure if there's a combination of "endings" where it's better to eliminate 6s than 8s.
I suspect not, since 6 x 6 involves 2 3s, so you could eliminate a 9 and 8 instead, but my Maths isn't good enough to prove it.

Now I just have to work out how to calculate the number of combinations when both 2 and 3 are involved...and then apply it to the limits...or maybe a bit of both.

Gad, this is a fun problem.

Winston
 
Ramsin Khoshaba
Ranch Hand
Posts: 65
7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Piet Souris wrote:@Ramsin
the formulas needed are those of the multinomial distribution. It boils down to: we have R red, G green, B blue and W white balls, how many different permutations are there?


I was thinking about multichoose, which disregards order. And I think I miscalculated there.

n-multichoose-k means the number of ways k-sized multisets can be formed with n (distinct) symbols. It's expressed as C(n + k - 1, k).
Having 9 distinct digits (ignoring 0) and k = 100, we have C(9 + 100 - 1, 100) = 352025629371 ≈ 352 billions.

To make it simple to begin with, assume we have 4 distinct digits and a 2-character string, then C(4 + 2 - 1, 2) = 10. And we can enumerate the combinations as follows:

1,1
1,2
1,3
1,4
2,2
2,3
2,4
3,3
3,4
4,4

Note the order in which I enumerate them.

In the worst case (where A=1 and B=10^100) there are approximately 352 billion different combinations of 1-9 digits.

If I have reasoned correctly, 12345 is equivalent to 54321 according to my calculation, which means that there is no over-counting.
So without duplicates, there are approximately 352 billion different combinations!
And please point out if I'm wrong.
 
Ramsin Khoshaba
Ranch Hand
Posts: 65
7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If 1335 is a hit for example (given K=45), then if the range permits 3135 is also a hit, and so on. But in accordance to my previous post, the combination {1,3,3,5} is counted only once.

If range permits all permutations of a given combination must be counted: there are 4!/2! arrangements of 1335 if the two 3s are considered identical.

The difficulty arises when all arrangements are not in the range [A, B].
 
Ramsin Khoshaba
Ranch Hand
Posts: 65
7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Ramsin Khoshaba wrote:In the worst case (where A=1 and B=10^100) there are approximately 352 billion different combinations of 1-9 digits.


I'm wrong here, because in the worst case we have,
C(9 + 100 - 1, 100) + C(9 + 99 - 1, 99) + C(9 + 98 - 1, 98) + ... + C(9 + 3 - 1, 3) + C(9 + 2 - 1, 2) + C(9 + 1 - 1, 1)
different combinations.

I think I'm gonna ask for tips from my math teacher tomorrow.
 
Piet Souris
Master Rancher
Posts: 2758
93
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Ramsin,

Well, I seem to have been explaining badly what I meant, since you come to the same conclusion as I did yesterday. So, let me give an example of what I meant.

Say, K = 12. We know that we have 3 possible combinations: [2, 2, 3], [2, 6] and [3, 4].

Let’s look at [2, 2, 3]. Now, in fact we have the number 223, but sice 322 is also a valid possibility, order does matter hare. Therefore. C(n, k) is not relevant in this case.

So, [2, 2, 3]. When we have a number of N digits, that can be written as: N = a^n1 * b ^n2 * c ^n3, then the number of permutations is:

N! / (n1! * n2! * …)

In the case of [2, 2, 3] we therefore have 3! / (2! * 1!) = 3 different permutations, and so, as a start, we have 3 different solutions when K = 12.

Now, suppose A has 5 digits and B has 15 digits. That means that we can safely add to [2, 2, 3] 3 ones, 4 ones, et cetera, up to 14 – 3 = 11 ones. We know for certain that the combinations we get, are between A and B.

Now, adding 3 ones to [2, 2, 3] gives us the collection [1, 1, 1, 2, 2, 3] and so the number of permutations is:

6! / (3! * 2! * 1!) = 60 numbers.

If we add 4 ones, then we get 7! / (4! * 2! * 1!) = 105, et cetera.

And when we add 14 ones, we get 17! / (14! * 2! * 1!) = …

That is for the combination [2, 2, 3].

Now, the problem arises when we add 2 ones. How many permutations are then more than or equal to A?

For instance, say A = [ 3, 1, 1], then how many permutations of [2, 2, 3] remain? How would you determine this?
And that is in fact the real puzzle, at least if you follow this solution.

One remark is that since K <= 10^18, we do not need any BigIntegers here. We get just by with using longs.

And finally: it might be worth to first check B – A. If that is less than say 10 ^7, then away with all clever solutions: vive Brute Force!
 
Ramsin Khoshaba
Ranch Hand
Posts: 65
7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So the puzzle is if given e.g. A=2332 and B=3322, how many permutations of {2,2,3,3} there are in [A, B] range.

Generally there are 4!/(2!*2!) = 6 permutations of {2,2,3,3}, but only 3 of which satisfy the condition.

2233
2323
2332*
3223*
3232*
3322

So the problem is to count in a clever way.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Piet Souris wrote:And finally: it might be worth to first check B – A. If that is less than say 10 ^7, then away with all clever solutions: vive Brute Force!


Ooof. I have to disagree here (and I may be wrong), but the requirements only ask us to find out how many combinations there are; not what they are,

And if we can work that number out for all possible combinations between 1 and 10¹°°, it should be a relatively simple reduction exercise to eliminate those that are less than A or greater than B - the first cut of which can be done on the number of digits alone.

This is why I suspect that a good algorithm is going to involve some combination of raw maths and reduction by numbers of digits, so if I can come up with numbers for the limits A=1 and B=10¹°°, I'll feel that I'm halfway there.

However, that may well involve knowing the number of combinations of a specific length (primarily for the number of digits in the lower limit A, but also for the upper limit if - and ONLY if - the longest possible combination of 1-digit factors of K - ie, the sum of powers of 2, 3, 5 and 7 - is greater than the number of digits in B).

I'm sure Piet will correct me if I'm wrong; but to me this problem is much more about understanding the numbers of combinations involved rather than what they actually are.

Winston
 
Piet Souris
Master Rancher
Posts: 2758
93
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:

Piet Souris wrote:And finally: it might be worth to first check B – A. If that is less than say 10 ^7, then away with all clever solutions: vive Brute Force!


Ooof. I have to disagree here (and I may be wrong), but the requirements only ask us to find out how many combinations there are; not what they are



Well, I too have to disagree. I meant this: (for A and B close enough, and both in the long-range)


I'm sure Piet will correct me if I'm wrong; but to me this problem is much more about understanding the numbers of combinations involved rather than what they actually are.

Winston


I'm not going to correct you, however, I do not quite understand why you think that I am interested in what the numbers actually are. I couldn't care less, I only gave some numbers by way of example, to illustrate what I did (and that boiled down to a bunch of combinatorics!).
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Piet Souris wrote:Well, I too have to disagree. I meant this: (for A and B close enough, and both in the long-range)


OK, perhaps I misspoke.

What I meant was that that's simply an optimization, and doesn't really help us to a general algorithm. Given the constraints for A, B and K, if I was to run a "smoke test" on my code, even with ranges and values of K that I knew would return a value other than 0, I suspect I'd be highly unlikely to get lower and upper limits that conform to those specs,

As you say, the real key to this problem is to work out the subset of combinations that are possible for a given lower or upper limit, assuming they restrict it.

However, since each limit is going to have a specific number of digits in it, the subset is only going to apply to permutations of a specific length, which is why I thought it would be a good idea not only to know the total number of permutations, but also to be able to
(a) Calculate the number of permutations for a specific length.
(b) (for eliminiation purposes only) Know what the lowest and highest possible number of a specific length is, based on factors of K.

It also seems to me that the worst possible case is going to be one where the powers of 2 and 3 that make up K are both large, so I think I might use something like 432 (2⁴ * 3³) or 1296 as a start point to see if I can work out any patterns for determining digit combinations and upper and lower limits (689 and 3332222 being the limits for 432).

Winston
 
Ranch Hand
Posts: 1154
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Is there any sort of statute of limitations on answer programming questions that is likely a homework assignment? On the one hand, I understand the concept of not doing someone's homework for them. On the other, it may be fun to share some code that implements the entire solution.
 
Ramsin Khoshaba
Ranch Hand
Posts: 65
7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Ryan McGuire wrote:Is there any sort of statute of limitations on answer programming questions that is likely a homework assignment? On the one hand, I understand the concept of not doing someone's homework for them. On the other, it may be fun to share some code that implements the entire solution.



This is not a homework, it is a competitive programming challenge. And it's not just a "programming question," rather a combinatorial problem.
 
Piet Souris
Master Rancher
Posts: 2758
93
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Ryan

yes, that is always the question. How much does one reveal a solution in cases like these?
Recently I warned against giving information about solving some Project Euler questions, but now I've gone pretty far myself.

But the mot important part of what I suggested as solution: I haven't revealed.

Now, to Ramsin and Winston:

what I did in the final hurdle (and that was very complex) is:

suppose we have the combination [1, 2, 3, 4, 5]. We know that the number of permutations is 5!
Suppose that we're only interested in permutations that (when considered as a number) are less than 50000.
So, all permutations starting with a 5 must be dropped. Well, in this case it is simple: there are 4! of them, leaving us with 4 * 4! permutations.

But now it gets interesting. Suppose we have [ 2, 2, 2, 3 ,3, 4] and we're only interested in permutations higher than 30000.
So, we must skip all permutations starting with a 2. How many permutations get dropped now?
And what if the permutations must be higher than 33000? How doe we proceed?

Well, getting this correct is far from easy.

But what worries me most is that on the website Ramsin was referring to, this poblem is only considered as 'moderate'.
And I had a look at this site an hour ago. There was this problem where an integer was given (between 1 and 10^130),
and the question is: is there a permutation of that number that is divisable by 8.

Now, that is pretty easy, I think, but that problem was also marked as 'moderate'. So, is OP's problem also that easy to solve? Hmmm...

But I rest my case now. Anyone with a brillliant easy solution?
 
Stephan van Hulst
Saloon Keeper
Posts: 9145
173
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is also the Diversions forum. I think it's fine to post complete solutions here, as long as the subject isn't clearly homework.
 
Ramsin Khoshaba
Ranch Hand
Posts: 65
7
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here is my thought. If only I could solve the equation.

Given 5 as the exponent of 2, in how many ways can we partition 5 units into groups of sizes 1, 2 and 3?
(Such a group cannot have 4 elements because 2^4 = 16.)

We have then,

2^x * 4^y * 8^z = 2^5
x + 2*y + 3*z = 5
where x denotes the number of groups of size 1, y the number of groups of size 2, and z the number of groups of size 3.

So the problem is reduced to finding the number of all non-negative solutions to the equation. I have worked with Diophantine equations of two unknowns, not three.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Piet Souris wrote:Now, that is pretty easy, I think, but that problem was also marked as 'moderate'. So, is OP's problem also that easy to solve? Hmmm...


I also notice that the next problem down (called 'Permutation problem') doesn't seem to be as difficult as Ramsin's (although I have to admit I don't have a complete solution for it) and has a 50% success rate for respondents; yet it's marked as 'difficult' and has the same maximum score. Ramsis's has no correct responses yet, and only one attempt - although whether that's just because it's newer I have no idea.

Anyone with a brillliant easy solution?


Nope; but it seems to me that if there is one, it must have something to do with limiting combinations - maybe something we're not seeing - because I think we've worked out how to eliminate cases where the answer is 0 (which is probably the vast majority) quite easily.

Winston
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Ramsin Khoshaba wrote:We have then, ...
x + 2*y + 3*z = 5
where x denotes the number of groups of size 1,


Hmmm, algebra. I like it.

A couple of other things also occurred to me (sleep is a wonderful thing):
1. I'd be inclined to use Strings for our "limits" rather than BigIntegers, since we're only ever worried about comparisons by length OR content, and for the latter, a String comparison will yield the same result as a numeric one.
2. For the tough part of our problem, the lower limit (A) is the "purer" of the two, since it isn't clouded by the case of adding '1's to make up a number long enough. I suspect also that determining the number of combinations for a lower limit will be the "flip side" of doing it for an upper limit.

Also:
  • The longest number possible from K (not including '1's) is dead easy, because it's simply the sum of powers of 2, 3, 5 and 7.
  • The highest number possible from K is also easy: it's those same digits listed in descending order.
  • If the shortest number possible from reducing the powers of 2 and 3 in K is longer than B, then the answer is 0.
  • If the smallest number possible (slightly different) is > B, then the answer is also 0, and if it's equal to B, the answer is 1.
  • If A is less than the smallest number possible, then it can't limit our combinations.
  • If B is greater than the highest number possible, then it can't limit our combinations.
  • Now some of those observations may be obvious, but I figured they were worth stating for the record.

    There can also be only 3 possible variants of the shortest number, and usually there will be only one. My algorithm above was slightly wrong, because I'm now pretty sure that you need to eliminate triplets of 2 first, because that reduces the number of digits by the greatest amount.

    So I think the correct algorithm is something like this:
    Lets call the number of 2s remaining 'w', and the number of 3s remaining 'x', and further assume that at least one of them is > 0, since otherwise you don't need to run it.
    (5s and 7s are irrelevant, since they don't affect the length of the shortest number)

    Step 1
    1. While w > 3:
      a. Remove a triplet of 2s.
      b. If x > 1, remove a pair of 3s as well.
    2. While x > 3:
      a. Remove a pair of 3s.

    That leaves you with at most three 2s, and at most three 3s, so:

    Step 2
    If x == 0,
      If w == 0, the job is done and you have your (one) variant.
      Otherwise you have one variant that includes either '2', '4' or '8', depending on the value of w.

    If w == 0, then you have only one variant that includes either '3', '9' or '39', depending on the value of x.

    If w == 1,
      If x == 1 then you must pair it with the remaining 2, so you have one variant that includes a '6'.
      If x == 2 then you have a choice of
        (a) pairing one 3 with with a 2, giving a number including the digits '36' or
        (b) pairing the 3s together to give '29'.
      If x == 3 then you have one variant: '69'.

    If w == 2,
      If x == 1 (Step 1 left only one 3) you have two variants: '34' and '26'.
      If x == 2 you have two variants: '66' and '49'.
      If x == 3 you have two variants: '366' and '349'.

    If w == 3,
      If x == 1 you have one variant: '38'.
      If x == 2 you have one variant: '89'.
      If x == 3 you have three variants: '666', '389' and '469'.

    That's as far as I've got at the moment. I'm currently working on trying to determine the number of combinations for a specific length.

    Winston
     
    Winston Gutkowski
    Bartender
    Posts: 10575
    66
    Eclipse IDE Hibernate Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Winston Gutkowski wrote:The longest number possible from K (not including '1's) ... blah blah blah...


    Aha! I think all this faffing around has pointed me to part of the solution.

    I've been obsessing about the longest and shortest possible numbers and, while I think these are still important, there's another that's possibly even more important:
     The number derived from K with every possible power of 2 and 3 "paired up".

    This number will contain at most one '2' OR one '3' (if there's one of each, we make it a '6'), along with w/2 '4's, and x/2 '9's (again, '5's and '7's are basically irrelevant).

    The reason why I think this number is important is because it helps us calculate the number of combinations of digits of length L, because if L is larger than the length of this number (let's call that value 'N'), then we know that exactly L-N of our "pairs" have to be expanded, and conversely, if it's less, then we know that N-L need to be "contracted", which is slightly more difficult, but not wildly so.

    I haven't worked it through completely in my mind yet, but it "feels" important.

    Winston
     
    Piet Souris
    Master Rancher
    Posts: 2758
    93
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Well, I'm not sure I understand, but I wish you succes! No doubt, you'll keep us informed.

    Since my replies were hardly answered or commented, I guess there is not much interest for it.
    I will explain in some more detail how I handled that final hurdle. I do solemly promise that this will be the last time I am boring you!

    So, here goes.

    Suppose K = 96.

    Now, that recursive routine that I gave in my opening reply, delivers me, among other combinations, this List: [2, 2, 4, 6].
    Now indeed, what matters here is a frequency table. We get: 2: 2, 4: 1, 6:1
    (The advantage of doing it this way is that I have this '4' in my list).

    Let A have 7 digits, being: 2, 4, 1, 1, 7, 2, 2.

    So, as I wrote, I first add 3 '1''s to my collection, getting now a frequency table of: 1:3, 2:2, 4:1, 6:1

    The number of permutations is: 7! / (3! * 2! * 1! * 1!) ( = 420)

    Now let's look at the first digit of A: 2

    In my frequency map, I count hoe many keys are smaller than this 2. I find only 1. This means that all permutations that start with a '1' must be dropped. How many permutations start with a '1'? Well, to calculate that, scrap one '1' from the frequency list. We then get: 1: 2, 2:2, 4:1, 6:1, and the number of permutations are 6! / (2! * 2! * 1! * 1!) (= 180). We loose that many permutations.

    We proceed. Skip the first digit of A, we then get A' = 4, 1, 1, 7, 2, 2.

    Again, we look at the first digit: 4, and we see that we now have to drop all permutations that start with either 1 or 2.
    How many? Well, again the combinatorics help us out here. Our reduced frequency table was 1: 2, 2: 2, 4:1, 6:1. If we calculate how many permutations start with a '1' we get:
    5! / (1! * 2! * 1! * 1!) = 60.
    When we also eliminate all permutations starting with a '2' we loose also 60 permutations. Ijn total we have lost now: 180 (first digit of A) and 120 (second digit of A).

    Skip the second digit of A as well. We get A'' = 1, 1, 7, 2, 2.

    And we also skip a 1 and a 2 from our frequency table, giving us two tables: 1:1, 2:2, 4:1, 6:1 and 1:2, 2:1, 4:1, 6:1.

    Look at the first digit of A''. That is '1'. This is unfortunately worst case, since we cannot eliminate anything. Therefore, each of our two frequency tables will be followed by a frequncy table in which the frequency of each key is reduced by 1. So, for instance, 1:1, 2:2, 4:1, 6:1 will give us 4 new tables (starting with 1:0, 2:2, et cetera), and so will the second one.

    Et cetera.

    When we arrive at the '7' of A'''', we see that we can accept all remaining combinations and we're done. We know how many permutations were in principal possible, and how many we had to skip.
    Complex? Yes. Can this be captured in a method? Yes. Is it similar for B? Yes. Should the person who came up with this problem have said that A and B were both of the form 10^n, with 0 <= n <= 100? Definitely. Can I guarantee that this will work for every value of K and A and B? Well, no.

    As promised: no further boring stuff from me.
     
    Ramsin Khoshaba
    Ranch Hand
    Posts: 65
    7
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Piet Souris wrote:Since my replies were hardly answered or commented, I guess there is not much interest for it.


    I think that is because everyone is really absorbed in its own thoughts, so it gets difficult to change your "perspective" when you've been thinking a lot from another one. That is how I feel anyway. Second, the problem is not so easy maybe.
     
    Ramsin Khoshaba
    Ranch Hand
    Posts: 65
    7
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Can't we just count all permutations up to B and all permutations up to A, and then take the difference?
    (And I don't know why they labeled this problem 'moderate'.)

    I was writing what follows, but now I became tired so I stopped. I believe with what follows I can turn "counting without limits" into a more general algorithm. I wonder if in the innermost loop one could put more logic to include the constraints (i.e. the upper- and lower-limits), and I believe one can.

    Suppose
    K = 96 = 2^5 * 3

    Then the number of non-negative solutions to
    x + 2*y + 3*z = 5
    is the number of ways to form a list whose element product is 2^5, without added 1s.
    It happens to be that that number of ways is 5. So you can form an unordered list whose element product is 2^5 in 5 different ways. Since we have only one 3, there is one way to form an unordered list whose digit product is 3, without added 1s.

    Now for numbers order matters. In our case, the number of elements in an unordered list is (x + y + z). To find how many permutations there are,
    (x + y + z)!/(x!*y!*z!)
    gives the number of ways to form a number whose digit product is 2^5.

    And it turns out that we have 13 such permutations.

    Now for each such permutation there should belong a 3 also. So we get,

    Or, 56 such permutations.
     
    Ramsin Khoshaba
    Ranch Hand
    Posts: 65
    7
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Ramsin Khoshaba wrote:Now for each such permutation there should belong a 3 also. So we get,

    Or, 56 such permutations.


    Oh, I forgot to count permutations with digit 6.
     
    Winston Gutkowski
    Bartender
    Posts: 10575
    66
    Eclipse IDE Hibernate Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Ramsin Khoshaba wrote:

    Piet Souris wrote:Since my replies were hardly answered or commented, I guess there is not much interest for it.


    I think that is because everyone is really absorbed in its own thoughts, so it gets difficult to change your "perspective" when you've been thinking a lot from another one.


    Absolutely.
    I'm really impressed by your work Piet; I'm probably just one step behind it. It's also quite involved so, as a lazy programmer, I'd only want to do it as a last resort; so I want to work out all the ways I can avoid it first.

    Ramsin Khoshaba wrote:Second, the problem is not so easy maybe.


    Certainly doesn't seem easy to me; but then I never did any higher Maths, so I'm probably missing some useful knowledge.

    Piet Souris wrote:Well, I'm not sure I understand, but I wish you success!


    OK, my reasoning is this.

    If K contains factors that can be "paired up", generating a number of length P (eg, for K=5184, '44499' = 5), then we can use that information to calculate the total number of permutations for a given length.
    Furthermore, unless K divides exactly by 8, we know that this is also the length of the shortest number.

    If A = 10⁷ (length 8), then we know we must "unpair" exactly 3 of our 5 pairs, and since (at this point) we're only worried about length, it doesn't matter which ones we choose. Therefore the number of ways of doing that is "5 choose 3", or 5 x 4 x 3 = 60.
    Unfortunately, the number of total permutations is also governed by the number of symbols we will have, so we also have to work out the number of ways of exhausting one of our existing ones (if it's possible).
    For '2' it's 3 x 2 x 1 = 6, which gives us 6 combinations with two symbols: '22222299'.
    For '3' it's (2 x 1 x 3) * 3 = 18, which gives us 18 combinations with three symbols: '22333344'.
    and all the others (36) must have 4 symbols: '22223349'.

    I suspect it'll also be good to break down those other combinations (although it's not necessary in this case), since a further wrinkle is that each pair of '4' and '9' can also be represented by '66' to give a number of equal length. Then it's simply a case of working out the number of ways that those symbols can be arranged (including, of course, any '5's and '7's) to get a total.

    Laborious, but pretty straightforward.

    Winston
     
    Piet Souris
    Master Rancher
    Posts: 2758
    93
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    First of all: I haven't read both your latest siblings, I was still busy with my own work.
    I did not like my final solution of the A and B hurdles, it is too complex, but most of all: it is incorrect.
    I already wrote somewhere that I discovered a bug, but that the repair was too laborious. But seeing both
    your efforts, I had no choice than to go on! After I have described my latest solution, I will have a more close look at what the both of you are suggesting.
    So, bear with me.

    Well this is my solution that I am content with. It is straightforward, very much easier, but I have to implement it yet.

    First of all: I recall the formula that I have been using al over:
    suppose we W white balls, R red and G green. We know that the number of permutations is: (W + R + G)! / (W! * R! * G!).
    That is a standard formula. The next formula is one that I have also used before:
    The number of permutations that start with a Green ball, is: (W + R + G - 1)! / (W! * R! * (G - 1)!) (and don't forget that 0! = 1)

    So, what do I have in mind then? Let me illustrate by another example:

    Suppose we have again the combination [2, 2, 4, 6] (i.e. K = 96), and let's forget the '1' s for the moment. We again write this in the form of a frequency table (say, a HashMap), we have 2:2, 4:1, 6:1.

    Now Let the first digit of A be: 3. We now proceed as follows: keep only those permutations that start with a digit bigger then 3. In our case: that means: 4 or 6. Now, how do we calculate that number? I eexplained it before, but let it first start with a 4: we then have a remaining frequency table of: 2:2, 4:0, 6:1, and so we get: (2 + 0 + 1)! / (2! * 0! * 1!) (= 3). And likewise, when we start with a 6.

    But we cannot rule out the possibility that A starts with our smallest digit of our frequency table (i.e. 2).

    So, lets assume that we now only look at the permutations that start with a 2. Our frequency table now becomes: 2:1, 4:1, 6:1. Drop the first digit of A.
    And we repaet the above procedure, until we have had all A's digit, or we arrive at a digit of A that is less than all our remaining keys. We then know that all remaining permutations are okay.

    The algorithm then becomes:

    Let the total of permutations be called Total, and initialize it to 0.


    This is straight forward, and I'll implement it as soon as possible, and show some results.

    Also, if we have (x + y) mod z, that is equl to (x mod z) + (y mod z), and that should enable us to avoid using big integers.

    But until then, please go on gentlemen, I'll give your work the attention it deserves.

    @Winston
    I'm really surprised about you fanatism. Never knew you were in these kinds of problems! To finish with a famous saying from 'Are you being served': keep up the good work!

    @Ramsin
    what is your background, if I may ask? Not many know about diiofantic equations. I remember doing a Project Euler problem that dealt with these things. As it turned out, I had to search Google for some theoretic results first.






     
    Ramsin Khoshaba
    Ranch Hand
    Posts: 65
    7
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Piet Souris wrote:@Ramsin
    what is your background, if I may ask? Not many know about diiofantic equations. I remember doing a Project Euler problem that dealt with these things. As it turned out, I had to search Google for some theoretic results first.


    I'm a freshman at KTH. My MScEng programme is called Information Technology. I'm having a course in discrete mathematics this period.

    The previous semester I had a course in Java, where I got 41/41 on the final exam
    Of course, after the course was done I started to better understand some parts that I had learned during the course, with frustration.
    And I still have to understand more.

    There is also an elective Java course I'm gonna choose for the next semester. It covers network programming in Java
     
    Winston Gutkowski
    Bartender
    Posts: 10575
    66
    Eclipse IDE Hibernate Ubuntu
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Piet Souris wrote:@Winston
    I'm really surprised about you fanatism. Never knew you were in these kinds of problems! To finish with a famous saying from 'Are you being served': keep up the good work!


    Cheers. I love these sorts of problems - especially ones like this that are just a bit beyond my Maths knowledge - so I have to use reason to solve them (if I can).

    Also, if we have (x + y) mod z, that is equl to (x mod z) + (y mod z), and that should enable us to avoid using big integers.


    I still reckon that the best thing to use are Strings (or possibly StringBuilders), because we're only interested in comparing numbers of equal length, or individual digits of a number, so a String or char comparison will yield the same result as a numeric one; and it's dead easy to add/remove 'digits' from a StringBuilder.

    It's also the form we get A and B in, so there's no conversion involved.

    Winston
     
    Piet Souris
    Master Rancher
    Posts: 2758
    93
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Treating A and B as strings: certainly. It makes getting the first digit so much easier, as well as counting the number of digits...

    But I meant calculating permutations. Rather sooner than later you're bound to leave the 'long' space. Now, if we can report outcomes modulo (10^9 + 7), then, since (ab) mod x = (a mod x) * (b mod x), you can avoid big integers by applying this rule as soon as you exceed 10^9 + 7.

    Unfortunately, this doesn't apply to division. (8 / 4) mod 5 != (8 mod 5) / (4 mod 5), so if we, say, must calculate 40! / (2! * 4! * 5!), then we still need something special (I simply used BI's for the time being. since my old VBA routines for C(n, m) were based on eliminating common factors and using doubles, and I don't want to use these).

    Well, I hope I have time to implement what I wrote about, since from tomorrow I'll be on holidays for a week, without internet
     
    Ramsin Khoshaba
    Ranch Hand
    Posts: 65
    7
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    There exists this math library, which includes some combinatorics functions:
    https://commons.apache.org/proper/commons-math/

    Unfortunately, there is no function for calculating multinomial coefficients.
     
    It is sorta covered in the JavaRanch Style Guide.
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!