Day 8: Treetop Tree House

#!/usr/bin/env pypy3

import sys

up = lambda f, r, c: [f[r_][c] for r_ in range(r)][::-1]
dn = lambda f, r, c: [f[r_][c] for r_ in range(r + 1, len(f))]
lt = lambda f, r, c: [f[r][c_] for c_ in range(c)][::-1]
rt = lambda f, r, c: [f[r][c_] for c_ in range(c + 1, len(f[r]))]

def main():
    forest = [[int(tree) for tree in line.strip()] for line in sys.stdin]
    total = 0
    for r in range(len(forest)):
        for c in range(len(forest[0])):
            total += any(forest[r][c] > max(d(forest, r, c), default=-1)
                         for d in (up, dn, lt, rt))

    print(total)

if __name__ == '__main__':
    main()

#!/usr/bin/env pypy3

import functools
import operator
import sys

up = lambda f, r, c: [f[r_][c] for r_ in range(r)][::-1]
dn = lambda f, r, c: [f[r_][c] for r_ in range(r + 1, len(f))]
lt = lambda f, r, c: [f[r][c_] for c_ in range(c)][::-1]
rt = lambda f, r, c: [f[r][c_] for c_ in range(c + 1, len(f[r]))]

def view(tree, direction):
    distance = 0
    for neighbor in direction:
        distance += 1
        if neighbor >= tree:
            break
    return distance

def main():
    forest = [[int(tree) for tree in line.strip()] for line in sys.stdin]
    max_score = 0
    for r in range(len(forest)):
        for c in range(len(forest[0])):
            views = (view(forest[r][c], d(forest, r, c))
                     for d in (up, dn, lt, rt))
            max_score = max(functools.reduce(operator.mul, views, 1),
                            max_score)

    print(max_score)

if __name__ == '__main__':
    main()

grid = [[int(x) for x in y.strip()] for y in open("input.txt").readlines()]
onview = [[0 for _ in range(len(grid[0]))] for _ in range(len(grid))]


def measure(m):
    return len(m[0]), len(m)


