mykl 9mo ago • 100%
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 10mo ago • 100%
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 10mo ago • 100%
Isn’t every video game just moving colourful blocks?
(Except Quake obviously)
mykl 10mo ago • 40%
i_understood_that_reference.jif
mykl 10mo ago • 100%
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);
}
mykl 10mo ago • 100%
That’s why I normally let computers do my sums for me. Corrected now.
mykl 10mo ago • 100%
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;
}
mykl 10mo ago • 100%
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);
mykl 10mo ago • 100%
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;
mykl 10mo ago • 100%
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 10mo ago • 100%
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
mykl 10mo ago • 100%
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 10mo ago • 100%
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);
mykl 10mo ago • 100%
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 10mo ago • 100%
If you're still stuck on part 2, have a look at my comment which shows an unreasonably easy approach :-)
mykl 10mo ago • 100%
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;
}
mykl 11mo ago • 100%
Dart
Nothing interesting here, just did it all explicitly. I might try something different in Uiua later.
solve(List lines, {int age = 2}) {
var grid = lines.map((e) => e.split('')).toList();
var gals = [
for (var r in grid.indices())
for (var c in grid[r].indices().where((c) => grid[r][c] == '#')) (r, c)
];
for (var row in grid.indices(step: -1)) {
if (!grid[row].contains('#')) {
gals = gals
.map((e) => ((e.$1 > row) ? e.$1 + age - 1 : e.$1, e.$2))
.toList();
}
}
for (var col in grid.first.indices(step: -1)) {
if (grid.every((r) => r[col] == '.')) {
gals = gals
.map((e) => (e.$1, (e.$2 > col) ? e.$2 + age - 1 : e.$2))
.toList();
}
}
var dists = [
for (var ix1 in gals.indices())
for (var ix2 in (ix1 + 1).to(gals.length))
(gals[ix1].$1 - gals[ix2].$1).abs() +
(gals[ix1].$2 - gals[ix2].$2).abs()
];
return dists.sum;
}
part1(List lines) => solve(lines);
part2(List lines) => solve(lines, age: 1000000);
mykl 11mo ago • 100%
Lots and lots of print statements :-)
mykl 11mo ago • 100%
I even have time to knock out a quick Uiua solution before going out today, using experimental recursion support. Bleeding edge code:
# Experimental!
{"0 3 6 9 12 15"
"1 3 6 10 15 21"
"10 13 16 21 30 45"}
StoInt ← /(+×10)▽×⊃(≥0)(≤9).-@0
NextTerm ← ↬(
↘1-↻¯1.. # rot by one and take diffs
(|1 ↫|⊢)=1⧻⊝. # if they're all equal grab else recurse
+⊙(⊢↙¯1) # add to last value of input
)
≡(⊜StoInt≠@\s.⊔) # parse
⊃(/+≡NextTerm)(/+≡(NextTerm ⇌))
How was day one for everyone? I was surprised at how tricky it was to get the right answer for part two. Not the usual easy start I've seen in the past. I'd be interested to see any solutions here.
Hi All, I [posted here recently](https://programming.dev/post/5572355) that I was spending November revisiting my AOC 2022 solutions (written in Dart) and posting them for reading, running and editing online. With my [last solution](https://lemmy.world/post/8729365) being posted yesterday, the series is now complete, and might be interesting if anyone's looking for an idea of the level of difficulty involved in a typical year. To ensure that this post isn't just about posts on other communities, I've added a little bonus content - a simple visualisation I created for my solution for day 14 (flowing sand).
As a warmup for this year's Advent of Code, I'm re-reading and posting my solutions to [last year's challenges](https://adventofcode.com/2022). You can read, run and edit today's solution by following the post link. [Today](https://adventofcode.com/2022/day/25) was the final challenge for the year, and as usual was quite simple and had only one part. This involved parsing and process numbers written in what I learned was called "[balanced base](https://en.wikipedia.org/wiki/Balanced_ternary) five" notation. Thanks for following along, now we just need to wait a few days to see what this year holds!
As a warmup for this year's Advent of Code, I'm re-reading and posting my solutions to [last year's challenges](https://adventofcode.com/2022). You can read, run and edit today's solution by following the post link. [Today](https://adventofcode.com/2022/day/24) had us running round a maze with moving obstacles. Treating time as a dimension allowed me to build a graph and find the shortest path. Part 2 just required doing this three times. This took me closer than I like to a full second runtime, but not close enough to make me re-think my solution.
As a warmup for this year's Advent of Code, I'm re-reading and posting my solutions to [last year's challenges](https://adventofcode.com/2022). You can read, run and edit today's solution by following the post link. [Today](https://adventofcode.com/2022/day/23) was a kinda variant of Conway's Game of Life: we had to move elves around according to a set of rules while avoiding collisions and observe the size of the bounding box after 10 rounds. Part 2 asked us to run until the pattern stagnated. Nothing clever in my solution as most of the challenge seemed to be in understanding the rules correctly :-)
The !adventofcode@lemmy.world community is currently without an active mod: the original creator does not seem to have been active on Lemmy in months. I PM’d them to check whether they were still interested in the community and have received no reply. I'm presently more or less the only active poster there, though that may change next month when this year's [Advent of Code](https://adventofcode.com/) kicks off.
As a warmup for this year's Advent of Code, I'm re-reading and posting my solutions to [last year's challenges](https://adventofcode.com/2022). You can read, run and edit today's solution by following the post link. [Today](https://adventofcode.com/2022/day/22) started quite easily: build a map and then follow some directions to navigate around it. Part 2? The map is now wrapped around a cube. Oof. I dealt with it by setting up logic for an "ideal" cube layout, and then mapping the provided definition onto that. Oddly, my solution for part2 seems to run faster than part1 despite all the added complexity...
As a warmup for this year's Advent of Code, I'm re-reading and posting my solutions to [last year's challenges](https://adventofcode.com/2022). You can read, run and edit today's solution by following the post link. [Today](https://adventofcode.com/2022/day/21) was again quite an easy one, requiring us to build up a tree of values and operations on those values. Part 1 had us evaluate the root value, and part 2 required us to change the value of a specific node to ensure that both branches below the root node evaluated to the same value. The linear nature of the operations allowed me to just try two different values and then interpolate the correct answer.
As a warmup for this year's Advent of Code, I'm re-reading and posting my solutions to [last year's challenges](https://adventofcode.com/2022). You can read, run and edit today's solution by following the post link. [Today](https://adventofcode.com/2022/day/20) came as a welcome relief after two tricky days! We had to jumble a file according to some simple rules. The biggest challenge was interpreting the instructions correctly; the solution itself took only a few lines. Part two just added a key and increased the number of iterations. My original approach still ran in under a second (0.7s) so I didn't bother looking into it any further, and just enjoyed the free time :-)
As a warmup for this year's Advent of Code, I'm re-reading and posting my solutions to [last year's challenges](https://adventofcode.com/2022). You can read, run and edit today's solution by following the post link. [Today](https://adventofcode.com/2022/day/19) was a sudden increase in difficulty (for me anyway). We had to find the best route for opening a system of valves to maximise the total flow through the network. Part two repeated the exercise, but with the addition of a friendly elephant to help with the work. I was able to simplify the network enough to solve part 1 in a reasonable time, but had to hack my solution for part 2 terribly to get it under a second. Reading some other solutions, I missed out on some key approaches including pre-calculating minimum paths between all pairs of valves (e.g. using the [Floyd–Warshall algorithm](https://en.wikipedia.org/wiki/Floyd–Warshall_algorithm)), aggressive caching of intermediate states, and separating out my movements from the elephant's movements. Go and read [@hal9001@lemmy.world](https://lemmy.world/u/hal9001)'s [Clojure solution](https://github.com/jjcomer/advent-2022/blob/main/src/y2022/d19.clj) for a much more thoughtful approach :smile:
As a warmup for this year's Advent of Code, I'm re-reading and posting my solutions to [last year's challenges](https://adventofcode.com/2022). You can read, run and edit today's solution by following the post link. [Today](https://adventofcode.com/2022/day/18) had us finding the surface area of a cluster of cubes, first in total, then excluding any internal voids. Nice and easy compared to the last couple of days!
As a warmup for this year's Advent of Code, I'm re-reading and posting my solutions to [last year's challenges](https://adventofcode.com/2022). You can read, run and edit today's solution by following the post link. [Today's challenge](https://adventofcode.com/2022/day/17) had us building a simple Tetris clone with the additional twist that a regular sequence of jets of air blow the falling pieces sideways. Part two asked us to model this for a bazillion cycles, so we needed to keep an eye on the pattern of landed blocks and look for the same pattern to repeat.
As a warmup for this year's Advent of Code, I'm re-reading and posting my solutions to [last year's challenges](https://adventofcode.com/2022). You can read, run and edit today's solution by following the post link. [Today](https://adventofcode.com/2022/day/16) we had to monitor and manage flow through a network of valves. The second part added a friendly elephant to help. So for me it was about building a weighted graph and then milling around it looking for good solutions. Despite my chaotic approach and somewhat ugly code, my solution ended up being impressively fast.
As a warmup for this year's Advent of Code, I'm re-reading and posting my solutions to [last year's challenges](https://adventofcode.com/2022). You can read, run and edit today's solution by following the post link. [Today](https://adventofcode.com/2022/day/15) we were given the output of a set of sensors recording the locations of their nearest beacons, and were asked to derive more information about those beacons. This was made much simpler due to the odd way these beacons' signal propagated, involving tracking diagonal lines rather than doing any trig. Part 2 required a bit of lateral thinking to avoid an overly-slow solution.
As a warmup for this year's Advent of Code, I'm re-reading and posting my solutions to [last year's challenges](https://adventofcode.com/2022). You can read, run and edit today's solution by following the post link. [Today](https://adventofcode.com/2022/day/14) we had to build a set of buckets from the given spec, and observe the behaviour of sand grains as they fell into them. I found this a really satisfying challenge, and enjoyed the visualisations that many people wrote for their solutions.
As a warmup for this year's Advent of Code, I'm re-reading and posting my solutions to [last year's challenges](https://adventofcode.com/2022). You can read, run and edit today's solution by following the post link. [Today](https://adventofcode.com/2022/day/13) we had to build and compare tree structures. I used Petitparser to parse the input and build the tree, and some questionable logic for the comparison, but it gave the right answer and quickly enough, so ship it!
As a warmup for this year's Advent of Code, I'm re-reading and posting my solutions to [last year's challenges](https://adventofcode.com/2022). You can read, run and edit today's solution by following the post link. Continuing the ramp up in difficulty, [today's challenge](https://adventofcode.com/2022/day/12) asked us to do some literal (virtual) hill-climbing, but with the added constraint of not allowing too large a step. I was able to re-use an existing Graph class I had built along with an implementation of Dijkstra search.