Skip to content

Instantly share code, notes, and snippets.

@lovebes

lovebes/Advent_of_Code_Day_15_Djikstra_implementation_enum_sort.ex

Last active December 18, 2021 06:04
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save lovebes/de57c109217ff87745f9153e25ef65a6 to your computer and use it in GitHub Desktop.
Save lovebes/de57c109217ff87745f9153e25ef65a6 to your computer and use it in GitHub Desktop.
Download ZIP
2021 Advent of Code Day 15 - with Djikstra Implementation in Elixir, two different min-dist finding solutions
Raw
Advent_of_Code_Day_15_Djikstra_implementation_enum_sort.ex
defmodule Advent do
@moduledoc """
How to use it:
1. Uncomment which `@proof` you want to run against - part I or part II
2. Uncomment correct `@last_coord` for target coordinate
3. Decide if you want to expand it or not (check docstring in `run/1), and pipe that result into `Advent.run/1`,
instead of just calling `Advent.run/1`
Metrics:
* Part I: 700ms ~ 1000ms
* Part II: hours (I left it running and slept)
"""
@ascii_offset 48
# @proof [
# '1964778752979887222739789777935919929996793679617497991954953881381939846468999159686925929898196249',
# '8759189989991999115121999113211788158983883981916933973182798769168715496674423979199573198873854989',
# '2916817799179797949192724497956464139512861918986689421481689714471669982489852996119597949888649993',
# '3429492714828168979771398891678818935485694839763399796988678112189583269768679792191755489996819818',
# '7956995159237939293319975584779958986526992814763894821138352743589946198365389719619992176545838879',
# '6894733223797749829183642911499532916859775927195417482554567729418599872969862136349799419994687895',
# '2759239975966982742446721118515649658718899983621767679758422696981391642329892996989459995669798697',
# '4871846878568885679911989919675587272979337779997878941142835988221478131873935963978729297886139169',
# '7999959169281333751174889518989895572896163199221368686388799926519794699799923174194941238928589796',
# '9673899872976699541997289776451458192595451289851921695168998599956996287274974589993895999911968979',
# '2189799897986439761837888853324829341216529742299672852941871997559375864789386122271746495896794791',
# '9938386946518957531699878681584584964918976817297812956462471969177758385919189982296399838923928939',
# '4275189819452758426829188964681958425813889249999799196398898929428939818471881449812315725979925948',
# '7839191997723839711989597539332999799698291856397972249727787849495896789269554411391811373488912969',
# '9991932961553536898969691427116875526215696896938613596999539698956698498155643927131628839711918729',
# '9689481119559879668959932516469834984764657446183977948691462949415366788398622963991783197189499749',
# '7893891719779792989279958991976795699181589597959138897764521861982247998328792718743913147198513966',
# '9229398293621962999951889798191298941966911561894718699997528891728499799769299594844878826379212229',
# '8114755891869969978798891934912769591996819776399989765797896128921791896759288599146617996799938892',
# '5972439691937789543995348496582934955419378443786946743176772134892759981289214999252492789994912519',
# '9999878284296198978291425928754817436271169898969986169389621659848796896718349699944959841976887979',
# '8995172699256977369819859998243969598411799887371899978965729218569995255335578989297761711979697279',
# '5964929613931779238784627758412212181166181675691169528311979637962893954537763982917915779197598919',
# '9329999971496358947166338919899899416981161169866529652865685792919877767118176597496599597196924899',
# '7271975999674778999171971959191993946848163989989997969948924863192929224488787991896699281749827981',
# '7699689989198719837571649869869997239499861716884656858395517769988394779311619459491989383499197268',
# '8138528939235689938575248913721989783488836178269759533138953836592979449873625149573891997212479889',
# '1194186961217198193988498992355788419825494192989525159689798712975319599971827597742959843955911979',
# '9991363768629695336799575699999721989989917969232982174499837972549921599924797598996111985425191495',
# '6224199895942439267375819799214473982598281689668323916911879197967989217151818849734921868839889953',
# '2797891953385665166198975159893818966216198377578712873269784989492119916357987941796591437988938957',
# '9779821394499494593989986959996998692998298791629567995816849947192476378699325431774652164876319399',
# '8279883158919549641581758481988868892673899854755757655799879479727992921235786698877699587719557817',
# '8994986299499779981878149737914546992923788331973355557931912813487414849169586776188929999316996999',
# '3499941923877958919184968172278689699896918797161441492525291995817947177988899429956927999874117615',
# '9518735698739793988999949283669535854518279898395156698682921779151989183918899376431178719847211917',
# '8959569562449992579869539699738394615824477992978595158952999831143599733757959319878895488818466994',
# '4771221597963589993951489919897987919972847979856478899532499699995165221761395991179429879943877199',
# '9358396988965649992967998569567913995272198899939966249136998289878785998148692727934781927566617716',
# '9695897663786123274922829519725449941162197499897582997999837678932164486457189978772888188949785949',
# '2229629789279799955899167476898994839159369899619998578354226667829287299556269181995691312568798773',
# '8986191398899845547849998899881493546398886844887168962985891999929956754259992377999937693899755175',
# '7175873171397179677593515237961898681148199598839711877778496983153317579398682998411683978987881997',
# '1298538869811849383999117371323559984927944988899199699928999419957218968156974484868752469129262989',
# '9731561977991246175968959799134367415782961298978241777998529577773489176786529999298276919819282278',
# '5139485996594989893145888798563499416819996991199156853594539997297977872962913739949965145219399965',
# '8983481898839581176999892935177977798924747335789486142969991819778229398776888781189418591899219928',
# '5991279788897976346748147414862695456951589321587991882347718411894488859198898259759815513119791569',
# '8227945959958298837959782585999896633581225814664916697479824997438358779792895774979843752914453972',
# '4969151368678265681558739735791991537887198957112191497717769345618978852795923288497297897895929999',
# '1519799684949231934618481659618992524489812446699528583999896615941151949985499999993886929639497791',
# '1919828829886491381185477846954179789637515617553898959167959989111765297739994219233999883196929166',
# '9998739993999963799842299399178749796575293889914288923995766963218597719191435991789849824475293761',
# '6292981699893999814978995879985986732598297996514589923713342895999879593853119193717396792997847699',
# '9995978699659218782765696299479144716993781213851813753413888998887766896164659855572836992467197889',
# '9217712236953916773136797729855561896118885989789931276897245797585829719971197298416959471465967299',
# '8749983199162381588749185138547797187291312282935858898773319299528189947814491298821948298698917998',
# '8869537419399779797931123692837166294495799967721996873988844831152966589773118129996872129174245734',
# '6999949888788198499769769893119838727389879594985996264338836189769745171919499431598495487598996829',
# '2643438319977946618997882718739614961945999488979133494999859875958989978289978891995578284983191769',
# '9711343348446947989897455526854391996559785892751279911869879891927989217818761659468859389913918159',
# '4684878627919284791377127887978412232228626693294949676597441174499789199371869999845955919776487925',
# '7336328939319927281586293939269992937969668286319998679381249791842789823962288582686236183876186189',
# '8498199998653599954199689592971461496115597192381769198382378211678161716941995196615974678163278978',
# '2998646498892845989822928114511999895167278839959595169842949959999918557832795946119311714389383991',
# '9984244818187938587919721975981668841119986975695637997888658465896898817589749499729979598979727197',
# '3863786997161389931987278761687458498299597892974921921998696597634973915194429518998588919819992157',
# '3119918226997269698895866728999573113997218692982671793292949996198899525937453993612931127922615284',
# '6379719955643911286241981859839442769958499849676976399619189989256898582949928891859195489926593225',
# '9466177592439495219155699988857895114899757931376891988791861639981429819498859829699953915984557119',
# '5374978935117993911513985778249971394799996215739819192271757989986194819377829685788878384186668579',
# '5996948596188399596276916591738868899415917585689991911459474597973519819254199897579188972591385492',
# '9322616873977891567797785992628933998998689889969238979881992269985738953791967118985999822789973433',
# '9199392396987912599354118198522389299456969987319191279618989499499887993924599797794177285631979167',
# '8855183914541833731439967697497418572879596386674694298959932189933841866512369842921637392699374912',
# '8988284461979263735382265499953696978939495465937911934474937417988811279816877822138921898948376181',
# '5437381949531929775936998169527199196578734594998292179919393485374186397999598711914297897676779586',
# '2396881448499782771276998937887566187891818989841832748994742788697928591911992786489698526461694989',
# '4246912291936687945949431175795992778687971357323979793399128579749866596897749827138281972961559158',
# '8647699922398842951889916948999698459962477299829918411933795388631159575199881299857589572777687999',
# '1311988719839948383899391321597894992589538493239179737996223383196197788192688789936916569885746193',
# '7954826979959947682969468987879991533849653569579969694792898697776848612986289349116791369579963519',
# '6593461421187759143952361892951669186319499192899168818751698499375889498194687225996979991984182191',
# '9335328245597991499897759977969229696591989282589998699129519144748578917798947994995199792918282991',
# '9398849415997381994698899787899727198999987399289971848636857987925948679582957479378858514993191181',
# '4149987331746768149745999853585139629671813691691596384395667999149381812199968928229665789284992374',
# '7427922988292997779559894894993998973997839317916919959899499493579911986477729836979789677259549118',
# '2642977979999586628631219897898878639971585969663183921898877933957895824999784889149738669989189789',
# '9762493593855472517917523499451984451888889977182975177177631967968932881279659956186784398919998985',
# '6432918193479269929129386389769916441769189759989721934769679259263889887181527989833327889848697941',
# '1393231159891181194862992269761747833947956873525561418387821863318689879524877738438288899299953799',
# '3842851494837961961556887296519919879914829134229941988917932644519999778998783391698499139917994989',
# '6459949159299986724199928878695399917976578879189193215239688557999671187992222149868714176139783787',
# '8463293782889894999994957687196286799689666437669478542975956699912379182795887258767997618178425918',
# '1953199634739829152796952926222792594239959671973846419654368418698936881329847929915911741616629164',
# '7845537283597249729992171128489499424199835337125999796988893187159337984973899291199499518477759357',
# '8997952978886957899187992878357919738776489938875699819693849929789872998684248986998859178999693399',
# '1138799983929178584919823996794446498474269912579351992888547384896372519992979599519718742166879882',
# '7298971978993365997919769838756115168896812437881278598927724918958597279567156161156299352891298849',
# '9179979719419789581891969361814895646898199782835916681989892966646599953969992849273537533978176119'
# ]
@proof [
'1163751742',
'1381373672',
'2136511328',
'3694931569',
'7463417111',
'1319128137',
'1359912421',
'3125421639',
'1293138521',
'2311944581'
]
# Set last coordinates here
@last_coord {9, 9}
# @last_coord {49, 49}
# @last_coord {99, 99}
# @last_coord {499, 499}
@doc """
Main function to run.
If you want to run the expansion of increasing the map 5-fold, do this:
ex = Advent.expand_raw_list()
Advent.run(ex)
Explanations:
----------------
This implements a pretty naive understanding of Djikstra.
Due to Elixir(Erlang to be exact)'s linked-list structure of how lists are implemented,
`dist` (distance list) is implemented by `map`, as it is a good middle ground (https://www.theerlangelist.com/article/sequences)
between functionality and ease of reasoning.
Both `visited_nodes` and `dist` are maps with coordinate tuples {x, y} as the key.
However, because it would have a lot of `:inf` items early on, it was attempted to also maintain an `inverted_dist`.
Even then... part II of Day 15 in Advent of Code takes HOURS to run.
I've run out of ideas other than tapping into Nx for something like this. Wonder if it would help.
"""
def run(raw_map \\ @proof) do
mapped = dump_raw_list_to_map(raw_map) |> IO.inspect(label: "mapped")
{dist, visited_nodes} = init(mapped)
# inverted dist so key is integer distance value, and key is coord tuple
inverted_dist = %{0 => [{0, 0}]}
walk(mapped, visited_nodes, dist, nil, inverted_dist)
end
# Last iteration, reaching the final target coordinate. Return the value for the @last_coord in dist
defp walk(_mapped, _visited_nodes, dist, @last_coord, _) do
dist |> Map.get(@last_coord)
end
defp walk(mapped, visited_nodes, dist, _prev_coord, inverted_dist) do
u = get_next_coord(visited_nodes, dist, inverted_dist)
# O(1)
updated_visited_nodes = update_value_at(visited_nodes, u, true)
# O(1)
{updated_dist, updated_inverted_dist} =
update_dist_of_all_unvisited_adjacent_nodes(mapped, dist, visited_nodes, u, inverted_dist)
walk(mapped, updated_visited_nodes, updated_dist, u, updated_inverted_dist)
end
defp check_dists_vals_parity(dist, inverted_dist) do
# check dist types parity
d_vals =
dist
|> Enum.filter(fn
{_coord, val} -> val != :inf
end)
|> Enum.map(fn {_, val} -> val end)
|> MapSet.new()
i_vals = inverted_dist |> Enum.map(fn {val, _coord} -> val end) |> MapSet.new()
if !MapSet.equal?(d_vals, i_vals) do
IO.inspect(d_vals, label: "d_vals")
IO.inspect(i_vals, label: "i_vals")
raise "not equal"
end
end
defp get_next_coord(visited_nodes, dist, inverted_dist) do
# # {next_coord, _} =
# check_dists_vals_parity(dist, inverted_dist)
# coords_by_inverted =
inverted_dist
|> Enum.reduce([], fn {val, coord_list}, acc ->
filtered_coords =
coord_list
|> Stream.filter(fn coord -> !get_value_at(visited_nodes, coord) end)
|> Enum.sort_by(fn {x, y} -> {x, y} end)
case filtered_coords do
[] ->
acc
rest ->
updated_pair = {val, rest}
[updated_pair | acc]
end
end)
|> get_smallest_inv_dist_coord()
end
defp get_smallest_inv_dist_coord(inverted_dist_in_list) do
smallest =
inverted_dist_in_list
|> Stream.map(fn {val, _coord} -> val end)
|> Enum.sort()
|> hd
Enum.find(inverted_dist_in_list, fn {val, _coord} -> val == smallest end)
|> elem(1)
|> hd
end
defp update_dist_of_all_unvisited_adjacent_nodes(
mapped,
dist,
visited_nodes,
coord,
inverted_dist
) do
coord_dist_value = get_value_at(dist, coord)
adjacent_nodes(mapped, coord)
|> adjacent_not_in_visited(visited_nodes)
|> Stream.filter(fn {_, val} -> !is_nil(val) end)
|> Enum.reduce({dist, inverted_dist}, fn {node_coord, wgt}, {prev_dist, prev_inverted_dist} ->
sum = coord_dist_value + wgt
node_dist_value = get_value_at(prev_dist, node_coord)
cond do
node_dist_value == :inf ->
{update_value_at(prev_dist, node_coord, sum),
put_in_inverted_dist(prev_inverted_dist, node_coord, sum)}
sum < node_dist_value ->
{update_value_at(prev_dist, node_coord, sum),
put_in_inverted_dist(prev_inverted_dist, node_coord, sum)}
true ->
{prev_dist, prev_inverted_dist}
end
end)
end
defp put_in_inverted_dist(inverted_dist, coord, sum) do
if inverted_dist[sum] do
Map.put(inverted_dist, sum, [coord | inverted_dist[sum]])
else
Map.put(inverted_dist, sum, [coord])
end
end
defp init(mapped) do
dist = create_dist_from_coord_val_map(mapped)
visited_nodes = %{}
{dist, visited_nodes}
end
# O(1)
defp adjacent_not_in_visited(list_of_adjacent_with_weight, visited_nodes) do
list_of_adjacent_with_weight
|> Enum.filter(fn {coord, _wgt} ->
!get_value_at(visited_nodes, coord)
end)
end
defp adjacent_nodes(mapped, {x, y}) do
[
coord_with_weight(mapped, {x - 1, y}),
coord_with_weight(mapped, {x + 1, y}),
coord_with_weight(mapped, {x, y - 1}),
coord_with_weight(mapped, {x, y + 1})
]
end
defp coord_with_weight(mapped, coord) do
{coord, get_value_at(mapped, coord)}
end
def dump_raw_list_to_map(list_charlist \\ @proof) do
list_charlist
|> Stream.with_index()
|> Stream.flat_map(fn {charlist, row_idx} ->
charlist
|> Stream.with_index()
|> Stream.map(fn {val, col_idx} ->
parsed_val = val - @ascii_offset
{{col_idx, row_idx}, parsed_val}
end)
end)
|> Map.new()
end
def expand_raw_list(list_charlist \\ @proof) do
# expand 5 fold
unit_width = list_charlist |> hd |> length
unit_height = list_charlist |> length
enlarged_rows =
for unit_row <- list_charlist do
1..4
|> Enum.reduce(unit_row, fn _, combined ->
next_set =
combined
|> Enum.reverse()
|> Stream.take(unit_width)
|> Stream.map(&incr_val/1)
|> Enum.reverse()
combined ++ next_set
end)
end
reversed_enlarged_rows =
enlarged_rows
|> Enum.reverse()
1..4
|> Enum.reduce(reversed_enlarged_rows, fn _, combined ->
combined
|> Enum.take(unit_height)
|> Enum.reverse()
|> Enum.reduce(combined, fn row, acc ->
[Enum.map(row, &incr_val/1) | acc]
end)
end)
|> Enum.reverse()
end
defp incr_val(char) do
case char - @ascii_offset do
9 -> @ascii_offset + 1
x -> @ascii_offset + (x + 1)
end
end
defp create_dist_from_coord_val_map(value_map) do
Enum.map(value_map, fn
{{0, 0}, _val} -> {{0, 0}, 0}
{coord, _val} -> {coord, :inf}
end)
|> Map.new()
end
def get_value_at(mapped, {x, y}) do
Map.get(mapped, {x, y})
end
defp update_value_at(mapped, coord, value) do
Map.put(mapped, coord, value)
end
end
Raw
Advent_of_Code_Day_15_Djikstra_implementation_pairing_heap.ex
defmodule Advent do
@moduledoc """
How to use it:
1. Uncomment which `@proof` you want to run against - part I or part II
2. Uncomment correct `@last_coord` for target coordinate
3. Decide if you want to expand it or not (check docstring in `run/1), and pipe that result into `Advent.run/1`,
instead of just calling `Advent.run/1`
Metrics:
===================
1. With Enum.sort of distance map
* Part I: 700ms ~ 1000ms (answer: 720)
* Part II: hours (I left it running and slept) (answer: 3025)
2. With using Pairing Heap (current solution)
* Part I: 38.558 ms (answer: 720)
* Part II: 1797 ms !!!!!! (answer: 3025)
NOTE: This uses Pairing Heap module for getting the minimal value of distance list,
code used from: https://github.com/ewildgoose/elixir_priority_queue/blob/master/lib/pairing_heap.ex
"""
@ascii_offset 48
@proof [
'1964778752979887222739789777935919929996793679617497991954953881381939846468999159686925929898196249',
'8759189989991999115121999113211788158983883981916933973182798769168715496674423979199573198873854989',
'2916817799179797949192724497956464139512861918986689421481689714471669982489852996119597949888649993',
'3429492714828168979771398891678818935485694839763399796988678112189583269768679792191755489996819818',
'7956995159237939293319975584779958986526992814763894821138352743589946198365389719619992176545838879',
'6894733223797749829183642911499532916859775927195417482554567729418599872969862136349799419994687895',
'2759239975966982742446721118515649658718899983621767679758422696981391642329892996989459995669798697',
'4871846878568885679911989919675587272979337779997878941142835988221478131873935963978729297886139169',
'7999959169281333751174889518989895572896163199221368686388799926519794699799923174194941238928589796',
'9673899872976699541997289776451458192595451289851921695168998599956996287274974589993895999911968979',
'2189799897986439761837888853324829341216529742299672852941871997559375864789386122271746495896794791',
'9938386946518957531699878681584584964918976817297812956462471969177758385919189982296399838923928939',
'4275189819452758426829188964681958425813889249999799196398898929428939818471881449812315725979925948',
'7839191997723839711989597539332999799698291856397972249727787849495896789269554411391811373488912969',
'9991932961553536898969691427116875526215696896938613596999539698956698498155643927131628839711918729',
'9689481119559879668959932516469834984764657446183977948691462949415366788398622963991783197189499749',
'7893891719779792989279958991976795699181589597959138897764521861982247998328792718743913147198513966',
'9229398293621962999951889798191298941966911561894718699997528891728499799769299594844878826379212229',
'8114755891869969978798891934912769591996819776399989765797896128921791896759288599146617996799938892',
'5972439691937789543995348496582934955419378443786946743176772134892759981289214999252492789994912519',
'9999878284296198978291425928754817436271169898969986169389621659848796896718349699944959841976887979',
'8995172699256977369819859998243969598411799887371899978965729218569995255335578989297761711979697279',
'5964929613931779238784627758412212181166181675691169528311979637962893954537763982917915779197598919',
'9329999971496358947166338919899899416981161169866529652865685792919877767118176597496599597196924899',
'7271975999674778999171971959191993946848163989989997969948924863192929224488787991896699281749827981',
'7699689989198719837571649869869997239499861716884656858395517769988394779311619459491989383499197268',
'8138528939235689938575248913721989783488836178269759533138953836592979449873625149573891997212479889',
'1194186961217198193988498992355788419825494192989525159689798712975319599971827597742959843955911979',
'9991363768629695336799575699999721989989917969232982174499837972549921599924797598996111985425191495',
'6224199895942439267375819799214473982598281689668323916911879197967989217151818849734921868839889953',
'2797891953385665166198975159893818966216198377578712873269784989492119916357987941796591437988938957',
'9779821394499494593989986959996998692998298791629567995816849947192476378699325431774652164876319399',
'8279883158919549641581758481988868892673899854755757655799879479727992921235786698877699587719557817',
'8994986299499779981878149737914546992923788331973355557931912813487414849169586776188929999316996999',
'3499941923877958919184968172278689699896918797161441492525291995817947177988899429956927999874117615',
'9518735698739793988999949283669535854518279898395156698682921779151989183918899376431178719847211917',
'8959569562449992579869539699738394615824477992978595158952999831143599733757959319878895488818466994',
'4771221597963589993951489919897987919972847979856478899532499699995165221761395991179429879943877199',
'9358396988965649992967998569567913995272198899939966249136998289878785998148692727934781927566617716',
'9695897663786123274922829519725449941162197499897582997999837678932164486457189978772888188949785949',
'2229629789279799955899167476898994839159369899619998578354226667829287299556269181995691312568798773',
'8986191398899845547849998899881493546398886844887168962985891999929956754259992377999937693899755175',
'7175873171397179677593515237961898681148199598839711877778496983153317579398682998411683978987881997',
'1298538869811849383999117371323559984927944988899199699928999419957218968156974484868752469129262989',
'9731561977991246175968959799134367415782961298978241777998529577773489176786529999298276919819282278',
'5139485996594989893145888798563499416819996991199156853594539997297977872962913739949965145219399965',
'8983481898839581176999892935177977798924747335789486142969991819778229398776888781189418591899219928',
'5991279788897976346748147414862695456951589321587991882347718411894488859198898259759815513119791569',
'8227945959958298837959782585999896633581225814664916697479824997438358779792895774979843752914453972',
'4969151368678265681558739735791991537887198957112191497717769345618978852795923288497297897895929999',
'1519799684949231934618481659618992524489812446699528583999896615941151949985499999993886929639497791',
'1919828829886491381185477846954179789637515617553898959167959989111765297739994219233999883196929166',
'9998739993999963799842299399178749796575293889914288923995766963218597719191435991789849824475293761',
'6292981699893999814978995879985986732598297996514589923713342895999879593853119193717396792997847699',
'9995978699659218782765696299479144716993781213851813753413888998887766896164659855572836992467197889',
'9217712236953916773136797729855561896118885989789931276897245797585829719971197298416959471465967299',
'8749983199162381588749185138547797187291312282935858898773319299528189947814491298821948298698917998',
'8869537419399779797931123692837166294495799967721996873988844831152966589773118129996872129174245734',
'6999949888788198499769769893119838727389879594985996264338836189769745171919499431598495487598996829',
'2643438319977946618997882718739614961945999488979133494999859875958989978289978891995578284983191769',
'9711343348446947989897455526854391996559785892751279911869879891927989217818761659468859389913918159',
'4684878627919284791377127887978412232228626693294949676597441174499789199371869999845955919776487925',
'7336328939319927281586293939269992937969668286319998679381249791842789823962288582686236183876186189',
'8498199998653599954199689592971461496115597192381769198382378211678161716941995196615974678163278978',
'2998646498892845989822928114511999895167278839959595169842949959999918557832795946119311714389383991',
'9984244818187938587919721975981668841119986975695637997888658465896898817589749499729979598979727197',
'3863786997161389931987278761687458498299597892974921921998696597634973915194429518998588919819992157',
'3119918226997269698895866728999573113997218692982671793292949996198899525937453993612931127922615284',
'6379719955643911286241981859839442769958499849676976399619189989256898582949928891859195489926593225',
'9466177592439495219155699988857895114899757931376891988791861639981429819498859829699953915984557119',
'5374978935117993911513985778249971394799996215739819192271757989986194819377829685788878384186668579',
'5996948596188399596276916591738868899415917585689991911459474597973519819254199897579188972591385492',
'9322616873977891567797785992628933998998689889969238979881992269985738953791967118985999822789973433',
'9199392396987912599354118198522389299456969987319191279618989499499887993924599797794177285631979167',
'8855183914541833731439967697497418572879596386674694298959932189933841866512369842921637392699374912',
'8988284461979263735382265499953696978939495465937911934474937417988811279816877822138921898948376181',
'5437381949531929775936998169527199196578734594998292179919393485374186397999598711914297897676779586',
'2396881448499782771276998937887566187891818989841832748994742788697928591911992786489698526461694989',
'4246912291936687945949431175795992778687971357323979793399128579749866596897749827138281972961559158',
'8647699922398842951889916948999698459962477299829918411933795388631159575199881299857589572777687999',
'1311988719839948383899391321597894992589538493239179737996223383196197788192688789936916569885746193',
'7954826979959947682969468987879991533849653569579969694792898697776848612986289349116791369579963519',
'6593461421187759143952361892951669186319499192899168818751698499375889498194687225996979991984182191',
'9335328245597991499897759977969229696591989282589998699129519144748578917798947994995199792918282991',
'9398849415997381994698899787899727198999987399289971848636857987925948679582957479378858514993191181',
'4149987331746768149745999853585139629671813691691596384395667999149381812199968928229665789284992374',
'7427922988292997779559894894993998973997839317916919959899499493579911986477729836979789677259549118',
'2642977979999586628631219897898878639971585969663183921898877933957895824999784889149738669989189789',
'9762493593855472517917523499451984451888889977182975177177631967968932881279659956186784398919998985',
'6432918193479269929129386389769916441769189759989721934769679259263889887181527989833327889848697941',
'1393231159891181194862992269761747833947956873525561418387821863318689879524877738438288899299953799',
'3842851494837961961556887296519919879914829134229941988917932644519999778998783391698499139917994989',
'6459949159299986724199928878695399917976578879189193215239688557999671187992222149868714176139783787',
'8463293782889894999994957687196286799689666437669478542975956699912379182795887258767997618178425918',
'1953199634739829152796952926222792594239959671973846419654368418698936881329847929915911741616629164',
'7845537283597249729992171128489499424199835337125999796988893187159337984973899291199499518477759357',
'8997952978886957899187992878357919738776489938875699819693849929789872998684248986998859178999693399',
'1138799983929178584919823996794446498474269912579351992888547384896372519992979599519718742166879882',
'7298971978993365997919769838756115168896812437881278598927724918958597279567156161156299352891298849',
'9179979719419789581891969361814895646898199782835916681989892966646599953969992849273537533978176119'
]
# @proof [
# '1163751742',
# '1381373672',
# '2136511328',
# '3694931569',
# '7463417111',
# '1319128137',
# '1359912421',
# '3125421639',
# '1293138521',
# '2311944581'
# ]
# Set last coordinates here
# @last_coord {9, 9}
# @last_coord {49, 49}
# @last_coord {99, 99}
@last_coord {499, 499}
@doc """
Main function to run.
If you want to run the expansion of increasing the map 5-fold, do this:
ex = Advent.expand_raw_list()
Advent.run(ex)
Explanations:
----------------
This implements a pretty naive understanding of Djikstra.
Due to Elixir(Erlang to be exact)'s linked-list structure of how lists are implemented,
`dist` (distance list) is implemented by `map`, as it is a good middle ground (https://www.theerlangelist.com/article/sequences)
between functionality and ease of reasoning.
Both `visited_nodes` and `dist` are maps with coordinate tuples {x, y} as the key.
"""
def run(raw_map \\ @proof) do
mapped = dump_raw_list_to_map(raw_map)
{dist, visited_nodes} = init(mapped)
priority_queue = {}
{time, result} = :timer.tc(fn -> walk(mapped, visited_nodes, dist, nil, priority_queue) end)
IO.inspect("Done. It took: #{time / 1_000} msec")
result
end
defp init(mapped) do
dist = create_dist_from_coord_val_map(mapped)
visited_nodes = %{}
{dist, visited_nodes}
end
# Last iteration, reaching the final target coordinate. Return the value for the @last_coord in dist
defp walk(_mapped, _visited_nodes, dist, @last_coord, _) do
dist |> Map.get(@last_coord)
end
defp walk(mapped, visited_nodes, dist, _prev_coord, priority_queue) do
u = get_next_coord(visited_nodes, dist, priority_queue)
# O(1)
updated_visited_nodes = update_value_at(visited_nodes, u, true)
# O(1)
{updated_dist, updated_priority_queue} =
update_dist_of_all_unvisited_adjacent_nodes(
mapped,
dist,
visited_nodes,
u,
priority_queue
)
cleaned_updated_priority_queue =
process_priority_queue_with_visited_nodes(updated_priority_queue, updated_visited_nodes)
walk(
mapped,
updated_visited_nodes,
updated_dist,
u,
cleaned_updated_priority_queue
)
end
defp process_priority_queue_with_visited_nodes({} = queue, _), do: queue
defp process_priority_queue_with_visited_nodes(
{_min_val, min_coord, _} = priority_queue,
visited_nodes
) do
if get_value_at(visited_nodes, min_coord) do
{_popped, updated_queue} = PairingHeap.pop(priority_queue)
updated_queue
else
priority_queue
end
end
defp get_next_coord(
_visited_nodes,
_dist_,
{} = _priority_queue
),
do: {0, 0}
defp get_next_coord(
_visited_nodes,
_dist,
{_curr_min_val, min_coord, _} = _priority_queue
) do
min_coord
end
defp update_dist_of_all_unvisited_adjacent_nodes(
mapped,
dist,
visited_nodes,
coord,
priority_queue
) do
coord_dist_value = get_value_at(dist, coord)
adjacent_nodes(mapped, coord)
|> adjacent_not_in_visited(visited_nodes)
|> Stream.filter(fn {_, val} -> !is_nil(val) end)
|> Enum.reduce({dist, priority_queue}, fn {node_coord, wgt},
{prev_dist, prev_priority_queue} ->
sum = coord_dist_value + wgt
node_dist_value = get_value_at(prev_dist, node_coord)
cond do
sum < node_dist_value || node_dist_value == :inf ->
{update_value_at(prev_dist, node_coord, sum),
maybe_put_to_queue(prev_priority_queue, sum, node_coord)}
true ->
{prev_dist, prev_priority_queue}
end
end)
end
defp maybe_put_to_queue({}, sum, node_coord), do: PairingHeap.new(sum, node_coord)
defp maybe_put_to_queue(
priority_queue,
sum,
node_coord
) do
PairingHeap.put(priority_queue, sum, node_coord)
end
# O(1)
defp adjacent_not_in_visited(list_of_adjacent_with_weight, visited_nodes) do
list_of_adjacent_with_weight
|> Enum.filter(fn {coord, _wgt} ->
!get_value_at(visited_nodes, coord)
end)
end
defp adjacent_nodes(mapped, {x, y}) do
[
coord_with_weight(mapped, {x - 1, y}),
coord_with_weight(mapped, {x + 1, y}),
coord_with_weight(mapped, {x, y - 1}),
coord_with_weight(mapped, {x, y + 1})
]
end
defp coord_with_weight(mapped, coord) do
{coord, get_value_at(mapped, coord)}
end
def dump_raw_list_to_map(list_charlist \\ @proof) do
list_charlist
|> Stream.with_index()
|> Stream.flat_map(fn {charlist, row_idx} ->
charlist
|> Stream.with_index()
|> Stream.map(fn {val, col_idx} ->
parsed_val = val - @ascii_offset
{{col_idx, row_idx}, parsed_val}
end)
end)
|> Map.new()
end
def expand_raw_list(list_charlist \\ @proof) do
# expand 5 fold
unit_width = list_charlist |> hd |> length
unit_height = list_charlist |> length
enlarged_rows =
for unit_row <- list_charlist do
1..4
|> Enum.reduce(unit_row, fn _, combined ->
next_set =
combined
|> Enum.reverse()
|> Stream.take(unit_width)
|> Stream.map(&incr_val/1)
|> Enum.reverse()
combined ++ next_set
end)
end
reversed_enlarged_rows =
enlarged_rows
|> Enum.reverse()
1..4
|> Enum.reduce(reversed_enlarged_rows, fn _, combined ->
combined
|> Enum.take(unit_height)
|> Enum.reverse()
|> Enum.reduce(combined, fn row, acc ->
[Enum.map(row, &incr_val/1) | acc]
end)
end)
|> Enum.reverse()
end
defp incr_val(char) do
case char - @ascii_offset do
9 -> @ascii_offset + 1
x -> @ascii_offset + (x + 1)
end
end
defp create_dist_from_coord_val_map(value_map) do
Enum.map(value_map, fn
{{0, 0}, _val} -> {{0, 0}, 0}
{coord, _val} -> {coord, :inf}
end)
|> Map.new()
end
def get_value_at(mapped, {x, y}) do
Map.get(mapped, {x, y})
end
defp update_value_at(mapped, coord, value) do
Map.put(mapped, coord, value)
end
end
Raw
part_where_it_is_slowest.ex
defp get_next_coord(visited_nodes, dist, inverted_dist) do
inverted_dist
|> Enum.reduce([], fn {val, coord_list}, acc ->
filtered_coords =
coord_list
|> Stream.filter(fn coord -> !get_value_at(visited_nodes, coord) end)
|> Enum.sort_by(fn {x, y} -> {x, y} end)
case filtered_coords do
[] ->
acc
rest ->
updated_pair = {val, rest}
[updated_pair | acc]
end
end)
|> get_smallest_inv_dist_coord()
end
defp get_smallest_inv_dist_coord(inverted_dist_in_list) do
smallest =
inverted_dist_in_list
|> Stream.map(fn {val, _coord} -> val end)
|> Enum.sort()
|> hd
Enum.find(inverted_dist_in_list, fn {val, _coord} -> val == smallest end)
|> elem(1)
|> hd
end
defp get_value_at(mapped, {x, y}) do
Map.get(mapped, {x, y})
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment