Day9.py

input="""9896513457895219985678901987899932101234895432101989013989656789689019778932123456789543210197689542
8764302969994398764568999986798763213356789543319878929876534245998998568943299767897659329986598921
9873219898989579896789987675987654344587897654929767899987321019876876457894987978998998998964497893
7654398767678998987899876554599875558788998979897656789798462198765464348989876799989876976543236789
9867999654569987699965965432101996679899789998788545989519553259874321245678965678978945989532125899
1979898765678976598754398743212987989976599987643634569329879345993210234789984789167896798673034679
0298769896789965439843139654453498998897989998732123458934989457986541345678999896256789989765123578
1987654987896799123921098765577689656789568997841014567896798969987432345678968965347899879897545689
2988663498965678939872129878788794545795456985432323789987987798798973479899459876498999767998957997
9876532679654567898653234989899893234894349876644435692199886665679654567891345987899987659899868976
5987643498767678987654356799923985456789246987655645789098765434579887679920124598987897644678978985
4398759999898989798765456899019876568890166898876876899987654325789999796431235789696689433567989524
0239898788999996569897567898999987679931245699998988999898985416898769896542345898545568921378995435
1545996567899899478987679997578999989549356987659599999769876527797658998743698987323467892989876557
3466987356789788989998789765489767999698999876544459988953988635689767899984567896516689999899987668
4578975238896567899989898654398755878997789999432398876794599545799898989875778965435999998778998979
6989854345789456999878987543239543569986579998910987645689698756892999765986789879569898784567989899
7899766567991245689769998865398754698765459877899876834898799767994987654598896998998789643469876798
8985977678920756789547899976579767987655368966798965423699989878989999743589945987847679432398765656
9764998989321569897636988987679899997644239854387965434589978989678998954678929865436568943987654535
9879869698943458994324567898989932986532198765456896645678967294569897978789546984323459954599653124
4998954567895767989401346799994321397321019876568987659789653123498656999898659875415667895698784234
3987553458976779876532346789875210986542123987879898767899873234998945789998797998734789986789895345
9876432899897897996545557899654349998763445698989799879998764349876735779999986569645678998998986656
5998543798789976987668769998965498989876569789997678989549879656954324567899875498789789999986598767
4459654597679895498779978987899987678989678999876567899929998969875436789979965319999897899875469898
2349765986578689329989989765698898567898799932997688998797997899996545678967894324989986799854345999
1269899997434567912392199894597767477789999891098899987656786799998656989458789455678975798765456789
2356987989323499324999012989986548345678998789129999876545345678998787895345678966989654899879599991
3479896567215989439898929878996433234567988679299799965434235689769998975467789878996543499998987890
5599765432104878998767899967689610123679876558987698764320146899659329696998999999987794989997676799
6989987543223467897656798754596531235698965437899549989432245988998934599899998765699895678986545678
9876987657335598976545897643479932349987654326788957997544556976767895989768999883799976989995436789
9965398767846679765434987621467893567898975214567898998867867895458969878756678954899897899987545894
9878459898987789986557896532356989798949876723678999459978978954349759865532566895999798999987657893
4989569989899895499878987654569878999433997934678995345989989863212349873201345789878679998999798932
3398798678799986598989398767698767998912986545679689256993299954323498764322456896569569987559899991
1239987547689998987891299878987654987923499657892579099892198765434569875438579976452458976443999979
2545998634567899876789987989699643986894998968921399988793019876547678987547679654321347894321298768
3659875323455678965459876593498901975679877899430989876589923989659789698678789763210156987434398657
5667994210134567895320975432987899864698766788959976545467894598767999459889899975321239896595976545
8779987321245679976459876679996987653598654667998765432356789689879768999995978965442398789989996423
9998765452456789989867987798964599769987543546899895421245778999989356789354569898754497654578989534
3239876564567897999978998987543459898798732135699985320134567899992124593253498799966596543365678945
4396997776678946789999989997632349997698644276789876534234778998963246999012349679997989342234568957
5975498989789235998998979898543498887598756987898987665356789987654357898929998598999876210134578968
6989329999892139897987656789654987654349897898987899985468896898799968956798767456889965431234589878
9898910989951029776899887898775699887212998999765321296567945679987899245999842345679876542345679999
8787899876543197655353999979989789976535679999987432987679234999996799458998943659789987986578989321
7656789998954569943212398767499899987646798987976543698789359879765678967987654578896798997689894310
3843458999765898762103569656321998999756987656799684569895479764334567899099898699965329298999765421
1012367899986798543212398743210197989869876545678965678976598743223479964125979789543210129678986632
4124878989897987659654987654323986678979865434567897789989987652101457893234569898798721234569999543
3234799976789998768765698786549765456989877655689998898799876543212345995686689959987642949698998969
4765678945678999899879899897998654346893989766895439987545988754323456789787789543298859898976546798
5876899766799999934989942998909765757892199989989920985434699876434789999899899432109998767995435697
6987989978943989955994321349919876898989019997678799876546892987945697987998998953212987656789521486
7898967899999976899875520457899987949978998987568689987678921099986796895987997894324598845693210245
9949459999987834894987521245678999234567896796434567899989439989987895796796876789495987656789654356
7431298989996325793295432957789654346698934987513678999996598979898954589985435699989998968898765458
6532987878954314679986649899998786467989423598923899798987987658789865679976323589579999879969976569
7643976667895323689997998677899897678978912499535994567899996545699876798765434579468899997657989978
8759765456789534567899877566789998899767893987676789698968997534469989899876556689356789349869898899
9867976578897645679998765434678959987846789998889898789349876212378998998989667793247890123998776799
5989987678987656889999976323489543976434568999999909891236954334489987766598798920124569434987645689
4399998789999968998976985401568964985423667999989212990545695546598765755469899531234568949875534578
3238999899989899357899876512359879897912356789879323989676987957989854332345995432345679698764323567
4346998999876789234999997675468998789895477899968939878997898768976543210236789543459896569995654678
5557897898765799356789898886579987679789568989959998766789959878988654632447898655569943456986789789
7678916987654678967998789997679977578678979577898989655678943989999766543456998776778932768999899892
8999935698543569898987678998798765456568989456987678934899321299879878956788979897889549879126999921
9789896987432689789987567899899984323499994345698789545689210359765989867999864999997698991014697432
5698769875421345679098778976912395544678943234569898787789322498964599988902963489129987889123976549
9989656995434597892129989765423987655789432123978999998995439987895678999219854678998876778945798698
8979937896665689999234799987634599767898543236899989129896798996789799854398765689987654867956789987
7567899987787798798975689999785679879987654345789878998798987895699898765459986792976543456897999876
2347999998998939667896789999897790989098786467898769898689996434578959978567987891297632365779999765
1356789879549023456987999891999991292169897678987658789579875423469543989678998954398721234567899853
2579899765432139567898998792398789965356998989298745689359989212378932399899109795459810125678999761
3458999879549298979919876599987689899769999890129634590298999102347891235994323679598323234789989842
4667899998798987894329875478976599798998898751398523791987898913456789356789434567987654456998976543
9788998969987976789498754357894398687666789942987434899876787894577899868899945878998787669897987655
9899997756796545689569543268943239546544567899876545689975656997689949878999896789999998798786499876
5932986542987323589979985179994998432133456789987656799864346789789431989998799999887659989695321989
4691987431299212567899876799989897657012567999898767899943235689894320197898698998764349876543210199
3589997620198343459979999899876789432123489998769878919874346795975431246789567789853234998754342999
2378998435297654568967988999985679543434599876543989202965457944986532347992345698742123789868769898
4567899949998765979756567998674789754678967989432198929876578923499693467898456989643345678979899776
9689998797899986899643459889543899869889757898953987999987689439698989568986579878967467789698998645
8789987686789997998794569768956789878998648997899876789998996598987678999298699867898988994567976434
9891096575678999459989998956898898999349899986798765678999987987896566789359987648999499123569884321
4999989434567994369879876346789997891235989765659543568999898986954345678969986534894321012498765432
5698778923456789298767995457898976789399879953549852346789799987893237789998758623799469993569878658
7987667994767890198857987768987635899989769892139761456894689998954345899879543712678998789678989767
9876546789878999987845898979996547999767659789019862867932399899865456798765432101567899656989999898
2987634599989998765435689989987657897655545679198654979653456789996587899876583312488996548899987949
1296545689999869984326796594598768987643435689239776789765579899987679935997765469699689437698965437
0987657899875456976457895412569899996432123596467987899876789998798989321098987878789578926567896545
1298769999764322987768954323456921987541012359578998921989895497659799533129898989893459212378998856
2349896598753210198978967764567890199432124568999109430199943298345678954235679999932368901456789768"""

