Finding all possible numbers for a sum

[Nicolas]

Hi!

I was about to write a very inefficient and time consuming function (I'm a AHK begginer...) that would do the following:

Sum(s="",i="") ; where "s" is the result of the sum and "i" the amount of numbers added to get the sum

eg.: let s=20, i=4 --> 20 = n1+n2+n3+n4, find all possible DIFFERENT n_i values (n1 != n2 != n3 ...) for which the expression is valid. "n_i" and "i" have to be greater or equal to 1 and smaller or equal to 9.

If all conditions are met, set an output ideally as a chart of all possible sums, but it can just be [Msgbox,%s%=%n1%+%n2%+%n3%+...] (I'll probably change the output later anyways).
Tell me if I forgot to mention important details.

What is an efficient way to write this without hundreds of lines of code?

[boiler]

This problem is really not about AHK as it is about the coding logic that would be generally the same no matter what the language. I suggest you write out the logic in pseudo-code (or in AHK the best you can) then ask specific questions about AHK implementation and/or syntax.

[FanaticGuru]

This problem is really not about AHK as it is about the coding logic that would be generally the same no matter what the language. I suggest you write out the logic in pseudo-code (or in AHK the best you can) then ask specific questions about AHK implementation and/or syntax.

I agree with boiler. This is a logic problem.

If I was going to code it, I would forget about computer code completely and just figure out how I would go about doing this on paper manually. Starting with small numbers and working up to the more complicated. Till I had a reliable way to do it on paper and then I would just code that process.

With just a moment scribbling on paper I believe I understand the basic process to getting all the combinations, maybe if I get time I will try coding a solutions. I like puzzles.

FG

[Nicolas]

Thanks for the answer!

First of all, 2 precisions : First, the values of n_i are whole numbers, no decimals (not to end up with infinitely many results!). Second, I'd rather have the output as all possible values for each variables instead of all combinations of sums (way more condensed and practical for my purposes).

As for the logic, I just realized that the route I was going to take was a death trap. I was originally going to set each variable's value to 1, and evaluate their sum. Then, I would compare that sum to the value of "s" and if both were equal and all the digits of the sum were different, I'd tell the program to output the sum in a certain way (eg.: a string in Excel). However, if the sum was not equal to "s", I'd add 1 to the first digit and repeat the process, testing each possible combinations. The thing is, to test a sum for which there are 9 variables, the program would have to repeat this process 9^9 times!!!

The only thing I thought of is reducing the maximum number of variables to a max of 4-5 (9^4 or 9^5 verifications), that way I wouldn't have to wait forever to get all answers.

I have no idea if there is any logic that can be used to speed things up. One way would be to tell the function to only try sums for which all digits are of different values (eg.: not trying something like 20 = 5 + 3 + 5 since there are two 5's in the sum).

[iPhilip]

I don't often use recursion to solve problems so it was fun to tackle this one. Here is my code:

Code: Select all

global n,o,sum

Loop, 4
   MsgBox % A_Index ":`n" Sums(9,A_Index)
return

Sums(s,i,a:=1,b:=9)
{
   if (a > b)
   {
      MsgBox, Please make sure that the lower bound is`nlower than or equal to the upper bound.`n`nThe script will now exit.
      ExitApp
   }
   o := "", n := [], sum := []
   n[0] := a-1
   sum[0] := 0
   RecSum(s,i,1,a,b)
   return o ? o : "No solution"
}

RecSum(s,i,j,a,b)
{
   if (j > i)
      return
   Loop, % i = j ? b-n[j-1] : b-a+2-i
   {
      n[j] := n[j-1] + A_Index
      Sum[j] := Sum[j-1] + n[j]
      if (Sum[j] > s)
         break
      if (i = j && Sum[j] = s)
      {
         o .= String(n) "=" s "`n"
         break
      }
      RecSum(s,i,j+1,a,b)
   }
}

String(n)
{
   for k, v in n
      s .= k ? Format("{1:+d}", v) : ""
   return LTrim(s, "+")
}

Edit: Generalized the code so that it takes an arbitrary interval [a,b], with a default of [1,9].

Cheers!

[Helgef]

@op, this types of equations are called edit: diophantine equations. diophante equations, google it for proper spelling
There are all sorts of algorithms for solving different types of such equations. In your case you might need to resort to brute force. But you should be able to avoid checking all possible combinations, I guess.

@iPhilip, I wouldn't have thought of solving this recursively, I look forward to check out your method later.

[Helgef]

@ iPhilip. It seems very good . Could you generalise it, such that it takes an arbitrary interval [a,b] that all ni is required to lie within it. As it is now, the interval is [1,9].

[Nicolas]

Thanks a lot @iPhilip, that's pretty close to what I asked for!

Your program seems to stop at i=4, is there a way to increase it or would it be too hard/too much work?

Either way, it's good enough for what I'm using it for!

[boiler]

This lets you enter the numbers you want each time you run it. First the sum, then how many numbers.

Code: Select all

global n,o,sum

InputBox, sEntry, Sum Solver, Enter the desired sum number:,, 236, 136
InputBox, iEntry, Sum Solver, Enter how many numbers are to be added:,, 309, 131

Loop, %iEntry%
   MsgBox % A_Index ":`n" Sums(sEntry,A_Index)
return

Sums(s,i)
{
   o := "", n := [], sum := []
   n[0] := sum[0] := 0
   RecSum(s,i,1)
   return o ? o : "No solution"
}

RecSum(s,i,j)
{
   if (j > i)
      return
   Loop, % i = j ? 9-n[j-1] : 10-i
   {
      n[j] := n[j-1] + A_Index
      Sum[j] := Sum[j-1] + n[j]
      if (Sum[j] > s)
         break
      if (i = j && Sum[j] = s)
      {
         o .= String(n) "=" s "`n"
         break
      }
      RecSum(s,i,j+1)
   }
}

String(n)
{
   for k, v in n
      if k = 0
         continue
      else
         s .= v "+"
   return RTrim(s, "+")
}

Nice job, iPhilip.

[Exaskryz]

I'd really need to review iPhillip's code to grasp what his solution was.

The following is me rambling! Please enjoy.

But to me, I'm noticing the problems break down into smaller ones*.

Say you want to know all 3 digit sums (given all digits are different) for the number 8. The answer, just mentally bruteforcing, is

1+2+5
1+3+4

1+4+3
1+5+2
2+1+5
2+5+1
3+1+4
3+4+1
4+1+3
4+3+1
5+1+2
5+2+1

You'll notice I spaced away two particular ones at the top. The other 10 answers are just different permutations; we are most likely just interested in the combinations. The two distinguished ones are sorted in ascending order, we can do the same in the code implementation - we don't need to check for non-ascending sums.

*What this breaks down to in smaller problems is saying "What is 1+7?" without using 1 as one of the addends. The solutions to 7 are 1+6, 2+5, and 3+4; we scrap the 1+6. How easy incorporating this recognition into code is unclear to me; I'm not seeing any immediate benefit to it.

Using a bruteforce method with just the ascending order should work. Let's work it out with 13 and using 4 terms.

1+2+3+4 = 10 < 13
1+2+3+5 = 11 < 13
1+2+3+6 = 12 < 13
1+2+3+7 = 13 = 13 ; this is good. Now any changes we make to our addends must be balanced - take one away and give to another. Save this as a checkpoint.
1+2+4+6 = 13 = 13 ; notice I started to decrease the last addend. I didn't try to increase it to 8, knowing that the first 3 addends can not go any lower.
1+2+5+5 --- error, we've duplicated. And notice that it duplicated using the two terms we were changing, this marks an endpoint.

1+2+3+7 = 13 = 13 ; this was a checkpoint. Now we're going to add to a different term.
1+3+3+6 --- error, we've duplicated. But we're going to keep going because we got a duplicate with an addend that was unchanged.
1+4+3+5 = 13 = 13 ; this is a good one. Interestingly, we're now out of ascending order... Hmmm.
1+5+3+4 = 13 = 13 ; this is just a permutation of the above. What I'm noticing is our two changed addends have reversed order of superiority, that is if it's a + b + c + d, we started with b<d, but now b>d. Looking back to the last "endpoint" we got where it failed, we can conclude: if b>=d, then it's an endpoint.

1+2+3+7 = 13 = 13 ; back to the checkpoint.
2+2+3+6 --- dup error
3+2+3+5 --- dup error
4+2+3+4 --- dup error and we have a>=d, where a and d were the terms we were changing. So there's no solution here.

This leads me to the conclusion that there are 3 equations for summing four positive integers to 13:

1+2+3+7
1+2+4+6
1+4+3+5

That last one could be sorted into ascending order... Or there could be a trick for ensuring ascending order. Just before we found 1+4+3+5, we found 1+3+3+6 - if we treat the case where we duplicate a "Constant" as a "fake" checkpoint of sorts, then we could go back to changing terms c and d such that 1+3+3+6 --> 1+3+4+5. But if we used that same kind of technique through the 2+2+3+6 mess, we'd have detoured ourselves to 2+3+3+5 into 2+3+4+4... Hmm, that's the same "trail" we took, just in ascending order. But then it takes a different way to identify that it's an endpoint that failed with no further progress. We can't use the a>=d trick now, but does it finalize to if c>=d? Maybe that's it -- if there is a duplicate value, increase the right-most of the duplicate and decrease the last most term.

So it seems the mechanics in bruteforcing a "smart" way would be:

1) Take the lowest possible sum of i addends (1+2+...+i). Increase the value of the last term by the difference of that lowest possible sum and the target sum. This is your first solution.
2) Then decrease the value of last term by 1 and increase the second-to-last term by 1.
2b) If the second-to-last term >= last term, that's the end of that branch. All permutations preceding this endpoint are considered valid solutions.
3) Go back to your first solution, and increase the value of the third-to-last term by 1 and decrease the value of the last term by 1.
3b) This will result in a duplicate. In the case of a duplicate, increase the right-most duplicate by 1 and decrease the last term by 1.

