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

  • CameronDevOPM
    3·
    5 days ago

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

    • Deebster
      3·
      5 days ago

      My rust code ran in 6s on my phone (Samsung A35 running under Termux). When I’m back at a computer it’d be interesting to compare times properly.

    • Pyro
      2·
      5 days ago

      About 15-20 seconds, not too bad.

      • CameronDevOPM
        1·
        5 days 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.

      • CameronDevOPM
        2·
        5 days ago

        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.

        • TunaCowboy@lemmy.world
          2·
          5 days 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.

        • Leavingoldhabits@lemmy.world
          2·
          5 days ago

          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.

          • CameronDevOPM
            1·
            5 days ago

            That’s probably quite optimal, compared with checking every state in the path, or running off a fixed number of steps

    • iAvicenna@lemmy.world
      1·
      5 days ago

      I did a similar approach (place obstacles on guards path). Takes about 80s 10-15s in 11th Gen Intel® Core™ 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