(Update: now allows a gas tank size maximum)
You can solve this in linear time as follows:
void FindStartingPoint(int[] gasOnStation, int[] gasDrivingCosts, int gasTankSize)
{
// Assume gasOnStation.length == gasDrivingCosts.length
int n = gasOnStation.length;
// Make a round, without actually caring how much gas we have.
int minI = 0;
int minEndValue = 0;
int gasValue = 0;
for (int i = 0; i < n; i++)
{
if (gasValue < minEndValue)
{
minI = i;
minEndValue = gasValue;
}
gasValue = gasValue + gasOnStation[i] - gasDrivingCosts[i];
}
if (gasValue < 0)
{
Console.WriteLine("Instance does not have a solution: not enough fuel to make a round.");
}
else
{
// Try a round.
int gas = DoLeg(0, minI, gasTankSize);
if (gas < 0)
{
Console.WriteLine("Instance does not have a solution: our tank size is holding us back.");
return;
}
for (int i = (minI + 1) % n; i != minI; i = (i + 1) % n)
{
gas = DoLeg(gas, i, gasTankSize);
if (gas < 0)
{
Console.WriteLine("Instance does not have a solution: our tank size is holding us back.");
return;
}
}
Console.WriteLine("Start at station: " + minI);
}
}
int DoLeg(int gas, int i, int gasTankSize)
{
gas += gasOnStation[i];
if (gas > gasTankSize) gas = gasTankSize;
gas -= gasDrivingCosts[i];
return gas;
}
First, we look at the case where we don't have a gas tank with a maximum.
Essentially, in the first for-loop, we just drive the circle around, not caring if our fuel tank has negative fuel or not. The point of this is that no matter where you start, the difference between how much there is in your fuel tank at the start (0) and at the end is the same.
Therefore, if we end up with less fuel than we started (so less than 0), this will happen no matter where we start, and so we can't go a full circle.
If we end up with at least as much fuel as we started after going a full circle, then we search for the moment our fuel tank was at its lowest point (which is always just as we get to a gas station). If we start at this point, we will never end up with less fuel than at this point (because it is the lowest point and because we don't lose fuel if we drive a circle).
Therefore, this point is a valid solution, and in particular, there always is such a point.
Now we'll look at the version where our gas tank can hold only so much gas.
Suppose our initial test (described above) we found out it is not impossible to go the entire circle. Suppose that we start at gas station i, we tank at gas station j, but our gas tank ends up being full, so we miss out on some extra gas the station has available. Then, before we get to station k, we end up not having enough fuel, because of the gas we missed out on.
We claim that in this scenario, this will end up happening no matter where you start. Suppose we start at station l.
If l is between j and k, then we either stop (long) before we can get to station k because we started at a bad station, or we'll always have at most the amount of fuel that we had when we started at i when we try to get to k, because we passed through the same stations (and our tank was full when we passed j). Either case is bad.
If l is not between j and k, then we either stop (long) before we get to j, or we arrive at j with at most a full tank, which means that we won't make it to k either. Either case is bad.
This means that if we make a round starting at a lowest point just like in the case with the infinitely large gas tank, then we either succeed, or we fail because our gas tank was too small, but that means that we will fail no matter which station we pick first, which means that the instance has no solution.
Here's a quick implementation in java. The idea is to find how many cards can be picked each step by counting the number of cards with a number below this step and subtracting the number of cards already picked. Of course a lot of work is unnecessarily repeated, but this should give a good idea of how to approach this problem.
public class PickCards {
public static int countLessOrEqualThanMax(int[] cards, int max) {
int count = 0;
for (int number : cards) {
if(number <= max) count++;
}
return count;
}
public static void main(String[] args) {
int[] cards = {0, 1, 2, 4, 3};
int numberOfWays = 1;
for(int i = 0; i < cards.length; i++) {
int ways = Math.max(0, countLessOrEqualThanMax(cards, i) - i);
numberOfWays *= ways;
}
System.out.println(numberOfWays);
}
}
Best Answer
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:
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.