Finding all possible combinations of numbers to reach a given sum

[Melba23]

jchd,

Is there a "standard" answer?

M23

[Melba23]

ferradavi,

After a lot of testing I managed to break my suggested solution, as I feared might well be the case if there were just not enough of the required values to make up the sum:

Unable to factor 82 after 106946 successful passes
Unable to factor 380 after 133703 successful passes

So it is not a perfect solution, but seems a pretty good approximation.

M23

Edited February 19, 2016 by Melba23

[jchd]

The standard answer for small-scale problems is essentially brute-force. Of course one hits a computability wall when the scale grows significantly. Algorithms used for certain variants of the knapsack problem can be used with success.

It's only when the problem is more constrained (e.g. sums of subsets of primes) that deeper number-theoretic algorithms enter into play, but none are trivial. It's somehow surprising that additive NB (number theory) is globally much more difficult than multiplicative NB, despite addition being a "simpler" operation than multiplication, at least from a intuitive point of view.

[Melba23]

jchd,

I have been reading about it this afternoon - fascinating but definitely "non-trivial" to my eyes so I will stick with my brute force approach. Thanks for replying.

M23

[RTFC]

@Melba23 and @jchd: This is an example of an NP-complete problem, and we can actually do a lot better than a brute force approach. When I have a few spare hours I'll translate an existing code (in a different language) I've got for these kinds of tricky problems into AutoIt. It won't guarantee that the global optimum is always found, but it homes in pretty quickly on the most promising candidate region(s) in any contiguous solution hyperplane, and you can tweak how aggressively it should optimise its search. Plus, you can define any number of competing constraints. I would not recommend brute-force for anything other than 1) an exhaustive mapping of the complete space, or 2) a problem that provides no quantified measure of how well you're doing with you current guess.

Unfortunately, you'll have to bear with me for a bit, because I'm off this entire weekend.

[Melba23]

RTFC,

I shall look forward to seeing what you come up with as a solution. But do enjoy the weekend first - we alas are promised rain and high winds.

M23

[RTFC]

Thanks, M23, We are promised the exact same weather where I am. May I suggest the AutoIt community acquires an archipelago of tropical isles for R & R of its most productive members? I'll promise to put this high on my todo-list. I should mention though, that this algorithm identifies a single optimum solution (based upon user-defined conditions, so in this case, the most parsimonious summation of some of the terms listed in the input array (condition 1) that is also closest to the specifiied target (condition 2)). So it won't yield all possible optimal permutations, as the OP originally requested; for that you would need brute force, as that requirement would match the first of the two scenarios I listed above.

Edited February 19, 2016 by RTFC

[ferradavi]

Wonderful M23 !!! You're great!!!

But now I need to learn your "lateral thinking" approach.

I'm serious!!! 

I'll appreciate every suggestion about books regarding this subject.

 

[Melba23]

ferradavi,

Quote

I need to learn your "lateral thinking" approach

Not mine at all, as you can see here: Lateral Thinking. I was introduced to the concept at school by a couple of very good teachers soon after Edward de Bono published his book and I have found it an invaluable technique over the years.

M23

[ferradavi]

@Melba23 Thank you. It's very interesting!

@RTFC I'm curious to know your solution.

@ALL thank you for your attention and prompt reply

Edited February 19, 2016 by ferradavi

[czardas]

Interesting topic. If the total sum of all the candidate numbers is less than double the target value, then using subtraction from the total sum would (generally) speed up brute force attempts. hic

Sorting the numbers first would enable more refined targeting of viable candidates (using a method modelled on the binary search algo). It's still a bit of a sticky (recursive) mess. 

You could also eliminate certain combinations which cannot possibly reach the target (for example determined by divisibility - the target/difference may be odd or even etc). I imagine this could go on and on.

8 hours ago, jchd said:

It's somehow surprising that additive NB (number theory) is globally much more difficult than multiplicative NB, despite addition being a "simpler" operation than multiplication, at least from a intuitive point of view.

Interesting comment (as always ), but it's not so surprising in this particular setting. It's very easy to eliminate non-factors.

Edited February 20, 2016 by czardas

[Melba23]

ferradavi,

Some more investigation into the failure cases I mentioned above have shown that they occur only when there are no " 1 " factors in the list - the total reached by the algorithm therefore ends up one short and there is no " 1 " factor to reach the required total.

So I have added a "adjust" algorithm to cater for this case. It works like this: Look for the smallest remaining factor and then try and replace an existing factor with another slightly lower factor that has not yet been used - calculated so that adding the lowest available factor will make the total correct.

I know it sounds complicated, but here is a simple example (taken from a real case):

• Looking for 320,  but total reached only 319 as no " 1 " available to make the count correct.
• Lowest available factor is a " 2 " - so we need to reduce the total by 1 so that we can add 2 and make the required value.
• Start by seeing if we can replace a " 9 " by an " 8 " - but in this case there were no available " 8 " factors as they had all been used previously
• So we drop down through the factors and the first possible "match" we find is replacing a " 6 " by a " 5 " - so that is what we do
• Finally we add the available " 2 " factor to make the count correct.

