[Maths] Set of numbers = X

[ronnie32]

Hello,

I'm working on a project, I would like to generate a set of 12 numbers (the first 3 and the last 4 are given), when adding all of them, equals X (lets say 60)

Example:

- My base is 262XXXXX1965

- I would like to generate 10 numbers from the following set of numbers 2+6+2+X+X+X+X+X+1+9+6+5 so the result should be 60

I was wondering if it would be possible? If yes, I have to compare them to my database, what do you think would be the best way codewise (I guess 2)?

1. Generate, save them in a text file, then compare the text file line by line to my database

2. Compare them one by one: generate, compare, generate, compare (x repeat)

Thanks for the help.

 

[RTFC]

Recently a very similar problem was discussed in this thread.

One possible solution is the first example in this thread.

[ronnie32]

11 minutes ago, RTFC said:

Recently a very similar problem was discussed in this thread.

One possible solution is the first example in this thread.

Problem is, that mine is based on 7 known numbers and 5 unknown

[RTFC]

So you would prefill your array with the known numbers at the front, and allow only the tail end to be changed.

[ronnie32]

11 minutes ago, RTFC said:

So you would prefill your array with the known numbers at the front, and allow only the tail end to be changed.

Care to explain that part:

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, _
                    2,2,3,1,5,5,7,1,4, _
                    3,2,1,2,3,6,6,6,4, _
                    3,2,3,4,5,6,7,8,3, _
                    2,2,3,8,1,4,7,1,2, _
                    1,7,3,5,5,6,7,1,2, _
                    7,2,3,7,5,1,7,8,9]

I know its commented, but I still don't understand that sequence in the array...

[RTFC]

That array was part of the posed problem in the other thread. In your case you would stick your fixed numbers at the front of it and pad the rest with digits 1-9 to swap into and out of your sequence. In the following example, note how variable $lockedlength determines the swapping areas:

expandcollapse popup

; Simulated Annealing example (combinatorial minimisation), by RTFC (2 Apr 2016)

; Note that this algorithm converges on A *local* minimum (in terms of the
; user-defined cost-function(s)), which is not necessarily THE *global* minimum.
; Note also that the search path, duration, and final result may differ from run to run.
; Several parameters can be tweaked to adjust this.

#include <Array.au3>
#include <Math.au3>

Global $temperat,$path,$kk,$nswap,$nswapstep,$cost,$altcost,$tempstep
Global $costadjust,$ttlsites,$totalcost,$factor,$maxsumlength,$maxsize
Global $site1,$site2,$index1,$index2,$weight_sum
Global $lockedlength

; initialise
SRandom(@MSEC+@AutoItPID)   ; initialise radnomising seed
$verbose=True           ; T: write regular progress updates to console
$factor=1               ; optional Oracle-response adjustment (not used here)
$sumlength=11           ; base-0

; adjust the balance of conditions here (see _Cost function)
$weight_sum=1           ; relative importance of matching condition 1 (sum = target)

; summation results buffer
Global $bestsum[$sumlength+1]
Global $bestsumlength=UBound($bestsum)

; define the summation result we wish to achieve (try different values here!)
$target = 60
; Note: if $target value is changed, you may have to adjust $minsumlength below as well!

; define our array of summation terms to select from
$dim=9
$ttlsites=$dim*$dim
$maxsize=$ttlsites-1


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

; in this specific case, we already know that we'll need exactly 12 terms
$minsumlength=11        ; base-0, so 12 entries altogether
$maxsumlength=11
$lockedlength=6     ; first 7 terms are locked (base-0)

;______START OF ANNEALING ROUTINE____________

$nover =1000            ; maximum number of changes at any temperature (for more complicated problems, set this several orders of magnitude higher)
$nlimit=Int($nover/4)   ; maximum number of successful changes before continuing
$nwrite=Int($nover/5)   ; default status update interval if verbose=.t.
$tempsteps=100          ; number of temperature steps to try
$tfactor=0.95           ; annealing schedule: temperature is reduced by this factor after each step