Keep repeating steps 2 and 3 (and their b substeps).

The only problem with the steps above is it seems to miss out on sums that all the terms can be increased by more than 1 (bar the last term). Let's work it out in 3 addends for sum 13:

1+2+10
1+3+9
1+4+8
1+5+7

2+3+8
2+4+7
2+5+6

That would be the end of it, technically, as going back to the first solution leaves no other addends to increase. I think all that would need to happen at this point is treat the first solution that had increased the first addend - and worked - as our "first solution" as used in Step 3 above. That is, instead of 1+2+10, we'll now use 2+3+8 as a term. And instead of working our way from right to left, just jump right into increasing the first term:

2+3+8 --> 3+3+7 -->
3+4+6

So I suppose Step 4 would be "If there are solutions after increasing the first addend by 1, take the first solution given by the increased first addend, again increase the first addend and decrease the last addend, repeating step 3b to find more solutions."

Translating all that into code sounds like a good way to pass the time. If only I hadn't procrastinated enough as is. And heck, perhaps this is what iPhillip's code is doing anyhow.

[Helgef]

@Exaskryz, I think you are on the right track to find a general algorithm. Also, looking at iPhilips method, you can see that the termination criterias are either, solution found or sum to high, there is no sorting or checking if solutions are permutated, i.e., it is utilising a pattern of the solutions, as you are also suggesting. I wouldn't call either of your approaches brute force methods, it is more refined.

