A Christmas Day treat: a one-liner for you all to decipher!
"#####\n.####\n.####\n.####\n.#.#.\n.#...\n.....\n\n#####\n##.##\n.#.##\n...##\n...#.\n...#.\n.....\n\n.....\n#....\n#....\n#...#\n#.#.#\n#.###\n#####\n\n.....\n.....\n#.#..\n###..\n###.#\n###.#\n#####\n\n.....\n.....\n.....\n#....\n#.#..\n#.#.#\n#####"
/+♭⊞(/×<8+)∩°□°⊟ ⊕(□≡≡/+⌕@#)≠@#≡(⊢⊢). ⊜(⍉⊜∘⊸≠@\n)¬±⦷"\n\n".
Quick and dirty, and slightly tipsy, code.
Happy Christmas everyone!
Thanks to Eric and the team at Advent of Code, to @Ategon@programming.dev and @CameronDev@programming.dev for giving us somewhere to share and discuss our solutions, and to everyone here for the friendly and supportive community.
See you all next year!
import 'package:collection/collection.dart';
import 'package:more/more.dart';
part1(List<String> lines) {
var (w, h) = (lines.first.length, lines.indexOf(''));
var (falsey: keys, truthy: locks) = (lines..insert(0, ''))
.splitBefore((l) => l.isEmpty)
.map((g) => [
for (var x in 0.to(w)) [for (var y in 1.to(h + 1)) g[y][x]]
])
.partition((g) => g[0][0] == '#');
return keys
.map((l) => locks.count((k) =>
0.to(w).every((r) => (l[r] + k[r]).count((e) => e == '#') < 8)))
.sum;
}
True, I’ve just been looking at the comments on the other place, and pretty much everyone there seems to have resorted to figuring it out manually too.
Haha, I spent about two hours fiddling about in the debugger and drawing bad diagrams to get an answer. I just checked and it turns out that I also got my personal best ranking on it too, though I’m not sure it should count :-)
Not very happy with this, as for part 2 the code just told me which four pairs of bits of the output needed investigation and I then tediously worked through how they differed from the correct adder implementation in the debugger.
Spoilered as it is overly long and not very interesting.
import 'package:collection/collection.dart';
import 'package:more/more.dart';
var nodes = <String, Node>{};
class Node {
bool? state;
var outputGates = <String>[];
}
class Wire implements Node {
@override
bool? state;
@override
var outputGates = <String>[];
Wire(this.state);
set() {
for (var g in outputGates) {
(nodes[g]! as Gate).set();
}
}
}
class Gate implements Node {
String name, input1, input2, type;
@override
bool? state;
@override
var outputGates = <String>[];
Gate(this.name, this.input1, this.input2, this.type);
set() {
var a = nodes[input1]!.state;
var b = nodes[input2]!.state;
if (a == null || b == null) return;
state = switch (type) { 'AND' => a && b, 'OR' => a || b, _ => a ^ b };
for (var g in outputGates) {
(nodes[g]! as Gate).set();
}
}
}
void setup(List<String> lines) {
var parts = lines.splitAfter((e) => e.isEmpty);
Map<String, Node> wires = Map.fromEntries(parts.first.skipLast(1).map((e) {
var p = e.split(': ');
return MapEntry(p[0], Wire(p[1] == '1'));
}));
nodes = Map.fromEntries(parts.last.map((e) {
var p = e.split(' ');
return MapEntry(p.last, Gate(p.last, p[0], p[2], p[1]));
}));
nodes.addAll(wires);
for (var g in nodes.values) {
if (g is! Gate) continue;
nodes[g.input1]!.outputGates.add(g.name);
nodes[g.input2]!.outputGates.add(g.name);
}
}
String line(String s) => nodes.keys
.where((e) => e.startsWith(s))
.sorted()
.reversed
.map((e) => nodes[e]!.state! ? '1' : '0')
.join('');
part1(List<String> lines) {
setup(lines);
nodes.values.whereType<Wire>().forEach((e) => e.set());
return int.parse(line('z'), radix: 2);
}
part2(List<String> lines) {
setup(lines);
var bits = nodes.keys.count((e) => e.startsWith('x'));
for (var b in 0.to(bits)) {
nodes.values.whereType<Gate>().forEach((e) => e.state = null);
nodes.values.whereType<Wire>().forEach(((e) => e.state = false));
nodes['y${b.toString().padLeft(2, "0")}']!.state = true;
nodes.values.whereType<Wire>().forEach((e) => e.set());
print('${line("x")}\t${line("y")}\t${line("z")}\t$b');
var output = line('z');
for (var i in 0.to(bits)) {
if (output[bits - i] != ((i == b) ? "1" : "0")) print(i);
}
}
// Add break point here and inspect and solve manually.
print('break here');
}
deleted by creator
A little bit of googling, a little bit of Wikipedia, and so a little bit of
gave me the following which takes about 300ms.
import 'package:collection/collection.dart';
import 'package:more/more.dart';
SetMultimap<String, String> getNodes(List<String> lines) {
var nodes = SetMultimap<String, String>();
for (var l in lines) {
var p = l.split('-');
nodes[p.first].add(p.last);
nodes[p.last].add(p.first);
}
return nodes;
}
part1(List<String> lines) {
var nodes = getNodes(lines);
var ts = nodes.keys.where((e) => e.startsWith('t'));
var ret = <String>[];
for (var t in ts) {
ret.addAll(nodes[t]
.combinations(2)
.where((e) => nodes[e.first].contains(e.last))
.map((e) => (([t] + e)..sort()).toString()));
}
return ret.toSet().length;
}
part2(List<String> lines) {
var nodes = getNodes(lines);
Iterable<Set<String>> useBK1(
Set<String> R, Set<String> P, Set<String> X) sync* {
if (P.isEmpty && X.isEmpty) {
yield R;
return;
}
for (var v in P.toSet()) {
yield* useBK1(R.toSet()..add(v), P.intersection(nodes[v]),
X.intersection(nodes[v]));
P.remove(v);
X.add(v);
}
}
var vs = nodes.keys.toSet()..addAll(nodes.values.deepFlatten());
var ret = useBK1({}, vs, {}).toList();
var max = ret.map((e) => e.length).max;
return ret.firstWhere((e) => e.length == max).sorted().join(',');
}
A messy drawer? There should be at least two: one for the kitchen and one for general.
It’s been a while since I posted one of these, but I thought this would be straightforward in Uiua. Turns out that bitwise operations are a bit (haha) of a pain, so the Rng operation is very slow at 4sec for live data.
I took this as an opportunity to play with the ⧈(stencil) operator which probably slowed things down too.
Data ← 1_2_3_2024
Xor ← °⋯◿2⬚0+∩⋯ # Bitwise xor of two numbers.
Rng ← ⊙◌◿,Xor×2048.◿,Xor⌊÷32.◿,Xor×64.⊙16777216
Runs ← ⍉(⇌[⍥(Rng.)])2000 Data # Should be constant?
Firsts ← (
⊟⊂0⧈₂/-.◿10 ↘¯1 # Build run, gen pair diffs
⊢⧈(⊟⊙⊣/(+×40+20)°⊟) 2_4 # Convert 4-diff into key, collect.
⊕⊢⊛⊙⍉⊙◌°⊟.⍉ # Only keep first of each key. # ⍜(map°⊟⍉⇌|∘) failed.
)
&p /+≡⊣.Runs
&p /↥⊕(/+)+1⊛°⊟⍉/◇⊂wait≡spawn(□Firsts) # Group by key, sum prices, return highest.
Great, thanks! I’ve always had Roassal at the back of my mind as a way of generating visualisations for AOC, but never got round to it. This might kick-start me, but maybe for next year at this point :-)
Well, that was certainly a bit easier than yesterday…
I know running a window over each full list of 2000 prices rather than looking for cycles etc means I’m doing a lot of unnecessary work, but it only takes a couple of seconds, so that’ll do.
import 'package:collection/collection.dart';
import 'package:more/more.dart';
rng(int i) {
i = ((i << 6) ^ i) % 16777216;
i = ((i >> 5) ^ i) % 16777216;
i = ((i << 11) ^ i) % 16777216;
return i;
}
Iterable<int> getPrices(int val, int rounds) {
var ret = [val];
for (var _ in 1.to(rounds)) {
ret.add(val = rng(val));
}
return ret.map((e) => e % 10);
}
int run(int val, int rounds) => 0.to(rounds).fold(val, (s, t) => s = rng(s));
part1(lines) => [for (var i in lines.map(int.parse)) run(i, 2000)].sum;
part2(List<String> lines) {
var market = <int, int>{}.withDefault(0);
for (var seed in lines.map(int.parse)) {
var seen = <int>{};
for (var w in getPrices(seed, 2000).window(5)) {
var key = // Can't use lists as keys, so make cheap hash.
w.window(2).map((e) => e[1] - e[0]).reduce((s, t) => (s << 4) + t);
if (seen.contains(key)) continue;
seen.add(key);
market[key] += w.last;
}
}
return market.values.max;
}
Have you published the source for this somewhere? I’m interested in seeing what Roassal is like to use.
The secret ingredient is a big cache.
import 'dart:math';
import 'package:collection/collection.dart';
import 'package:more/more.dart';
Map<String, Point<num>> mapper(List<String> list) => {
for (var r in list.indexed())
for (var c in r.value.split('').indexed())
c.value: Point<num>(c.index, r.index)
};
var dirMap = mapper(['_^A', '<v>']);
var numMap = mapper(['789', '456', '123', '_0A']);
var lenCache = <(String, int), int>{};
int len(String code, int level, isNum) =>
lenCache.putIfAbsent((code, level), () => _len(code, level, isNum));
int n(p, isNum, level) => len(getMoves(p[0], p[1], isNum), level - 1, false);
int _len(String code, int level, isNum) => (level == 0)
? code.length
: 'A$code'.split('').window(2).map((p) => n(p, isNum, level)).sum;
String getMoves(String f, String t, bool isNum) {
var map = isNum ? numMap : dirMap;
var (from, to) = (map[f]!, map[t]!);
var mv = to - from;
var s = <String>{};
var x = ''.padRight(mv.x.abs() as int, mv.x.sign == 1 ? '>' : '<');
var y = ''.padRight(mv.y.abs() as int, mv.y.sign == 1 ? 'v' : '^');
// avoid '_', dislike '<'
if (Point(from.x, to.y) != map['_']!) s.add('$y${x}A');
if (Point(to.x, from.y) != map['_']!) s.add('$x${y}A');
return (s.length < 2 || mv.x > 0) ? s.first : s.last;
}
int solve(String code, int level) =>
len(code, level + 1, true) * int.parse(code.skipLast(1));
part1(List<String> lines) => lines.map((e) => solve(e, 2)).sum;
part2(List<String> lines) => lines.map((e) => solve(e, 25)).sum;
Nice. Roassal? Is that Smalltalk then?
Simple path-finding + brute force. O(n*sqrt-n) I think but only takes ~200 milliseconds so that’ll do for today. Time to walk the dog!
After being so pleased to have written my own path-finding algorithm the other day, I discovered that my regular more library already includes one. D’oh.
(edit: shaved some milliseconds off)
import 'dart:math';
import 'package:more/more.dart';
List<Point<num>> d4 = [Point(1, 0), Point(-1, 0), Point(0, 1), Point(0, -1)];
List<Point<num>> findPath(List<String> lines) {
var maze = {
for (var r in lines.indexed())
for (var c in r.value.split('').indexed().where((e) => e.value != '#'))
Point<num>(c.index, r.index): c.value
}.withDefault('#');
var path = AStarSearchIterable<Point>(
startVertices: [maze.entries.firstWhere((e) => e.value == 'S').key],
successorsOf: (p) => d4.map((e) => (e + p)).where((n) => maze[n] != '#'),
costEstimate: (p) => 1,
targetPredicate: (p) => maze[p] == 'E').first.vertices;
return path;
}
num dist(Point p1, Point p2) => (p1.x - p2.x).abs() + (p1.y - p2.y).abs();
solve(List<String> lines, int cheat, int target) {
List<Point<num>> path = findPath(lines);
var cheats = 0;
for (int s = 0; s < path.length - cheat; s++) {
for (int e = s + cheat; e < path.length; e++) {
var d = dist(path[e], path[s]);
var diff = e - s - d;
if (d <= cheat && diff >= target) cheats += 1;
}
}
return cheats;
}
Wee-wuh 😉
Wanna try some Uiua?
It was a real D’oh! moment when I visualised the data I was generating and saw all the zeros stretching across the page.
Yeah, I had to fiddle with that limit before it actually worked for me, so it’s clearly quite sensitive to the data :-)
Thanks for sharing this. It’s always good to be reminded of the thinking process and dead ends behind the successful solutions.
I really enjoyed figuring out your C code this year, and would be very interested to see what you could do with Uiua :-)