swlabr
joined 1 year ago
d8: done, and nothing to say about it.
re: branch cutting
IDK if this is what your issue was, but one thing I ran into was that if you do something like if (current_total >= target) prune(), this can be problematic because if the tail end of the data is 0s and 1s, you exit too early. Basically I would prune strictly when the current total > target.
Day 7
1 and 2
On reflection, it was a pretty fun little problem to solve. There wasn't much of a difference between the two parts. I ran into some bugs with my recursion termination conditions, but I got them in the end.
Part 1. A quick look at the data showed that the input length was short enough to perform an O(2^n^) search with some early exits. I coded it as a dfs.
Part 2. Adding concatenation just changes the base from 2 to 3, which, while strictly slower, wasn't much slower for this input.
code
void d7(bool sub) => print(getLines()
.map((l) => l.split(RegExp(r':? ')).map(int.parse).toList())
.fold<int>(
0, (p, ops) => test(ops, ops[0], ops[1], 2, sub) ? ops[0] + p : p));
bool test(List<int> l, int cal, int cur, int i, bool sub) =>
cur == cal && i == l.length ||
(i < l.length && cur <= cal) &&
(test(l, cal, cur + l[i], i + 1, sub) ||
test(l, cal, cur * l[i], i + 1, sub) ||
(sub && test(l, cal, cur.concat(l[i]), i + 1, sub)));
Fucking hell. What exactly do they pay Salty Ballman for if all he does is come up the same ideas over and over? Just replace him with a coin with “cram another LLM into the trenchcoat” on one side and “add another payment tier” on the other.
Worst fake techonology revolution ever. This bubble can’t burst fast enough.
I have heard that egg nog and orange soda is a surprisingly good drink.
as the edgy commie teens say, praxis
I will probably slow down and try to solve the problems on the weekends rather than daily. Anyway, 9:
part 1
This was straightforward in that all you need to do is implement the algorithm as given. I did optimise a little using the arithmetic progression sum, but this is a speed-up of, at most like, a factor of 9.I am pretty sure I did an OK job at avoiding edge cases, though I suspect this problem has many of them.
part 2
Again, the algorithm is more or less given: Start from the back, look for a hole that'll work, and put it in if you can. Otherwise, don't. Then, calculate the contribution to the checksum.The complex part was the "look for a hole" part. My input size was 19999, meaning an O(n^2^) solution was probably fast enough, but I decided to optimise and use a min heap for each space size prematurely. I foresaw that you need to split up a space if it is oversized for a particular piece of data, i.e. pop the slot from the heap, reduce the size of the slot, and put it in the heap corresponding to the new size.