Several TI-Basic programs have been created for the the 24 Game. The goal of this game is to manipulate four integers from 1-9 so that the result is 24. You can use the four common math operators (+,-,*,/). In addition, you can use parentheses/brackets to group operations. The following is an example of a valid solution: 4+8/(2/5)=24.

Instead of creating another port, I wanted to create a solver. This prompted me to start thinking about it.



Here is my code right now.

Code:

This program is testing each possible solution by changing each operator one at a time, then the parentheses, then the order of the numbers. It will test all 24576 possible solutions.
It will solve for most solutions. However, there are some drawbacks to this. Sometimes, it will test duplicate solutions. Sometimes, it will test for solutions such as A-(B)/(C+D. Sometimes, it will error in a divide by zero error. This usually happens when there are duplicate numbers in the 4 numbers or when the expression has a divide by zero such as 5/(9-6-3).

I am looking for a faster way to test for a solution. Here is something that I found to be helpful. However, I am unsure of which is the best method nor do I know how to duplicate the method into TI-Basic.http://rosettacode.org/wiki/24_game/Solve

Thanks!

Electo, that is some spiffy code right there! As for your questions, I feel that to do error checking would definitely slow down the program drastically, and it is really a toss-up between speed and accuracy. However, I do feel that a divide by 0 error can be rather annoying, so I'm wondering if it would be possible to do a quick check to see if stuff after the division sign is 0, and if so, to skip that statement. So maybe:


Code:


Or something like that? Please keep in mind though that it is like 2 am and my mind might be on the fritz.

Thanks! I went with the following:

Code:

I added that last part to test the the evaluation of what it actually being divided, not the entire string after the "/". Note that this won't work for double parentheses such as 2/((4-2)-2).

I decided to display the numbers instead of the letters. This was an easy substitution. Also, instead of changing the parentheses, I have defined the 11 possible combinations.


Code:


This method is similar the BBC Basic method on the page I linked to in the first post.

Download here.

Here is a animated screenshot of what it looks like now.

I thought of an idea that could lead to a massive improvement in speed; the only problem is that the string can't be displayed every time.

Regarding checking for divide-by-zero errors, as I mentioned in SAX, the numbers can be slightly changed, in the 11th or 10th decimal place, so that they will equal something small, rather than zero—that way, the answer will be large rather than causing an error. I suggest offsetting the numbers by... maybe {0, E-10, -E-10, -E-9}? I don't know exactly what would work. When checking if the expression is equal to 24, it can be rounded first.

Here's my idea: Instead of using separate loops for parentheses and operations, use the sequence variables, and have them refer to each other. There are two possible arrangements of the tree. For example, u could be v/w, v could be [first num]+[second num] and w could be [third num]-[fourth num]. As the calculator evaluates the subexpressions automatically, those ten or so calls to sub( in the innermost loop can be eliminated.

In the first, with your numbers stored in L₁ u uses v and w, v uses L₁(1) and L₁(2), and w uses L₁(3) and L₁(4).
In the second, u uses v and L₁(1), v uses w and L₁(2), and w uses L₁(3) and L₁(4). Notice how similar these are.

For each tree, there are 4^3 operation choices, and 2^3 choices for the order of the operand. But some of these can be eliminated—multiplication and addition are commutative, so changing the order isn't necessary unless the operation is / or -. Therefore, there are only (2*2+2)^3 choices for the combined order and operation choices, and multiplying this by the 24 permutations of four numbers and two possible trees gives 10368 iterations, also a significant improvement over the other method. I think this still catches every possible distinct number that the numbers can generate.

The program should be organized like this:
[Initialize stuff]
Outermost loop, to select which tree
Loop to store string to u
Loop to store string to v
Loop to store string to w
Innermost loop, to permute the numbers:
[Set L₁, which u depends on]
If u=24, if so Goto DISPCODE]
Lbl MAINLP
End
End
End
End
While 0 //subroutine
Lbl DISPCODE
[display numbers]
Goto MAINLP
End

Here is the code I have so far. I have left close-parens and quotes on for clarity, and have done no line-by-line optimization besides what came to me immediately. Maybe you could use Ans rather than L₁. Storing the formula to L₁ won't work as it will re-evaluate every time, slowing the program down.

Also, this is completely untested. Sorry.

Code:

Wow, this is amazing lirtosiast! I had never thought of using equation variables to manipulate the different combinations. On top of that, this is my first time dealing with trees.

I never mentioned that the code in the third post of this topic dealt with 16896 iterations. (4 operations)³ × (11 parentheses groups) × (24 order groups).

Am I right to say that you code does indeed test for groups such as "(#*(#-#))-#"?

Using your code, I was able to display the combinations using a subroutine I wrote. Here is the code I have in TokenIDE:

Code:


However, as can be seen in the screenshot below, it is apparently testing some combinations twice. This can be duplicated by inputing the list {4,5,6,7 with the above code.

Is there something fixable causing this?

Also, the subroutine for displaying does not yet support the equation variables that are nested (e.g., u=#/v where v=w-# where w=#*#).

I have not implemented the divide by zero error checking yet.

Thanks in advance for any help!

I haven't really dealt with trees either—it just seemed like the right name for a structure where expressions depend on ones below them.

Yes, an expression like "(A*(B-C))-D" will be calculated like this:
u=v-x1
v=x2*w
w=x3-x4 (or the duplicate solution x4-x3)
(A,B,C,D)=(x2,x3,x4,x1). (or the duplicate solution (x2,x4,x3,x1). Permutations where x4 comes before x3 are unnecessary.)

Yes, this can be easily fixed. Here's what you do:
-Never permute x3 and x4. They will be interchanged in w whenever necessary.
-If T=1, don't permute x1 and x2 either, as they will be interchanged in v whenever necessary.

EDIT: fixed this paragraph
So you can rearrange the columns in the matrix (use twelve columns, all with the 3rd number less than the 4th) so that the first six also have the 1st number less than the 2nd. Then in the innermost For loop, you can use For(P,1,6T) for the necessary six and twelve permutations when T=1 and 2 respectively.

This reduces the number of iterations by a factor of three, to 3456, and I think it still gets every possible combination.

Nice display code—I gave up on writing one because thinking about the sub(s melted my brain. A more elegant solution may not be possible for this, but you may be able to shorten it by taking advantage of the stored values for T, X, Y, and Z. Also note that when the third argument to inString( is 1, it can be elided.

EDIT 2: I think you actually only need three permutations for T=1! These are (1,2,3,4); (1,3,2,4); and (1,4,2,3). This reduces the total number of iterations to 2880.