Bruteforcing algebra problems

[iamtheky]

pretty self explanatory, someone posted this problem to see if folks could still actually solve it,  "If a + b = 100 and b + c = 200 and c + a =240, what is a + b + c?" I wanted to see if i could script it.  If you have a better way to bruteforce it (like maybe one with decimals), or a way to actually solve them in script I would be interested.

;~ $a + $b = $x
;~ $b + $c = $y
;~ $c  + $a = $z

$x=100
$y=200
$z=240

for $a = 1 to $z
    for $b = 1 to $y
        for $c = 1 to $z

If $a + $b = $x AND $b + $c = $y AND $c + $a = $z Then msgbox (0, '' , $a & " + " & $b & " + " & $c & " = " & $a+$b+$c)

        Next
    Next
Next

Edited March 5, 2015 by boththose

[jchd]

You might want to try the diophantine equation solver in regexp examplified in >this post. Limit yourself to small coefficients, please!

[RTFC]

I'll show you brute force :

#include "Eigen4AutoIt.au3"

_Eigen_Startup()

$rows = 3
$variables = 3
Local $arrayA[$rows][$variables]=[ _
    [  1, 1, 0 ], _
    [  0, 1, 1 ], _
    [  1, 0, 1 ]]
$matA=_Eigen_CreateMatrix_FromArray($arrayA)
_ArrayDisplay($arrayA,"original data")

Local $arrayB[$rows][1]=[[100], [200], [240]]
$matB=_Eigen_CreateMatrix_FromArray($arrayB)
_ArrayDisplay($arrayB,"sum")

$matX=_Eigen_Multiply_AB(_Eigen_Inverse($matA),$matB)
_MatrixDisplay($matX,"result")

_Eigen_CloseDown()

Of course, this works only for exact solutions (otherwise use least-squares normal equations, for example, see my E4A tutorial Regression), and if you have more than 4 rows of data you'd better us a stable matrix decomposition to obtain the matrix inverse  (e.g., householderQR with pivoting, or JacobiSVD if you really want to go to town). Oh, and you do need my Eigen4AutoIt computing environment (see signature).

Edited March 6, 2015 by RTFC

[LarsJ]

boththose, What is your goal? These three equations seems to have a simple unique solution.

[AndyG]

three equations with three unknown... no need to bruteforce

c = (z+y-x)/2 = 340/2 = 170

b = y-c = 200-170 = 30 

a = x-b = 100-30 =70

less then one minute...without any computer

[spudw2k]

I was on the right track.

(100 + 200 + 240) / 2 = 270

Just wasn't sure how to derive a, b and c. 

Nice work AndyG

Edited March 6, 2015 by spudw2k

[Iczer]

hmm... maybe it would be good if some new UDF could introduce high performance functions for linear algebra, parallel computation, partial differential equations etc. using free/open source numerical analysis libraries from

http://en.wikipedia.org/wiki/List_of_numerical_libraries

[AndyG]

long time ago i wrote a little script to solve linear equation systems.

You can use the GUI to input your variables, or, like in RTFC´s post, an array.

expandcollapse popup

#include <GUIConstantsEx.au3>

;linearer gleichungslöser nach Gaußschem Eliminationsverfahren,
;~ #include <array.au3>
;~ $n = 3
;~ Dim $a[$n][$n] = [[1, 1, 0],[0, 1, 1],[1, 0, 1]] ;matrix
;~ Dim $b[$n] = [100, 200, 240]                       ;lösungen

;$n = 4
;Dim $a[$n][$n] = [[1, 3, -2, 1],[-2, 1, -4, -5],[1, -3, 1, 0],[-3, 4, -6, 2]] ;matrix
;Dim $b[$n] = [-7, -6, 6, -21]                 ;lösungen

;~ $s = _solve_linear_quad($a, $b)
;~ _ArrayDisplay($s)



