mykl

mykl, 4 months ago

We stayed in Sheerness (where this flight took place), and when my girlfriend saw this she immediately asked “Did pigs fly before women did?”. And the answer turned out to be no, women beat pigs by two weeks: “Sarah Van Deman … was the woman who flew with Wilbur Wright on October 27, 1909” source

mykl, 4 months ago

What does “zoomed in to check which colour they re-used in the second chart so didn’t even realise there was a third one” count as?

mykl, 5 months ago

Isn’t every video game just moving colourful blocks?

(Except Quake obviously)

mykl, 5 months ago

i_understood_that_reference.jif

mykl, 5 months ago

Dad mode activated

mykl, 5 months ago (edited 5 months ago)

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.

<span style="color:#323232;">Map, Set>> seen = {};
</span><span style="color:#323232;">
</span><span style="color:#323232;">Map fire(List> grid, Point here, Point dir) {
</span><span style="color:#323232;">  seen = {};
</span><span style="color:#323232;">  return _fire(grid, here, dir);
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="color:#323232;">Map, Set>> _fire(
</span><span style="color:#323232;">    List> grid, Point here, Point dir) {
</span><span style="color:#323232;">  while (true) {
</span><span style="color:#323232;">    here += dir;
</span><span style="color:#323232;">    if (!here.x.between(0, grid.first.length - 1) ||
</span><span style="color:#323232;">        !here.y.between(0, grid.length - 1)) {
</span><span style="color:#323232;">      return seen;
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">    if (seen[here]?.contains(dir) ?? false) return seen;
</span><span style="color:#323232;">    seen[here] = (seen[here] ?? >{})..add(dir);
</span><span style="color:#323232;">
</span><span style="color:#323232;">    Point split() {
</span><span style="color:#323232;">      _fire(grid, here, Point(-dir.y, -dir.x));
</span><span style="color:#323232;">      return Point(dir.y, dir.x);
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">
</span><span style="color:#323232;">    dir = switch (grid[here.y][here.x]) {
</span><span style="color:#323232;">      '/' => Point(-dir.y, -dir.x),
</span><span style="color:#323232;">      r'' => Point(dir.y, dir.x),
</span><span style="color:#323232;">      '|' => (dir.x.abs() == 1) ? split() : dir,
</span><span style="color:#323232;">      '-' => (dir.y.abs() == 1) ? split() : dir,
</span><span style="color:#323232;">      _ => dir,
</span><span style="color:#323232;">    };
</span><span style="color:#323232;">  }
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="color:#323232;">parse(List lines) => lines.map((e) => e.split('').toList()).toList();
</span><span style="color:#323232;">
</span><span style="color:#323232;">part1(List lines) =>
</span><span style="color:#323232;">    fire(parse(lines), Point(-1, 0), Point(1, 0)).length;
</span><span style="color:#323232;">
</span><span style="color:#323232;">part2(List lines) {
</span><span style="color:#323232;">  var grid = parse(lines);
</span><span style="color:#323232;">  var ret = 0.to(grid.length).fold(
</span><span style="color:#323232;">      0,
</span><span style="color:#323232;">      (s, t) => [
</span><span style="color:#323232;">            s,
</span><span style="color:#323232;">            fire(grid, Point(-1, t), Point(1, 0)).length,
</span><span style="color:#323232;">            fire(grid, Point(grid.first.length, t), Point(-1, 0)).length
</span><span style="color:#323232;">          ].max);
</span><span style="color:#323232;">  return 0.to(grid.first.length).fold(
</span><span style="color:#323232;">      ret,
</span><span style="color:#323232;">      (s, t) => [
</span><span style="color:#323232;">            s,
</span><span style="color:#323232;">            fire(grid, Point(t, -1), Point(0, 1)).length,
</span><span style="color:#323232;">            fire(grid, Point(t, grid.length), Point(0, -1)).length
</span><span style="color:#323232;">          ].max);
</span><span style="color:#323232;">}
</span>

mykl, 5 months ago (edited 5 months ago)

Dart

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

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

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

mykl, 5 months ago

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

mykl, 5 months ago (edited 5 months ago)

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.

<span style="color:#323232;">int hash(List> rocks) =>
</span><span style="color:#323232;">    (rocks.map((e) => e.join('')).join('n')).hashCode;
</span><span style="color:#323232;">
</span><span style="color:#323232;">/// Slide rocks in the given (vert, horz) direction.
</span><span style="color:#323232;">List> slide(List> rocks, (int, int) dir) {
</span><span style="color:#323232;">  // Work out in which order to check rocks for most efficient movement.
</span><span style="color:#323232;">  var rrange = 0.to(rocks.length);
</span><span style="color:#323232;">  var crange = 0.to(rocks.first.length);
</span><span style="color:#323232;">  var starts = [
</span><span style="color:#323232;">    for (var r in (dir.$1 == 1) ? rrange.reversed : rrange)
</span><span style="color:#323232;">      for (var c in ((dir.$2 == 1) ? crange.reversed : crange)
</span><span style="color:#323232;">          .where((c) => rocks[r][c] == 'O'))
</span><span style="color:#323232;">        (r, c)
</span><span style="color:#323232;">  ];
</span><span style="color:#323232;">
</span><span style="color:#323232;">  for (var (r, c) in starts) {
</span><span style="color:#323232;">    var dest = (r, c);
</span><span style="color:#323232;">    var next = (dest.$1 + dir.$1, dest.$2 + dir.$2);
</span><span style="color:#323232;">    while (next.$1.between(0, rocks.length - 1) &amp;&amp;
</span><span style="color:#323232;">        next.$2.between(0, rocks.first.length - 1) &amp;&amp;
</span><span style="color:#323232;">        rocks[next.$1][next.$2] == '.') {
</span><span style="color:#323232;">      dest = next;
</span><span style="color:#323232;">      next = (dest.$1 + dir.$1, dest.$2 + dir.$2);
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">    if (dest != (r, c)) {
</span><span style="color:#323232;">      rocks[r][c] = '.';
</span><span style="color:#323232;">      rocks[dest.$1][dest.$2] = 'O';
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">  }
</span><span style="color:#323232;">  return rocks;
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="color:#323232;">List> oneCycle(List> rocks) =>
</span><span style="color:#323232;">    [(-1, 0), (0, -1), (1, 0), (0, 1)].fold(rocks, (s, t) => slide(s, t));
</span><span style="color:#323232;">
</span><span style="color:#323232;">spin(List> rocks, {int target = 1}) {
</span><span style="color:#323232;">  var cycle = 1;
</span><span style="color:#323232;">  var seen = {};
</span><span style="color:#323232;">  while (cycle != target) {
</span><span style="color:#323232;">    rocks = oneCycle(rocks);
</span><span style="color:#323232;">    var h = hash(rocks);
</span><span style="color:#323232;">    if (seen.containsKey(h)) {
</span><span style="color:#323232;">      var diff = cycle - seen[h]!;
</span><span style="color:#323232;">      var count = (target - cycle) ~/ diff;
</span><span style="color:#323232;">      cycle += count * diff;
</span><span style="color:#323232;">      seen = {};
</span><span style="color:#323232;">    } else {
</span><span style="color:#323232;">      seen[h] = cycle;
</span><span style="color:#323232;">      cycle += 1;
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">  }
</span><span style="color:#323232;">  return weighting(rocks);
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="color:#323232;">parse(List lines) => lines.map((e) => e.split('').toList()).toList();
</span><span style="color:#323232;">
</span><span style="color:#323232;">weighting(List> rocks) => 0
</span><span style="color:#323232;">    .to(rocks.length)
</span><span style="color:#323232;">    .map((r) => rocks[r].count((e) => e == 'O') * (rocks.length - r))
</span><span style="color:#323232;">    .sum;
</span><span style="color:#323232;">
</span><span style="color:#323232;">part1(List lines) => weighting(slide(parse(lines), (-1, 0)));
</span><span style="color:#323232;">
</span><span style="color:#323232;">part2(List lines) => spin(parse(lines), target: 1000000000);
</span>

mykl, 5 months ago

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

<span style="color:#323232;">bool reflectsH(int m, List p) => p.every((l) {
</span><span style="color:#323232;">      var l1 = l.take(m).toList().reversed.join('');
</span><span style="color:#323232;">      var l2 = l.skip(m);
</span><span style="color:#323232;">      var len = min(l1.length, l2.length);
</span><span style="color:#323232;">      return l1.take(len) == l2.take(len);
</span><span style="color:#323232;">    });
</span><span style="color:#323232;">
</span><span style="color:#323232;">bool reflectsV(int m, List p) {
</span><span style="color:#323232;">  var l1 = p.take(m).toList().reversed.toList();
</span><span style="color:#323232;">  var l2 = p.skip(m).toList();
</span><span style="color:#323232;">  var len = min(l1.length, l2.length);
</span><span style="color:#323232;">  return 0.to(len).every((ix) => l1[ix] == l2[ix]);
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="color:#323232;">int findReflection(List p, {int butNot = -1}) {
</span><span style="color:#323232;">  var mirrors = 1
</span><span style="color:#323232;">      .to(p.first.length)
</span><span style="color:#323232;">      .where((m) => reflectsH(m, p))
</span><span style="color:#323232;">      .toSet()
</span><span style="color:#323232;">      .difference({butNot});
</span><span style="color:#323232;">  if (mirrors.length == 1) return mirrors.first;
</span><span style="color:#323232;">
</span><span style="color:#323232;">  mirrors = 1
</span><span style="color:#323232;">      .to(p.length)
</span><span style="color:#323232;">      .where((m) => reflectsV(m, p))
</span><span style="color:#323232;">      .toSet()
</span><span style="color:#323232;">      .difference({butNot ~/ 100});
</span><span style="color:#323232;">  if (mirrors.length == 1) return 100 * mirrors.first;
</span><span style="color:#323232;">
</span><span style="color:#323232;">  return -1; //never
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="color:#323232;">int findSecondReflection(List p) {
</span><span style="color:#323232;">  var origMatch = findReflection(p);
</span><span style="color:#323232;">  for (var r in 0.to(p.length)) {
</span><span style="color:#323232;">    for (var c in 0.to(p.first.length)) {
</span><span style="color:#323232;">      var pp = p.toList();
</span><span style="color:#323232;">      var cells = pp[r].split('');
</span><span style="color:#323232;">      cells[c] = (cells[c] == '#') ? '.' : '#';
</span><span style="color:#323232;">      pp[r] = cells.join();
</span><span style="color:#323232;">      var newMatch = findReflection(pp, butNot: origMatch);
</span><span style="color:#323232;">      if (newMatch > -1) return newMatch;
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">  }
</span><span style="color:#323232;">  return -1; // never
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="color:#323232;">Iterable> parse(List lines) => lines
</span><span style="color:#323232;">    .splitBefore((e) => e.isEmpty)
</span><span style="color:#323232;">    .map((e) => e.first.isEmpty ? e.skip(1).toList() : e);
</span><span style="color:#323232;">
</span><span style="color:#323232;">part1(lines) => parse(lines).map(findReflection).sum;
</span><span style="color:#323232;">
</span><span style="color:#323232;">part2(lines) => parse(lines).map(findSecondReflection).sum;
</span>

mykl, 5 months ago

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!

mykl, 5 months ago

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.

mykl, 5 months ago

Dart

Nothing interesting here, just did it all explicitly. I might try something different in Uiua later.

<span style="color:#323232;">solve(List lines, {int age = 2}) {
</span><span style="color:#323232;">  var grid = lines.map((e) => e.split('')).toList();
</span><span style="color:#323232;">  var gals = [
</span><span style="color:#323232;">    for (var r in grid.indices())
</span><span style="color:#323232;">      for (var c in grid[r].indices().where((c) => grid[r][c] == '#')) (r, c)
</span><span style="color:#323232;">  ];
</span><span style="color:#323232;">  for (var row in grid.indices(step: -1)) {
</span><span style="color:#323232;">    if (!grid[row].contains('#')) {
</span><span style="color:#323232;">      gals = gals
</span><span style="color:#323232;">          .map((e) => ((e.$1 > row) ? e.$1 + age - 1 : e.$1, e.$2))
</span><span style="color:#323232;">          .toList();
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">  }
</span><span style="color:#323232;">  for (var col in grid.first.indices(step: -1)) {
</span><span style="color:#323232;">    if (grid.every((r) => r[col] == '.')) {
</span><span style="color:#323232;">      gals = gals
</span><span style="color:#323232;">          .map((e) => (e.$1, (e.$2 > col) ? e.$2 + age - 1 : e.$2))
</span><span style="color:#323232;">          .toList();
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">  }
</span><span style="color:#323232;">  var dists = [
</span><span style="color:#323232;">    for (var ix1 in gals.indices())
</span><span style="color:#323232;">      for (var ix2 in (ix1 + 1).to(gals.length))
</span><span style="color:#323232;">        (gals[ix1].$1 - gals[ix2].$1).abs() +
</span><span style="color:#323232;">            (gals[ix1].$2 - gals[ix2].$2).abs()
</span><span style="color:#323232;">  ];
</span><span style="color:#323232;">  return dists.sum;
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="color:#323232;">part1(List lines) => solve(lines);
</span><span style="color:#323232;">part2(List lines) => solve(lines, age: 1000000);
</span>

mykl, 5 months ago

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

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

mykl, 5 months ago (edited 5 months ago)

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!

<span style="color:#323232;">var up = Point(0, -1),
</span><span style="color:#323232;">    down = Point(0, 1),
</span><span style="color:#323232;">    left = Point(-1, 0),
</span><span style="color:#323232;">    right = Point(1, 0);
</span><span style="color:#323232;">var pipes = >>{
</span><span style="color:#323232;">  '|': [up, down],
</span><span style="color:#323232;">  '-': [left, right],
</span><span style="color:#323232;">  'L': [up, right],
</span><span style="color:#323232;">  'J': [up, left],
</span><span style="color:#323232;">  '7': [left, down],
</span><span style="color:#323232;">  'F': [right, down],
</span><span style="color:#323232;">};
</span><span style="color:#323232;">late List> grid; // Make grid global for part 2
</span><span style="color:#323232;">Set> buildPath(List lines) {
</span><span style="color:#323232;">  grid = lines.map((e) => e.split('')).toList();
</span><span style="color:#323232;">  var points = {
</span><span style="color:#323232;">    for (var row in grid.indices())
</span><span style="color:#323232;">      for (var col in grid.first.indices()) Point(col, row): grid[row][col]
</span><span style="color:#323232;">  };
</span><span style="color:#323232;">  // Find the starting point.
</span><span style="color:#323232;">  var pos = points.entries.firstWhere((e) => e.value == 'S').key;
</span><span style="color:#323232;">  var path = {pos};
</span><span style="color:#323232;">  // Replace 'S' with assumed pipe.
</span><span style="color:#323232;">  var dirs = [up, down, left, right].where((el) =>
</span><span style="color:#323232;">      points.keys.contains(pos + el) &amp;&amp;
</span><span style="color:#323232;">      pipes.containsKey(points[pos + el]) &amp;&amp;
</span><span style="color:#323232;">      pipes[points[pos + el]]!.contains(Point(-el.x, -el.y)));
</span><span style="color:#323232;">  grid[pos.y][pos.x] = pipes.entries
</span><span style="color:#323232;">      .firstWhere((e) =>
</span><span style="color:#323232;">          (e.value.first == dirs.first) &amp;&amp; (e.value.last == dirs.last) ||
</span><span style="color:#323232;">          (e.value.first == dirs.last) &amp;&amp; (e.value.last == dirs.first))
</span><span style="color:#323232;">      .key;
</span><span style="color:#323232;">
</span><span style="color:#323232;">  // Follow the path.
</span><span style="color:#323232;">  while (true) {
</span><span style="color:#323232;">    var nd = dirs.firstWhereOrNull((e) =>
</span><span style="color:#323232;">        points.containsKey(pos + e) &amp;&amp;
</span><span style="color:#323232;">        !path.contains(pos + e) &amp;&amp;
</span><span style="color:#323232;">        (points[pos + e] == 'S' || pipes.containsKey(points[pos + e])));
</span><span style="color:#323232;">    if (nd == null) break;
</span><span style="color:#323232;">    pos += nd;
</span><span style="color:#323232;">    path.add(pos);
</span><span style="color:#323232;">    dirs = pipes[points[pos]]!;
</span><span style="color:#323232;">  }
</span><span style="color:#323232;">  return path;
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="color:#323232;">part1(List lines) => buildPath(lines).length ~/ 2;
</span><span style="color:#323232;">part2(List lines) {
</span><span style="color:#323232;">  var path = buildPath(lines);
</span><span style="color:#323232;">  var count = 0;
</span><span style="color:#323232;">  for (var r in grid.indices()) {
</span><span style="color:#323232;">    var outside = true;
</span><span style="color:#323232;">    // We're only interested in how many times we have crossed the path
</span><span style="color:#323232;">    // to get to any given point, so mark anything that's not on the path
</span><span style="color:#323232;">    // as '*' for counting, and collapse all uninteresting path segments.
</span><span style="color:#323232;">    var row = grid[r]
</span><span style="color:#323232;">        .indexed()
</span><span style="color:#323232;">        .map((e) => path.contains(Point(e.index, r)) ? e.value : '*')
</span><span style="color:#323232;">        .join('')
</span><span style="color:#323232;">        .replaceAll('-', '')
</span><span style="color:#323232;">        .replaceAll('FJ', '|') // zigzag
</span><span style="color:#323232;">        .replaceAll('L7', '|') // other zigzag
</span><span style="color:#323232;">        .replaceAll('LJ', '') // U-bend
</span><span style="color:#323232;">        .replaceAll('F7', ''); // n-bend
</span><span style="color:#323232;">    for (var c in row.split('')) {
</span><span style="color:#323232;">      if (c == '|') {
</span><span style="color:#323232;">        outside = !outside;
</span><span style="color:#323232;">      } else {
</span><span style="color:#323232;">        if (!outside &amp;&amp; c == '*') count += 1;
</span><span style="color:#323232;">      }
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">  }
</span><span style="color:#323232;">  return count;
</span><span style="color:#323232;">}
</span>

mykl, 5 months ago

If you’re still stuck on part 2, have a look at my comment which shows an unreasonably easy approach :-)

mykl, 5 months ago

It’s so humbling when you’ve hammered out a solution and then realise you’ve been paddling around in waters that have already been mapped out by earlier explorers!

mykl, 5 months ago (edited 5 months ago)

Dart

I was getting a bad feeling when it explained in such detail how to solve part 1 that part 2 was going to be some sort of nightmare of traversing all those generated numbers in some complex fashion, but this has got to be one of the shortest solutions I’ve ever written for an AoC challenge.

<span style="color:#323232;">int nextTerm(Iterable ns) {
</span><span style="color:#323232;">  var diffs = ns.window(2).map((e) => e.last - e.first);
</span><span style="color:#323232;">  return ns.last +
</span><span style="color:#323232;">      ((diffs.toSet().length == 1) ? diffs.first : nextTerm(diffs.toList()));
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="color:#323232;">List> parse(List lines) => [
</span><span style="color:#323232;">      for (var l in lines) [for (var n in l.split(' ')) int.parse(n)]
</span><span style="color:#323232;">    ];
</span><span style="color:#323232;">
</span><span style="color:#323232;">part1(List lines) => parse(lines).map(nextTerm).sum;
</span><span style="color:#323232;">part2(List lines) => parse(lines).map((e) => nextTerm(e.reversed)).sum;
</span>

mykl, 5 months ago (edited 5 months ago)

I even have time to knock out a quick Uiua solution before going out today, using experimental recursion support. Bleeding edge code:

<span style="color:#323232;"># Experimental!
</span><span style="color:#323232;">{"0 3 6 9 12 15"
</span><span style="color:#323232;"> "1 3 6 10 15 21"
</span><span style="color:#323232;"> "10 13 16 21 30 45"}
</span><span style="color:#323232;">StoInt ← /(+×10)▽×⊃(≥0)(≤9).-@0
</span><span style="color:#323232;">NextTerm ← ↬(
</span><span style="color:#323232;">  ↘1-↻¯1..      # rot by one and take diffs
</span><span style="color:#323232;">  (|1 ↫|⊢)=1⧻⊝. # if they're all equal grab else recurse
</span><span style="color:#323232;">  +⊙(⊢↙¯1)      # add to last value of input
</span><span style="color:#323232;">)
</span><span style="color:#323232;">≡(⊜StoInt≠@s.⊔) # parse
</span><span style="color:#323232;">⊃(/+≡NextTerm)(/+≡(NextTerm ⇌))
</span>

mykl, 5 months ago (edited 5 months ago)

Dart

I’m glad I took the time to read the directions very carefully before starting coding :-)

Top Tip: my ranking of hand types relies on the fact that if you count instances of each face and sort the resulting list from high to low, you get a list that when compared with lists from other hands gives an exact correspondence with the order of the hand types as defined, so no need for a bunch of if/thens, just

<span style="color:#323232;">  var type = Multiset.from(hand).counts.sorted(descending).join('');
</span>

Otherwise it should all be pretty self-explanatory apart from where I chose to map card rank to hex digits in order to facilitate sorting, so ‘b’ means ‘J’!

<span style="color:#323232;">int descending(T a, T b) => b.compareTo(a);
</span><span style="color:#323232;">var cToH = "  23456789TJQKA"; // used to map card rank to hex for sorting.
</span><span style="color:#323232;">
</span><span style="color:#323232;">handType(List hand, {wildcard = false}) {
</span><span style="color:#323232;">  var type = Multiset.from(hand).counts.sorted(descending).join('');
</span><span style="color:#323232;">  var i = hand.indexOf('b');
</span><span style="color:#323232;">  return (!wildcard || i == -1)
</span><span style="color:#323232;">      ? type
</span><span style="color:#323232;">      : '23456789acde'
</span><span style="color:#323232;">          .split('')
</span><span style="color:#323232;">          .map((e) => handType(hand.toList()..[i] = e, wildcard: true))
</span><span style="color:#323232;">          .fold(type, (s, t) => s.compareTo(t) >= 0 ? s : t);
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="color:#323232;">solve(List lines, {wildcard = false}) => lines
</span><span style="color:#323232;">    .map((e) {
</span><span style="color:#323232;">      var l = e.split(' ');
</span><span style="color:#323232;">      var hand =
</span><span style="color:#323232;">          l.first.split('').map((e) => cToH.indexOf(e).toRadixString(16));
</span><span style="color:#323232;">      var type = handType(hand.toList(), wildcard: wildcard);
</span><span style="color:#323232;">      if (wildcard) hand = hand.map((e) => e == 'b' ? '0' : e);
</span><span style="color:#323232;">      return (hand.join(), type, int.parse(l.last));
</span><span style="color:#323232;">    })
</span><span style="color:#323232;">    .sorted((a, b) {
</span><span style="color:#323232;">      var c = a.$2.compareTo(b.$2);
</span><span style="color:#323232;">      return (c == 0) ? a.$1.compareTo(b.$1) : c;
</span><span style="color:#323232;">    })
</span><span style="color:#323232;">    .indexed(offset: 1)
</span><span style="color:#323232;">    .map((e) => e.value.$3 * e.index)
</span><span style="color:#323232;">    .sum;
</span><span style="color:#323232;">
</span><span style="color:#323232;">part1(List lines) => solve(lines);
</span><span style="color:#323232;">
</span><span style="color:#323232;">part2(List lines) => solve(lines, wildcard: true);
</span>

mykl, 5 months ago (edited 5 months ago)

It’s Uiua time!

It works, but even I can’t understand this code any more as I’m well into my second beer, so don’t put this into production, okay? (Run it here if you dare.)

<span style="color:#323232;">{"32T3K 765"
</span><span style="color:#323232;"> "T55J5 684"
</span><span style="color:#323232;"> "KK677 28"
</span><span style="color:#323232;"> "KTJJT 220"
</span><span style="color:#323232;"> "QQQJA 483"}
</span><span style="color:#323232;">StoInt ← /(+×10)▽×⊃(≥0)(≤9).-@0
</span><span style="color:#323232;">ToHex ← ⊏:"  23456789abcde"⊗:"  23456789TJQKA"
</span><span style="color:#323232;">ToHexJ ← ⊏:"  23456789a0cde"⊗:"  23456789TJQKA"
</span><span style="color:#323232;"># A hand of "311" with one J will have same rank as "41"
</span><span style="color:#323232;"># Dots indicate impossible hands.
</span><span style="color:#323232;">Rankings ← {
</span><span style="color:#323232;">  {"11111" "2111" "221" "311" "32" "41" "5"}   # 0
</span><span style="color:#323232;">  {"..." "11111" ".." "2111" "221" "311" "41"} # 1
</span><span style="color:#323232;">  {"..." "....." ".." "2111" "..." "221" "32"} # 2
</span><span style="color:#323232;">  {"..." "....." ".." "...." "..." "311" "32"} # 3
</span><span style="color:#323232;">  {"..." "....." ".." "...." "..." "..." "41"} # 4
</span><span style="color:#323232;">  {"..." "....." ".." "...." "..." "..." "5"}  # 5
</span><span style="color:#323232;">}
</span><span style="color:#323232;">RankHand ← (
</span><span style="color:#323232;">  +@0⊏⍖.⊕⧻⊛⊢⍉⇌⊕∘⍖...          # Count instances, sort desc, to string
</span><span style="color:#323232;">  ⊗⊃⊢(⊔⊡:Rankings/+=@0⊢↘1)⊟∩□ # Use table to get ranking
</span><span style="color:#323232;">)
</span><span style="color:#323232;">ScoreHands! ← (
</span><span style="color:#323232;">  ≡(⊐⊟⊓(⊐⊟RankHand.^1⊔)∘⍘⊟) # Rank every hand
</span><span style="color:#323232;">  /+/×⊟+1⇡⧻.∵⊔≡(⊢↘1)⊏⍏≡⊢.   # Sort based on rankings
</span><span style="color:#323232;">)
</span><span style="color:#323232;">⍉⊟⊓∘(∵StoInt)⍘⊟⍉≡(⊐⊜∘≠@s.) # Parse input
</span><span style="color:#323232;">⊃(ScoreHands!ToHex)(ScoreHands!ToHexJ)
</span><span style="color:#323232;">
</span>

mykl, 5 months ago

Lots and lots of print statements :-)

mykl, 5 months ago

Dart Solution

I decided to use the quadratic formula to solve part 1 which slowed me down while I struggled to remember how it went, but meant that part 2 was a one line change.

This year really is a roller coaster…

<span style="color:#323232;">int countGoodDistances(int time, int targetDistance) {
</span><span style="color:#323232;">  var det = sqrt(time * time - 4 * targetDistance);
</span><span style="color:#323232;">  return (((time + det) / 2).ceil() - 1) -
</span><span style="color:#323232;">      (max(((time - det) / 2).floor(), 0) + 1) +
</span><span style="color:#323232;">      1;
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="color:#323232;">solve(List> data, [param]) {
</span><span style="color:#323232;">  var distances = data.first
</span><span style="color:#323232;">      .indices()
</span><span style="color:#323232;">      .map((ix) => countGoodDistances(data[0][ix], data[1][ix]));
</span><span style="color:#323232;">  return distances.reduce((s, t) => s * t);
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="color:#323232;">getNums(l) => l.split(RegExp(r's+')).skip(1);
</span><span style="color:#323232;">
</span><span style="color:#323232;">part1(List lines) =>
</span><span style="color:#323232;">    solve([for (var l in lines) getNums(l).map(int.parse).toList()]);
</span><span style="color:#323232;">
</span><span style="color:#323232;">part2(List lines) => solve([
</span><span style="color:#323232;">      for (var l in lines) [int.parse(getNums(l).join(''))]
</span><span style="color:#323232;">    ]);
</span>

mykl, 5 months ago (edited 5 months ago)

Today was easy enough that I felt confident that I could hammer out a solution in Uiua, so read and enjoy (or try it out live):

<span style="color:#323232;">{"Time:      7  15   30"
</span><span style="color:#323232;"> "Distance:  9  40  200"}
</span><span style="color:#323232;">StoInt ← /(+ ×10) ▽×⊃(≥0)(≤9). -@0
</span><span style="color:#323232;">Count ← (
</span><span style="color:#323232;">  ⊙⊢√-×4:×.⍘⊟.           # Determinant, and time
</span><span style="color:#323232;">  +1-⊃(+1↥0⌊÷2-)(-1⌈÷2+) # Diff of sanitised roots
</span><span style="color:#323232;">)
</span><span style="color:#323232;">≡(↘1⊐⊜∘≠@s.)
</span><span style="color:#323232;">⊃(/×≡Count⍉∵StoInt)(Count⍉≡(StoInt⊐/⊂))
</span>

mykl, 5 months ago

Same here: the “Out of Heap” error came as a bit of a surprise…