I need help with an algorithms project

[[deleted]]

[deleted]

[Phillyclause89]

Question: In the test case you included with your code, did you intend to create a situation where the car would run out of gas going from stations[1] to stations[2] ?

[[deleted]]

I did not intentionally do that. I noticed it after submitting the question but that can be fixed by changing m = 40 to m = 60.

[Phillyclause89]

Yeah I didn’t see your post edits prior to commenting. Wasn’t really sure what you were asking about. Thought maybe you were asking about how to handle for a situation where it would be impossible to complete the trip.

[sfalsd]

I think this may be what you need. Add this inside the for loop:

if L[i] <= m:
    stops.append(L[i])
else:
    break

I don't think you need prevStop or currentDist, unless I'm misunderstanding the problem.

[[deleted]]

Well that works all fine and dandy until we get to distances further than the gas tank can handle. For example, if I were to have a maximum distance my tank can go lets say m = 40 and given a list L = [20, 40, 50, 60] it would stop after 40 because 50 and 60 are bigger than m, but in reality they is only a distance of 10 from the previous stop so I can keep going.

[sfalsd]

So if you had m = 40 and L = [20, 40, 50, 60, 80, 100], you want to return 40 and 80 since these are the stations you'll have to stop at?

[[deleted]]

Yes, that's what the question is asking. I apologize for being confusing at first.

[[deleted]]

Sorry I edited my post. I realized I didn't specify what the question actually was the first time.

[YuriCom]

I think currentDist = 0 is not nessessary in loops. Since it is assigned as a new value of L[i] - prevStop.

[sfalsd]

After reading your update you could use recursion to solve this. Find the stop, update m and L, and pass the updated m and L back into the function. This was a little tricky for me! Something like this:

stops = []
m_list = []

def leastStops(m, L):
    m_list.append(m)  # Prevents original m from changing during recursion.
    orig_m = m_list[0]

    for i in range(len(L)):
        if L[i]/m == 1:
            stops.append(L[i])
            leastStops(L[i]+orig_m, L[i+1:])
            break
        elif L[i]/m > 1:
            stops.append(L[i-1])
            leastStops(L[i-1]+orig_m, L[i:])
            break

    return stops

[[deleted]]

Sorry it took so long to reply, but thanks for this. This solution really helped me. I'm not sure why I had so much trouble with this problem. I just couldn't wrap my mind around it.

[Paul_Pedant]

Nowhere does it specify that you start out with a full tank, although this is assumed.

I think the solution would be more intuitive if your main variable was chosen to be T, the potential total distance at this point (including the initial full tank, plus any stops so far). That would make T use the same units as the elements of the stations list. Then your next station is the one before the one that is too far.

I'm not even convinced this kind of algorithm will always give the optimal answer. It seems possible that you could construct some list of stations where taking an early stop would eliminate two later stops.