16
[2024 Day 6] What is the optimal algorithm for Part 2? (programming.dev)
submitted 2 years ago by to c/advent_of_code@programming.dev
14 comments fedilink hide all child comments
 

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?

you are viewing a single comment's thread
view the rest of the comments
[–] 1 point 2 years ago* (last edited 2 years ago) (4 children)

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.

  • permalink
  • fedilink
  • source
  • parent
  • hideshow 4 child comments
    •
  • [–] 2 points 2 years ago* (3 children)

    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.

  • permalink
  • fedilink
  • source
  • parent
  • hideshow 3 child comments
    •
  • [–] 1 point 2 years ago (2 children)

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

  • permalink
  • fedilink
  • source
  • parent
  • hideshow 2 child comments
    •
  • [–] 2 points 2 years ago (1 child)

    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?

  • permalink
  • fedilink
  • source
  • parent
  • hideshow 1 child comment
    •
  • [–] 2 points 2 years 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!

  • permalink
  • fedilink
  • source
  • parent