aoc 2025 08

2025_08.jl

using LinearAlgebra

function day09_2025_1(; i = input_2025_09())
    tiles = [parse.(Int, split(l, ",")) for l = split(i, "\n")]
    area_it = ((1 + abs(x1 - x2)) * (1 + abs(y1 - y2)) for (x1, y1) = tiles, (x2, y2) = tiles)
    maximum(area_it)
end

function tiles_09_2025()
    [parse.(Int, split(l, ",")) for l = split(input_2025_09(), "\n")]
end

function day09_2025_2(; i = input_2025_09())
    drop = Iterators.drop
    cycle = Iterators.cycle
    take = Iterators.take
    flatten = Iterators.flatten

    cross = (x1, y1, x2, y2) -> dot(rot90(x1, y1), [x2, y2])
    rot90 = (x, y) -> [-y, x] # assume z axis down in paper
    takec = (x, n) -> collect(take(x, n))
    shrink = r -> r.start:(r.stop - 1)

    tiles = [parse.(Int, split(l, ",")) for l = split(i, "\n")]
    tiles_c = cycle(tiles)
    pairs0 = zip(tiles_c, drop(tiles_c, 1))
    direction_vecs = (sign.(vec(p2 .- p1)) for (p1, p2) = pairs0)
    cross_prods = (cross(x1, y1, x2, y2) for ((x1, y1), (x2, y2)) = zip(direction_vecs, drop(direction_vecs, 1)))

    (firsty, lasty) = extrema([y for (_, y) = tiles])

    # sum is positive, rotation is clockwise
    # we trace the line around the left hand side as we walk around the edges
    # @show sum(collect(take(cross_prods, length(tiles))))
    # lines are given in a coordinate system that surrounds the grid blocks. grid(1,1) is surrounded by (0,0) -> (0,1) -> (1,1) -> (0,1)
    # the coordinate of the gris in the border coordinate system is (x_g, y_g) + (0.5, 0.5)
    border_point = function(p, direction_to, cross_prod)
        # cross_prod is zero for straight ahead, 
        # @show (p = p, d = direction, c = cross_prod)
        tmp = if abs(cross_prod) == 1
            # +90 deg turn
            [p .+ [0.5, 0.5] - 0.5 * rot90(direction_to...) + sign(cross_prod) * 0.5 * direction_to]
        elseif cross_prod == 0
            # we dont need to keep track of points on a straight line
            []
        else
            error("180 degree turn detected at point $p, cross: $cross_prod, direction: $direction_to")
        end
        [Int.(p) for p = tmp]
    end
    p_d_c = zip(drop(tiles_c, 1), direction_vecs, cross_prods)
    border_it = flatten((border_point(p, d, c) for (p, d, c) = p_d_c))
    border_pairs = zip(border_it, drop(border_it, 1))

    # figure out which tiles are captured at a given tile y
    build_vertical_reducer = function(acc, pair)
        ((x1, y1), (x2, y2)) = pair
        if x1 == x2
            set = union(get(acc, x1, Set()), [min(y1, y2):max(y1, y2)])
            acc[x1] = set
            acc
        else
            acc
        end
    end
    vertical = foldl(build_vertical_reducer, take(border_pairs, length(tiles) + 1), init = Dict()) 

    # for each value of x, make a list of ranges that are inside the border path
    x_captures = function(tile_y)
        x_and_ys = flatten((zip(x, ys_set) for (x, ys_set) = vertical))
        xs = (x for (x, ys) = x_and_ys if tile_y in shrink(ys))
        (shrink(min(a, b):max(a, b)) for (a, b) = Iterators.partition(xs, 2))
    end

    captures = [(y, collect(x_captures(y))) for y = firsty:lasty]
    #for y = firsty:lasty
        #println("y: $y, captures: $(collect(x_captures(y)))")
    #end

    compressor = function(acc, cap)
        if length(acc) < 2
            vcat(acc, [cap])
        elseif acc[end - 1][2] == acc[end][2] == cap[2]
            vcat(acc[1:(end - 1)], [cap])
        else
            vcat(acc, [cap])
        end
    end
    captures_c = reduce(compressor, captures, init = [])
    captures_c
end