input_test = """2199943210
3987894921
9856789892
8767896789
9899965678"""

def check_low_point(matrix, i, j):
    if i > 0 and int(matrix[i-1][j]) <= int(matrix[i][j]):
        return 0
    if j > 0 and int(matrix[i][j-1]) <= int(matrix[i][j]):
        return 0
    if i < len(matrix) -1  and int(matrix[i+1][j]) <= int(matrix[i][j]):
        return 0
    if j < len(matrix[i]) -1  and int(matrix[i][j+1]) <= int(matrix[i][j]):
        return 0
    return int(matrix[i][j]) +1


def first_star():
    global input
    input_list = list(map(list,input.split('\n')))
    res = 0
    for i in range(len(input_list)):
        for j in range(len(input_list[i])):
            res+= check_low_point(input_list, i, j)
    print(f"First star: {res}")


def compute_basin(matrix, i, j):
    if i >= len(matrix) or i < 0:
        return 0
    if j >= len(matrix[i]) or j < 0:
        return 0
    if matrix[i][j] == '9':
        return 0
    res = 1
    matrix[i][j] = '9'
    res += compute_basin(matrix, i + 1, j) + compute_basin(matrix, i - 1, j) + compute_basin(matrix, i, j + 1) + compute_basin(matrix, i, j - 1)
    return res


from functools import reduce
def second_star():
    global input
    input_list = list(map(list, input.split('\n')))
    res = [0,0,0]
    for i in range(len(input_list)):
        for j in range(len(input_list[i])):
            if input_list[i][j] != '9':
                basin = compute_basin(input_list, i, j)
                if basin > res[0]:
                    res[0] = basin
                    res = sorted(res)
    print(f"Second star: {reduce(lambda x,y: x*y, res)}")



if __name__ == '__main__':
   first_star()
   second_star()