tjf's recent activity

Comment on Day 9: Disk Fragmenter in ~comp.advent_of_code

tjf

December 10

Link

Part 2 is slow, but I'm sick of thinking about disk defrag so I'm calling it a day. After doing some ahead-of-time indexing, I got it down to about 6s. My Python solutions: Part 1 import itertools...

Part 2 is slow, but I'm sick of thinking about disk defrag so I'm calling it a day. After doing some ahead-of-time indexing, I got it down to about 6s. My Python solutions:

Part 1

import itertools
import sys

flatten = itertools.chain.from_iterable
disk = list(flatten([i // 2] * int(char) if not i % 2 else [-1] * int(char)
                    for i, char in enumerate(sys.stdin.read().strip())))
left = 0
right = len(disk) - 1
while left < right:
    if disk[left] < 0 and disk[right] >= 0:
        disk[left] = disk[right]
        disk[right] = -1
    left += disk[left] >= 0
    right -= disk[right] < 0

print(sum(i * int(char) for i, char in enumerate(disk) if char >= 0))

Part 2

from collections import Counter
import itertools
import sys

def index_disk(disk: list[int]) -> tuple[dict[int, int], dict[int, int]]:
    free_blocks = {}
    free_len = 0
    file_ids = {}
    for i in range(len(disk)):
        if disk[i] < 0:
            free_len += 1
            continue
        if free_len > 0:
            free_blocks[i - free_len] = free_len
        free_len = 0
        if disk[i] not in file_ids:
            file_ids[disk[i]] = i
    return free_blocks, file_ids

def find_free_blocks(free_blocks: dict[int, int], file_idx: int, file_len: int) -> tuple[int, int]:
    for free_idx, free_len in sorted(free_blocks.items()):
        if free_idx < file_idx and free_len >= file_len:
            return free_idx, free_len
    return -1, 0

flatten = itertools.chain.from_iterable
disk = list(flatten([i // 2] * int(char) if not i % 2 else [-1] * int(char)
                    for i, char in enumerate(sys.stdin.read().strip())))
free_blocks, file_ids = index_disk(disk)
file_lens = Counter(block for block in disk if block > 0)
for file_id, file_idx in sorted(file_ids.items(), reverse=True):
    file_len = file_lens[file_id]
    free_idx, free_len = find_free_blocks(free_blocks, file_idx, file_len)
    if free_idx < 0:
        continue
    for i in range(file_len):
        disk[free_idx + i] = file_id
        disk[file_idx + i] = -1
    del free_blocks[free_idx]
    if free_len > file_len:
        free_blocks[free_idx + file_len] = free_len - file_len

print(sum(i * int(char) for i, char in enumerate(disk) if char >= 0))

1 vote

Comment on Day 8: Resonant Collinearity in ~comp.advent_of_code

tjf

December 9

Link

I constructed complex-valued parametric equations for lines through antennae which is probably overthinking things, but it works. Python's itertools.combinations was also useful today. My Python...

I constructed complex-valued parametric equations for lines through antennae which is probably overthinking things, but it works. Python's itertools.combinations was also useful today. My Python solutions:

Part 1

from collections import defaultdict
import itertools
import sys

def antinodes_in_bounds(w: int, h: int, z1: complex, z2: complex) -> list[complex]:
    a1 = 2 * z1 - z2
    a2 = 2 * z2 - z1
    return [a for a in (a1, a2) if 0 <= a.real < w and 0 >= a.imag > -h]

w, h = 0, 0
freqs = defaultdict[str, list[complex]](list)
for b, line in enumerate(sys.stdin):
    w = len(line.strip())
    h += 1
    for a, char in enumerate(line.strip()):
        if char != '.':
            freqs[char].append(complex(a, -b))

antinodes = set()
for antennae in freqs.values():
    for z1, z2 in itertools.combinations(antennae, 2):
        antinodes.update(antinodes_in_bounds(w, h, z1, z2))

print(len(antinodes))

Part 2

from collections import defaultdict
import itertools
import sys

def antinodes_in_bounds(w: int, h: int, z1: complex, z2: complex) -> list[complex]:
    # place bounds on t for the parametrized line f(t) = (z2 - z1) * t + z1
    top = -z1.imag / (z2 - z1).imag
    bottom = (-(h - 1) - z1.imag) / (z2 - z1).imag
    left = -z1.real / (z2 - z1).real
    right = ((w - 1) - z1.real) / (z2 - z1).real
    t1, t2 = map(int, sorted((top, bottom, left, right))[1:3])

    # compute f(t) at integer values of t in [t1, t2]
    return [(z2 - z1) * t + z1 for t in range(t1, t2 + 1)]

w, h = 0, 0
freqs = defaultdict[str, list[complex]](list)
for b, line in enumerate(sys.stdin):
    w = len(line.strip())
    h += 1
    for a, char in enumerate(line.strip()):
        if char != '.':
            freqs[char].append(complex(a, -b))

antinodes = set()
for antennae in freqs.values():
    for z1, z2 in itertools.combinations(antennae, 2):
        antinodes.update(antinodes_in_bounds(w, h, z1, z2))

print(len(antinodes))

1 vote

Comment on Day 6: Guard Gallivant in ~comp.advent_of_code

tjf

December 6

Link

Having the same frustration as basically everyone else here. Part 2 works, but it's slow (roughly 20 seconds for both CPython and PyPy). I would like to think about the problem more and come back...

Having the same frustration as basically everyone else here. Part 2 works, but it's slow (roughly 20 seconds for both CPython and PyPy). I would like to think about the problem more and come back to it in a few hours, but future me might be too tired. I did get to use complex numbers again, though, which makes me happy. My Python solutions:

Part 1

import sys

def move_guard(lab: dict[complex, str], pos: complex, heading: complex) -> tuple[complex, complex]:
    if lab[pos + heading] == '#':
        heading *= -1j
    else:
        pos += heading
        lab[pos] = 'X'
    return pos, heading

lab = {}
for b, line in enumerate(sys.stdin):
    for a, char in enumerate(line.strip()):
        if char == '^':
            startpos = complex(a, -b)
            char = 'X'
        lab[complex(a, -b)] = char

pos = startpos
heading = 1j
while pos + heading in lab:
    pos, heading = move_guard(lab, pos, heading)

print(sum(char == 'X' for char in lab.values()))

Part 2

from collections.abc import Iterator
import sys

def move_guard(lab: dict[complex, str], pos: complex, heading: complex) -> tuple[complex, complex]:
    if lab[pos + heading] == '#':
        heading *= -1j
    else:
        pos += heading
        lab[pos] = 'X'
    return pos, heading

def obstruction_candidates(_lab: dict[complex, str], pos: complex, heading: complex) -> Iterator[complex]:
    lab = _lab.copy()
    while pos + heading in lab:
        oldchar = lab[pos + heading]
        pos, heading = move_guard(lab, pos, heading)
        if oldchar == '.':
            yield pos

def would_loop(_lab: dict[complex, str], pos: complex, heading: complex, obstruction: complex) -> bool:
    lab = _lab.copy()
    lab[obstruction] = '#'
    history = set()
    while pos + heading in lab:
        if (pos, heading) in history:
            return True
        history.add((pos, heading))
        pos, heading = move_guard(lab, pos, heading)
    return False

lab = {}
for b, line in enumerate(sys.stdin):
    for a, char in enumerate(line.strip()):
        if char == '^':
            startpos = complex(a, -b)
            char = 'X'
        lab[complex(a, -b)] = char

print(sum(would_loop(lab, startpos, 1j, candidate)
          for candidate in obstruction_candidates(lab, startpos, 1j)))

1 vote

Comment on Day 5: Print Queue in ~comp.advent_of_code
tjf
December 6
Link Parent
A neat Python type you might like is collections.defaultdict. That will let you access and manipulate a dictionary without checking whether a key is already present. If it's not, it gets created...

A neat Python type you might like is collections.defaultdict. That will let you access and manipulate a dictionary without checking whether a key is already present. If it's not, it gets created with some user-chosen default value (such as an empty set). E.g. ruleset = defaultdict(set) will let you do ruleset[after].add(before) without having to check if after not in ruleset.

3 votes
Comment on Fitness Weekly Discussion in ~health
tjf
December 5
Link
I've been running 3-5 days per week since the spring, but now that it's getting cold here (Northeastern US) I'm finding it takes much more willpower to keep my streak. There's always the...

I've been running 3-5 days per week since the spring, but now that it's getting cold here (Northeastern US) I'm finding it takes much more willpower to keep my streak. There's always the treadmill, but I much prefer the fresh air and scenery once I've started out. The earlier sunsets are also a bummer, but I'll either shift my runs to the morning or invest in a good headlamp and reflective clothing.

4 votes

Comment on Day 5: Print Queue in ~comp.advent_of_code

tjf

December 5 (edited December 5)

Link

Once again, input sizes are small enough that I don't have to be clever. My Python solutions: Part 1 from collections import defaultdict import itertools import sys def is_correctly_ordered(rules:...

Once again, input sizes are small enough that I don't have to be clever. My Python solutions:

Part 1

from collections import defaultdict
import itertools
import sys

def is_correctly_ordered(rules: defaultdict[int, list[int]], update: list[int]) -> bool:
    for x, y in itertools.pairwise(update):
        if x in rules[y]:
            return False
    return True

rules_input, updates_input = sys.stdin.read().split('\n\n')
rules = defaultdict[int, list[int]](list)
for line in rules_input.split('\n'):
    x, y = map(int, line.split('|'))
    rules[x].append(y)

total = 0
for line in updates_input.strip().split('\n'):
    update = [*map(int, line.split(','))]
    if is_correctly_ordered(rules, update):
        total += update[len(update) // 2]

print(total)

Part 2

from collections import defaultdict
import functools
import itertools
import sys

def is_correctly_ordered(rules: defaultdict[int, list[int]], update: list[int]) -> bool:
    for x, y in itertools.pairwise(update):
        if x in rules[y]:
            return False
    return True

# XXX: relies on rules being global (cmp_to_key functions take exactly 2 args)
def cmp(x: int, y: int) -> int:
    if x in rules[y]:
        return 1
    elif y in rules[x]:
        return -1
    else:
        return 0

rules_input, updates_input = sys.stdin.read().split('\n\n')
rules = defaultdict[int, list[int]](list)
for line in rules_input.split('\n'):
    x, y = map(int, line.split('|'))
    rules[x].append(y)

total = 0
for line in updates_input.strip().split('\n'):
    update = [*map(int, line.split(','))]
    if not is_correctly_ordered(rules, update):
        fixed = sorted(update, key=functools.cmp_to_key(cmp))
        total += fixed[len(fixed) // 2]

print(total)

Edit: I went back and used a closure returning a lambda to clean up that awkward cmp function. Before it relied on rules being global, since functools.cmp_to_key functions take exactly 2 arguments.

def cmp_with_rules(rules: defaultdict[int, list[int]]) -> Callable[[int, int], int]:
    return lambda x, y: 1 if x in rules[y] else (-1 if y in rules[x] else 0)

1 vote

Comment on Day 4: Ceres Search in ~comp.advent_of_code

tjf

December 5

Link

Brute force, but it worked well enough. I found complex numbers useful here for storing and shifting coordinates. My Python solutions: Part 1 import sys DIRECTIONS = ( (0, 1, 2, 3), # up (0, -1j,...

Brute force, but it worked well enough. I found complex numbers useful here for storing and shifting coordinates. My Python solutions:

Part 1

import sys

DIRECTIONS = (
    (0, 1, 2, 3),                       # up
    (0, -1j, -2j, -3j),                 # down
    (0, -1, -2, -3),                    # left
    (0, 1j, 2j, 3j),                    # right
    (0, -1 - 1j, -2 - 2j, -3 - 3j),     # diagonal down and left
    (0, -1 + 1j, -2 + 2j, -3 + 3j),     # diagonal up and left
    (0, 1 + 1j, 2 + 2j, 3 + 3j),        # diagonal up and right
    (0, 1 - 1j, 2 - 2j, 3 - 3j),        # diagonal down and right
)

grid = {}
for a, line in enumerate(sys.stdin):
    for b, char in enumerate(line.strip()):
        grid[complex(a, b)] = char

total = 0
for coord in grid:
    for direction in DIRECTIONS:
        if ''.join(grid.get(coord + d, '') for d in direction) == 'XMAS':
            total += 1

print(total)

Part 2

import sys

DIRECTIONS = (
    (-1 + 1j, 0, 1 - 1j),   # diagonal upper left to lower right
    (-1 - 1j, 0, 1 + 1j),   # diagonal lower left to upper right
)

grid = {}
for a, line in enumerate(sys.stdin):
    for b, char in enumerate(line.strip()):
        grid[complex(a, b)] = char

total = 0
for coord in grid:
    diag1 = ''.join(grid.get(coord + d, '') for d in DIRECTIONS[0])
    diag2 = ''.join(grid.get(coord + d, '') for d in DIRECTIONS[1])
    if diag1 in ('MAS', 'SAM') and diag2 in ('MAS', 'SAM'):
        total += 1

print(total)

3 votes

Comment on Day 3: Mull It Over in ~comp.advent_of_code

tjf

December 3

Link

I feared regex would only get me so far, but it worked for both parts quite well! My Python solutions: Part 1 import re import sys operands = re.findall(r'mul\((\d{1,3}),(\d{1,3})\)',...

I feared regex would only get me so far, but it worked for both parts quite well! My Python solutions:

Part 1

import re
import sys

operands = re.findall(r'mul\((\d{1,3}),(\d{1,3})\)', sys.stdin.read())
print(sum(int(x) * int(y) for x, y in operands))

Part 2

import re
import sys

memory = re.sub(r"don't\(\).*?(do\(\)|$)", '', sys.stdin.read(), flags=re.DOTALL)
operands = re.findall(r'mul\((\d{1,3}),(\d{1,3})\)', memory)
print(sum(int(x) * int(y) for x, y in operands))

3 votes

Comment on Day 2: Red-Nosed Reports in ~comp.advent_of_code

tjf

December 3

Link

Here are my Python solutions. I'm not doing them right at midnight this year, just when I have the time. Part 1 import sys def is_safe(report: list[int]) -> bool: diffs = [a - b for a, b in...

Here are my Python solutions. I'm not doing them right at midnight this year, just when I have the time.

Part 1

import sys

def is_safe(report: list[int]) -> bool:
    diffs = [a - b for a, b in zip(report, report[1:])]
    return is_strictly_monotone(diffs) and is_gradual(diffs)

def is_strictly_monotone(diffs: list[int]) -> bool:
    return abs(sum(abs(d) // d if d else 0 for d in diffs)) == len(diffs)

def is_gradual(diffs: list[int]) -> bool:
    return all(1 <= abs(d) <= 3 for d in diffs)

safe = sum(is_safe([*map(int, line.split())]) for line in sys.stdin)
print(safe)

Part 2

import sys

def is_safe(report: list[int], tolerate: bool = True) -> bool:
    diffs = [a - b for a, b in zip(report, report[1:])]
    if is_strictly_monotone(diffs) and is_gradual(diffs):
        return True
    if tolerate:
        for i in range(len(report)):
            subreport = report[:i] + report[i + 1:]
            if is_safe(subreport, tolerate=False):
                return True
    return False

def is_strictly_monotone(diffs: list[int]) -> bool:
    return abs(sum(abs(d) // d if d else 0 for d in diffs)) == len(diffs)

def is_gradual(diffs: list[int]) -> bool:
    return all(1 <= abs(d) <= 3 for d in diffs)

safe = sum(is_safe([*map(int, line.split())]) for line in sys.stdin)
print(safe)

2 votes

Comment on What are your ten favourite movies of all time? in ~movies
tjf
August 15
Link
I wasn't going to comment since it's such a huge thread, but I noticed a lack of my favorite filmmakers (Terrence Malick, Wong Kar-wai, Charlie Kaufman). So here is my list, limited to one movie...
I wasn't going to comment since it's such a huge thread, but I noticed a lack of my favorite filmmakers (Terrence Malick, Wong Kar-wai, Charlie Kaufman). So here is my list, limited to one movie per director. If you asked me again in a month it will have changed a bit, since I will have changed a bit myself.
1. The Tree of Life (Malick, 2011)
2. Synecdoche, New York (Kaufman, 2008)
3. Chungking Express (Wong, 1994)
4. Rushmore (W. Anderson, 1998)
5. The Umbrellas of Cherbourg (Demy, 1964)
6. Eternal Sunshine of the Spotless Mind (Gondry, 2004)
7. Mirror (Tarkovsky, 1975)
8. First Reformed (Schrader, 2017)
9. Modern Times (Chaplin, 1936)
10. Barry Lyndon (Kubrick, 1975)
6 votes
Comment on Zig: The small language (2022) in ~comp
tjf
August 14
Link
My only significant use of Zig so far is as a nicer way to interface with C libraries, specifically the forthcoming SDL3. And for that it's kind of perfect. The build system is so much better than...

My only significant use of Zig so far is as a nicer way to interface with C libraries, specifically the forthcoming SDL3. And for that it's kind of perfect. The build system is so much better than writing janky makefiles and I appreciate the compiler's sensible defaults. I also like that the language itself is documented on a single big web page. Zig feels a lot more approachable to me than some of the other C replacement languages out there.

10 votes
Comment on Announcing the Ladybird Browser Initiative in ~tech
tjf
July 1
Link Parent
Totally agree re: the new website design. The old site (archive) was way more charming and less sterile. Though I do like the switch from .dev to .org.

Totally agree re: the new website design. The old site (archive) was way more charming and less sterile. Though I do like the switch from .dev to .org.

7 votes
Comment on What email client do you use? in ~tech
tjf
April 3
Link
On my Linux desktops I use aerc, a terminal-based client. I use its maildir backend, so everything feels snappy. Syncing between my hard drives and the IMAP server is handled by a cronjob running...

On my Linux desktops I use aerc, a terminal-based client. I use its maildir backend, so everything feels snappy. Syncing between my hard drives and the IMAP server is handled by a cronjob running mbsync. Prior to aerc I used mutt (specifically neomutt).

On my iPhone I use plain old mail.app. It’s fine, and I do most of email work on desktop anyway. The major third-party mail apps on iOS all seem to have something fundamentally unacceptable to me, such as mail provider lock-in, non-native UI, annoying AI integrations, and other privacy nightmares like fetching your mail onto their own servers. So stock mail.app it is for me.
Comment on Best foreign films and TV shows? in ~tv
tjf
March 16
Link Parent
I love Drive My Car, so I'll chime in to recommend Wheel of Fortune and Fantasy (TMDB, IMDb, Letterboxd) which is also directed by Ryusuke Hamaguchi (and released in the same year!). It's an...

I love Drive My Car, so I'll chime in to recommend Wheel of Fortune and Fantasy (TMDB, IMDb, Letterboxd) which is also directed by Ryusuke Hamaguchi (and released in the same year!). It's an anthology film in three parts, a structure I wish more filmmakers played with.

1 vote
Comment on When do you listen to podcasts? in ~life
tjf
March 12
Link
As others have mentioned, I like to listen to podcasts while doing household chores (washing dishes, folding laundry, cooking dinner). But I'm careful to give my ears a break sometimes, e.g. when...

As others have mentioned, I like to listen to podcasts while doing household chores (washing dishes, folding laundry, cooking dinner). But I'm careful to give my ears a break sometimes, e.g. when I go for a walk or take a shower or fall asleep. I find I have my best thoughts and ideas in these settings, and my mind can't wander and pay attention to a podcast at the same time.

1 vote
Comment on LeBron James' path to 40,000 career regular-season points in ~sports.basketball
tjf (OP)
March 4
Link
Last night LeBron James hit the 40k mark. This is a cool timeline charting his career leading up to that moment. Ironically the Lakers ended up losing the game, which also happened last season...

Last night LeBron James hit the 40k mark. This is a cool timeline charting his career leading up to that moment. Ironically the Lakers ended up losing the game, which also happened last season when LeBron broke Kareem's record to become the all-time leading scorer. It's hard to see anyone catching this record.

3 votes
LeBron James' path to 40,000 career regular-season points

~sports.basketball Article 279 words

1 comment

espn.com

March 4

7 votes
Comment on 50 Algorithms Every Programmer Should Know (Second Edition) in ~comp
tjf
January 4
Link Parent
I wouldn't be surprised if this book was itself written by an LLM, seeing how clickbaity that sounds.

I wouldn't be surprised if this book was itself written by an LLM, seeing how clickbaity that sounds.

13 votes
Comment on Day 10: Pipe Maze in ~comp.advent_of_code
tjf
December 11, 2023
Link Parent
I can confirm my input had this property too, and I am thankful for it.

I can confirm my input had this property too, and I am thankful for it.

2 votes

Comment on Day 10: Pipe Maze in ~comp.advent_of_code

tjf

December 11, 2023

Link

Nice ramp up in difficulty from part one to two, which I always appreciate. Seems like there were a couple different ways to solve this, and I'm not convinced mine is a great one. But it works!...

Nice ramp up in difficulty from part one to two, which I always appreciate.
Seems like there were a couple different ways to solve this, and I'm not
convinced mine is a great one. But it works! And it's fast enough to not care
too much.

Here are my Python solutions, albeit messy ones:

Part 1

Not too bad for a part one. Walk the graph from S all the way back to itself,
keeping track of steps travelled. Then it works out that the farthest piece
in the loop from S is half that total loop length.

#!/usr/bin/env python3

from collections import defaultdict 

DIRECTIONS = (-1 + 0j, 1 + 0j, 0 - 1j, 0 + 1j)
CONNECTIONS = {'|': (-1 + 0j, 1 + 0j),
               '-': (0 - 1j, 0 + 1j),
               'L': (-1 + 0j, 0 + 1j),
               'J': (-1 + 0j, 0 - 1j),
               '7': (0 - 1j, 1 + 0j),
               'F': (0 + 1j, 1 + 0j),
               '.': (),
               ' ': ()}

# now that we know the coordinates of 'S', replace it with the pipe that fits
def normalize_start(g, start):
    v = tuple(d for d in DIRECTIONS if any(start + d + conn == start
                                           for conn in CONNECTIONS[g[start + d]]))
    pipe = next(k for k in CONNECTIONS if set(CONNECTIONS[k]) == set(v))
    g[start] = pipe

# walk around the main loop, return number of steps to make it all the way around
def walk_loop(g, start):
    steps = 2
    visited = set([start])
    start_conns = tuple(start + conn for conn in CONNECTIONS[g[start]])
    here = start_conns[0]
    while here != start_conns[1]:
        visited.add(here)
        here = next(filter(lambda pos: pos not in visited,
                           (here + conn for conn in CONNECTIONS[g[here]])))
        steps += 1
    return steps

G = defaultdict(lambda: '.')
for r, line in enumerate(open(0)):
    for c, char in enumerate(line.strip()):
        G[complex(r, c)] = char
start = next(pos for pos, char in G.items() if char == 'S')
normalize_start(G, start)
steps_around = walk_loop(G, start)
print(steps_around // 2)

Part 2

The trickiest part in part two was the notion that tiles could squeeze between
pipes to be considered non-enclosed. My idea to attack this is to "zoom in" on
the graph, effectively putting empty spaces between every tile in the original
graph. Because I used complex coordinates, this was as easy as multiplying
coordinates by 2 and then filling in vertical and horizontal pipe pieces that
belonged in the newly created empty spaces. I also turned all non-mainloop pipes
into ground pipes (dots) to make things easier. Then I used flood fill on the
new zoomed graph on the exterior of the loop found the difference between all
ground tiles and these exterior ground tiles to end up with the final answer.

#!/usr/bin/env python3

from collections import defaultdict, deque

DIRECTIONS = (-1 + 0j, 1 + 0j, 0 - 1j, 0 + 1j)
CONNECTIONS = {'|': (-1 + 0j, 1 + 0j),
               '-': (0 - 1j, 0 + 1j),
               'L': (-1 + 0j, 0 + 1j),
               'J': (-1 + 0j, 0 - 1j),
               '7': (0 - 1j, 1 + 0j),
               'F': (0 + 1j, 1 + 0j),
               '.': (),
               ' ': ()}

# now that we know the coordinates of 'S', replace it with the pipe that fits
def normalize_start(g, start):
    v = tuple(d for d in DIRECTIONS if any(start + d + conn == start
                                           for conn in CONNECTIONS[g[start + d]]))
    pipe = next(k for k in CONNECTIONS if set(CONNECTIONS[k]) == set(v))
    g[start] = pipe

# walk around the main loop, return a set containing the coords of all its pieces
def walk_loop(g, start):
    visited = set([start])
    start_conns = tuple(start + conn for conn in CONNECTIONS[g[start]])
    here = start_conns[0]
    while here != start_conns[1]:
        visited.add(here)
        here = next(filter(lambda pos: pos not in visited,
                           (here + conn for conn in CONNECTIONS[g[here]])))
    visited.add(here)
    return visited

# returns a "zoomed in" graph with empty space between the original's tiles
def zoom(g, loop, factor=2):
    zg = defaultdict(lambda: ' ')
    for pos, char in g.items():
        zg[pos * factor] = char
    zloop = {pos * factor for pos in loop}
    for pos, char in zg.items():
        if char in ('|-LJ7F') and pos not in zloop:
            zg[pos] = '.'    # set all extra pipes to ground tiles
    max_r = int(max(zg, key=lambda pos: pos.real).real)
    max_c = int(max(zg, key=lambda pos: pos.imag).imag)
    for r in range(0, max_r + 1):
        for c in range(0, max_c + 1):
            pos = complex(r, c)
            if zg[pos] == ' ':
                up, down, left, right = (pos + d for d in DIRECTIONS)
                if zg[up] in ('|7F') or zg[down] in ('|JL'):
                    zg[pos] = '|'    # fill in vertical pipe gaps
                elif zg[left] in ('-LF') or zg[right] in ('-J7'):
                    zg[pos] = '-'    # fill in horizontal pipe gaps
    return zg

# starting from outside of the main loop, flood tiles around the loop
# return a set containing the coords of all outside tiles
def flood(g):
    min_pos = complex(min(g, key=lambda pos: pos.real).real - 1,
                      min(g, key=lambda pos: pos.imag).imag - 1)
    max_pos = complex(max(g, key=lambda pos: pos.real).real + 1,
                      max(g, key=lambda pos: pos.imag).imag + 1)
    start = min_pos
    outside = set()
    todo = deque([start])
    while todo:
        here = todo.popleft()
        if here in outside:
            continue
        outside.add(here)
        for d in DIRECTIONS:
            pos = here + d
            if ((min_pos.real <= pos.real <= max_pos.real)
                and (min_pos.imag <= pos.imag <= max_pos.imag)
                and g[pos] in ('.', ' ')):
                todo.append(pos)
    return outside

G = defaultdict(lambda: '.')
for r, line in enumerate(open(0)):
    for c, char in enumerate(line.strip()):
        G[complex(r, c)] = char
start = next(pos for pos, char in G.items() if char == 'S')
normalize_start(G, start)
loop = walk_loop(G, start)
ZG = zoom(G, loop)
outside = flood(ZG)
num_enclosed = sum(pos not in outside and char == '.' for pos, char in ZG.items())
print(num_enclosed)

All in all I liked today's problem, as I often do with graph-type problems.
Also this is my first day this year that I chose to use complex numbers for
coordinates, which I think worked out well.

2 votes

tjf's recent activity

Comment on Day 9: Disk Fragmenter in ~comp.advent_of_code

Comment on Day 8: Resonant Collinearity in ~comp.advent_of_code

Comment on Day 6: Guard Gallivant in ~comp.advent_of_code

Comment on Day 5: Print Queue in ~comp.advent_of_code

Comment on Fitness Weekly Discussion in ~health

Comment on Day 5: Print Queue in ~comp.advent_of_code

Comment on Day 4: Ceres Search in ~comp.advent_of_code

Comment on Day 3: Mull It Over in ~comp.advent_of_code

Comment on Day 2: Red-Nosed Reports in ~comp.advent_of_code

Comment on What are your ten favourite movies of all time? in ~movies

Comment on Zig: The small language (2022) in ~comp

Comment on Announcing the Ladybird Browser Initiative in ~tech

Comment on What email client do you use? in ~tech

Comment on Best foreign films and TV shows? in ~tv

Comment on When do you listen to podcasts? in ~life

Comment on LeBron James' path to 40,000 career regular-season points in ~sports.basketball

Comment on 50 Algorithms Every Programmer Should Know (Second Edition) in ~comp

Comment on Day 10: Pipe Maze in ~comp.advent_of_code

Comment on Day 10: Pipe Maze in ~comp.advent_of_code