(Post is in english, because I've decided to make russian blog posts at specialized it-oriented web community -
http://olostan.habrahabr.ru/blog/, so translations of these posts would be posted there)
(Пост на английском потому что я решил русско-язычные посты вести в блоге сообщества
http://olostan.habrahabr.ru/blog/. Перевод этого поста будет доступен позже по этой ссылке)
Not so long ago I've noticed one funny
post on bash.org.ru (free translation):
xxx: There is numbers 1 3 4 and 6. Task is to get 24 using addition, substruction and multiplication. Numbers could be used only once.
yyy: Listen, can you send me when I will be at office - I got something else to do at home
...and I start thinking about efficient algorithm for solving this problem!
To simplify little bit I've decided to forbid using grouping parentheses. So problem could be stated in such way:
There is a set of numbers A
1...A
n, and target number X. Task is no find such combination of this numbers (order could be changed), that A
x1 (op
1) A
x2 (op
2) ... (op
n-1) A
n = X. (op
1..n-1 - are one of operations "+","-","*","/")
I decided to use C++ to practice with this language. Mostly same solution could be made on any language.
Ok, lets start.
First analysis shows that this problem could be solved with finding vertex in the graph with predefined characteristics. So we can reduce this problem to problem of finding path from some (any) initial vertex to target vertex.
Graph could be set in such way:
- Vertex are some permutation of initial numbers and some set of operations.
- Two vertexes are connected if there is one swap op numbers and one operation changed.
So from any vertex we can get connected vertexes in such way: swap all possible pairs of numbers and for all swapped numbers change one operation.
For example: we have initial numbers 1,2,3. So from vertex (1+2+3) we can get vertexes: (2+1+3),(1*2+3), (3*2+1) etc.
After initial implementation of this algorithm I got results what I've expected. Example output could be:
result:2-1*3-4+5=0 (tested 29828)
Nice, but I do not like 29k of tested solutions... "Can we do better"? I think yes. Lets remember "
A* search algorithm". May be we can use that idea and sort solutions based on how closer we are to target?
There was a tiny change: replace 'queue' with 'priority_queue' and add cost function that will compare two solutions based on how close we are. So each time we get some solution to test we get solution that is more closer to target result.
So after this change I got:
result:4/1+3-5-2=0 (tested 4)
Much better! So with only such small optimization I've lowered length of searching to 4 iterations! Here is a table comparing results of 'queue' and 'priority_queue':
| priority_queue | queue |
| result:4/1+3-5-2=0 (tested 4) | result:2-1*3-4+5=0 (tested 29828) |
| result:1+2-3-4+5=1 (tested 3) | result:1-2+3+4-5=1 (tested 251) |
| result:3/1*4-5*2=2 (tested 109) | result:3-2-1*4+5=2 (tested 29601) |
| result:1-2+3-4+5=3 (tested 3) | result:1-2+3-4+5=3 (tested 248) |
| result:1*2+4-5+3=4 (tested 3) | result:1-2*3+4+5=4 (tested 246) |
| result:1+2+3-5+4=5 (tested 2) | result:2+1+3+4-5=5 (tested 11) |
| result:1+5+3*2*4=30 (tested 3) | result:2*4*3+1+5=30 (tested 558) |
| result:1+5/2*3*4=31 (tested 4) | result:3*5/2*4+1=31 (tested 59961) |
| result:5*2*4-1-3=36 (tested 181) | result:4*2*5-1-3=36 (tested 1006943) |
| result:1*2*4*5-3=37 (tested 160) | result:2*1*5*4-3=37 (tested 1004303) |
So as result I can say that there is a point try to find more efficient way of solving problem.
Source code of solution (very dirty and may be contains some implementation bugs, but my task was not to write a 'clean code' example, but write a solution) is stored on
GitHub Gist.