Global $num_unknowns = Number(InputBox("Lösung Lineare Gleichungssysteme", "Anzahl Unbekannte?", 3))
Dim $coeff[$num_unknowns][$num_unknowns] ;matrix
Dim $values[$num_unknowns + 1][$num_unknowns + 2] ;
Dim $b[$num_unknowns]         ;lösungen
GUICreate("Enter Equations:", (48 * $num_unknowns) + 121, (26 * $num_unknowns) + 77)
For $n = 1 To $num_unknowns
    For $r = 1 To $num_unknowns
        $values[$n][$r] = GUICtrlCreateInput("", 48 * $r, 26 * $n, 25, 21)
        GUICtrlCreateLabel(StringMid("abcdefghijklmnopqrstuvwxyz", $r, 1), (48 * $r) + 26, (26 * $n) + 5, 10, 17)
        If $r < $num_unknowns Then
            GUICtrlCreateLabel("+", (48 * $r) + 37, (26 * $n) + 5, 10, 17)
        Else
            GUICtrlCreateLabel("=", (48 * $r) + 37, (26 * $n) + 5, 10, 17)
        EndIf
    Next
    $values[$n][$r] = GUICtrlCreateInput("", 48 * $r, 26 * $n, 25, 21)
Next
$solve_button = GUICtrlCreateButton("Lösen", (48 * $num_unknowns) + 38, (26 * $num_unknowns) + 36, 50, 25)
GUISetState()

While 1
    $msg = GUIGetMsg()
    Switch $msg
        Case $GUI_EVENT_CLOSE
            ExitLoop
        Case $solve_button
            For $n = 0 To $num_unknowns - 1
                For $r = 0 To $num_unknowns - 1
                    $coeff[$n][$r] = Number(GUICtrlRead($values[$n + 1][$r + 1]))
                Next
                $b[$n] = Number(GUICtrlRead($values[$n + 1][$num_unknowns + 1]))
            Next
;~             _arraydisplay($b)
;~             _arraydisplay($coeff)

            GUISetState(@SW_HIDE)
            $sols = _solve_linear_quad($coeff, $b)
            ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $sols = ' & $sols & @CRLF & '>Error code: ' & @error & @CRLF) ;### Debug Console

            $solutWin = GUICreate("Lösungen:", 280, (21 * UBound($sols)) + 42)
            For $n = 0 To UBound($sols) - 1
                GUICtrlCreateLabel(StringMid("abcdefghijklmnopqrstuvwxyz", $n + 1, 1) & " = " & Round($sols[$n], 3) & "   (Max. 3 Nachkommastellen)", 30, 21 * ($n + 1), 200, 20)
            Next
            GUISetState(@SW_SHOW, $solutWin)
    EndSwitch
WEnd




