Finding a path of a solved recursive function

Question

In the code below, I got the optimal value of a recursive function that I set.
Now I want to get the values that helped build it - I mean, know which choice (or a "ride" (this is my decision)) was used in each step, and return that also as a string/array/somehow.

thestory : i have 6 rides, in every step i need to choose whether to go on the ride im on again, or switch. every ride has a fun rate for each time i go on it and i want to maximize the fun. right now i have the optimal value but not the rides that i went on that led me to it

The function F is the main focus here.

import math
import numpy as np

#fun rate for each ride,per loop
def funPerRide(rideNum,loopsNum):
    if rideNum==1:
        return 0

    if rideNum==2:
        return 100-np.power((4*loopsNum-10),2)

    if rideNum==3:
        return 50-(1000*np.power(np.e,(-loopsNum/2))/(5*loopsNum+20))

    if rideNum==4:
        return 4*loopsNum

    if rideNum==5:
        return 2.5*np.power(loopsNum,2)

    if rideNum==6:
        return 50*np.power(np.e,(-2*loopsNum+4))


def F(totalTime,timeLeft,rideNum,loopOnCurrRide):
    #time of line+operation of ride
    totalTimePerRide={1:0,2:40,3:15,4:20,5:23,6:11}
    #time of operation of rides
    operationTimePerRide={1:0,2:4,3:5,4:8,5:3,6:6}
     #unfeasable conditions:        
    if timeLeft<0:
        return -np.inf

    if timeLeft+loopOnCurrRide*operationTimePerRide[rideNum]>totalTime:
        return -np.inf

    if loopOnCurrRide>3:
        return -np.inf
    #edge condition
    if timeLeft == 0:
        return 0

    #fun if i stay on the ride im on right now
    staying = funPerRide(rideNum,loopOnCurrRide+1)-funPerRide(rideNum,loopOnCurrRide)+F(totalTime,timeLeft-operationTimePerRide[rideNum],rideNum,loopOnCurrRide+1)

    #calculating fun if i switch to the maximum-fun-ride, that is not the ride im currently at
    switching = -1
    whichRide=-1
    for i in range(1,7):
        if i>rideNum:
            switchOption = funPerRide(i,loopOnCurrRide)+F(totalTime,timeLeft-4.5-totalTimePerRide[i],i,1)
            if switchOption>switching:
                switching, whichRide=switchOption,i

    #calculating maximum fun between switching and staying
    maxval,maxride=max((staying,rideNum),(switching,whichRide))
    path.append(maxride)
    maxval=float(maxval)

    return float(maxval)

path = []    
print(F(120,120,1,0),path)

I see a case of severe hardcoding. You can replace all those countless if-statements with a one-liner using a dictionary. — Eli Korvigo, Jan 01 '16 at 15:00
true. i will make it all a dictionary/list, but this isn't the current issue i'm afraid.. i need to think of a way to record the path — DaniKa, Jan 01 '16 at 15:17
Hey @DanielleKapon, please comment the code whenever you can and use camelCase for readability's sake. And welcome to Python — RinkyPinku, Jan 01 '16 at 16:02
Yup, working on it. In the mean time you might wanna take a look at https://docs.python.org/3/library/traceback.html and http://stackoverflow.com/questions/3702675/how-to-print-the-full-traceback-without-halting-the-program — RinkyPinku, Jan 01 '16 at 16:56
will do. thank you! will be waiting also for your reply, I am really into solving this. thanks alot! — DaniKa, Jan 01 '16 at 16:57
I have tried to analyse both the code and the concept (take a look at my version here http://pastebin.com/7Wm3vQfC) and as far as I understand there is probably a problem in algorithm (of the function F()). Why? Because there is no bifurcation, code flow is completely serial. And if the algorithm is correct then you have already found optimal path (see http://pastebin.com/kivAZ2mc). Can you possibly point me to the theory or source of this challenge - I like the math behind it. — RinkyPinku, Jan 01 '16 at 17:54
The theory is actually of a problem i once wrote for a course in uni, and am now trying to code. its basically having an amusement park with 5 rides (no. 1 is the entrance, 2-6 are the rides). My goal is to spend 120 minutes in the park, having the most fun, where I set functions of fun for each ride, according to how much I enjoy it over time. What I want to do now, is to find the optimal route and fun value, within the 5 rides, in the 120 minutes i've got. I also have a restriction that I can not go on one ride more than 3 times. I have written the Bellman equation (see next for more) — DaniKa, Jan 01 '16 at 18:05
and constraints, also the boundary value, and now I just want to program it. i can make you screen captures of what i wrote but where can i place it here? — DaniKa, Jan 01 '16 at 18:11
maybe somthing IS wrong with F because the path i'm getting in your code does not make sense - it is far too long and is against the constraints+I need to print the maxval also — DaniKa, Jan 01 '16 at 18:24
problem solved. I forgot 1 multiplier in my fun functions. thank you so much for your time. — DaniKa, Jan 01 '16 at 18:46
Congrats @DanielleKapon, great job & happy new year :). On a side note you can answer your own question - it would fetch you points and some privileges on this site. — RinkyPinku, Jan 01 '16 at 23:45

