Finding all possible combinations of numbers to reach a given sum

[ferradavi]

M23,

I see. Ok!

@iamtheky very interesting solution.

 

Edited February 21, 2016 by ferradavi

[ferradavi]

I modified the list in a 2d array, 8x8 grid and I defined the target number between 11 and 50.

expandcollapse popup

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

Local $iMaxPossible = 0

;Create random 64 elements and calculate the max possible value
Global $aFactors[8][8]

For $i = 0 To 7
   For $ii = 0 To 7
      $aFactors[$i][$ii] = Random(1, 9, 1)
      $iMaxPossible += $aFactors[$i][$ii]
   Next
Next

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

ConsoleWrite("Required: " & $iRequired & @CRLF)

Global $aFactorCount[10]

For $i = 0 To 7
   For $ii = 0 To 7
    $aFactorCount[$aFactors[$ii][$i]] += 1
   Next
Next

; 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] Then
        $iFactorReq = $aFactorCount[$iFactorValue]
    EndIf
    ; Adjust values for next pass and create result string
    For $j = 1 To $iFactorReq
        $iTotal += $iFactorValue
        $iRemainder -= $iFactorValue
        $sFactors &= $iFactorValue & "+"
    Next
    ; if required total reached then stop
    If $iTotal = $iRequired Then
        ExitLoop
    EndIf

Next

_ArrayDisplay($aFactors,"8x8 Grid")
;_ArrayDisplay($aFactorCount, "", Default, 8)


If $iTotal = $iRequired Then
    ConsoleWrite(StringTrimRight($sFactors, 1) & "=" & $iRequired & @CRLF)
    MsgBox(0,"Solution",StringTrimRight($sFactors, 1)& "=" & $iRequired)
Else
    ConsoleWrite("Unable to factor " & $iRequired & @CRLF)
    MsgBox(0,"No Solution","Unable to factor")
EndIf

I'd like to update the 2D array when the target is reached:

i.e. assuming that:

1. the starting grid (2d array), randomly generated, is the first file I attached below (8x8 grid original.bmp), 
2. and the target number is 44

the result is:

9+9+9+9+8 = 44

How can I get (re-write) the 2D array I attached as second image (8x8 grid update.bmp) where the remaining elements are slid down in the column (not only deleted).

Then, I'd like to re-start the script using a loop, drawing another random target number and so on till the end: a funny and simple auto-solving mathematical game.

Thank you!

8x8 grid original.bmp  8x8 grid update.bmp

Edited February 22, 2016 by ferradavi

[RTFC]

 

As promised, here's my take on this.

 

[jchd]

Agreed SA can be used in general for finding a solution in similar contexts, well unless it fails to. Yet that doesn't answer the OP original question (find all solutions). SA is also pretty hard to analyze computationally and be proven to succeed, if at all.

[RTFC]

@jchd: I already mentioned in post#27 in this thread that SA yields a single solution per run, and the OP mentioned this as alternate requirement after their initial post. As to your other points, you're definitely right that SA is hard to analyse, and cannot be proven to succeed (and I never claimed this). But I'm coming at this from a more practical perspective, based upon my own work using SA to come up with reasonable solutions that balance many conflicting requirements in a high-dimensional solution space, before the universe dies of heat-death. And if you run my first SA example a few times, you can see that in this particular case. most often it does come up with one of the several optimal solutions (exact target match + minimum number of terms). If the only other alternative is brute-force, and brute-force is going to take forever and a day, then I'll settle for anything that gives me a decent chance at a good estimate, even if its success is not guaranteed. I agree that it may be impossible to determine in advance how likely an acceptable outcome is. But the time gain w.r.t. brute-force can be so gargantuan that one can easily run dozens or hundreds of SA estimates to explore the SA solution space to get a sense of its distribution. Plus, I like the simplicity of the algorithm, wich is of course completely subjective.

Edited February 23, 2016 by RTFC

[ferradavi]

@RTFC Extremely refined!!!

[ferradavi]

On 20/2/2016 at 11:58 PM, iamtheky said:

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")

 

@iamthekyCould you explain me how does it work?

[RTFC]

@ferradavi: Thanks (didn't invent this though, just ported it to AutoIt). However, jchd is quite right in stressing this is not a fix-all, and it won't yield all permutations as you requested in your first post. Also, SA's efficacy and efficiency depend sensitively on the way you define and balance your cost functions; sometimes it can take a fair bit of fiddling before the algorithm starts finding what one wants it to find, rather than what one apparently instructed it to find. It all depends on the type of problem you're tackling.

Furthermore, I should have mentioned that if you change the target value in my test example 1 (the one that handles your scenario), you may have to also adjust the $minsumlength accordingly (so for example, if your target value is set to 12, $minsumlength would become 1 (base-0, so minimum two values to sum)). Anyway, have fun playing with it.

Edited February 23, 2016 by RTFC

[jchd]

Exactly: "know your data" is a pretty imperative prerequisite to using SA successfully since you can esily obtain surprisingly fast but poor results if you don't parametrize the search by means of suitable costs evaluators. That's why I never recommend SA to unexperienced audience. For French readers, SA translates as "recuit simulé", due to similarity with the rearrangement of atoms in crytals of some metals (e.g. copper) or alloys after fusion, cooling, re-heating to lower temp and re-cooling.

[RTFC]

@jchd: you're right, but I would argue that "know your data" applies pretty much across the board, regardless of what optimisation/minimisation algorithm you apply. And experienced audiences often make the same mistake, for example applying Gaussian-based statistics on distinctly non-Gaussian datasets, or attempting to invert a strongly underdetermined system. I like SA because it forces me to explicitly express my cost functions and thereby consider carefully how these expressions translate into whatever optimum I'm seeking. And when the outcome is unexpected/oviously wrong, the algorithm is also so simple that even a beginner can tinker with it (for example, by adjusting weights and scaling), whereas more sophisticated methods (e.g., downhill simplex, conjugate gradient) may be completely inscrutable  to someone without a solid maths background. In that sense, SA can be a good learning experience to get to know your problem better, at least that's how it works for me. But of course, no such method should ever be used as a black-box; I'm with you on that one.

Edited February 23, 2016 by RTFC
typo

[iamtheky]

5 hours ago, ferradavi said:

@iamthekyCould you explain me how does it work?

 

It iterates through the array X number of times (where x is the ubound * ubound).  after every iteration deletes a random element, after every full loop it resets the array and swaps out my starting element.   Hopefully getting enough variations of the data set to capture the targets.

Edited February 23, 2016 by iamtheky

[ferradavi]

@iamtheky That's really amazing!

Edited February 23, 2016 by ferradavi