Big O ignores constants like the division by two, but yeah that's an optimization in fact, big O is too stupid sometimes: if your algorithm had a fixed amount of particles and kept all of them somewhere very far away until you chose to spawn them, but ran the quadratic algorithm to calculate the gravity, then it would be O(1) because the running time would be constant (as in, constantly the worst lol)
Hi just have a question. Since n-body problems (for n > 2) are known to be chaotic, isnt the barnes hut algorithm unsuitable for long time scales? The error accumulation may be significant right?
Good solution but it annoys me greatly when advent of code makes it so that the only way to solve the problem is to look at your specific input data for patterns and make assumptions that weren't in the instructions or the example. Going back to the previous years and this seems to be the only one in 2021 that does (unless day 25 has it, haven't gotten to it yet) but 2023 had like 5 of these. Is it really that hard to just...make the assumptions part of the problem?
This is an interesting solution for problem 4, but I am still trying to fully understand it. I can see how the location of a specific cut fully determines a set of subsets, and the number of steps we get for this given cut. However, I struggle to convince myself why one of the optimal solutions must exist among those provided by the cuts.
My recommendation for dealing with cases where the base and test number are not relatively prime is to only remove all factors of the test number from the base if the base is indeed a multiple of the test number. If the test number is prime but is not relatively prime to the base, then the test number must divide the base, and removing all factors of it will yield a "new" base that is indeed relatively prime to the test number, so the Miller-Rabin test can still run (if the resulting "new" base is all the way down to 1, pass the test number for that base right away). This guarantees that if a composite test number does not divide the base and the test number and base are not relatively prime, the test will properly flag the test number as composite, while still allowing primes that divide an original base to pass the test.
I "invented" this when I was in eleventh grade learning how to program, it was my first real "hard" problem I solved kinda neat seeing someone else talk about it :)
I am trying to learn dynamic programming, and for the most basic of problems like the staircase stepping I fully understand how to reach those objectie function/recurrence relationships. I had no idea how to apply DP to this problem and I thank you for taking the time to exlain it it in a table manner (non-recursive) because it truly captures the essence of dynamic programming that way, it feels like to me at least.
Just add this line before the part one if else statements #also i used value instead of amount if len(value) != 0 : value[-1] += joker else: value = [joker]
12.2 has been kicking my ass for 2 weeks now, I understand the purpose of pushing solutions to a map to reduce the amount of time spent processing solutions. People have tried to explain using a fib() function, which makes sense. Instinct tells me I should be running the original 12.1 to get solutions for each individual block, then multiplying out for the five. What throws me is how the combination works, there's an extra ? in the middle so the original solutions only make sense if every additional ? is a . I'm trying to understand dynamic programming and I keep getting "it's complicated, I won't go into it" 😂 I'm sat there like no, please do!
I implemented the "hashmap" as a list of dictionaries (python3). The list is 256 elements long, and the index of the list to either place the lens into or pop from is the result of the hashing algorithm developed in part 1 on the first letters in the current line in the sequence (ie. 'rn', 'cm', 'qp', ...). Hope that helps.
Thank you for the explanation of part 2, that was very clear. Would be interesting to know what made you think to look into the input data and how you came up to the conclusion that the nodes looped. I tried to solve it by spawning a thread for each starting node and then let them run until they all reach a node ending with 'Z': this will be super fast, I thought, but instead it took forever. It never occurred to me to look into possible patterns in the input data. I am kind of disappointed about the fact they did not give any hint about the input pattern.
I reached the same conclusion that William did, but only after trying to do parallel runs for all of them, like you. When I tried to debug it, I took a single starting point and made it loop 10 times and logged the amount of steps per loop. I noticed that the 10th loop was 10x bigger than the 1st loop, and everything in between was also a multiple.
Kept coming back to this one. From brute force (2.5min), to multithreaded (45s), to parallel reverse lookup (75ms) and finally splitting the ranges from back to front (450us). Amazing how much difference an approach can make
For reverse lookup do you mean start with locations? I couldn't figure out how to handle when something "upstream" doesn't have a mapped downstream value so instead just uses itself in that case.
@@briandawley7808 yes. But you have to pretty much start at 0 and count up, because the default mapping says "if no mapping, value maps to itself". So you can't just look at the location ranges, since all values are potentially possible.
In part 2, Instead of trying every substitution, I iterated over rows, and kept a tally of the total number of differing characters. If that exceeded 1, I had an early stop, and if it wasn't 1 in the end the line wasn't a smudged mirror location.
For part 1 I was happy with my one pass approach. Making it more generic for part 2 somewhat ruined the neatness. Rolling a column north just keeps track of the next valid destination as it goes, so no nested loops needed (swapping ranges with indexing for clarity): int64_t dst_row = 0; for (row...) { if (grid[row][col] == 'O') { swap(grid[dst_row++][col], grid[row][col]); } else if (grid[row][col] == '#') { dst_row = row + 1; } } Still can't get part under 19ms, though. All the copies to keep a history up to the first cycle must be killing it.
In part one we have a method that finds a reflection point (horizontal or vertical) where there are 0 errors between reflected lines. So for part two we can run the same method but looking for exactly one error instead of 0! I tried this thinking I was probably missing something and was quite surprised when it worked!
In part 2 there is no need to count the rem_jokers variable and also add it in if condition because it will always be 0. Remove it, think about it and see that the result will be the same.
Nice! In the second grid in the sample, it changes the fifth symbol in row 2, but why couldn't it be the fifth in row 1 to a dot, please? #...##..# #....#..#