[iPhilip]

@ iPhilip. It seems very good . Could you generalise it, such that it takes an arbitrary interval [a,b] that all ni is required to lie within it. As it is now, the interval is [1,9].

Thank you, Helgef. I edited the above code so that it takes an arbitrary interval [a,b], including negative numbers. Note that, in the case of an interval that crosses zero (e.g. [-1,1], zero is an allowed integer in the solution.

Thanks a lot @iPhilip, that's pretty close to what I asked for!

Your program seems to stop at i=4, is there a way to increase it or would it be too hard/too much work?

Either way, it's good enough for what I'm using it for!

The script actually covers the interval [1,9]. The 4 you see is just a way to demonstrate four different examples, i.e. Sums(9,1), Sums(9,2), Sums(9,3), Sums(9,4).

This lets you enter the numbers you want each time you run it. First the sum, then how many numbers ... Nice job, iPhilip.

Thank you, boiler.

... I'm noticing the problems break down into smaller ones ...

I noticed the same thing. It's what led me to use recursion.

... looking at iPhilips method, you can see that the termination criterias are either, solution found or sum to high, there is no sorting or checking if solutions are permutated ...

What ensures that there are no permutated solutions is the starting value of the loop for the following integers. For example, in the case of s=10, i=2, the solution 3,7 will not be permutated because the loop for the first value of 7 will start at 8, i.e. the script will start at [7,8] and continue with [7,9]. The line n[j] := n[j-1] + A_Index insures that. I hope this helps.

Cheers!

[Helgef]

Very nice iPhilip!
There are a few simple checks to do in the begining, to ensure that solutions exists.
Put this before the recursive function is called,

Code: Select all

; Determine if solution exists.

if (i>b-a){
	Msgbox, % "No solutions possible, to many unknowns (" i ") for the interval [" a "," b "]." 
	return
}
maxSum:=0,minSum:=0	
Loop, % i
	maxSum+=b-A_Index+1,minSum+=a+A_Index-1
if (s>maxSum || s<minSum) {
	Msgbox, % "No solutions possible, for the current parameters, sum need be between: " minSum " and " maxSum "."
	return
} else if (maxSum=s) {	; Special case, return solution
	Loop, % i
		str.=b-A_Index+1 "+" 
	return RTrim(str,"+") "=" s
} else if (minSum=s) {	; Special case, return solution
	Loop, % i
		str.=a+A_Index-1 "+"
	return RTrim(str,"+") "=" s
}