From 230cb62ae502719fff9a31ff858abc354ef42b4e Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Tue, 26 Nov 2019 11:59:01 +0000 Subject: [PATCH] Done day 23 --- advent-of-code.cabal | 11 + data/advent23.txt | 1000 ++++++++++++++++++++++++++++++++++++++ problems/day23.html | 163 +++++++ src/advent23/advent23.hs | 238 +++++++++ 4 files changed, 1412 insertions(+) create mode 100644 data/advent23.txt create mode 100644 problems/day23.html create mode 100644 src/advent23/advent23.hs diff --git a/advent-of-code.cabal b/advent-of-code.cabal index 47dfd89..d3cd45c 100644 --- a/advent-of-code.cabal +++ b/advent-of-code.cabal @@ -270,3 +270,14 @@ executable advent22 build-depends: base >= 4.7 && < 5 , containers , pqueue + +executable advent23 + hs-source-dirs: src/advent23 + main-is: advent23.hs + default-language: Haskell2010 + build-depends: base >= 4.7 && < 5 + , containers + , text + , megaparsec + , linear + , pqueue diff --git a/data/advent23.txt b/data/advent23.txt new file mode 100644 index 0000000..9f66f2c --- /dev/null +++ b/data/advent23.txt @@ -0,0 +1,1000 @@ +pos=<70932188,34743415,13062034>, r=76082857 +pos=<106955091,25680936,39877548>, r=76227207 +pos=<53185960,-34838071,17086321>, r=79082157 +pos=<23486359,39569255,89931713>, r=97870382 +pos=<60023478,-38231503,83130191>, r=97171540 +pos=<67439466,22612444,3128451>, r=70392218 +pos=<70807196,62675476,35937093>, r=81014557 +pos=<84062142,31605221,28090534>, r=71045602 +pos=<94481737,-348921,40188224>, r=62787002 +pos=<115014210,8116575,40291216>, r=74750733 +pos=<130051481,16083298,36826149>, r=92777434 +pos=<100623374,-2402591,27320132>, r=83850130 +pos=<104850603,14011883,80188271>, r=90161622 +pos=<60595056,3873536,8887820>, r=55978226 +pos=<51454631,18048888,54567182>, r=88280232 +pos=<65904249,58628570,36140145>, r=71861499 +pos=<68798916,13894702,41659583>, r=85865960 +pos=<98790279,25761991,22278750>, r=85742293 +pos=<8996994,-28039790,33297161>, r=94634944 +pos=<106727332,35931026,44602047>, r=81525324 +pos=<60322605,17347145,52271167>, r=80914487 +pos=<64875283,1577480,39978898>, r=94480425 +pos=<-4157832,75402939,-50851076>, r=94021483 +pos=<122490329,14289977,42391900>, r=77857135 +pos=<114263327,-182934,39616904>, r=82973875 +pos=<37081774,37743973,29042705>, r=55833691 +pos=<-19504304,148534982,41486052>, r=93493754 +pos=<74064449,48243714,25455353>, r=80321637 +pos=<125026875,8312219,43195295>, r=81663677 +pos=<102114413,14855613,43042421>, r=57396401 +pos=<18813976,21452931,-2433338>, r=89286488 +pos=<63952384,14337568,-12876419>, r=74635127 +pos=<-11051509,18593887,43462428>, r=70396710 +pos=<69238671,50114806,32257411>, r=70565075 +pos=<80932135,32458826,18362699>, r=78497081 +pos=<56349554,35833484,70754111>, r=54047849 +pos=<95757757,34120917,22854111>, r=90493429 +pos=<54212105,49503608,181447>, r=87003350 +pos=<114989490,30670146,36753165>, r=92375397 +pos=<90789672,26178062,31902222>, r=68534300 +pos=<63987777,-58552423,59560182>, r=97886808 +pos=<56722210,20731826,34878607>, r=56288593 +pos=<90614128,15047837,32669791>, r=56460936 +pos=<100295228,15745485,43459876>, r=56049581 +pos=<54479747,32201863,75980199>, r=53772768 +pos=<39687165,5031646,109898927>, r=81711558 +pos=<58882772,6081340,8109949>, r=52835849 +pos=<-713051,18388572,41702775>, r=61612684 +pos=<103196987,25104857,30391244>, r=81380083 +pos=<76557255,-17356336,62927471>, r=72627324 +pos=<-3929222,14320850,37584102>, r=64879743 +pos=<97892656,14447007,41736963>, r=54071443 +pos=<-1271439,10252819,37385375>, r=62523034 +pos=<56325974,-4242704,-26972102>, r=95685148 +pos=<65315494,40992947,56077994>, r=53497187 +pos=<99421295,19631521,69175033>, r=79338677 +pos=<483195,45610683,41004669>, r=88336631 +pos=<100654183,22211924,29779631>, r=76555240 +pos=<56865293,16954244,3385892>, r=53902655 +pos=<114986974,20758908,37509521>, r=81705382 +pos=<13972220,35365136,38964263>, r=66642469 +pos=<63582095,47821293,34987865>, r=59884351 +pos=<94706141,55838175,41179101>, r=92834462 +pos=<101809135,16210718,85005028>, r=94135789 +pos=<43337912,71833224,17340722>, r=95368362 +pos=<-2047258,16499499,38925129>, r=63835574 +pos=<127650967,14466667,34660600>, r=90925762 +pos=<114194906,20421111,21029193>, r=97055554 +pos=<51933802,66752449,42540417>, r=59614573 +pos=<-31061971,16472680,45018088>, r=86730336 +pos=<126578089,14194797,62965771>, r=94849609 +pos=<51530964,4080625,-9981324>, r=65576101 +pos=<51852445,86159865,48519307>, r=77642340 +pos=<52180921,17777293,-8588817>, r=62015759 +pos=<37750926,54194202,58341899>, r=66640916 +pos=<86938460,-5356594,26415367>, r=74024050 +pos=<52662726,36643923,-7423982>, r=80199804 +pos=<118200303,22849547,45019771>, r=79498936 +pos=<66831889,55362649,23353479>, r=82309990 +pos=<108830050,17269267,28763865>, r=80804499 +pos=<91394962,-9397628,38509365>, r=70427514 +pos=<110054400,26797739,26129382>, r=94191618 +pos=<55627764,35130154,21541616>, r=52685108 +pos=<119021155,10252122,33545289>, r=83368586 +pos=<58722115,41511957,33182121>, r=50520865 +pos=<64403559,46194824,50821057>, r=52530253 +pos=<55357505,6659841,-18830634>, r=75672596 +pos=<76254957,37319909,23660920>, r=73382702 +pos=<61640535,52599442,75170506>, r=80521210 +pos=<122385451,14203889,66220841>, r=93921012 +pos=<100244104,5018079,31520266>, r=71850158 +pos=<82081383,23129394,4379732>, r=84300056 +pos=<99065937,30825858,15588119>, r=97772595 +pos=<116133693,18265457,51547284>, r=77057141 +pos=<52256299,30358745,50007183>, r=74240591 +pos=<59509894,49026601,15676312>, r=76329320 +pos=<59175810,58285957,48100353>, r=56672847 +pos=<89129622,-27112672,51059866>, r=83088437 +pos=<54779474,14931281,29211474>, r=84781460 +pos=<58446570,42845141,32698159>, r=52062283 +pos=<61862173,46364434,38645244>, r=53050120 +pos=<59644216,-4104996,104670106>, r=84205700 +pos=<113466424,-6277854,40699853>, r=87188713 +pos=<88618711,20141576,40923119>, r=51306024 +pos=<30502823,51831249,38274519>, r=67267911 +pos=<56738812,20510965,-5250022>, r=65968528 +pos=<58293908,43697440,69251205>, r=62353463 +pos=<109500456,24736053,39729692>, r=77975558 +pos=<78456611,17775083,23905850>, r=55794579 +pos=<103517548,19126241,53371699>, r=67126208 +pos=<-12263026,14804850,44707521>, r=66574097 +pos=<59710908,15511091,-990057>, r=59680928 +pos=<61928634,20561019,45136409>, r=75458094 +pos=<89825180,10772426,36769829>, r=50427220 +pos=<54798081,22088148,39561793>, r=70123747 +pos=<67677948,-22427413,42811645>, r=55438016 +pos=<-5695864,16853699,24908958>, r=81854355 +pos=<-13617304,14298749,43021926>, r=69107886 +pos=<97639071,4221323,33966350>, r=67595740 +pos=<94668710,40164358,40194419>, r=78107385 +pos=<31264483,2721629,12897457>, r=62005744 +pos=<53576971,24447380,8988631>, r=52504478 +pos=<76258490,519073,32838432>, r=51045275 +pos=<15425129,21986272,-7792889>, r=98567820 +pos=<90598370,26198910,40951799>, r=59314220 +pos=<32582492,-355164,18997671>, r=57664381 +pos=<73835746,63171851,29802095>, r=90674230 +pos=<126677052,19125296,33329525>, r=95941569 +pos=<56089763,19181211,-15491718>, r=74231424 +pos=<57519720,20084856,126740281>, r=95455607 +pos=<33386890,48038589,946548>, r=97918894 +pos=<66236948,83721210,41963263>, r=91463670 +pos=<59765458,30283310,-16471215>, r=89988727 +pos=<-2933604,23038390,21838497>, r=88347289 +pos=<69081478,53364906,38412173>, r=67503077 +pos=<101049675,10060125,41141395>, r=57992558 +pos=<100008356,32454967,43340830>, r=72591438 +pos=<109393083,-18948615,44410556>, r=92075431 +pos=<65031132,-19896749,53672918>, r=54387080 +pos=<101137076,109876103,-29433305>, r=69441271 +pos=<37489010,16664382,51487976>, r=65428674 +pos=<77877189,16229651,42389859>, r=51083530 +pos=<83644395,28290365,41187874>, r=54215655 +pos=<59270430,28524212,21184520>, r=50078866 +pos=<82200309,17808555,-4263046>, r=87741199 +pos=<94845158,44049406,30934045>, r=91429251 +pos=<38222205,36136535,-8780366>, r=90908667 +pos=<63890697,43632727,38922734>, r=52069518 +pos=<94704333,-950161,42263760>, r=61535022 +pos=<55494341,22073513,-20723460>, r=81760064 +pos=<85117842,14777006,27936303>, r=55427357 +pos=<99981747,23687693,71070838>, r=85851363 +pos=<92771274,51188159,27928078>, r=99500124 +pos=<29921726,17282907,47951257>, r=62962444 +pos=<52517489,17495577,119596987>, r=80720865 +pos=<107543935,-952558,37781114>, r=78859668 +pos=<227363471,20271523,30344823>, r=79921258 +pos=<56840403,8901316,20360281>, r=88710921 +pos=<-15031494,7679708,43655908>, r=72585256 +pos=<-1977883,8829489,30452009>, r=71585719 +pos=<130654084,6797807,40150026>, r=91850781 +pos=<27995505,18498744,-9366619>, r=84083728 +pos=<53593650,59502550,35284278>, r=61280650 +pos=<56639910,18756016,66809724>, r=52859168 +pos=<4956780,105313555,128100318>, r=89551723 +pos=<98904092,32207856,20750688>, r=93830055 +pos=<100007144,16869733,64902332>, r=72889978 +pos=<37727965,4599141,44557302>, r=69383432 +pos=<54063133,28687053,31545410>, r=59159300 +pos=<89335625,18731801,-2426760>, r=93962997 +pos=<74106169,52601353,22607411>, r=87568884 +pos=<81493072,62667056,37775575>, r=89853287 +pos=<123317452,14217567,43522565>, r=77481258 +pos=<92035356,45926855,54170316>, r=83243600 +pos=<57407835,62022858,38853311>, r=64046577 +pos=<100123788,29024509,42895298>, r=69721959 +pos=<65326818,21746775,16889163>, r=53653358 +pos=<122104832,20231127,38021089>, r=87783657 +pos=<34626921,33813790,16436186>, r=66964425 +pos=<129579038,10175556,34393931>, r=93153918 +pos=<76144539,7311472,10657230>, r=66320218 +pos=<93083215,31906812,66538939>, r=82639679 +pos=<44967994,18648196,2208091>, r=55686307 +pos=<13736172,-1245811,76800718>, r=80841660 +pos=<75380971,33097677,25078375>, r=66869019 +pos=<23974728,19339834,15015517>, r=64563600 +pos=<38830051,15329267,-25722538>, r=86435554 +pos=<-11570741,25060510,38310618>, r=82534385 +pos=<86831012,41249358,20448451>, r=91100814 +pos=<79979836,61812338,29997554>, r=95263603 +pos=<46305086,17350179,-23848220>, r=79107062 +pos=<118342906,14571828,44370572>, r=72013039 +pos=<76033011,16898158,-11948638>, r=88348552 +pos=<62704362,16430254,-4369420>, r=66972780 +pos=<107027000,29941235,30669820>, r=89767165 +pos=<30496026,73252753,44597437>, r=82373047 +pos=<121716240,22679491,44860838>, r=83003785 +pos=<99283587,39170616,39708136>, r=82215017 +pos=<93205806,36626096,28112740>, r=85187898 +pos=<78146780,37791515,43825596>, r=55581553 +pos=<110845284,27396232,44818881>, r=76891462 +pos=<53299340,67762644,43321640>, r=61209139 +pos=<86570062,32074254,26909185>, r=75203874 +pos=<112723064,16503283,34499712>, r=78195412 +pos=<96362159,-16937367,44268953>, r=77175042 +pos=<72716722,26825213,32992189>, r=50018520 +pos=<107118512,10041966,28544776>, r=76676065 +pos=<94854731,19887353,54938259>, r=60791043 +pos=<45411745,56433750,41561093>, r=53674723 +pos=<85104835,-3376398,43539720>, r=53085816 +pos=<21525897,18004714,26910887>, r=53781694 +pos=<87273082,22511350,8923463>, r=84329770 +pos=<54466633,37133728,12562615>, r=62506494 +pos=<72583180,42795470,26596683>, r=72250701 +pos=<79210200,-10583508,49134706>, r=54714968 +pos=<65893085,31063517,8290298>, r=72135052 +pos=<89301607,21323330,43135075>, r=50958735 +pos=<80294388,46054750,29047457>, r=80770576 +pos=<58415299,31113892,14444133>, r=58554143 +pos=<114093045,14587868,17129555>, r=95020151 +pos=<52603343,57530045,60523075>, r=61767195 +pos=<86154314,45339205,32435303>, r=82527169 +pos=<80469421,17516916,-9796402>, r=91251494 +pos=<73647532,15891462,-4083176>, r=77090924 +pos=<77816161,5841211,75469422>, r=63230842 +pos=<92286265,-3250083,52480511>, r=63803125 +pos=<114337437,21410963,24298078>, r=94919058 +pos=<61250631,22128606,86819244>, r=61309196 +pos=<55008425,73304267,65589057>, r=85012720 +pos=<91469553,10726208,7589166>, r=81298489 +pos=<53613729,22131067,60372585>, r=50600487 +pos=<69729507,25197598,9359821>, r=69036551 +pos=<98126273,13610904,-1803454>, r=97009369 +pos=<57752575,67359913,74147914>, r=90371199 +pos=<56572655,41140026,9119875>, r=72061990 +pos=<235573853,15940681,25618381>, r=66013864 +pos=<69517360,46830354,26789807>, r=73026639 +pos=<52821244,38251876,18033636>, r=56508684 +pos=<78384192,20406467,-9860849>, r=92120257 +pos=<95192781,22237846,42737425>, r=58161987 +pos=<101506148,23633287,43088246>, r=65520547 +pos=<99532103,35149229,34197016>, r=83953045 +pos=<89753970,29096815,54069701>, r=64031312 +pos=<57921252,55363160,35803100>, r=60950143 +pos=<87996121,49077993,44990305>, r=75552664 +pos=<119351019,37878806,50145259>, r=98485937 +pos=<63289151,62456996,11484417>, r=97730502 +pos=<124294684,17155940,41138755>, r=83780602 +pos=<92946232,15325979,36051543>, r=55689572 +pos=<62984214,38794770,26511399>, r=58736314 +pos=<58993040,18175513,90105147>, r=58384414 +pos=<65432944,45082631,39795478>, r=54188929 +pos=<120487958,4744614,41472294>, r=82415426 +pos=<56681505,-37409368,59775019>, r=69652499 +pos=<71549434,16013395,44884207>, r=83118699 +pos=<90591593,41668508,36479769>, r=79249262 +pos=<41590873,27833796,16487174>, r=53970036 +pos=<87293640,-3963069,60734738>, r=67778096 +pos=<105055384,-27934458,45075630>, r=96058551 +pos=<132640024,15373125,40124598>, r=91357344 +pos=<7684657,17864546,43413828>, r=50979871 +pos=<62058682,16424591,41810626>, r=95613266 +pos=<72915497,-18905763,80639176>, r=88246733 +pos=<-13441558,16681914,71160743>, r=93140018 +pos=<124820194,27159689,42877912>, r=92570835 +pos=<40487601,-8915142,20477267>, r=56839814 +pos=<86389449,-21090847,50938871>, r=74205474 +pos=<37015113,-3295525,19983721>, r=55186054 +pos=<60207127,-27168092,33825428>, r=61694136 +pos=<62247437,-2518738,22163497>, r=50747062 +pos=<89034518,30752468,12608525>, r=90647201 +pos=<43393427,-10882732,11965118>, r=64413573 +pos=<58919962,37018946,15188893>, r=64218777 +pos=<34315735,20954623,-1918295>, r=72771256 +pos=<33854038,-10366773,25650372>, r=59751699 +pos=<66912162,51141869,43377247>, r=58145571 +pos=<55524611,-6081568,76722209>, r=54114901 +pos=<71854691,37412153,42165490>, r=50570235 +pos=<85766984,26211515,38770849>, r=56676399 +pos=<94120503,22477559,34905335>, r=65161529 +pos=<103317059,21136979,37725048>, r=70197938 +pos=<57439678,-47054692,19967742>, r=92670962 +pos=<72101158,38595705,28845493>, r=65320131 +pos=<107687401,10881248,58999891>, r=71592480 +pos=<74970023,-37388530,40321165>, r=80181765 +pos=<76937770,32922538,34578813>, r=58750534 +pos=<-135,22450414,41506326>, r=65157970 +pos=<70322286,-22683623,3264099>, r=97886101 +pos=<99263374,18831130,38125744>, r=63437498 +pos=<56366494,-14909150,64500580>, r=51562512 +pos=<70292590,37815373,20804681>, r=70772053 +pos=<118558684,7603904,40863240>, r=78235875 +pos=<118483811,18972897,22651590>, r=98273928 +pos=<77888761,-41393874,41134729>, r=86292281 +pos=<75856913,38386207,34391475>, r=63320381 +pos=<111097751,41676916,43866326>, r=92377109 +pos=<113525811,21705104,49217334>, r=75558961 +pos=<98524230,28556190,26320429>, r=84228926 +pos=<89483526,21255654,11940210>, r=82267712 +pos=<53772085,28397224,-3238650>, r=68876943 +pos=<92137248,25639372,2482103>, r=98763245 +pos=<61494572,49095318,32811929>, r=61246709 +pos=<57770023,21599053,48182330>, r=77639521 +pos=<119675752,24284057,35284924>, r=92143788 +pos=<58681802,43668449,77102465>, r=70563510 +pos=<98017692,14039116,23795265>, r=71730294 +pos=<213257001,10867144,3779072>, r=94161786 +pos=<93227678,29855563,37217154>, r=69334966 +pos=<127425092,15698764,47857303>, r=82091988 +pos=<110422808,39015111,42731450>, r=90175355 +pos=<106497764,17603881,43374791>, r=64195712 +pos=<78169274,40515146,27573779>, r=74579476 +pos=<75492274,43420252,41313224>, r=61068069 +pos=<64328974,26568685,44223964>, r=80774458 +pos=<138574944,-80338904,85301139>, r=58360297 +pos=<71467721,4500701,40814781>, r=77313843 +pos=<105999567,28148425,43906497>, r=73710362 +pos=<70146123,62830834,34228040>, r=82217661 +pos=<76460859,25162945,17081921>, r=68010625 +pos=<119236573,21462695,42682863>, r=81485730 +pos=<66241763,26976163,447593>, r=76239161 +pos=<52281608,24543671,6050441>, r=54244018 +pos=<130895902,21414307,44517737>, r=91261369 +pos=<60567154,46052480,77520572>, r=75250910 +pos=<87694070,36970707,62972440>, r=78747980 +pos=<60999244,47043083,3121906>, r=88389160 +pos=<75384477,27462431,30765826>, r=55549847 +pos=<70844659,33521267,30884677>, r=56950147 +pos=<87380557,55194883,36049751>, r=89994563 +pos=<59864202,38797380,445045>, r=81685634 +pos=<97564520,8335495,43757107>, r=53616464 +pos=<100325183,15212463,31958848>, r=67047628 +pos=<70484296,19884994,68494837>, r=49974862 +pos=<75804074,-13544681,56299817>, r=61435021 +pos=<67186249,39311940,100056825>, r=97665841 +pos=<120207954,15969093,44402280>, r=75243565 +pos=<111429965,26134179,23103388>, r=97929534 +pos=<61409153,74846698,40635193>, r=79089707 +pos=<46549084,45864667,29916338>, r=53613015 +pos=<12205713,7404653,37276327>, r=52002675 +pos=<56779380,28558304,86834950>, r=63283378 +pos=<100804815,41519480,34658537>, r=91134770 +pos=<73796757,20838064,9264842>, r=68838749 +pos=<92013855,27536295,9085502>, r=93933422 +pos=<86701143,31220777,21531909>, r=79859390 +pos=<29829857,62161831,41570971>, r=74974887 +pos=<120888627,17198766,57268851>, r=86467204 +pos=<53728511,-63527412,41436715>, r=83963502 +pos=<55653284,41918087,45120037>, r=53620157 +pos=<94569373,18238003,37181462>, r=59094666 +pos=<9107247,15732527,89153350>, r=87634399 +pos=<132174699,16065282,43059662>, r=88649254 +pos=<97614639,13671176,44637516>, r=50117284 +pos=<53430300,42800416,14169866>, r=65529586 +pos=<91472285,10966750,9034842>, r=79615065 +pos=<63652062,39175236,26155480>, r=60140745 +pos=<61436871,26833166,57322562>, r=68700938 +pos=<-12804865,13869842,47787040>, r=66317691 +pos=<67474973,15717424,-28158099>, r=94819300 +pos=<108144462,14004921,44962500>, r=60655643 +pos=<85435963,136314174,4763652>, r=68966791 +pos=<71269973,58702436,28793178>, r=84647970 +pos=<82808554,54864698,32375067>, r=88766943 +pos=<13726235,24995443,32147016>, r=63336014 +pos=<9724226,16385886,32649030>, r=58226463 +pos=<76533938,16631647,24319164>, r=52315179 +pos=<10361335,29989315,34903118>, r=68938820 +pos=<86922809,34362873,20641054>, r=84113380 +pos=<84609145,14503042,14118219>, r=68462976 +pos=<85901960,24454051,5916945>, r=87907835 +pos=<911749,17934644,29100126>, r=72136528 +pos=<71799943,48372530,26822436>, r=76818808 +pos=<90762541,33905004,42208335>, r=65928007 +pos=<127683674,27814562,42967719>, r=95999250 +pos=<61313411,44483874,26236865>, r=63029196 +pos=<82330670,43531579,29695152>, r=79635893 +pos=<84579277,3344500,37133665>, r=52245460 +pos=<89786027,-28064110,34422863>, r=91571585 +pos=<3448232,15214632,40908247>, r=55071912 +pos=<104634977,28425459,43277287>, r=73252117 +pos=<70533047,-32864231,43259769>, r=68281805 +pos=<83699735,15735868,32177616>, r=50726988 +pos=<105613457,28457982,40209085>, r=77331663 +pos=<73103580,39214597,42129380>, r=53657636 +pos=<15768633,27388784,305600>, r=95528469 +pos=<109831837,22346920,61651659>, r=84941153 +pos=<94418576,32875691,21304836>, r=89458192 +pos=<117396279,8643842,38882961>, r=78013838 +pos=<52521139,-42950879,9198973>, r=94417491 +pos=<88397618,35596798,47360540>, r=62465729 +pos=<66556165,27984856,9515247>, r=68494516 +pos=<54360652,27637245,-3705048>, r=69171674 +pos=<18944405,1236255,18797842>, r=69910853 +pos=<100883817,16929767,36786240>, r=64496150 +pos=<101971278,24896866,54875502>, r=72854426 +pos=<83080823,39850389,55116317>, r=69158326 +pos=<103243332,1422355,10857245>, r=99108358 +pos=<58559031,17364061,47425177>, r=82724074 +pos=<74108879,45799658,29966206>, r=73411059 +pos=<91722287,43329270,61640166>, r=87802426 +pos=<91303909,23651688,41733770>, r=56690701 +pos=<88627675,41454426,20844061>, r=92707019 +pos=<62840128,-10795446,27132359>, r=54647662 +pos=<103982205,41008993,41600845>, r=86859094 +pos=<80994329,5336525,21671996>, r=62130685 +pos=<64436541,50190520,44675991>, r=53419818 +pos=<190700012,48316879,2802685>, r=50646355 +pos=<62184018,-1691939,4489882>, r=67530564 +pos=<17225645,66052129,36746642>, r=96293639 +pos=<79193345,18905429,29535408>, r=52032101 +pos=<97648165,40693585,40125792>, r=81684876 +pos=<38596926,66817136,25490271>, r=86943925 +pos=<120551410,21357664,27859946>, r=97517872 +pos=<107730705,23155425,59326645>, r=81323515 +pos=<105730922,-2299762,28418998>, r=87755985 +pos=<83686905,28545287,5584198>, r=90116739 +pos=<103414363,19478473,71850672>, r=85854259 +pos=<103691008,29370839,34985143>, r=81545804 +pos=<81766841,11296717,-2237476>, r=80852030 +pos=<-19405787,25333530,38441506>, r=90511676 +pos=<99093499,14689938,43716706>, r=53535701 +pos=<65566422,63506251,25685596>, r=86855810 +pos=<136558340,17399297,49582576>, r=94650941 +pos=<140438663,13429841,50613368>, r=95592585 +pos=<15051990,-13383092,43535355>, r=63685047 +pos=<-6219770,17031316,44892543>, r=62572362 +pos=<113564260,29753040,39081766>, r=87704264 +pos=<63040268,52279046,44162031>, r=54626016 +pos=<20004753,-24677056,57108450>, r=78312214 +pos=<85306823,30801712,86008733>, r=93227997 +pos=<25584336,14063310,90005945>, r=70340635 +pos=<45426883,72261970,41143493>, r=69905719 +pos=<4794220,21673464,9230418>, r=91863304 +pos=<46157156,58746273,27498914>, r=69303948 +pos=<99055616,16094738,41556751>, r=57062456 +pos=<57588158,33167083,92930972>, r=74797010 +pos=<99570220,-7434363,19910990>, r=95237922 +pos=<110603460,21573150,37417271>, r=78228067 +pos=<68671252,24993285,16408573>, r=60724735 +pos=<5688868,413683,26341727>, r=76445164 +pos=<94815334,18430291,94814783>, r=99171363 +pos=<92032029,-12214020,29307247>, r=83083470 +pos=<65981521,33060712,64274708>, r=54427643 +pos=<55567401,21272312,44320104>, r=64166359 +pos=<96373096,23158975,21847210>, r=81153643 +pos=<65372230,46312467,48484385>, r=51279804 +pos=<32350863,5623030,19309307>, r=51606106 +pos=<106411168,47975723,43128386>, r=94727263 +pos=<100826113,13564812,2353420>, r=95506255 +pos=<6378825,3037779,40508607>, r=58964428 +pos=<74643818,8131608,89255598>, r=71554088 +pos=<109793466,16831822,41837189>, r=68256842 +pos=<76361642,51152233,24568522>, r=86414089 +pos=<74580544,45041414,49763711>, r=60496592 +pos=<100869189,47521352,34384180>, r=97475258 +pos=<124019636,-98570919,64085932>, r=65508178 +pos=<62584689,26341862,18621669>, r=53773611 +pos=<98126572,13746651,1219878>, r=94122341 +pos=<83129609,17996392,68308405>, r=60545294 +pos=<76315160,23793010,86194268>, r=77413346 +pos=<83470558,3697222,30631783>, r=57285905 +pos=<91424109,54502627,41133381>, r=88262109 +pos=<93524589,38230805,19040648>, r=96183478 +pos=<65124071,18705377,49975736>, r=82962793 +pos=<91260215,24744195,16300725>, r=83172469 +pos=<60677870,50957812,53815044>, r=56561442 +pos=<71591827,3867947,68211622>, r=51721761 +pos=<59359524,58714008,26826036>, r=74716285 +pos=<100630152,33988338,19951780>, r=98135835 +pos=<37184102,71458584,42928283>, r=75559984 +pos=<68250482,17778641,49991787>, r=90125295 +pos=<104287291,44148413,44128712>, r=87775752 +pos=<39876473,16839503,-7530856>, r=68708254 +pos=<102713728,23931036,24543545>, r=85569998 +pos=<73168357,46751267,32442956>, r=70945437 +pos=<41949878,156504068,-18954149>, r=64756163 +pos=<102930204,35343248,37104041>, r=84638379 +pos=<62480158,37333867,21753855>, r=61529451 +pos=<43894718,43692479,63807540>, r=55461021 +pos=<137734844,21573597,43989106>, r=98788073 +pos=<63730722,57074855,43620327>, r=60654019 +pos=<83015911,24807864,3735239>, r=87557358 +pos=<69634519,40706124,38411287>, r=55398196 +pos=<52562114,27785684,-15676002>, r=79492557 +pos=<20520103,15854086,26002730>, r=53545185 +pos=<87434870,18437719,38414706>, r=50926615 +pos=<57755577,16647886,-28634221>, r=86506431 +pos=<43133634,48934212,37068935>, r=52945543 +pos=<57033158,78392283,59521728>, r=86057939 +pos=<102991185,29588343,42694512>, r=73353901 +pos=<108102397,29068005,27666063>, r=92973074 +pos=<9348572,17282316,33605027>, r=58542486 +pos=<143592360,15779409,44632933>, r=98207640 +pos=<-1647028,43767597,39571986>, r=90056565 +pos=<60526569,46081547,31524058>, r=58552839 +pos=<82935099,18040707,31699777>, r=52744784 +pos=<48323466,13417331,13716841>, r=72430650 +pos=<45773594,27297986,14975779>, r=50762360 +pos=<24097804,53090148,29390826>, r=83815291 +pos=<25005107,11325324,44788022>, r=68812043 +pos=<105404305,16729309,36466602>, r=69135756 +pos=<74634700,28685680,-1644353>, r=88433471 +pos=<27048089,46671968,29808821>, r=74028909 +pos=<58330408,114784165,-56072901>, r=69651104 +pos=<98670748,16040227,17339727>, r=80840147 +pos=<58048812,36006113,83397014>, r=68562891 +pos=<74014047,45988260,35623744>, r=67847541 +pos=<71568949,-13314586,37419374>, r=55608560 +pos=<59375646,24636541,9089410>, r=58391622 +pos=<138086403,19876935,50066719>, r=99140816 +pos=<98023645,14943492,16667203>, r=79768666 +pos=<52491721,59202118,28220497>, r=66942282 +pos=<90777106,57123923,37312202>, r=94057562 +pos=<113219705,23287968,43704790>, r=76271626 +pos=<66618416,48429695,8543343>, r=89973513 +pos=<-10351135,33197516,62671553>, r=98076092 +pos=<53630033,20687772,43709526>, r=54032535 +pos=<64859508,44595359,41296301>, r=51627349 +pos=<78205322,31496284,13487017>, r=79683666 +pos=<104655644,14589094,27637230>, r=75076741 +pos=<77541983,17024291,96730063>, r=82407123 +pos=<46216339,-21583971,66314537>, r=58213444 +pos=<83275281,15995716,15709165>, r=67030735 +pos=<55595202,15673921,27769253>, r=63393522 +pos=<98681204,24215772,37076499>, r=69289270 +pos=<75136995,-9362540,52474867>, r=52760677 +pos=<63600285,57212426,11963503>, r=92318114 +pos=<105866093,-405007,35224527>, r=79190897 +pos=<29698311,14979861,13235314>, r=56259978 +pos=<110328170,38335241,52657644>, r=92431876 +pos=<88542421,-870088,13207367>, r=84349456 +pos=<74640267,22206239,14645795>, r=65669532 +pos=<79065600,16087561,18528157>, r=60093859 +pos=<111823392,19903352,23089223>, r=92106547 +pos=<98366966,20052988,49891348>, r=59422141 +pos=<29682182,31506604,34545446>, r=51492791 +pos=<120848541,16730806,44774435>, r=76273795 +pos=<57458216,50046962,30808309>, r=60165921 +pos=<107663575,36525510,35923096>, r=91734717 +pos=<64195559,32116535,77982552>, r=65405350 +pos=<83512336,18917361,30750618>, r=55147891 +pos=<80721760,40690424,7152397>, r=97728592 +pos=<92294258,14234030,20416605>, r=69580495 +pos=<68073349,64458816,37581438>, r=78419487 +pos=<85524993,37438019,25046423>, r=81385663 +pos=<86541195,24280626,41918996>, r=52371589 +pos=<-13645389,15473382,22641566>, r=90690964 +pos=<44366724,100351984,42967204>, r=97231920 +pos=<86060439,17194021,-3770824>, r=90494079 +pos=<30049658,-5175494,25937638>, r=58077580 +pos=<107047197,22562690,44858175>, r=68220453 +pos=<127530824,27391996,52516364>, r=98550161 +pos=<64602574,3500377,-7797016>, r=77043638 +pos=<60270940,19412849,41872685>, r=88511219 +pos=<155526325,48371118,-26973138>, r=85591169 +pos=<107697033,52594463,-59041716>, r=74771672 +pos=<52298403,27693100,-30556065>, r=94016699 +pos=<114608699,14112690,44347121>, r=67843100 +pos=<72416922,57138051,19381835>, r=93641875 +pos=<95470538,-19749813,59828631>, r=90835630 +pos=<64854541,45323496,-4318783>, r=97965570 +pos=<114336015,10526848,43407780>, r=68546129 +pos=<44846695,34904424,38850487>, r=95051622 +pos=<91656904,16345566,39603921>, r=51867354 +pos=<78594244,43166462,82913458>, r=95785616 +pos=<123125125,9804601,45069352>, r=76395474 +pos=<107657632,23343797,44704438>, r=69765825 +pos=<110581427,19616264,47348915>, r=68657336 +pos=<69661168,31877975,33420581>, r=51587392 +pos=<94610218,13960801,64886899>, r=64568692 +pos=<69308901,57655769,38379289>, r=72054167 +pos=<135755923,10617817,38172368>, r=95110029 +pos=<86320905,59403445,35250752>, r=93942475 +pos=<118396084,30078667,41839960>, r=90103776 +pos=<82277876,17504638,28419641>, r=54831707 +pos=<113851054,24701483,37906662>, r=84114888 +pos=<105310453,19737919,38025470>, r=70491908 +pos=<130611957,7501593,41030202>, r=90224528 +pos=<65033300,78643636,50422027>, r=85209865 +pos=<33138251,17525027,37435621>, r=74580514 +pos=<96100212,30444455,25703008>, r=84310420 +pos=<27145406,44942359,36724008>, r=65286818 +pos=<65649299,44984252,27469621>, r=66633046 +pos=<64002938,67553935,75525638>, r=98193246 +pos=<93514191,16501448,43454650>, r=50029750 +pos=<84850566,3822237,32273082>, r=56899535 +pos=<79295673,23091753,4035821>, r=81820737 +pos=<113842735,15863962,49866858>, r=70684260 +pos=<62979159,19236013,11046588>, r=54637318 +pos=<70378058,38120569,23398679>, r=68568739 +pos=<77376105,57342410,20346141>, r=97841172 +pos=<37868298,22228217,-12332506>, r=80906394 +pos=<68207397,60961438,30142085>, r=82495737 +pos=<69858320,18729014,5445097>, r=66611048 +pos=<9116764,10344026,53693553>, r=50764356 +pos=<39005253,55520872,36722372>, r=64007061 +pos=<17794858,-6628512,7640246>, r=90083051 +pos=<85740536,26507750,51400594>, r=54759599 +pos=<84208747,35340884,25583462>, r=77434911 +pos=<87271504,19943739,20752408>, r=69931564 +pos=<96088602,14281014,48787654>, r=50268026 +pos=<27511816,40332464,6060608>, r=90973833 +pos=<65462523,-36697315,20913509>, r=89390698 +pos=<88573282,6738266,20779889>, r=69199413 +pos=<59865925,39227558,25266094>, r=57296238 +pos=<81227330,33431916,56973852>, r=62743804 +pos=<68366501,16547559,14647200>, r=53735619 +pos=<54230681,33414850,76455668>, r=55212004 +pos=<59541777,14580425,49151658>, r=72625643 +pos=<68098093,55194464,33122908>, r=73638498 +pos=<10118173,26785894,38943474>, r=61938305 +pos=<23416973,8660001,25767066>, r=51045270 +pos=<22184672,44730909,11787630>, r=94972351 +pos=<23839890,31017358,16049191>, r=75342069 +pos=<81054139,20266304,13433299>, r=71355888 +pos=<71626734,38408998,41533069>, r=51971530 +pos=<89478444,32502556,38338114>, r=67111625 +pos=<76389485,35414383,59701778>, r=62616358 +pos=<91422364,30853471,14672017>, r=91072657 +pos=<97715651,3633649,41305952>, r=60920935 +pos=<98302426,566943,44455286>, r=61424508 +pos=<87972808,16057009,74031530>, r=69172050 +pos=<104315590,30205049,42996111>, r=74993895 +pos=<7843002,28260225,57714932>, r=69987942 +pos=<70271568,42229743,51449522>, r=55061712 +pos=<97481885,18734492,35228517>, r=64456781 +pos=<93841182,-2752730,34858124>, r=69880597 +pos=<73292477,21940254,19166892>, r=59534575 +pos=<45448246,27863328,-10504487>, r=77133658 +pos=<21056077,17443631,-17767603>, r=98368965 +pos=<69249061,13430750,35948045>, r=58685625 +pos=<82363267,66412107,47639253>, r=87525334 +pos=<103724932,17569482,50836002>, r=63241196 +pos=<94743752,13539919,38313097>, r=53439563 +pos=<-1208391,41560402,41887717>, r=85094985 +pos=<2242162,19855988,37643999>, r=64183571 +pos=<108529318,34126090,39249978>, r=86874288 +pos=<104263315,20950911,30967568>, r=77715409 +pos=<101782231,41882974,39241307>, r=87892742 +pos=<88948941,21893456,20971406>, r=73339767 +pos=<97674914,9295684,57468225>, r=61633779 +pos=<52033323,19539936,90961981>, r=53645982 +pos=<72012599,47549588,36801296>, r=66229633 +pos=<85911193,46406475,36087876>, r=79698630 +pos=<83201681,67905359,49672601>, r=91890385 +pos=<110140280,17764489,35359837>, r=76013827 +pos=<76000089,23518895,20166406>, r=62821306 +pos=<88784014,23131762,30867583>, r=64517040 +pos=<87103475,32997307,32991213>, r=70578365 +pos=<8313690,20263541,35282625>, r=60881058 +pos=<118506095,20495671,42504099>, r=79966396 +pos=<105828823,21653771,33583579>, r=77367788 +pos=<79882555,6386659,12248677>, r=69391612 +pos=<44065053,1171023,-2206058>, r=65859440 +pos=<93899687,16799293,34733156>, r=59434573 +pos=<76120150,68727389,29393654>, r=98922623 +pos=<24794676,-294963,22172063>, r=62217542 +pos=<105606508,-12698036,38804880>, r=87644065 +pos=<149023157,20079454,-58121104>, r=96595437 +pos=<15014094,20436607,34582765>, r=55053525 +pos=<75581653,14125008,72078023>, r=52895402 +pos=<78759177,24062440,70435398>, r=64368175 +pos=<88908302,13808547,27190095>, r=58995559 +pos=<135130974,20492550,42963912>, r=96129007 +pos=<111832572,16345757,41911698>, r=69735380 +pos=<92723116,44304319,29118289>, r=91377952 +pos=<-21612986,-435582,34358465>, r=96579424 +pos=<69914320,22186526,84117667>, r=67329280 +pos=<10825182,24223567,31977094>, r=65635711 +pos=<125021022,14253079,48761688>, r=79146635 +pos=<53787124,14030357,29451273>, r=68747561 +pos=<73603349,-18919546,77824411>, r=86133587 +pos=<8803856,3778601,39670106>, r=56636756 +pos=<131833249,19137425,47238926>, r=89320349 +pos=<127096722,16870418,47183249>, r=82261369 +pos=<65771237,15933994,-17945635>, r=83119767 +pos=<129800653,16549371,42816551>, r=87002357 +pos=<73012023,32203096,17286028>, r=71398123 +pos=<85331745,66634021,55698321>, r=98775020 +pos=<3975073,15434520,36729664>, r=58943957 +pos=<76744678,-19473941,28802127>, r=75560873 +pos=<97046282,27688293,33628334>, r=74574981 +pos=<78021809,21416712,105411342>, r=95960754 +pos=<70174100,47832147,29589031>, r=71885946 +pos=<53243173,16479574,16583706>, r=97191800 +pos=<62675854,41357258,61502222>, r=56646100 +pos=<10398405,30103521,51737049>, r=63297943 +pos=<62789936,37579126,31318087>, r=52519744 +pos=<80646022,50390362,29100737>, r=85404405 +pos=<75059823,-3397631,-5855714>, r=92457535 +pos=<-26876547,26071980,54067049>, r=98871293 +pos=<94348553,13560168,39860824>, r=51516814 +pos=<70355332,25236589,27287999>, r=51772658 +pos=<9984512,17339484,9801485>, r=81767309 +pos=<105552760,13377201,55083427>, r=65124092 +pos=<76047874,-6194276,38463922>, r=51922646 +pos=<56479243,18000824,50728186>, r=84528342 +pos=<71894991,47704103,84715882>, r=95425758 +pos=<9457595,64238772,43347552>, r=95647462 +pos=<69898271,71459737,42769342>, r=82057449 +pos=<64151267,26165333,73057428>, r=54484787 +pos=<66031500,48985903,70945515>, r=77073892 +pos=<62035457,4482782,-29392371>, r=95089803 +pos=<64624210,79720253,34723156>, r=93090040 +pos=<112152682,27907103,57932441>, r=89103100 +pos=<60750946,2586567,15050454>, r=51258468 +pos=<80634960,32640080,37031696>, r=59712112 +pos=<57808402,86153331,39423147>, r=88007500 +pos=<70818888,43398822,34489718>, r=63196720 +pos=<68090318,27430690,-10278716>, r=89268549 +pos=<87890312,17996875,33238638>, r=56117353 +pos=<44413922,31891701,44564394>, r=94607110 +pos=<-27692985,18387215,39538274>, r=90756009 +pos=<47066581,53965612,27711250>, r=63401540 +pos=<95719838,34436228,28489267>, r=85135992 +pos=<-12471275,14645614,45067839>, r=66262794 +pos=<60738379,16592356,33988421>, r=79884260 +pos=<96326119,5728018,42788895>, r=55953511 +pos=<83907152,-10700839,14372026>, r=88380290 +pos=<109423924,23037116,75736387>, r=99308127 +pos=<31578359,-27417543,32628087>, r=72100454 +pos=<78512642,39729876,37461103>, r=64250145 +pos=<96926110,32512942,26709703>, r=86198131 +pos=<136106094,24310044,45004652>, r=98880595 +pos=<101078372,48784683,41810964>, r=91520964 +pos=<86206880,-22092154,19953965>, r=96489535 +pos=<81427199,30406859,38124910>, r=57177955 +pos=<123680256,20349363,42988596>, r=84509815 +pos=<11994475,31211035,44112943>, r=59317362 +pos=<69541980,42411019,28060638>, r=67361093 +pos=<18018824,19545861,33105306>, r=52635496 +pos=<69092489,16558452,41126433>, r=51187189 +pos=<65063790,-16268688,24495629>, r=64981137 +pos=<97448057,34132770,36427044>, r=78622515 +pos=<94859517,37403832,66435426>, r=89809493 +pos=<88595890,29830949,57521005>, r=67058554 +pos=<76972562,25538240,22837916>, r=63141778 +pos=<108214600,34601528,61118998>, r=95045880 +pos=<51848130,38004319,12700821>, r=60620456 +pos=<70151686,46463009,23084904>, r=76998527 +pos=<1479860,27508266,35045530>, r=75196637 +pos=<71533662,5246549,-15619408>, r=90050932 +pos=<61585126,-21429698,25366413>, r=65792791 +pos=<44250844,48388098,23828196>, r=64523005 +pos=<70268621,15863388,-29825644>, r=99426397 +pos=<72944088,62212490,44214235>, r=74411135 +pos=<65205412,6844511,-9872084>, r=76377320 +pos=<98378311,21213552,31447950>, r=71612707 +pos=<86532715,21669978,35142455>, r=56529076 +pos=<59513198,75710409,22364255>, r=96328110 +pos=<108573090,15275777,11967972>, r=95349627 +pos=<76451088,17816660,-2830425>, r=80567393 +pos=<-20979332,23290461,32130450>, r=96353089 +pos=<167472890,28321420,-28628457>, r=51800698 +pos=<126844291,20559148,41572491>, r=89299685 +pos=<104381467,-15359,49606197>, r=69789997 +pos=<72215311,42128830,30405803>, r=67407361 +pos=<60921916,21482471,38495006>, r=97223018 +pos=<97413729,17645063,41785452>, r=56742069 +pos=<41794614,59529953,35967787>, r=65981295 +pos=<55112593,-19101227,-12478192>, r=94836390 +pos=<53763415,-17694738,20745956>, r=58856661 +pos=<97433025,20709014,44378903>, r=57231982 +pos=<54833398,70844932,42561701>, r=66585419 +pos=<6735877,17243311,72860646>, r=75223926 +pos=<65035825,15796737,55942657>, r=95875884 +pos=<58631744,37720962,67416481>, r=54879925 +pos=<76548353,-4436543,59824784>, r=56596078 +pos=<29902114,75401238,36162686>, r=93550277 +pos=<4306799,19057972,55580414>, r=62187302 +pos=<77788277,-36286588,69739194>, r=99600371 +pos=<62069812,21846020,39048668>, r=98895350 +pos=<55789655,-50662209,28539717>, r=86056440 +pos=<57852930,-6240314,-21507089>, r=93744847 +pos=<85853628,22373244,70020215>, r=69357814 +pos=<68558182,36883167,38469454>, r=50440630 +pos=<91844168,13857117,36011460>, r=53158553 +pos=<-79773251,-16608784,-7261838>, r=64379316 +pos=<53851737,16320556,107113329>, r=68396335 +pos=<96355811,39006972,42748737>, r=76082810 +pos=<61304521,13899542,51145101>, r=87293939 +pos=<-33027734,16129088,43484391>, r=89886343 +pos=<62891864,16852512,-4456638>, r=67669834 +pos=<-31728430,13454094,47664051>, r=84702348 +pos=<66323108,80722929,41554146>, r=88960737 +pos=<131483327,8478771,44387297>, r=86761808 +pos=<65463135,27516385,19755668>, r=56692600 +pos=<68836614,47802794,34075021>, r=66033116 +pos=<93087880,20601381,66940941>, r=71741655 +pos=<58556801,44076131,2148137>, r=83953625 +pos=<53789613,2722281,69620824>, r=52267250 +pos=<56408739,62183585,42399134>, r=59661929 +pos=<139567001,16481920,42124245>, r=97393427 +pos=<109673569,13815521,40743013>, r=66215151 +pos=<71504105,-31521953,44529299>, r=66641049 +pos=<52458571,-4531791,33044861>, r=84331563 +pos=<60132097,49495123,25064768>, r=68031371 +pos=<89501692,28087472,42522993>, r=58534901 +pos=<113700013,2608326,35420298>, r=83815773 +pos=<59365679,19493223,11205910>, r=51121759 +pos=<115816190,17471804,19350278>, r=97406516 +pos=<117983710,15579957,34684898>, r=82347526 +pos=<61126255,89024443,36042155>, r=97577361 +pos=<17111127,24014433,40025508>, r=51091572 +pos=<88563757,36493034,38330072>, r=70195784 +pos=<61147214,-40216804,41755918>, r=67752808 +pos=<93351242,21718052,27420214>, r=71117815 +pos=<116029495,4752794,52987375>, r=80050433 +pos=<21660920,17548110,72499472>, r=60242607 +pos=<77160452,21499145,10721549>, r=71406806 +pos=<21942199,30246059,19421950>, r=73095654 +pos=<41187870,-45023108,49799775>, r=70166458 +pos=<130508106,13402664,39958143>, r=87421472 +pos=<56694305,7382384,37989881>, r=70266488 +pos=<83278137,30226252,44992838>, r=51980335 +pos=<33787468,39097305,30943051>, r=58580537 +pos=<83809192,56422250,32070922>, r=91629251 +pos=<96222566,22542322,14213451>, r=88020381 +pos=<58618515,86070796,48199210>, r=83999330 +pos=<-24204477,312836,49946178>, r=90369133 +pos=<52462043,36773575,-14970243>, r=87674762 +pos=<61723954,7397101,119681550>, r=89794798 +pos=<71499605,-3775574,83892822>, r=74954681 +pos=<58226285,-15532456,67609414>, r=57154435 +pos=<34600292,67684147,28580679>, r=88717009 +pos=<43999378,32581929,8344735>, r=64451559 +pos=<72886084,23772601,22866013>, r=57262263 +pos=<89258200,46124188,42357440>, r=76493762 +pos=<118913509,5203615,41666247>, r=80188160 +pos=<60103205,66334528,20303984>, r=89602518 +pos=<134318186,20453957,38718882>, r=99522026 +pos=<57873352,29888746,35872132>, r=73840137 +pos=<87126674,-1837528,75860646>, r=80611108 +pos=<9815166,29956489,55421777>, r=67418824 +pos=<53883155,35168736,-12789198>, r=85310001 +pos=<56631888,86291541,44066704>, r=82325568 +pos=<78754183,45036404,40773185>, r=66486134 +pos=<107354622,1812012,22006919>, r=91679989 +pos=<66319496,-19485922,28720517>, r=65229305 +pos=<-157274598,13380491,44536512>, r=89937328 +pos=<-15980994,11168062,26691731>, r=87010650 +pos=<74297174,13659419,18344770>, r=53080855 +pos=<95290737,55947500,52143083>, r=94492072 +pos=<83566796,27612717,86676968>, r=88967191 +pos=<54615003,-50090275,19394514>, r=93455280 +pos=<72475406,24159568,-10446912>, r=90551249 +pos=<124320846,20917953,34558971>, r=94148589 +pos=<59556870,22468387,61960875>, r=95835235 +pos=<85850498,15173335,31275408>, r=53217449 +pos=<97043794,31260129,28847756>, r=82925080 +pos=<-30806492,14288685,40811101>, r=88498239 +pos=<109287733,32084817,37834188>, r=87007245 +pos=<31905560,16815816,19202933>, r=49921070 +pos=<34019142,39948256,-2555641>, r=92698498 +pos=<60423258,7058633,56093742>, r=92372725 +pos=<89000117,-7433325,17215242>, r=87362491 +pos=<16101256,155411726,8054919>, r=70751286 +pos=<55704860,-14115747,-19026705>, r=96991783 +pos=<76111136,17678988,26494944>, r=50764086 +pos=<53996075,26826438,-20153399>, r=84444641 +pos=<92968133,15660890,38060165>, r=54037587 +pos=<91070503,16637689,1909834>, r=89267088 +pos=<54005791,14758605,23430167>, r=75715153 +pos=<97507260,34047237,31941753>, r=83081560 +pos=<2975754,14095254,41779614>, r=53554014 +pos=<120978834,16899315,49154133>, r=78143195 +pos=<85328494,14256843,-15259618>, r=98314431 +pos=<77488091,14434711,44013572>, r=80913116 +pos=<77937834,29827225,29893239>, r=61340581 +pos=<62003606,52335663,43593778>, r=54214235 +pos=<96942383,20841587,3023742>, r=98228956 +pos=<33569431,74871555,50770256>, r=83928098 +pos=<80642364,-9203025,29662289>, r=68327482 +pos=<71311380,33322959,86603336>, r=82348679 +pos=<91246638,34400631,64666269>, r=81424244 +pos=<62099892,-10515215,27347000>, r=53412475 +pos=<86486433,4770547,54282108>, r=51784461 +pos=<19952675,22271190,32383977>, r=54148390 +pos=<121311725,20148992,53827517>, r=86399193 +pos=<77348748,17811759,27529684>, r=51099587 +pos=<103756328,-1826372,64248899>, r=85618200 +pos=<90425490,37860898,35743279>, r=76011902 +pos=<31214024,59832039,37840529>, r=74991427 +pos=<31673713,39035689,31747578>, r=59828579 +pos=<98324243,50763490,55975205>, r=96173646 +pos=<96576351,31703521,43739565>, r=68009035 +pos=<-8224616,21505287,38900804>, r=75043015 +pos=<70215790,31414121,78075490>, r=70816266 +pos=<94624267,17311286,44243466>, r=51160854 +pos=<145315567,13539738,45057136>, r=97266900 +pos=<107424182,37921701,56052282>, r=92508941 +pos=<114460312,2827441,54027099>, r=81446368 +pos=<84896185,155524818,14117185>, r=65838022 +pos=<78348024,51197526,18625154>, r=94389194 +pos=<108428541,16263952,49423969>, r=65227366 +pos=<81803332,43810143,39593001>, r=69489218 +pos=<64193468,59796582,24457666>, r=83001229 +pos=<105935338,43426130,38951290>, r=93879023 +pos=<102525624,15797811,42481599>, r=59310728 +pos=<61070486,42324464,14285639>, r=72578708 +pos=<-3580448,34355560,67479433>, r=97271195 +pos=<27493234,74949936,37170967>, r=94499543 +pos=<95307147,-10563377,39956422>, r=74058438 +pos=<77046324,39054620,22348631>, r=77221054 +pos=<84407202,33709489,43001788>, r=58583751 +pos=<79109293,-17607209,43472660>, r=61388128 +pos=<65037457,17041091,9319590>, r=56227947 +pos=<109879935,23611904,27427552>, r=89533599 +pos=<92206989,21528011,44364581>, r=52839229 +pos=<131893694,26645912,44533231>, r=97475131 +pos=<57988955,16799006,42746894>, r=72660238 +pos=<55721147,14679631,55050327>, r=65360918 +pos=<56475053,157335785,-18064494>, r=71791529 +pos=<62549961,60037990,32925786>, r=73130893 +pos=<59962903,50696798,-3189506>, r=97318003 +pos=<93935257,42163544,40780776>, r=78786826 +pos=<16519652,46247773,44291354>, r=69650742 +pos=<55273762,41596698,102298194>, r=90279426 +pos=<68486368,26630184,20967249>, r=57618037 +pos=<52440594,97891439,41544256>, r=92256520 +pos=<126721971,997071,34169987>, r=99699325 +pos=<66438947,28090755,1663670>, r=76334792 +pos=<86306992,29933079,45076173>, r=54632631 +pos=<79796241,33650378,38339901>, r=58575585 +pos=<110000504,24827983,21364635>, r=96932811 +pos=<121739354,-11767031,44329657>, r=97321098 +pos=<10968572,16182916,34651449>, r=54776658 +pos=<113589071,386508,33179751>, r=88167154 +pos=<108550628,30531833,27071734>, r=95479473 +pos=<54912455,35642492,-488940>, r=74512627 +pos=<62280453,9998892,2377939>, r=58047920 +pos=<80853563,41988026,44416424>, r=61893957 +pos=<57293617,25033521,37489332>, r=74142419 +pos=<14309765,6830187,5838479>, r=81911035 +pos=<94541481,15222609,9714685>, r=83518148 +pos=<80841989,27169928,11949785>, r=79531149 +pos=<-362258,13463058,21353515>, r=76685573 +pos=<27437887,16132050,7254878>, r=65653233 +pos=<65301653,50795438,54919831>, r=62127770 +pos=<86068196,23496306,25134585>, r=67899074 +pos=<-4736408,31592571,39406124>, r=81136599 +pos=<84172874,5396808,88301162>, r=82863550 +pos=<69740725,28984190,31528539>, r=50665290 +pos=<83145817,15815890,24133349>, r=58297229 +pos=<69904981,13410730,42110977>, r=98542627 +pos=<538011,15281796,50838781>, r=57438310 +pos=<104063039,-12837030,37449187>, r=87595173 +pos=<55239793,17436269,41649368>, r=94175234 +pos=<83179547,-4381663,56585839>, r=59933413 +pos=<723975,16972924,41584616>, r=58878081 +pos=<147830225,5518323,-70521872>, r=78879176 +pos=<67973856,15136115,-8974036>, r=75552768 +pos=<53572576,32679591,2268600>, r=67452309 +pos=<57152954,-30733037,25713188>, r=70317114 +pos=<218528673,17733915,7607567>, r=65780865 +pos=<69958919,7920680,51038539>, r=97289674 +pos=<106026959,17030059,49792871>, r=63960693 +pos=<111780868,23816938,34089373>, r=84977162 +pos=<84201829,26521257,36652898>, r=57539065 +pos=<56777356,39515685,107963797>, r=95367869 +pos=<91129382,11164875,77043760>, r=72794591 +pos=<12418901,30720097,21118618>, r=81396347 +pos=<40328861,61655976,38790871>, r=66750088 +pos=<79052781,61013468,43118962>, r=80416016 +pos=<91602755,14213054,16347301>, r=72937328 +pos=<80961166,14181363,70025900>, r=56279155 +pos=<93876633,45195501,27764981>, r=94776149 +pos=<52340903,96232207,33718273>, r=98323607 +pos=<-14549796,16458043,51313341>, r=74176910 +pos=<88064162,17055593,28317909>, r=60270625 +pos=<93212354,48955840,64308486>, r=97587422 +pos=<53206420,17000872,-20024069>, r=73700273 +pos=<61052510,72394917,24220630>, r=92696140 +pos=<81687177,23834949,25335493>, r=63655364 +pos=<25106966,75185729,36676609>, r=97615982 +pos=<84068626,17255936,66666514>, r=59101990 +pos=<93588309,32275899,41533703>, r=67799240 +pos=<68583096,49916685,13027357>, r=88941396 +pos=<89717353,14816348,65449930>, r=61094665 +pos=<42239161,46819277,31154947>, r=57638911 +pos=<71410181,33633339,36023280>, r=52488978 +pos=<139724278,6862209,44421905>, r=96584453 +pos=<88615644,19615206,7053643>, r=84646144 +pos=<97097646,18833100,47802953>, r=54844475 +pos=<27441579,48278852,48445570>, r=61138646 +pos=<95037495,22702070,22907364>, r=78301552 +pos=<109029378,-13758958,37747166>, r=93185495 +pos=<70698540,33634311,59195734>, r=54639431 +pos=<87928019,22287380,32163447>, r=61520947 +pos=<-1034006,19421980,41991282>, r=62678624 +pos=<82611502,22158853,31969676>, r=56269416 +pos=<91857084,29722737,25533276>, r=79515360 +pos=<58649310,36506151,26295244>, r=52329029 +pos=<98762131,10275863,37582977>, r=59047674 +pos=<76108314,20510191,3556285>, r=76531089 +pos=<91558604,21916814,30253777>, r=66690373 +pos=<73269802,14315090,18597632>, r=52456065 +pos=<54579450,47828534,80012131>, r=73530839 +pos=<101039686,-32593259,48147878>, r=97567279 +pos=<66015384,68046604,62242035>, r=87414990 diff --git a/problems/day23.html b/problems/day23.html new file mode 100644 index 0000000..daea5d8 --- /dev/null +++ b/problems/day23.html @@ -0,0 +1,163 @@ + + + + +Day 23 - Advent of Code 2018 + + + + + + + +