Func _solve_linear_quad($a, $b) ;matrix,lösung  Gaußsches Eliminationsverfahren, löst  x gleichungen mit x unbekannten
    ;by Andy  www.autoit.de
    Local $n, $t
    Dim $Y[UBound($b)]        ;ergebnisse
    $n = UBound($a) - 1       ;anzahl der zeilen/spalten
    ;falls erforderlich, zeilen und spalten tauschen
    If $a[0][0] = 0 Then      ;wenn erster koeffizient = 0, dann kann das system nicht starten => spalten tauschen ggf zeilen tauschen
        For $k = 0 To $n      ;jede zeile
            For $j = 0 To $n  ;alle spalten in dieser Zeile testen
                If $a[$k][$j] <> 0 Then
                    For $m = 0 To $n ;treffer, die erste spalte mit der j. tauschen
                        $t = $a[$m][$j] ;sichern
                        $a[$m][$j] = $a[$m][0] ;mit erster spalte tauschen
                        $a[$m][0] = $t
                    Next
                    For $j = 0 To $n ;zeilen tauschen
                        $t = $a[0][$j] ;sichern
                        $a[0][$j] = $a[$k][$j] ;mit erster spalte tauschen
                        $a[$k][$j] = $t
                    Next
                    $t = $b[0] ;ergebnisse auch tauschen
                    $b[0] = $b[$k]
                    $b[$k] = $t
                    ExitLoop 2
                EndIf
            Next
        Next
    EndIf

    If $a[0][0] = 0 Then Return SetError(1, 0, 1)

    ;endlich rechnen :)
    For $I = 0 To $n          ;alle zeilen
        If $a[$I][$I] <> 0 Then
            ;erstes element auf 1 bringen indem man gesamte zeile durch erstes Element teilt
            For $k = $I To $n
                $t = $a[$k][$I] ;erstes element merken
                If $t <> 0 Then ;nur, wenn das erste element ungleich null ist...
                    For $j = $I To $n
                        $a[$k][$j] /= $t ;alle zeilenmitglieder durch erstes element teilen
                    Next
                    ;b durch i teilen
                    $b[$k] /= $t ;ergebnis natürlich auch
                EndIf
            Next
            ;  _ArrayDisplay($a, "oben " & $I)
            ;zeile i von allen weiteren zeilen subtrahieren, erstes element wird zu 0
            For $k = $I + 1 To $n
                If $a[$k][$I] <> 0 Then ;wenn null, dann überspringen
                    For $j = $I To $n
                        $a[$k][$j] -= $a[$I][$j] ;die i.zeile von der aktuellen zeile subtrahieren
                    Next
                    $b[$k] -= $b[$I] ;ergebnisse natürlich auch
                EndIf
            Next
            ;   _ArrayDisplay($a, "unten " & $I)
        Else                  ;null in aktueller spalte
            ;zeilen tauschen
            ;    msgbox(0,$i,"null gefunden")
            For $k = $I + 1 To $n
                If $a[$k][$I] <> 0 Then ;zeile tauschen
                    For $j = $I To $n ;zeilen tauschen
                        $t = $a[$I][$j] ;sichern
                        $a[$I][$j] = $a[$k][$j] ;mit erster spalte tauschen
                        $a[$k][$j] = $t
                    Next
                    $t = $b[$I] ;ergebnisse auch tauschen
                    $b[$I] = $b[$k]
                    $b[$k] = $t
                EndIf
                ;erstes element auf 1 bringen indem man gesamte zeile durch erstes Element teilt
                For $k = $I To $n
                    $t = $a[$k][$I] ;erstes element merken
                    If $t <> 0 Then ;nur, wenn das erste element ungleich null ist...
                        For $j = $I To $n
                            $a[$k][$j] /= $t ;alle zeilenmitglieder durch erstes element teilen
                        Next
                        ;b durch i teilen
                        $b[$k] /= $t ;ergebnis natürlich auch
                    EndIf
                Next
                ; _ArrayDisplay($a, "oben1 " & $I)
                ;zeile i von allen weiteren zeilen subtrahieren, erstes element wird zu 0
                For $k = $I + 1 To $n
                    If $a[$k][$I] <> 0 Then ;wenn null, dann überspringen
                        For $j = $I To $n
                            $a[$k][$j] -= $a[$I][$j] ;die i.zeile von der aktuellen zeile subtrahieren
                        Next
                        $b[$k] -= $b[$I] ;ergebnisse natürlich auch
                    EndIf
                Next
                ;_ArrayDisplay($a, "unten1 " & $I)

            Next
        EndIf
    Next

    ;alle parameter bestimmen durch rückwärtseinsetzen

    $Y[$n] = $b[$n]           ;letzter ist bereits bekannt
    For $I = $n - 1 To 0 Step -1
        For $j = $n To $I + 1 Step -1
            $b[$I] -= $a[$I][$j] * $Y[$j]
        Next
        $Y[$I] = $b[$I]
    Next
    Return $Y
EndFunc                       ;==>_solve_linear_quad
Exit

[RTFC]

@Iczer: on that very page you link to, Eigen is listed (under C++), for which I already wrote a pretty comprehensive port for AutoIt, with over 350 functions, including almost all linear algebra functionality (except support for sparse matrices). Worth checking out if you're into linear algebra and AutoIt...

