advent day 9 part 2

advent.py

#!/usr/bin/env python

input="""97652,50353
97652,51578
98177,51578
98177,52782
97848,52782
97848,54028
98180,54028
98180,55220
97818,55220
97818,56391
97377,56391
97377,57573
97103,57573
97103,58738
96759,58738
96759,59924
96540,59924
96540,61136
96426,61136
96426,62265
95966,62265
95966,63548
96058,63548
96058,64735
95776,64735
95776,65881
95363,65881
95363,67069
95062,67069
95062,68316
94887,68316
94887,69336
94154,69336
94154,70373
93489,70373
93489,71299
92620,71299
92620,72393
92107,72393
92107,73844
92218,73844
92218,74552
91010,74552
91010,75746
90632,75746
90632,76770
89971,76770
89971,77508
88904,77508
88904,78805
88625,78805
88625,79864
87996,79864
87996,80347
86660,80347
86660,81783
86473,81783
86473,82435
85370,82435
85370,83144
84354,83144
84354,84268
83764,84268
83764,84688
82487,84688
82487,86007
82050,86007
82050,86384
80770,86384
80770,87439
80068,87439
80068,88568
79399,88568
79399,89172
78320,89172
78320,89820
77280,89820
77280,90654
76363,90654
76363,91139
75221,91139
75221,91388
73952,91388
73952,91921
72863,91921
72863,92719
71913,92719
71913,93621
70997,93621
70997,93862
69761,93862
69761,93895
68452,93895
68452,94308
67319,94308
67319,94922
66259,94922
66259,95857
65296,95857
65296,95455
63892,95455
63892,96596
62960,96596
62960,96344
61633,96344
61633,97187
60582,97187
60582,97323
59360,97323
59360,97241
58106,97241
58106,97077
56855,97077
56855,97914
55741,97914
55741,97491
54474,97491
54474,98186
53310,98186
53310,98313
52091,98313
52091,97963
50859,97963
50859,97993
49644,97993
49644,98131
48423,98131
48423,97674
47227,97674
47227,97818
46001,97818
46001,97541
44809,97541
44809,97674
43568,97674
43568,97153
42418,97153
42418,97018
41212,97018
41212,96839
40011,96839
40011,96908
38747,96908
38747,96211
37669,96211
37669,95612
36582,95612
36582,95958
35205,95958
35205,95395
34106,95395
34106,94919
32984,94919
32984,94904
31675,94904
31675,93591
30909,93591
30909,93627
29561,93627
29561,93181
28420,93181
28420,92249
27530,92249
27530,91650
26476,91650
26476,91293
25278,91293
25278,90408
24395,90408
24395,89733
23389,89733
23389,89410
22133,89410
22133,88221
21495,88221
21495,88098
20055,88098
20055,86954
19408,86954
19408,86000
18627,86000
18627,85174
17744,85174
17744,84290
16917,84290
16917,83949
15543,83949
15543,82524
15272,82524
15272,82014
14033,82014
14033,81229
13071,81229
13071,80009
12633,80009
12633,79298
11563,79298
11563,77911
11393,77911
11393,77034
10537,77034
10537,76109
9737,76109
9737,75227
8849,75227
8849,74191
8199,74191
8199,72849
8104,72849
8104,71723
7650,71723
7650,70806
6775,70806
6775,69808
6032,69808
6032,68422
6177,68422
6177,67599
4974,67599
4974,66360
4800,66360
4800,65212
4392,65212
4392,63906
4498,63906
4498,62834
3855,62834
3855,61672
3502,61672
3502,60414
3559,60414
3559,59362
2664,59362
2664,58173
2368,58173
2368,56862
2875,56862
2875,55672
2668,55672
2668,54503
2191,54503
2191,53257
2581,53257
2581,52087
1778,52087
1778,50859
2032,50859
2032,50331
94803,50331
94803,48426
1962,48426
1962,47196
1792,47196
1792,46022
2423,46022
2423,44825
2604,44825
2604,43540
2118,43540
2118,42384
2636,42384
2636,41104
2401,41104
2401,39959
2912,39959
2912,38754
3117,38754
3117,37500
3158,37500
3158,36316
3485,36316
3485,35167
3921,35167
3921,34151
4732,34151
4732,33078
5330,33078
5330,32041
5990,32041
5990,30813
6188,30813
6188,29525
6294,29525
6294,28756
7492,28756
7492,27549
7785,27549
7785,26435
8276,26435
8276,25150
8492,25150
8492,24090
9110,24090
9110,23448
10355,23448
10355,22560
11193,22560
11193,21191
11371,21191
11371,20292
12203,20292
12203,19636
13320,19636
13320,18789
14184,18789
14184,17567
14633,17567
14633,16387
15159,16387
15159,15698
16203,15698
16203,15120
17332,15120
17332,14042
17994,14042
17994,13241
18913,13241
18913,12731
20068,12731
20068,12034
21059,12034
21059,10932
21755,10932
21755,10488
22931,10488
22931,9468
23716,9468
23716,9203
24989,9203
24989,8064
25730,8064
25730,8168
27185,8168
27185,7292
28092,7292
28092,6335
28981,6335
28981,5999
30176,5999
30176,5479
31284,5479
31284,5717
32690,5717
32690,5150
33766,5150
33766,4409
34793,4409
34793,4363
36052,4363
36052,3890
37175,3890
37175,3302
38277,3302
38277,2760
39406,2760
39406,3329
40768,3329
40768,2470
41844,2470
41844,2397
43068,2397
43068,1912
44237,1912
44237,2403
45515,2403
45515,1733
46683,1733
46683,2489
47943,2489
47943,2215
49143,2215
49143,1549
50359,1549
50359,2310
51562,2310
51562,2412
52767,2412
52767,1685
54039,1685
54039,1939
55247,1939
55247,2436
56416,2436
56416,2774
57593,2774
57593,2803
58820,2803
58820,3228
59973,3228
59973,3694
61107,3694
61107,3625
62374,3625
62374,3718
63614,3718
63614,4723
64574,4723
64574,5009
65751,5009
65751,5104
67006,5104
67006,5837
68021,5837
68021,5991
69272,5991
69272,6559
70350,6559
70350,7123
71427,7123
71427,7230
72746,7230
72746,7872
73792,7872
73792,8795
74668,8795
74668,9195
75855,9195
75855,9964
76812,9964
76812,10693
77792,10693
77792,11903
78411,11903
78411,12115
79776,12115
79776,13307
80374,13307
80374,13750
81588,13750
81588,14917
82171,14917
82171,15618
83170,15618
83170,16626
83871,16626
83871,16952
85285,16952
85285,17879
86086,17879
86086,19186
86436,19186
86436,20037
87307,20037
87307,21153
87842,21153
87842,22036
88678,22036
88678,23106
89256,23106
89256,23660
90616,23660
90616,25133
90560,25133
90560,26184
91150,26184
91150,26973
92220,26973
92220,27937
93010,27937
93010,29308
92984,29308
92984,30226
93888,30226
93888,31507
93990,31507
93990,32600
94512,32600
94512,33798
94761,33798
94761,34939
95152,34939
95152,35910
96099,35910
96099,37037
96604,37037
96604,38375
96308,38375
96308,39427
97144,39427
97144,40708
96973,40708
96973,41904
97176,41904
97176,43128
97185,43128
97185,44263
97870,44263
97870,45488
97885,45488
97885,46729
97606,46729
97606,47920
98042,47920
98042,49141
97867,49141
97867,50353
"""
import numpy as np
EMPTY=0
PAINTED=1
RED=2
EXTERIOR=3
HERE=4
BOOM=5
state_to_pattern = dict({
    EMPTY: ".",
    PAINTED: "X",
    RED:"#",
    EXTERIOR:"P",
    HERE:"*",
    BOOM:"B",
})
class Matrix:

    def __init__(self,size_x,size_y, mutable_sequence):
        """construct a view of a dimension x and y on mutable_sequence
        the mutable_sequence must have a dimension compliant with its size
        """
        self.size_y=size_y
        self.size_x=size_x
        self.matrix=mutable_sequence
        self.pattern = [ state_to_pattern[k] for k in sorted(state_to_pattern.keys())]

    def _oneD_offset(self,ix,iy):
        x=ix%self.size_x
        y=iy%self.size_y
        offset = y*self.size_x+x
        if offset >= self.size_x * self.size_y :
            print("%d(%d), %d(%d) => %d BOOOM"% (x,ix, y,iy, offset))
        return offset

    def get(self,x,y):
        """get item at coordinates x,y"""

        return self.matrix[round(y)*self.size_x+round(x)]

    def set(self,x,y,val):
        """set value val at coordinates x, y"""
        self.matrix[round(y)*self.size_x+round(x)]=val

    def __str__(self):
        """poor man's amazing graphical effects:)"""
        to_print=" "
        to_print+="'    " * (self.size_y//5 )

        for x in range(self.size_y):
            for y in range(self.size_x):
                if (y==0):
                    to_print+='\n ' if x%5 else "\n-"
                #import pdb;pdb.set_trace()
                to_print+=self.pattern[self.get(y,x)]
        return to_print

input2="""
7,1
11,1
11,7
9,7
9,5
2,5
2,3
7,3
"""
from ctypes import c_uint8, c_float
from multiprocessing import Pool, Manager, cpu_count, shared_memory, Queue, Process, Value
from functools import reduce
from time import sleep
def generate_ppm(arg):
    queue, mask_shm, X, Y, lock = arg
    mask = Matrix(X,Y, np.ndarray((X*Y), dtype=np.uint8, buffer=mask_shm.buf))
    process = 1
    while True:
        with open(f"out.{X//100}.{Y//100}.{process}.ppm", "w") as out:
            out.write(f"""P2
{Y//100 -1} {X//100-1}
15
""")

            for y in range(0, Y, 100):
                for i,x in enumerate(range(0, X, 100)):
                    out.write(str(mask.matrix[(x) + X * (y)] * 5) + " ")
                    if i and i%20==0: out.write("\n")
                out.write("\n")
        sleep(60)
        process+=1

def paint(arg):
    init, mask_shm, X, Y, lock = arg
    propagated = 0
    todo = {init,}
    mask = Matrix(X,Y, np.ndarray((X*Y), dtype=np.uint8, buffer=mask_shm.buf))
    while todo:
        new_todo=set()
        for p in todo:
            x,y = p
            propagated+=1
            #if propagated % (10 * max(X,Y)) ==0:
                #print(".", end="")
            for dx,dy in ( (-1, 0), (1,0), (0,-1), (0,1), (0,0)):
                   # with lock:
                if X>x+dx>=0 and Y>y+dy>=0 and mask.matrix[(x+dx) + X * (y+dy)]==EMPTY:
                    mask.matrix[(x+dx) + X * ( y+dy)]= EXTERIOR
                    new_todo|={(x+dx,y+dy,),}
            if propagated % 1000 == 0 :
                print(".", end="")
            if propagated % 10000 == 0 :
                print(f"({len(todo)})", end="")

        todo=new_todo


    return True

def check_rectangle_inside(arg):
    inq, maxor, X, Y, mask, lock = arg
    print("!" * 80)
    while p := inq.get():
        if p == "boom": break
        tile1, tile2 = p
        lower = complex(min(tile1.real, tile2.real), min(tile1.imag, tile2.imag))
        upper = complex(max(tile1.real, tile2.real)+1 , max(tile1.imag, tile2.imag)+1)
        recentered = upper - lower
        if  recentered.imag * recentered.real <= maxor.value: continue
        is_interior  = np.vectorize(lambda x : x != EXTERIOR)
        is_in=True
        for y in range(round(lower.imag),round( upper.imag)):
            is_in &= np.all(is_interior(mask.matrix[round(lower.real)+X*y:round(upper.real)+X*y]))
            if not is_in : break
        print(f"{upper}x{lower} {( recentered.imag) * (recentered.real)} {is_in}")
        if is_in:
            with lock:
                
                maxor.value = max(maxor.value, recentered.imag * recentered.real)

def treat_input(input, hole=False):
    tiles=tuple()
    max_area = 0
    print("*-" * 20)
    for l in input.split():
        tiles+=(complex(*map(int,l.split(","))),)
    #paint
    X = int(max(map(lambda c:c.real, tiles))) +1 
    Y = int(max(map(lambda c:c.imag, tiles))) +1

    print(X)
    print(Y)

    mask_shm = shared_memory.SharedMemory(create=True, size=X*Y)
    mask = Matrix(X,Y, np.ndarray((X*Y), dtype=np.uint8, buffer=mask_shm.buf))
    

    for c,tile1 in enumerate(tiles):
        print("progression = %3.2f" % (c/len(tiles) * 100), end="\r")
        mask.set(tile1.real, tile1.imag, RED)
        for tile2 in (tiles[(c+1)%len(tiles)],tiles[(c-1)%len(tiles)]):
            if tile1.real == tile2.real:
                for y in range(round(tile1.imag),round( tile2.imag)+1):
                    if mask.get(tile1.real,y) == EMPTY:
                        mask.set(tile1.real, y,PAINTED)
            if tile1.imag == tile2.imag:
                for x in range(round(tile1.real),round( tile2.real)+1):
                    if mask.get(x,tile2.imag) == EMPTY:
                        mask.set(x, tile1.imag,PAINTED)
            mask.set(tile2.real, tile2.imag, RED)
    

    #print(mask)
    CENTER=sum(tiles)/len(tiles)
    print(f"{int(CENTER.real)}, {int(CENTER.imag)}")
    x,y=int(CENTER.real), int(CENTER.imag)
     
    with Manager() as m:
        lock = m.Lock()
        #paint(((0,0), mask_shm, X, Y, lock ),)
        processes = [
        Process(target=paint,args= (((0,0), mask_shm, X, Y, lock),)),
        Process(target=paint,args= (((X-1,0), mask_shm, X, Y, lock),)),
        Process(target=paint,args= (((0,Y-1), mask_shm, X, Y, lock),)),
        Process(target=paint,args= (((X-1,Y-1), mask_shm, X, Y, lock),)),
        ]
        if hole:
            processes += [
                Process(target=paint,args= (((x,y), mask_shm, X, Y, lock),)),
            ]
        
        draw = Process(target=generate_ppm, args= (((x,y), mask_shm, X, Y, lock),))
        draw.start()
        list(map(lambda p : p.start(), processes))
        list(map(lambda p : p.join(), processes))
        draw.terminate()

    print("prout")
    print("*" * 80)
    print("*k*")

    i=0

    print("detection suf")
    with Manager() as m:
        lock = m.Lock()
        QMS=1_000
        inq=Queue(QMS)
        maxor = Value(c_float, 0)

        #paint(((0,0), mask_shm, X, Y, lock ),)
        processes = [
        Process(target=check_rectangle_inside,args= ((inq,maxor, X, Y, mask, lock),)),
        Process(target=check_rectangle_inside,args= ((inq,maxor, X, Y, mask, lock),)),
        Process(target=check_rectangle_inside,args= ((inq,maxor, X, Y, mask, lock),)),
        Process(target=check_rectangle_inside,args= ((inq,maxor, X, Y, mask, lock),)),
        ]
        list(map(lambda p : p.start(), processes))
        for c,tile1 in enumerate(tiles):
            print("progression = %3.5f" % (c/len(tiles) * 100))

            for d,tile2 in enumerate(tiles[c:]):
                i+=1
                if tile1 == tile2: continue
                inq.put((tile1, tile2),)
                if inq.qsize() > .9 * QMS:
                    sleep(.1)

        inq.put("boom")
        inq.put("boom")
        inq.put("boom")
        inq.put("boom")
        list(map(lambda p : p.join(), processes))


        print(maxor.value)
        return(maxor.value)

print(treat_input(input2))
print("-" * 80)
assert treat_input(input2)==24.0
print(treat_input(input))

output.mp4