Here are the factor strings (taken from the same case) before and after the change:

9+9+9+9+9+9+9+9+9+9+9+9+8+8+8+8+8+8+8+8+8+7+7+7+7+7+7+7+7+7+7+7+7+7+6+6+6+6+6+6+6+6  =319
9+9+9+9+9+9+9+9+9+9+9+9+8+8+8+8+8+8+8+8+8+7+7+7+7+7+7+7+7+7+7+7+7+7+6+6+6+6+6+6+6+5+2=320
                                                                                  ^        <-- Changed
                                                                                    ^      <-- Added

I hope that makes sense.

I have now had the modified code running for over 5,000,000 cycles and the only failure has been when it was asked to reach a total of " 1 " with no " 1 " elements - which I regard as a very edge case and one for which is very easy to create an exception.

Here is the code:

expandcollapse popup

#include <Array.au3>
#include <MsgBoxConstants.au3>

HotKeySet("{SPACE}", "_NormalCheck")

Global $fNormalCheck = False
Global $iCount = 0

ConsoleWrite("Running" & @CRLF)

While 1

    Local $iMaxPossible = 0

    ; Create random 81 elements and calculate the max possible value
    Global $aFactors[81]
    For $i = 0 To 80
        $aFactors[$i] = Random(1, 9, 1)
        $iMaxPossible += $aFactors[$i]
    Next

    ; Determine required number
    $iRequired = Random(1, $iMaxPossible, 1)

    ; Count number of each separate element - second column shows remaining elements after the first pass
    Global $aFactorCount[10][2]
    For $i = 1 To 9
        $aFactorCount[$i][0] = 0
        $aFactorCount[$i][1] = 0
    Next
    For $i = 0 To 80
        $aFactorCount[$aFactors[$i]][0] += 1
        $aFactorCount[$aFactors[$i]][1] += 1
    Next

    While 1

        ; Declare variables
        Local $iTotal = 0, $iRemainder = $iRequired, $sFactors = ""

        ; Starting with the highest element
        For $iFactorValue = 9 To 1 Step -1
            ; How many can be used to reach the required value
            $iFactorReq = Int($iRemainder / $iFactorValue)
            ; if there are not enough, then only use the available number
            If $iFactorReq > $aFactorCount[$iFactorValue][0] Then
                $iFactorReq = $aFactorCount[$iFactorValue][0]
            EndIf
            ; Adjust values for next pass
            For $j = 1 To $iFactorReq
                ; Increase total
                $iTotal += $iFactorValue
                ; Adjust remainder
                $iRemainder -= $iFactorValue
                ; Create result string
                $sFactors &= $iFactorValue & "+"
                ; Reduce remaining elements
                $aFactorCount[$iFactorValue][1] -= 1
            Next
            ; If required total reached then stop
            If $iTotal = $iRequired Then
                ExitLoop
            EndIf
        Next

        If $iTotal = $iRequired Then

            ; Display factors found to reach required value
            If $fNormalCheck Then
                ConsoleWrite("Normal:" & @CRLF & StringTrimRight($sFactors, 1) & "=" & $iRequired & @CRLF)
                $fNormalCheck = False
            EndIf

            ; Just to show loop running and allow CPU to breathe
            $iCount += 1
            If StringRight($iCount, 4) = "0000" Then
                ConsoleWrite("Count = " & $iCount & @CRLF)
                Sleep(10)
            EndIf

            ; Run another list/required pair
            ExitLoop

        Else

            ; Confirm we are in the "off by 1 with no [1]s" case
            If ($iRequired - $iTotal = 1) And $aFactorCount[1][0] = 0 Then

                ;Display
                ConsoleWrite("Adjusting:" & @CRLF & StringTrimRight($sFactors, 1) & "=" & $iTotal & @CRLF)

                ; Find lowest remaining factor
                Local $iLowest = -1
                For $i = 1 To 8
                    If $aFactorCount[$i][1] <> 0 Then
                        $iLowest = $i
                        ExitLoop
                    EndIf
                Next

                ; Now find a pair of factors to adjust
                $fAdjust = False
                ; Look for a factor to replace
                For $iReplace = 9 To $iLowest + 1 Step -1
                    ;Calculate paired factor required
                    $iReplacer=$iReplace - $iLowest + 1
                    ; Convert both to strings
                    $sToReplace = $iReplace & "+"
                    $sReplacer =  $iReplacer & "+"
                    ; Is there an instance of the factor to replace and an available replacement of the required value
                    If StringInStr($sFactors, $sToReplace) And $aFactorCount[$iReplacer][1] <> 0 Then
                        ; Replace the factor (always the final instance)
                        $sFactors = StringReplace($sFactors, $sToReplace, $sReplacer, -1)
                        ; And add the lowest factor
                        $sFactors &= $iLowest & "+"
                        ; Total now matches
                        $fAdjust = True
                        ExitLoop
                    EndIf
                Next

                If $fAdjust Then
                    ; Announce successful adjustment
                    ConsoleWrite(StringTrimRight($sFactors, 1) & "=" & $iRequired & @CRLF)
                    ConsoleWrite("Adjusted - Success" & @CRLF)
                    
                    ; Run another list/required pair
                    ExitLoop
            
                Else
                    ; Announce failure to adjust
                    ConsoleWrite("Adjustment - Failed" & @CRLF & "Req: " & $iRequired & " - Reached: " & $iTotal & @CRLF & StringTrimRight($sFactors, 1) & @CRLF)
                    
                    ; End script
                    ExitLoop 2
                EndIf

            Else
                ; This has never happened in over 5 million cycles
                ConsoleWrite("Unable to factor" & @CRLF & "Req: " & $iRequired & " - Reached: " & $iTotal & @CRLF & StringTrimRight($sFactors, 1) & @CRLF)

                ; End script
                ExitLoop 2
            EndIf

        EndIf

    WEnd

