this post was submitted on 06 Dec 2024
17 points (100.0% liked)

Advent Of Code

979 readers
19 users here now

An unofficial home for the advent of code community on programming.dev!

Advent of Code is an annual Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like.

AoC 2024

Solution Threads

M T W T F S S
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25

Rules/Guidelines

Relevant Communities

Relevant Links

Credits

Icon base by Lorc under CC BY 3.0 with modifications to add a gradient

console.log('Hello World')

founded 1 year ago
MODERATORS
Ategon
[email protected]
CameronDev
17
[2024 Day 6] What is the optimal algorithm for Part 2? (self.advent_of_code)
submitted 2 weeks ago by Pyro to c/advent_of_code
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
[–] [email protected] 2 points 2 weeks ago (1 children)

I'm not sure I understand the concern, maybe a visualization would help describe what you're talking about? I updated my comment to describe my process in better detail, it was confusing before. I'm only focused in checking unobstructed straight lines from places where the guard has turned, so I don't think it could get into unexplored areas.

[–] [email protected] 1 points 2 weeks ago* (last edited 2 weeks ago) (1 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.

[–] [email protected] 2 points 2 weeks ago* (last edited 2 weeks ago) (1 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.

[–] [email protected] 1 points 2 weeks ago (1 children)

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

[–] [email protected] 2 points 1 week ago (1 children)

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?

[–] [email protected] 2 points 1 week 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!