Advent of Code

Neil Smith (AoC++) 46*

      /^2018$/

+ + + +
+

--- Day 23: Experimental Emergency Teleportation ---

Using your torch to search the darkness of the rocky cavern, you finally locate the man's friend: a small reindeer.

+

You're not sure how it got so far in this cave. It looks sick - too sick to walk - and too heavy for you to carry all the way back. Sleighs won't be invented for another 1500 years, of course.

+

The only option is experimental emergency teleportation.

+

You hit the "experimental emergency teleportation" button on the device and push I accept the risk on no fewer than 18 different warning messages. Immediately, the device deploys hundreds of tiny nanobots which fly around the cavern, apparently assembling themselves into a very specific formation. The device lists the X,Y,Z position (pos) for each nanobot as well as its signal radius (r) on its tiny screen (your puzzle input).

+

Each nanobot can transmit signals to any integer coordinate which is a distance away from it less than or equal to its signal radius (as measured by Manhattan distance). Coordinates a distance away of less than or equal to a nanobot's signal radius are said to be in range of that nanobot.

+

Before you start the teleportation process, you should determine which nanobot is the strongest (that is, which has the largest signal radius) and then, for that nanobot, the total number of nanobots that are in range of it, including itself.

+

For example, given the following nanobots:

+
pos=<0,0,0>, r=4
+pos=<1,0,0>, r=1
+pos=<4,0,0>, r=3
+pos=<0,2,0>, r=1
+pos=<0,5,0>, r=3
+pos=<0,0,3>, r=1
+pos=<1,1,1>, r=1
+pos=<1,1,2>, r=1
+pos=<1,3,1>, r=1
+
+

