I suspect this has to do with how the puzzle was constructed. Starting point was probably the grid with the Christmas tree and overall N robots in distinct locations, and then the generator randomly choses vx, vy for each robot and a number of seconds to work backwards to generate the puzzle input.
@@mathiaskern7031 this is nice approach and works quite fast def check_area(robots): robot_positions = set([(px, py) for px, py, _, _ in robots]) return len(robot_positions) == len(robots)
0) my first instinct was that picture would be vertically symmetric, but it did not work, so tried cc 1) I've counted not how many connected components are there, but what is the size of biggest cc started with threshold at 10, 20, 30 and found a tree ;-); using all 8 neighbours 2) Eric did not highlighted that robots at middle axes don't count 3) modulo ;-) px = (px + vx + width) % width py = (py + vy + height) % height
At 1:26 I'm surprised to see while loops instead of just %, but you were faster than me, so I'm not one to judge! Edit: Oh I think you're trying to avoid using mod on negative numbers. But it's nicely behaved in Python to only map to the range [0, m)
For pt2, I ended up just print out all the states to a file then searching for a line with a bunch of robots next to each other (assuming that would only happen for the valid answer). Once you know the pattern, it's quite easy to find the answer.
My idea for part 2 was that the tree probably has a stem, so I printed out states with long vertical lines (at least 10), which immediately gave me the tree state. It wasn‘t the stem but the boundary of the image, so I got a bit lucky.
I tried something similar but was counting just the number in each row/column, rather than contiguous, so I was getting a lot of noise. I'm frustrated that I gave up and looked for a picture of someone else's tree and then discovered I'd been on the right track.
@@rastislavsvoboda4363 In the absence of any clear definition of what the Christmas tree would look like, it was a fair - and successful - guess, hence I wrote it was a heuristic. The aim is to solve the puzzle given, not to develop a solution for every possible case. Your solution based on a large connected component is equally a guess - the tree could have been formed by robots which are two cells apart and thus do not appear connected. But it is a very sound guess, and it worked.
@@mathiaskern7031 no problem, we are programmers and sometimes we need luck; otherwise you need to generate pic by pic and try AI if it can see a tree there ;-)
I solved part 2 just by looking at states after each simulation. It's easy to spot a pattern, for my input after 99th, every 101st iterations robots gathered closer to center of grid, so I started printing only "interesting" grids and found the easter egg after 7371 (72 interesting) iterations.
the solution to part 2 is that no 2 robots should be in the same cell. why this works idk
I suspect this has to do with how the puzzle was constructed. Starting point was probably the grid with the Christmas tree and overall N robots in distinct locations, and then the generator randomly choses vx, vy for each robot and a number of seconds to work backwards to generate the puzzle input.
@@mathiaskern7031
this is nice approach
and works quite fast
def check_area(robots):
robot_positions = set([(px, py) for px, py, _, _ in robots])
return len(robot_positions) == len(robots)
0) my first instinct was that picture would be vertically symmetric, but it did not work, so tried cc
1) I've counted not how many connected components are there, but what is the size of biggest cc
started with threshold at 10, 20, 30 and found a tree ;-); using all 8 neighbours
2) Eric did not highlighted that robots at middle axes don't count
3) modulo ;-)
px = (px + vx + width) % width
py = (py + vy + height) % height
At 1:26 I'm surprised to see while loops instead of just %, but you were faster than me, so I'm not one to judge!
Edit: Oh I think you're trying to avoid using mod on negative numbers. But it's nicely behaved in Python to only map to the range [0, m)
I initially thought that the image would be symmetrical so we could use the quadrant counts from part 1, but I guess that would have been too easy?
For pt2, I ended up just print out all the states to a file then searching for a line with a bunch of robots next to each other (assuming that would only happen for the valid answer). Once you know the pattern, it's quite easy to find the answer.
My idea for part 2 was that the tree probably has a stem, so I printed out states with long vertical lines (at least 10), which immediately gave me the tree state. It wasn‘t the stem but the boundary of the image, so I got a bit lucky.
I tried something similar but was counting just the number in each row/column, rather than contiguous, so I was getting a lot of noise. I'm frustrated that I gave up and looked for a picture of someone else's tree and then discovered I'd been on the right track.
Nicely done with the second part! quite clever. I was very happy to see my tree printed!!
My heuristic for part 2: the number of grid positions that have a robot and also have robots in all 4 neighbour cells must be at least k; I used k=10.
just luck, because tree could be only outlined
@@rastislavsvoboda4363 In the absence of any clear definition of what the Christmas tree would look like, it was a fair - and successful - guess, hence I wrote it was a heuristic. The aim is to solve the puzzle given, not to develop a solution for every possible case. Your solution based on a large connected component is equally a guess - the tree could have been formed by robots which are two cells apart and thus do not appear connected. But it is a very sound guess, and it worked.
@@mathiaskern7031 no problem, we are programmers and sometimes we need luck;
otherwise you need to generate pic by pic and try AI if it can see a tree there ;-)
Haha your poor tree fallen to the side. Good Video
I solved part 2 just by looking at states after each simulation. It's easy to spot a pattern, for my input after 99th, every 101st iterations robots gathered closer to center of grid, so I started printing only "interesting" grids and found the easter egg after 7371 (72 interesting) iterations.
what a funny puzzle, looks like it's a puzzle in heuristics
you could see a horizontal pattern at i and a vertical pattern at j
so chinese remainder theorem for *result mod 103 = i* and *result mod 101 = j*
> The problem is you cannot print out like 7000 grids.
Oh but you can!!
2 eroor