function day09_2025_2b(captures = day09_2025_2(), tiles = tiles_09_2025())
    drop = Iterators.drop
    cycle = Iterators.cycle
    take = Iterators.take
    flatten = Iterators.flatten

    find_seeds = function(cap0, cap1)
        is_overlapping = (a, b) -> a.start in b || a.stop in b || b.start in a || b.stop in a
        (y0, captures0) = cap0
        (y1, captures1) = cap1
        ((y1, c) for c = captures1 if !any((is_overlapping(c, o) for o = captures0)))
    end

    capture_pairs = zip(vcat([(0, [])], captures), captures)
    seeds = flatten([find_seeds(a, b) for (a, b) = capture_pairs]) |> collect

    only_largest_capture_path = function(capture)
        span = r -> r.stop - r.start
        (y, c0) = capture
        c1 = sort(c0, by = span)
        (y, c1[end])
    end

    largest_capture = [only_largest_capture_path(c) for c = captures_c]
    for (_, r) = largest_capture
        @assert(r.start < r.stop)
    end

    largest_box = function(captures)
        ys = (y for (y, _) = captures)
        x0s = (r.start for (_, r) = captures)
        x1s = (r.stop for (_, r) = captures)
        (y0, y1) = extrema(ys)
        x0 = maximum(x0s)
        x1 = minimum(x1s)

        ((y1 - y0 + 1) * (x1 - x0 + 1), x0, y0, x1, y1)
    end

    is_box_free = function(p0, p1)
        (x0, y0) = p0
        (x1, y1) = p1

        cc = [(y, c) for (y, c) = captures if min(y0, y1) <= y <= max(y0, y1)]
        all((any(((x0 in c) && (x1 in c) for c = cap)) for (_, cap) = cc))
    end

    calc_area = function(p0, p1)
        (x0, y0) = p0
        (x1, y1) = p1
        (abs(x0 - x1) + 1) * (abs(y0 - y1) + 1)
    end



    # solution = maximum([largest_box(largest_capture[i:j]) for i = 1:length(largest_capture), j = 1:length(largest_capture) if i < j])
    # solution

    pt_pairs = ((a, b) for a = tiles, b = tiles if a < b && is_box_free(a, b)) |> collect
    area_pt_pair = zip((calc_area(a, b) for (a, b) = pt_pairs), pt_pairs) |> collect |> sort |> last 
end

function plot_2025_09(captures_c)
    (_, ((x0, y0), (x1, y1))) = day09_2025_2b(captures_c)
    plot(getindex.(tiles_09_2025(), 1), getindex.(tiles_09_2025(), 2))
    plot!([x0, x1, x1, x0, x0], [y0, y0, y1, y1, y0], size = (2000, 2000))
end

#             X
#      01234567890123
#   00 ..............
#   01 .......#...#..
#   02 ..............
#   03 ..#....#......
# Y 04 ..............
#   05 ..#......#....
#   06 ..............
#   07 .........#.#..
#   09 ..............


function input_2025_09()
    "97603,50471
