Advent of Code Day 9¶

def area(pair):
    p1, p2 = pair
    if p1[0] == p2[0]:
        #Case 1 same row
        return abs(p1[0]-p2[0])+1
    elif p1[1] == p2[1]:
        #Case 2 same column:
        return abs(p1[1]-p2[1])+1
    else:
        #Case 3 NW SE
        #Case 4 NE SW
        return (abs(p1[1]-p2[1])+1)*(abs(p1[0]-p2[0])+1)
print(f"The answer for example in part one is {max([ area(pr) for pr in list(
itertools.combinations(small_points, 2))])}")
print(f"The answer for part one is {max([ area(pr) for pr in list(itertools.combinations(points, 2))])}")

def compressGrid(points: list[(int,int)]) -> list[list[int]]:
    xs = sorted({ x for x,_ in points })
    ys = sorted({ y for _,y in points })
    grid = [[0]*(len(xs) * 2 - 1) for _ in range(len(ys)*2-1)]
    for (x1,y1), (x2,y2) in zip(points, points[1:]+points[:1]):
        cx1,cx2  = sorted([xs.index(x1) * 2, xs.index(x2) * 2])
        cy1,cy2  = sorted([ys.index(y1) * 2, ys.index(y2) * 2])
        for cx in range(cx1,cx2+1):
            for cy in range(cy1,cy2+1):
                grid[cy][cx]=1
    return grid

grid = compressGrid(points)
small_grid = compressGrid(small_points)
            
for row in small_grid:
    print("".join([str(n) for n in row]))

def flood(grid: list[list[int]])-> list[list[int]]:
    outside={(-1,-1)}

    q = deque(outside)

    while q :
        tx, ty = q.popleft()
        for nx,ny in [(tx-1,ty), (tx+1,ty), (tx,ty-1),(tx,ty+1)]:
            if nx < -1 or ny < -1 or nx > len(grid[0]) or ny > len(grid): continue
            if 0 <= nx < len(grid[0]) and 0 <= ny < len(grid) and grid[ny][nx]==1: continue
            if (nx,ny) in outside: continue
            outside.add((nx,ny))
            q.append((nx,ny))

    for x in range(len(grid[0])):
        for y in range(len(grid)):
            if (x,y) not in outside:
                grid[y][x]=1
    return grid

grid=flood(grid)
small_grid=flood(small_grid)

for row in small_grid:
    print("".join([str(n) for n in row]))

def buildPSA(grid: list[list[int]]) -> list[list[int]]:

    psa = [[0] * len(row) for row in grid]

    for y in range(len(psa)):
        for x in range(len(psa[0])):
            left = psa[y][x- 1] if x > 0 else 0
            top = psa[y-1][x] if y > 0 else 0
            topleft = psa[y - 1][x - 1] if x > 0 < y else 0
            psa[y][x] = left + top - topleft + grid[y][x]
    
    return psa
    
psa = buildPSA(grid)
s_psa = buildPSA(small_grid)

for row in s_psa:
    print("".join([f"{n:02d}|" for n in row]))

def valid(psa, x1, y1, x2, y2,xs,ys):
    cx1, cx2 = sorted([xs.index(x1)*2, xs.index(x2)*2])
    cy1, cy2 = sorted([ys.index(y1)*2, ys.index(y2)*2])
    left    = psa[cy2][cx1 - 1]   if cx1 > 0 else 0
    top     = psa[cy1-1][cx2]     if cy1 > 0 else 0
    topleft = psa[cy1-1][cx1 - 1] if (cx1 > 0 < cy1) else 0
    count = psa[cy2][cx2] - left - top + topleft  
    return count == (abs(cx2 - cx1) + 1) * (abs(cy2 - cy1) + 1)

sxs = sorted({ x for x,_ in small_points })
sys = sorted({ y for _,y in small_points })
areas = [((x1,y1,x2,y2),(abs(x2 - x1) + 1) * (abs(y2 - y1) + 1)) for i, (x1, y1) in enumerate(small_points) for x2, y2 in small_points[:i]]
valid_areas = [((x1,y1,x2,y2),(abs(x2 - x1) + 1) * (abs(y2 - y1) + 1)) for i, (x1, y1) in enumerate(small_points) for x2, y2 in small_points[:i] if valid(s_psa,x1,y1,x2,y2,sxs,sys)]
invalid_areas = [((x1,y1,x2,y2),(abs(x2 - x1) + 1) * (abs(y2 - y1) + 1)) for i, (x1, y1) in enumerate(small_points) for x2, y2 in small_points[:i] if not valid(s_psa,x1,y1,x2,y2,sxs,sys)]
small_ans1 = max((abs(x2 - x1) + 1) * (abs(y2 - y1) + 1) for i, (x1, y1) in enumerate(small_points) for x2, y2 in small_points[:i] if valid(s_psa,x1,y1,x2,y2,sxs,sys))

print(f"The areas are \n{areas}")
print(f"The valid areas are \n{valid_areas}")
print(f"The invalid areas are \n{invalid_areas}")
print(f"The answer for part two example prompt is {small_ans1}")

xs = sorted({ x for x,_ in points })
ys = sorted({ y for _,y in points })
ans1 = max((abs(x2 - x1) + 1) * (abs(y2 - y1) + 1) for i, (x1, y1) in enumerate(points) for x2, y2 in points[:i] if valid(psa,x1, y1, x2, y2,xs,ys))
print(f"The answer for part two is {ans1}")