def fertilize():
    if not use_item(Items.Fertilizer):
        if get_entity_type() == None:
            return True
        if num_items(Items.Fertilizer) == 0 and not trade(Items.Fertilizer, 100):
            return False
        if not use_item(Items.Fertilizer):
            return False
    return True

def xy_to_idx(x, y):
        return y * get_world_size() + x

def idx_to_xy(idx):
    s = get_world_size()
    return idx % s, idx // s

# Assuming we start somewhere in the middle for more efficient pathing
def maze():
    SIZE = get_world_size()
    SIZE_M_1 = SIZE - 1

    U = 0
    R = 1
    D = 2
    L = 3
    DIRS = [U, R, D, L]
    BACK = [D, L, U, R]
    MOVES = [North, East, South, West]
    SYMBOLS = ["^", ">", "v", "<"]
    OFFSETS = [SIZE, 1, -SIZE, -1]

    # Tuples of (back, distance, exhausted)
    flow = []
    for i in range(SIZE ** 2):
        flow.append(None)

    ox = get_pos_x()
    oy = get_pos_y()
    oi = xy_to_idx(ox, oy)

    flow[oi] = [None, 0, False]

    def navigate_to(target):
        back_path = {-1}
        moves_back = []
        moves = []
        pos = xy_to_idx(get_pos_x(), get_pos_y())
        if pos == target:
            return

        intersection = oi

        while pos != oi:
            back_path.add(pos)
            moves_back.append(flow[pos][0])
            pos += OFFSETS[flow[pos][0]]
        while target != oi:
            if target in back_path:
                intersection = target
                break
            dir = flow[target][0]
            moves.insert(0, BACK[dir])
            target += OFFSETS[dir]

        for dir in moves_back:
            if xy_to_idx(get_pos_x(), get_pos_y()) == intersection:
                break
            if not move(MOVES[dir]):
                print("Path: ")
                print(moves)
                print("Attempted to make a bad move" * 5)
        for dir in moves:
            if not move(MOVES[dir]):
                print("Path: ")
                print(moves)
                print("Attempted to make a bad move" * 5)

    def can_explore_dir(pos, dir):
        from = flow[pos]
        # Do not go back
        if dir == from[0]:
            return False

        x, y = idx_to_xy(pos)

        # Do not go OOB
        if dir == U and y == SIZE_M_1:
            return False
        if dir == D and y == 0:
            return False
        if dir == L and x == 0:
            return False
        if dir == R and x == SIZE_M_1:
            return False

        return True

    treasure = [None]

    def explore(max_line):
        for i in range(SIZE ** 2):
            flow[i] = None
        flow[oi] = (None, 0)

        to_explore = {oi: 0}
        linear = []
        while len(to_explore) > 0 or len(linear) > 0:
            #quick_print("= STEP =")
            if get_entity_type() == Entities.Treasure:
                treasure[0] = pos

            pos = oi
            if len(linear) > 0:
                pos = linear.pop()
            else:
                min_distance = 999999
                for p in to_explore:
                    dist = to_explore[p]
                    if dist < min_distance:
                        min_distance = dist
                        pos = p
            navigate_to(pos)

            data = flow[pos]

            end_linear = False

            next_distance = data[1] + 1

            viable_dirs = []

            for dir in DIRS:
                if not can_explore_dir(pos, dir):
                    continue

                other_pos = pos + OFFSETS[dir]
                other = flow[other_pos]
                # Explored cell is distance 1 away, ignore it
                if other != None and abs(other[1] - data[1]) <= 1:
                    continue

                # Can't move to that cell, ignore it
                if not move(MOVES[dir]):
                    continue
                move(MOVES[BACK[dir]])

                linear.append(other_pos)
                if other == None:
                    flow[other_pos] = (BACK[dir], next_distance)
                else:
                    if other[1] > next_distance:
                        flow[other_pos] = (BACK[dir], next_distance)
                    end_linear = True
                    linear.pop()
                    continue

            if pos in to_explore:
                to_explore.pop(pos)

            if end_linear or len(linear) > max_line:
                for pos in linear:
                    to_explore[pos] = flow[pos][1]
                linear = []

            continue # old code below
            if not move(MOVES[dir]):
                continue
            pos += OFFSETS[dir]
            flow[pos] = (BACK[dir], data[1] + 1)
            for dir in DIRS:
                if can_explore_dir(pos, dir):
                    to_explore.append((pos, dir))

    # Will break with cycles
    def dumb_explore():
        def try_explore_dir(pos, dir):
            from = flow[pos]
            # Do not go back
            if dir == from[0]:
                return False

            x, y = idx_to_xy(pos)

            # Do not go OOB
            if dir == U and y == SIZE_M_1:
                return False
            if dir == D and y == 0:
                return False
            if dir == L and x == 0:
                return False
            if dir == R and x == SIZE_M_1:
                return False

            cell = flow[pos + OFFSETS[dir]]
            if cell == None:
                return True

            # Do not go to exhausted cells
            return not cell[2]

        for i in range(SIZE ** 2):
            flow[i] = None
        flow[oi] = [None, 0, False]

        pos = oi
        while True:
            if get_entity_type() == Entities.Treasure:
                treasure[0] = pos
            moved = False
            for dir in DIRS:
                try_explore_dir(pos, dir)
            for dir in DIRS:
                if try_explore_dir(pos, dir) and move(MOVES[dir]):
                    moved = True
                    distance = flow[pos][1] + 1
                    pos += OFFSETS[dir]
                    flow[pos] = [BACK[dir], distance, False]
                    break
            if not moved:
                if pos == oi:
                    return
                flow[pos][2] = True
                dir = flow[pos][0]
                move(MOVES[dir])
                pos += OFFSETS[dir]

    dumb_explore()

    iter = 0
    while True:
        iter += 1
        if iter == 100 or iter == 200:
            navigate_to(oi)
            explore(35 - (iter // 10))

        navigate_to(treasure[0])
        next = measure()
        if next == None:
            harvest()
            return
        nx, ny = next
        treasure = [xy_to_idx(nx,ny)]
        while get_entity_type() == Entities.Treasure:
            fertilize()