While True
    $temperat=0.5       ; initial temperature; smaller = more aggressive + more myopic search
    $absimp=0           ; counter
    $nswapstepzero=0    ; counter

    ; prep the cost vars
    $totalcost=_Cost()
    $cost=$totalcost
    $lowestcost=$totalcost
    $initcost=$totalcost

    ; main loop starts here
    For $tempstep=1 to $tempsteps       ; try up to N temperature steps
        $nswap=0
        $nswapstep=0
        For $kk=1 to $nover
            _TrySwap()      ;   swap and determine cost adjustment

            Switch _AskOracle()     ; Feel the Force, Luke.
                Case True
                    $nswap+=1
                    $totalcost+=$costadjust
                    $cost=$altcost

                    If $lowestcost>$totalcost Then
                        $nswapstep+=1
                        $absimp+=1
                        $lowestcost=$totalcost

                        ; ensure results buffer is sufficiently large
                        If $bestsumlength<=$sumlength Then
                            $bestsumlength+=5
                            ReDim $bestsum[$bestsumlength]
                        EndIf

                        ; flush current-best summation
                        For $bc=0 to $sumlength-1
                            $bestsum[$bc]=$aArray[$bc]
                        Next

                        ; pad tail with zeroes
                        For $bc=$sumlength to $bestsumlength-1
                            $bestsum[$bc]=0
                        Next

                        _ScreenOut()
                        If $totalcost<=0 Then ExitLoop
                    Endif

                Case Else   ; restore the previous state
                    $aArray[$index1]=$site1
                    $aArray[$index2]=$site2
            EndSwitch

            ; show we're still alive
            If $verbose And mod($kk,$nwrite)=0 Then _ScreenOut()
            If $nswap>=$nlimit Or $lowestcost<=0 then ExitLoop
        Next

        ; optional early-out scenario (disable for a more thorough search)
        If $nswapstep=0 then $nswapstepzero+=1
        If $nswapstepzero=10 then ExitLoop      ; no more improvements in the last N temperature steps

        ; reduce temperature = likelihood of following a trajectory away from the nearest LOCAL optimum (in the hope of getting nearer to the GLOBAL optimum)
        $temperat*=$tfactor
    Next

    ; present final result
    _Arraysort($bestsum)    ; just for clarity

    $summation="Best result so far (at a cost of " & $lowestcost & ") is: " & @CRLF
    $terms=0
    $result=0
    For $cc=0 to $sumlength
        If $aArray[$cc]>0 then
            $summation&=$aArray[$cc] & "+"
            $result+=$aArray[$cc]
            $terms+=1
        Endif
    Next
    $summation=StringTrimRight($summation,1) & " = " & $result & " (target = " & $target & ")" & @CRLF
    $summation&="Number of summation terms: " & $terms & @CR & "Temperature steps: " & $tempstep & @CR & @CR & "Press <Ok> to try again, <Cancel> to Quit"

    if Msgbox($MB_OKCANCEL,"Simulated Annealing Test Result",$summation)=$IDCANCEL then Exit

    ; shuffle entries a bit for variety
    For $cc=1 to $maxsize*10
        $index1=random($lockedlength+1,$sumlength,1)
        $index2=random($sumlength+1,$maxsize,1)
        $tmp=$aArray[$index1]
        $aArray[$index1]=$aArray[$index2]
        $aArray[$index2]=$tmp
    Next
WEnd

Exit


Func _AskOracle()

    If $costadjust<0 Then
        Return True
    Else        ; this is where all the magic happens!
        Return (random()<Exp(-($costadjust*$factor)/$temperat))
    Endif

EndFunc


Func _TrySwap()

    $index1=0       ; these vars are all Globals
    $index2=0
    $altcost=0

    $index1=random($lockedlength+1,$minsumlength,1)
    $index2=random($minsumlength+1,$maxsize,1)

    ; store current contents, in case we decide later that this was a bad idea
    $site1=$aArray[$index1]
    $site2=$aArray[$index2]

    ; swap contents for now
    $aArray[$index1]=$site2
    $aArray[$index2]=$site1

    ; compute the new sum (as either length or content has changed)
    $altcost=_Cost()

    ; performance difference between original and new state
    $costadjust=$altcost-$cost  ; $cost is already filled in previous pass

EndFunc


Func _Cost()

    Local $cc,$result=0
    For $cc=0 to $sumlength
        $result+=$aArray[$cc]
    Next
    Return (Abs($result-$target)*$weight_sum)

EndFunc


Func _ScreenOut()

    ConsoleWrite("Simulated Annealing. Initial total cost: " & $initcost & @CRLF)
    ConsoleWrite("Step: " & $tempstep & " of " & $tempsteps & "; Temperature: " & $temperat & @CRLF)
    ConsoleWrite("Executed Swaps: " & $nswap & "; Lowest Cost so far: " & $lowestcost & @CRLF)
    ConsoleWrite("Total Improvements: " & $absimp & "; Improvements this step: " & $nswapstep & @CRLF  & @CRLF)