The strongest nanobot is the first one (position 0,0,0) because its signal radius, 4 is the largest. Using that nanobot's location and signal radius, the following nanobots are in or out of range:

+
    +
  • The nanobot at 0,0,0 is distance 0 away, and so it is in range.
    • +
  • The nanobot at 1,0,0 is distance 1 away, and so it is in range.
    • +
  • The nanobot at 4,0,0 is distance 4 away, and so it is in range.
    • +
  • The nanobot at 0,2,0 is distance 2 away, and so it is in range.
    • +
  • The nanobot at 0,5,0 is distance 5 away, and so it is not in range.
    • +
  • The nanobot at 0,0,3 is distance 3 away, and so it is in range.
    • +
  • The nanobot at 1,1,1 is distance 3 away, and so it is in range.
    • +
  • The nanobot at 1,1,2 is distance 4 away, and so it is in range.
    • +
  • The nanobot at 1,3,1 is distance 5 away, and so it is not in range.
    • +
+

In this example, in total, 7 nanobots are in range of the nanobot with the largest signal radius.

+

Find the nanobot with the largest signal radius. How many nanobots are in range of its signals?

+
+

Your puzzle answer was 510.

--- Part Two ---

Now, you just need to figure out where to position yourself so that you're actually teleported when the nanobots activate.

