Day 5: Cafeteria

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

  • Chais@sh.itjust.works
    link
    fedilink
    arrow-up
    2
    ·
    6 days ago

    Again part 2 took me way longer than I would’ve liked and also than feels appropriate for the simplicity of the solution I finally came up with.
    Turned out quite fast, thanks to the ranges.

    Python

    from pathlib import Path
    from typing import List
    from itertools import combinations
    
    def parse_input(input: str) -> tuple[set[range], list[int]]:
        parts = input.split("\n\n")
        fresh = set((lambda r: range(int(r[0]), int(r[1]) + 1))(line.split("-")) for line in parts[0].splitlines())
        return (fresh, list(map(int, parts[1].splitlines())))
    
    
    def merge_ranges(a: range, b: range) -> List[range]:
        if a.stop <= b.start or b.stop <= a.start:
            return [a, b]
        return [range(min(a.start, b.start), max(a.stop, b.stop))]
    
    
    def part_one(input: str) -> int:
        fresh, available = parse_input(input)
        return len(list(filter(None, [any(i in r for r in fresh) for i in available])))
    
    
    def part_two(input: str) -> int:
        fresh, _ = parse_input(input)
        while True:
            for a, b in combinations(fresh, 2):
                if len(m := merge_ranges(a, b)) == 1:
                    fresh.remove(a)
                    fresh.remove(b)
                    fresh.add(m[0])
                    break
            else:
                break
        return sum(map(len, fresh))
    
    
    if __name__ == "__main__":
        input = Path("_2025/_5/input").read_text("utf-8")
        print(part_one(input))
        print(part_two(input))
    
    • CameronDev@programming.devOPM
      link
      fedilink
      arrow-up
      1
      ·
      6 days ago

      That is nice and simple, power of python I guess. How quick was the pt2 solve? I could imagine that being pathalogically slow with the wrong ordering of inputs?

      Eg: (99,100),(0,1),…, (95,96), (96,97), (97,98), (98,99)

      • Chais@sh.itjust.works
        link
        fedilink
        arrow-up
        2
        ·
        edit-2
        5 days ago

        I haven’t timed it, but easily below a second.
        Could that be optimised? Most certainly.

        Due to the ranges being in a set, rather than a list, the input order doesn’t matter anyway. And the set really does a lot of heavy lifting for making the code so concise. You’ll need a bunch of boilerplate for list maintenance, especially if you continuously keep it sorted.
        The set also removed 8 duplicates I had in the input.