WEnd

Func _NormalCheck()
    $fNormalCheck = True
EndFunc

Pressing {SPACE} will display the current factor list so you can check it is correct - any adjusted lists display automatically so you can see what the code did to correct the factors. If the code cannot adjust - or the failure is not because there are no " 1 " elements (which has never happened so far) - the script stops in disgust.

I enjoyed coding that as a diversion on a very wet and windy morning - thanks very much for posing the question.

M23

Edited February 20, 2016 by Melba23
Formatting

[ferradavi]

Hi M23,

you have done a fine job. I hope for you tomorrow will be sunny 

Now I have to find a way to use your code for a practical purpose... as required during the classes. I think the better one is an auto-solving game... I imagine a 9x9 grid with random numbers (from 1 to 9), and a random target number, what do you think?

 

[Melba23]

ferradavi,

Glad you like it - I must say I am quite pleased with that little piece of code. But alas tomorrow is forecast to be just like today.

Quote

I imagine a 9x9 grid with random numbers (from 1 to 9), and a random target number, what do you think?

That is exactly what you have with the script I posted - each pass generates a new list and a new target.

M23

[ferradavi]

M23,

it's a shame...for the weather!

Maybe the fastest way could be to solve an existing game like this one: <snip>

Even if it isn't a 9x9 grid it seems to be suitable for the purpose (Random Numbers in a grid and a Target Number). How to quickly read (recognize) the numbers in the grid and memorize them in the list ($aFactors array)?

Thank you!

Edited February 21, 2016 by Melba23
Link removed

[Gianni]

1 hour ago, ferradavi said:

. . . Now I have to find a way to use your code for a practical purpose . . .

another practical pupose could be to build a rectangular wall having bricks with different dimensions, a similar problem is described here:

http://codegolf.stackexchange.com/questions/49536/build-a-steady-brick-wall (leaving aside the part about "instability")

Edited February 20, 2016 by Chimp

[iamtheky]

Is this accurate (other than random, that cant be right, if you could fix that it would be super), I am doing my best at brute forcing my way there

All attempts take the same amount of time, and there are certainly results that seem mathishly correct.

expandcollapse popup

;BruteForceFactory(BFF)
#include<array.au3>

local $aAnswers[0]
;~ $target = 110
$target = 50
;~ $target = 9

Global $aArray = [9,2,2,3,1,1,6,3,4, _
                  4,2,3,4,5,6,7,8,7, _
                  7,2,3,4,5,1,7,2,2]


$aWork = $aArray
_ArraySort($aWork , 1)
$last = ""
$count = 0

for $k = ubound($aWork) - 1 to 0 step - 1
tooltip($count , 0 ,0 )

If $count = ubound($aArray) * ubound($aArray) Then exitloop

$total = $k <> 0 ? _ArrayToString($aWork , "+" , 0 , $k) : $aWork[0]

    If execute($total) = number($target) then
        _ArrayAdd($aAnswers , $total)
    EndIf

    If $k = 0 Then
        $aWork = $aArray
        $count += 1
        _ArraySwap($aWork , 0 , mod($count , ubound($aWork) - 1))
        $k = ubound($aWork) - 1
    Else
        _ArrayDelete($aWork , random(0 , ubound($aWork) - 1 , 1))
    EndIf
next

If ubound($aAnswers) < 1 Then msgbox(0, '' , 'no match')

$aAnswers = _ArrayUnique($aAnswers , 0 ,0 , 0 , 0)
_ArrayDisplay($aAnswers , ubound($aAnswers) - 1 & " Unique Combos")

 

Edited February 20, 2016 by iamtheky

[Melba23]

ferradavi,

Be careful about the suggestions you make - read the Forum rules to see why the link above has now been removed.

M23

 

[ferradavi]

M23,

I read their rules. Nothing about automation. It isn't a gambling site and the code cannot be used to cheat or to make money with. However I'm sorry and accept your advice. 

[Melba23]

ferradavi,

It is not a question of their rules, but ours:

Quote

Do not ask for help with AutoIt scripts, post links to, or start discussion topics on the following subjects:

• [...]
• Launching, automation or script interaction with games or game servers, regardless of the game.

M23