Golden choice problem


#1


I am blocked on the level golden choice. Must I test each possible path or must I find the best coin in the first line and then test with the neighbers?
Thank you for helping


#2

For more help, here is my code

# You must collect the required amount of gold.
# The gate keeper will tell you how much you need.
# Always move in the direction of the exit.
# For each row you can take only one coin.
# Choose only one from the nearest coins in the next row.

# Distance between rows and coins.
distanceX = 4
distanceY = 6
zeroPoint = {"x": 14, "y": 14}
coinLines = 10

def makeGoldMap(coins):
    template = [[0 for j in range(2 * coinLines - 1)] for i in range(coinLines)]
    for coin in coins:
        row = int((coin.pos.y - zeroPoint.y) / distanceY)
        col = int((coin.pos.x - zeroPoint.x) / distanceX)
        template[row][col] = coin.value
    return template

# Prepare the gold map. It looks like:
# [[1, 0, 9, 0, 4],
#  [0, 1, 0, 9, 0],
#  [8, 0, 2, 0, 9]]
goldMap = makeGoldMap(hero.findItems())

# Find your path.
maxi=0
index=0
for x in range(10):
    if goldMap[9][x]>maxi:
        maxi=goldMap[9][x]
        index=x
hero.moveXY(14+index*8,14)
for x in range(9):
    if x%2==0:
        if goldMap[8-x][index]>goldMap[8-x][index-1]:
            hero.moveXY(hero.pos.x+4,hero.pos.y+6)
        else:
            hero.moveXY(hero.pos.x-4,hero.pos.y+6)
            index-=1
    else:
        if goldMap[8-x][index]>goldMap[8-x][index+1]:
            hero.moveXY(hero.pos.x+4,hero.pos.y+6)
            index+=1
        else:
            hero.moveXY(hero.pos.x-4,hero.pos.y+6)

And in witch direction is the golMap?


#3

This level is an advanced one and shouldn’t block the main path.
You can try tree search algorithm (slooooow for this level) or look at dynamic programming algorithms.


#4

Oh I see, then It will be a pretty good exercice