@AndyG: that's a nice Gauss-Jordan solver   (but beware of infinitesimals...)

Edited March 7, 2015 by RTFC

[AndyG]

@AndyG: that's a nice Gauss-Jordan solver   (but beware of infinitesimals...)

hehe, easy problems require easy solutions 

I know the restrictions of these "easy solutions" and you too! (i like your Eigen-udf  )

But I am sure, those "bruteforcers" are not able to understand what we are talking about....feed their "algorythm" with some suitable numbers and they will find....nothing!

[RTFC]

@AndyG: I hear you, mate, and thanks. (Feel a bit bad about hijacking this thread though.)

For all bruteforcers out there, as AndyG and I already hinted at, the OP's example has a serious flaw in that it'll only yield a solution if an exact solution exists based on integer inputs. in real life (other than in math test questions), this is hardly ever the case. The crucial question you need to answer first is: what kind of system are we dealing with here, more specifically, do we have more observations (rows) than unknowns (variables), i.e., an overdetermined system (use least squares or some other norm; all is fine), the opposite case (an underdetermined system; you'll need to add damping to get rid of you null space, and even then you're still on shaky ground), or an equal number (in which case a solution exists only if the square kernel ($matA in my earlier example) can be inverted (i.e. its determinant is non-zero), otherwise it's insoluble.

Bruteforcing is fine, and for some problems (e.g., simulated annealing) it's the only viable way to get any solution (even though it may not be the/an optimal one), but you'll need to wield more sophisticated (matrix) tools than simply cycling through all possible permutations of integer inputs.

[iamtheky]

When yall are done mathturbating....

The point was that bruteforcing worked, and the script is easily shat.  And because Im not finding much info on these thoughts Im going to create some:

1) to figure out which problems can be (or have a greater potential for being) bruteforced before looping, which is where the proper solution helps (thanks Andy), my first thought for this type, as i only want whole numbers, is checking $z prior to continuing.

2) Figure out the best way to return all solutions from a problem that does not have enough information.

3) stay as generic as possible, a slow as balls bruteforce script that would handle multiple types of problems would be the imaginary unicorn. 

And limited applications are not flaws, they are limited applications.  Thinking my first exercise will be, if from the OP, $x, $y or $z, at random will also not be given, return all solutions that are all whole numbers (and reasonable, bonus points if you determine the upper limit of $x, $y, or $z given only two of them):

;~ $a + $b = $x

;~ $b + $c = $y

;~ $c  + $a = $z

$x=100

$y=200

$z=240

Edited March 7, 2015 by boththose

[AndyG]

...And limited applications are not flaws, ...

Nobody said that!

But this is a Forum about programming. For me, the sense of a Forum is to ask a question, show what i have already done and wait for other people´s ideas to evolve my skill.

Three FOR/TO loops and a line of IF´s are not a challenge...

 

..... or a way to actually solve them in script I would be interested....

you asked, you got answers 

[iamtheky]

the OP's example has a serious flaw  

 

sorry, i dont know how else to interpret that.    It was admittedly not clearly defined, but also not a flawed example, it returns the same correct answer for the given input.

And I explained the intent for your answer, as that was also not clearly defined.  It was an intentionally simple example, designed to not be challenging at all, to express the overall concept of bruteforcing a simple algebra problem.  Not everyone here speaks english, but they all speak script.

And here is my current effort towards all possible solutions

expandcollapse popup

;~ ;;;;---All solutions given two of three

;~ ;Given-----------
;~ (a)alf + (b)bird = 10
;~ (b)bird + (c)cat = 12
;~ (c)cat  +(a)alf = ?

$x = 10
$y = 12

;--------------

$sAnswer="Possible Solutions:" & @CRLF & @CRLF

for $a = 1 to ($x <= $y) ? ($x) : ($y)
    for $b = 1 to ($x <= $y) ? ($x) : ($y)
        for $c = 1 to $y
            for $z = 2 to $x + $y