Andreikkaa · Accepted Answer · 2016-01-01T17:29:05.833

0

Your function F can return a pair of two values: first - optimal answer, second - optimal path as a list of indexes.

def F(totalTime, timeLeft, rideNum, loopOnCurrRide):
    # time of line+operation of ride
    totalTimePerRide = {1: 0, 2: 40, 3: 15, 4: 20, 5: 23, 6: 11}
    # time of operation of rides
    operationTimePerRide = {1: 0, 2: 4, 3: 5, 4: 8, 5: 3, 6: 6}
    if timeLeft + loopOnCurrRide * operationTimePerRide[rideNum] > totalTime:
        return -10, []

    if loopOnCurrRide > 3:
        return -10, []

    if timeLeft == 0:
        return 0, []

    staying, staying_path = F(totalTime, timeLeft - operationTimePerRide[rideNum], rideNum, loopOnCurrRide + 1)
    staying += funPerRide(rideNum, loopOnCurrRide + 1) - funPerRide(rideNum, loopOnCurrRide)
    staying_path = [-1] + staying_path

    switching = -1
    switching_path = []
    for i in range(1, 7):
        if i > rideNum:
            switchOption, switchOption_path = F(totalTime, timeLeft - 4.5 - totalTimePerRide[i], i, 1)
            switchOption += funPerRide(i, loopOnCurrRide)
            if switchOption > switching:
                switching = switchOption
                switching_path = [i] + switchOption_path

    return max((staying, staying_path), (switching, switching_path))


answer, path = F(120, 120, 1, 0)

edited Jan 01 '16 at 17:29

answered Jan 01 '16 at 16:46

Andreikkaa

297
1
7

with this I am getting: TypeError: unsupported operand type(s) for +: 'int' and 'tuple' on the row of the staying,staying path. moreover if we put staying,staying_path and only recieve one value to it, what does it do? – DaniKa Jan 01 '16 at 16:54
This is getting really close! now i am getting answer= 2728.90750166 (like before) and path = [6], which is probably the last option i'm in, but I am still missing the whole path... if I just put this option that i just went to ride 6, i get a much smaller value for the answer – DaniKa Jan 01 '16 at 17:38
@DanielleKapon, implementation of path is correct, but your code seems buggy. For example, check the statement "timeLeft - loopOnCurrRide * operationTimePerRide[rideNum] > totalTime". timeLeft variable should decrease with each round of recursion, and possible you meant "if timeLeft - loopOnCurrRide * operationTimePerRide[rideNum] < 0:"? – Andreikkaa Jan 01 '16 at 18:19
I FOUND IT! i forgot 1 multiplier in my fun functions. thank you so so much! have a wonderful weekend – DaniKa Jan 01 '16 at 18:44
@Andreikkaa great answer, can you please explain how you got such great insight into the problem so quickly? – RinkyPinku Jan 01 '16 at 23:51

Finding a path of a solved recursive function

1 Answers1