Dart

I’m cheating a bit by posting this as it does take 11s for the full part 2 solution, but having tracked down and eliminated the excessively long path for part 1, I can’t be bothered to do it again for part 2.

I’m an idiot. Avoiding recursively adding the same points to the seen set dropped total runtime to a hair under 0.5s, so line-seconds are around 35.

Map, Set>> seen = {};

Map fire(List> grid, Point here, Point dir) {
  seen = {};
  return _fire(grid, here, dir);
}

Map, Set>> _fire(
    List> grid, Point here, Point dir) {
  while (true) {
    here += dir;
    if (!here.x.between(0, grid.first.length - 1) ||
        !here.y.between(0, grid.length - 1)) {
      return seen;
    }
    if (seen[here]?.contains(dir) ?? false) return seen;
    seen[here] = (seen[here] ?? >{})..add(dir);

    Point split() {
      _fire(grid, here, Point(-dir.y, -dir.x));
      return Point(dir.y, dir.x);
    }

    dir = switch (grid[here.y][here.x]) {
      '/' => Point(-dir.y, -dir.x),
      r'\' => Point(dir.y, dir.x),
      '|' => (dir.x.abs() == 1) ? split() : dir,
      '-' => (dir.y.abs() == 1) ? split() : dir,
      _ => dir,
    };
  }
}

parse(List lines) => lines.map((e) => e.split('').toList()).toList();

part1(List lines) =>
    fire(parse(lines), Point(-1, 0), Point(1, 0)).length;

part2(List lines) {
  var grid = parse(lines);
  var ret = 0.to(grid.length).fold(
      0,
      (s, t) => [
            s,
            fire(grid, Point(-1, t), Point(1, 0)).length,
            fire(grid, Point(grid.first.length, t), Point(-1, 0)).length
          ].max);
  return 0.to(grid.first.length).fold(
      ret,
      (s, t) => [
            s,
            fire(grid, Point(t, -1), Point(0, 1)).length,
            fire(grid, Point(t, grid.length), Point(0, -1)).length
          ].max);
}

That’s why I normally let computers do my sums for me. Corrected now.

Dart

Just written as specced. If there’s any underlying trick, I missed it totally.

9ms * 35 LOC ~= 0.35, so it’ll do.

int decode(String s) => s.codeUnits.fold(0, (s, t) => ((s + t) * 17) % 256);

part1(List lines) => lines.first.split(',').map(decode).sum;

part2(List lines) {
  var rules = lines.first.split(',').map((e) {
    if (e.contains('-')) return ('-', e.skipLast(1), 0);
    var parts = e.split('=');
    return ('=', parts.first, int.parse(parts.last));
  });
  var boxes = Map.fromEntries(List.generate(256, (ix) => MapEntry(ix, [])));
  for (var r in rules) {
    if (r.$1 == '-') {
      boxes[decode(r.$2)]!.removeWhere((l) => l.$1 == r.$2);
    } else {
      var box = boxes[decode(r.$2)]!;
      var lens = box.indexed().firstWhereOrNull((e) => e.value.$1 == r.$2);
      var newlens = (r.$2, r.$3);
      (lens == null) ? box.add(newlens) : box[lens.index] = newlens;
    }
  }
  return boxes.entries
      .map((b) =>
          (b.key + 1) *
          b.value.indexed().map((e) => (e.index + 1) * e.value.$2).sum)
      .sum;
}

Dart

Big lump of code. I built a general slide function which ended up being tricksy in order to visit rocks in the correct order, but it works.

int hash(List> rocks) =>
    (rocks.map((e) => e.join('')).join('\n')).hashCode;

