Массивы Numpy и векторизация

Я немного отстал, и я не думаю, что закончу в этом году. Постараюсь доделать остальные задачи. Однако я остановился после того, как заболел и сейчас не в лучшей форме, и я был занят работой. Для Дня 8 у нас есть поле деревьев, представленное матрицей значений. В части 1 нам нужно определить, видны ли деревья.

Дерево видимо, если все остальные деревья между ним и краем сетки короче его. Рассматривайте деревья только в одной строке или столбце; то есть смотреть только вверх, вниз, влево или вправо от любого данного дерева.

The expedition comes across a peculiar patch of tall trees all planted carefully in a grid. The Elves explain that a previous expedition planted these trees as a reforestation effort. Now, they're curious if this would be a good location for a tree house.

First, determine whether there is enough tree cover here to keep a tree house hidden. To do this, you need to count the number of trees that are visible from outside the grid when looking directly along a row or column.

The Elves have already launched a quadcopter to generate a map with the height of each tree (your puzzle input). For example:

30373
25512
65332
33549
35390

Чтобы определить это, я использовал NumPy с массивами и использовал синтаксис векторизации NumPy, чтобы определить, все ли деревья в одном направлении были короче, чем текущее дерево.

Во второй части нам нужно найти максимальную сценическую оценку дерева. Сценическая оценка является произведением всех расстояний просмотра в каждом направлении. Этот балл рассчитывается для каждого дерева, а затем находится максимальное значение.

Чтобы измерить расстояние просмотра от данного дерева, посмотрите вверх, вниз, влево и вправо от этого дерева; остановитесь, если вы дойдете до края или до первого дерева, которое той же высоты или выше, чем рассматриваемое дерево. (Если дерево находится прямо на краю, по крайней мере одно из расстояний его просмотра будет равно нулю.)

Чтобы найти это, самым простым способом было сделать петлю в каждом направлении и сломаться, когда будет найдено дерево равной или большей высоты; код написан ниже. В целом алгоритм использует O(N²) в худшем случае, потому что нам нужно пройтись по каждому дереву, а затем нам, возможно, придется перейти к концу ввода для каждого. Возможно, есть более быстрый способ, но я его еще не нашел.

import numpy as np
import itertools


def parse_data(data):
    data = data.splitlines()
    arr = np.zeros((len(data), len(data[0])), dtype=np.int32)
    for r in range(len(data[0])):
        for c in range(len(data[1])):
            arr[r, c] = int(data[r][c])
    return arr


# is tree at r, c visible
def is_visible(trees, r, c):
    return (
        r == 0
        or c == 0
        or r == trees.shape[0] - 1
        or c == trees.shape[0] - 1
        or np.all(trees[r, :c] < trees[r, c])
        or np.all(trees[r, c + 1 :] < trees[r, c])
        or np.all(trees[:r, c] < trees[r, c])
        or np.all(trees[r + 1 :, c] < trees[r, c])
    )


def scenic_score(trees, r, c):
    up = down = left = right = 0
    # up direction
    for k in range(r - 1, -1, -1):
        if trees[k, c] >= trees[r, c]:
            up += 1
            break
        up += 1
    # down direction
    for k in range(r + 1, trees.shape[0]):
        if trees[k, c] >= trees[r, c]:
            down += 1
            break
        down += 1
    # left direction
    for k in range(c - 1, -1, -1):
        if trees[r, k] >= trees[r, c]:
            left += 1
            break
        left += 1
    # right direction
    for k in range(c + 1, trees.shape[1]):
        if trees[r, k] >= trees[r, c]:
            right += 1
            break
        right += 1

    print(up, down, left, right)
    return up * down * left * right


def max_scenic_score(forest):
    # Keep track of the maximum scenic score seen so far
    max_score = 0
    for r, c in itertools.product(range(forest.shape[0]), range(forest.shape[1])):
        score = scenic_score(trees, r, c)
        if score > max_score:
            max_score = score
    return max_score


def count_visible(trees):
    return int(
        sum(
            is_visible(trees, r, c)
            for r, c in itertools.product(range(trees.shape[0]), range(trees.shape[1]))
        )
    )


if __name__ == "__main__":
    with open("input.txt") as file:
        data = file.read()
        trees = parse_data(data)
        count = count_visible(trees)
        print(f"Count is {count}")
        max_score = max_scenic_score(trees)
        print(f"Max scenic score is {max_score}")