# Bruteforcing algebra problems

## Recommended Posts

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 by boththose

```,-. .--. ________ .-. .-. ,---. ,-. .-. .-. .-.
|(| / /\ \ |\ /| |__ __||| | | || .-' | |/ / \ \_/ )/
(_) / /__\ \ |(\ / | )| | | `-' | | `-. | | / __ \ (_)
| | | __ | (_)\/ | (_) | | .-. | | .-' | | \ |__| ) (
| | | | |)| | \ / | | | | | |)| | `--. | |) \ | |
`-' |_| (_) | |\/| | `-' /( (_)/( __.' |((_)-' /(_|
'-' '-' (__) (__) (_) (__)```

##### Share on other sites

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

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

##### Share on other sites

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 by RTFC

My Contributions and Wrappers

Spoiler

##### Share on other sites

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

##### Share on other sites

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

##### Share on other sites

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 by spudw2k

Spoiler

Misc Code Snippets:
Projects: SubnetCalc
Cool Stuff:

##### Share on other sites

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

##### Share on other sites

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.

```#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

;~ _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)
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
Exit```

##### Share on other sites

@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 by RTFC

My Contributions and Wrappers

Spoiler

##### Share on other sites

@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!

##### Share on other sites

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.

My Contributions and Wrappers

Spoiler

##### Share on other sites

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 by boththose

```,-. .--. ________ .-. .-. ,---. ,-. .-. .-. .-.
|(| / /\ \ |\ /| |__ __||| | | || .-' | |/ / \ \_/ )/
(_) / /__\ \ |(\ / | )| | | `-' | | `-. | | / __ \ (_)
| | | __ | (_)\/ | (_) | | .-. | | .-' | | \ |__| ) (
| | | | |)| | \ / | | | | | |)| | `--. | |) \ | |
`-' |_| (_) | |\/| | `-' /( (_)/( __.' |((_)-' /(_|
'-' '-' (__) (__) (_) (__)```

##### Share on other sites

...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....

##### Share on other sites
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

```;~ ;;;;---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 by boththose

```,-. .--. ________ .-. .-. ,---. ,-. .-. .-. .-.
|(| / /\ \ |\ /| |__ __||| | | || .-' | |/ / \ \_/ )/
(_) / /__\ \ |(\ / | )| | | `-' | | `-. | | / __ \ (_)
| | | __ | (_)\/ | (_) | | .-. | | .-' | | \ |__| ) (
| | | | |)| | \ / | | | | | |)| | `--. | |) \ | |
`-' |_| (_) | |\/| | `-' /( (_)/( __.' |((_)-' /(_|
'-' '-' (__) (__) (_) (__)```

##### Share on other sites

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 & _
@TAB & "a + b + c = " & (\$x + \$y + \$z) / 2)```

##### Share on other sites

@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 by RTFC

My Contributions and Wrappers

Spoiler

## Create an account

Register a new account

• ### Recently Browsing   0 members

×

• Wiki

• Back

• #### Beta

• Git
• FAQ
• Our Picks
×
• Create New...