EndFunc

Note also that this approach yields a single possible solution per run; if you wish to explore all possible permutations, you'll have to use brute force. Of course, you'd have to remap the final five digits to their original intermediate positions afterwards again as well.

All clear now?

 

Edited April 2, 2016 by RTFC

[Melba23]

ronnie32,

And here is my script from the first of the 2 threads to which RTFC linked adjusted to meet your requirements.

expandcollapse popup

HotKeySet("{ESC}", "_Exit")

; Set required number
Global $iRequired = 60

While 1

    Local $iMaxPossible = 0

    ; Create random 81 elements and calculate the max possible value
    Global $aFactors[12] = [2, 6, 2, 0, 0, 0, 0, 0, 1, 9, 6, 5]
    ConsoleWrite(@CRLF & "Random factors for this run:")
    $iSum = 0
    For $i = 3 To 7
        $aFactors[$i] = Random(1, 9, 1)
        $iSum += $aFactors[$i]
        ConsoleWrite(" " & $aFactors[$i])
        $iMaxPossible += $aFactors[$i]
    Next
    ConsoleWrite(@CRLF)
    If $iSum < 29 Then
        ConsoleWrite("! Total too small to reach target - max = " & 31 + $iSum & @CRLF)
        ; Try again
        ContinueLoop
    EndIf

    ; 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 11
        $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
            ConsoleWrite("+ Success:" & @CRLF & StringTrimRight($sFactors, 1) & "=" & $iRequired & @CRLF)
            Sleep(10)
            ; 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
                EndIf
            EndIf
        EndIf

    WEnd

WEnd

Func _Exit()
    Exit
EndFunc

The script looks at the additional factors generated and aborts instantly if their sum, together with that of the fixed values, is too small to total 60 - it then attempts to match 60 with the available factors and tries to adjust if necessary and possible (although I have not seen that happening in my tests so far). The output is coloured to reflect the result (Success - Adjusted - Failed). You get the results formatted as follows:

Random factors for this run: 6 3 6 9 9
+ Success:
9+9+9+6+6+6+6+5+3+1=60

Random factors for this run: 1 7 3 2 9
! Total too small to reach target - max = 53

Random factors for this run: 3 4 6 6 5
! Total too small to reach target - max = 55

Random factors for this run: 3 3 7 8 3
! Total too small to reach target - max = 55

Random factors for this run: 3 9 7 7 4
+ Success:
9+9+7+7+6+6+5+4+3+2+2=60

I hope that helps. And just out of interest, why are you doing this? What is the underlying requirement?

M23

[ronnie32]

As usual Melba, you're awesome, your explanations are great, I'm reading everything now and trying to understand, will report if I meet any problem or need help.

To answer your question, thats a school project, they've asked us to code in any language we'd like (my friends made fun of me when I said AutoIT, so I will show them how powerful it can be), a program that generates numbers based on a logic (kind of an easy algorithm), and compare them in our local database.

[Melba23]

ronnie32,

Quote

my friends made fun of me when I said AutoIT

Then I hope you really enjoy showing them what it can do. Best ask quickly if you have any questions as I am away for the next week.

M23

[ronnie32]

21 minutes ago, Melba23 said:

ronnie32,

Then I hope you really enjoy showing them what it can do. Best ask quickly if you have any questions as I am away for the next week.

M23

Thank you!

Here is my first question; what if I change the iRequired var to something lower, would I need to redefine the $aFactors array ?

[Melba23]

ronnie32,

No. The required total and the array are totally separate - the original script used an 81-element array and a random required number. However, you would need to change the check for the "random" elements being large enough - something like this would do:

If $iSum < $iRequired - 31 Then
    ConsoleWrite("! Total too small to reach target - max = " & 31 + $iSum & @CRLF)
    ; Try again
    ContinueLoop
EndIf

And if you wanted to change the "preset" values of the array then you would need to change each instance of "31" to match the new total.

M23

Edited April 2, 2016 by Melba23
Typo

[ronnie32]

<snip>

Pretty clear, so far. Thanks!

Edited April 2, 2016 by Melba23
Quote removed

[Melba23]

ronnie32,

When you reply, please use the "Reply to this topic" button at the top of the thread or the "Reply to this topic" editor at the bottom rather than the "Quote" button - I know what I wrote and it just pads the thread unnecessarily.