/// Slide rocks in the given (vert, horz) direction.
List> slide(List> rocks, (int, int) dir) {
  // Work out in which order to check rocks for most efficient movement.
  var rrange = 0.to(rocks.length);
  var crange = 0.to(rocks.first.length);
  var starts = [
    for (var r in (dir.$1 == 1) ? rrange.reversed : rrange)
      for (var c in ((dir.$2 == 1) ? crange.reversed : crange)
          .where((c) => rocks[r][c] == 'O'))
        (r, c)
  ];

  for (var (r, c) in starts) {
    var dest = (r, c);
    var next = (dest.$1 + dir.$1, dest.$2 + dir.$2);
    while (next.$1.between(0, rocks.length - 1) &&
        next.$2.between(0, rocks.first.length - 1) &&
        rocks[next.$1][next.$2] == '.') {
      dest = next;
      next = (dest.$1 + dir.$1, dest.$2 + dir.$2);
    }
    if (dest != (r, c)) {
      rocks[r][c] = '.';
      rocks[dest.$1][dest.$2] = 'O';
    }
  }
  return rocks;
}

List> oneCycle(List> rocks) =>
    [(-1, 0), (0, -1), (1, 0), (0, 1)].fold(rocks, (s, t) => slide(s, t));

spin(List> rocks, {int target = 1}) {
  var cycle = 1;
  var seen = {};
  while (cycle != target) {
    rocks = oneCycle(rocks);
    var h = hash(rocks);
    if (seen.containsKey(h)) {
      var diff = cycle - seen[h]!;
      var count = (target - cycle) ~/ diff;
      cycle += count * diff;
      seen = {};
    } else {
      seen[h] = cycle;
      cycle += 1;
    }
  }
  return weighting(rocks);
}

parse(List lines) => lines.map((e) => e.split('').toList()).toList();

weighting(List> rocks) => 0
    .to(rocks.length)
    .map((r) => rocks[r].count((e) => e == 'O') * (rocks.length - r))
    .sum;

part1(List lines) => weighting(slide(parse(lines), (-1, 0)));

part2(List lines) => spin(parse(lines), target: 1000000000);

Dart

Just banging strings together again. Simple enough once I understood that the original reflection may also be valid after desmudging. I don’t know if we were supposed to do something clever for part two, but my part 1 was fast enough that I could just try every possible smudge location and part 2 still ran in 80ms

bool reflectsH(int m, List p) => p.every((l) {
      var l1 = l.take(m).toList().reversed.join('');
      var l2 = l.skip(m);
      var len = min(l1.length, l2.length);
      return l1.take(len) == l2.take(len);
    });

bool reflectsV(int m, List p) {
  var l1 = p.take(m).toList().reversed.toList();
  var l2 = p.skip(m).toList();
  var len = min(l1.length, l2.length);
  return 0.to(len).every((ix) => l1[ix] == l2[ix]);
}

int findReflection(List p, {int butNot = -1}) {
  var mirrors = 1
      .to(p.first.length)
      .where((m) => reflectsH(m, p))
      .toSet()
      .difference({butNot});
  if (mirrors.length == 1) return mirrors.first;

  mirrors = 1
      .to(p.length)
      .where((m) => reflectsV(m, p))
      .toSet()
      .difference({butNot ~/ 100});
  if (mirrors.length == 1) return 100 * mirrors.first;

  return -1; //never
}

int findSecondReflection(List p) {
  var origMatch = findReflection(p);
  for (var r in 0.to(p.length)) {
    for (var c in 0.to(p.first.length)) {
      var pp = p.toList();
      var cells = pp[r].split('');
      cells[c] = (cells[c] == '#') ? '.' : '#';
      pp[r] = cells.join();
      var newMatch = findReflection(pp, butNot: origMatch);
      if (newMatch > -1) return newMatch;
    }
  }
  return -1; // never
}

Iterable> parse(List lines) => lines
    .splitBefore((e) => e.isEmpty)
    .map((e) => e.first.isEmpty ? e.skip(1).toList() : e);

part1(lines) => parse(lines).map(findReflection).sum;

part2(lines) => parse(lines).map(findSecondReflection).sum;

Imagine you’re looking at a grid with your path drawn out on it. On any given row, start from the left and move right, cell by cell. You’re outside the area enclosed by your path at the start of the row. As you move across that row, you remain outside it until you meet and cross the line made by your path. Every non-path cell you now pass can be added to your ‘inside’ count, until you next cross your path, when you stop counting until you cross the path again, and so on.

