If you're stuck with your list data structure
If you strive purely to minimize number of priority updates, there's not too much you can do beyond the binary-search approach.
Otherwise, one possible smallish improvement I can think of is, whenever you insert an item C between B and D, check the item A to the B and E to the right of D and redistribute their priorities.
So for something like:
C
↓
A B D E
0 1 7 8
You'd end up with:
A B C D E
0 2 4 6 8
Note that A
and E
don't change, their priorities are just required in the calculation.
Or you can leave B
where it is and only update D
, or vice versa, depending on whether A
and D
or B
and E
are further apart.
If you can pick another data structure
It would be better to pick one where the priority is structurally defined, not explicitly for each element.
A modified balanced binary search tree could work here, where you store the number of ancestors for each node.
The comparison for insertion would then be defined purely on where you want to insert it compared with the counts of each node.
Note that something like a red-black tree doesn't require any comparisons to keep itself balanced.
Update, insert and delete operations will all take O(log n)
.
Depending on your requirements, you can have a secondary data structure that allows you to look up some node for a given element.
Disclaimer: This answer does not answer the question that completely. But it's too long for a comment.
NP-hard? I believe, this problem could be NP-hard.
Consider a special case of the Knapsack problem:
Given a set of positive integers and a positive integer b, does there exist a subset of the set such that the sum of all integers in that subset equals b?
This sounds somewhat similar to our Countdown problem, and it seems to be much simpler. However, Knapsack (and this special case of Knapsack) is NP-hard (and NP-complete, of course).
I did not manage to use this for a proof that Countdown is NP-hard. I could not get rid of the division. Consider we have a thousand 2, and b = 7. This will never be solvable with Knapsack, but always (?) with Countdown, at least in all the ways I tried to transfer the problem.
Now, if Countdown really was NP-hard, we could deduce that there with very high probability is no algorithm that is significantly more efficient than brute-force trying all possibilities. (And if we should find such an algorithm, we will become very famous.)
No, I don't think there must be an efficient algorithm.
Heuristics. The Youtube video linked in the question has a nice example: The contestant found an exact answer 952 = ((100 + 6) * 3 * 75 - 50) / 25. That is completely against my intuition, I would never have tried it that way in the first time: Produce a very large number, then divide it and yield the result.
On the other, we humans feel that we do not need to try (arbitrary example) 50 * 75 * 100 / 2 / 3 / 7 to reach a three-digit-number. But computers do not feel anything, they simple calculate.
After all, if we implemented some heuristics, and this heuristics does not find an exact solution, we still will have to try all other solutions to make sure there really is none.
What the contestant in the Youtube video does is, I think, to very quickly check a large number of possibilities and to quickly discard those that will not (or likely will not) give a solution.
Conclusion. When implementing an algorithm, one could take care to strip equal calculations such as a / b / c = a / (b * c), but I think this is quite hard to do and I do not know whether this improves the runtime significantly.
Computers of course are faster than humans in checking a large number of possibilities. And nowadays, even smartphones are so fast they can solve this problem, I think, within a second by simply trying all possibilities. (I did not test this.) There are only six numbers, it would be different if there were e.g. 60 of them.
Best Answer
The easiest way is brute force. Generate all the ways to order the numbers and apply the operators, then see if any matches the target value. This will scale very badly, but can be improved with heuristics.
Using your example, we can notice that we only need to try division when it will come out to an integer (assuming you don't mean
/
as truncating integer division). So when we start with 3, we don't need to try dividing by anything but 1.Memoization could also help, but unless you're planning on a large list of targets or expensive operations it probably won't be worth it. If you do go with memoization, I would recommend thinking carefully about what you expect to repeat. If the same target can come up many times, memoizing
target => (numbers, operators)
would make sense. If the numbers can be repeated, you could try memoizing each operator,(operator, operands) => value
. Either way, I would profile any options here before making a decision.Also, if your language has any way to reference functions (closures, function pointers, functors) it will probably be clearest to use those for the operators. Definitely avoid string parsing or
eval
ing expressions.Some ruby-ish pseudocode: