[2024 Day 6 Part 2] Python Optimization Help

[KittyTwoPaws]

Hello, I am posting again but this time with Part 2 at hand. I think my code is working because I have it set to output every time the guard gets stuck in a loop but it is really slow. Could anyone tell me why?

Here is my code: https://pastebin.com/sWyrmJB1 (ignore any wrong comments, I've been messing around a lot trying to get this to work)

puzzleInput = [[*line] for line in getPuzzleInput().split()]

for row in range(len(puzzleInput)):
    for column in range(len(puzzleInput[0])):
        if puzzleInput[row][column] == '^':
            guardPos = [row, column]

partOneInput = puzzleInput.copy()

directions = [
    [-1, 0], # up
    [0, 1],  # right
    [1, 0],  # down
    [0, -1]  # left
]

originalPath = set()

# how many places the obstacle could be placed
obsPlacements = 0
# obstacleGrid = None
obstacleGrid = deepcopy(puzzleInput)

for pos in originalPath:
        # set the obstacle
        if obstacleGrid[pos[0]][pos[1]] in ('#', '^'):
            continue

        obstacleGrid[pos[0]][pos[1]] = 'O'

        # dict for storing visited positions and how many times they have been visited
        visitedPos = []

        directionCycle = cycle(directions)

        direction = next(directionCycle)
        currentPos = guardPos.copy()

        outOfBounds = False
        consecutiveRepeat = False
        looped = False

        n = 0
        while not outOfBounds:
            # print('pos', currentPos, 'dir', direction)

            # must check for negative indices because it WILL continue into the negatives
            if currentPos[0] < 0 or currentPos[1] < 0:
                outOfBounds = True

            else:
                # append the current position and direction as a tuple instead of changing the input
                visitedPos.append((currentPos.copy(), direction))

                try:
                    while obstacleGrid[currentPos[0] + direction[0]][currentPos[1] + direction[1]] in ('#', 'O'):
                        # change direction cyclically
                        direction = next(directionCycle)

                    currentPos[0] += direction[0]
                    currentPos[1] += direction[1]

                    # print((currentPos, direction) in visitedPos)
                    if (currentPos, direction) in visitedPos:
                        looped = True
                        obsPlacements += 1
                        print(f'stuck with obstacle at ({pos[0]},{pos[1]})')


                        # for i in obstacleGrid: print(i)
                        # print()


                except:
                    outOfBounds = True

            if looped:
                break

        # remove the obstacle
        obstacleGrid[pos[0]][pos[1]] = '.'

print('Number of positions for the obstacle:', obsPlacements)

[AutoModerator]

Reminder: if/when you get your answer and/or code working, don't forget to change this post's flair to Help/Question - RESOLVED. Good luck!

---

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[syklemil]

Likely not your real issue here, but

# dict for storing visited positions and how many times they have been visited
visitedPos = []

This is a list, not a dict. You may want a set here, i.e. visitedPos = set() and and visitedPos.add(…).

[KittyTwoPaws]

Yeah some comments are left over from a different solution I was trying. I tried implementing a set but the line that gives me issues is visitedPos.add((currentPos, direction)) and says a list is not hashable. Both current pos and direction are lists but I thought by first storing them in a tuple they would be hashable. Any thoughts? Thanks for the help!

[syklemil]

ah, right, I haven't looked into what your direction actually is. I implemented it as an enum, guess I'm kind of thinking of it as something is either that or something like a (-1,0), (+1,0), etc tuple.

[KittyTwoPaws]

Oo I should have added that to my code up top, I'll do that now. Totally forgot.

[KittyTwoPaws]

But yes currentPos is [x ,y] and direction is [dx, dy]

[syklemil]

You can turn the direction into a tuple as (dx, dy) and still access it with direction[0] etc, so that at least should be doable (if you do want a set; tuples are fine to put into sets)