this repo has no description
hauleth.dev
1<!-- livebook:{"persist_outputs":true} -->
2
3# Day 09
4
5```elixir
6Mix.install([:kino_aoc])
7```
8
9## Section
10
11<!-- livebook:{"attrs":"eyJhc3NpZ25fdG8iOiJwdXp6bGVfaW5wdXQiLCJkYXkiOiI5Iiwic2Vzc2lvbl9zZWNyZXQiOiJBRFZFTlRfT0ZfQ09ERV9TRVNTSU9OIiwieWVhciI6IjIwMjQifQ","chunks":null,"kind":"Elixir.KinoAOC.HelperCell","livebook_object":"smart_cell"} -->
12
13```elixir
14{:ok, puzzle_input} =
15 KinoAOC.download_puzzle("2024", "9", System.fetch_env!("LB_ADVENT_OF_CODE_SESSION"))
16```
17
18<!-- livebook:{"output":true} -->
19
20```
21{:ok,
22 "6920945132536042828994482345396169724991532616269072173941615129441070989533549353544192338215647480107561245832285861135469128938656230362333818111433746344751894125805448321674418337459440436476402523264257512621383849394968854739721644705231266361534476141022646838663844981685665728936624151235476791584929822482292987334479824016888196957024425673938289753698621244157130975989396226731549454298144391686468562820376390235135108330238590316674261440783039581594584646247629719986582560203598244312596985279832984526808559405915881067383593502384107494586724976925694948216635952475703445963854271259175649271576378184603074946598276445248640841860479933368524996925945274749282264063148922416399632485376097486952663787643633316356949469798134153950341455917737349115548390535536536397237654519556679716185652595572754749672866345553911576628161614338861880658781637382837898686889463249126116447176285128303560134154431099612772162289797131303641655015516771696046959228585241299646581370538088916416989047515564526116366867367181678616439431284930379889626059473847818663132232979123503952455854489755245141781899866948543116887346827534697893607177987563154596774691267167851154138330695352108499217988406372425774968626985943665687196181233111972699532427257992757984672882888037943925818450345177398760216079692074854569485530377584183586279552981343712063437565138087959796501957177177884278405560475435141829787014884681355059571489723985901554488154898784759668954752934048679146776060562786272011429026535298115262548593878183498916571398351436431313482968486771572527901996664899792152552410493090499727835643526428881322227999149881884793853729989624533029587010105028429614225841889414576176753414877452414680577843459538128911939238704598815126186492327558383740971333501769852667796188543180462490517062819496532859194781303437743159526136553370517461484469733677187178992265612439155938358015666261906673153823768535183244601645561579916316476813124539675061263411515873626197742860301068615568696174716481151333516718804424987323957615961444822618946925923196806747458558553262735686467327309580525855605085698452928593956820699112556481136173708346321771719645737818963669665547522134505223646796667286359173528172301211931188731691358636677670346032949579894428251583802532214067603254278658698940647270167640764638397570409829821264846762426836572463386475815673329747876757249732659277388030843590439617143487927833367461978526979212861844382550791390358527895937281110537852835869713059958217969899704145215985377666628719451233132412294358444746793946343553683032671225858498134340537229859741987180829468238642605723478228646886791227546199853372232566387139711011753555879744151132642224546223435667375781861424845134566438891443785750344893853718679532879854483395621276216275644617996376282773738211864275304297979547422875934634992111232368475557713129934172577624852042405732858060209959806520925730394293739081861693532946112557827992852621975727432957291082907728921029905725787812513023871891551681262814572424452648875694586632916946898788794936727799526748807158546930659285568029733948646265541485187570661411984840326374573377475525442055851882711851241546246736884066686885724058588220382743451817154627144869212944944985727560911326298754699513901913775411631051155448259136813383243697125190592983671813131786588158152523929049549018258627964330945831994544156999373027523966329015316477207024639470312244244043635392684240435826402148884612989874566739774998162494686244143442812672951249922585423333957811202767768597518787769627151336335561386093158376767595684951873065594471827052965041948820794865486179401375326111497235854418829486872664452298163169179763609277741983868518845423468770227926607088302941698125295594475259881783566721809397453893791727816025381929613950311537338366491240658016437269618697401059446097141870959520762921795565136242743648578086232855147488427619213536145259919693337741268680894834764319547389247696113145205712656834305853252319218569748862345539664553175240528621328137233671331496239591159242157540311894387168" <> ...}
23```
24
25```elixir
26#puzzle_input = "2333133121414131402"
27
28tags =
29 Stream.from_index()
30 |> Stream.intersperse(:gap)
31
32files =
33 puzzle_input
34 |> String.split("", trim: true)
35 |> Enum.map(&String.to_integer/1)
36 |> Enum.zip(tags)
37```
38
39<!-- livebook:{"output":true} -->
40
41```
42[
43 {6, 0},
44 {9, :gap},
45 {2, 1},
46 {0, :gap},
47 {9, 2},
48 {4, :gap},
49 {5, 3},
50 {1, :gap},
51 {3, 4},
52 {2, :gap},
53 {5, 5},
54 {3, :gap},
55 {6, 6},
56 {0, :gap},
57 {4, 7},
58 {2, :gap},
59 {8, 8},
60 {2, :gap},
61 {8, 9},
62 {9, :gap},
63 {9, 10},
64 {4, :gap},
65 {4, 11},
66 {8, :gap},
67 {2, 12},
68 {3, :gap},
69 {4, 13},
70 {5, :gap},
71 {3, 14},
72 {9, :gap},
73 {6, 15},
74 {1, :gap},
75 {6, 16},
76 {9, :gap},
77 {7, 17},
78 {2, :gap},
79 {4, 18},
80 {9, :gap},
81 {9, 19},
82 {1, :gap},
83 {5, 20},
84 {3, :gap},
85 {2, 21},
86 {6, :gap},
87 {1, 22},
88 {6, :gap},
89 {2, 23},
90 {6, :gap},
91 {9, ...},
92 {...},
93 ...
94]
95```
96
97```elixir
98defmodule Disk do
99 def checksum(files) do
100 files
101 |> Enum.reduce({0, 0}, fn
102 {gap, :gap}, {pos, sum} ->
103 {pos + gap, sum}
104
105 {len, idx}, {pos, sum} ->
106 new_pos = pos + len
107 score = Enum.sum(pos..(new_pos - 1)) * idx
108
109 {new_pos, score + sum}
110 end)
111 |> elem(1)
112 end
113
114 def display(lst) do
115 Enum.map(lst, fn
116 {len, val} ->
117 sym = if val == :gap, do: ".", else: to_string(val)
118
119 List.duplicate(sym, len)
120 end)
121 |> IO.iodata_to_binary()
122 end
123end
124```
125
126<!-- livebook:{"output":true} -->
127
128```
129{:module, Disk, <<70, 79, 82, 49, 0, 0, 11, ...>>, {:display, 1}}
130```
131
132## Part 1
133
134```elixir
135defmodule Compactor do
136 def run(files) do
137 occupied =
138 Enum.reduce(files, 0, fn
139 {_, :gap}, acc -> acc
140 {len, _idx}, acc -> acc + len
141 end)
142
143 compact([], occupied, files, Enum.reverse(files))
144 end
145
146 defp compact(acc, 0, _, _), do: Enum.reverse(acc)
147
148 defp compact(acc, left, [{0, :gap} | rest], rfiles),
149 do: compact(acc, left, rest, rfiles)
150
151 defp compact(acc, left, rest, [{_, :gap} | rfiles]),
152 do: compact(acc, left, rest, rfiles)
153
154 defp compact(acc, left, rest, [{0, _idx} | rfiles]) do
155 compact(acc, left, rest, rfiles)
156 end
157
158 defp compact(acc, left, [{gap, :gap} | rest], [{len, idx} | rfiles]) do
159 fill = min(gap, len)
160
161 compact([{fill, idx} | acc], left - fill, [{gap - fill, :gap} | rest], [
162 {len - fill, idx} | rfiles
163 ])
164 end
165
166 defp compact(acc, left, [{len, idx} = file | rest], rfiles) when is_integer(idx) do
167 compact([file | acc], left - len, rest, rfiles)
168 end
169end
170```
171
172<!-- livebook:{"output":true} -->
173
174```
175{:module, Compactor, <<70, 79, 82, 49, 0, 0, 11, ...>>, {:compact, 4}}
176```
177
178```elixir
179files
180|> Compactor.run()
181|> Disk.checksum()
182```
183
184<!-- livebook:{"output":true} -->
185
186```
1876332189866718
188```
189
190## Part 2
191
192```elixir
193defmodule Defrag do
194 def run(files) do
195 files
196 |> Enum.reverse()
197 |> Enum.reduce(files, fn
198 {_, :gap}, acc -> acc
199 file, acc -> do_run(acc, file, [])
200 end)
201 end
202
203 defp do_run([], _, acc), do: Enum.reverse(acc)
204
205 defp do_run([file | _] = list, file, acc), do: Enum.reverse(acc, list)
206
207 defp do_run([{len, :gap} | rest], {len, idx}, acc),
208 do: Enum.reverse(acc, [{len, idx} | rep(rest, {len, idx})])
209
210 defp do_run([{gap, :gap} | rest], {len, idx}, acc) when len < gap,
211 do: Enum.reverse(acc, [{len, idx}, {gap - len, :gap} | rep(rest, {len, idx})])
212
213 defp do_run([hd | rest], file, acc), do: do_run(rest, file, [hd | acc])
214
215 defp rep([{a, :gap}, file, {b, :gap} | rest], {len, _} = file),
216 do: [{a + len + b, :gap} | rest]
217
218 defp rep([{a, :gap}, file | rest], {len, _} = file), do: [{a + len, :gap} | rest]
219 defp rep([file, {b, :gap} | rest], {len, _} = file), do: [{len + b, :gap} | rest]
220 defp rep([file | rest], {len, _} = file), do: [{len, :gap} | rest]
221 defp rep([hd | rest], file), do: [hd | rep(rest, file)]
222end
223```
224
225<!-- livebook:{"output":true} -->
226
227```
228{:module, Defrag, <<70, 79, 82, 49, 0, 0, 12, ...>>, {:rep, 2}}
229```
230
231```elixir
232files
233|> Defrag.run()
234|> Disk.checksum()
235```
236
237<!-- livebook:{"output":true} -->
238
239```
2406353648390778
241```
242
243<!-- livebook:{"offset":8665,"stamp":{"token":"XCP.-mRlAHFcVs4Mg2hQj8TCLWgOv8zjlatUnbxbgI43tZXllMXB8VfJTbRJrHTJ1k_FrGDhUdviUPyCSPNKqXk-ZOQ9PHWUPFkLaK5S4SMKa18Ny7WrQvSmaHuoE2R6vJhqrck","version":2}} -->