Pyro

joined 2 years ago
[โ€“] Pyro@programming.dev 2 points 8 months ago (1 children)

Can you add your current code to the question? Maybe it's an edge case you're missing.

[โ€“] Pyro@programming.dev 2 points 8 months ago* (last edited 8 months ago) (1 children)

About 15-20 seconds, not too bad.

[โ€“] Pyro@programming.dev 5 points 8 months ago* (last edited 8 months ago) (10 children)

Python

Part 1: Simulate the guard's walk, keeping track of visited positions
Part 2: Semi brute-force. Try to place an obstacle at every valid position in the guard's original path and see if it leads to a loop.

import os
from collections import defaultdict

# paths
here = os.path.dirname(os.path.abspath(__file__))
filepath = os.path.join(here, 'input.txt')

# read input
with open(filepath, mode='r', encoding='utf8') as f:
    data = f.read()
rows = data.splitlines()

# bounds
m = len(rows)
n = len(rows[0])

# directions following 90 degree clockwise turns
#   up, right, down, left
DIRECTIONS = [(-1, 0), (0, 1), (1, 0), (0, -1)]

# find position of guard
guard_i, guard_j = -1, -1
for i in range(m):
    for j in range(n):
        if rows[i][j] == '^':
            guard_i, guard_j = i, j
            break
    if guard_i != -1:
        break


def part1(guard_i, guard_j):
    # keep track of visited positions
    visited = set()
    visited.add((guard_i, guard_j))

    dir_idx = 0     # current direction index

    # loop while guard is in map
    while True:
        delta_i, delta_j = DIRECTIONS[dir_idx]
        next_gi, next_gj = guard_i + delta_i, guard_j + delta_j   # next pos
        
        # if out of bounds, we are done
        if not (0 <= next_gi < m) or not (0 <= next_gj < n):
            break
        # change direction when obstacle encountered
        if rows[next_gi][next_gj] == "#":
            dir_idx = (dir_idx + 1) % 4
            continue
        # update position and visited
        guard_i, guard_j = next_gi, next_gj
        visited.add((guard_i, guard_j))

    print(f"{len(visited)=}")


def part2(guard_i, guard_j):
    # keep track of visited positions
    visited = set()
    visited.add((guard_i, guard_j))

    dir_idx = 0 # current direction index
    loops = 0   # loops encountered

    # walk through the path
    while True:
        delta_i, delta_j = DIRECTIONS[dir_idx]
        next_gi, next_gj = guard_i + delta_i, guard_j + delta_j # next pos
        
        # if out of bounds, we are done
        if not (0 <= next_gi < m) or not (0 <= next_gj < n):
            break
        # change direction when obstacle encountered
        if rows[next_gi][next_gj] == "#":
            dir_idx = (dir_idx + 1) % 4
            continue
        # if a position is not already in path,
        # put a obstacle there and see if guard will loop
        if (next_gi, next_gj) not in visited and willLoop(guard_i, guard_j, dir_idx):
            loops += 1
        # update position and visited
        guard_i, guard_j = next_gi, next_gj
        visited.add((guard_i, guard_j))
    
    print(f"{loops=}")

# used in part 2
# returns whether placing an obstacle on next pos causes a loop or not
def willLoop(guard_i, guard_j, dir_idx) -> bool:
    # obstacle pos
    obs_i, obs_j = guard_i + DIRECTIONS[dir_idx][0], guard_j + DIRECTIONS[dir_idx][1]

    # keep track of visited pos and the direction of travel
    visited: defaultdict[tuple[int, int], list[int]] = defaultdict(list)
    visited[(guard_i, guard_j)].append(dir_idx)
    
    # walk until guard exits map or loops
    while True:
        delta_i, delta_j = DIRECTIONS[dir_idx]
        next_gi, next_gj = guard_i + delta_i, guard_j + delta_j # next pos
        
        # if out of bounds, no loop
        if not (0 <= next_gi < m) or not (0 <= next_gj < n):
            return False
        # change direction when obstacle encountered
        if rows[next_gi][next_gj] == "#" or (next_gi == obs_i and next_gj == obs_j):
            dir_idx = (dir_idx + 1) % 4
            continue
        # we are looping if we encounter a visited pos in a visited direction
        if (next_gi, next_gj) in visited and dir_idx in visited[(next_gi, next_gj)]:
            return True
        
        # update position and visited
        guard_i, guard_j = next_gi, next_gj        
        visited[(guard_i, guard_j)].append(dir_idx)


part1(guard_i, guard_j)
part2(guard_i, guard_j)

[โ€“] Pyro@programming.dev 24 points 8 months ago (1 children)

Their war on emulation is the reason I'll never buy Nintendo again.

[โ€“] Pyro@programming.dev 2 points 8 months ago

Too much water

[โ€“] Pyro@programming.dev 17 points 8 months ago* (last edited 8 months ago) (1 children)

I would hold off on switching to AllDebrid for a bit, because they are also based in France and may be hit with a similar order.

[โ€“] Pyro@programming.dev 1 points 8 months ago

It sounds and looks really cool! Added to my list.

[โ€“] Pyro@programming.dev 8 points 8 months ago

Reading your comment and #32459, I realize that VSCode source control did have some major issues back then.

It looks like they have improved though, as the latest VSCode I use doesn't auto-initialize repositories anymore.

[โ€“] Pyro@programming.dev 5 points 8 months ago (1 children)

It's not that. It means discard all changes made after the last change committed to this local repository.

[โ€“] Pyro@programming.dev 10 points 8 months ago* (last edited 8 months ago) (2 children)

~~He wouldn't have seen the "Discard Changes" button at all if source control wasn't already setup (and detected by VSCode).~~

~~No sane program will delete files when you initialize source control either.~~

As I found later, VSCode did have weird behaviors with source control back then. My experience is more with the latest versions.

[โ€“] Pyro@programming.dev 3 points 8 months ago* (last edited 8 months ago) (3 children)

"Changes" encompass more than you think. Creating / Deleting files are also changes, not just edits to a file.

  • If the change is an edit to a tracked file, "Discard Changes" will reverse the edit.
  • If the change is deleting a tracked file, "Discard Changes" will restore it back.
  • If the change is a new untracked file, "Discard Changes" will remove it as intended.

It can also be all of them at the same time, which is why VSCode uses "Changes" instead of "Files".

[โ€“] Pyro@programming.dev 2 points 8 months ago

Look at what they need to mimic a fraction of my cuteness.

view more: โ€น prev next โ€บ