113 lines
3.9 KiB
Python
113 lines
3.9 KiB
Python
|
|
import fileinput
|
|
|
|
def get_row(m, idx):
|
|
return m[idx]
|
|
|
|
def get_col(m, idx):
|
|
return list(map(lambda x: x[idx], m))
|
|
|
|
class Forest:
|
|
|
|
def __init__(self, width, height):
|
|
self.visible = []
|
|
self.heightmap = []
|
|
self.score = []
|
|
self.width = width
|
|
for _ in range(height):
|
|
self.visible.append([False] * width)
|
|
self.heightmap.append([0] * width)
|
|
self.score.append([0] * width)
|
|
|
|
def print(self):
|
|
print("Heightmap:")
|
|
for r in self.heightmap:
|
|
print(''.join(map(lambda x: str(x), r)))
|
|
print("Visibility:")
|
|
for r in self.visible:
|
|
print(''.join(map(lambda x: "X" if x else "O", r)))
|
|
|
|
def solve_visibility(self):
|
|
# TOP-DOWN
|
|
limit = [-1] * self.width
|
|
for rowidx in range(self.width):
|
|
for colidx in range(self.width):
|
|
if limit[colidx] < self.heightmap[rowidx][colidx]:
|
|
self.visible[rowidx][colidx] = True
|
|
limit[colidx] = self.heightmap[rowidx][colidx]
|
|
|
|
# BOT-UP
|
|
limit = [-1] * self.width
|
|
for rowidx in range(self.width):
|
|
for colidx in range(self.width):
|
|
if limit[colidx] < self.heightmap[-rowidx-1][colidx]:
|
|
self.visible[-rowidx-1][colidx] = True
|
|
limit[colidx] = self.heightmap[-rowidx-1][colidx]
|
|
|
|
# LEFT-RIGHT
|
|
limit = [-1] * self.width
|
|
for colidx in range(self.width):
|
|
for rowidx in range(self.width):
|
|
if limit[rowidx] < self.heightmap[rowidx][colidx]:
|
|
self.visible[rowidx][colidx] = True
|
|
limit[rowidx] = self.heightmap[rowidx][colidx]
|
|
|
|
# RIGHT-LEFT
|
|
limit = [-1] * self.width
|
|
for colidx in range(self.width):
|
|
for rowidx in range(self.width):
|
|
if limit[rowidx] < self.heightmap[rowidx][-colidx-1]:
|
|
self.visible[rowidx][-colidx-1] = True
|
|
limit[rowidx] = self.heightmap[rowidx][-colidx-1]
|
|
|
|
def solve_score(self):
|
|
for rowidx in range(self.width):
|
|
for colidx in range(self.width):
|
|
current = self.heightmap[rowidx][colidx]
|
|
lscore = 0
|
|
rscore = 0
|
|
uscore = 0
|
|
dscore = 0
|
|
for idx in range(colidx): # left
|
|
lscore += 1
|
|
if self.heightmap[rowidx][colidx-idx-1] >= current:
|
|
break
|
|
for idx in range(self.width - colidx - 1): # right
|
|
rscore += 1
|
|
if self.heightmap[rowidx][colidx+idx+1] >= current:
|
|
break
|
|
for idx in range(rowidx): # up
|
|
uscore += 1
|
|
if self.heightmap[rowidx-idx-1][colidx] >= current:
|
|
break
|
|
for idx in range(self.width - rowidx - 1): # down
|
|
dscore += 1
|
|
if self.heightmap[rowidx+idx+1][colidx] >= current:
|
|
break
|
|
self.score[rowidx][colidx] = lscore*rscore*uscore*dscore
|
|
|
|
@classmethod
|
|
def parse(cls, lines):
|
|
output = None
|
|
idx = 0
|
|
for line in map(lambda x: x.strip(), lines):
|
|
if line != "":
|
|
if output is None:
|
|
output = cls(len(line), len(line))
|
|
output.heightmap[idx] = list(map(lambda x: int(x), list(line)))
|
|
idx += 1
|
|
return output
|
|
|
|
def visible_count(self):
|
|
output = 0
|
|
for r in self.visible:
|
|
output += sum(r)
|
|
return output
|
|
|
|
if __name__ == "__main__":
|
|
forest = Forest.parse(fileinput.input())
|
|
forest.solve_visibility()
|
|
forest.solve_score()
|
|
forest.print()
|
|
print(f"Visible: {forest.visible_count()}")
|
|
print(f"Score: {max([max(row) for row in forest.score])}") |