1
\$\begingroup\$

The code is an attempted divide and conquer method of finding the maximum total reward of a game where each turn two adjacent numbers in an arbitrary list are multiplied by each other to create a reward and then those two numbers are replaced by a 0, creating a new list and another turn of the game. When the list eventually becomes length 1, the rewards are added up to get the total reward. Any help is appreciated.

I've removed any unnecessary new variables however there are still a handful which I'm not sure if I could cut further. I need the code to output a value in under 5 seconds when a is a list of over 100 elements. I'm certain that the function erase numbers isn't bottlenecking the code so this code is what needs to be optimized from what I know. I'm new to python so apologies if it seems clunky.

def max_reward_daq(a):

n=len(a)

if n<2:
    return 0
else:
    N=n//2
    M=(n//2)+1
    b=a[:N]
    c=a[N:]
    d=a[:M]
    e=a[M:]
    
    r=[]
    s=[]
    t=[]
    u=[]
    for j in range(len(a[:N])-1):
        reward, b=erase_numbers(a[:N],j)
        r.append(reward + max_reward_daq(b))
    for j in range(len(a[N:])-1):
        reward, c=erase_numbers(a[N:],j)
        s.append(reward + max_reward_daq(c))
    for j in range(len(a[:M])-1):
        reward, d=erase_numbers(a[:M],j)
        t.append(reward + max_reward_daq(d))
    for j in range(len(a[M:])-1):
        reward, e=erase_numbers(a[M:],j)
        u.append(reward + max_reward_daq(e))
if r==[]:
    r=[0]
if s==[]:
    s=[0]
if t==[]:
    t=[0]
if u==[]:
    u=[0]
return max(max(r)+max(s),max(t)+max(u))

And the erase_numbers function is this here:

def erase_numbers(a,j):
    
    n = len(a)
    if n < 2:
        raise Exception("list too short")
    elif (j+1>=n):
        raise Exception("invalid j")
    else:
        a_copy=a.copy()
        reward=a_copy[j]*a_copy[j+1]
        a_copy[j]=0
        del(a_copy[j+1])
        return reward, a_copy
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Welcome to Code Review! I changed the title so that it describes what the code does per site goals: "State what your code does in your title, not your main concerns about it.". Feel free to edit and give it a different title if there is something more appropriate. \$\endgroup\$ Dec 10 '21 at 21:18
  • 1
    \$\begingroup\$ Can you fix your formatting (indentation) in the first code file? \$\endgroup\$ Dec 12 '21 at 20:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.