I know that we can brute force it by placing an obstacle at every valid position in the path, but is there a more elegant / efficient solution?
I know that we can brute force it by placing an obstacle at every valid position in the path, but is there a more elegant / efficient solution?
Ohh that is helpful, yeah, i don’t know how I’d get these counted. This is probably the ones I’m missing. The way I’ve been thinking about it is that all a loop is is a rectangle. So basically each guard’s turn is a corner of a rectangle. By taking opposite corners (every other turn the guard makes) we can see if we can draw a full rectangle without hitting any walls. If we can, then that would make a loop.
A few things I figured out playing with this:
So maybe the logic would be to ignore the rotations in part one when the guard walks unobstructed, and do a pass through the whole map and mark each point of a possible rotation, and then drawing possible rectangles where 3 corners exist, to find an obstruction point. Then you can check if the obstruction point is in the set of steps the guard made in part 1 when unobstructed. Still though, I think this doesn’t take into account the guards rotation, so will probably be wrong.
Rectangles don’t account for all loops though, right? Couldn’t you have a loop with, say, 6 points in an L shape?
Yeah you’re right. I keep focusing on the smaller example where everything is just rectangle loops, but the big map is way more complex. I do wonder though if an L shaped loop is just multiple rectangle loops combined though? Like if you can find all the rectangles, then find ones where combined they make bigger loops?
I mean, sure you can combine rectangles to make any path, but since there is no upper limit I don’t think that will help much. You may be on to something and I just can’t see it, though! Good luck!