+

To increase the probability of success, you need to find the coordinate which puts you in range of the largest number of nanobots. If there are multiple, choose one closest to your position (0,0,0, measured by manhattan distance).

+

For example, given the following nanobot formation:

+
pos=<10,12,12>, r=2
+pos=<12,14,12>, r=2
+pos=<16,12,12>, r=4
+pos=<14,14,14>, r=6
+pos=<50,50,50>, r=200
+pos=<10,10,10>, r=5
+
+

Many coordinates are in range of some of the nanobots in this formation. However, only the coordinate 12,12,12 is in range of the most nanobots: it is in range of the first five, but is not in range of the nanobot at 10,10,10. (All other coordinates are in range of fewer than five nanobots.) This coordinate's distance from 0,0,0 is 36.

+

Find the coordinates that are in range of the largest number of nanobots. What is the shortest manhattan distance between any of those points and 0,0,0?

+
+

Your puzzle answer was 108889300.

Both parts of this puzzle are complete! They provide two gold stars: **

+

At this point, you should return to your Advent calendar and try another puzzle.

+

If you still want to see it, you can get your puzzle input.

+

You can also this puzzle.

+
+ + + + + + \ No newline at end of file diff --git a/src/advent23/advent23.hs b/src/advent23/advent23.hs new file mode 100644 index 0000000..9812cd4 --- /dev/null +++ b/src/advent23/advent23.hs @@ -0,0 +1,238 @@ +{-# LANGUAGE NegativeLiterals #-} +{-# LANGUAGE FlexibleContexts #-} +{-# LANGUAGE OverloadedStrings #-} +{-# LANGUAGE TypeFamilies #-} +{-# LANGUAGE BangPatterns #-} + +-- Box division approach taken from fizbin: +-- https://www.reddit.com/r/adventofcode/comments/a8s17l/2018_day_23_solutions/ecfmpy0/ + +import Debug.Trace + +-- import Prelude hiding ((++)) +import Data.Text (Text) +import qualified Data.Text as T +import qualified Data.Text.IO as TIO + +import Data.Void (Void) +import Text.Megaparsec hiding (State) +import Text.Megaparsec.Char +import qualified Text.Megaparsec.Char.Lexer as L +import qualified Control.Applicative as CA + +import qualified Data.Map.Strict as M +import Data.Map.Strict ((!)) + +import Data.List + +import Linear (V3(..), (^-^)) + +import qualified Data.PQueue.Max as P + + +type Coord = V3 Integer -- x, y, z +type BotSwarm = M.Map Coord Integer +-- type VertexCounts = M.Map Coord Integer +type Box = (Coord, Coord) +data LabelledBox = LabelledBox { _box :: Box + , _intersectCount :: Int + } deriving (Eq, Show) +-- instance Ord LabelledBox where +-- lb1 `compare` lb2 = if (_intersectCount lb1) /= (_intersectCount lb2) +-- then (_intersectCount lb1) `compare` (_intersectCount lb2) +-- else if (boxSize lb1) /= (boxSize lb2) +-- then (boxSize lb1) `compare` (boxSize lb2) +-- else (distanceFromOrigin lb1) `compare` (distanceFromOrigin lb2) +-- where boxSize lb = manhattan (fst $ _box lb) (snd $ _box lb) +-- distanceFromOrigin lb = min (distance $ fst $ _box lb) (distance $ snd $ _box lb) +instance Ord LabelledBox where + lb1 `compare` lb2 = if (_intersectCount lb1) /= (_intersectCount lb2) + then (_intersectCount lb1) `compare` (_intersectCount lb2) + else if (boxSize lb1) /= (boxSize lb2) + then (boxSize lb1) `compare` (boxSize lb2) + else (distanceFromOrigin $ _box lb1) `compare` (distanceFromOrigin $ _box lb2) + +boxSize lb = manhattan (fst $ _box lb) (snd $ _box lb) +distanceFromOrigin lb = boxDistanceFromPoint lb origin + +type BoxQueue = P.MaxQueue LabelledBox + + +origin :: Coord +origin = V3 0 0 0 + + +main :: IO () +main = do + text <- TIO.readFile "data/advent23.txt" + let bots = successfulParse text + let swarm = enSwarm bots + print $ part1 swarm + print $ part2 swarm + -- print (ip, instrs) + -- print $ zip [0..] instrs + -- print $ part1 ip instrs + -- print $ part2 ip instrs + + +part1 :: BotSwarm -> Int +part1 swarm = M.size inRangeBots + where centre = strongest swarm + range = swarm!centre + botInRange loc _ = (manhattan loc centre) <= range + inRangeBots = M.filterWithKey botInRange swarm + + +-- part2 swarm = ((distance $ snd best), best) +-- where vcs = vertexCounts vs swarm +-- vs = verticesOfSwarm swarm +-- best = targetVertex vcs + + + + +manhattan :: Coord -> Coord -> Integer +-- manhattan $ (V3 0 0 0) ^-^ (V3 1 3 1) +manhattan (V3 x y z) (V3 x' y' z') = (abs (x - x')) + (abs (y - y')) + (abs (z - z')) + +distance :: Coord -> Integer +distance = manhattan origin + +enSwarm :: [(Coord, Integer)] -> BotSwarm +enSwarm = foldl' (\s (c, r) -> M.insert c r s) M.empty + + +strongest :: BotSwarm -> Coord +strongest swarm = fst $ M.foldlWithKey' findStrongest pair0 swarm + where findStrongest (currentCoord, currentMax) coord range = + if range > currentMax + then (coord, range) + else (currentCoord, currentMax) + pair0 = M.findMin swarm + + +boxIntersectionCount :: Box -> BotSwarm -> Int +boxIntersectionCount box swarm = M.size $ M.filterWithKey (\b _ -> intersects box b swarm) swarm + +intersects :: Box -> Coord -> BotSwarm -> Bool +intersects box bot swarm = + d <= range + where d = boxDistanceFromPoint box bot + range = swarm!bot + + +boxDistanceFromPoint :: Box -> Coord -> Integer +boxDistanceFromPoint ((V3 l f t), (V3 r b u)) (V3 x y z) = d + + -- # returns whether box intersects bot + -- d = 0 + -- for i in (0, 1, 2): + -- boxlow, boxhigh = box[0][i], box[1][i] - 1 + -- d += abs(bot[i] - boxlow) + abs(bot[i] - boxhigh) + -- d -= boxhigh - boxlow + -- d //= 2 + -- return d <= bot[3] + + -- dmin = 0; + -- for( i = 0; i < 3; i++ ) { + -- if( C[i] < Bmin[i] ) dmin += SQR( C[i] - Bmin[i] ); else + -- if( C[i] > Bmax[i] ) dmin += SQR( C[i] - Bmax[i] ); + -- } + -- if( dmin <= r2 ) return TRUE; + + + where d = sum [ dist boxLow boxHigh coord + | (boxLow, boxHigh, coord) + <- [(l, r, x), (f, b, y), (t, u, z)] + ] + dist bl bh v = (if v <= bl then abs (v - bl) else 0) + + + (if v >= bh then abs (v - bh) else 0) + + +subBoxes :: Box -> [Box] +subBoxes ((V3 l f t), (V3 r b u)) = + [ ((V3 l f t ) , (V3 r' b' u')) + , ((V3 l f t'), (V3 r' b' u )) + , ((V3 l f' t ), (V3 r' b u')) + , ((V3 l f' t'), (V3 r' b u )) + , ((V3 l' f t ) , (V3 r b' u')) + , ((V3 l' f t'), (V3 r b' u )) + , ((V3 l' f' t ), (V3 r b u')) + , ((V3 l' f' t'), (V3 r b u )) + ] + where w = (r - l) `div` 2 + r' = l + w + b' = f + w + u' = t + w + l' = r' + 1 + f' = b' + 1 + t' = u' + 1 + + +unitBox :: Box -> Bool +unitBox ((V3 l f t), (V3 r b u)) = l == r && f == b && t == u + + +boundingBox swarm = ((V3 minX minY minZ), (V3 maxX maxY maxZ)) + where minX = minimum $ [ _x bot | bot <- M.keys swarm ] + minY = minimum $ [ _y bot | bot <- M.keys swarm ] + minZ = minimum $ [ _z bot | bot <- M.keys swarm ] + maxX = maximum $ [ _x bot | bot <- M.keys swarm ] + maxY = maximum $ [ _y bot | bot <- M.keys swarm ] + maxZ = maximum $ [ _z bot | bot <- M.keys swarm ] + _x (V3 x _ _) = x + _y (V3 _ y _) = y + _z (V3 _ _ z) = z + + +part2 = distanceFromOrigin . bestUnitBox + +bestUnitBox :: BotSwarm -> Box +bestUnitBox swarm = findBestBox swarm initialQueue + where initialBox = boundingBox swarm + initialQueue = P.singleton $ enLabel swarm initialBox + +findBestBox :: BotSwarm -> BoxQueue -> Box +findBestBox swarm queue + | unitBox currentBox = currentBox + | otherwise = findBestBox swarm newQueue + where (currentLBox, queue') = P.deleteFindMax queue + currentBox = _box currentLBox + nextBoxes = subBoxes currentBox + nextLBoxes = map (enLabel swarm) nextBoxes + newQueue = foldl' (\ q b -> P.insert b q) queue' nextLBoxes + +enLabel :: BotSwarm -> Box -> LabelledBox +enLabel swarm box = LabelledBox { _box = box, _intersectCount = boxIntersectionCount box swarm} + + +type Parser = Parsec Void Text + +sc :: Parser () +sc = L.space (skipSome spaceChar) CA.empty CA.empty + +lexeme = L.lexeme sc +integer = lexeme L.decimal +signedInteger = L.signed sc integer +symb = L.symbol sc +comma = symb "," +posOpenP = symb "pos=<" +posCloseP = symb ">" +radiusStartP = symb "r=" + +swarmP = many nanobotP +nanobotP = (,) <$> posP <* comma <*> radiusP + +posP = posify <$> (posOpenP `between` posCloseP) coordP + where posify (a, b, c) = V3 a b c +coordP = (,,) <$> signedInteger <* comma <*> signedInteger <* comma <*> signedInteger +radiusP = radiusStartP *> signedInteger + + +successfulParse :: Text -> [(Coord, Integer)] +-- successfulParse _ = [] +successfulParse input = + case parse swarmP "input" input of + Left _error -> [] -- TIO.putStr $ T.pack $ parseErrorPretty err + Right swarm -> swarm -- 2.34.1