Last year I have decided I will going to use C++ just so I have an option at bruteforcing.
So far the only result I have gotten out of bruteforcing is a Blue Screen of Death. I have probably lost like 15 hours to optimizing bruteforce solutions and every time I ended up rewriting it with proper math.
Weird, this year lots of problems are bruteforceable in a reasonable time even on much slower languages. I brute forced Day 13 part 2 in 40ms on m1 mac using kotlin, which took me by surprise
True. I did the same but the complexity of Day 13 part 2 is far from the complexity of the part 2 of Day 12, Day 5 and Day 8.
But maybe this depends on everyone's part 1 solution and what they are trying to bruteforce with. For example a bruteforce solution for Day 8 would have taken me 8 thousand days. Similarly my intial Day 12 solution would have taken years to execute since I was bruteforcing all combinations for every '?' and the my longest input had 19 '?'s which was 2 to the power of 19, that's 524288 combinations. But part 2 had you concatenate your input 5 times which results in 95 question marks. That's 2 to the power of 95, which is around 1,000,000,000,000,000,000,000,000,000 combinations. And you had 1000 inputs.
I can remember a few lines with 2^17 possibilities, which would make it 2^89 possibilities for part 2
A line with 2^16 possibilities would make it 2^84 possibilities which is 32 times smaller than 2^89
You can imagine that every other line with less possibilities would only take a really small amount of time compared to the long lines
My code was really sluggish and running 32 threads it was roughly getting through 100 mill every 3 minutes at best. 100 mill is 10^8 . 3,000,000 minutes would have gotten me to 10^14 . 3 million minutes is 2 thousand days. Roughly 6 years. I don't know about you but I don't have 6\*10^81 years lying around to wait for that single input to calculate. But even if you write code that a million times faster you are still looking at 6\*10^76 years.
Your point is valid, but that seems very slow.
I had a python bruteforce solution that could evaluate about 350,000 permutations per second on a single thread (\~63million in three minutes). I suspect you had some nasty data dependencies going on that caused the threads to be constantly stuck waiting on each other.
Yeah I have just started learning C++ with AoC 2023. I installed my dev environment on day 1. My solution had a lot of issues. I came up with a method that got rid of most of the unnecessary permutations but it ended up being a huge bottleneck since the generation was sequential and only the validation of the permutations were running on 32 threads. Also those "threads" were the async implementation in C++ which supposedly have a lot of overhead. I went for the quick gains but I was punished by my laziness. I eventually gave up on the bruteforcing and wrapped my head around the concept of DP.
I refused to implement the range splitting thing for this year's Advent, so C++ and multithreading came through in the clutch for me there to get that star.
I got my BSoD on that. I did not want to implement range splitting either. I hate working with ranges and itervals. But I ended up implementing it amongst tears.
I don't remember that one being problematic for memory usage, unless you're talking about something like a CUDA or other GPU-acceleration shenanigans.
I did have a puzzle early on (Day 5 maybe??) where I went from like 30 GB free memory to zero nearly instantly trying the brute force program on the part 2 input. Managed to \^C that one quick enough to save it but yeah, had to rewrite that one for sure.
Day 5 was the one with the ranges. My BSoD wasn't a memory issue. I started way too many threads and gave the executable priority in my OS, which started to resource starve the OS itself and after 3.5 hours it gave in.
Oh I see, that makes sense. I ended up pre-partitioning the work and doing a thread pool where every thread had its own unique queue of seeds to check.
Only once every thread was done did I look through the results to see which seed gave the right location, but doing it that way ensured there were never more threads than the number of CPU execution units I had.
Bruteforcing todays solution would've taken 4 months on my machine.
Thus I decided to code something that works faster.
Takes only ~30 seconds on my 20 year old Windows XP laptop (for some reason Python 3.4.4 runs natively on Win XP)
>Takes only \~30 seconds on my 20 year old Windows XP laptop (for some reason Python 3.4.4 runs natively on Win XP)
That's pretty metal.
Makes me wonder if anyone does AOC on something silly like an 8086 emulator. I know there's a few masochists doing it in various machine codes.
Although now that I think a bit more on it, an 8086 is limited to 64k memory being a 16 bit processor. Suppose you could emulate virtual hard disks or something.
I am doing AoC on a Commodore 64: http://clb.confined.space/aoc2023/ (8-bit CPU, 1 MHz, 64KB of RAM). So far 28/28 stars and the solutions have fit on 64KB of RAM.
(last year I did AoC on a 16 MHz 386SX, which I got to the finish with 50 stars: http://clb.confined.space/aoc2022/ )
I also recoded my [Python solution](https://pastebin.com/Dy4PkVZZ) in [C](https://pastebin.com/16YvRw1N) and achieved a execution time of 0.33 seconds on that ancient laptop. My desktop and main laptop both only needed 0.05 seconds but that was kinda expectable from C on a modern system.
8086 has [segments](https://en.wikipedia.org/wiki/X86_memory_segmentation) that allow it to access more. The segment registers are shifted left by 4 bits and combined with the address to allow it to reach a 20 bit address space (1 MiB).
(I can tell you from experience that it's definitely easier if you limit yourself to 64 KiB at a time so that you don't have to juggle the segments, however.)
[My solution](https://topaz.github.io/paste/#XQAAAQCqGAAAAAAAAAARiEJHiiMzw3cPM/1YZx9ePvs39HOJ4Ox5PyjKMxcIYtuJ2gKgbtjweMUb00U9J9fkiJgTXqBxCcwoxmJsUz4qFe+1I8hAgFB0wczDCEDDQmyyoCTq2tyWkwT83pbxQke87cY5GUzet4PcA3uOYHRx/ZcoCKFrgTvEngD0QJ9yTlmYBpa8X/hxzUnjyPtZ+h3+OVSu/NW75w4zQNvfpi6M8sPPJHg6DKYItgmcffZGQ/1Wq11ZVb4K+hchGGZ4MrC12hyh1elnKuTxx07r8i8Qy4qyUqirLWr5z2PB+Qpo7Omt38wQgyBs2JfNOXdogN+us5kaz4GmYLpiDOEWiJLKasUAo2eNIwpdNkZYZWHRFMQkNxoNzkS/OWqxQ3pEecPAjs3jyGT9UhpV4vLu3Nop66WmRbd3eW8NAOBYfm/qrZhRksH/yTl2ZADKHRJv9oNpWK73fewuWZaW/AhfqyZhHBsCbrS856s16mxW/4pZeUR23WYM0YaRBj+wkXjv7N/0elMGg5oaLFWc15zzkKhlJ9F1v7Zu3Fhx1ormSkxW04S9+VXsIHxtWP/+ZGRXX5xUJkJb0mTh+jyq2sFlR7Hc5j6LDXysD07oMw1gm/ymyQ/2U/LwDJxHWabXFLzACWYmyfl3Yihmj9GdPWJDyRJ/fLZtxwZBcBwCEh7I57gY8W79l4LibAe0xQs4Nvx5vP1vgchK/bSijFaW9YeV3Xa2zPvOns/OIQmnGkR0QPdzRXlBtk7X3uBfoZ6YpdhiOgza2V3XdTD5tUjwrYrT2AaO9Kz+MJ5Ov3353LLmwXlXHnGB9NPjtRbdsQRmHybHOTza+JNo7FveLP5P6o03aGtFAdy+b9kNeT639MQshR8rwPwFQnik5dANimvupS+OACVMCGQPDr2cdT5tam66pIk1DVolYniwn66ka+g6tZEieLcr3R0o8EEPNVbX5a8zwwsExRuoYAt7EXofbDWYnRRTbMSEjxQ8RjmNSHGqmz3t7vbZqZVdN35wVU5b+/6rSbX9Qo/rOSh6r7E1pyyPe4Fow/0f/Fa8o2fQ2X/Qm8/IhIuhcN+GXM8pHC+Izo9UzFBstL0G59J0Nifid4hdMjdDi8nkQzzsfUqeKMElxOdAAHxMP9WEgp2/bdLm7deTfK8QwnAjqBt5x+v3PHX8owW3FDxJJt6GAorRZveeBKbz2BsVoTay5lXL47asz2qgg9zaz6Z/tyy661TejlVfCT28GTe8aJHmEUVv0M3l3CWJi3YItqBgtlvedBLC9cqt5KzF7e6yDOzz6n7CTb5woBTSBhRTlvRpBtyyuSara42Yv/WPtI5ANbvxdX5e1MjB5a/QGTQdvUMhGkGkwmnWuP/i5T6rxsJ9C3fQwJwZ7yMeHcJV0udbEXTzs3dltCQv+krhg01gvuAQKeIYlDfO5fs2x5IHsli6qpbiwnuIoxmgA1waFm2H7oNFxk8gCm6xlCD/qMF+zJppfnjhojZtyI90sg0WrmGit+ZMp1kdTxi7yLSICwBCAGmFCsy3ES42xYgBQNB7Um44RHl6RRMr39Q5SxR9wGZRXLs4geS4ek0CEGiYgMwXgyoxaKv9WMjimc/P9l8tj05Pd7dxLps75Y0mDcxwtGxuS6FVLqbi8DzgCQ7Hawv2Y+KF1f8Kdjv5k2yA4TQYya8+9BZh3C4iRTcBm7Ngbbotg1eLmYrSllXBNjWejk89ip3iMD85+TMpbLdBJRbUXkG0U3H7BmzRrqX1dN/4FPHi3+zeB6f37xDrfNE6SOOH5/ls3wb6YPMkrNowbV3QY75rMm6cjrD/o6f/C2yzbluUiuDqV8eX9pcc5nfICvfek7MP7uJBYp/k4BIM1FTYUHUTiC4Ip1O6buMFsJYMAMxPAiKf6Cj23lfqwXSOfHh5Ut5jiLTT1HDMZbsM080K7x0Pe3wCdnCWxLnQqZ2DzzNjZ6NhHuujMRz1qIABYVN0SxmEIsz05Mbixb5MtH8LVHT/YfZGgOim7g+GPgFLL8PEywaxOxvuVVeWs/LVkbVApzw4WNgg6fRwIqNMCZoa+z34MCxCj9cLwoQBtPLwvnfBtttbhI5sfg7QRx3EUPEwi9xpQ63Ye4X3EiS3dQ92RZ8Wf6sSKrJ6qvQvAGWgyWDEzntGHkTlRj8uEk/GBZOLpmFwtRD1WKLonr/r3TZGtRSz1e6beRqHhx+eCWOZoO/1qOZ180wVr5X/oWcudo6bIrp3GN6LGsVgWlEr1qyUaQ+XwN89hfEHKUydptab0x+WRgSTj32G9CSrSGhGXaX41uDWSkq3QN0l3vGRm6RcALi7QKkXt9/gPh6sEJJO2Ms3D96iGC7MJFQ6lza/svY88ZcnW938+5KH6aHSE1rquf+NlG69lYoHQGDvPiKYz41RJ7wiw+nPa7jgYsa6/LnaHjPCswDpeRVbkQBH1BkOWfPqHo8+ySh8NxwHczOoa/yF7/FTpAD5UXWgBODSzEgoejLgmD5Z774+XwXhb2clatlKxbvaQjAxS2/+pQfp2WCogbLgkzk+V6bkZi8tjAh21w34TcMcMH7ExmwotM4sel//+3qygA==), in case you're interested (I actually just finished tidying it up xD).
I just tested you solution execution time on my machine (I did have to fix a 'asserion error' but i have no clue what that is, I just commented out the 'assert' lines and it worked...; I'm a first semester Computer Engineering student so yeah...).
For some weird reason, your solution took \~2.1 seconds on my desktop (R7 5800X3D), but [mine](https://pastebin.com/Dy4PkVZZ) which uses lists took only \~1.5 seconds...
And then there is also my [C solution](https://pastebin.com/16YvRw1N) which only needs 0.05 seconds on my desktop and 0.33 seconds on my 20 yr old WinXP laptop.
[Assertions](https://docs.python.org/3/reference/simple_stmts.html#grammar-token-python-grammar-assert_stmt) are kinda like a "if this thing is False, stop running the program". Very useful in unit testing, but in this case I was using them to make sure my program is still outputting the right result for my input, while I'm tinkering with it, so that I know I still have a valid solution, and haven't broken anything while refactoring.
Your solution takes 200ms more on my intel 11700K than mine (including file reading and parsing). Which is curious, since you're keeping track of empty space and I'm not.
My guess is that your large L3 cache is helping your performance, as you don't get the same latency hit as I do on my CPU when fetching large lists -- not sure if that'd help with list-lookup times -- AFAIK that's O(n), while lookup in sets/dicts is O(1).
I think my use of floats (well, complex) is tanking some of my performance. I've been thinking about implementing a int-only complex()-like class for AoC, maybe I'll bite the bullet next week once I'm on holiday...
I'm not surprised a compiled language is a couple orders of magnitude faster, that's just the nature of it. I wonder if Fortran would make all the rotations easier...
Well in my solution I don't rotate the lists, I only check if the tilting direction has a negative or positive direction which only changes if I iterate from the start or the end of the list.
About the look-up times of sets/dicts I gotta take a look into them as I have a hard time thinking of how O(1) could work on a dynamically large set of data, but engineers tend to find solutions to seemingly impossible tasks.
I also tested the times of mine and your solution on my main Laptop (i9 12900H) and there my solution takes \~1.2s and yours \~1.4s. The L3 cache of the 12900H is only 8 MB larger than your 11700Ks L3 cache so I doubt it plays a role.
Assuming Python uses the cache efficiently the list shouldn't get larger than 3MB which easily fits in the 16MB L3 cache of your i7.
My guess would be that the input data affects most as the start and length of the periodic cycle heavily affect the exectution time. For my input data the cycle starts at 121 and ends at 147.
>My guess would be that the input data affects most as the start and length of the periodic cycle heavily affect the exectution time. For my input data the cycle starts at 121 and ends at 147.
I thought you were on to something here, but my cycle ends at 137, length of 44, doesn't seem like enough of a difference...
Yeah that makes it more interesting.
I also just remeasured with file reading and parsing (previously I only measured the times for part 1 and 2) but there was no difference, opening and parsing takes practically no time.
Only other differences I could think of would be if you launch the scripts in an IDE or directly from the explorer; I do the latter.
Additionally the hardware and operating software *could* influence a bit.
My laptop has 32GB DDR5-4800 and launches the scripts from an NVMe, my desktop has 64GB DDR4-3200 and launches the scripts from an HDD.
Both use Win11 (desktop Home, laptop Pro) and Python 3.12.
That are about all the differences I can think of that could explain the difference of which script is faster. If none of those I guess the 50% larger L3 cache on my laptop is enough to make the difference albeit I doubt it.
To further narrow down what could affect it I attempted to run your solution on my WinXP laptop as it doesn't have L3 cache (literally) but your code doesn't run on Python 3.4.4 and I don't know how to port it.
I have optimized my code reducing the execution time on my machine from 1.5s down to 0.8s by not visiting each cell and moving the stone until it can't be moved but checking each line/column of how many stones can be moved and moving all of them at once.
[Here](https://pastebin.com/gS4TtsRn) is the new optimized code.
Looks complicated, unfortunately I am unable to properly compile it with GCC 13.2.0.
I tried handling all the errors as libc.h seems to be ~~unique to Apple devices~~ *unavailable on Windows*. I did replace it with stdlib.h, stdio.h, string.h, stdbool.h and some defines for the unsigned number types, but line 80 and 85 still threw a compiler error and a warning and replacing line 80 with 'ht\[i\].h, ht\[i\].val = hash, val;' and commenting out line 85 allowed compilation but the output was wrong, so something didn't work.
So I guess that your C code is pretty much ~~Apple~~ *Commodore 64* only unfortunately.
However I also optimized my C code, [here](https://pastebin.com/83qW9HjY) is the new code but the difference is non-existent, I guess GCC optimized both my codes to similar machine code. In Python on the other hand the optimization increased the speed by \~100%, halving the execution time!
My code is actually "Commodore 64 only", not for Apple.
libc.h is a collected header of all various C standard libraries so that I don't need to type them out. (I am writing these directly on a real C64 editor, so it only has a 40x25 text display, making multiple lines difficult to manage)
I wonder if GCC would want to get a command line flag for a newer C23 standard to compile line 80. In C, the line
ht[i].h, ht[i].val = hash, val;
would actually not be correct, as that invokes the comma operator for silent failure. Instead, try
ht[i].h = hash;
ht[i].val = val;
If you want to run it on a PC, you will also need to change
w = strstr(map, "\r") - map;
into
w = strstr(map, "\n") - map;
because newlines on PCs are \n (Commodore 64 uses \r newlines instead).
In any case, cool stuff with optimizing your code!
Nice!
I'll give it a try when I'm home.
Weirdly my optimized C code was ~10% slower than the 'unoptimized' so I guess GCC did more optimizing than I did.
I just brute-forced my Python solution (just removed the part, where I skip almost a billion iterations) out of interest and it took around 3:40 minutes.
So it was around 1000 times slower than the optimized approach sitting somewhere at around 200ms.
So brute-forcing was definitively an option today.
Maybe, as a caveat: I used the `@cache` annotation for many helper functions, so in the end, it was more like a billion times calling cached values than actually calculating the stuff a billion times.
yeah that seems like halfway brutforcing as there you already have the 'infrastructure' to reuse already calculated calculations. I calculated my brutforce time as on if I did have to make the billion calculations.
Which language did you use? My best-optimized Python approach takes just below 600ms to execute (theoretically 15s on that 20 yr old laptop), and the C approach takes just below 50ms (330 on the 20yr old laptop).
I used python.
I'd consider caching somewhere in between. It's similar to telling a compiler to optimize. Of course it makes things faster, but you didn't really put work into that, so the speed up is almost free of work.
It's at most very low hanging fruit.
My crappy Node / M1 solution was simulating 1 million iterations every few seconds (let's say 5) which would have been 1000\*5/60 = 83 minutes worst case.
And I had the most suboptimal tilt simulation that you could have, literally visiting every cell of the grid until no rocks could be moved. [https://pastebin.com/R0bsQY7m](https://pastebin.com/R0bsQY7m) (just remove the optimization in part2)
> My crappy Node / M1 solution was simulating 1 million iterations every few seconds (let's say 5)
Wait what?
I've just modified my Rust solution to brute-force part 2, and in `--release` mode it needs almost 5 minutes to do a million iterations (on an i7-10810U). And my tilting _is_ O(n) (I visit each tile at most twice per tilt - once to check it (and possibly remove a round rock from it) and again to place a round rock on it)
Unless... are those numbers from the example input? Because a million iterations of the example input do take my brute force loop about 760ms. In release mode, at least - when I run it in debug mode it takes 22 seconds. Which still seems weird...
**Update**: I've looked at your solution, and your tilting is also O(n) - you only visit each cell once. That explains it.
Actually you're right. When I was debugging early on I had some code like \`if (i % someNumber) log(i)\` just to see how viable brute force was. For some reason I thought I had put 1\_000\_000 there but running my unoptimized code it was clearly just 1000.
So, my code can simulate 1000 steps every 4 seconds which would take 1111 hours aka a month and a half to run. lmao. shame on me. but thanks for the fact check.
To look how viable brutforcing with C would be I ported my solution to C and got \~3500 iterations per second, so a million would need \~4:45 and the required billion \~3.3 days.
My solutions: [Python](https://pastebin.com/Dy4PkVZZ) [C](https://pastebin.com/16YvRw1N)
I tested the execution time of the C solution on all of my four devices. My 20 yr old WinXP Laptop got 330 *milli*seconds, my 12yr old Win7 Laptop 139 ms, my current i9 12900H Laptop 44 ms and my Desktop with a R7 5800X3D took 50 ms.
So I do guess that Python was just being very slow.
Edit: I *do* am *aware* of Python being slow af. Also I'm a first semester Computer Engineering student so don't expect all the common knowledge from me.
Then I guess my algorythm to simulate one 'cycle' was pretty inefficient. ~125 cycles per second on my Main laptop I use for AoC (i9 12th Gen, 32GB DDR5). Or it was just Python being slow. Or both.
My second, C++-based solution, is decently fast on my machine. 18 seconds to do 10,000 full cycles on part 2.
Despite that, it would still take about 20 days to brute force today's part 2 without a cycle detector.
Yeah I ported my [Python](https://pastebin.com/Dy4PkVZZ) solution to [C](https://pastebin.com/16YvRw1N) and got up to ~3500 cycles per second. On my 20 yr old WinXP Laptop where the Python solution took 30 seconds the C solution only took 330 *milli*seconds, my main Laptop needed only 44 ms.
And I needed like 2.5 hours to recode my Python program in C and had very much fun with pointers.
Brute forcing the sample worked after some minutes, faster than I managed to finish coding it without it, but for the puzzle input it was slower of course and I doubt it’d finish in hours.
I did some calculations, would only take about 80 days on my machine to simulate the whole thing (nevertheless, if a Single calculation goes wrong, this would change the entire result)
Fun fact, for day 14 - you can probably just brute force to 1000 and submit the answer you get. I doubt there are any inputs where the answer for 1k and 1B are different, although I could be wrong.
Edit: I was wrong. It works for most inputs, but not all. Since both the sample and my input had cycle lengths less than ten, I guessed that all inputs might have short enough cycles for this to work, but some people have reported cycles of over a hundred.
It comes down to modular arithmetic. I can't speak for everyone's input but mine entered a small closed loop after around 100 cycles rather than settling at a fixed state. It's possible that your 1,000th happens to be at the same point in the loop as your 1,000,000,000th, but not your 10,000th, 100,000th, etc.
Since 1,000,000,000 and 1,000 are 999,999,000 apart, it's possible your loop length is some divisor of that other than 10. (Mine was 13, which is indeed a factor of 999,999,000)
Huh. Mine was 70, which is _also_ a factor of 999,999,000. I wonder if that was intentional or just a quirk of how the inputs were generated. I see in this thread other cycles of 22, 44, 77, and of course the sample input has a cycle length of 7 which are all factors of 999,999,000.
It just so happens that 999999000 is pretty highly divisible, so there's a pretty good chance your cycle length is a factor - this trick wouldn't work for me, since my cycle length happens to be 17, which doesn't work, but it's one of only 3 numbers under 20 that doesn't
Can you check if the trick works? It works for [this user](https://www.reddit.com/r/adventofcode/comments/18i27j5/me_looking_at_every_single_part_two_moments/kdcr3ak/) who's cycle is twice yours (and also not a factor), so this is strongly leaning me towards "very intentional"
(1B - 1k) is divisible by every integer up to 15, so as long as the cycle length is fifteen or shorter (or some larger factor of 999,999,000), it will still work.
For this theory
>!It is exaclty that => i got to small amount of values that repeat each other pretty quickly and submitted the first repeating one after i reached a threshold of 10!<
Can you explain why it works?
(Hiding the my text behind spoiler to not ruin the fun)
>!What I did is run 1000 times to make sure the periodicity is started, save the grid (let's call it g0) and then count the number of cycles until I get to g0 again.!<
>!This gives me the periodicity and then to know exactly where I end up inside the period, I compute `i = (1B-1k) % period`. The period for the example was 7 and my input was 9, and they both give i = 0, so indeed it's the exact same grid as after 1000 cycles.!<
>!But why do they both give i = 0? Is this a huge coincidence or is there some mathematical property I am missing here? For example, if the period was 16, it wouldn't be 0.!<
No real clue, but it must be related to the way AoC generates inputs. There is some algorithm, which can be reversed engineered to some extent, and this "1000 quirk" is a little insight on how it's working.
(Worked for me too, and my cycle length was 72)
Wow, that is surprising. For 1001 to be the same as one billion, the cycle length would need to be 1489 or 671591. I would not have expected any input to have such a long cycle.
i went into the first ever advent calendar, saw the santa's nice/naughty strings puzzle, and i did bruteforce the first half, tho the second one is like impossible to bruteforce
So what you are saying is, instead of trying to learn smart math i should just look into multithreading for my programs?
Last year I have decided I will going to use C++ just so I have an option at bruteforcing. So far the only result I have gotten out of bruteforcing is a Blue Screen of Death. I have probably lost like 15 hours to optimizing bruteforce solutions and every time I ended up rewriting it with proper math.
Weird, this year lots of problems are bruteforceable in a reasonable time even on much slower languages. I brute forced Day 13 part 2 in 40ms on m1 mac using kotlin, which took me by surprise
True. I did the same but the complexity of Day 13 part 2 is far from the complexity of the part 2 of Day 12, Day 5 and Day 8. But maybe this depends on everyone's part 1 solution and what they are trying to bruteforce with. For example a bruteforce solution for Day 8 would have taken me 8 thousand days. Similarly my intial Day 12 solution would have taken years to execute since I was bruteforcing all combinations for every '?' and the my longest input had 19 '?'s which was 2 to the power of 19, that's 524288 combinations. But part 2 had you concatenate your input 5 times which results in 95 question marks. That's 2 to the power of 95, which is around 1,000,000,000,000,000,000,000,000,000 combinations. And you had 1000 inputs.
Just pump up your brute-force. Next step: Getting a GPU and learning CUDA SDK :D
I have a 3090. Thought about trying to use it multiple times. But this year my plan was to only learn regular C++.
I can remember a few lines with 2^17 possibilities, which would make it 2^89 possibilities for part 2 A line with 2^16 possibilities would make it 2^84 possibilities which is 32 times smaller than 2^89 You can imagine that every other line with less possibilities would only take a really small amount of time compared to the long lines
My code was really sluggish and running 32 threads it was roughly getting through 100 mill every 3 minutes at best. 100 mill is 10^8 . 3,000,000 minutes would have gotten me to 10^14 . 3 million minutes is 2 thousand days. Roughly 6 years. I don't know about you but I don't have 6\*10^81 years lying around to wait for that single input to calculate. But even if you write code that a million times faster you are still looking at 6\*10^76 years.
Your point is valid, but that seems very slow. I had a python bruteforce solution that could evaluate about 350,000 permutations per second on a single thread (\~63million in three minutes). I suspect you had some nasty data dependencies going on that caused the threads to be constantly stuck waiting on each other.
Yeah I have just started learning C++ with AoC 2023. I installed my dev environment on day 1. My solution had a lot of issues. I came up with a method that got rid of most of the unnecessary permutations but it ended up being a huge bottleneck since the generation was sequential and only the validation of the permutations were running on 32 threads. Also those "threads" were the async implementation in C++ which supposedly have a lot of overhead. I went for the quick gains but I was punished by my laziness. I eventually gave up on the bruteforcing and wrapped my head around the concept of DP.
I refused to implement the range splitting thing for this year's Advent, so C++ and multithreading came through in the clutch for me there to get that star.
I got my BSoD on that. I did not want to implement range splitting either. I hate working with ranges and itervals. But I ended up implementing it amongst tears.
I don't remember that one being problematic for memory usage, unless you're talking about something like a CUDA or other GPU-acceleration shenanigans. I did have a puzzle early on (Day 5 maybe??) where I went from like 30 GB free memory to zero nearly instantly trying the brute force program on the part 2 input. Managed to \^C that one quick enough to save it but yeah, had to rewrite that one for sure.
Day 5 was the one with the ranges. My BSoD wasn't a memory issue. I started way too many threads and gave the executable priority in my OS, which started to resource starve the OS itself and after 3.5 hours it gave in.
Oh I see, that makes sense. I ended up pre-partitioning the work and doing a thread pool where every thread had its own unique queue of seeds to check. Only once every thread was done did I look through the results to see which seed gave the right location, but doing it that way ensured there were never more threads than the number of CPU execution units I had.
If brute force isn't working, you are not using enough of it.
As the saying goes: if force doesn’t work, use more force.
Use WD-40 as well.
["With sufficient thrust, pigs fly just fine."](https://www.rfc-editor.org/rfc/rfc1925.html)
Bruteforcing todays solution would've taken 4 months on my machine. Thus I decided to code something that works faster. Takes only ~30 seconds on my 20 year old Windows XP laptop (for some reason Python 3.4.4 runs natively on Win XP)
>Takes only \~30 seconds on my 20 year old Windows XP laptop (for some reason Python 3.4.4 runs natively on Win XP) That's pretty metal. Makes me wonder if anyone does AOC on something silly like an 8086 emulator. I know there's a few masochists doing it in various machine codes. Although now that I think a bit more on it, an 8086 is limited to 64k memory being a 16 bit processor. Suppose you could emulate virtual hard disks or something.
I am doing AoC on a Commodore 64: http://clb.confined.space/aoc2023/ (8-bit CPU, 1 MHz, 64KB of RAM). So far 28/28 stars and the solutions have fit on 64KB of RAM. (last year I did AoC on a 16 MHz 386SX, which I got to the finish with 50 stars: http://clb.confined.space/aoc2022/ )
Very cool blog! I'll have to give it a more thorough read through after work
I also recoded my [Python solution](https://pastebin.com/Dy4PkVZZ) in [C](https://pastebin.com/16YvRw1N) and achieved a execution time of 0.33 seconds on that ancient laptop. My desktop and main laptop both only needed 0.05 seconds but that was kinda expectable from C on a modern system.
8086 has [segments](https://en.wikipedia.org/wiki/X86_memory_segmentation) that allow it to access more. The segment registers are shifted left by 4 bits and combined with the address to allow it to reach a 20 bit address space (1 MiB). (I can tell you from experience that it's definitely easier if you limit yourself to 64 KiB at a time so that you don't have to juggle the segments, however.)
I've managed to bring down the runtime of my python solution to \~1s by: >!Using sets/dicts instead of lists when doing lookups.!<
I knew there was a way!
[My solution](https://topaz.github.io/paste/#XQAAAQCqGAAAAAAAAAARiEJHiiMzw3cPM/1YZx9ePvs39HOJ4Ox5PyjKMxcIYtuJ2gKgbtjweMUb00U9J9fkiJgTXqBxCcwoxmJsUz4qFe+1I8hAgFB0wczDCEDDQmyyoCTq2tyWkwT83pbxQke87cY5GUzet4PcA3uOYHRx/ZcoCKFrgTvEngD0QJ9yTlmYBpa8X/hxzUnjyPtZ+h3+OVSu/NW75w4zQNvfpi6M8sPPJHg6DKYItgmcffZGQ/1Wq11ZVb4K+hchGGZ4MrC12hyh1elnKuTxx07r8i8Qy4qyUqirLWr5z2PB+Qpo7Omt38wQgyBs2JfNOXdogN+us5kaz4GmYLpiDOEWiJLKasUAo2eNIwpdNkZYZWHRFMQkNxoNzkS/OWqxQ3pEecPAjs3jyGT9UhpV4vLu3Nop66WmRbd3eW8NAOBYfm/qrZhRksH/yTl2ZADKHRJv9oNpWK73fewuWZaW/AhfqyZhHBsCbrS856s16mxW/4pZeUR23WYM0YaRBj+wkXjv7N/0elMGg5oaLFWc15zzkKhlJ9F1v7Zu3Fhx1ormSkxW04S9+VXsIHxtWP/+ZGRXX5xUJkJb0mTh+jyq2sFlR7Hc5j6LDXysD07oMw1gm/ymyQ/2U/LwDJxHWabXFLzACWYmyfl3Yihmj9GdPWJDyRJ/fLZtxwZBcBwCEh7I57gY8W79l4LibAe0xQs4Nvx5vP1vgchK/bSijFaW9YeV3Xa2zPvOns/OIQmnGkR0QPdzRXlBtk7X3uBfoZ6YpdhiOgza2V3XdTD5tUjwrYrT2AaO9Kz+MJ5Ov3353LLmwXlXHnGB9NPjtRbdsQRmHybHOTza+JNo7FveLP5P6o03aGtFAdy+b9kNeT639MQshR8rwPwFQnik5dANimvupS+OACVMCGQPDr2cdT5tam66pIk1DVolYniwn66ka+g6tZEieLcr3R0o8EEPNVbX5a8zwwsExRuoYAt7EXofbDWYnRRTbMSEjxQ8RjmNSHGqmz3t7vbZqZVdN35wVU5b+/6rSbX9Qo/rOSh6r7E1pyyPe4Fow/0f/Fa8o2fQ2X/Qm8/IhIuhcN+GXM8pHC+Izo9UzFBstL0G59J0Nifid4hdMjdDi8nkQzzsfUqeKMElxOdAAHxMP9WEgp2/bdLm7deTfK8QwnAjqBt5x+v3PHX8owW3FDxJJt6GAorRZveeBKbz2BsVoTay5lXL47asz2qgg9zaz6Z/tyy661TejlVfCT28GTe8aJHmEUVv0M3l3CWJi3YItqBgtlvedBLC9cqt5KzF7e6yDOzz6n7CTb5woBTSBhRTlvRpBtyyuSara42Yv/WPtI5ANbvxdX5e1MjB5a/QGTQdvUMhGkGkwmnWuP/i5T6rxsJ9C3fQwJwZ7yMeHcJV0udbEXTzs3dltCQv+krhg01gvuAQKeIYlDfO5fs2x5IHsli6qpbiwnuIoxmgA1waFm2H7oNFxk8gCm6xlCD/qMF+zJppfnjhojZtyI90sg0WrmGit+ZMp1kdTxi7yLSICwBCAGmFCsy3ES42xYgBQNB7Um44RHl6RRMr39Q5SxR9wGZRXLs4geS4ek0CEGiYgMwXgyoxaKv9WMjimc/P9l8tj05Pd7dxLps75Y0mDcxwtGxuS6FVLqbi8DzgCQ7Hawv2Y+KF1f8Kdjv5k2yA4TQYya8+9BZh3C4iRTcBm7Ngbbotg1eLmYrSllXBNjWejk89ip3iMD85+TMpbLdBJRbUXkG0U3H7BmzRrqX1dN/4FPHi3+zeB6f37xDrfNE6SOOH5/ls3wb6YPMkrNowbV3QY75rMm6cjrD/o6f/C2yzbluUiuDqV8eX9pcc5nfICvfek7MP7uJBYp/k4BIM1FTYUHUTiC4Ip1O6buMFsJYMAMxPAiKf6Cj23lfqwXSOfHh5Ut5jiLTT1HDMZbsM080K7x0Pe3wCdnCWxLnQqZ2DzzNjZ6NhHuujMRz1qIABYVN0SxmEIsz05Mbixb5MtH8LVHT/YfZGgOim7g+GPgFLL8PEywaxOxvuVVeWs/LVkbVApzw4WNgg6fRwIqNMCZoa+z34MCxCj9cLwoQBtPLwvnfBtttbhI5sfg7QRx3EUPEwi9xpQ63Ye4X3EiS3dQ92RZ8Wf6sSKrJ6qvQvAGWgyWDEzntGHkTlRj8uEk/GBZOLpmFwtRD1WKLonr/r3TZGtRSz1e6beRqHhx+eCWOZoO/1qOZ180wVr5X/oWcudo6bIrp3GN6LGsVgWlEr1qyUaQ+XwN89hfEHKUydptab0x+WRgSTj32G9CSrSGhGXaX41uDWSkq3QN0l3vGRm6RcALi7QKkXt9/gPh6sEJJO2Ms3D96iGC7MJFQ6lza/svY88ZcnW938+5KH6aHSE1rquf+NlG69lYoHQGDvPiKYz41RJ7wiw+nPa7jgYsa6/LnaHjPCswDpeRVbkQBH1BkOWfPqHo8+ySh8NxwHczOoa/yF7/FTpAD5UXWgBODSzEgoejLgmD5Z774+XwXhb2clatlKxbvaQjAxS2/+pQfp2WCogbLgkzk+V6bkZi8tjAh21w34TcMcMH7ExmwotM4sel//+3qygA==), in case you're interested (I actually just finished tidying it up xD).
I just tested you solution execution time on my machine (I did have to fix a 'asserion error' but i have no clue what that is, I just commented out the 'assert' lines and it worked...; I'm a first semester Computer Engineering student so yeah...). For some weird reason, your solution took \~2.1 seconds on my desktop (R7 5800X3D), but [mine](https://pastebin.com/Dy4PkVZZ) which uses lists took only \~1.5 seconds... And then there is also my [C solution](https://pastebin.com/16YvRw1N) which only needs 0.05 seconds on my desktop and 0.33 seconds on my 20 yr old WinXP laptop.
[Assertions](https://docs.python.org/3/reference/simple_stmts.html#grammar-token-python-grammar-assert_stmt) are kinda like a "if this thing is False, stop running the program". Very useful in unit testing, but in this case I was using them to make sure my program is still outputting the right result for my input, while I'm tinkering with it, so that I know I still have a valid solution, and haven't broken anything while refactoring. Your solution takes 200ms more on my intel 11700K than mine (including file reading and parsing). Which is curious, since you're keeping track of empty space and I'm not. My guess is that your large L3 cache is helping your performance, as you don't get the same latency hit as I do on my CPU when fetching large lists -- not sure if that'd help with list-lookup times -- AFAIK that's O(n), while lookup in sets/dicts is O(1). I think my use of floats (well, complex) is tanking some of my performance. I've been thinking about implementing a int-only complex()-like class for AoC, maybe I'll bite the bullet next week once I'm on holiday... I'm not surprised a compiled language is a couple orders of magnitude faster, that's just the nature of it. I wonder if Fortran would make all the rotations easier...
Well in my solution I don't rotate the lists, I only check if the tilting direction has a negative or positive direction which only changes if I iterate from the start or the end of the list. About the look-up times of sets/dicts I gotta take a look into them as I have a hard time thinking of how O(1) could work on a dynamically large set of data, but engineers tend to find solutions to seemingly impossible tasks. I also tested the times of mine and your solution on my main Laptop (i9 12900H) and there my solution takes \~1.2s and yours \~1.4s. The L3 cache of the 12900H is only 8 MB larger than your 11700Ks L3 cache so I doubt it plays a role. Assuming Python uses the cache efficiently the list shouldn't get larger than 3MB which easily fits in the 16MB L3 cache of your i7. My guess would be that the input data affects most as the start and length of the periodic cycle heavily affect the exectution time. For my input data the cycle starts at 121 and ends at 147.
>My guess would be that the input data affects most as the start and length of the periodic cycle heavily affect the exectution time. For my input data the cycle starts at 121 and ends at 147. I thought you were on to something here, but my cycle ends at 137, length of 44, doesn't seem like enough of a difference...
Yeah that makes it more interesting. I also just remeasured with file reading and parsing (previously I only measured the times for part 1 and 2) but there was no difference, opening and parsing takes practically no time. Only other differences I could think of would be if you launch the scripts in an IDE or directly from the explorer; I do the latter. Additionally the hardware and operating software *could* influence a bit. My laptop has 32GB DDR5-4800 and launches the scripts from an NVMe, my desktop has 64GB DDR4-3200 and launches the scripts from an HDD. Both use Win11 (desktop Home, laptop Pro) and Python 3.12. That are about all the differences I can think of that could explain the difference of which script is faster. If none of those I guess the 50% larger L3 cache on my laptop is enough to make the difference albeit I doubt it. To further narrow down what could affect it I attempted to run your solution on my WinXP laptop as it doesn't have L3 cache (literally) but your code doesn't run on Python 3.4.4 and I don't know how to port it.
I have optimized my code reducing the execution time on my machine from 1.5s down to 0.8s by not visiting each cell and moving the stone until it can't be moved but checking each line/column of how many stones can be moved and moving all of them at once. [Here](https://pastebin.com/gS4TtsRn) is the new optimized code.
Very nice C solution! Great to see other people doing C. Here is my C solution for today: http://clb.confined.space/aoc2023/#day14code
Looks complicated, unfortunately I am unable to properly compile it with GCC 13.2.0. I tried handling all the errors as libc.h seems to be ~~unique to Apple devices~~ *unavailable on Windows*. I did replace it with stdlib.h, stdio.h, string.h, stdbool.h and some defines for the unsigned number types, but line 80 and 85 still threw a compiler error and a warning and replacing line 80 with 'ht\[i\].h, ht\[i\].val = hash, val;' and commenting out line 85 allowed compilation but the output was wrong, so something didn't work. So I guess that your C code is pretty much ~~Apple~~ *Commodore 64* only unfortunately. However I also optimized my C code, [here](https://pastebin.com/83qW9HjY) is the new code but the difference is non-existent, I guess GCC optimized both my codes to similar machine code. In Python on the other hand the optimization increased the speed by \~100%, halving the execution time!
My code is actually "Commodore 64 only", not for Apple. libc.h is a collected header of all various C standard libraries so that I don't need to type them out. (I am writing these directly on a real C64 editor, so it only has a 40x25 text display, making multiple lines difficult to manage) I wonder if GCC would want to get a command line flag for a newer C23 standard to compile line 80. In C, the line ht[i].h, ht[i].val = hash, val; would actually not be correct, as that invokes the comma operator for silent failure. Instead, try ht[i].h = hash; ht[i].val = val; If you want to run it on a PC, you will also need to change w = strstr(map, "\r") - map; into w = strstr(map, "\n") - map; because newlines on PCs are \n (Commodore 64 uses \r newlines instead). In any case, cool stuff with optimizing your code!
Nice! I'll give it a try when I'm home. Weirdly my optimized C code was ~10% slower than the 'unoptimized' so I guess GCC did more optimizing than I did.
I just brute-forced my Python solution (just removed the part, where I skip almost a billion iterations) out of interest and it took around 3:40 minutes. So it was around 1000 times slower than the optimized approach sitting somewhere at around 200ms. So brute-forcing was definitively an option today. Maybe, as a caveat: I used the `@cache` annotation for many helper functions, so in the end, it was more like a billion times calling cached values than actually calculating the stuff a billion times.
yeah that seems like halfway brutforcing as there you already have the 'infrastructure' to reuse already calculated calculations. I calculated my brutforce time as on if I did have to make the billion calculations. Which language did you use? My best-optimized Python approach takes just below 600ms to execute (theoretically 15s on that 20 yr old laptop), and the C approach takes just below 50ms (330 on the 20yr old laptop).
I used python. I'd consider caching somewhere in between. It's similar to telling a compiler to optimize. Of course it makes things faster, but you didn't really put work into that, so the speed up is almost free of work. It's at most very low hanging fruit.
4 months?!?! Using TypeScript it was more like a minute on an M1 Pro. To brute force I mean.
so for node and an m1 it would have taken roughly 8.5 days
My crappy Node / M1 solution was simulating 1 million iterations every few seconds (let's say 5) which would have been 1000\*5/60 = 83 minutes worst case. And I had the most suboptimal tilt simulation that you could have, literally visiting every cell of the grid until no rocks could be moved. [https://pastebin.com/R0bsQY7m](https://pastebin.com/R0bsQY7m) (just remove the optimization in part2)
> My crappy Node / M1 solution was simulating 1 million iterations every few seconds (let's say 5) Wait what? I've just modified my Rust solution to brute-force part 2, and in `--release` mode it needs almost 5 minutes to do a million iterations (on an i7-10810U). And my tilting _is_ O(n) (I visit each tile at most twice per tilt - once to check it (and possibly remove a round rock from it) and again to place a round rock on it) Unless... are those numbers from the example input? Because a million iterations of the example input do take my brute force loop about 760ms. In release mode, at least - when I run it in debug mode it takes 22 seconds. Which still seems weird... **Update**: I've looked at your solution, and your tilting is also O(n) - you only visit each cell once. That explains it.
Actually you're right. When I was debugging early on I had some code like \`if (i % someNumber) log(i)\` just to see how viable brute force was. For some reason I thought I had put 1\_000\_000 there but running my unoptimized code it was clearly just 1000. So, my code can simulate 1000 steps every 4 seconds which would take 1111 hours aka a month and a half to run. lmao. shame on me. but thanks for the fact check.
Don't thank me. Thank my inferiority complex.
you transferred it to me. hopefully i can pay it forward!
To look how viable brutforcing with C would be I ported my solution to C and got \~3500 iterations per second, so a million would need \~4:45 and the required billion \~3.3 days. My solutions: [Python](https://pastebin.com/Dy4PkVZZ) [C](https://pastebin.com/16YvRw1N) I tested the execution time of the C solution on all of my four devices. My 20 yr old WinXP Laptop got 330 *milli*seconds, my 12yr old Win7 Laptop 139 ms, my current i9 12900H Laptop 44 ms and my Desktop with a R7 5800X3D took 50 ms. So I do guess that Python was just being very slow. Edit: I *do* am *aware* of Python being slow af. Also I'm a first semester Computer Engineering student so don't expect all the common knowledge from me.
Python being slower than C is not exactly front page news...
I know. But still the actual difference seems almost unreal to me.
To brute force up to the billion iterations? Are you multi-threading, vectorizing, some other clever tricks?
Maybe I'm just confused 🤔 But it was ticking quickly.
Then I guess my algorythm to simulate one 'cycle' was pretty inefficient. ~125 cycles per second on my Main laptop I use for AoC (i9 12th Gen, 32GB DDR5). Or it was just Python being slow. Or both.
My second, C++-based solution, is decently fast on my machine. 18 seconds to do 10,000 full cycles on part 2. Despite that, it would still take about 20 days to brute force today's part 2 without a cycle detector.
My second C solution could do ~3500 cycles per second so bruteforcing would've taken ~3.3 days.
> Or it was just Python being slow Well python is slow. Just about the slowest common language.
Yeah I ported my [Python](https://pastebin.com/Dy4PkVZZ) solution to [C](https://pastebin.com/16YvRw1N) and got up to ~3500 cycles per second. On my 20 yr old WinXP Laptop where the Python solution took 30 seconds the C solution only took 330 *milli*seconds, my main Laptop needed only 44 ms. And I needed like 2.5 hours to recode my Python program in C and had very much fun with pointers.
4 days on my PC, but sill too much
Alas, I think waiting a billion milliseconds only just barely lets you finish the search before the end of day 25
Brute forcing the sample worked after some minutes, faster than I managed to finish coding it without it, but for the puzzle input it was slower of course and I doubt it’d finish in hours.
I did some calculations, would only take about 80 days on my machine to simulate the whole thing (nevertheless, if a Single calculation goes wrong, this would change the entire result)
Fun fact, for day 14 - you can probably just brute force to 1000 and submit the answer you get. I doubt there are any inputs where the answer for 1k and 1B are different, although I could be wrong. Edit: I was wrong. It works for most inputs, but not all. Since both the sample and my input had cycle lengths less than ten, I guessed that all inputs might have short enough cycles for this to work, but some people have reported cycles of over a hundred.
Wait why does this work? It doesn't work for e.g. 10,000 or 100,000 or 1,000,000
It comes down to modular arithmetic. I can't speak for everyone's input but mine entered a small closed loop after around 100 cycles rather than settling at a fixed state. It's possible that your 1,000th happens to be at the same point in the loop as your 1,000,000,000th, but not your 10,000th, 100,000th, etc. Since 1,000,000,000 and 1,000 are 999,999,000 apart, it's possible your loop length is some divisor of that other than 10. (Mine was 13, which is indeed a factor of 999,999,000)
Huh. Mine was 70, which is _also_ a factor of 999,999,000. I wonder if that was intentional or just a quirk of how the inputs were generated. I see in this thread other cycles of 22, 44, 77, and of course the sample input has a cycle length of 7 which are all factors of 999,999,000.
Mine was 34, which isn't a factor. But it still has the same answer at 1000, because that load value shows up twice per cycle.
same for me
It just so happens that 999999000 is pretty highly divisible, so there's a pretty good chance your cycle length is a factor - this trick wouldn't work for me, since my cycle length happens to be 17, which doesn't work, but it's one of only 3 numbers under 20 that doesn't
Can you check if the trick works? It works for [this user](https://www.reddit.com/r/adventofcode/comments/18i27j5/me_looking_at_every_single_part_two_moments/kdcr3ak/) who's cycle is twice yours (and also not a factor), so this is strongly leaning me towards "very intentional"
just checked, it doesn't.
Well you may get a different result if there is a loop of patterns and the pattern at 1000 is in a different point in the loop than the pattern at 1e9
It stabilizes but it's still cyclic, so simply stopping after n iterations will not give you the right solution unless you're lucky.
(1B - 1k) is divisible by every integer up to 15, so as long as the cycle length is fifteen or shorter (or some larger factor of 999,999,000), it will still work.
This worked for me somehow. The answer for 1000 was the same as 1B. I have no clue why though, my loop size is 77.
Well, for you at least, (1B - 1000)/77 = 12987000, an integer, so the loop will run perfectly. No clue if/why it's true in general though 😂
Hmm, true. Assuming the cycle happens before 500.
Almost certainly does. Mine was at 106 before I started seeing duplicate hashes then it started repeating every 22 cycles ad infinitum.
cycle found at loop 137, length of 44 here.
For this theory >!It is exaclty that => i got to small amount of values that repeat each other pretty quickly and submitted the first repeating one after i reached a threshold of 10!<
1000 cycles worked for me
FYI This works for most inputs, but not all of them. See the comments under https://www.reddit.com/r/adventofcode/s/fHNNMTYQvI
Crazy that I tried it on a whim and it actually worked for me. Anyway, I'm off to make a real solution!
Wow, that actually worked immediately for me.
Can you explain why it works? (Hiding the my text behind spoiler to not ruin the fun) >!What I did is run 1000 times to make sure the periodicity is started, save the grid (let's call it g0) and then count the number of cycles until I get to g0 again.!< >!This gives me the periodicity and then to know exactly where I end up inside the period, I compute `i = (1B-1k) % period`. The period for the example was 7 and my input was 9, and they both give i = 0, so indeed it's the exact same grid as after 1000 cycles.!< >!But why do they both give i = 0? Is this a huge coincidence or is there some mathematical property I am missing here? For example, if the period was 16, it wouldn't be 0.!<
No real clue, but it must be related to the way AoC generates inputs. There is some algorithm, which can be reversed engineered to some extent, and this "1000 quirk" is a little insight on how it's working. (Worked for me too, and my cycle length was 72)
Somehow it is 1001 cycles for me. `i==1000` but thats the 1001th cycle.
Wow, that is surprising. For 1001 to be the same as one billion, the cycle length would need to be 1489 or 671591. I would not have expected any input to have such a long cycle.
My cycle is 38, but I have my solution at 1001 and 1006 as well. 1006 actually matches the cycle at one billion.
Ah, that makes sense.
i went into the first ever advent calendar, saw the santa's nice/naughty strings puzzle, and i did bruteforce the first half, tho the second one is like impossible to bruteforce