![User's banner](/_next/image?url=https%3A%2F%2Flemm.ee%2Fapi%2Fv3%2Fimage_proxy%3Furl%3Dhttps%253A%252F%252Flemmy.world%252Fpictrs%252Fimage%252Fee96efeb-08dd-4f7e-9f8c-bd08bfadff73.jpeg&w=2048&q=75)
![Avatar](/_next/image?url=https%3A%2F%2Flemm.ee%2Fapi%2Fv3%2Fimage_proxy%3Furl%3Dhttps%253A%252F%252Flemmy.world%252Fpictrs%252Fimage%252Fd4a4abe6-aa80-4d50-96db-00ddb6932f74.jpeg&w=3840&q=75)
![Avatar](/_next/image?url=%2Flemmy-icon-96x96.webp&w=3840&q=75)
mykl
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
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?
Isn’t every video game just moving colourful blocks?
(Except Quake obviously)
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);
}
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;