In this problem, you can tell you’re crossing the path when you encounter one of:

• a ‘|’
• a ‘F’ (followed by 0 or more '-'s) followed by ‘J’
• a ‘L’ (followed by 0 or more '-'s) followed by ‘7’

If you encounter an ‘F’ (followed by 0 or more '-'s) followed by ‘7’, you’ve actually just skimmed along the line and not actually crossed it. Same for the ‘L’/ ‘J’ pair.

Try it out by hand on the example grids and you should get the hang of the logic.

Uiua

As promised, just a little later than planned. I do like this solution as it’s actually using arrays rather than just imperative programming in fancy dress. Run it here

Grid ← =@# [
  "...#......"
  ".......#.."
  "#........."
  ".........."
  "......#..."
  ".#........"
  ".........#"
  ".........."
  ".......#.."
  "#...#....."
]

GetDist! ← (
  # Build arrays of rows, cols of galaxies
  ⊙(⊃(◿)(⌊÷)⊃(⧻⊢)(⊚=1/⊂)).
  # check whether each row/col is just space
  # and so calculate its relative position
  ∩(\++1^1=0/+)⍉.
  # Map galaxy co-ords to these values
  ⊏:⊙(:⊏ :)
  # Map to [x, y] pairs, build cross product, 
  # and sum all topright values.
  /+≡(/+↘⊗0.)⊠(/+⌵-).⍉⊟
)
GetDist!(×1) Grid
GetDist!(×99) Grid

There is a really simple approach that I describe in my comment on the megathread, but it’s always good to have a nice visualisation so thanks for sharing!

Dart

Terrible monkey-coding approach of banging strings together and counting the resulting shards. Just kept to a reasonable 300ms runtime by a bit of memoisation of results. I’m sure this can all be replaced by a single line of clever combinatorial wizardry.

var __countMatches = {};
int _countMatches(String pattern, List counts) =>
    __countMatches.putIfAbsent(
        pattern + counts.toString(), () => countMatches(pattern, counts));

int countMatches(String pattern, List counts) {
  if (!pattern.contains('#') && counts.isEmpty) return 1;
  if (pattern.startsWith('..')) return _countMatches(pattern.skip(1), counts);
  if (pattern == '.' || counts.isEmpty) return 0;

  var thisShape = counts.first;
  var minSpaceForRest =
      counts.length == 1 ? 0 : counts.skip(1).sum + counts.skip(1).length + 1;
  var lastStart = pattern.length - minSpaceForRest - thisShape;
  if (lastStart < 1) return 0;

  var total = 0;
  for (var start in 1.to(lastStart + 1)) {
    // Skipped a required spring. Bad, and will be for all successors.
    if (pattern.take(start).contains('#')) break;
    // Includes a required separator. Also bad.
    if (pattern.skip(start).take(thisShape).contains('.')) continue;
    var rest = pattern.skip(start + thisShape);
    if (rest.startsWith('#')) continue;
    // force '.' or '?' to be '.' and count matches.
    total += _countMatches('.${rest.skip(1)}', counts.skip(1).toList());
  }
  return total;
}

solve(List lines, {stretch = 1}) {
  var ret = [];
  for (var line in lines) {
    var ps = line.split(' ');
    var pattern = List.filled(stretch, ps.first).join('?');
    var counts = List.filled(stretch, ps.last)
        .join(',')
        .split(',')
        .map(int.parse)
        .toList();
     ret.add(countMatches('.$pattern.', counts)); // top and tail.
  }
  return ret.sum;
}

part1(List lines) => solve(lines);

part2(List lines) => solve(lines, stretch: 5);

Dart

Finally got round to solving part 2. Very easy once I realised it’s just a matter of counting line crossings.

Edit: having now read the other comments here, I’m reminded that the line-crossing logic is actually an application of Jordan’s Curve Theorem which looks like a mathematical joke when you first see it, but turns out to be really useful here!

