diff options
Diffstat (limited to '2025')
| -rw-r--r-- | 2025/README.md | 36 |
1 files changed, 35 insertions, 1 deletions
diff --git a/2025/README.md b/2025/README.md index dc87240..09d97c1 100644 --- a/2025/README.md +++ b/2025/README.md | |||
| @@ -178,4 +178,38 @@ cases now. | |||
| 178 | ### Day 10: Factory | 178 | ### Day 10: Factory |
| 179 | 179 | ||
| 180 | Phew, this was a hard one! | 180 | Phew, this was a hard one! |
| 181 | (More details coming soon, for now read the code and the comments) | 181 | |
| 182 | Part 1 was quite easy, I just try all combinations of button presses | ||
| 183 | until one works. It still took me relatively long to type it out. | ||
| 184 | |||
| 185 | Part 2 was hard. Maybe not as hard to come up with as Day 9, but it | ||
| 186 | took me much longer to thing through and type the complete solution. | ||
| 187 | It is the first problem of this year's edition that I cannot fully solve | ||
| 188 | before going to work (problems come out at 6AM in my time zone). | ||
| 189 | |||
| 190 | So at first I tried to implement a recursive solution with memoization | ||
| 191 | (using Python's | ||
| 192 | [`functools.cache`](https://docs.python.org/3/library/functools.html#functools.cache)), but that was too slow. You can still check it out | ||
| 193 | in `10/b-recursive-slow.py`. | ||
| 194 | |||
| 195 | Then I thought about using linear algebra. I also had other ideas, | ||
| 196 | but one particular sentence in the problem's statement strongly hints | ||
| 197 | at that: *"You have to push each button an integer number of times; | ||
| 198 | there's no such thing as "0.5 presses" (nor can you push a button a | ||
| 199 | negative number of times)."* | ||
| 200 | |||
| 201 | Like, come on. This sentence makes no sense at all in the context | ||
| 202 | of this problem. It is only useful if you are already thinking about | ||
| 203 | using linear algebra to solve this, but somehow along your reasoning | ||
| 204 | you forgot that you are working with non-negative integers? | ||
| 205 | |||
| 206 | Anyway, I briefly tried using [numpy's linear system | ||
| 207 | solver](https://numpy.org/doc/stable/reference/generated/numpy.linalg.solve.html), | ||
| 208 | but it would have been more complicated to figure out how to use this | ||
| 209 | library in my case than to re-implement the necessary algorithms from | ||
| 210 | scratch. And so I rolled up my sleeves and started coding... after all, | ||
| 211 | it is not the first time I have to home-cook some linear algebra for an | ||
| 212 | AoC problem (see `../2023/24/24b.c`). | ||
| 213 | |||
| 214 | This time I left some comments in the code, so check out `10/b.py` if | ||
| 215 | you want to know the details. | ||
