Dynamic Programming - HotelProblem - Version3 Regularization

BOTTOM = 0
RIGHT = 1

def min_steps(movement_cost, life, reg = 2):
    rows = len(movement_cost)
    cols = len(movement_cost[0])
    m = [[None for __ in range(cols)] for _ in range(rows)]
    decisions = [[None for __ in range(cols)] for _ in range(rows)]
    steps = [[None for __ in range(cols)] for _ in range(rows)]
    life = [[None for __ in range(cols)] for _ in range(rows)]
    m[rows-1][cols-1] = 0   # starting point
    life[rows-1][cols-1] = 4
    steps[rows-1][cols-1] = 0

    for i in range(rows-1, -1, -1):
        for j in range(cols-1, -1, -1):
            if i == rows-1 and j == cols-1:
                continue
            # The above code is in order not to make m[len1, len2] ---> inf
            m[i][j] = float('inf')
            if i < rows-1 and life[i+1][j] > life_cost[i][j]:
                value = m[i + 1][j] + movement_cost[i][j] - reg * life[i+1][j]
                if value < m[i][j]:
                    m[i][j] = value
                    life[i][j] = life[i+1][j] - life_cost[i][j]
                    # Ήρθα από το κάτω κουτί
                    decisions[i][j] = BOTTOM
                    steps[i][j] = steps[i+1][j] + movement_cost[i][j]
            if j < cols-1 and life[i][j+1] > life_cost[i][j]:
                value = m[i][j + 1] + movement_cost[i][j] - reg * life[i][j+1]
                if value < m[i][j]:
                    m[i][j] = value
                    # Ήρθα από το δεξιά κουτί
                    decisions[i][j] = RIGHT
                    life[i][j] = life[i][j+1] - life_cost[i][j]
                    steps[i][j] = steps[i][j+1] + movement_cost[i][j]
    return steps[0][0], decisions, life

# Creating the map with river and rocks
movement_cost = [[1 for __ in range(7)] for _ in range(8)]
# river
movement_cost[3][0] = 3
movement_cost[3][2] = 3
movement_cost[3][3] = 3
movement_cost[3][4] = 3
movement_cost[2][3] = 3
movement_cost[2][4] = 3
movement_cost[0][4] = 3
movement_cost[2][6] = 3
# rocks
movement_cost[0][2] = 5
movement_cost[4][2] = 5
movement_cost[4][3] = 5
movement_cost[6][2] = 5
movement_cost[7][2] = 5
movement_cost[5][5] = 5

life_cost = [[0 for __ in range(7)] for _ in range(8)]
life_cost[1][0] = 2
life_cost[1][3] = 3
life_cost[3][3] = 3
life_cost[3][6] = 2
life_cost[5][1] = 3
life_cost[5][3] = 3

#trees
life_cost[4][0] = -2
life_cost[7][1] = -2


def get_decisions(decisions, life, i, j):
    describe_square = "("+str(i)+","+str(j)+")  Life: "+str(life[i][j])
    if decisions[i][j] is None:
        return describe_square
    if decisions[i][j]==BOTTOM:
        return get_decisions(decisions, life, i+1, j)+"\n-> "+describe_square
    if decisions[i][j]==RIGHT:
        return get_decisions(decisions, life, i, j+1)+"\n-> "+describe_square
    raise Exception("Shouldn't be called")


for reg in range(0,10):
    print("********  reg = " + str(reg) + "  ********")
    steps, decisions, life = min_steps(movement_cost, life_cost, reg)
    print("Steps: " + str(steps))
    print(get_decisions(decisions, life, 0, 0))
    print()

reg2 = 0.0
while reg2 < 1:
    print("********  reg2 = " + str(reg2) + "  ********")
    steps, decisions, life = min_steps(movement_cost, life_cost, reg2)
    print("Steps: " + str(steps))
    print(get_decisions(decisions, life, 0, 0))
    print()
    reg2 += 0.1