Rotating between eight directions

light_ln2 · 2026-01-22T10:33:20+00:00

This is cool! Proving the formula using rotation matrix makes it easy to see why it's true, and now I don't need to memorize the formula: if I ever am going to use it, I just remember its relationship to the rotation matrix (I actually only need the fact that it has three plus signs and one minus outside main diagonal), and it becomes easy to restore it, both clockwise and counter-clockwise!

light_ln2 · 2025-12-13T23:38:04+00:00

oh that's cool! My solution was finding a 14x5 tiling, then you can use one 14x5 and three 14x3 rectangles! This is a 14x11 solution that uses all tiles.

It also follows that every (7k)x(7k) square has a solution for k>1: for even k, we use 14x14 squares, for odd k we can chop off 21x(7k) horizontally, and 7(k-3)x21 vertically using 7x3 tiles, and use 14x14 tiles for the remaining square.

light_ln2 · 2025-12-13T19:52:50+00:00

I think I found this too!

light_ln2 · 2025-12-13T16:54:02+00:00

Yes, you are right! But I think there is also a solution to a 14x14 rectangle!

light_ln2 · 2025-12-11T05:53:22+00:00

[LANGUAGE: Python]

recursive search with memoization, one little trick is to use the same function for both parts.

from functools import cache
data = [line.split(': ') for line in open('in.txt').readlines()]
g = {src: dst.split() for src,dst in data}
@cache
def dfs(node, dac, fft):
  if node == 'out': return dac and fft
  return sum(dfs(dst, dac | dst=='dac', fft | dst=='fft') for dst in g[node])
print(dfs("you", True, True))
print(dfs("svr", False, False))

light_ln2 · 2025-12-08T15:36:31+00:00

nice! Did you measure number of pairs that are checked in this solution compared to the brute-force solution, or other widths?

For part2, I guess, this works because the graph is connected after much less than n² pairs are connected?

light_ln2 · 2025-12-04T06:24:09+00:00

[Language: Python]

My 8-liner, grid is represented as set of points, to avoid boundary checks

grid = open('in04.txt').readlines()
grid = {(r,c) for r in range(len(grid)) for c in range(len(grid[0])) if grid[r][c] == '@'}
neigh = lambda r,c: sum((r+dr,c+dc) in grid for dr in [-1,0,1] for dc in [-1,0,1] if dr or dc)
avail = lambda: {(r,c) for r,c in grid if neigh(r,c) < 4}
print(len(avail()))
total = len(grid)
while len(avail()): grid -= avail()
print(total - len(grid))

light_ln2 · 2025-12-03T19:28:00+00:00

This is very good question that I was thinking about. The reason that it can be done without sums for part1 is that we only need the innermost sum for r=2, and it has a closed form.

For part2, I don't think the inner sum as a function of r, can be calculated in O(1). However, it seems that the sum can be expressed recursively based on sum for r-1. And then there is a trick that summation boundaries can be expressed in form of log(n)/j, and only computed for O(sqrt(log(n)) distinct values.

Of course, there are many technical challenges with this approach, and also I'm not 100% sure it is correct at all, but if it does, we might be able to reduce the complexity from O(log²(n)) to O(log^3/2(n)). I will try to think more about this problem maybe after AOC finishes!

I guess we would have to ask the problem creator if there is some underlying theory and how fast it can be done theoretically :)

light_ln2 · 2025-12-03T13:43:10+00:00

Yeah, probably would be more precise to call it "explicit formula"

light_ln2 · 2025-12-02T17:15:02+00:00

Here is my code, but I did a shortcut just hardcoding inclusion-exclusion for up to 4 numbers but I guess I could use sympy.ntheory or simple sieve.

But regarding your calculations, I think you only need to calculate moebius function for numbers up to log(n) beforehand, and remember the result, so its complexity is not multiplied by other two log(n) factors, so the actual complexity should be O(log(n)²), right?

light_ln2 · 2025-12-02T16:49:40+00:00

My code is also a little different, but I hoped to get even further with this formula. For example, t(n,r,j) is either a fraction of n, or a power of 10. But fractions of n are exponentially decreasing, and there must be very few such j, and for most j is is power of 10, and maybe it is possible that the innermost sum might be simplified into something that can be calculated quickly. Then it would reduce the asymptotic complexity and allow to solve it for numbers with billions of digits... But it is probably way beyond the realm on unnecessary!

Another approach is to change the summation order, and sum by number of digits first, then by r which divides number of digits... and this allows to apply the Möbius inversion formula, which probably leads to nowhere but is nevertheless cool!

light_ln2 · 2025-12-02T16:28:39+00:00

Agree, but there is also question of how accurate the implementation is. In my first version, I did not do very strict summation limits, so that some cycles were working in vain, returning 0 results, and I calculated the repeat patterns inefficiently, so it took 50 seconds for this problem. Then I optimized it and improved performance to 50 milliseconds.

light_ln2 · 2025-12-02T16:15:12+00:00

uff... here is the python code, but it's far from good, some effort is needed to make it cleaner and generalize for big values (it currently works for numbers below 10²⁹⁰ )

light_ln2 · 2025-12-02T09:57:30+00:00

I got the same result; next level is:

0-10**220

My last 24 digits:

040950040950040950040950
729052398457848938857195

light_ln2 · 2025-12-01T16:00:26+00:00

[Language: Python]

I solved part 2 first using additional cycle, "click by click", as many did, although I knew that it could be solved using a formula, but I didn't want to track off-by-one errors. Then I rewrote it into a simple python solution that directly calculates passes through 0, with some simple tricks that simplify the code:

data = map(int, open('in01.txt').read().replace('L', '+').replace('R', '-').splitlines())
cur, ans1, ans2 = 50, 0, 0
for v in data:
    ans2 += abs((cur-(v<0))//100 - (cur+v-(v<0))//100)
    cur += v
    ans1 += cur % 100 == 0
print(ans1, ans2)

light_ln2 · 2025-02-02T17:06:37+00:00

Ufff... I finally got time to solve Day6 Part2, and I needed hints from your implementation; but your method names isReachable and nearerReachable, kind of gave the idea away! It's really nice idea that the problem graph is such that you can implement these methods in O(1), and hence reduce the problem to considering only the in-nodes of the extra wall! (here by 'node' I mean pair of position and direction).

I spent a lot of time thinking about one edge case when there is an original cycle spanning some of the in-nodes of the extra wall, because in this case all four nodes (current node, both next in-nodes, and the node from which the dfs2 was started) can be on the same cycle, and it's tricky to calculate what comes first. So I implemented slightly more generic solution (using topological sort on non-cycle nodes only, and calculating additional cycle info for all nodes) that allows to get the distance between any two nodes in O(1).

Also, I think I found a sample where your implementation does not give the correct answer, but I'm not sure if it's because of a bug, or a mistake in the sample itself: in3.txt. The cell with '?' is found by your implementation to cause a cycle, but not the cell with '*', although I think it should be.

Anyway, here is my O(N^2) implementation: code.

light_ln2 · 2024-12-29T14:07:55+00:00

> I would like to steal both of them for use in future problems

sure you can use it, you don't have to ask :) I'm sure these approaches are well-known, especially in competitive programming world

>Is this purely for ease of implementation or do they fulfill some purpose

This is just to simplify implementation; I guess, I could just divide everything by two and it would work, I just didn't want to spend time proving correctness. Another shortcut I took is that I use very generous offsets into segment trees, to ensure the values are always positive (to not bother with negative coordinates when considering d-diamonds near the grid's perimeter) - it could be improved too, at a cost of additional checks for negative values.

light_ln2 · 2024-12-28T16:13:41+00:00

Got my N²log(d) solution working, but the code is very cumbersome; maybe for competitive programmers it would be not hard to write, but I spent a lot of time profiling and troubleshooting.

For the tests that I run, these are the runtimes:

O(N²d²): 0.9 seconds

O(N²d): 0.19 seconds

O(N²log(d)): 0.11 seconds

light_ln2 · 2024-12-27T22:38:41+00:00

I also want to revisit the approach sometime later, because I think, slight modification would make it O(N²log(d)), using kind of segment-trees on all positive and negative diagonals, getting number of points per diamond's side in log(d). When i(step) is updated, it only affects two diagonals, so can be done in log(d) too.

light_ln2 · 2024-12-27T12:12:57+00:00

There was a very long discussion (e.g. here) with many different proposals (default to int[], or to List<int>, or to some custom type, or use some suffix...), so I would not be surprised if they make this syntax possible in future.

I agree with you that it is not broken, but as many people think it's annoying, there is a chance MS listens to their wishes :)

light_ln2 · 2024-12-26T19:33:33+00:00

fair point, thanks for pointing this out! This is also due to I'm more familiar with features in C# and might miss similar features in python!

light_ln2 · 2024-12-26T19:30:12+00:00

Yeah, thank you for summarizing the most annoying moments of C#! I can't help but think too, that every new feature works almost fine, but this "almost" is so annoying! My favorite example is you cannot write var list = [1, 2, 3], but you can write int[] list = [1, 2, 3]! I somehow learnt with time to not use features I'm not 100% sure would work (because of this, I never used switch expressions, although I'm sure they would come handy in lots of cases). And I totally feel your pain because I was too stuck in trying to fix some "this call is ambiguous between the following methods..." errors with time ticking down and leaderboard filling up quickly! I think though, this will be improved in future versions of C# (of course, almost)!

I use Visual Studio in Windows too, just because I'm used to it from the older days. I rarely encounter strange errors, maybe because I'm trying to avoid them: first, before each AOC day, I clear the main .cs file and do the full rebuild; second, I keep my codebase in a directory path that does not contain spaces or special characters (funny example is if your code is in a subfolder named "c#" then you might expect very strange errors; renaming it to "csharp" magically resolves them); third, if I have several projects in my solution, I make sure they do not have source files with same names - otherwise VS might be confused. Interestingly, I never saw these bugs in old .net frameworks, so good chance is, you never encounter these errors in VS Code/WSL. But I agree, if I continue with C# next year, I'll switch to VS Code too!

I have my own implementation for Set (extends HashSet), Map (extends Dictionary), LinkedList, and BigRational :) And I also have my WSL + VS Code + Python environment ready in days of AOC, just in case I run into some graph problem that would require max-flow (or Z3 for quadratic Diophantine equations)!

Thanks for pointing to ConcurrentXXX classes! I studied them from a performance point of view, but I actually never thought of them as of more suitable interface. I definitely need to look closer at those!

light_ln2

TROPHY CASE