Solved: Math Problem Puzzle(Brain teaser)

[Len Piwowar]

My son returned home with some math problems, I helped him complete most and explained how to use reason to get the answers. I then commented that Excel could be used to automate the process of answering the problems. After reviewing and trying to setup a sheet I must admit I have gotten stumped any Idea's on how to proceed? The problem is:

8 13 14 23 6 = 14

The object is to figure out using +-/* to the left of the = sign to have the numbers equal 14. The numbers can be placed in any order.

example:
7 12 4 21 11 = 14
21+12=33/11=3+7=10+4 =14

His assignment has been completed and turned, I just thought this would stimulate some brain cells!
:doh:

[makako]

Option Base 1
Sub SearchCharacters()
Dim Vars As Range, Answ As Double, RangeA As Range
Dim Char() As Integer, X As Integer, EString As String
Set Vars = Application.InputBox("Select the Variables range", Type:=8)
Answ = InputBox("Answer:")
Set RangeA = Application.InputBox("Select the location for answers", Type:=8)
ReDim Char(Vars.Cells.Count - 1)
For X = 1 To Vars.Cells.Count - 1
Char(X) = 1
Next
While Char(1) < 5
EString = ""
For X = 1 To Vars.Cells.Count - 1
Select Case Char(X)
Case 1:
EString = EString & Vars.Cells(X).Value & "+"
Case 2:
EString = EString & Vars.Cells(X).Value & "-"
Case 3:
EString = EString & Vars.Cells(X).Value & "*"
Case 4:
EString = EString & Vars.Cells(X).Value & "/"
End Select
Next
EString = EString & Vars.Cells(Vars.Cells.Count).Value
If Evaluate("=" & EString) = Answ Then
RangeA = EString
RangeA.Offset(, 1).Value = Evaluate("=" & EString)
MsgBox EString
Exit Sub
End If
RangeA = EString
RangeA.Offset(, 1).Value = Evaluate("=" & EString)
Set RangeA = RangeA.Offset(1)
For X = Vars.Cells.Count - 1 To 1 Step -1
If Char(X) = 4 And X <> 1 Then
Char(X) = 1
Else
Char(X) = Char(X) + 1
Exit For
End If
Next
Wend
MsgBox "No possible combination"
End Sub

first you have to select a line with one number per cell, then enter the answer numerically (not range) and after that select a range for answers.
hope it works

[mdmackillop]

Hi Makako,
If you select your text and click the VBA button it will format as above, making it more readable.
It also highlights here that you have used colons in your select statement, turning these lines into Labels, which I suspect will make your code fail.

[makako]

thaks for the tip.
did you tried it? it worked for me

[mdmackillop]

Two problems I see with your solution
Numbers can be in any order
Effect of bracketing in the calculation, as per the example.

[Aussiebear]

I have found in the past it is easier if you work backwards from the solution, but hey I'm an Aussie so we're a bit laid back compared to the rest of you good people.

[stanl]

I put the problem before another scripting forum and one reply was



To solve the problem, I'd just put all the numbers and operators into an array and then do combinatorics to test all possibilities. Should be relatively straighforward once you have the "generate all possibilities" algorithm in hand.

which I replied seemed to reinforce Fudd's 2nd Law of Univeral Ditcum:

Reasoning - Code = BS

[Fudd's First Law, of course, was "If you push something hard enough it will fall over"... just checking if there are any Firesign Fans here]

were but the Holy Grail buried in my back yard:banghead: Stan

[mdmackillop]

Should be relatively straighforward once you have the "generate all possibilities" algorithm in hand.
Is that the one that starts "Let there be light..."?:

[Aaron Blood]

Man... :banghead:

Thought I had that one beat cold.

Ran my logic on the first example and found 20 solutions:
11 * 7 - 12 * 21 / 4 = 14
11 * 7 - 12 / 4 * 21 = 14
11 * 7 - 21 * 12 / 4 = 14
11 * 7 - 21 / 4 * 12 = 14
21 - 11 - 12 / 4 + 7 = 14
21 - 11 + 7 - 12 / 4 = 14
21 - 12 / 4 - 11 + 7 = 14
21 - 12 / 4 + 7 - 11 = 14
21 + 7 - 11 - 12 / 4 = 14
21 + 7 - 12 / 4 - 11 = 14
7 - 11 - 12 / 4 + 21 = 14
7 - 11 + 21 - 12 / 4 = 14
7 - 12 / 4 - 11 + 21 = 14
7 - 12 / 4 + 21 - 11 = 14
7 * 11 - 12 * 21 / 4 = 14
7 * 11 - 12 / 4 * 21 = 14
7 * 11 - 21 * 12 / 4 = 14
7 * 11 - 21 / 4 * 12 = 14
7 + 21 - 11 - 12 / 4 = 14
7 + 21 - 12 / 4 - 11 = 14

Notice I wanted to avoid adding anything more than a single math op between each value. I thought allowing the = operator was cheating! 21+12=33/11=3+7=10+4 =14 That just didn't seem right to me...

Woohoo! :dance: It worked.


Then tried it on: 8 13 14 23 6 = 14
...and it couldn't find a solution.

Broke my heart. :boohoo

That was very naughty...

Obviously they should change the rules so my logic works!
...and just toss that horrid second example.

[Aussiebear]

and if you were only able to use an operator once only?

[stanl]

It may be a coin toss between reasoning and logic:dunno but is it safe to posit (for this specific problem)

Given 5 2-digit number that can be combined with +-/* to equal a positive integer, determine 1 or more of those calculations? ; which assume a solution is possible. Stan

[Aaron Blood]

and if you were only able to use an operator once only?

That was actually my first attempt...

Build a matrix based on 4! and 5! mathOp/number sequences.
4!x5! = 24x120 = 2880 possible formulas

...in which case, no solution for either:
7 12 4 21 11 = 14
8 13 14 23 6 = 14

So, I expanded the scope to...

Build a matrix based on 4^4 and 5! mathOp/Number sequences.
4^4x5! = 256x120 = 30720 possible formulas

That's when I got 20 answers for the first and no joy on the second.

The next logical step (I guess) might be to toss out standard order of operations and always process the math ops left to right. In which case I'd maybe try it again first with factorials for both and expand the scope again if it didn't work.

[Aaron Blood]

It may be a coin toss between reasoning and logic:dunno but is it safe to posit (for this specific problem)

Given 5 2-digit number that can be combined with +-/* to equal a positive integer, determine 1 or more of those calculations? ; which assume a solution is possible. Stan

...maybe if you toss out standard order of operations. Otherwise, no it's not a safe assumption. I may try again this afternoon if I have some free time. :think:

[stanl]

I'd love to see a code snippet to play around with...:bow: Stan

[stanl]

Hope I don't get in trouble here, but went with another scripting language (Winbatch; pretty much like VBA when dealing with COM). The resident guru, Marty used simple arrays and found the 20 matches Aaron found, but 34 matches when parentheses were used. I'm placing it here just as an FYI



;Winbatch 2006E - Math quiz computation
;Given
var = "7 12 4 21 11 = 14"
;arrray is 0-based, so create extra element to keep straight count
NumArray=ArrDimension(6)
For i = 1 To 5
NumArray[i]=Int(ItemExtract(i,var," ")) * 1.0
Next
result=ItemExtract(7,var," ")
OpArray=ArrDimension(5)
OpArray[1]="+"
OpArray[2]="-"
OpArray[3]="*"
OpArray[4]="/"
Answers=""

goodcount=0
compcount=0
maxcompcount=5*4*3*2*1 *4*4*4*4
Boxopen(0,"Max Iterations: ":maxcompcount) ;dialog display
For a1=1 to 5
numA=NumArray[a1]
For a2=1 to 5
If a2==a1 then continue
NumB=NumArray[a2]
For a3=1 to 5
If a3==a1 then continue
If a3==a2 then continue
NumC=NumArray[a3]
For a4=1 to 5
If a4==a1 then continue
If a4==a2 then continue
If a4==a3 then continue
NumD=NumArray[a4]
For a5=1 to 5
If a5==a1 then continue
If a5==a2 then continue
If a5==a3 then continue
If a5==a4 then continue
NumE=NumArray[a5]
For b1=1 to 4
OPA=OpArray[b1]
For b2=1 to 4
OPB=Oparray[b2]
For b3=1 to 4
OPC=OpArray[b3]
For b4=1 to 4
OPD=OpArray[b4]
; parentheses use to force left to right evaluation instead of
; standard evaluation order [will find 34 results]
line= "(((%numa% %opa% %numb%) %opb% %numc%) %opc% %numd%) %opd% %nume%"
;no parenthese uses standard evaluation order [will find 20 results]
;line= "%numa% %opa% %numb% %opb% %numc% %opc% %numd% %opd% %nume%"
r= %line%
If r==result
If answers=="" then answers=line
else answers=answers:@tab:line
goodcount=goodcount+1
Endif
compcount=compcount+1
BoxTitle("Good: ":goodcount:" Iterations: ":compcount)
Next
Next
Next
Next
Next
Next
Next
Next
Next
AskItemList("Good Count: ":goodcount,answers,@tab,@unsorted,@single)
Exit
;/////////////////////////////////////////////////////////////////////


Stan

[Aaron Blood]

Yeah I think the fact that you found 34 vs. the 20 (doesn't surprise me) leads me back to the 4!x5! matrix to try again...

I took a rather crude approach. Just used nested loops to create the combinations/permutations and then converted those combinations to cell formulas and literally had all the cell formulas in a matrix. Although they were all unique formulas that couldn't be copy/pasted around... but no I didn't enter all 30k of them by hand.

[stanl]

Yeah I think the fact that you found 34 vs. the 20

Actually it found both, depending on whether or not parentheses played a part in the calculations. Here are the 34, subject to scrutiny:think: Stan

(((12 + 4) - 11) * 7) - 21
(((12 + 21) / 11) + 7) + 4
(((12 + 21) / 11) + 4) + 7
(((12 - 11) + 4) * 7) - 21
(((4 - 7) + 11) / 12) * 21
(((4 - 7) + 11) * 21) / 12
(((4 / 12) + 7) * 21) / 11
(((4 / 12) + 7) / 11) * 21
(((4 - 12) + 21) - 11) * 7
(((4 + 12) - 11) * 7) - 21
(((4 - 12) - 11) + 21) * 7
(((4 + 21) - 12) - 11) * 7
(((4 + 21) - 11) / 7) + 12
(((4 + 21) - 11) - 12) * 7
(((4 + 11) - 7) / 12) * 21
(((4 + 11) - 7) * 21) / 12
(((4 - 11) + 12) * 7) - 21
(((4 - 11) - 12) + 21) * 7
(((4 - 11) + 21) / 7) + 12
(((4 - 11) + 21) - 12) * 7
(((21 - 12) + 4) - 11) * 7
(((21 + 12) / 11) + 7) + 4
(((21 + 12) / 11) + 4) + 7
(((21 - 12) - 11) + 4) * 7
(((21 + 4) - 12) - 11) * 7
(((21 + 4) - 11) / 7) + 12
(((21 + 4) - 11) - 12) * 7
(((21 - 11) - 12) + 4) * 7
(((21 - 11) + 4) / 7) + 12
(((21 - 11) + 4) - 12) * 7
(((11 - 7) + 4) / 12) * 21
(((11 - 7) + 4) * 21) / 12
(((11 + 4) - 7) / 12) * 21
(((11 + 4) - 7) * 21) / 12

[stanl]

Then tried it on: 8 13 14 23 6 = 14
...and it couldn't find a solution.


I tried that combination with my code and found no solution either. So, is the issue expanding the possibilities or certifying a non-solution? Stan

[Aaron Blood]

Well, I'm glad you did it... I didn't want to spend too much more of my time on it.

I'm inclined to say that if you can't find a solution for a 4^4 x 5! matrix with the left-to-right paren logic in place that it must be proof that a solution does not exist.

It's usually at this point (once I've gone out on the limb and said it can't be done) that someone posts the equation that adds up to 14... :shifty:

[makako]

Well, Im getting there. I Still have some problems with the Function that creates the next permutation. I like this solution cause it doesnt restrict the number of variables. I also found and interesting game with the parenthesis but I would gladly receive some ideas on how to work the function or to shape up the sub.


Option Base 1
Type MathArray
MType As Integer '1 for "(", 2 for ")", 3 for "X", 4 for "Operator"
MNum As Integer
MMax As Integer
End Type
Public MOrder() As Integer
Sub SearchCharacters()
Dim Vars As Range, Answ As Double, RangeA As Range, TempAns As Double, OpenPa As Integer, ClosingPa As Integer
Dim X As Long, Y As Long, Z As Integer, EString As String, CHString As String
Dim MArray() As MathArray
Set Vars = Application.InputBox("Select the Variables range", Type:=8)
Answ = InputBox("Answer:")
Set RangeA = Application.InputBox("Select the location for answers", Type:=8)
ReDim MArray((Vars.Cells.Count * Vars.Cells.Count) + Vars.Cells.Count - 1)
Z = 1
ReDim MOrder(Vars.Cells.Count)
For X = Vars.Cells.Count To 1 Step -1
For Y = 1 To Vars.Cells.Count
If X = Y Then
MArray(Z).MType = 3
MArray(Z).MNum = 1
MArray(Z).MMax = Vars.Cells.Count
Z = Z + 1
ElseIf X > Y Then
MArray(Z).MType = 1
MArray(Z).MNum = 1
MArray(Z).MMax = 2
Z = Z + 1
ElseIf X < Y Then
MArray(Z).MType = 2
MArray(Z).MNum = 1
MArray(Z).MMax = 2
Z = Z + 1
End If
Next
If X <> 1 Then
MArray(Z).MType = 4
MArray(Z).MNum = 1
MArray(Z).MMax = 4
Z = Z + 1
End If
Next

While MArray(1).MNum < 3
EString = ""
For X = 1 To UBound(MArray)
With MArray(X)
Select Case .MType
Case 1:
If .MNum = 1 Then
EString = EString & "("
Else
EString = EString & " "
End If
Case 2:
If .MNum = 1 Then
EString = EString & ")"
Else
EString = EString & " "
End If
Case 3:
EString = EString & "X"
Case 4:
Select Case .MNum
Case 1:
EString = EString & "+"
Case 2:
EString = EString & "-"
Case 3:
EString = EString & "*"
Case 4:
EString = EString & "/"
End Select
End Select
End With
Next

For X = 1 To UBound(MOrder)
MOrder(X) = X
Next
For Y = 2 To Application.WorksheetFunction.Permut(Vars.Cells.Count, Vars.Cells.Count) + 1
CHString = EString
For X = 1 To UBound(MOrder) 'Ini Position
CHString = Left(CHString, (InStr(CHString, "X") - 1)) & _
Vars.Cells(MOrder(X)) & Right(CHString, Len(CHString) - _
InStr(CHString, "X"))
Next
On Error Resume Next
TempAns = Evaluate("=" & CHString)
If Err.Number = 0 Then
If TempAns = Answ Then
MsgBox CHString & "=" & Answ
Exit Sub
End If
RangeA.Value = CHString
RangeA.Offset(, 1).Value = TempAns
Set RangeA = RangeA.Offset(1)
End If
Err.Clear
On Error GoTo 0
'Next Iter
X = Y
NextIter X, 1
Next
GotoNextPar:
For X = UBound(MArray) To 1 Step -1
With MArray(X)
If .MType = 3 Then
ElseIf .MNum >= .MMax And X <> 1 Then
.MNum = 1
Else
.MNum = .MNum + 1
Exit For
End If
End With
Next
OpenPa = 0
ClosingPa = 0
For X = 1 To UBound(MArray)
With MArray(X)
If .MType = 1 And .MNum = 1 Then
OpenPa = OpenPa + 1
ElseIf .MType = 2 And .MNum = 1 Then
ClosingPa = ClosingPa + 1
End If
End With
Next
If ClosingPa <> OpenPa Then GoTo GotoNextPar:
Wend
MsgBox "No possible combination"
End Sub
Function NextIter(X As Long, Iter As Integer)
Dim Group As Integer, Control As Boolean, Y As Long
If Iter > UBound(MOrder) Then Exit Function
Y = UBound(MOrder) + 1 - Iter
Group = Application.WorksheetFunction.Permut(Y, Y) / Y
MOrder(Iter) = Int((X - 1) / Group) + 1
Control = False
While Control = False
For Y = 1 To UBound(MOrder)
If MOrder(Iter) = MOrder(Y) And Y <> Iter Then
lvcontrol = True
MOrder(Iter) = MOrder(Iter) + 1
If MOrder(Iter) > UBound(MOrder) Then
MOrder(Iter) = 1
End If
Exit For
End If
Next
Control = Not (Control)
Wend
X = X Mod Group
If X = 0 Then X = Group
NextIter X, Iter + 1
End Function

[Aussiebear]

Sorry guys, way toooooooo deep for me. I was struggling with the initial post then Aaron posted and I was left with help help I'm drowning here, then Stanl made the tide come in, and Makako has sent it interplanetary.....

What happened to a simple post?

[mdmackillop]

Hi Ted,
I know exactly what you mean. This is my closer to my level.
http://vbaexpress.com/forum/showthread.php?t=10361
Regards
MD

[stanl]

The question: is it difficult or time consuming? I think the consesnus is that you need to evaluate 30k possibilities regardless. One way is with the assistance of Excel cells to fit a matrix, the other is to find an algorithm which could then be written as a Function() to either return "Cannot Be Solved", a list of regular math solutions, or a list of solutions w/parentheses.

I've looked at the algorithm I posted for 3 days... irritated a bit that it is not more elegant:bug: , but it appears to work so it is now time consuming not difficult. I will however, convert it to a VBA function unless that is also time consuming. Stan

[makako]

Option Base 1
Type MathArray
MType As Integer '1 for "(", 2 for ")", 3 for "X", 4 for "Operator"
MNum As Integer
MMax As Integer
End Type
Public MOrder() As Integer
Dim PossibleArray() As Integer
Sub SearchCharacters()
Dim Vars As Range, Answ As Double, RangeA As Range, TempAns As Double, OpenPa As Integer, ClosingPa As Integer
Dim X As Long, Y As Long, Z As Integer, EString As String, CHString As String
Dim MArray() As MathArray
Set Vars = Application.InputBox("Select the Variables range", Type:=8)
Answ = InputBox("Answer:")
'Set RangeA = Application.InputBox("Select the location for answers", Type:=8)
ReDim MArray((Vars.Cells.Count * Vars.Cells.Count) + Vars.Cells.Count - 1)
Z = 1
ReDim MOrder(Vars.Cells.Count)
For X = Vars.Cells.Count To 1 Step -1
For Y = 1 To Vars.Cells.Count
If X = Y Then
MArray(Z).MType = 3
MArray(Z).MNum = 1
MArray(Z).MMax = Vars.Cells.Count
Z = Z + 1
ElseIf X > Y Then
MArray(Z).MType = 1
MArray(Z).MNum = 1
MArray(Z).MMax = 2
Z = Z + 1
ElseIf X < Y Then
MArray(Z).MType = 2
MArray(Z).MNum = 1
MArray(Z).MMax = 2
Z = Z + 1
End If
Next
If X <> 1 Then
MArray(Z).MType = 4
MArray(Z).MNum = 1
MArray(Z).MMax = 4
Z = Z + 1
End If
Next

While MArray(1).MNum < 3
EString = ""
For X = 1 To UBound(MArray)
With MArray(X)
Select Case .MType
Case 1:
If .MNum = 1 Then
EString = EString & "("
Else
EString = EString & " "
End If
Case 2:
If .MNum = 1 Then
EString = EString & ")"
Else
EString = EString & " "
End If
Case 3:
EString = EString & "X"
Case 4:
Select Case .MNum
Case 1:
EString = EString & "+"
Case 2:
EString = EString & "-"
Case 3:
EString = EString & "*"
Case 4:
EString = EString & "/"
End Select
End Select
End With
Next

For X = 1 To UBound(MOrder)
MOrder(X) = X
Next
For Y = 1 To Application.WorksheetFunction.Permut(Vars.Cells.Count, Vars.Cells.Count)
CHString = EString
For X = 1 To UBound(MOrder) 'Ini Position
CHString = Left(CHString, (InStr(CHString, "X") - 1)) & _
Vars.Cells(MOrder(X)) & Right(CHString, Len(CHString) - _
InStr(CHString, "X"))
Next
On Error Resume Next
TempAns = Evaluate("=" & CHString)
If Err.Number = 0 Then
If TempAns = Answ Then
MsgBox CHString & "=" & Answ
Exit Sub
End If
'RangeA.Value = CHString
'RangeA.Offset(, 1).Value = TempAns
'Set RangeA = RangeA.Offset(1)
End If
Err.Clear
On Error GoTo 0
'Next Iter
For X = 1 To UBound(MOrder)
MOrder(X) = 0
Next
If Y = Application.WorksheetFunction.Permut(Vars.Cells.Count, Vars.Cells.Count) Then Exit For
X = Y + 1
NextIter X, 1
Next
GotoNextPar:
For X = UBound(MArray) To 1 Step -1
With MArray(X)
If .MType = 3 Then
ElseIf .MNum >= .MMax And X <> 1 Then
.MNum = 1
Else
.MNum = .MNum + 1
Exit For
End If
End With
Next
OpenPa = 0
ClosingPa = 0
For X = 1 To UBound(MArray)
With MArray(X)
If .MType = 1 And .MNum = 1 Then
OpenPa = OpenPa + 1
ElseIf .MType = 2 And .MNum = 1 Then
ClosingPa = ClosingPa + 1
End If
End With
Next
If ClosingPa <> OpenPa Then GoTo GotoNextPar:
Wend
MsgBox "No possible combination"
End Sub
Function NextIter(X As Long, Iter As Integer)
Dim Group As Integer, Y As Long, I As Integer, J As Integer
If Iter > UBound(MOrder) Then Exit Function
If Iter = 1 Then
ReDim PossibleArray(UBound(MOrder))
For I = 1 To UBound(MOrder)
PossibleArray(I) = I
Next
End If
Y = UBound(MOrder) + 1 - Iter
Group = Application.WorksheetFunction.Permut(Y, Y) / Y
MOrder(Iter) = PossibleArray(Int((X - 1) / Group) + 1)
For I = 1 To UBound(PossibleArray)
If PossibleArray(I) = MOrder(Iter) Then
For J = I To UBound(PossibleArray) - 1
PossibleArray(J) = PossibleArray(J + 1)
Next
If UBound(PossibleArray) > 1 Then _
ReDim Preserve PossibleArray(UBound(PossibleArray) - 1)
Exit For
End If
Next
X = X Mod Group
If X = 0 Then X = Group
NextIter X, Iter + 1
End Function


not my cleanest code but it works, compares all permutations on any number of variables and compares all combinations (some are repeated because of the parentheses) but eventually should get to a result. Next time your son gets such homeworks i hope im on vacations ;)

(((8+13)*6)/(23-14))

[Aaron Blood]

Next time your son gets such homeworks i hope im on vacations ;)

(((8+13)*6)/(23-14))

Curse the foul teacher who would devise such an evil exercise :devil2:

footinmout Ah well, at least I was able to predict that someone would come forth with an answer and prove me wrong.

Good job on the code to derive it. :clap:

[Len Piwowar]

Thanks for all who answered, the VBA code provided a lot of Brain food! This site is GREAT!!! :bow: