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?

  • lwhjp@lemmy.sdf.org
    1·
    5 days ago

    I’m imagining something like this:

    .#........
....#..#..
.O.......#
.........#
......#...
.^......#.

    The original path hits the leftmost two obstructions, whereas the new path avoids these but hits all the others (and loops).

    O is not on an intersection of any two turns in the original path. It is if you check all possible turning points, although there’s potentially a lot more of them.

    • bambooEnglish
      2·
      5 days ago

      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:

      • You need to pay attention to the rotation rule of the guard. Taking any random rotation points won’t take the guards rotation into effect and will result in false positives.
      • Thinking about the rectangle visualization, since you’re only trying to test opposite corners, you only need to compare one turn and turn + 2 to see if they finish the rectangle.

      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.

      • lwhjp@lemmy.sdf.org
        1·
        5 days ago

        Rectangles don’t account for all loops though, right? Couldn’t you have a loop with, say, 6 points in an L shape?

        • bambooEnglish
          2·
          4 days ago

          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?

          • lwhjp@lemmy.sdf.org
            2·
            4 days ago

            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!