Day 10: Pipe Maze

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)
  • Code block support is not fully rolled out yet but likely will be in the middle of the event. Try to share solutions as both code blocks and using something such as https://topaz.github.io/paste/ , pastebin, or github (code blocks to future proof it for when 0.19 comes out and since code blocks currently function in some apps and some instances as well if they are running a 0.19 beta)

FAQ


🔒 Thread is locked until there’s at least 100 2 star entries on the global leaderboard

🔓 Unlocked after 40 mins

  • I always felt I was one fix away from the solution, which was both nice and bad.

    Walking the path was fine, and part 2 looked easy until I missed the squeezed pipes. I for some silly reason thought I only had to expand the grid by x2 instead of x3 and had to re-do that. Fill is hyper bad but works for <1 minute.

    Python
    import re
    import math
    import argparse
    import itertools
    from enum import Flag,Enum
    
    class Connection(Flag):
        Empty = 0b0000
        North = 0b0001
        South = 0b0010
        East = 0b01000
        West = 0b10000
    
    def connected_directions(first:Connection,second:Connection) -> bool:
        return bool(((first.value >> 1) &amp; second.value) or
                ((first.value &lt;&lt; 1) &amp; second.value))
    
    def opposite_direction(dir:Connection) -> Connection:
        if dir.value &amp; 0b00011:
            return Connection(dir.value ^ 0b00011)
        if dir.value &amp; 0b11000:
            return Connection(dir.value ^ 0b11000)
        return Connection(0)
    
    class PipeElement:
        def __init__(self,symbol:chr) -> None:
            self.symbol = symbol
            self.connection = Connection.Empty
            if symbol in [*'|LJS']:
                self.connection |= Connection.North
            if symbol in [*'|7FS']:
                self.connection |= Connection.South
            if symbol in [*'-LFS']:
                self.connection |= Connection.East
            if symbol in [*'-J7S']:
                self.connection |= Connection.West
            if self.connection == Connection.Empty:
                self.symbol = '.'
    
        def __repr__(self) -> str:
            return f"Pipe({self.connection})"
        
        def __str__(self) -> str:
            return self.symbol
    
        def connected_to(self,pipe,direction:Connection) -> bool:
            if not (self.connection &amp; direction):
                return False
            
            if self.connection &amp; direction and pipe.connection &amp; opposite_direction(direction):
                return True
            
            return False
            
    class Navigator:
        def __init__(self,list:list,width) -> None:
            self.list = list
            self.width = width
    
        def at(self,position):
            return self.list[position]
        
        def neighbor(self,position,direction:Connection) -> tuple | None:
            match direction:
                case Connection.North:
                    return self.prev_row(position)
                case Connection.South:
                    return self.next_row(position)
                case Connection.East:
                    return self.next(position)
                case Connection.West:
                    return self.prev(position)
            raise Exception(f"Direction not found: {direction}")
    
        def prev_row(self,position) -> tuple | None:
            p = position - self.width
            if p &lt; 0:
                return None
            return (p,self.list[p])
    
        def next_row(self,position) -> tuple | None:
            p = position + self.width
            if p >= len(self.list):
                return None
            return (p,self.list[p])
        
        def prev(self,position) -> tuple | None:
            p = position - 1
            if p &lt; 0:
                return None
            return (p,self.list[p])
    
        def next(self,position) -> tuple | None:
            p = position + 1
            if p >= len(self.list):
                return None
            return (p,self.list[p])
        
        def all_neighbors(self,position) -> list:
            l = list()
            for f in [self.next, self.prev, self.next_row,self.prev_row]:
                t = f(position)
                if t != None:
                    l.append(t)
            return l
        
        def find_connected(self,position,exclude=Connection.Empty) -> tuple | None:
            for dir in [Connection.East,Connection.West,Connection.North,Connection.South]:
                if dir == exclude:
                    continue
    
                n = self.neighbor(position,dir)
                if n == None:
                    continue
    
                if self.at(position).connected_to(n[1],dir):
                    return (*n,dir)
            return None
    
    class TileType(Enum):
        Inside = 1
        Outside = 0
        Pipe = 2
        PlaceHolder = 3
    
    def pipe_to_tile_expand(pipe:PipeElement) -> list:
        s = str(pipe)
        expansions = {
            '.': '.PP'+ 'PPP' + 'PPP',
            '-': 'PPP'+ '---' + 'PPP',
            '|': 'P|P'+ 'P|P' + 'P|P',
            'F': 'PPP'+ 'PF-' + 'P|P',
            '7': 'PPP'+ '-7P' + 'P|P',
            'J': 'P|P'+ '-JP' + 'PPP',
            'L': 'P|P'+ 'PL-' + 'PPP',
            'S': 'P|P'+ '-S-' + 'P|P'
            }
        l = expansions[s]
        return [pipe_to_tile(x) for x in [*l]]
    def pipe_to_tile(pipe:str) -> TileType:
        expansions = {
            '.': TileType.Inside,
            '-': TileType.Pipe,
            '|': TileType.Pipe,
            'F': TileType.Pipe,
            '7': TileType.Pipe,
            'J': TileType.Pipe,
            'L': TileType.Pipe,
            'S': TileType.Pipe,
            'P': TileType.PlaceHolder
            }
        return expansions[pipe]
    
    def chunks(lst, n):
        """Yield successive n-sized chunks from lst."""
        for i in range(0, len(lst), n):
            yield lst[i:i + n]
    
    def print_tiles(tile_list:list,width:int):
        for c in chunks(tile_list,width):
            print("".join([str(t.value) for t in c]))
    
    def print_pipes(tile_list:list,width:int):
        for c in chunks(tile_list,width):
            print("".join([str(t) for t in c]))
    
    def main(line_list:list,part:int):
        width = None
    
        pipe_list = list()
        tile_list = list()
        start_o = None
        for line in line_list:
            line = line + ' ' # stops east/west joining over new lines
            if width == None:
                width = len(line)
            for c in [*line]:
                o = PipeElement(c)
                pipe_list.append(o)
                tile_list.append(TileType.Inside)
                if c == 'S':
                    start_o = o
        #print(pipe_list)
        start_pos = pipe_list.index(start_o)
        start_co = (start_pos // width, start_pos % width)
        print(f"starting index: {start_pos}: {start_co}")
    
        nav = Navigator(pipe_list,width)
    
        cur_pos = None
        last_dir = Connection.Empty
        steps = 0
        while cur_pos != start_pos:
            if cur_pos == None:
                cur_pos = start_pos
            
            pipe = nav.find_connected(cur_pos,exclude=opposite_direction(last_dir))
            if pipe == None:
                raise Exception(f"end of pipe at: {cur_pos}, {nav.at(cur_pos)}")
            cur_pos = pipe[0]
            last_dir = pipe[2]
            steps += 1
            #print(f"{cur_pos}->",end="")
    
            tile_list[cur_pos] = TileType.Pipe
        
        print(f"end: {cur_pos}, steps: {steps}")
    
        clean_pipe = list()
        for i in range(0,len(pipe_list)):
            if tile_list[i] == TileType.Pipe:
                clean_pipe.append(pipe_list[i])
            else:
                clean_pipe.append(PipeElement('.'))
    
        print_pipes(clean_pipe,width)
        print(f"part 1: {steps/2}")
    
        # part 2 outputs
        #print("start tile:")
        #print_tiles(tile_list,width)
    
        # add outsides to edge of map
        tile_list2 = list()
        #first row
        expanded_width = (width*3)+2
        for i in range(0,expanded_width):
            tile_list2.append(TileType.Outside)
        for row in chunks(clean_pipe, width):
            ## we need to expand this to 2x size tiles
            t_rows = [ list() for x in range(0,3)]
            [ x.append(TileType.Outside) for x in t_rows]
            for r in row:
                parts = pipe_to_tile_expand(r)
                [ t_rows[x].extend( parts[x*3:(x*3)+3] ) for x in range(0,3)]
            [ x.append(TileType.Outside) for x in t_rows]
            [ tile_list2.extend(x) for x in t_rows]
        for i in range(0,expanded_width):
            tile_list2.append(TileType.Outside)
    
        #print("with o tile:")
        #print_tiles(tile_list2,width+2)
    
        tilenav = Navigator(tile_list2,expanded_width)
        changes = True
        while changes == True:
            changes = False
            count_in = 0
            
            for i in range(0,len(tile_list2)):
                t = tilenav.at(i)
                if t == TileType.Inside or t == TileType.PlaceHolder:
                    n = tilenav.all_neighbors(i)
                    if any([x[1] == TileType.Outside for x in n]):
                        tilenav.list[i] = TileType.Outside
                        changes = True
                        continue
                    if t == TileType.Inside:
                        count_in += 1
    
        print("with outside tile:")
        print_tiles(tile_list2,expanded_width)
        print(count_in)
    
    if __name__ == "__main__":
        parser = argparse.ArgumentParser(description="template for aoc solver")
        parser.add_argument("-input",type=str)
        parser.add_argument("-part",type=int)
        args = parser.parse_args()
        filename = args.input
        if filename == None:
            parser.print_help()
            exit(1)
        part = args.part
        file = open(filename,'r')
        main([line.rstrip('\n') for line in file.readlines()],part)
        file.close()