M23

 

[Melba23]

ronnie32,

Here is the script rewritten to do the calculations automatically:

expandcollapse popup

HotKeySet("{ESC}", "_Exit")

; Set required number
Global $iRequired = 60
; Create array of factors
Global $aFactors[12] = [2, 6, 2, 0, 0, 0, 0, 0, 1, 9, 6, 5]
$iFixedSum = 0
For $i = 0 To 11
    $iFixedSum += $aFactors[$i]
Next

While 1

    ConsoleWrite(@CRLF & "Random factors for this run:")
    $iRandomSum = 0
    For $i = 3 To 7
        $aFactors[$i] = Random(1, 9, 1)
        $iRandomSum += $aFactors[$i]
        ConsoleWrite(" " & $aFactors[$i])
    Next
    ConsoleWrite(@CRLF)
    If $iRandomSum < $iRequired - $iFixedSum Then
        ConsoleWrite("! Total too small to reach target - max = " & $iFixedSum + $iRandomSum & @CRLF)
        ; Try again
        ContinueLoop
    EndIf

    ; 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 11
        $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
            ConsoleWrite("+ Success:" & @CRLF & StringTrimRight($sFactors, 1) & "=" & $iRequired & @CRLF)
            Sleep(10)
            ; 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
                EndIf
            EndIf
        EndIf

    WEnd

WEnd

Func _Exit()
    Exit
EndFunc

Now you can change the required value and the array fixed values as you require.

M23

[ronnie32]

Calculation looks off with the last one or did I miss something:

 

Quote

Random factors for this run: 2 8 8 9 9
+ Success:
9+9+9+8+8+6+6+5=60

Global $aFactors[12] = [2, 6, 2, 0, 0, 0, 0, 0, 1, 9, 6, 5]

It doesn't take in consideration the numbers already preset, so I thought it was about the random factors for the current run but still: 2+6+2+2+8+8+9+9+1+9+6+5 does not equal to 60

Edited April 2, 2016 by ronnie32

[UEZ]

Here my version:

expandcollapse popup

HotKeySet("{ESC}", "_Exit")

; Set required number
Global $iRequired = 60
; Create array of factors
Global $aFactors[12] = [2, 6, 2, 0, 0, 0, 0, 0, 1, 9, 6, 5]

Global $i, $s, $iMax = 9, $iPos = 3, $iEnd = 7, $iSum = 0, $c = 0, $iFound = 0

Global $iRounds = ($iMax + 1)^($iEnd - $iPos + 1)

Do  ;brute force 3 - 7
    For $i = 0 To UBound($aFactors) - 1 ;create sum of current values
        $iSum += $aFactors[$i]
    Next
    If $iSum = $iRequired Then ;if sum is required number print it out
        For $i = 0 To UBound($aFactors) - 1
            $s &= $aFactors[$i] & " + "
        Next
        ConsoleWrite(StringTrimRight($s, 3) & " = " & $iRequired & @CRLF)
;~      ConsoleWrite(StringTrimRight($s, 3) & " = " & Execute(StringTrimRight($s, 3)) & @CRLF) ;cross check
        $s = ""
        $iFound += 1
    EndIf
    For $i = $iPos to $iEnd
        $aFactors[$i] = Int(Mod($c, ($iMax + 1) * 10^(-$iPos + $i)) / 10^(-$iPos + $i))
    Next
    $iSum = 0 ;reset sum
    $c += 1
Until $c = $iRounds

ConsoleWrite("Rounds: " & $c & @CRLF)
ConsoleWrite("Found: " & $iFound & @CRLF)

Func _Exit()
    ConsoleWrite("c:" & $c & @CRLF)
    Exit
EndFunc

I hope it works properly.

Edited April 2, 2016 by UEZ
Little correction

[Melba23]

ronnie32,

Found a free WiFi link, so I can reply for the moment - but future responses might be a bit few and far between.

That result looks fine to me:

Random factors for this run: 2 8 8 9 9

which means the array looks like this:

Global $aFactors[12] = [2, 6, 2, 2, 8, 8, 9, 9, 1, 9, 6, 5]
Used:                      ^        ^  ^  ^  ^     ^  ^  ^
9+9+9+8+8+6+6+5=60

Some of the presets and some of the random elements are used to make the total. The algorithm uses the minimum number of factors to create the total - does that pose a problem?

M23