It's interesting after you mentioned the quadrants, i assumed the tree would actually be split into mirror pieces across the quadrants and that might be a way to find it - although it's actually in 1 quadrant for all inputs. Still, there were some really creative solutions here that are fairly general: 1. Connected components - find the largest connected component 2. Entropy! This was my favorite. Encode the grid as a string , compress it and track the minimum compressed size. This corresponds to minimum entropy and should find the pattern! This one is actually brilliant and should work to find a variety of patterns in many puzzles.
The point is that an image has lower entropy than a random robot distribution. I think the problem was very funny and excellent. I calculated how many neighbours the robots have in the grid. This is correlated to the entropy. More neighbours means lower entropy. This turned out to easily detect the christmas tree. Also, part 2 made me laugh pretty hard since I was expecting the same kind of part 2 as we've seen in the past where we have to calculate a periodicity of the grid. And out of the blue we get a funny Easter Egg!
The second part might be less well-defined than the usual problems, but it seems to have the merit of being much harder for LLM cheaters to solve. I found it surprising and funny!
I agree, this seemed like an "anti-LLM" puzzle. Based on the AoC leaderboards seemed to have worked with several of the LLM users getting the first star in seconds and not even making the leaderboard for the second star.
A friend directly said ah they want to make a picture of all robots so we have to search for a second where no robots overlap. Seems to work as well, for me part 2 text was very confusing.
Nice approach for part 2! My approach was to do a water fill from (0,0) and look for the lowest water fill area. This worked, because the tree image blocked the most water fill space.
@@widyaanugrahputra7233 Absolutely! I created a method to start at position (0,0) that continues inspecting its neighbours (left, right, up, down) that are empty (not contain a robot). This is what I ment with 'water fill'. The number of empty positions to reach from (0,0) is what I count on every step. I searched for the lowest value and used this step as my answer.
I simply searched for a vertical lineup of length at least 10 (turns out the tree is a lot taller than that - and it has a box around it) thinking that the tree must at least have a solid trunk. This worked, and the first stop was in fact the tree
I used matplotlib to make actual images, and plotted a few iterations, just to get a feel of what I might encounter. I noticed that the size of the field is given by prime numbers, and in the first 100 iterations I noticed a regular pattern, a band of aligned robots. I then used the field-size to take bigger steps, and found the solution quite quickly. For matplotlib I already stored the field in a bumpy array. I used the gzip module to compress the bytes-array representation of the image, figuring that the Christmas tree would be the field with the lowest entropy, and therefore resulting in the smallest compressed size. This returned the same answer. Having seen the image, the reason your solution works is probably because it is located on the vertical axis, cutting out a fair number of robots in the middle, lowering the safety factor. I think it was located towards the top of the field, but I think you got a little bit lucky here.
I used the exact same approach for part one waiting for a second part with more seconds....I didn't understand part two until I saw your solution (thanks for it!!!).
I used a different solution. I made the assumption that to generate the input all robots were on a unique spot. And at every time step other than the picture at least two robots would overlap. This worked for my input.
My tree was very close to the center, and what worked for me was looking for frames where the top left and right corner regions were mostly empty. A corner region I defined as half of a quadrant, where the quadrant is cut diagonally such that the corner of the grid is not part of the diagonal.
Instead I really loved today's part 2, I had to think really outside the box, just to mention a couple of things I had in mind like low number of connected components, low entropy or higher density in one specific area like a quadrant. It was fun to stop and think about how to approach a real problem not directly related to some pre-categorized algorithmic solution
Absolutely fantastic videos, you have a talent for explaining concepts, thanks. I'll definitely watch more as I work through a few more of these problems belatedly. I got stuck on part B here. And for my input the find the minimum safety factor did not work! As was also my first guess.. I had to do some longest stretch of adjacent spaces with robot heuristic to find it. Conversely, I actually really liked part B, maybe because of the unknown factor in what the pattern you're looking for is.. your criticisms are legit tho, of course.
Completely agree with your points on part 2. It's an interesting problem, but even just a little bit more explanation would go a long way (though it would likely be still confusing)
I searched through looking for the state with the largest contiguous region. I guessed at a threshold of 10 and printed those. It had some false positives, 50 worked to isolate the tree. My previous attempt was to look for a state where no robots share a position, assuming this may be a starting state. Unfortunately I only ran it up to 1000 so didn't find it this way, but I've re-tried it now and it works too. Your method also works. Thanks for the video!
I went straight forward for the picture as I remembered from two or three years back but didn't had any clou about how much. I just put in a wait for .1 and printing from 5,000 till 5,500 with my fingers on the CTRL-C buttons. Next upgrade with 500 and somewhere between 7,000 and 7,500 I noticed a bulb somewhere and than zoomed in and zoomed in and found the second in less than 15 minutes which I find acceptable. But totally not satisfied, sometimes having a solution is not at all satisfying, I thought (but I had seen the picture) I must look for a 'bubble' or cluster of robots. That gave me a hint close to my solution but not the exact one. Then I looked around and saw your solution and it worked for me but like you I didn't found part-2 a nice challenge. Thank you for sharing your solution.
I tried a few things that failed, but found the Christmas tree by looking (programmatically) for images that had a low spread of x-values and y-values. Similar to the connected components or pairwise distance approaches mentioned elsewhere, but much simpler to implement. Great problem, in my opinion.
I love that he added something that is more in the street of datascience. It was really interesting to try using cluster detection and be less certain of whether an implementation would work or not. Part 1 was a good test to see if the setup for part 2 was correct.
Part 2 Worked. And after some minutes i figured the grid stuff, and could even print my Tree. :) (absolutly noob hobby programmer here) I enjoy every day your videos, always good Explaining the Code and Problems.
each second produces a map, so I coded a solution where I'd create a grid and then check for symmetry by scoring left and right side, obv I didn't find anything because it wasn't in the middle, so I had to sweep every map... then I find out that it could've been this easy... lol
Your part 2 solution worked for me. I don't like the vagueness for part 2 either (I immediately gave up and came to your channel for clarification on the prompt lol) but one silver lining is that it's cool to see how this problem generated very unique solution styles from everyone in the comments.
for p2 looking at the largest component of robots in the grid and then looking for the overall largest one in like 10000 seconds gave me the answer. i did this cause the text stated "most of the robots" so after i found a valid looking size, i printed the grid to make sure and found the tree. surely was confused about "what is a chritmas tree?" in the beginning aswell though
Great job! Using the quadrants from part 1 was clever and not something that I thought of, I simply used the assuption that the iteration containing the tree would have a long continous line of robots forming the base of the tree (which is very ugly but works). I tried running your solution on my input and it worked. So that seems to be the intended solution (at least with the updated sample size of three)
My partner and I agreed that the solution to part 2 was the iteration where the most number of robots end up within the region that we defined as the christmas tree region which was the area encompassed by a triangle where the top point was the middle of the top line, the bottom points were the bottom left and right of the area so it would look like this: . . . X . . . . . XXX . . . XXXXX . XXXXXXX And then we went through the first 20K iterations and figured out what percentage of the robots were in that X region described above and returned the one where the percentage was highest. Agreed that the question is phrased confusingly and poorly but I think the resulting answer is cute
Part 2 was fun as a problem to solve, but I agree that it's not great for a competition (though my impression is that he creator isn't a fan of that aspect). My flailing approach was to print each state at full speed and see if any shapes are noticed, just to get some vague idea about the tree (straight or jagged, filled or outline). Not getting anywhere, I started to look for triangle shapes (the top). First in the top center, then going down the center and eventually everywhere within reason. Each time something matched I would print, gradually increasing the triangle height until the "noise" was eliminated. This could still be easily thrown off by random triangle shapes, but with "manual" verification you can still get there. Very unsatisfying, though.
For part 2 I just assumed that the puzzle input would have been computed by reverse scrambling a binary image, which would have no overlaps. So just looking for the first grid without two or more robots at the same spot proved to be enough. Took 2 minutes to code and seemed pretty obvious to me. I've seen worse challenges on AoC in the past.
Love your content! Off topic question, what type of keyboard are you using? Would your share the model and types of switches your are using? They sounds nice
it's a lenovo SK-8823 lmao, it's just the default keyboard that came with this PC from costco. it's a flat membrane keyboard that i'm using because my razer keyboard and the gaming keyboard i took from my brother when he replaced his both have issues with activating twice or not responding to keypresses properly; until i can get a better keyboard again i'm just using this because it's the only one that i have that types properly
so yeah in my input the tree was in all 4 quadrants was pretty evenly in the top and bottom on the left side but some of its frame ended up in the top and bottom of the right side as well
So, did you get the solution by finding the min(safety factors)? My tree was spread over the right half of the grid, so the min(safety factors) did NOT work.
I missed the quadrant assumption and instead used a more naive solution where I calculated the total distance between all the pairs of points and picked the min of that. It was still the same answer. And yes my puzzle input also resulted in the tree being in a quadrant. It wasn't very efficient, but still completed in about 0.5 sec.
i solved part2 by determining the timepoint where the average pairwise distances between the robots was minimum. i thought that when the robots are in tree formation, they would be much closer to each other than if they were not aligned in the pattern
I also did not like the problem at all when doing it, so much so that after scrolling through 1k grids I looked up a solution cause i though I missed the actual answer. But looking back, there are some interesting things you can do. Theres a number of heuristics that could work (low number of connected components, high number of average neighbors) for which you could print out the grid and check.
I looked for any quadrant that had more than 300 robots in it and that worked. My tree was predominately in the SW quadrant, but just crept over into the SE. Initially I dumped 10000 frames to a file and looked for a lot of robots in a line using Vim.
I initially tried to find them manually by creating a huge 103MB file where all grids for every tilmestep until 101*103 are in there (after I found out, all robot arrangements repeat every 101*103 timesteps). Then after skimming through the file using vsocdes minimap I eventually found the tree. But interestingly it turns out this is not the timestamp which has the lowest safety factor, it's the 3 lowest for me. So this method seems to not work for all inputs.
I struggled to understand part2. Then i re-read "most robots" and "picture" so I thought maybe they are forming a tree by standing near/on top of each other. So looking from the top they will be crowded into one side/ one quadrant.
In trying to sort part 2 I'd accidentally moved robots as well as calculated from their (now wrong) starting position. Frustrating bug. I was wondering why it didn't just work by output inspection 🙂
They should have at least said that the tree would be entirely in one quadrant there are just too many assumptions you have to make to solve this the assignment doesn't say that the tree would be in one quadrant, it doesn't say that the robots would be each sitting in an unique position (there could have been a small 10x10 tree with hundreds of robots sitting on top of each other), it didn't have to be a connected image, it could have been an image spanning the entire grid, with empty spaces between robots, or a tree that's empty inside, it could have been empty inside with christmas decoraction sprinkled inside randomly, since it's supposed to be a christmas tree
Not sure if anyone said it here already, but in my input, the Christmas tree was exactly in the middle of the area. Not sure if that would work with your code, I didn't tested it.
My first idea was that the tree would be in the middle, so I was looking for symmetrical rows. I didn’t read the bit about “most robots” (and my input wasn’t symmetrical).
I've looked at first thousand snapshots and noticed two types of resonances - horizontal and vertical one, when robots definitely formed longed horizontal and vertical lines. Surprisingly, resonances's periods were 101 and 103, but they had different 'shift'. So, I have found a moment in time, when both resonances happen (this is a simple linear equation with two variables that have to be integers, very easy to brute force). That was the answer. Probably the correct approach is to measure enthropy using any method you like.
Nice to see that someone approached it the same as me. I looked at the first couple of hundred grids, and noticed 4 anomalies by then. Two of them were 101 apart, and two were 103 apart. I used the Chinese Remainder Theorem to find where the two series would meet each other. I think there's no "correct" approach, what works works.
I'm not sure how I feel about part 2 to be honest. But the problem mentions that "most of the robots should arrange themselves", so I assumed that the arrangement means that they're connected. Calculating the number of connected components after each second and tracking the least number worked, although had to experiment with the num of iterations/seconds. And yeah your quadrant approach worked for my input as well.
I've computed connected components with 8 neighbors, check if max size of component is greater than my threshold tried with 10,20,30, and printed the image it worked but what if it would be some kind of "dashed" outlined (centered, or in 1 quadrant only) tree ? probably entropy, water fill, CC (also guess that robots will not overlap) would not work I think maybe just manual (or AI) image recognition would ;-)
Looks like for me the solution for part 2 does not work with your approach, came here to look how other people solved part two ;-) The safetyfactor of my actual solution was only the 4th lowest one.
"issue 1" - I agree, but was fun to find some algorithm that works "issue 2" - bunch of previous AoC days had answer as graphically produced letters, so visually impaired people are probably already used to it ;-)
It's interesting after you mentioned the quadrants, i assumed the tree would actually be split into mirror pieces across the quadrants and that might be a way to find it - although it's actually in 1 quadrant for all inputs. Still, there were some really creative solutions here that are fairly general:
1. Connected components - find the largest connected component
2. Entropy! This was my favorite. Encode the grid as a string , compress it and track the minimum compressed size. This corresponds to minimum entropy and should find the pattern! This one is actually brilliant and should work to find a variety of patterns in many puzzles.
what if the numbers are just very close but not forming a christimas tree?
The point is that an image has lower entropy than a random robot distribution. I think the problem was very funny and excellent. I calculated how many neighbours the robots have in the grid. This is correlated to the entropy. More neighbours means lower entropy. This turned out to easily detect the christmas tree. Also, part 2 made me laugh pretty hard since I was expecting the same kind of part 2 as we've seen in the past where we have to calculate a periodicity of the grid. And out of the blue we get a funny Easter Egg!
What’s entropy
@antoineleduc7611 If you can't be bothered to look it up you will remain clueless 😅
@@mcg6762 true enough
The second part might be less well-defined than the usual problems, but it seems to have the merit of being much harder for LLM cheaters to solve. I found it surprising and funny!
I agree, this seemed like an "anti-LLM" puzzle. Based on the AoC leaderboards seemed to have worked with several of the LLM users getting the first star in seconds and not even making the leaderboard for the second star.
A friend directly said ah they want to make a picture of all robots so we have to search for a second where no robots overlap. Seems to work as well, for me part 2 text was very confusing.
So it was the earliest moment where no robot overlap? dem!
Oh yeah. It works!
Nice approach for part 2! My approach was to do a water fill from (0,0) and look for the lowest water fill area. This worked, because the tree image blocked the most water fill space.
Can you explain more about your approach?
@@widyaanugrahputra7233 Absolutely! I created a method to start at position (0,0) that continues inspecting its neighbours (left, right, up, down) that are empty (not contain a robot). This is what I ment with 'water fill'. The number of empty positions to reach from (0,0) is what I count on every step. I searched for the lowest value and used this step as my answer.
@@rolfschellenberger thanks
The way I did it was to simply print out a lot of iterations into a text file then control-f for a lot of robots in a row
I did something very similar, but I had my code scan for a ^ pattern (top of tree) and it found it lol.
I simply searched for a vertical lineup of length at least 10 (turns out the tree is a lot taller than that - and it has a box around it) thinking that the tree must at least have a solid trunk. This worked, and the first stop was in fact the tree
I used matplotlib to make actual images, and plotted a few iterations, just to get a feel of what I might encounter. I noticed that the size of the field is given by prime numbers, and in the first 100 iterations I noticed a regular pattern, a band of aligned robots. I then used the field-size to take bigger steps, and found the solution quite quickly.
For matplotlib I already stored the field in a bumpy array. I used the gzip module to compress the bytes-array representation of the image, figuring that the Christmas tree would be the field with the lowest entropy, and therefore resulting in the smallest compressed size. This returned the same answer.
Having seen the image, the reason your solution works is probably because it is located on the vertical axis, cutting out a fair number of robots in the middle, lowering the safety factor. I think it was located towards the top of the field, but I think you got a little bit lucky here.
I used the exact same approach for part one waiting for a second part with more seconds....I didn't understand part two until I saw your solution (thanks for it!!!).
I used a different solution. I made the assumption that to generate the input all robots were on a unique spot. And at every time step other than the picture at least two robots would overlap. This worked for my input.
I had to use this solution, too, thanks for the suggestion, lol.
The lowest score as shown in the video didn’t work.
wow
My tree was very close to the center, and what worked for me was looking for frames where the top left and right corner regions were mostly empty. A corner region I defined as half of a quadrant, where the quadrant is cut diagonally such that the corner of the grid is not part of the diagonal.
My tree was nearly dead center, but this method also worked.
I assumed the tree would be large and hollow until I found it via image generation.
Instead I really loved today's part 2, I had to think really outside the box, just to mention a couple of things I had in mind like low number of connected components, low entropy or higher density in one specific area like a quadrant. It was fun to stop and think about how to approach a real problem not directly related to some pre-categorized algorithmic solution
Absolutely fantastic videos, you have a talent for explaining concepts, thanks. I'll definitely watch more as I work through a few more of these problems belatedly. I got stuck on part B here. And for my input the find the minimum safety factor did not work! As was also my first guess.. I had to do some longest stretch of adjacent spaces with robot heuristic to find it. Conversely, I actually really liked part B, maybe because of the unknown factor in what the pattern you're looking for is.. your criticisms are legit tho, of course.
Completely agree with your points on part 2. It's an interesting problem, but even just a little bit more explanation would go a long way (though it would likely be still confusing)
I searched through looking for the state with the largest contiguous region. I guessed at a threshold of 10 and printed those. It had some false positives, 50 worked to isolate the tree.
My previous attempt was to look for a state where no robots share a position, assuming this may be a starting state. Unfortunately I only ran it up to 1000 so didn't find it this way, but I've re-tried it now and it works too.
Your method also works.
Thanks for the video!
I went straight forward for the picture as I remembered from two or three years back but didn't had any clou about how much. I just put in a wait for .1 and printing from 5,000 till 5,500 with my fingers on the CTRL-C buttons. Next upgrade with 500 and somewhere between 7,000 and 7,500 I noticed a bulb somewhere and than zoomed in and zoomed in and found the second in less than 15 minutes which I find acceptable.
But totally not satisfied, sometimes having a solution is not at all satisfying, I thought (but I had seen the picture) I must look for a 'bubble' or cluster of robots. That gave me a hint close to my solution but not the exact one.
Then I looked around and saw your solution and it worked for me but like you I didn't found part-2 a nice challenge.
Thank you for sharing your solution.
I tried a few things that failed, but found the Christmas tree by looking (programmatically) for images that had a low spread of x-values and y-values. Similar to the connected components or pairwise distance approaches mentioned elsewhere, but much simpler to implement. Great problem, in my opinion.
I enjoyed today's puzzle a lot, I think it's great to have different types of challenges.
Funny how everyone seems to have done part 2 differently, for my input the tree appear the first time every robot had a unique positions
I love that he added something that is more in the street of datascience. It was really interesting to try using cluster detection and be less certain of whether an implementation would work or not. Part 1 was a good test to see if the setup for part 2 was correct.
Part 2 Worked. And after some minutes i figured the grid stuff, and could even print my Tree. :) (absolutly noob hobby programmer here) I enjoy every day your videos, always good Explaining the Code and Problems.
each second produces a map, so I coded a solution where I'd create a grid and then check for symmetry by scoring left and right side, obv I didn't find anything because it wasn't in the middle, so I had to sweep every map... then I find out that it could've been this easy... lol
Your part 2 solution worked for me. I don't like the vagueness for part 2 either (I immediately gave up and came to your channel for clarification on the prompt lol) but one silver lining is that it's cool to see how this problem generated very unique solution styles from everyone in the comments.
for p2 looking at the largest component of robots in the grid and then looking for the overall largest one in like 10000 seconds gave me the answer. i did this cause the text stated "most of the robots" so after i found a valid looking size, i printed the grid to make sure and found the tree. surely was confused about "what is a chritmas tree?" in the beginning aswell though
Great job! Using the quadrants from part 1 was clever and not something that I thought of, I simply used the assuption that the iteration containing the tree would have a long continous line of robots forming the base of the tree (which is very ugly but works). I tried running your solution on my input and it worked. So that seems to be the intended solution (at least with the updated sample size of three)
My partner and I agreed that the solution to part 2 was the iteration where the most number of robots end up within the region that we defined as the christmas tree region which was the area encompassed by a triangle where the top point was the middle of the top line, the bottom points were the bottom left and right of the area so it would look like this:
. . . X . . .
. . XXX . .
. XXXXX .
XXXXXXX
And then we went through the first 20K iterations and figured out what percentage of the robots were in that X region described above and returned the one where the percentage was highest. Agreed that the question is phrased confusingly and poorly but I think the resulting answer is cute
Part 2 was fun as a problem to solve, but I agree that it's not great for a competition (though my impression is that he creator isn't a fan of that aspect). My flailing approach was to print each state at full speed and see if any shapes are noticed, just to get some vague idea about the tree (straight or jagged, filled or outline). Not getting anywhere, I started to look for triangle shapes (the top). First in the top center, then going down the center and eventually everywhere within reason. Each time something matched I would print, gradually increasing the triangle height until the "noise" was eliminated. This could still be easily thrown off by random triangle shapes, but with "manual" verification you can still get there. Very unsatisfying, though.
For part 2 I just assumed that the puzzle input would have been computed by reverse scrambling a binary image, which would have no overlaps. So just looking for the first grid without two or more robots at the same spot proved to be enough. Took 2 minutes to code and seemed pretty obvious to me.
I've seen worse challenges on AoC in the past.
I assumed no robots would be overlapping which worked.
This worked for me to. I just had to reverse the loop which finds the lowest entropy.
Love your content! Off topic question, what type of keyboard are you using? Would your share the model and types of switches your are using? They sounds nice
it's a lenovo SK-8823 lmao, it's just the default keyboard that came with this PC from costco. it's a flat membrane keyboard that i'm using because my razer keyboard and the gaming keyboard i took from my brother when he replaced his both have issues with activating twice or not responding to keypresses properly; until i can get a better keyboard again i'm just using this because it's the only one that i have that types properly
so yeah in my input the tree was in all 4 quadrants was pretty evenly in the top and bottom on the left side but some of its frame ended up in the top and bottom of the right side as well
So, did you get the solution by finding the min(safety factors)? My tree was spread over the right half of the grid, so the min(safety factors) did NOT work.
I missed the quadrant assumption and instead used a more naive solution where I calculated the total distance between all the pairs of points and picked the min of that. It was still the same answer. And yes my puzzle input also resulted in the tree being in a quadrant. It wasn't very efficient, but still completed in about 0.5 sec.
I still wonder why does that count as a chrismas tree
i solved part2 by determining the timepoint where the average pairwise distances between the robots was minimum. i thought that when the robots are in tree formation, they would be much closer to each other than if they were not aligned in the pattern
I also did not like the problem at all when doing it, so much so that after scrolling through 1k grids I looked up a solution cause i though I missed the actual answer. But looking back, there are some interesting things you can do. Theres a number of heuristics that could work (low number of connected components, high number of average neighbors) for which you could print out the grid and check.
I looked for any quadrant that had more than 300 robots in it and that worked.
My tree was predominately in the SW quadrant, but just crept over into the SE.
Initially I dumped 10000 frames to a file and looked for a lot of robots in a line using Vim.
I initially tried to find them manually by creating a huge 103MB file where all grids for every tilmestep until 101*103 are in there (after I found out, all robot arrangements repeat every 101*103 timesteps). Then after skimming through the file using vsocdes minimap I eventually found the tree. But interestingly it turns out this is not the timestamp which has the lowest safety factor, it's the 3 lowest for me. So this method seems to not work for all inputs.
I struggled to understand part2. Then i re-read "most robots" and "picture" so I thought maybe they are forming a tree by standing near/on top of each other. So looking from the top they will be crowded into one side/ one quadrant.
In trying to sort part 2 I'd accidentally moved robots as well as calculated from their (now wrong) starting position. Frustrating bug. I was wondering why it didn't just work by output inspection 🙂
it doesnt works for my example :( I have to low result
worked for me, even though the tree was almost dead center...
I guess it's 'cause the tree puts more of the bots in the midline cross than usual?
They should have at least said that the tree would be entirely in one quadrant
there are just too many assumptions you have to make to solve this
the assignment doesn't say that the tree would be in one quadrant, it doesn't say that the robots would be each sitting in an unique position (there could have been a small 10x10 tree with hundreds of robots sitting on top of each other), it didn't have to be a connected image, it could have been an image spanning the entire grid, with empty spaces between robots, or a tree that's empty inside, it could have been empty inside with christmas decoraction sprinkled inside randomly, since it's supposed to be a christmas tree
Not sure if anyone said it here already, but in my input, the Christmas tree was exactly in the middle of the area. Not sure if that would work with your code, I didn't tested it.
My first idea was that the tree would be in the middle, so I was looking for symmetrical rows. I didn’t read the bit about “most robots” (and my input wasn’t symmetrical).
I've looked at first thousand snapshots and noticed two types of resonances - horizontal and vertical one, when robots definitely formed longed horizontal and vertical lines. Surprisingly, resonances's periods were 101 and 103, but they had different 'shift'. So, I have found a moment in time, when both resonances happen (this is a simple linear equation with two variables that have to be integers, very easy to brute force). That was the answer.
Probably the correct approach is to measure enthropy using any method you like.
Nice to see that someone approached it the same as me. I looked at the first couple of hundred grids, and noticed 4 anomalies by then. Two of them were 101 apart, and two were 103 apart. I used the Chinese Remainder Theorem to find where the two series would meet each other.
I think there's no "correct" approach, what works works.
This solution worked for me, but 0xDF solution did not work.
I'm not sure how I feel about part 2 to be honest. But the problem mentions that "most of the robots should arrange themselves", so I assumed that the arrangement means that they're connected. Calculating the number of connected components after each second and tracking the least number worked, although had to experiment with the num of iterations/seconds.
And yeah your quadrant approach worked for my input as well.
I've computed connected components with 8 neighbors, check if max size of component is greater than my threshold
tried with 10,20,30, and printed the image
it worked
but what if it would be some kind of "dashed" outlined (centered, or in 1 quadrant only) tree ?
probably entropy, water fill, CC (also guess that robots will not overlap) would not work I think
maybe just manual (or AI) image recognition would ;-)
I would also suggest Neil Thistlethewaite's video where he discusses the logic and prints the Christmas Tree
I don't even know what's part 2 even asking lol. Look for egg or tree? Sample visual in grid form please? It become a guessing game at that point.
Looks like for me the solution for part 2 does not work with your approach, came here to look how other people solved part two ;-)
The safetyfactor of my actual solution was only the 4th lowest one.
It worked for me.
"issue 1" - I agree, but was fun to find some algorithm that works
"issue 2" - bunch of previous AoC days had answer as graphically produced letters, so visually impaired people are probably already used to it ;-)