« first day    last day (16 days later) » 

00:13
def naive_cost(d, Cmax) :
price = 0
C = Cmax
current = d[0]
i = 1
while i <= len(d) :
if d[i-1]-current < C :
C -= (d[i-1]-current)
else :
price += (Cmax-current)**2
current=d[i-1]
C = Cmax

i+=1
return price


def _cost(lastStop, d, Cmax, i) :

if i == len(d)-1 :
return (d[i]-lastStop)**2

current = d[i]
next = d[i+1]
price = (Cmax-(lastStop-current))**2

#We have water left
if (next-lastStop) >= 0 :
return min(_cost(lastStop, d, Cmax, i+1), _cost(current, d, Cmax, i+1) + price)
#We don't have enough water we have to stop and refuel
I simplified my program and it displays the value 576, I made a simple program that simply pays there is no more fuel and we get 68. Which is not logical, I don't know where is the problem please
I don't know why, I don't have a button to display code sorry
I modified my topic the indented code is above
 
1 hour later…
01:42
Okay, so this looks like a greedy algorithm, but probably greedy in the wrong way. There's also some probable off-by-one errors there. Almost always (pay attention to this bit :P ):
- Loops should use `< upperBound` as their limit (not `<= upperBound`)
- `len(d)` or anything that returns the size of an array or list gives the number of elements in the list
- an array of list has elements at indices from `0` to `length - 1` inclusive
Those three things really go together. Any time you break one of those rules (which you are, with your loop), you'll confuse other programmers and invite off-by-one errors where your code disagrees with the standard every library or piece of input uses.
Again, I think you're only hurting yourself by keeping this C variable around. Properly updating it is going to be a pain, don't bother. You have to refill completely at each oasis you stop at, so your remaining water is just a function of your max, your current position, and the the position you last stopped at. It's a lot easier to just compute it when you need it than try to update it to remain correct. Generally that's a good habit to get into.
I notice your naive_cost algorithm is not recursive - it is calling the _cost algorithm. It's probably not a good idea to mix the two.
 
2 hours later…
04:06
Yes I see, but the naive_coste algorithm. Is not an algorithm that answers the problem, I coded it quickly to find out how much the price will be if we stop in each oasis when we have no more water, without looking for a minimum cost. I did just show that the recursive algorithm I made displayed a nonsensical result. So I would like to know where I could have gone wrong on the recursive algorithm please
 
13 hours later…
17:29
My answer is still the same as before - you're making your life difficult by keeping track of the C parameter, get rid of it. This is often the case in coding - it is easier to compute things once when you need them, than to try to "keep them accurate" by having a mutable value which you update to reflect underlying changes. You should really only do the latter as a performance thing, and in this case the calculation is so cheap there's no reason to.
Do you understand why I'm claiming it's unnecessary?
 
4 hours later…
21:50
    def _cost(lastStop, d, Cmax, i) :

        if i == len(d)-1 :
            return (d[i]-lastStop)**2

        price = (Cmax-(d[i]-lastStop))**2

        return min(_cost(lastStop, d, Cmax, i+1), _cost(d[i], d, Cmax, i+1) + price)

    def cost(d, Cmax) :
        return _cost(0,d,Cmax,0)


    d = [8, 9, 16, 18, 24, 27, 32]
    Cmax = 10

Yes I see but the recursive algorithm still does not work. The minimum is always the price without filling the bottle

« first day    last day (16 days later) »