Массивы 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}")