Category Archives: C#

Programming in the C# language

Solving the 24 game (or, alternatively, Letters and Numbers)

When I was a child, my parents would play the 24 game with me – pick four numbers, usually from 1 to 9, and try to make 24 using the four basic operations (+ – × ÷). For example, given “5 6 7 8”, you could solve it like this:

  • 7 – 5 = 2
  • 6 ÷ 2 = 3
  • 3 × 8 = 24

Each number had to be used exactly once. It was good arithmetic practice, and made for an educational boredom killer on long car rides. Not every combination of four numbers gave a solution, but most of them did – the trick was usually to work your way to one of 2 × 12, 3 × 8 or 4 × 6.

Once I became somewhat proficient at this game, my parents gave me the killer problem – “1 5 5 5”. I never got it. The answer was quite counterintuitive to me at the time – it’s at the bottom of this post if you want to try it yourself.

I’ve made a program to solve this problem before – about 3 years ago in… Adobe Flash. Yes, Flash and its Actionscript. I couldn’t really code properly at the time, so the algorithm was literally if statements brute forcing through every single possibility.

Then again, I had only just started programming then...

What on earth was I thinking

But the day before yesterday I found out that Microsoft’s Dreamspark program offers free software for students. Perfect for me – I instantly downloaded Visual Studio 2012. I guess they’re trying to get more people to use their software so that they can maintain their market share but, hey, free software works for me.

After messing around a bit in Visual Studio (and following this tutorial to the end), I realised that I could actually make applications now, as opposed to personal-use programs which only I really knew how to use properly.

And this is where the 24 game comes in.

v1.0 - A basic 24 game solver

v1.0 – A basic 24 game solver

Above is the first version I made. I’d never done any C# before, but luckily for me its syntax was so close to that of Java (which universities seem to love teaching nowadays), that it didn’t take long for me to pick up. Being able to look stuff up online is an invaluable skill to have.

The algorithm was quite simple – you start out with n numbers. Pick two of them, and an operation to perform on the numbers. Now you have n-1 numbers. Repeat recursively until you have only 1 number left, and check if it’s 24. If not, then backtrack and pick the next operation or, if you’ve run out of those, the next pair of numbers.

Of course, once you’ve got something basic down perfectly (barring OverflowExceptions, but there’s not much I can do about the limits of 32-bit integers), you want to expand things a bit. And that I did.

v1.5 - I'm just making these version numbers up as I go along

v1.5 – I’m just making these version numbers up as I go along

I took a guess that there was some way to hide/show text boxes, and it turns out that there was. So I added a way to have a variable number of inputs (from 3-6 only, due to running time constraints) and a way to change what your target number was. So now you could play Letters and Numbers.Thanks to the fact that I didn’t hardcode the fact that were four inputs previously, the new change wasn’t hard to make.

As shown above though, the program sometimes gives unusual results, such as unnecessarily dipping into negative numbers/fractions and back out again. This is because the program halts immediately upon finding any solution – maybe I could modify that in the future if I’m bothered. The fractions are there because all numbers are stored as fractions consisting of two integers – a numerator and a denominator, to solve the trickier puzzles.

But after an easy modification like that, I wanted a challenge.

Exponentiation could potentially be a major troll

Exponentiation could potentially be a major troll

Another variant is the “Train Carriage Game” – train carriages where I live have a four digit code. Split the code up into its individual digits, and try to make the number 10. Only thing is, this variant sometimes allowed exponentiation.

So I wanted to add exponentiation in there. That would be easy if everything was integers, but what if you had fractional powers? You could potentially take 2 to the one-third, giving cube root 2! Unfortunately, I didn’t want to handle irrational numbers because that could result in inexact answers (due to rounding errors), so I only let the program use exponentiation if the answer would be a rational number. Unfortunate, I know.

Not that fractional powers weren’t painful enough already – it took me about an hour or two to iron out bugs like division by zero problems, overflow exceptions and, sneakiest of all, negative powers which became too small for the computer to handle making it think its new fraction was 0/0.

But all in all, I was glad that it worked out in the end, and I had finally made my first usable and somewhat useful application.

Also as tricky is "3 8 3 8"

 

Advertisements