Math problem, maybe for the programmer-minded?

Not Games
1

I have nine numbers, values 0 to 4.
I want to check that when eight of those number are not 0, two are 1, two are 2, two are 3, and two are 4.
The only tools I have for doing this are simple ones like adding all the numbers together, multiplying all the non-0 numbers together, etc. Oh, I can also check how many are not 0.

So, my current best effort is three checks:
Check that eight numbers are not 0
Check that adding all nine numbers together equals 20
Check that multiplying all non-0 numbers together equals 576

Is that airtight? Are there other combinations than 0,1,1,2,2,3,3,4,4 that fit those criteria? Is there an easier way to do it?

Yes, this is how I spend my Sundays, sorry.

1 Like
2

Not sure if there is a more efficient way to do it, but that seems airtight.

  • The prime factorization for any number is unique, and the prime factorization for 576 is (2,2,2,2,2,2,3,3).
  • Since only values 0-4 are permitted, the only combination of those primes that would allow for 8 or fewer values is (2,2,2,2,3,3,4), (2,2,3,3,4,4) and (3,3,4,4,4), with 1’s filling in the remaining values.
  • However, since all these combinations have the same sum (since 2*2 = 2 + 2), but differing quantities of 1’s, they will have a different sum total of values. The only combination summing to 20 is (1,1,2,2,3,3,4,4).

The product check does most of the work, but you can’t eliminate those other two values without checking the sum, and you need to check the number of non-0 values to eliminate other options, so I think that’s efficient too.

2 Likes
3

If there needs to be 2 1s, 2 2s, 2 3s and 2 4s, does that mean there always has to be one 0? Or can there be more than two of the values 1-4?

1 Like
4

I also need to generalize to simpler cases using the same three checks:
0,0,0,1,1,2,2,3,3 with results 6, 12, 36
0,0,0,0,0,1,1,2,2 with results 4, 6, 4

Any combination of 0-4 for any of the values is possible to input.

5

number of non-zero digits, sum of digits, product of non-zero digits? And only considering when there are either exactly 2 or exactly 0 of each of the digits 1, 2, 3, and 4?

6

I am unable to check whether there are only sets of two identical numbers, that’s what the checks have to establish.

1 Like
7

Do you need to detect, for instances, when it is 0,0,0,0,0,1,1,3,3?

Just trying to understand.

8

Checking # of non-zero cards, sum of digits, and non-zero product should be enough to tell you any possible combination of values. If you know how many values are non-zero, the prime factorization of the non-zero product will give you a unique quanity of 2’s and 3’s that make up the product. You can pair up 2’s into 4’s, but as the number of 4’s increases, the sum of all 9 numbers also strictly increases, so the sum will uniquely determine the combination of values.

2 Likes
9

Oh, I see. No, that should never happen, I can cap the numbers when the player count is lower. So, when 4 non-0 numbers, only values of 0-2, when 6 non-0 numbers, only values of 0-3, and when 8 non-0 numbers, values of 0-4 are valid.

1 Like
10

Thanks, your answers are exactly the confirmation I was looking for. I am curious whether refining the conditions as pillbox is doing can produce a simpler set of checks.

1 Like
11

It’s pretty late here and I’m tired, but I think checking the number of non-zero digits is in [ 4, 6, 8 ], the sum digits is in [ 6, 12, 20 ] and the product of non-zero digits is in [ 4, 36, 576 ] is likely about as optimal as you can get with the limited toolset you have.

I ran through all the permutations and if you make those 3 assertions, you don’t actually have to assert a specific combination of which index in each check (like you don’t have to assert that sum_of_digits == 6 AND product_non_zero == 4; there’s no combination of values that is going to produce mixed-matches across the checks; i.e. you don’t have to worry about a set of numbers where the sum_of_digits matches the sum of 0,0,0,0,0,1,1,2,2 and the product_non_zero matching the product of 0,1,1,2,2,3,3,4,4.

Now, I’m not sure what toolset you’re working within, so it may just be easier to assert all three simultaneously… or maybe it’s easier to just make sure that each of those things matches one of the 3 values in each of the assertions.

1 Like
12

Cheers!

It’s nice to have confirmation, this isn’t the kind of thing I usually tackle. If I need all 3 checks for one situation, it makes no difference trimming one or two out for another situation - the overhead is (I think) in having the 3 checks running at all. The whole thing is kind of slow at the moment, but I think that’s mainly due to other factors.

2 Likes