I solved GCHQ puzzle and this is how I did it

Today, I was reading the BBC news and I stumbled upon this GCHQ puzzle:
Take the digits 1,2,3 up to 9 in numerical order and put either a plus sign or a minus sign or neither between the digits to make a sum that adds up to 100. 

For example, one way of achieving this is: 1 + 2 + 34 - 5 + 67 - 8 + 9 = 100, which uses six plusses and minuses. What is the fewest number of plusses and minuses you need to do this?

I love to challenge myself with these kind of puzzles, so I solved this and here is how:

We have 9 numbers [1 to 9] and also we have three possible separators [+, - and nothing] which to fill the gap between numbers we have 8 combinations of separators, e.g. we have 1+2+3+4+5+6+7-89 which in this case we have six times plus, one minus and one time nothing.
So, I need to find all possibilities of combination which total is: 6561

Then, hook the possible combinations into numbers and check the total, easy enough. Now print the solution.

I have written this algorithm in PHP but easily can be written in any other languages too. Of course, this code can be improved, this is just for demonstration:

123+45-67+8-9=100
123+4-5+67-89=100
123-45-67+89=100
123-4-5-6-7+8-9=100
12+3+4+5-6-7+89=100
12+3-4+5+67+8+9=100
12-3-4+5-6+7+89=100
1+23-4+56+7+8+9=100
1+23-4+5+6+78-9=100

Link to the code: https://bitbucket.org/snippets/MehdiDana/8yyLr4/gchq-puzzle-1


Feel free to comment.


BBC link: http://www.bbc.co.uk/programmes/articles/5wkxjTtqRvq8Cyrrjxtk7tc/puzzle-for-today

Comments

Popular posts from this blog

Why I don't have social media account?

The best way to predict the future is to create it