If $a + $b = $x AND $b + $c = $y AND $c + $a = $z Then $sAnswer &=  "alf = " & $a & " bird = " & $b & "  cat = " & $c & @CRLF

            Next
        Next
    Next
Next

($sAnswer = "Possible Solutions:" & @CRLF & @CRLF) ? (msgbox(0, '' , "no whole answers")) : (msgbox(0, '' , $sAnswer))


;;;;---All solutions given only one answer


;Given-----------
;~ (a)alf + (b)bird = ?
;~ (b)bird + (c)cat = 12
;~ (c)cat  +(a)alf = ?

$y = 12

;--------------

$sAnswer="Possible Solutions:" & @CRLF & @CRLF

for $a = 1 to $y
    for $b = 1 to $y
        for $c = 1 to $y
            for $z = 2 to $y
                for $x = 2 to $y

If $a + $b = $x AND $b + $c = $y AND $c + $a = $z Then $sAnswer &=  "alf = " & $a & " bird = " & $b & "  cat = " & $c & @CRLF

                Next
            Next
        Next
    Next
Next

($sAnswer = "Possible Solutions:" & @CRLF & @CRLF) ? (msgbox(0, '' , "no whole answers")) : (msgbox(0, '' , $sAnswer))

Edited March 8, 2015 by boththose

[Malkey]

In post #1, deriving individual values for a, b, and c was not asked for, and, is not necessary.
What is a + b + c?

a + b = 100           equation (1)
b + c = 200           equation (2)
c + a = 240           equation (3)

Add the 3 equations together, we get

a + b + b + c + c + a = 100 + 200 + 240  [Equation (4) = equations (1) + (2) + (3)]

2a + 2b + 2c  = 540          [Simplify equation (4)]

2(a + b + c) = 540           [Further simplify equation (4)]

a + b + c = 540 / 2          [Further simplify equation (4)]

a + b + c = 270              [Simplified equation (4)]

This better explains the track spudw2k was on in post #6.

;~ a + b = $x
;~ b + c = $y
;~ c + a = $z

$x = 100
$y = 200
$z = 240

MsgBox(0, "Results", "Given:-" & @CRLF & _
        @TAB & "a + b = " & $x & @CRLF & _
        @TAB & "b + c = " & $y & @CRLF & _
        @TAB & "c + a = " & $z & @CRLF & @CRLF & _
        "Answer:-" & @CRLF & _
        @TAB & "a + b + c = " & ($x + $y + $z) / 2)

[RTFC]

@boththose: maybe I worded my previous response carelessly, I suppose I should have said serious "limitation" rather than "flaw". No offence was intended.

But it's not about criticising a toy example script for being just a toy example; it's about how the problem is approached (and adding non-integer steps to your loops isn't going to fix this). Your basic assumption is wrong, in that bruteforcing as in your example often does not work. Please let me explain:

My first point in post #11 was that you first need to figure out whether or not your problem has a solution at all, before you start churning away, burning precious CPU oil. And in your example case with exactly as many observations as unknowns, a tiny bit of arithmetic (testing whether the kernel's determinant is zero or not) could tell you this immediately.

My second point was that even well-posed linear algebra problems do not necessarily have a  unique solution, and may need additional information to be solved. They may require a user-defined additional regularisation to converge (if underdetermined),  or (if overdetermined) a user-defined norm that reflects the (expected) error distribution of your observations around the true values of your coefficients (for example, least-squares assumes a Gaussian error distribution of your data). For any realistically-sized problem, "bruteforcing" would be applied in matrix decomposition and/or inversion of large datasets.

But if you insist on just trial and error with coefficients you supply yourself (rather than your CPU/GPU computing these coefficients for you), then it would still be more efficient to apply, some iterative adjusted-step scheme that homes in on some optimum that is closest to your intitial guess, according to some criterion you define. Check out simulated annealing; (see link in my signature) that would produce a solution using a fraction of the effort of your nested loops, and all you need to do is define a cost function (which is trivial in this case). I'd recommend that approach if you don't want to use matrix algebra.

Edited April 1, 2016 by RTFC