Note: 10

Start time: 12:28

Code: 9 ()

from fastcore.utils import *

Code: 60 ()

from aocd import get_data
inp = get_data(year=2025, day=9)
len(inp), len(inp.splitlines()), len(inp.splitlines()[0]), inp[:100]

Output: 115

(5767,
 496,
 11,
 '97998,50303\n97998,51528\n98246,51528\n98246,52758\n98334,52758\n98334,53970\n98115,53970\n98115,55177\n9789')

Code: 54 ()

samp = """7,1
11,1
11,7
9,7
9,5
2,5
2,3
7,3"""

Code: 6 ()

import numpy as np

Note: 45

We want to find the largest rectangle with opposing corners being red tiles - coordinates of tiles given as input. There are only <500 locs.

Note: 91

We could make a grid as an array, and then delete empty rows and cols from the outside until we get our rect. Or just look for min and max for part 1? Part 2 will likely benefit from some parsing, e.g. into at least the format they show for rts.

Code: 34 ()

lines = samp.splitlines()
coords = [L(l.split(",")).map(int) for l in lines]
coords

Output: 112

[(#2) [7,1],
 (#2) [11,1],
 (#2) [11,7],
 (#2) [9,7],
 (#2) [9,5],
 (#2) [2,5],
 (#2) [2,3],
 (#2) [7,3]]

Code: 22 ()

xs, ys = map(np.array, zip(*coords))
xs, ys

Output: 99

(array([ 7, 11, 11,  9,  9,  2,  2,  7]), array([1, 1, 7, 7, 5, 5, 3, 3]))

Code: 87 ()

g = np.array([["."]*(max(xs)+1) for _ in range(max(ys)+1)])
for x, y in zip(xs, ys):
    g[y][x] = "#"
print("\n".join(["".join(l) for l in g]))

Output: 52

............
.......#...#
............
..#....#....
............
..#......#..
............
.........#.#

Note: 18

OK enough lollygagging, let's submit part 1

Note: 30

Using two red tiles as opposite corners, what is the largest area of any rectangle you can make?

Note: 21

Oh I can't quite take just the min and max coords independently, duh

Note: 45

Let's go with eliminating empty rows and cols. Or do we find the convex hull and guarentee the biggest rect starts from a point on that?

Note: 19

Yeah guarenteed one of two corners will be on convex hull

Note: 28

In fact both will, pretty sure! And not just the convex hull but the bounding rect?

Code: 108 ()

minx, miny, maxx, maxy = min(xs), min(ys), max(xs), max(ys)
points_to_check = L(coords).filter(lambda c: c[0] == minx or c[0] == maxx or c[1] == miny or c[1] == maxy)
points_to_check

Output: 66

(#6) [[7, 1],[11, 1],[11, 7],[9, 7],[2, 5],[2, 3]]

Code: 145 ()

# Now we iterate over these
max_a = 0
for p in points_to_check:
    for p2 in points_to_check:
        if p2 == p: continue
        a = abs(1+p[0] - p2[0]) * abs(1+p[1] - p2[1]) # 1+ because inclusive
        # print(a, p, p2)
        max_a = max(max_a, a)
max_a

Output: 16

Prompt: 28

Using the code above, make a solve function that takes samp and outputs this final area

Assistant: 297

Copied!

def solve(s):
    lines = s.splitlines()
    coords = [L(l.split(",")).map(int) for l in lines]
    xs, ys = map(np.array, zip(*coords))
    minx, miny, maxx, maxy = min(xs), min(ys), max(xs), max(ys)
    points_to_check = L(coords).filter(lambda c: c[0] == minx or c[0] == maxx or c[1] == miny or c[1] == maxy)
    max_a = 0
    for p in points_to_check:
        for p2 in points_to_check:
            if p2 == p: continue
            a = abs(1+p[0] - p2[0]) * abs(1+p[1] - p2[1])
            max_a = max(max_a, a)
    return max_a

solve(samp)

Code: 291 ()

def solve(s):
    lines = s.splitlines()
    coords = [L(l.split(",")).map(int) for l in lines]
    xs, ys = map(np.array, zip(*coords))
    minx, miny, maxx, maxy = min(xs), min(ys), max(xs), max(ys)
    points_to_check = L(coords).filter(lambda c: c[0] == minx or c[0] == maxx or c[1] == miny or c[1] == maxy)
    max_a = 0
    for p in points_to_check:
        for p2 in points_to_check:
            if p2 == p: continue
            a = abs(1+p[0] - p2[0]) * abs(1+p[1] - p2[1])
            max_a = max(max_a, a)
    return max_a

solve(samp)

Output: 16

Code: 4 ()

solve(inp)

Output: 21

2693548496

Note: 36

Apparently that's too low, am I wrong about the convex hull? I can just brute-force it for this few points.

Code: 292 ()

def solve(s):
    lines = s.splitlines()
    coords = [L(l.split(",")).map(int) for l in lines]
    xs, ys = map(np.array, zip(*coords))
    minx, miny, maxx, maxy = min(xs), min(ys), max(xs), max(ys)
    points_to_check = L(coords)#.filter(lambda c: c[0] == minx or c[0] == maxx or c[1] == miny or c[1] == maxy)
    max_a = 0
    for p in points_to_check:
        for p2 in points_to_check:
            if p2 == p: continue
            a = abs(1+p[0] - p2[0]) * abs(1+p[1] - p2[1])
            max_a = max(max_a, a)
    return max_a

solve(samp)

Output: 16

Code: 4 ()

solve(inp)

Output: 21

4755429952

Note: 10

Huh, that was right.

Note: 6

Part 2

Note: 400

The Elves just remembered: they can only switch out tiles that are red or green. So, your rectangle can only include red or green tiles.

In your list, every red tile is connected to the red tile before and after it by a straight line of green tiles. The list wraps, so the first red tile is also connected to the last red tile. Tiles that are adjacent in your list will always be on either the same row or the same column.

Using the same example as before, the tiles marked X would be green:

Copied!

..............
.......#XXX#..
.......X...X..
..#XXXX#...X..
..X........X..
..#XXXXXX#.X..
.........X.X..
.........#X#..
..............

In addition, all of the tiles inside this loop of red and green tiles are also green. So, in this example, these are the green tiles:

Copied!

..............
.......#XXX#..
.......XXXXX..
..#XXXX#XXXX..
..XXXXXXXXXX..
..#XXXXXX#XX..
.........XXX..
.........#X#..
..............

The remaining tiles are never red nor green.

The rectangle you choose still must have red tiles in opposite corners, but any other tiles it includes must now be red or green. This significantly limits your options.

Note: 54

The largest rectangle you can make in this example using only red and green tiles has area 24. One way to do this is between 9,5 and 2,3

Note: 91

OK, what's a good fast way to check this? For each coord, we can store whether it has red/green above/below/left/right. Then we can check if a rectangle is valid by checking if all the coords in the rectangle have red/green above/below/left/right appropriately.

Note: 40

Or we can just draw the grid the way they want and check for each rect we're checking. It'll be a little slow but doable.

Code: 64

g = np.array([["."]*(max(xs)+1) for _ in range(max(ys)+1)])
for x, y in zip(xs, ys): g[y][x] = "#"
g

Output: 1,237

array([['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'],
       ['.', '.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '#'],
       ['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'],
       ['.', '.', '#', '.', '.', '.', '.', '#', '.', '.', '.', '.'],
       ['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'],
       ['.', '.', '#', '.', '.', '.', '.', '.', '.', '#', '.', '.'],
       ['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.'],
       ['.', '.', '.', '.', '.', '.', '.', '.', '.', '#', '.', '#']],
      dtype='<U1')

Code: 99

for i,row in enumerate(g):
    rlocs = np.where(row == "#")[0]
    if len(rlocs) > 1: g[i, rlocs[0]+1:rlocs[-1]] = "X"
print("\n".join(["".join(l) for l in g]))

Output: 55

............
.......#XXX#
............
..#XXXX#....
............
..#XXXXXX#..
............
.........#X#

Note: 4

Now for cols

Code: 124

for i in range(g.shape[1]):
    col = g[:,i]
    rlocs = np.where((col == "#")|(col == "X"))[0]
    if len(rlocs) > 1: g[rlocs[0]+1:rlocs[-1], i] = "X"
print("\n".join(["".join(l) for l in g]))

Output: 60

............
.......#XXX#
.......XXXXX
..#XXXXXXXXX
..XXXXXXXXXX
..#XXXXXXXXX
.........XXX
.........#X#

Code: 657

def solveb(s):
    lines = s.splitlines()
    coords = [L(l.split(",")).map(int) for l in lines]
    xs, ys = map(np.array, zip(*coords))
    g = np.array([["."]*(max(xs)+1) for _ in range(max(ys)+1)])
    for x, y in zip(xs, ys): g[y][x] = "#"
    for i in range(len(coords)):
        p1, p2 = coords[i], coords[(i+1)%len(coords)]
        if p1[0] == p2[0]:
            miny, maxy = min(p1[1], p2[1]), max(p1[1], p2[1])
            g[miny:maxy+1, p1[0]] = "X"
        else:
            minx, maxx = min(p1[0], p2[0]), max(p1[0], p2[0])
            g[p1[1], minx:maxx+1] = "X"
    for i in range(g.shape[0]):
        rlocs = np.where((g[i] == "#")|(g[i] == "X"))[0]
        if len(rlocs) > 1: g[i, rlocs[0]+1:rlocs[-1]] = "X"
    max_a = 0
    for p in coords:
        for p2 in coords:
            if p2 == p: continue
            minx, maxx = min(p[0], p2[0]), max(p[0], p2[0])
            miny, maxy = min(p[1], p2[1]), max(p[1], p2[1])
            rect = g[miny:maxy+1, minx:maxx+1]
            if np.all((rect == "#")|(rect == "X")): max_a = max(max_a, (maxx-minx+1)*(maxy-miny+1))
    return max_a

solveb(samp)

Output: 16

Note: 27

OK I tried for the main one but even crating the grid freezes - here's why:

Code: 72

lines = inp.splitlines()
coords = [L(l.split(",")).map(int) for l in lines]
xs, ys = map(np.array, zip(*coords))
min(xs), max(xs), min(ys), max(ys)

Output: 57

(np.int64(1776), np.int64(98334), np.int64(1823), np.int64(98366))

Code: 10

max(xs)*max(ys)

Output: 27

np.int64(9672722244)

Note: 22

Yeah let's not store 9 billion things in memory and search through them.

Note: 64

Sparsity

We know that there are only <500 locs. So most rows and most cols will be separate. We can 'compress' the grid into something much more manageable and solve that way.

Code: 84

xmap = {x:i for i,x in enumerate(list(set(xs)))}
ymap = {y:i for i,y in enumerate(list(set(ys)))}
new_coords = [(xmap[x], ymap[y]) for x,y in coords]
new_coords[:4]

Output: 51

[(91, 63), (91, 160), (221, 160), (221, 10)]

Code: 834

def solveb(s):
    lines = s.splitlines()
    coords = [L(l.split(",")).map(int) for l in lines]
    xs, ys = map(np.array, zip(*coords))
    xmap = {x:i for i,x in enumerate(sorted(set(xs)))}
    ymap = {y:i for i,y in enumerate(sorted(set(ys)))}
    xrev = {i:x for x,i in xmap.items()}
    yrev = {i:y for y,i in ymap.items()}
    new_coords = [(xmap[x], ymap[y]) for x,y in coords]
    g = np.array([["."]*(len(xmap)) for _ in range(len(ymap))])
    for x, y in new_coords: g[y][x] = "#"
    for i in range(len(new_coords)):
        p1, p2 = new_coords[i], new_coords[(i+1)%len(new_coords)]
        if p1[0] == p2[0]:
            miny, maxy = min(p1[1], p2[1]), max(p1[1], p2[1])
            g[miny:maxy+1, p1[0]] = "X"
        else:
            minx, maxx = min(p1[0], p2[0]), max(p1[0], p2[0])
            g[p1[1], minx:maxx+1] = "X"
    for i in range(g.shape[0]):
        rlocs = np.where((g[i] == "#")|(g[i] == "X"))[0]
        if len(rlocs) > 1: g[i, rlocs[0]+1:rlocs[-1]] = "X"
    max_a = 0
    for p in new_coords:
        for p2 in new_coords:
            if p2 == p: continue
            minx, maxx = min(p[0], p2[0]), max(p[0], p2[0])
            miny, maxy = min(p[1], p2[1]), max(p[1], p2[1])
            rect = g[miny:maxy+1, minx:maxx+1]
            if np.all((rect == "#")|(rect == "X")): 
                orig_w = xrev[maxx] - xrev[minx] + 1
                orig_h = yrev[maxy] - yrev[miny] + 1
                max_a = max(max_a, orig_w * orig_h)
    return max_a

solveb(samp)

Output: 22

np.int64(24)

Code: 6

solveb(inp)

Output: 27

np.int64(1429596008)