mawelborn's recent activity
-
Comment on Day 10: Factory in ~comp.advent_of_code
-
Comment on Day 9: Movie Theater in ~comp.advent_of_code
mawelborn Link ParentI love the idea of compressing the coordinate space to be able to represent it as a full grid instead of sparse set of points. That's so clever!I love the idea of compressing the coordinate space to be able to represent it as a full grid instead of sparse set of points. That's so clever!
-
Comment on Day 9: Movie Theater in ~comp.advent_of_code
mawelborn (edited )LinkWow, I don't think I've seen such a jump in difficulty between Part 01 and Part 02. The first part was trivially easy, and the second part I have basically given up on a pleasing solution... or...Wow, I don't think I've seen such a jump in difficulty between Part 01 and Part 02. The first part was trivially easy, and the second part I have basically given up on a pleasing solution... or even a general one.
Given the large search space, I knew the in-memory representation had to be sparse, and I'd likely need to take some shortcuts based on my particular input. I ran a validator and confirmed that no 2 consecutive red tiles are adjacent and no 3 consecutive red tiles are collinear. Based on that I figured it's likely a rectangle is "inside" if it doesn't intersect any edges.
My original approach was to use set intersection to test every edge simultaneously (or at least let the CPython set intersection code do it for me which I hoped would be fast). Alas no. This is catastrophically slow given the size of the grid (and is still running). I afterwards switched to a sparser line/box intersection check for each edge that completes in ~10 seconds.
There are many adversarial inputs for which my solution doesn't work. Even for the sample input it gets the right answer but using the wrong corner tiles. The selected rectangle is technically "outside." It feels hacky and unearned; plus I just kind of don't like it code-wise.
:/
Part 1
Tile = namedtuple("Tile", ["x", "y"]) def solve(input: str) -> int: return max(map(area, combinations(red_tiles(input), r=2))) def red_tiles(input: str) -> Iterator[Tile]: for line in input.split(): yield Tile(*map(int, line.split(","))) def area(a_b: tuple[Tile, Tile]) -> int: a, b = a_b return ( (abs(a.x - b.x) + 1) * (abs(a.y - b.y) + 1) )Part 2
Tile = namedtuple("Tile", ["x", "y"]) def solve(input: str) -> int: red_tiles_ = tuple(red_tiles(input)) edges = tuple(pairwise(red_tiles_)) + ((red_tiles_[-1], red_tiles_[0]),) largest_rectangles = sorted(combinations(red_tiles_, r=2), key=area, reverse=True) for corners in largest_rectangles: c0, c1 = corners for e0, e1 in edges: if e0.x == e1.x: if min(c0.x, c1.x) < e0.x < max(c0.x, c1.x): if not ( (max(e0.y, e1.y) <= min(c0.y, c1.y)) or (min(e0.y, e1.y) >= max(c0.y, c1.y)) ): break else: if min(c0.y, c1.y) < e0.y < max(c0.y, c1.y): if not ( (max(e0.x, e1.x) <= min(c0.x, c1.x)) or (min(e0.x, e1.x) >= max(c0.x, c1.x)) ): break else: return area(corners) def red_tiles(input: str) -> Iterator[Tile]: for line in input.split(): yield Tile(*map(int, line.split(","))) def area(a_b: tuple[Tile, Tile]) -> int: a, b = a_b return ( (abs(a.x - b.x) + 1) * (abs(a.y - b.y) + 1) ) -
Comment on Day 8: Playground in ~comp.advent_of_code
mawelborn Link ParentTIL about disjoint set data structures and quick select. Definitely going to check those out later. Very nice solution!TIL about disjoint set data structures and quick select. Definitely going to check those out later. Very nice solution!
-
Comment on Day 8: Playground in ~comp.advent_of_code
mawelborn (edited )LinkNice little increase in difficulty! I started with each junction box position in its own circuit frozenset, then iteratively merged the sets in the order of shortest position combinations. I'm...Nice little increase in difficulty! I started with each junction box
positionin its own circuitfrozenset, then iteratively merged the sets in the order of shortest position combinations. I'm sure there's some optimization left on the table, but a runtime of <5s using only built-in Python types is good enough IMO.Part 1
JunctionBox = namedtuple("JunctionBox", ["x", "y", "z"]) Circuit: TypeAlias = frozenset[JunctionBox] def solve(input: str) -> int: circuits = connected_circuits(input, connection_count=1000) return prod(sorted(map(len, circuits), reverse=True)[:3]) def connected_circuits(input: str, connection_count: int) -> Iterator[Circuit]: circuits = {jb: Circuit([jb]) for jb in junction_boxes(input)} shortest_combinations = sorted(combinations(circuits.keys(), r=2), key=distance) for a, b in shortest_combinations[:connection_count]: for c in (connected_circuit := circuits[a] | circuits[b]): circuits[c] = connected_circuit yield from set(circuits.values()) def junction_boxes(input: str) -> Iterator[JunctionBox]: for line in input.split(): yield JunctionBox(*map(int, line.split(","))) def distance(a_b: tuple[JunctionBox, JunctionBox]) -> float: a, b = a_b return hypot(a.x - b.x, a.y - b.y, a.z - b.z)Part 2
def solve(input: str) -> int: a, b = last_connection(input) return a.x * b.x def last_connection(input: str) -> tuple[JunctionBox, JunctionBox]: circuits = {jb: Circuit([jb]) for jb in junction_boxes(input)} shortest_combinations = sorted(combinations(circuits.keys(), r=2), key=distance) for a, b in shortest_combinations: if a in circuits[b]: continue for c in (connected_circuit := circuits[a] | circuits[b]): circuits[c] = connected_circuit last_connection_ = a, b return last_connection_ def junction_boxes(input: str) -> Iterator[JunctionBox]: for line in input.split(): yield JunctionBox(*map(int, line.split(","))) def distance(a_b: tuple[JunctionBox, JunctionBox]) -> float: a, b = a_b return hypot(a.x - b.x, a.y - b.y, a.z - b.z) -
Comment on Day 7: Laboratories in ~comp.advent_of_code
mawelborn Link ParentSame! I really shot myself in the foot by thinking it couldn't be done in a single pass when I started, only to realize while writing a debug visualization, that the visualization was a single...I enjoy when it's feasible to do both parts in a single pass over the input!
Same! I really shot myself in the foot by thinking it couldn't be done in a single pass when I started, only to realize while writing a debug visualization, that the visualization was a single pass solution.
-
Comment on Day 7: Laboratories in ~comp.advent_of_code
mawelborn LinkWow I burned about 2 hours way overengineering a solution that made Part 02 impossible to solve. Only to realize while writing a debug visualization that both are actually incredibly simple. And...Wow I burned about 2 hours way overengineering a solution that made Part 02 impossible to solve. Only to realize while writing a debug visualization that both are actually incredibly simple. And then did both parts in 5 minutes with a dozen lines each.
Don't assume a problem's hard folks! You might waste a lot of time writing a hard solution for something that's actually very simple. (Still have to relearn that lesson the hard way sometimes, even after a decade+ experience.)
Part 1
def solve(input: str) -> int: start, *rows = input.split() beams = [(cell == "S") for cell in start] splits = 0 for row in rows: for index, cell in enumerate(row): if beams[index] and cell == "^": beams[index - 1] = True beams[index + 1] = True beams[index] = False splits += 1 return splitsPart 1
def solve(input: str) -> int: start, *rows = input.split() timelines = [int(cell == "S") for cell in start] for row in rows: for index, cell in enumerate(row): if cell == "^": timelines[index - 1] += timelines[index] timelines[index + 1] += timelines[index] timelines[index] = 0 return sum(timelines) -
Comment on Day 6: Trash Compactor in ~comp.advent_of_code
mawelborn Link"It's no use, Mr. James--it's generators all the way down." Much easier today than yesterday, I think. Though the values not being left- or right-aligned in the columns was a wrinkle for Part 02...."It's no use, Mr. James--it's generators all the way down."
Much easier today than yesterday, I think. Though the values not being left- or right-aligned in the columns was a wrinkle for Part 02. As others have said, the actual problem is solved quickly and in only a few lines. The rest is parsing an input format that's more annoying than interesting.
Part 1
def solve(input: str) -> int: return sum(calculations(input)) def calculations(input: str) -> Iterator[int]: operators = {"+": add, "*": mul} for operator, operands in operators_and_operands(input): yield reduce(operators[operator], operands) def operators_and_operands(input: str) -> Iterator[tuple[str, Iterable[int]]]: for column in columns_of_rows(input): *operands, operator = column yield operator, map(int, operands) def columns_of_rows(input: str) -> Iterator[Iterable[str]]: rows = input.strip().split("\n") rows_of_columns = map(str.split, rows) yield from zip(*rows_of_columns)Part 2
def solve(input: str) -> int: return sum(calculations(input)) def calculations(input: str) -> Iterator[int]: operators = {"+": add, "*": mul} for operator, operands in operators_and_operands(input): yield reduce(operators[operator], map(int, operands)) def operators_and_operands(input: str) -> Iterator[tuple[str, Iterable[str]]]: *operand_rows, operator_row = input.strip().split("\n") operand_cols = cephalpod_notation(operand_rows) return zip(operator_row.split(), operand_cols) def cephalpod_notation(operand_rows: Iterable[str]) -> Iterator[Iterable[str]]: operands = map("".join, zip_longest(*operand_rows, fillvalue="")) operands = map(str.strip, operands) yield from split_at(operands, lambda operand: operand == "") -
Comment on Day 5: Cafeteria in ~comp.advent_of_code
mawelborn Link ParentI had almost the exact same experience! My first approach was to create a set of all fresh inventory IDs, which promptly consumed all RAM and froze XFCE. I had to switch to a TTY and kill it in...I had almost the exact same experience! My first approach was to create a
setof all fresh inventory IDs, which promptly consumed all RAM and froze XFCE. I had to switch to a TTY and kill it in htop before it took out my swap too. Then struggled with so many off-by-one errors I wrote a customRangetype to make it easier to get right. -
Comment on Day 5: Cafeteria in ~comp.advent_of_code
mawelborn Link ParentI think it probably is. Making the null range have a length of zero lets me eliminate one of the conditionals, since yielding it won't affect the sum. But I think sorting + overlap check is pretty...I think it probably is. Making the null range have a length of zero lets me eliminate one of the conditionals, since yielding it won't affect the sum. But I think sorting + overlap check is pretty much required.
Definitely no performance issues though! Both parts run in ~0.2s total.
-
Comment on Day 5: Cafeteria in ~comp.advent_of_code
mawelborn LinkOoh first day where the simplest naive solution ran out of memory ^.^ For Part 01, doing a linear search of the ranges worked without issue and is still very straightforward. Part 02 gave me a...Ooh first day where the simplest naive solution ran out of memory ^.^
For Part 01, doing a linear search of the ranges worked without issue and is still very straightforward.
Part 02 gave me a bear of a time with the range overlap checks and off-by-one errors. I eventually created a custom type for the ranges that factors out the calculations, making it easier to get right. Once I had that, sorting, merging, and summing the ranges was easy.
I'm not super pleased with my range merging generator. It's clean enough, but I feel like there should be a more concise way to say "take each range and merge it with the previous if they overlap" that doesn't require nested conditionals. Let me know if you've got an
itertools-based approach or something that you think is better!Part 1
def solve(input: str) -> int: fresh_slices = list(fresh_ingredient_slices(input)) available_ids = set(available_ingredient_ids(input)) return len([ available_id for available_id in available_ids if any( slice.start <= available_id <= slice.stop for slice in fresh_slices ) ]) def fresh_ingredient_slices(input: str) -> Iterator[slice]: id_ranges = input.split("\n\n")[0] for id_range in id_ranges.split(): yield slice(*map(int, id_range.split("-"))) def available_ingredient_ids(input: str) -> Iterator[int]: ids = input.split("\n\n")[1] yield from map(int, ids.split())Part 2
@dataclass(frozen=True, order=True) class Range: start: int _stop: int @property def stop(self) -> int: return self._stop + 1 @staticmethod def from_str(ids: str) -> "Range": return Range(*map(int, ids.split("-"))) def __bool__(self) -> bool: return self != NULL_RANGE def __len__(self) -> int: return self.stop - self.start def __or__(self, other: "Range") -> "Range": if self.stop < other.start or other.stop < self.start: return NULL_RANGE return Range( min(self.start, other.start), max(self._stop, other._stop), ) NULL_RANGE: Final = Range(-1, -1) def solve(input: str) -> int: return sum(map(len, fresh_ingredient_ranges(input))) def fresh_ingredient_ranges(input: str) -> Iterator[Range]: merged_range = NULL_RANGE for range in sorted(map(Range.from_str, input.split())): if merged_range | range: merged_range |= range else: if merged_range: yield merged_range merged_range = range yield merged_range -
Comment on Day 4: Printing Department in ~comp.advent_of_code
mawelborn LinkThis was a fun one! It strikes that perfect balance of hard enough to make you think, but simple enough to have a pleasing solution after ~30 minutes of work. After writing some utility generators...This was a fun one! It strikes that perfect balance of hard enough to make you think, but simple enough to have a pleasing solution after ~30 minutes of work.
After writing some utility generators to yield positions with paper rolls and positions adjacent to them, it was an easy solve with Python sets and Counters. I didn't want to deal with conditional logic for what's "inside" the bounds of the grid; so I forewent a list in favor of a sparse set of roll positions and heatmap of adjacent roll counts.
There's some performance left on the table for Part 02 with the way I check all remaining rolls to calculate the next batch of rolls to remove after removing the previous batch. Doing them one at a time and maintaining a stack of rolls would be more efficient. I could check only the remaining roll positions when updating the adjacent counts and push them onto the stack when they fall below 4. But this way made for a cleaner, simpler solution that runs in 0.5s on my old Thinkpad.
Part 1
Position: TypeAlias = tuple[int, int] def solve(input: str) -> int: roll_positions = set(positions_with_rolls(input)) adjacent_roll_count = Counter(adjacent_positions(roll_positions)) return len([ position for position in roll_positions if adjacent_roll_count[position] < 4 ]) def positions_with_rolls(input: str) -> Iterator[Position]: for row, rolls in enumerate(input.split()): for column, roll in enumerate(rolls): if roll == "@": yield row, column def adjacent_positions(positions: Iterable[Position]) -> Iterator[Position]: for row, column in positions: yield from ( (row - 1, column - 1), (row - 1, column), (row - 1, column + 1), (row, column - 1), # (row, column), (row, column + 1), (row + 1, column - 1), (row + 1, column), (row + 1, column + 1), )Part 2
Position: TypeAlias = tuple[int, int] def solve(input: str) -> int: roll_positions = set(positions_with_rolls(input)) adjacent_roll_count = Counter(adjacent_positions(roll_positions)) removed_roll_count = 0 while positions_to_remove := set( position for position in roll_positions if adjacent_roll_count[position] < 4 ): roll_positions.difference_update(positions_to_remove) adjacent_roll_count.subtract(adjacent_positions(positions_to_remove)) removed_roll_count += len(positions_to_remove) return removed_roll_count def positions_with_rolls(input: str) -> Iterator[Position]: for row, rolls in enumerate(input.split()): for column, roll in enumerate(rolls): if roll == "@": yield row, column def adjacent_positions(positions: Iterable[Position]) -> Iterator[Position]: for row, column in positions: yield from ( (row - 1, column - 1), (row - 1, column), (row - 1, column + 1), (row, column - 1), # (row, column), (row, column + 1), (row + 1, column - 1), (row + 1, column), (row + 1, column + 1), ) -
Comment on Day 3: Lobby in ~comp.advent_of_code
mawelborn LinkWhat a great puzzle for Day 03! It makes for such a satisfying solution. The key insight for me from Part 01 was that the first digit would never be the end digit, and the second digit would...What a great puzzle for Day 03! It makes for such a satisfying solution.
The key insight for me from Part 01 was that the first digit would never be the end digit, and the second digit would always be to the right of the first digit. So the first digit is the
max(bank[start:end-1])and the second digit is themax(bank[first_index+1:end]).That generalized pretty naturally to any number of digits in Part 02 with this solution:
Part N
def solve(input: str) -> int: return sum(max_joltages(input, batteries=12)) def max_joltages(input: str, batteries: int) -> Iterator[int]: for bank in input.split(): yield int("".join(max_batteries(bank, batteries))) def max_batteries(bank: str, batteries: int) -> Iterator[str]: start_index = 0 end_index = len(bank) - batteries for _ in range(batteries): end_index += 1 digit = max(bank[start_index:end_index]) start_index = bank.index(digit, start_index) + 1 yield digit -
Comment on Day 2: Gift Shop in ~comp.advent_of_code
mawelborn (edited )LinkMore Python generator madness on Day 02! Super interesting to see how everyone approached the "has repetition" check. For my part, I used an all() substring comparison approach for any() valid...More Python generator madness on Day 02! Super interesting to see how everyone approached the "has repetition" check. For my part, I used an
all()substring comparison approach forany()valid substring length.Part 1
def solve(input: str) -> int: return sum(filter(twiced, product_ids(input))) def twiced(product_id: int) -> bool: product_id_str = str(product_id) product_id_len = len(product_id_str) return ( product_id_len % 2 == 0 and product_id_str[: product_id_len // 2] == product_id_str[product_id_len // 2 :] ) def product_ids(input: str) -> Iterator[int]: for start_end in input.split(","): start, end = start_end.split("-") for product_id in range(int(start), int(end) + 1, 1): yield product_idPart 2
def solve(input: str) -> int: return sum(filter(repetition, product_ids(input))) def repetition(product_id: int) -> bool: product_id_str = str(product_id) product_id_len = len(product_id_str) return any( repetition_of(repetition_len, product_id_str, product_id_len) for repetition_len in repetition_lens(product_id_len) ) def repetition_of(rep_len: int, product_id_str: str, product_id_len: int) -> bool: return all( product_id_str[:rep_len] == product_id_str[rep_len * rep_mult : rep_len * (rep_mult + 1)] for rep_mult in range(1, product_id_len // rep_len, 1) ) def repetition_lens(product_id_len: int) -> Iterator[int]: for repetition_len in range(product_id_len // 2): repetition_len += 1 if product_id_len % repetition_len == 0: yield repetition_len def product_ids(input: str) -> Iterator[int]: for start_end in input.split(","): start, end = start_end.split("-") for product_id in range(int(start), int(end) + 1, 1): yield product_id -
Comment on Day 1: Secret Entrance in ~comp.advent_of_code
mawelborn LinkKeeping it simple with Python this year, and focusing on writing clean solutions over anything else. (Until algorithmic complexity and optimization becomes a necessary evil anyway.) My love of...Keeping it simple with Python this year, and focusing on writing clean solutions over anything else. (Until algorithmic complexity and optimization becomes a necessary evil anyway.)
My love of generators served me well for Day 01. Just had to set up a sequence of position changes and count the zeros. Part 02 actually worked out to be cleaner in that regard I think.
Part 1
from collections import Counter from collections.abc import Iterator def solve(input: str) -> int: counter = Counter(positions(input)) return counter[0] def positions(input: str) -> Iterator[int]: position = 50 for line in input.split(): direction = line[0] clicks = int(line[1:]) if direction == "R": position += clicks else: position -= clicks position %= 100 yield positionPart 2
from collections import Counter from collections.abc import Iterator from operator import add, sub def solve(input: str) -> int: counter = Counter(positions(input)) return counter[0] def positions(input: str) -> Iterator[int]: position = 50 for line in input.split(): direction = line[0] clicks = int(line[1:]) op = add if direction == "R" else sub for _ in range(clicks): position = op(position, 1) % 100 yield position -
Comment on Advent of Code starts tomorrow/tonight! Are you participating? Do you have any specific plans for this year? in ~comp.advent_of_code
mawelborn LinkI did it in '21 and '22, but wasn't able to finish either year. The highest I got was day 16. The problems eventually outgrew my knowledge of algorithms, and it's just difficult to keep it up...I did it in '21 and '22, but wasn't able to finish either year. The highest I got was day 16. The problems eventually outgrew my knowledge of algorithms, and it's just difficult to keep it up every day for 25 days as the holidays roll through.
It being 12 days is just what I need to feel like I can jump in this year. ~2 weeks feels a lot more manageable, and I'm looking forward to seeing how that affects the difficulty this time around!
-
Comment on Is this a game? | Blank Quiz, made in Google Forms in ~games
mawelborn LinkThis takes the thought I had for the original survey, "it should ask if filling in this form is a game," and executes it perfectly! Absolute gold.This takes the thought I had for the original survey, "it should ask if filling in this form is a game," and executes it perfectly!
Is Blank Form a game?
This question isn't accepting answers at this time.
Absolute gold.
-
Comment on What makes a game, a game? in ~games
mawelborn LinkI consider it a missed opportunity that the survey didn't ask if answering the survey itself was a game :P Filling it out actually surprised me by how many things are "game" adjacent that I...I consider it a missed opportunity that the survey didn't ask if answering the survey itself was a game :P
Filling it out actually surprised me by how many things are "game" adjacent that I actually consider to be "competitions." And I'm not sure I can articulate why. It seems to involve competing players or teams interacting with each other.
Tennis - individual - "game"
Soccer - team - "game"
Swimming relay - team - "competition"
Pole vault - individual - "competition"As with many things relating to language, especially English, I'm sure there are exceptions that I haven't thought of yet. I imagine my definition of "game" and "competition" have more to do with how I heard them used growing up than any intentional rules or qualifications. Though I may be able to come up with some that often apply, I doubt they're consistent.
It's like "pornography" in that way. I can't define what a "game" is, but I know it when I'm playing one.
-
Comment on The vast majority ~90% of us only consume, never post and never comment. So come on in, leave a tildes-worthy comment, and join the 10% my dear lurker in ~talk
mawelborn Link ParentThat's an excellent point! Regarding comments, I can usually explain my lurking with "others are more eloquent, informed, or just earlier to say the thing I was going to say." But I don't have a...That's an excellent point!
Regarding comments, I can usually explain my lurking with "others are more eloquent, informed, or just earlier to say the thing I was going to say." But I don't have a good reason for not posting links to things I find interesting.
I'm going to make an effort to do that!
-
Comment on The America Party in ~society
mawelborn (edited )Link ParentI think it speaks volumes when cryptocurrency scams are so endemic to your desired demographic that you have to put a disclaimer at the top saying you haven't issued one. (Yet anyway. I'm reading...I think it speaks volumes when cryptocurrency scams are so endemic to your desired demographic that you have to put a disclaimer at the top saying you haven't issued one. (Yet anyway. I'm reading that last sentence as there will be a coin announced for this.)
Well I made it to Day 10 Part 02. I believe this is where I admit defeat.
Part 01 was straightforward enough. I parsed the lights as a bitmap and the buttons as bitmasks used to toggle the lights by XORing them together. A breadth-first search of the permutations finds a solution in 160ms without any optimization.
Part 02 not so much. I recently read a blog post--SIMD in Pure Python--about using the SIMD built into Python's
inthandling. Effectively packing all of the joltage counters into a single integer to do all of the additions simultaneously. It's a neat idea and works well for scaling horizontally across the number of joltages. But does nothing for the size, which appears to go up to 255 in my input. There's not enough room in the universe, let alone my aged ThinkPad, to handle all of the permutations of that many button presses.I've done some optimization--like pruning branches that are overjolted using a quick bitmask. But I think this is a dead end, and I'm out of ideas. Short of some very lucky stochastic methods, this one shall remain unsolved. (Without cheating anyway.)
Part 1
Part 2 (Given a Sufficiently-large Computer/Universe)