def rotate(m):
    row, col = measure(m)

    for i in range(row // 2):
        m[i], m[col - i - 1] = m[col - i - 1], m[i]

    for i in range(row):
        for j in range(i):
            m[i][j], m[j][i] = m[j][i], m[i][j]

    return m


for side in range(4):
    i, j = measure(grid)

    for y in range(i):
        tallest = grid[y][0]
        onview[y][0] = 1

        for x in range(j):
            if grid[y][x] > tallest:
                tallest = grid[y][x]
                onview[y][x] = 1
            elif grid[y][x] == 9:
                break
            else:
                continue
    if side == 4:
        break
    grid = rotate(grid)
    onview = rotate(onview)

print(sum(map(sum, onview)))  # Part One: 1543

grid = [[int(x) for x in y.strip()] for y in open("input.txt").readlines()]
hor, ver = len(grid[0]), len(grid)
scenes = [[1 for _ in range(hor)] for _ in range(ver)]


def view(opt: int, length: int, route: int = 1) -> int:
    tallest: int = grid[y][x]
    trees: int = 0
    m = list(zip(*grid) if opt else grid)
    i, j = (x, y) if opt else (y, x)

    for step in range(1, length):
        trees += 1

        if tallest <= m[i][j + step * route]:
            break

    return trees


for y in range(hor):
    for x in range(ver):
        for opts in [(0, ver - x), (0, x + 1, -1), (1, hor - y), (1, y + 1, -1)]:
            scenes[y][x] *= view(*opts)

print(max(map(max, scenes)))  # Part Two: 595080

use std::error::Error;
use std::fs::File;
use std::io::Read;

fn main() -> Result<(), Box<dyn Error>> {
    let mut file = File::open("input_8.txt")?;
    let mut contents = String::new();
    file.read_to_string(&mut contents)?;
    let map: Vec<Vec<char>> = contents.lines().map(|l| l.chars().collect()).collect();
    let visible_count = (0..map.len()).fold(0, |acc, h| {
        acc + (0..map[h].len()).filter(|w| visible(&map, h, *w)).count()
    });
    println!("{visible_count}");
    Ok(())
}

fn visible(map: &Vec<Vec<char>>, h: usize, w: usize) -> bool {
    let (height, tree) = (map.len(), map[h][w]);
    let from_left = map[h].iter().take(w).all(|c| c < &tree);
    let from_right = map[h].iter().skip(w + 1).all(|c| c < &tree);
    let from_top = (0..h).all(|h| map[h][w] < tree);
    let from_bottom = ((h + 1)..height).all(|h| map[h][w] < tree);
    from_left || from_right || from_top || from_bottom
}

use std::error::Error;
use std::fs::File;
use std::io::Read;

fn main() -> Result<(), Box<dyn Error>> {
    let mut file = File::open("input_8.txt")?;
    let mut contents = String::new();
    file.read_to_string(&mut contents)?;
    let map: Vec<Vec<char>> = contents.lines().map(|l| l.chars().collect()).collect();
    let max_view_score = (0..map.len())
        .map(|h| (0..map[h].len()).map(|w| view_score(&map, h, w)).max())
        .max()
        .unwrap()
        .unwrap();
    println!("{max_view_score}");
    Ok(())
}

fn view_score(map: &Vec<Vec<char>>, h: usize, w: usize) -> usize {
    let (height, width, tree) = (map.len(), map[0].len(), map[h][w]);
    let lview = (0..w).rev().take_while(|w| map[h][*w] < tree).count();
    let rview = ((w + 1)..width).take_while(|w| map[h][*w] < tree).count();
    let tview = (0..h).rev().take_while(|h| map[*h][w] < tree).count();
    let bview = ((h + 1)..height).take_while(|h| map[*h][w] < tree).count();
    (lview + if lview == w { 0 } else { 1 })
        * (rview + if rview == width - 1 - w { 0 } else { 1 })
        * (tview + if tview == h { 0 } else { 1 })
        * (bview + if bview == height - 1 - h { 0 } else { 1 })
}

Only including the relevant parts for this puzzle.

defmodule AdventOfCode.CharGrid do
  @moduledoc "Data structure representing a finite grid of characters by a map of {x, y} => char"

  alias __MODULE__, as: T

  @type t :: %T{
          grid: grid,
          width: non_neg_integer,
          height: non_neg_integer
        }

  @typep grid :: %{coordinates => char}

  @type coordinates :: {non_neg_integer, non_neg_integer}

  @type cell :: {coordinates, char}

  @enforce_keys ~w[grid width height]a
  defstruct @enforce_keys

  # List of coords that produce the 8 coordinates surrounding a given coord when added to it
  @all_adjacent_deltas for x <- -1..1, y <- -1..1, not (x == 0 and y == 0), do: {x, y}

  # List of coords that produce the 4 coordinates horizontally/vertically adjacent to a given coord when added to it
  @cardinal_adjacent_deltas for x <- -1..1, y <- -1..1, abs(x) + abs(y) == 1, do: {x, y}

  # List of coords that produce the 4 coordinates diagonally adjacent to a given coord when added to it
  @intercardinal_adjacent_deltas for x <- -1..1, y <- -1..1, abs(x) + abs(y) == 2, do: {x, y}

  @adjacency_deltas_by_type %{
    all: @all_adjacent_deltas,
    cardinal: @cardinal_adjacent_deltas,
    intercardinal: @intercardinal_adjacent_deltas
  }

  @spec from_input(String.t()) :: t()
  def from_input(input) do
    charlists =
      input
      |> String.split()
      |> Enum.map(&String.to_charlist/1)

    height = length(charlists)
    width = length(hd(charlists))

    grid =
      for {line, y} <- Enum.with_index(charlists),
          {char, x} <- Enum.with_index(line),
          into: %{} do
        {{x, y}, char}
      end

    %T{
      grid: grid,
      width: width,
      height: height
    }
  end

  @doc "Gets the value at the given coordinates."
  @spec at(t(), coordinates) :: char | nil
  def at(%T{} = t, coords) do
    t.grid[coords]
  end

  @doc """
  Returns a list of lists of cells in lines from the one at `coords`.
  Each list starts with the cell nearest `coords`, and radiates outward.

  The type of adjacency is determined by the third argument:

  - `:all` (default behavior):
    ```
    O.O.O
    .OOO.
    OO*OO
    .OOO.
    O.O.O
    ```
  - `:cardinal`:
    ```
    ..O..
    ..O..
    OO*OO
    ..O..
    ..O..
    ```
  - `:intercardinal`:
    ```
    O...O
    .O.O.
    ..*..
    .O.O.
    O...O
    ```
  """
  @spec lines_of_cells(t(), coordinates, adjacency_type) :: list(list(cell))
  def lines_of_cells(%T{} = t, coords, adjacency_type \\ :all) do
    @adjacency_deltas_by_type[adjacency_type]
    |> Enum.map(&get_line_of_cells(t, &1, sum_coordinates(coords, &1)))
  end

  @doc """
  Convenience function that behaves the same as `lines_of_cells/3`,
  but returns only the char value of each cell.
  """
  @spec lines_of_values(t(), coordinates, adjacency_type) :: list(list(char))
  def lines_of_values(%T{} = t, coords, adjacency_type \\ :all) do
    t
    |> lines_of_cells(coords, adjacency_type)
    |> Enum.map(fn line -> Enum.map(line, &elem(&1, 1)) end)
  end

  @doc """
  Convenience function that behaves the same as `lines_of_cells/3`,
  but returns only the coordinates of each cell.
  """
  @spec lines_of_coords(t(), coordinates, adjacency_type) :: list(list(coordinates))
  def lines_of_coords(%T{} = t, coords, adjacency_type \\ :all) do
    t
    |> lines_of_cells(coords, adjacency_type)
    |> Enum.map(fn line -> Enum.map(line, &elem(&1, 0)) end)
  end

  defp get_line_of_cells(t, step, coords) do
    case at(t, coords) do
      nil -> []
      val -> [{coords, val} | get_line_of_cells(t, step, sum_coordinates(coords, step))]
    end
  end

  defp sum_coordinates({x1, y1}, {x2, y2}), do: {x1 + x2, y1 + y2}
end

Edit: Made the solution cleaner (but slightly slower) by removing code that ignores the grid perimeter.

defmodule AdventOfCode.Solution.Year2022.Day08 do
  alias AdventOfCode.CharGrid

  def part1(input) do
    input
    |> parse_sight_lines_by_tree()
    |> Enum.count(&visible?/1)
  end

  def part2(input) do
    input
    |> parse_sight_lines_by_tree()
    |> Enum.map(&scenic_score/1)
    |> Enum.max()
  end

  defp parse_sight_lines_by_tree(input) do
    grid = CharGrid.from_input(input)

    grid
    |> CharGrid.to_list()
    |> Enum.map(fn {coords, tree} ->
      {tree, CharGrid.lines_of_values(grid, coords, :cardinal)}
    end)
  end

  defp visible?({tree, sight_lines}) do
    Enum.any?(sight_lines, fn other_trees ->
      Enum.all?(other_trees, &(&1 < tree))
    end)
  end

  defp scenic_score({tree, sight_lines}) do
    sight_lines
    |> Enum.map(&count_visible(&1, tree))
    |> Enum.product()
  end

  # A little tricky because we want to include the first tree that blocks our view.
  # All of the relevant `Enum` functions omit the first element that fails the condition,
  # so I needed to define my own recursive function.
  defp count_visible([], _), do: 0
  defp count_visible([tree | _trees], from_tree) when tree >= from_tree, do: 1
  defp count_visible([_tree | trees], from_tree), do: 1 + count_visible(trees, from_tree)
end

use std::env;
use std::io::{self, prelude::*, BufReader};
use std::fs::File;

const DIM: usize = 99; // Sample=5

fn visible_trees(tree_map: &Vec<Vec<u32>>) -> usize {
    let mut num_visible = 0;
    for y in 0..DIM {
        'srch: for x in 0..DIM {
            // Handle edges
            if x == 0 || y == 0 || x == DIM-1 || y == DIM-1 { num_visible += 1; continue 'srch; }
            let v = tree_map[x][y];
            // Scan -y
            let mut visible = true;
            'ym: for y0 in 0..y {
                if tree_map[x][y0] >= v { visible = false; break 'ym; }
            }
            if visible { num_visible += 1; continue 'srch; }
            // Scan +y
            let mut visible = true;
            'yp: for y0 in y+1..DIM {
                if tree_map[x][y0] >= v { visible = false; break 'yp; }
            }
            if visible { num_visible += 1; continue 'srch; }
            // Scan -x
            let mut visible = true;
            'xm: for x0 in 0..x {
                if tree_map[x0][y] >= v { visible = false; break 'xm; }
            }
            if visible { num_visible += 1; continue 'srch; }
            // Scan +x
            let mut visible = true;
            'xp: for x0 in x+1..DIM {
                if tree_map[x0][y] >= v { visible = false; break 'xp; }
            }
            if visible { num_visible += 1; continue 'srch; }
        }
    }
    num_visible
}

fn scenic_score(tree_map: &Vec<Vec<u32>>) -> usize {
    let mut max_scenic = 0;
    for y in 0..DIM {
        'srch: for x in 0..DIM {
            // Handle edges
            if x == 0 || y == 0 || x == DIM-1 || y == DIM-1 { continue 'srch; } // Zero scenic
            let v = tree_map[x][y];
            // Scan -y
            let mut dist_ym = 0;
            'ym: for y0 in (0..y).rev() {
                if tree_map[x][y0] <= v { dist_ym += 1; }
                if tree_map[x][y0] >= v { break 'ym; }
            }
            // Scan +y
            let mut dist_yp = 0;
            'yp: for y0 in y+1..DIM {
                if tree_map[x][y0] <= v { dist_yp += 1; }
                if tree_map[x][y0] >= v { break 'yp; }
            }
            // Scan -x
            let mut dist_xm = 0;
            'xm: for x0 in (0..x).rev() {
                if tree_map[x0][y] <= v { dist_xm += 1; }
                if tree_map[x0][y] >= v { break 'xm; }
            }
            // Scan +x
            let mut dist_xp = 0;
            'xp: for x0 in x+1..DIM {
                if tree_map[x0][y] <= v { dist_xp += 1; }
                if tree_map[x0][y] >= v { break 'xp; }
            }
            max_scenic = std::cmp::max(max_scenic, dist_ym * dist_yp * dist_xp * dist_xm);
        }
    }
    max_scenic
}

fn solve(input: &str) -> io::Result<()> {
    let file = File::open(input).expect("Input file not found.");
    let reader = BufReader::new(file);

    // Input
    let input: Vec<String> = match reader.lines().collect() {
        Err(err) => panic!("Unknown error reading input: {}", err),
        Ok(result) => result,
    };

    // Build tree map
    let mut tree_map = vec![vec![0; DIM]; DIM];
    for (y,line) in input.iter().enumerate() {
        for (x,c) in line.chars().enumerate() {
            tree_map[x][y] = c.to_digit(10).unwrap();
        }
    }

    // Outputs
    println!("Part 1: {}",visible_trees(&tree_map)); // 1693
    println!("Part 2: {}",scenic_score(&tree_map)); // 422059

    Ok(())
}

fn main() {
    let args: Vec<String> = env::args().collect();
    let filename = &args[1];
    solve(&filename).unwrap();
}

Tree = namedtuple("Tree", ["height", "visible"])


def process_grid(lines: List[str]) -> List[List[Tree]]:

    return [[Tree(int(height), False) for height in line] for line in lines]


def determine_visible(grid: List[List[Tree]]):

    # Left to right
    for row_idx in range(len(grid)):
        max_height: int = -1
        for col_idx in range(len(grid[row_idx])):
            if grid[row_idx][col_idx].height > max_height:
                max_height = grid[row_idx][col_idx].height
                grid[row_idx][col_idx] = grid[row_idx][col_idx]._replace(visible=True)

    # Right to left
    for row_idx in range(len(grid)):
        max_height = -1
        for col_idx in range(len(grid[row_idx]) - 1, -1, -1):
            if grid[row_idx][col_idx].height > max_height:
                max_height = grid[row_idx][col_idx].height
                grid[row_idx][col_idx] = grid[row_idx][col_idx]._replace(visible=True)

    # top to bottom
    for row_idx in range(len(grid)):
        max_height = -1
        for col_idx in range(len(grid[row_idx])):
            if grid[col_idx][row_idx].height > max_height:
                max_height = grid[col_idx][row_idx].height
                grid[col_idx][row_idx] = grid[col_idx][row_idx]._replace(visible=True)

    # bottom to top
    for row_idx in range(len(grid)):
        max_height = -1
        for col_idx in range(len(grid[row_idx]) - 1, -1, -1):
            if grid[col_idx][row_idx].height > max_height:
                max_height = grid[col_idx][row_idx].height
                grid[col_idx][row_idx] = grid[col_idx][row_idx]._replace(visible=True)


def viewing_score(grid: List[List[Tree]], row: int, col: int) -> int:

    curr_tree = grid[row][col]

    up = 0
    for row_idx in range(row - 1, -1, -1):
        if grid[row_idx][col].height >= curr_tree.height:
            up += 1
            break
        up += 1

    down = 0
    for row_idx in range(row + 1, len(grid)):
        if grid[row_idx][col].height >= curr_tree.height:
            down += 1
            break
        down += 1

    left = 0
    for col_idx in range(col - 1, -1, -1):
        if grid[row][col_idx].height >= curr_tree.height:
            left += 1
            break
        left += 1

    right = 0
    for col_idx in range(col + 1, len(grid[row])):
        if grid[row][col_idx].height >= curr_tree.height:
            right += 1
            break
        right += 1

    return up * down * left * right


def main(filepath: str) -> Tuple[int, int]:

    unprocessed_grid = load_file.load_cleaned_lines(filepath)
    grid = process_grid(unprocessed_grid)
    determine_visible(grid)

    return (
        sum((tree.visible for row in grid for tree in row)),
        max(
            (
                viewing_score(grid, row_idx, col_idx)
                for row_idx, row in enumerate(grid)
                for col_idx, tree in enumerate(row)
            )
        ),
    )

#!/usr/bin/awk -f
BEGIN { FS = "" }

{
	for (x = 1; x <= NF; ++x)
		grid[x, NR] = $x
}

END {
	X = length($0)
	Y = NR

	for (x = 1; x <= X; ++x) {
		i = -1
		for (y = 1; y <= Y; ++y) {
			if (grid[x, y] < i)
				continue
			if (grid[x, y] > i)
				visible[x, y] = 1
			i = grid[x, y]
		}
	}

	for (x = 1; x <= X; ++x) {
		i = -1
		for (y = Y; y >= 1; --y) {
			if (grid[x, y] < i)
				continue
			if (grid[x, y] > i)
				visible[x, y] = 1
			i = grid[x, y]
		}
	}

	for (y = 1; y <= Y; ++y) {
		i = -1
		for (x = 1; x <= X; ++x) {
			if (grid[x, y] < i)
				continue
			if (grid[x, y] > i)
				visible[x, y] = 1
			i = grid[x, y]
		}
	}

	for (y = 1; y <= Y; ++y) {
		i = -1
		for (x = X; x >= 1; --x) {
			if (grid[x, y] < i)
				continue
			if (grid[x, y] > i)
				visible[x, y] = 1
			i = grid[x, y]
		}
	}

	for (i in visible)
		sum += 1

	print(sum)
}

#!/usr/bin/awk -f
function sight(x, y, _x, _y, X, Y,	i, sum) {
	i = grid[x, y]
	sum = 0

	do {
		x += _x
		do {
			y += _y
			if (grid[x, y] != "") {
				sum += 1
				if (grid[x, y] >= i)
					return sum
			}
		} while (y != Y)
	} while (x != X)

	return sum
}

BEGIN { FS = "" }

{
	for (x = 1; x <= NF; ++x)
		grid[x, NR] = $x
}

END {
	X = length($0)
	Y = NR

	for (x = 1; x <= X; ++x)
		for (y = 1; y <= Y; ++y) {
			score = sight(x, y, 0, -1, x, 1-1) * \
				 sight(x, y, 0, +1, x, Y+1) * \
				 sight(x, y, -1, 0, 1-1, y) * \
				 sight(x, y, +1, 0, X+1, y)

			if (score > max)
				max = score
		}

	print(max)
}

My forest is a nested list.

(define (read-forest input)
  (for/list ([l (in-list input)])
    (map char->digit (string->list l))))

(define (char->digit c)
  (- (char->integer c) 48))

• Visibile trees increase monotonically.
  • Iterate through a list of trees, keeping a note of the tallest tree so far.
  • Each tree taller than the tallest is marked visible - #t, noting the new tallest tree.
• Horizontal visibility
  • Trees visible from the left are monotonically increasing (described above)
  • Trees visible from the right are identical after reversing the list.
  • Combine those using logical OR
• Vertical visibility is identical using a transposed forest.
• Combine horizontal and vertical visibility again with logical OR

Old lispers know a neat to tranpose nested lists: (apply map list xs))
Happy to explain it if anyone asks.

(define (part-01 input)
  (define d (read-forest input))
  (define d* (transpose d))
  (define left/right (map visibility d))
  (define up/down (transpose (map visibility d*)))
  (for/sum ([row (in-list left/right)]
            [col (in-list up/down)])
    (count identity (combine-visibile row col))))

(define (transpose xs)
  (apply map list xs))

;; #t for each tree visible (from either end)
(define (visibility trees)
  (combine-visibile (reverse (monotonic trees))
          (monotonic (reverse trees))))

(define (combine-visibile a b)
  (for/list ([l (in-list a)]
             [r (in-list b)])
    (or l r)))

;; #t for each value in the list that is monotonically increasing
;;  1  2  5  3  0  6
;; #t #t #t #f #f #t
(define (monotonic trees)
  (for/fold ([visible null]
             [tallest -1]
             #:result visible)
            ([t (in-list trees)])
    (cond [(> t tallest) (values (cons #t visible) t)]
          [else (values (cons #f visible) tallest)])))

Part 2 is a similar approach, tranposing the forest, but it was easier to find the viewing distance by converting to a vector.

(define (part-02 input)
  (define d (read-forest input))
  (define d* (transpose d))
  (define left/right (map scenic-score d))
  (define up/down (transpose (map scenic-score d*)))
  (for/fold ([hut 0])
            ([row (in-list left/right)]
             [col (in-list up/down)])
    (apply max hut (map * row col))))

(define (scenic-score trees)
  (define v (list->vector trees))
  (define left  (viewing-distances v look-left))
  (define right (viewing-distances v look-right))
  (map * left right))

(define (viewing-distances trees f)
  (for/fold ([counts null]
             #:result (reverse counts))
            ([i (in-range (vector-length trees))])
    (cons (f trees i) counts)))

(define (look-right trees i) (scan-with trees i add1 (vector-length tv)))
(define (look-left  tress i) (scan-with trees i sub1 -1))

(define (scan-with trees i next stop)
  (define (scan hut j total)
    (cond [(= j stop) total]
          [(>= (vector-ref tv j) hut) (add1 total)]
          [else (scan hut (next j) (add1 total))]))
  (scan (vector-ref trees i) (next i) 0))

def is_visible?(x, y)
  
  tree = $map[y][x]
  up    = (0...y).map{ |i| $map[i][x] }
  right = (x+1...$map.first.size).map{ |i| $map[y][i] }
  down  = (y+1...$map.size).map{ |i| $map[i][x] }
  left  = (0...x).map{ |i| $map[y][i] }
  
  up.all?{ |e| e < tree } ||
  right.all?{ |e| e < tree } ||
  down.all?{ |e| e < tree } ||
  left.all?{ |e| e < tree } ||
  x == 0 || y == 0 ||
  x == $map.first.size-1 ||
  y == $map.size-1
end

$map = File
      .read("input.txt")
      .split
      .map{ |x| x.chars.map(&:to_i) }

p (0...$map.size*$map.first.size)
    .count { |i| is_visible?(i%$map.first.size, i/$map.size) }