var up = Point(0, -1),
    down = Point(0, 1),
    left = Point(-1, 0),
    right = Point(1, 0);
var pipes = >>{
  '|': [up, down],
  '-': [left, right],
  'L': [up, right],
  'J': [up, left],
  '7': [left, down],
  'F': [right, down],
};
late List> grid; // Make grid global for part 2
Set> buildPath(List lines) {
  grid = lines.map((e) => e.split('')).toList();
  var points = {
    for (var row in grid.indices())
      for (var col in grid.first.indices()) Point(col, row): grid[row][col]
  };
  // Find the starting point.
  var pos = points.entries.firstWhere((e) => e.value == 'S').key;
  var path = {pos};
  // Replace 'S' with assumed pipe.
  var dirs = [up, down, left, right].where((el) =>
      points.keys.contains(pos + el) &&
      pipes.containsKey(points[pos + el]) &&
      pipes[points[pos + el]]!.contains(Point(-el.x, -el.y)));
  grid[pos.y][pos.x] = pipes.entries
      .firstWhere((e) =>
          (e.value.first == dirs.first) && (e.value.last == dirs.last) ||
          (e.value.first == dirs.last) && (e.value.last == dirs.first))
      .key;

  // Follow the path.
  while (true) {
    var nd = dirs.firstWhereOrNull((e) =>
        points.containsKey(pos + e) &&
        !path.contains(pos + e) &&
        (points[pos + e] == 'S' || pipes.containsKey(points[pos + e])));
    if (nd == null) break;
    pos += nd;
    path.add(pos);
    dirs = pipes[points[pos]]!;
  }
  return path;
}

part1(List lines) => buildPath(lines).length ~/ 2;
part2(List lines) {
  var path = buildPath(lines);
  var count = 0;
  for (var r in grid.indices()) {
    var outside = true;
    // We're only interested in how many times we have crossed the path
    // to get to any given point, so mark anything that's not on the path
    // as '*' for counting, and collapse all uninteresting path segments.
    var row = grid[r]
        .indexed()
        .map((e) => path.contains(Point(e.index, r)) ? e.value : '*')
        .join('')
        .replaceAll('-', '')
        .replaceAll('FJ', '|') // zigzag
        .replaceAll('L7', '|') // other zigzag
        .replaceAll('LJ', '') // U-bend
        .replaceAll('F7', ''); // n-bend
    for (var c in row.split('')) {
      if (c == '|') {
        outside = !outside;
      } else {
        if (!outside && c == '*') count += 1;
      }
    }
  }
  return count;
}

I’m not sure that this link really helps your case, given these key points from the description:

The resolution by the British representative, Ambassador Sir Anthony Parsons

demanded an immediate cessation of hostilities between Argentina and the United Kingdom and a complete withdrawal by Argentine forces

Resolution 502 was in the United Kingdom’s favour by giving it the option to invoke Article 51 of the United Nations Charter and to claim the right of self-defence

he likes to larp in the words of a better man

That’s such a great description of this kind of tech-bro behaviour.

True. I’m certainly at the point where quick jobs that I would have once done in Python quite often get done in Dart instead, avoiding the “context switch” of having to think in Python for that one task.

Yes, when I did a search, I found I had a choice between two quite small and inactive communities, so I went for the slightly larger one. I’ll crosspost today’s post to that community see if it stirs up any more interest.

Yes, I really adopted it due to Flutter, but the dev team really are doing great work to make it a nice language, especially with version 3.

Oof. I got about 65% on the images I hadn’t seen in the post. I must be pretty close to being replaceable by an adversarial network.

Really, radio communication is about creating and transmitting those radio waves. Sign language relies on reflected light waves so it’s actually a form of RADAR 😀

What, this Emad Mostaque?

The AI Founder Taking Credit For Stable Diffusion’s Success Has A History Of Exaggeration

Since light bounces off walls and is thus confined to individual rooms, there is less interference and higher bandwidth, and traffic is harder to intercept from outside.

He must be another new Lemmy user dusting off his old memes.