97603,51688
97910,51688
97910,52889
97643,52889
97643,54140
98081,54140
98081,55332
97733,55332
97733,56569
97800,56569
97800,57733
97343,57733
97343,58996
97483,58996
97483,60230
97398,60230
97398,61323
96693,61323
96693,62437
96148,62437
96148,63711
96183,63711
96183,64829
95675,64829
95675,66056
95497,66056
95497,67159
94960,67159
94960,68169
94210,68169
94210,69500
94227,69500
94227,70429
93325,70429
93325,71522
92799,71522
92799,72867
92741,72867
92741,73675
91676,73675
91676,74818
91222,74818
91222,75610
90195,75610
90195,77017
90123,77017
90123,77844
89172,77844
89172,78974
88649,78974
88649,79886
87830,79886
87830,80745
86952,80745
86952,81318
85759,81318
85759,82374
85127,82374
85127,83268
84311,83268
84311,84414
83739,84414
83739,85299
82895,85299
82895,86128
81997,86128
81997,86720
80897,86720
80897,87218
79739,87218
79739,87877
78723,87877
78723,89194
78188,89194
78188,89419
76861,89419
76861,90179
75913,90179
75913,90850
74904,90850
74904,92015
74176,92015
74176,92349
72960,92349
72960,92802
71821,92802
71821,93728
70915,93728
70915,94003
69693,94003
69693,94322
68502,94322
68502,94730
67356,94730
67356,95100
66197,95100
66197,95162
64939,95162
64939,95978
63927,95978
63927,96183
62721,96183
62721,96984
61669,96984
61669,96948
60405,96948
60405,97193
59212,97193
59212,97025
57948,97025
57948,97102
56739,97102
56739,97458
55567,97458
55567,97828
54385,97828
54385,97473
53142,97473
53142,98135
51963,98135
51963,98420
50747,98420
50747,97827
49526,97827
49526,98438
48292,98438
48292,97494
47119,97494
47119,97428
45915,97428
45915,97999
44638,97999
44638,97417
43483,97417
43483,97450
42249,97450
42249,96815
41129,96815
41129,96489
39965,96489
39965,97129
38570,97129
38570,96797
37387,96797
37387,96063
36324,96063
36324,95633
35184,95633
35184,95032
34107,95032
34107,95069
32798,95069
32798,94419
31744,94419
31744,93872
30656,93872
30656,93621
29431,93621
29431,93185
28283,93185
28283,92100
27475,92100
27475,91308
26533,91308
26533,91132
25234,91132
25234,90160
24412,90160
24412,89578
23349,89578
23349,89218
22122,89218
22122,88439
21183,88439
21183,87856
20092,87856
20092,86696
19467,86696
19467,86176
18315,86176
18315,85164
17591,85164
17591,84146
16891,84146
16891,83571
15756,83571
15756,82441
15187,82441
15187,81555
14369,81555
14369,80764
13437,80764
13437,79694
12836,79694
12836,78864
11937,78864
11937,77901
11204,77901
11204,77297
9940,77297
9940,76240
9312,76240
9312,74854
9229,74854
9229,73715
8785,73715
8785,72754
8029,72754
8029,71674
7484,71674
7484,70845
6416,70845
6416,69410
6627,69410
6627,68674
5265,68674
5265,67245
5553,67245
5553,66381
4385,66381
4385,65137
4237,65137
4237,63971
3876,63971
3876,62823
3446,62823
3446,61496
3714,61496
3714,60411
3025,60411
3025,59195
2894,59195
2894,57919
3147,57919
3147,56859
2055,56859
2055,55595
2304,55595
2304,54418
1809,54418
1809,53148
2431,53148
2431,51945
2301,51945
2301,50745
1708,50745
1708,50444
94904,50444
94904,48302
1837,48302
1837,47103
2244,47103
2244,45854
1861,45854
1861,44707
2621,44707
2621,43400
1983,43400
1983,42305
2892,42305
2892,41070
2871,41070
2871,39882
3124,39882
3124,38602
3001,38602
3001,37612
4038,37612
4038,36422
4266,36422
4266,35198
4408,35198
4408,33998
4656,33998
4656,32900
5197,32900
5197,31914
5995,31914
5995,30442
5641,30442
5641,29656
6854,29656
6854,28337
6921,28337
6921,27513
7970,27513
7970,26413
8479,26413
8479,25335
9034,25335
9034,24009
9207,24009
9207,22946
9822,22946
9822,22428
11211,22428
11211,21082
11426,21082
11426,20284
12386,20284
12386,19458
13292,19458
13292,18499
14033,18499
14033,17579
14822,17579
14822,16855
15816,16855
15816,15681
16354,15681
16354,14626
17036,14626
17036,13881
18011,13881
18011,13589
19363,13589
19363,12496
20033,12496
20033,11401
20729,11401
20729,10674
21717,10674
21717,10120
22825,10120
22825,9696
24006,9696
24006,8622
24774,8622
24774,8345
26031,8345
26031,8115
27292,8115
27292,7600
28383,7600
28383,6965
29416,6965
29416,6587
30571,6587
30571,5570
31452,5570
31452,5076
32569,5076
32569,4541
33674,4541
33674,4693
35013,4693
35013,4437
36198,4437
36198,4197
37383,4197
37383,3743
38510,3743
38510,3573
39710,3573
39710,2957
40817,2957
40817,3016
42058,3016
42058,2191
43159,2191
43159,2620
44442,2620
44442,2050
45603,2050
45603,1749
46805,1749
46805,2080
48045,2080
48045,2301
49263,2301
49263,1683
50478,1683
50478,1933
51694,1933
51694,2137
52902,2137
52902,2464
54093,2464
54093,2483
55307,2483
55307,2136
56578,2136
56578,2649
57734,2649
57734,3105
58885,3105
58885,2842
60178,2842
60178,3278
61330,3278
61330,3237
62602,3237
62602,3589
63778,3589
63778,3946
64952,3946
64952,4498
66057,4498
66057,5500
66983,5500
66983,5747
68186,5747
68186,6282
69275,6282
69275,6913
70316,6913
70316,7301
71471,7301
71471,7657
72654,7657
72654,8000
73858,8000
73858,8531
74967,8531
74967,9441
75841,9441
75841,10567
76551,10567
76551,10971
77742,10971
77742,11426
78917,11426
78917,12725
79447,12725
79447,12789
80959,12789
80959,13600
81879,13600
81879,14611
82614,14611
82614,15832
83128,15832
83128,16106
84571,16106
84571,17152
85248,17152
85248,18185
85923,18185
85923,18938
86915,18938
86915,20331
87129,20331
87129,21205
87970,21205
87970,21945
89008,21945
89008,23116
89451,23116
89451,24135
90103,24135
90103,25113
90822,25113
90822,26059
91606,26059
91606,27335
91803,27335
91803,28359
92448,28359
92448,29249
93385,29249
93385,30232
94169,30232
94169,31630
94004,31630
94004,32520
95049,32520
95049,33734
95291,33734
95291,34808
95924,34808
95924,36006
96196,36006
96196,37365
95867,37365
95867,38397
96712,38397
96712,39561
97095,39561
97095,40834
96955,40834
96955,42018
97219,42018
97219,43151
97868,43151
97868,44368
98004,44368
98004,45579
98210,45579
98210,46848
97612,46848
97612,48049
97814,48049
97814,49253
98400,49253
98400,50471"
end