BackFromBrazil

Given 10 different squares made up of 1000x1000 random numbers you need to input the optimal path from the upper left to the lower right corner consisting only of steps d - down or r - right. The sum of all the visited numbers must be maximal.

An approach using dynamic programming can be used to find the optimal path through the square.

import sys

MAX_RUNS = 10
DIMENSION = 1000

# make recursion depth large enough so that width and length of the eggs-square fits in
sys.setrecursionlimit(2*DIMENSION + sys.getrecursionlimit())

def find_max_path(eggs, x, y, cached_result = None):
    if cached_result is None:
        cached_result = dict()

    if (x,y) in cached_result:
        return cached_result[(x,y)]

    right_result = None
    if x+1 < DIMENSION:
        right_result = find_max_path(eggs, x+1, y, cached_result)

    down_result = None
    if y+1 < DIMENSION:
        down_result = find_max_path(eggs, x, y+1, cached_result)

    if right_result is None and down_result is None:
        cached_result[(x,y)] = ('', eggs[y][x])
        return ('', eggs[y][x])

    if down_result is not None and (right_result is None or down_result[1] > right_result[1]):
        result = ('d' + down_result[0], eggs[y][x] + down_result[1])
        cached_result[(x,y)] = result
        return result

    if right_result is not None and (down_result is None or right_result[1] > down_result[1]):
        result = ('r' + right_result[0], eggs[y][x] + right_result[1])
        cached_result[(x,y)] = result
        return result

f = open("backfrombrazil.log", "w")

success = True

# read first input for run
received_reply = input()
f.write("< " + received_reply + "\n")

for run in range(MAX_RUNS):
    received_rows = []
    for i in range(DIMENSION):
        received_rows.append(received_reply)

        received_reply = input()
        f.write("< " + received_reply + "\n")

    eggs = []
    for received_row in received_rows:
        row = list(map(
            lambda s: int(s), 
            received_row.split(" ")[:-1]
        ))
        eggs.append(row)

    (path, sum_value) = find_max_path(eggs, 0, 0)
    print(path)
    f.write("> " + path + "\n")

    if "still in brazil" in received_reply or "didn't find" in received_reply or "out of time" in received_reply:
        success = False
        break

    # read first input for next run
    received_reply = input()
    f.write("< " + received_reply + "\n")

if success:
    received_reply = input()
    print(received_reply, file=sys.stderr)
    f.write("< " + received_reply + "\n")

    received_reply = input()
    print(received_reply, file=sys.stderr)
    f.write("< " + received_reply + "\n")

f.close()

social