26
πŸ’‚ - 2024 DAY 6 SOLUTIONS - πŸ’‚ (programming.dev)
submitted 2 years ago by [M] to c/advent_of_code@programming.dev
39 comments fedilink hide all child comments
 

Day 6: Guard Gallivant

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

you are viewing a single comment's thread
view the rest of the comments
[–] [S] 3 points 2 years ago (4 children)

How long did brute force take? Mine was 9s on an m1 with rust.

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

    About 15-20 seconds, not too bad.

  • permalink
  • fedilink
  • source
  • parent
  • hideshow 2 child comments
    •
  • [–] [S] 1 point 2 years ago*

    I got mine down to 3s, but it wasn't a very smart loop detection. All I did was count steps and stop after 10000. The 9 second run was 100000 steps, which is obviously a bit excessive.

    Does save iterating over the list of past visits, so probably a good shortcut.

  • permalink
  • fedilink
  • source
  • parent
  • [–] 1 point 2 years ago* (last edited 2 years ago)

    I did a similar approach (place obstacles on guards path). Takes about 80s 10-15s in 11th Gen Intel(R) Core(TM) i7-11800H. Motivated by the code above, I also restricted the search to start right before the obstacle rather than the whole path which took it down from 80s to 10-15s

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

    Mine was 9s

    That's about how long it takes for my python solution to complete.

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

    How did you detect loops? I just ran for 100000 steps to see if I escaped, got my time down to 3s by doing only 10000 steps.

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

    Not who you asked but: I save coordinates and direction into a vector each time the guard faces a #. Also every time the guard faces a #, I check if the position exists in the vector, if true, it’s an infinite loop. 78ms rust aolution.

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

    I added each visited position/direction to a set, and when a 'state' is reached again you have entered a loop:

    v = set()
while t[g.r][g.c] != 'X':
    state = (g.r, g.c, g.d)
    if state in v:
        acc += 1
        break
    v.add(state)
    g.move(t)

    You can view my full solution here.

  • permalink
  • fedilink
  • source
  • parent