Day15
Setup
sample = """
1163751742
1381373672
2136511328
3694931569
7463417111
1319128137
1359912421
3125421639
1293138521
2311944581
"""
input = """
4552285989441124719798465825773318252269422625731628851155123123687151412171224298271625249662328175
8311826917677295561395716245426184212471311214851351547842124165674922644719934113217134531111711843
3134155528231296313292951689371671611355199429313261226392991129959293212461289411393263181213122398
7134159681533331172991932819128718131121428715191238612623891233112534231482681182354129791911339131
3291622121893821258215111531614233999661649271811871529461211115739821388973611183517651567314846349
9116197319992223784973749159912918948514855218957329971416177152174169497812373219984133121155319113
4968439114135996923939621521227438616432262962572553451333141591641121311129913812892293179114231721
6239219785234675391281641114148225942622192542113712327361223716951191275736388845623994891799592928
1939273152114165815621898131741625142273757411141673112259897358299222269191191214321758245326199814
3816295121211713919918129141521748315579413854273125311823434671365133636981112367451294972238794443
2852174392175217891292769297329734141529288318181221953212137313858911222727424134319782324839616229
8183411981136718428823127681411246528222138421871778251231423171588642328395114123811125612118626218
3338418958818229331399513691921921869922413136194421828291197132791812222241633461426938621462118999
6118582765375541144491519871123121172943678873247541921192915151717957812714841145223161116244141719
1469257418313218951211511591224281868433285518896571868973996776391916421179863524342144166273783912
1422118419319515496189391158516462277393622129936871982217562457129964219912124123218312977313682811
8162546139952136189911177533357821252891975965218152184112132367245486747212214333324221119951528114
1488239611461491973865185242959577752914191817477523179143671148316542517213281111151119111864959392
2218917661868133141243819962413216131979913232799988871913939111823317421712824994542992792255223561
5734326732884792428191241121191811111111473387959653938269214112192296162111121271889621211118195111
1511935111861121935741768338923128124661819191925137121591321229121111755219811212182121742778172224
9691562183513388221726493821238419121411141652415724257169175511984419826317912119999434678121339231
2729237532959444733225435991119461921916882435586112311223124141186312488218129149812515658171863425
7312559181323743938221212236191514318418548186139317233736171333421416212237192119355192471989892212
9415747738346141691418825197173192515219266172136455452815162517475883863143239112116141841148451749
1716263121115631141784252251314588413213814511691451393911924811572861144235991292175255372133811315
2113414911731164962342223421317921647461491268117386815433911112541511131114761959253123128112819312
5611912334927221252711276871211624911564162161151291141471494555221624112246614151591111923265776291
1232313271113554189955413155112699163114821911353171341215485252647889646619236253688482351315735369
2928123121191267721323822133384328412616119246178131321245693192617151348489271993468574213234923161
3738152544625516916693642738573193818379635241112299568611511432174519855133859227139712691931163454
4978932237312615451115123994194181387239461985218454596664714694169812591251542128791112588238428113
3912899182798916628918131979371112226953512814111311128381119548221199616478868331875333186481121175
1192927421372584232141915111886499529492278636769145793985139259812374369331982931471421336131151625
3911185215582434844193161925151121286721292842811119362211484112143921956211724157122539837492394492
2953216722815212632732453117127324334249682233371211614762722313186947295795983392311121826197161624
1198382767218312279682278191822374559293793873174499211516436372431371961648282146283935293224883912
2721884412949147613342941184192811799669771915122149974294638981641377324238731539914369681342394477
3115118226257112172214531484191979121212629611941829729475142214919216183112798119132131299929929699
1466138152589912253129981816414331451718321345795981111891281781111972184919821925923141344127119916
9122134452846226111158128491291121145921222611191948931811123751226221716719166843766823615463271932
6619413231595241518519791341359886562981116111712917233731162191991239432652386931159591326187113817
1591845559162771847321152825187221391211122541281244754119292979548984493162991919959714934322337916
9145672294212142439213811931976372247362114829339211131128281865174113912121498492324131148121412341
1756381967913432222112226193132111121163731192131143782119299311666751422511193161912311177255311491
7115421916752266197811918146237953712817131391633913821814582931412513381932142138371125246189914126
1598759376392514417822195284118133472211872183424131361292781113442751745432173337612973642181819911
1591927514986431542931331139613924212515831921359261755424117232619116257358732811361551433133715429
2212111786268518388677923211533188345939141431423322741185388818746937933316139596963917115156513628
1855546869784857736214551457262769215529832121261231613433399962496153414792119714419153328447319921
3511415871713341517259565232116433981351421678135321191415221837295414292764788231114826312162341834
1318126219119423358223393722114232919911513119438148878413538911488323992254252914857272139929315563
4289226872419291861111383538111219112723121131591971688293116191243172327912122531151228931163825361
4267158139198923577615628157767215331521989227229273443329721698929373269121122111211118234885216413
1721281392353248918171111348431632192885983433192911673143212314835824251437392163131172671133214211
5692434767167216246181911647487628151199631629919256742261113166114149911986911217644914329391511712
3171778979133384821415911915931112614411161443519188221518117991151822193121471212118516171612194481
5728892915394116535685132841521314914121155636512129949659431291134139338413127321115791617158219492
5922861319161211595287232112219437811222352666151929995431111444364119321358256314981447283261239184
3222922881213813538112221219919839222562138222214373588415721997345273115221926221171788323425398221
7121892289471757714164192317199889321525289161191684627127231622121813228164928171711883131411171115
4142133195631891911149439213662211433837321296381465816173997759492225942284821492317392226316171421
7171767952218516859111921382981412117845155531414929285844619281338151913746922229418521329595329132
4816434489225615129112978111511319222163357872511891321872136916132598114322114834241711175313191619
2514669152191264429122527554915621525232982214127922591124617421227986192172464521171554113293241255
1774416897439364241311525518963326121825461491834135917315678145446394222119252415181557212319979836
2924418171212166376217332219928524125161151381352283981249219536811189593191191599828153912124771153
4727284757417238221195571727143816932519912332164191111313562582931769391773963555132631269421642112
1826176132932591211811281494184124649671144935551536222129675132732112314333131883173928216124343136
3941791891125279118465128381591141714936412111144872142196359856953125116815582139618126238119115194
6384117152771514979552471442881941755398722446886791413239114561671931482126123895183722933123653386
8288171182979883467251168211845926325328548779112522134122556292344839656392433126114296546576969111
2138989191121173198114315232525383591485375339363419514352517573221121171933413254921418513742631831
2213937521219111556424717112813918859811613149217542121258771325685446299113436243924329111883434559
5617411212729914494182219773316932281919155593277131423859448626521722117873728694549823541912312231
7221118972111421391134729292837321281576312986563112977458467319418639282574649243117271379499867916
7481381681214113329839118518993911987199743449929119497141229931317315347953958761558423818144714914
1962828621421912127195245938424121754697118642194232414827848912318131722969611192541614712413124389
1453414916661118796193123189169627934943195131587127135111441988921215121971461323995311761192254778
1518323154639911222886514111893851359235192392211115741135984919811553443945191524421112271149351165
2124619118928812488832412319378222622441927332925587491814133367139228519219159512159781839661391252
9136123238713391213615338836814173613372192337512891881479195988521936915119119435812284115134985121
3187261985313118116972571821212913911963714631126731221266314529196541119322571137312995744923631544
2332196771181422121471611133259321313136947141217624113313181189182899571613229611511529134392846341
2251119425212277151215291781189314975221719413134967665311869114521729499121116213885163746111535137
9586226199417317151915282291149995631781731851159711348611212628493271263152555273213316776492793658
9912626841129251219151217833912973311223772814496593297471731359818991699147989928243894313247532231
3418241618947516332227613831374921874855584125558114429471121321232177214321598521597161191128216954
8822616123274861411769128213421232113175792178713153351744856521396128117147182712443411512198547621
5136333391414812842139999627612251181119116134115993237221194432774327464926135181519819157243157311
3251712384221229339111197239365114189176819952384125831111975148571184652387121257481133311981238514
4179221897253196943111444994381452998232779759947119714529137541964411154341851412468966612128546572
3561511861976915288819136237471569199991221811128611595299121117942329621124911194511484259317211339
7111129229731261111283415393296113773364287191681115113218825813213487828249222962695115515691873514
7329411182343148337133461144181931219118279336638688643366271821255171224147641198181918236522367641
9283273114241197532168149326977442972132134212116845582279681563772677122931571239535226581819843529
1998826211243465142314171494115638947312397589362193711385179619216332311195192919797766423111769171
5525112294591818267911389162211123228611241372111487571111114322132741612141213853137289112282145369
3749112349379788119372851572694972255221141172838213557111196117255932787266739885219667115595878115
2711353211472121989372124182678117398917811239219156315953193628344552163451161917419183114199897172
"""
Part a
defmodule Day15 do
def dimensions(grid) do
{length(grid |> Enum.at(0)) - 1, length(grid) - 1}
end
def get(grid, x, y) do
grid |> Enum.at(y) |> Enum.at(x)
end
def valid_neighbors(grid, x, y) do
{x_max, y_max} = dimensions(grid)
[{-1, 0}, {1, 0}, {0, -1}, {0, 1}]
|> Enum.map(fn {i, j} -> {i + x, j + y} end)
|> Enum.reject(fn {i, j} -> i < 0 or i > x_max or j < 0 or j > y_max end)
end
def optimize_score_map_until_stable(score_map, risk_grid) do
optimize_score_map_until_stable(score_map, risk_grid, :math.pow(10, 10))
end
def optimize_score_map_until_stable(score_map, risk_grid, total_score) do
new_score_map = optimize_score_map(score_map, risk_grid)
new_total_score =
new_score_map
|> display
|> Enum.concat()
|> Enum.sum()
if new_total_score < total_score do
# IO.puts("current score is: #{new_total_score}")
optimize_score_map_until_stable(new_score_map, risk_grid, new_total_score)
else
new_score_map
end
end
def optimize_score_map(score_map, risk_grid) do
{x_max, y_max} = dimensions(risk_grid)
for j <- 0..y_max,
i <- 0..x_max do
{i, j}
end
|> Enum.reduce(score_map, fn {x, y} = key, acc ->
new_min =
min(
get(risk_grid, x, y) + local_minimum_score(score_map, risk_grid, x, y),
Map.fetch!(score_map, key)
)
Map.put(acc, key, new_min)
end)
end
def initialize_score_map(risk_grid) do
{x_max, y_max} = dimensions(risk_grid)
start_map = Map.put(%{}, {0, 0}, 0)
for j <- 0..y_max,
i <- 0..x_max do
{i, j}
end
# Don't reduce the entry point
|> Enum.slice(1..-1)
|> Enum.reduce(start_map, fn {x, y} = key, acc ->
Map.put(acc, key, get(risk_grid, x, y) + local_minimum_score(acc, risk_grid, x, y))
end)
end
def local_minimum_score(score_map, risk_grid, x, y) do
local_scores =
valid_neighbors(risk_grid, x, y)
|> Enum.map(fn key ->
Map.get(score_map, key)
end)
if Enum.any?(local_scores) do
local_scores |> Enum.min()
else
0
end
end
def display(score_map) do
{x_max, y_max} =
score_map
|> Map.keys()
|> Enum.reduce({0, 0}, fn {x, y}, {i, j} -> {max(x, i), max(y, j)} end)
for j <- 0..y_max do
for i <- 0..x_max do
Map.get(score_map, {i, j}, 0)
end
end
end
end
risk_grid =
input
|> String.split("\n", trim: true)
|> Enum.map(&String.graphemes/1)
|> Enum.map(fn row -> Enum.map(row, &String.to_integer/1) end)
risk_grid
|> Day15.initialize_score_map()
|> Day15.optimize_score_map_until_stable(risk_grid)
|> Day15.display()
|> Enum.at(-1)
|> Enum.at(-1)
Part b
risk_grid =
input
|> String.split("\n", trim: true)
|> Enum.map(&String.graphemes/1)
|> Enum.map(fn row -> Enum.map(row, &String.to_integer/1) end)
{x_max, y_max} = Day15.dimensions(risk_grid)
expanded_risk_grid =
for j <- 0..4,
y <- 0..y_max do
for i <- 0..4,
x <- 0..x_max do
risk_grid
|> Day15.get(x, y)
|> then(&(&1 + i + j))
|> then(fn
x when x > 9 -> x - 9
x -> x
end)
end
end
expanded_risk_grid
|> Day15.initialize_score_map()
# |> Day15.optimize_score_map_until_stable(expanded_risk_grid)
# |> Day15.display()
# |> Enum.at(-1)
# |> Enum.at(-1)
