AOC2022 day08

main.dart

/// Given a grid of (real) trees of different heights
/// 1) Find how many are visible from any edge
/// 2) Find the best view from any trees (= product of distances)
/// https://dartpad.dev/?id=a2f73b120ad6620d14ff769d54c71efd

import 'dart:math';

extension IntegerRangeExtension on int {
  List<int> to(int end, {int step = 1}) =>
      List.generate((end - this + (step - 1)) ~/ step, (i) => i * step + this);
}

class Index {
  final int r;
  final int c;

  const Index(this.r, this.c);

  Index operator +(Index other) => Index(r + other.r, c + other.c);
}

class ListGrid<T> {
  late final List<List<T>> _list;
  static const n4 = [Index(-1, 0), Index(1, 0), Index(0, -1), Index(0, 1)];

  /// Use the supplied list -- DESTRUCTIVE!
  ListGrid(List<List<T>> list) : _list = list;

  /// Create an empty grid of the required size, prefilled with `value`.
  ListGrid.ofSize(rows, columns, T value)
      : _list =
            List.generate(rows, (r) => List.generate(columns, (c) => value));

  int get width => _list.first.length;
  int get height => _list.length;

  bool isInBounds(Index n) =>
      n.r >= 0 && n.r < height && n.c >= 0 && n.c < width;

  put(Index p, T value) => _list[p.r][p.c] = value;

  T operator [](Index p) => _list[p.r][p.c];

  operator []=(Index p, T value) => _list[p.r][p.c] = value;

  Iterable<Index> get indexes sync* {
    for (int r in 0.to(height)) {
      for (int c in 0.to(width)) {
        yield Index(r, c);
      }
    }
  }
}

ListGrid<int> readTrees(List<String> lines) {
  var treeGrid = ListGrid<int>.ofSize(lines.length, lines.first.length, 0);
  for (var row in 0.to(treeGrid.height)) {
    for (var col in 0.to(treeGrid.width)) {
      treeGrid.put(
          Index(row, col), int.parse(lines[row].substring(col, col + 1)));
    }
  }
  return treeGrid;
}

part1(List<String> lines) {
  var treeGrid = readTrees(lines);
  var seenGrid = ListGrid<bool>.ofSize(lines.length, lines.first.length, false);

  // helper function
  int markVisibleTrees(tallest, row, col) {
    if (treeGrid[Index(row, col)] > tallest) {
      seenGrid[Index(row, col)] = true;
      tallest = treeGrid[Index(row, col)];
    }
    return tallest;
  }

  for (var row in 0.to(treeGrid.height)) {
    0.to(treeGrid.width).fold(-1, (s, t) => markVisibleTrees(s, row, t));
    0
        .to(treeGrid.width)
        .reversed
        .fold(-1, (s, t) => markVisibleTrees(s, row, t));
  }
  for (var col in 0.to(treeGrid.width)) {
    0.to(treeGrid.height).fold(-1, (s, t) => markVisibleTrees(s, t, col));
    0
        .to(treeGrid.height)
        .reversed
        .fold(-1, (s, t) => markVisibleTrees(s, t, col));
  }
  return seenGrid.indexes
      .map((e) => seenGrid[e])
      .where((e) => e == true)
      .length;
}

List<int> viewsFromTree(ListGrid<int> treeGrid, Index ix) {
  var high = treeGrid[ix];
  var vals = <int>[];
  for (var dir in ListGrid.n4) {
    var here = ix;
    var val = 0;
    while (true) {
      here += dir;
      if (!treeGrid.isInBounds(here)) break;
      val += 1;
      if (treeGrid[here] >= high) break;
    }
    vals.add(val);
  }
  return vals;
}

part2(List<String> lines) {
  var treeGrid = readTrees(lines);
  return readTrees(lines).indexes.fold(
      -1, (s, t) => max(s, viewsFromTree(treeGrid, t).reduce((s, t) => s * t)));
}

var testdata = r"""30373
25512
65332
33549
35390"""
    .split('\n');

void main(List<String> args) {
  var dt = DateTime.now();
  assert(part1(testdata) == 21);
  assert(part2(testdata) == 8);
  var rt = DateTime.now().difference(dt).inMilliseconds;
  print('tests succeeded in $rt ms');
}