• 167 Posts
  • 222 Comments
Joined 9 months ago
cake
Cake day: July 28th, 2023

help-circle
rss
  • I’ve used Fastmail with a custom domain for a few years now… (5+?) and have been really happy with it. I wish it was a bit cheaper (or had a better family plan), but it works well with my terminal email client (mutt).

    The web client is pretty quick and I use the calendar there all the time. Fastmail supports all the normal standards such as CalDAV, so you can use it with third party applications.
























  • Language: Python

    Part 1

    Pretty straightforward. Took advantage of itertools.pairwise.

    def predict(history: list[int]) -> int:
        sequences = [history]
        while len(set(sequences[-1])) > 1:
            sequences.append([b - a for a, b in itertools.pairwise(sequences[-1])])
        return sum(sequence[-1] for sequence in sequences)
    
    def main(stream=sys.stdin) -> None:
        histories   = [list(map(int, line.split())) for line in stream]
        predictions = [predict(history) for history in histories]
        print(sum(predictions))
    
    Part 2

    Only thing that changed from the first part was that I used functools.reduce to take the differences of the first elements of the generated sequences (rather than the sum of the last elements for Part 1).

    def predict(history: list[int]) -> int:
        sequences = [history]
        while len(set(sequences[-1])) > 1:
            sequences.append([b - a for a, b in itertools.pairwise(sequences[-1])])
        return functools.reduce(
            lambda a, b: b - a, [sequence[0] for sequence in reversed(sequences)]
        )
    
    def main(stream=sys.stdin) -> None:
        histories   = [list(map(int, line.split())) for line in stream]
        predictions = [predict(history) for history in histories]
        print(sum(predictions))
    

    GitHub Repo


  • Language: Python

    Part 1

    First part was very straight-forward: read the input in and simulate the navigation. Taking advantage of itertools.cycle made cycling through the instructions very easy :]

    Network = dict[str, dict[str, str]]
    
    def read_instructions(stream=sys.stdin) -> Iterator[str]:
        return itertools.cycle(stream.readline().strip())
    
    def read_network(stream=sys.stdin) -> Network:
        network = defaultdict(dict)
    
        for line in map(str.strip, stream):
            if not line:
                continue
    
            source, target_l, target_r = re.findall('[A-Z]{3}', line)
            network[source] = {
                'L': target_l,
                'R': target_r,
            }
    
        return network
    
    def navigate(instructions: Iterator[str], network: Network) -> int:
        count  = 0
        source = 'AAA'
        target = 'ZZZ'
    
        while source != target:
            source = network[source][next(instructions)]
            count += 1
    
        return count
    
    def main(stream=sys.stdin) -> None:
        instructions = read_instructions(stream)
        network      = read_network(stream)
        print(navigate(instructions, network))
    
    Part 2

    The second part was also straight-forward: locate the ghosts, and then navigate from each ghost until you hit an element that ends with a ‘Z’. The trick to avoid brute-forcing is to realize that the ghosts will cycle (ie. repeat the same paths) if they all don’t land on an element that ends with a ‘Z’ at the same time. To solve the problem, you just ened to calculate the steps for each ghost to reach an endpoint and then compute the lowest common multiple of those counts. Fortunately, Python has math.lcm, so not much code was needed!

    def navigate(instructions: Iterator[str], network: Network, element: str) -> int:
        count = 0
    
        while not element.endswith('Z'):
            element = network[element][next(instructions)]
            count += 1
    
        return count
    
    def locate_ghosts(network: Network) -> list[str]:
        return [element for element in network if element.endswith('A')]
    
    def main(stream=sys.stdin) -> None:
        instructions = read_instructions(stream)
        network      = read_network(stream)
        ghosts       = locate_ghosts(network)
        counts       = [navigate(cycle(instructions), network, ghost) for ghost in ghosts]
        print(math.lcm(*counts))
    

    GitHub Repo


  • Language: Python

    This was fun. More enjoyable than I initially thought (though I’ve done card sorting code before).

    Part 1

    This was pretty straightforward: create a histogram of the cards in each hand to determine their type, and if there is a tie-breaker, compare each card pairwise. I use the Counter class from collections to do the counting, and then had a dictionary/table to convert labels to numeric values for comparison. I used a very OOP approach and wrote a magic method for comparing hands and used that with Python’s builtin sort. I even got to use Enum!

    LABELS = {l: v for v, l in enumerate('23456789TJQKA', 2)}
    
    class HandType(IntEnum):
        FIVE_OF_A_KIND  = 6
        FOUR_OF_A_KIND  = 5
        FULL_HOUSE      = 4
        THREE_OF_A_KIND = 3
        TWO_PAIR        = 2
        ONE_PAIR        = 1
        HIGH_CARD       = 0
    
    class Hand:
        def __init__(self, cards=str, bid=str):
            self.cards  = cards
            self.bid    = int(bid)
            counts      = Counter(self.cards)
            self.type   = (
                HandType.FIVE_OF_A_KIND  if len(counts) == 1 else
                HandType.FOUR_OF_A_KIND  if len(counts) == 2 and any(l for l, count in counts.items() if count == 4) else
                HandType.FULL_HOUSE      if len(counts) == 2 and any(l for l, count in counts.items() if count == 3) else
                HandType.THREE_OF_A_KIND if len(counts) == 3 and any(l for l, count in counts.items() if count == 3) else
                HandType.TWO_PAIR        if len(counts) == 3 and any(l for l, count in counts.items() if count == 2) else
                HandType.ONE_PAIR        if len(counts) == 4 and any(l for l, count in counts.items() if count == 2) else
                HandType.HIGH_CARD
            )
    
        def __lt__(self, other):
            if self.type == other.type:
                for s_label, o_label in zip(self.cards, other.cards):
                    if LABELS[s_label] == LABELS[o_label]:
                        continue
                    return LABELS[s_label] < LABELS[o_label]
                return False
            return self.type < other.type
    
        def __repr__(self):
            return f'Hand(cards={self.cards},bid={self.bid},type={self.type})'
    
    def read_hands(stream=sys.stdin) -> list[Hand]:
        return [Hand(*line.split()) for line in stream]
    
    def main(stream=sys.stdin) -> None:
        hands    = sorted(read_hands(stream))
        winnings = sum(rank * hand.bid for rank, hand in enumerate(hands, 1))
        print(winnings)
    
    Part 2

    For the second part, I just had to add some post-processing code to convert the jokers into actual cards. The key insight is to find the highest and most numerous non-Joker card and convert all the Jokers to that card label.

    This had two edge cases that tripped me up:

    1. ‘JJJJJ’: There is no other non-Joker here, so I messed up and ranked this the lowest because I ended up removing all counts.

    2. ‘JJJ12’: This also messed me up b/c the Joker was the most numerous card, and I didn’t handle that properly.

    Once I fixed the post-processing code though, everything else remained the same. Below, I only show the parts that changed from Part A.

    LABELS = {l: v for v, l in enumerate('J23456789TQKA', 1)}
    
    ...
    
    class Hand:
        def __init__(self, cards=str, bid=str):
            self.cards  = cards
            self.bid    = int(bid)
            counts      = Counter(self.cards)
    
            if 'J' in counts and len(counts) > 1:
                max_label = max(set(counts) - {'J'}, key=lambda l: (counts[l], LABELS[l]))
                counts[max_label] += counts['J']
                del counts['J']
    
            self.type   = (...)
    

    GitHub Repo


  • Language: Python

    Part 1

    Not much to say… this was pretty straightforward.

    def race(charge_time: int, total_time: int) -> int:
        return charge_time * (total_time - charge_time)
    
    def main(stream=sys.stdin) -> None:
        times     = [int(t) for t in stream.readline().split(':')[-1].split()]
        distances = [int(d) for d in stream.readline().split(':')[-1].split()]
        product   = 1
    
        for time, distance in zip(times, distances):
            ways     = [c for c in range(1, time + 1) if race(c, time) > distance]
            product *= len(ways)
    
        print(product)
    
    Part 2

    Probably could have done some math, but didn’t need to :]

    def race(charge_time: int, total_time: int):
        return charge_time * (total_time - charge_time)
    
    def main(stream=sys.stdin) -> None:
        time     = int(''.join(stream.readline().split(':')[-1].split()))
        distance = int(''.join(stream.readline().split(':')[-1].split()))
        ways     = [c for c in range(1, time + 1) if race(c, time) > distance]
        print(len(ways))
    

    GitHub Repo


  • Language: Python

    Part 1

    The first part wasn’t too bad… once I realized you should store the ranges and not actually generate all the numbers o_O.

    Seeds = list[int]
    Map   = tuple[int, int, int]
    Maps  = list[Map]
    
    def read_almanac(stream=sys.stdin) -> tuple[Seeds, list[Map]]:
        seeds: Seeds = [int(seed) for seed in stream.readline().split(':')[-1].split()]
        maps:  Maps  = []
    
        for line in map(str.strip, stream):
            if line.endswith('map:'):
                maps.append([])
                continue
                
            try:
                dst, src, length = map(int, line.split())
            except ValueError:
                continue
                
            maps[-1].append((dst, src, length))
    
        return seeds, maps
    
    def locate_seed(seed: int, maps: list[Map]) -> int:
        location = seed
        for amap in maps:
            for dst, src, length in amap:
                if src <= location < src + length:
                    location = dst + (location - src)
                    break
        return location
    
    def main(stream=sys.stdin) -> None:
        seeds, maps = read_almanac(stream)
        locations   = [locate_seed(seed, maps) for seed in seeds]
        print(min(locations))
    
    Part 2

    This part took me forever, mostly to actually run, but also to fix a few off-by-one errors :|

    Fortunately, I was able to re-use most of my code in Part A and just add a new function to search the range of seeds.

    Even with concurrent.futures and a 24-core machine, it still took me about 30 - 45 minutes to complete with Python (that said, there were only 10 seed range s in the input, so I could only use 10 cores, and of those 5 of the ranges appeared to be really large, leading to a long tail effect).

    def locate_seeds(srange: Range, maps: list[Map]={}) -> int:
        seeds   = range(srange[0], srange[0] + srange[1])
        locator = functools.partial(locate_seed, maps=maps)
        return min(map(locator, seeds))
    
    # Main Execution
    
    def main(stream=sys.stdin) -> None:
        seeds, maps = read_almanac(stream)
        locator     = functools.partial(locate_seeds, maps=maps)
    
        with concurrent.futures.ProcessPoolExecutor() as executor:
            locations = executor.map(locator, batched(seeds, 2))
    
        print(min(locations))
    

    GitHub Repo


  • Language: Python

    Part 1

    Sets really came in handy for this challenge, as did recognizing that you can use powers of two to compute the points for each card. I tried using a regular expression to parse each card, but ended up just doing it manually with split :|

    Numbers = set[int]
    Card    = list[Numbers]
    
    def read_cards(stream=sys.stdin) -> Iterator[Card]:
        for line in stream:
            yield [set(map(int, n.split())) for n in line.split(':')[-1].split('|')]
    
    def main(stream=sys.stdin) -> None:
        cards  = [numbers & winning for winning, numbers in read_cards(stream)]
        points = sum(2**(len(card)-1) for card in cards if card)
        print(points)
    
    Part 2

    This took me longer than I wished… I had to think about it carefully before seeing how you can just keep track of the counts of each card, and then when you get to that card, you add to its copies your current count.

    def main(stream=sys.stdin) -> None:
        cards  = [numbers & winning for winning, numbers in read_cards(stream)]
        counts = defaultdict(int)
    
        for index, card in enumerate(cards, 1):
            counts[index] += 1
            for copy in range(index + 1, index + len(card) + 1):
                counts[copy] += counts[index]
    
        print(sum(counts.values()))
    

    GitHub Repo


  • Language: Python

    Classic AoC grid problem… Tedious as usual, but very doable. Took my time and I’m pretty happy with the result. :]

    Part 1

    For the first part, I decided to break the problem into: 1. Reading the schematic, 2. Finding the numbers, 3. Finding the parts. This was useful for Part 2 as I could re-use my read_schematic and find_numbers functions.

    Two things I typically do for grid problems:

    1. Pad the grid so you can avoid annoying boundary checks.
    2. I have a DIRECTIONS list I loop through so I can check easily check the neighbors.
    Schematic  = list[str]
    Number     = tuple[int, int, int]
    
    DIRECTIONS = (
        (-1, -1),
        (-1,  0),
        (-1,  1),
        ( 0, -1),
        ( 0,  1),
        ( 1, -1),
        ( 1,  0),
        ( 1,  1),
    )
    
    def read_schematic(stream=sys.stdin) -> Schematic:
        schematic = [line.strip() for line in stream]
        columns   = len(schematic[0]) + 2
        return [
            '.'*columns,
            *['.' + line + '.' for line in schematic],
            '.'*columns,
        ]
    
    def is_symbol(s: str) -> bool:
        return not (s.isdigit() or s == '.')
    
    def find_numbers(schematic: Schematic) -> Iterator[Number]:
        rows    = len(schematic)
        columns = len(schematic[0])
    
        for r in range(1, rows):
            for number in re.finditer(r'[0-9]+', schematic[r]):
                yield (r, *number.span())
    
    def find_parts(schematic: Schematic, numbers: Iterator[Number]) -> Iterator[int]:
        for r, c_head, c_tail in numbers:
            part = int(schematic[r][c_head:c_tail])
            for c in range(c_head, c_tail):
                neighbors = (schematic[r + dr][c + dc] for dr, dc in DIRECTIONS)
                if any(is_symbol(neighbor) for neighbor in neighbors):
                    yield part
                    break
    
    def main(stream=sys.stdin) -> None:
        schematic = read_schematic(stream)
        numbers   = find_numbers(schematic)
        parts     = find_parts(schematic, numbers)
        print(sum(parts))
    
    Part 2

    For the second part, I just found the stars, and then I found the gears by checking if the stars are next to two numbers (which I had found previously).

    def find_stars(schematic: Schematic) -> Iterator[Star]:
        rows    = len(schematic)
        columns = len(schematic[0])
    
        for r in range(1, rows):
            for c in range(1, columns):
                token = schematic[r][c]
                if token == '*':
                    yield (r, c)
    
    def find_gears(schematic: Schematic, stars: Iterator[Star], numbers: list[Number]) -> Iterator[int]:
        for star_r, star_c in stars:
            gears = [                                                                                                                      
                int(schematic[number_r][number_c_head:number_c_tail])
                for number_r, number_c_head, number_c_tail in numbers
                if any(star_r + dr == number_r and number_c_head <= (star_c + dc) < number_c_tail for dr, dc in DIRECTIONS)
            ]
            if len(gears) == 2:
                yield gears[0] * gears[1]
    
    def main(stream=sys.stdin) -> None:
        schematic = read_schematic(stream)
        numbers   = find_numbers(schematic)
        stars     = find_stars(schematic)
        gears     = find_gears(schematic, stars, list(numbers))
        print(sum(gears))
    

    GitHub Repo


  • This was mostly straightforward… basically just parsing input. Here are my condensed solutions in Python

    Part 1
    Game = dict[str, int]
    
    RED_MAX   = 12
    GREEN_MAX = 13
    BLUE_MAX  = 14
    
    def read_game(stream=sys.stdin) -> Game:
        try:
            game_string, cubes_string = stream.readline().split(':')
        except ValueError:
            return {}
    
        game: Game = defaultdict(int)
        game['id'] = int(game_string.split()[-1])
    
        for cubes in cubes_string.split(';'):
            for cube in cubes.split(','):
                count, color = cube.split()
                game[color] = max(game[color], int(count))
    
        return game
    
    def read_games(stream=sys.stdin) -> Iterator[Game]:
        while game := read_game(stream):
            yield game
    
    def is_valid_game(game: Game) -> bool:
        return all([
            game['red']   <= RED_MAX,
            game['green'] <= GREEN_MAX,
            game['blue']  <= BLUE_MAX,
        ])
    
    def main(stream=sys.stdin) -> None:
        valid_games = filter(is_valid_game, read_games(stream))
        sum_of_ids  = sum(game['id'] for game in valid_games)
        print(sum_of_ids)
    
    Part 2

    For the second part, the main parsing remainded the same. I just had to change what I did with the games I read.

    def power(game: Game) -> int:
        return game['red'] * game['green'] * game['blue']
    
    def main(stream=sys.stdin) -> None:
        sum_of_sets = sum(power(game) for game in read_games(stream))
        print(sum_of_sets)
    

    GitHub Repo