From 4bfd90a11af7c1e597c4e30bbd6d7e1818911562 Mon Sep 17 00:00:00 2001 From: jacopograndi Date: Mon, 10 Jan 2022 14:58:41 +0100 Subject: day15 --- 2021/day15/day15 | Bin 0 -> 114728 bytes 2021/day15/day15.cpp | 122 ++++++++++++++++++++++++++++++++++++++++++ 2021/day15/day15_input.txt | 100 ++++++++++++++++++++++++++++++++++ 2021/day15/day15_input_ez.txt | 10 ++++ 2021/day15/day15_test.txt | 5 ++ 2021/day15/day15_test_2.txt | 6 +++ 2021/day15/day15_test_3.txt | 4 ++ 2021/day15/makefile | 2 + 8 files changed, 249 insertions(+) create mode 100755 2021/day15/day15 create mode 100644 2021/day15/day15.cpp create mode 100644 2021/day15/day15_input.txt create mode 100644 2021/day15/day15_input_ez.txt create mode 100644 2021/day15/day15_test.txt create mode 100644 2021/day15/day15_test_2.txt create mode 100644 2021/day15/day15_test_3.txt create mode 100644 2021/day15/makefile (limited to '2021') diff --git a/2021/day15/day15 b/2021/day15/day15 new file mode 100755 index 0000000..5694e3f Binary files /dev/null and b/2021/day15/day15 differ diff --git a/2021/day15/day15.cpp b/2021/day15/day15.cpp new file mode 100644 index 0000000..f829cd5 --- /dev/null +++ b/2021/day15/day15.cpp @@ -0,0 +1,122 @@ +#include +#include +#include +#include +#include +#include +#include +#include "../utils.h" + +class Grid { + public: Grid () { } + int xytoi (int x, int y) { return x+ y*sizex; } + int itox (int i) { return i % sizex; } + int itoy (int i) { return i / sizex; } + bool oob (int x, int y) { + if (x < 0 || x > sizex-1) return true; + if (y < 0 || y > sizey-1) return true; + return false; + } + + int sizex, sizey; + std::vector cells; + + std::vector fw (int i) { + int x = itox(i), y = itoy(i); + std::vector star; + for (int t=-1; t<2; t++) { + for (int s=-1; s<2; s++) { + if (abs(s)+abs(t) == 1 && !oob(x+s, y+t)) { + star.push_back(xytoi(x+s, y+t)); + } + } + } + return star; + } + + int astar (int istart, int iend) { + std::map cost; + std::map prev; + cost[iend] = cells[iend]; + prev[iend] = iend; + auto cmp = [&cost] (int a, int b) { return cost[a] > cost[b]; }; + std::priority_queue, decltype(cmp)> Q(cmp); + Q.push(iend); + + while (Q.size() > 0) { + int n = Q.top(); Q.pop(); + auto star = fw(n); + int min = cost[prev[n]]; + for (int j : star) { + if (prev.find(j) == prev.end()) { + prev[j] = n; + cost[j] = cost[prev[j]] + cells[j]; + Q.push(j); + } + if (min >= cost[j]) { + prev[n] = j; + cost[n] = cost[prev[n]] + cells[n]; + min = cost[j]; + } + } + } + + if (true) { + for (int y=0; y 9) k -= 9; + big.cells.push_back(k); + } + } + } + } + return big; +} + +int main (int argc, char *argv[]) { + std::string raw; + std::getline(std::ifstream(argv[1]), raw, '\0'); + std::vector lines; + split(lines, raw, "\n"); + + Grid grid; + grid.sizey = 0; + for (std::string line : lines) { + if (line.size() == 0) continue; + grid.sizex = 0; + for (char c : line) { + grid.cells.push_back(std::stoi(std::string { c })); + grid.sizex ++; + } + grid.sizey ++; + } + + if (argc > 2) grid = five(grid); + + int l = grid.astar(grid.xytoi(0, 0), grid.xytoi(grid.sizex-1, grid.sizey-1)); + std::cout << "min risk: " << l << std::endl; + + return 0; +} diff --git a/2021/day15/day15_input.txt b/2021/day15/day15_input.txt new file mode 100644 index 0000000..8a2175e --- /dev/null +++ b/2021/day15/day15_input.txt @@ -0,0 +1,100 @@ +2522414939711849132228579816748823728379124311418111161529639822623219297197656312386831265718721211 +7119125991574111336131978938112955121422183362398517132564814661292561181421134141499624511692694112 +3127235291311117732711221595212461287834821864268181236173834391241692536216841911355119911169521283 +1181155152189111774111156796369418892573474529449114243368393188187466226115613499124591912775811129 +4511586224241188433132151131912322433627252532818342691614969559425683161447111791121549111146484532 +5413831212391138911819213166957149213922161137291919117113531382416132121124858321148398497135261112 +3141189114547157882263926111828665483177711211394322187226895913495654276512911298585113827786152821 +8139154185512648535373192171842522111781272122639619926142743623114419711811419181134834173248346866 +6131817237181957336623411991444413536213224516221697817415389416311235139732243655118584442412599145 +1718527358218195924512318645311122933297111329286687374945374614773121499269961183811521727398185311 +3481151521221189311126811235832569921337354392175131599321326783387163848295333231182825314233581171 +5171429946536911171547532412699913195693631981517211295814192796223191999671726151521111228699694495 +5731624261487716916211124279184347912542257442518826222117821961594127731715739323835513111141439813 +1369513736556212936295111719858412198182886373247978725451813524111444118681111124821121862374272185 +3312732241492183466791771757118623969963121992111428649113794614499532441441141428121976111121223453 +1323512461571182817929939121211713121331191618931184488921591924371235949236168615391825511262223251 +1844736754225215827118148196139158162168679832813293479114597571111121411671116786889524639436242557 +4129283884611621139311619918595314638141219118197141982129117931591223136764173918143299992113253194 +6671213763912343811231319922512514312369111929282929165115129559956116288484182461615162311121211148 +2181433993113222146117211167911285371166791149379422215815118977498295214751775791959491311282321124 +1893917971839118469544291628117512951141192191241581996647811817614684113124339455132319119114111833 +3194199213412152114124178931454213517429615776219211422169278113182121444219111131179993118914924997 +8219157811341224982161348148111137699341495216731165567471616617941931189972413946971741111281539372 +3152991117932991922251181118416182931569516111612171922275213185896565291135832617881969216831717171 +8121312176196962611113271281983885941434758534152637122112688674391761284711462212621329281482136967 +8912131712629191413717199581682992241791258247943427519627115113181185118893474742221612199416241114 +2221161716133212262324458823185719629698212514616894944235615445525451113712232992549892442332219993 +6911428166248291364296657112178221953148681417139715698913134796992291191172362729179523142135611926 +9193236341295518167899946545124351411258968629291352811613236111815329611335145489738414432321321432 +6499112739337254948563116237193161125349119739111891452711618219882237913445111154917766361994516299 +4229111836211397937422211492241292322326927188315516321228751111732223381939852566191913828113619658 +4833174199812161182295513144544918898488232695919771112444311825381832117171263412399721619352658112 +7345157387254272529181221134266152214182213139812959885519442556151428591127252113184465879292314161 +4121465311125417865689227119793711491911121482117238853817572153785844421215789241437331227838558423 +7523449997166932491931658961611531315911811164945424124681119911514197115371331269117411119195916939 +9128356914695294253146521193138399121128911413417518232932311581117299227259128821183119275215162333 +8227711221398832121511812135311996274919173171129616622917349424125661165191393153231221123245228595 +4661116386124142435676668639172615623882971851132123111533289551472765422233434392326129112321811177 +1114217118682227172769681833229791919152755377579244542792389334115282624447734191114139324262441812 +6333952614971166184221548154711268114116731892434448374621261433111364575261971518211189121489159114 +2643196276215391358127393286244464171242921198641798351383314226421425913793645897272129967531283212 +5221131154713291512567291442563229223436517211423727422223922197775199547432692311674116717814141189 +1819812131622311541323862952123752381291168856181384249979548263219194576715373571921367953197516599 +2698391452599945182154313714292112611651861235644938114519912171341121343514175192421245367422118845 +1611517822616311553312232428414211183613187966271813393742419936965141554638677392552594157325161112 +2616289141825669321758111712577299113571118732335179737221439878266941941412314591611896381134423452 +1527518133297694711977121278995238611939331141152651419529812614622461553336429953291144879147151561 +6213921184159959912652486789753618112941772164917131997527427312889291111154689437932652465371922993 +1589621196261511215112194551558331982928756286156353223919126143241698114592611956762736234771235113 +8165134892151911811992165572238498525759113712471968163566177711133512677122986191491333635131511791 +5121221111325162242111121122831421669143125569751141468542973371346331562315313969174126843799229968 +9311826253374818154286131873371269258326126213915219114431182511695131248953693559426228911488261322 +6591912229221199191129116241691328113778565819111151417179291232116973821215214994781183977822113919 +2655733341912396361634999147955152969525556354836191314176963932513419228391962945211314943311783881 +3118513322278916893854417223419174791345313746443425946927242923322912213948211723553112339311144122 +5393914115613713593912123214127131162129218517429461299451985249947485233933233921659915294223287391 +1136191983199344171731412199186927561119191219449214216992974151651232175255264491687372483691287841 +9979467192332442137813919617268197123213515265393883398799246483166214491885851268864128943317146789 +5137813992711119791889189943164114839536152943452515191991159113143114778121351814419428981641345112 +1139549732431283823889222929962191941833515674999331261216489474223871213121931162521316251539111719 +9648979341691798386938175539169825511368121122518621349181719251191923915224299327193775463296152619 +2311686178629622129357219123853166497242116415121621253426142621912642623299254411219291611241129171 +7121116711145236394141163917421425189867111859681243149523155243991912931714194994881892515611113358 +1818136725482517518915422141595131218142168351111612261359827276317281438261183179221111193792271938 +1139232197366129111613197151415986632374322119127213743117112134123523163898634321495279921127151221 +1455314773112765478191612311924292793128399375128619158595924411116981162347622141987917914911132244 +8251232313319753992222152996483791494285141669117359623333132226419358827367424225513193954688331113 +6111234734513789142262268362695121242113336193619579246538959597918449963359798412951815198197838189 +1578813352693398121218392393228426881375119641573137139414326439413217641415223545191618221945511142 +1911342279476333131545622131253816127514398158171126197453819142121921259134342249152113279914226717 +1181629961152116111141119143162937219335744191534119193429336859258124131916718881314941225494635341 +3222424734834755922262268951935198255226535129825126496551953155492124112112211175279241996463213119 +1593211411152338281162891684932212324129938521214175966519115616258481414912622151114391841157816911 +9141742471551231591911521557311235228349158433361181732488334569224298416181419199789621481599971133 +6431198331792522412624936255227425156144247631813877119181883195211392367931313972411512151112618967 +2267991391137261324361516124912921857412152165751315973914128819334272982513357434496931189261186356 +9731813991313183129492113339525281972169411596682712297561568989281898122432796821932939271461411118 +9527134412189191252414927113351112113969912114126318294265393127727772965192682248351121436671131949 +2934611311112198347953125482617172423953569149249533769821945569113994113763296118552242729222291678 +1119821798911229468135239194762377711532847158111932619121161511191149211189681391816252112113662712 +6214121139114981831641312844617298831755199745993362226745938625473922122411831659139316811819252196 +3924199495311615731298928326511113989189152121371528721212116121162831153589349432417428485259451119 +5671887941514276146115224125348154943341717912911297112361317998423125793133517712118312219932327921 +3441237411174773198815869762621122911338922117263951832219575348184521221829897832142581331278543895 +2211991891331676514418141258839222191162231674139112521311364936142331963939355929771951341931514622 +3747831369635231342124231137812472365447171343913391192962128751842928364413553211815321439116297947 +3831431319439189562841352632121129765521147556153119234918143471929436282139114141121119611153125122 +2139868123226218473119733131211449463783356211861164441899319364198832981181141122831449381518499837 +4838641963928213442551872111262529681463281171145974513318477114933139791111182125546543252119792122 +1959561559542891384239921218331871441193122413948521139911152336487323225262262552411443442912132194 +4314213327111115624539372751956191844329316172123933514157637524332315229214279183693125891951974216 +4121185311217111892962855325351544592933191142755325176455121327454442754548131832152935917115212312 +1154235973614813121713111278736277174981611157831121152921813123844315723944435135596869139295122111 +1191164343178491732236111338376338452883881999141122152922792155423112322571421418882716619274477923 +2942191994588631294975973591371724121221115633251176816331419716599528162253122115638991142695511897 +1515552919629173654117969541842691298189369498352573484463845716711425113318121951513141136111791614 +2338151152352731719473221793641322611375192411551164617517155997347919611627517828225538711524251539 +9161345711264179182921881491169952213815926531391622324113233224122432611247811369169532962163481152 +1396729196339538914672129619583981562917642411114972418153771391277221143911393951111126922719818115 +8795124512286141121694662341622161368222432113312766132151575916676412414382618623933742751114159519 diff --git a/2021/day15/day15_input_ez.txt b/2021/day15/day15_input_ez.txt new file mode 100644 index 0000000..ab80887 --- /dev/null +++ b/2021/day15/day15_input_ez.txt @@ -0,0 +1,10 @@ +1163751742 +1381373672 +2136511328 +3694931569 +7463417111 +1319128137 +1359912421 +3125421639 +1293138521 +2311944581 diff --git a/2021/day15/day15_test.txt b/2021/day15/day15_test.txt new file mode 100644 index 0000000..3d9db81 --- /dev/null +++ b/2021/day15/day15_test.txt @@ -0,0 +1,5 @@ +39999 +19999 +19999 +19111 +11194 diff --git a/2021/day15/day15_test_2.txt b/2021/day15/day15_test_2.txt new file mode 100644 index 0000000..92d8559 --- /dev/null +++ b/2021/day15/day15_test_2.txt @@ -0,0 +1,6 @@ +111111 +999991 +911191 +919111 +919999 +911111 diff --git a/2021/day15/day15_test_3.txt b/2021/day15/day15_test_3.txt new file mode 100644 index 0000000..7ef505f --- /dev/null +++ b/2021/day15/day15_test_3.txt @@ -0,0 +1,4 @@ +19999 +19111 +11191 +99991 diff --git a/2021/day15/makefile b/2021/day15/makefile new file mode 100644 index 0000000..dbf871a --- /dev/null +++ b/2021/day15/makefile @@ -0,0 +1,2 @@ +all day15.cpp: + g++ -std=c++20 -o day15 day15.cpp -- cgit v1.2.3-54-g00ecf