<3 
btw i just boils down to implicit requirements and to understand the problem. Thanks again
jarlah
1
adamu
I’m glad to see it was not just me that was struggling / writing… less than pretty code for this one. 
I didn’t complete part 2, because although it worked on the sample, like @Aetherus I hadn’t accounted for the fact that moving a file that’s next to a space will leave a bigger space behind - and it’ll need a completely different approach to fix 
1
lud
It should be easy to remember where to search:
If you move a file that starts at block 123, from now on you will not search free space after 123.
Even more, for a file that starts at block 100 and is of size 5, then you will only look for free space in the blocks 0..(100-5)
This is my new version using only lists, the version with maps was too much of a chore to my taste. This one was fun! (and best run was 33ms)
defmodule AdventOfCode.Solutions.Y24.Day09 do
alias AoC.Input
def parse(input, _part) do
input
|> Input.read!()
|> String.trim()
|> String.graphemes()
|> Enum.map(&String.to_integer/1)
end
def part_one(problem) do
rev_blocks = build_disk(problem)
blocks = :lists.reverse(rev_blocks)
blocks = compress(blocks, Enum.filter(rev_blocks, fn {_, v} -> v != :free end), [])
hash(blocks)
end
defp build_disk(problem) do
build_disk(problem, :file, 0, 0, [])
end
defp build_disk([0 | t], :file, block_id, file_id, acc) do
build_disk(t, :free, block_id, file_id + 1, acc)
end
defp build_disk([0 | t], :free, block_id, file_id, acc) do
build_disk(t, :file, block_id, file_id, acc)
end
defp build_disk([h | t], :file, block_id, file_id, acc) do
build_disk([h - 1 | t], :file, block_id + 1, file_id, [{block_id, file_id} | acc])
end
defp build_disk([h | t], :free, block_id, file_id, acc) do
build_disk([h - 1 | t], :free, block_id + 1, file_id, [{block_id, :free} | acc])
end
defp build_disk([], _, _, _, acc) do
acc
end
defp compress([{bid, :free} | blocks], [{fbid, file_id} | movables], acc) when bid <= fbid do
compress(blocks, movables, [{bid, file_id} | acc])
end
defp compress([{bid, file_id} | blocks], [{fbid, _} | _] = movables, acc) when bid <= fbid do
compress(blocks, movables, [{bid, file_id} | acc])
end
defp compress(_blocks, _movables, acc) do
acc
end
defp hash(blocks) do
Enum.reduce(blocks, 0, fn
{i, f}, acc when is_integer(f) -> acc + i * f
{_, :free}, acc -> acc
end)
end
def part_two(problem) do
rev_blocks = build_disk(problem)
{free_chunks, files_chunks} =
rev_blocks
|> :lists.reverse()
|> Enum.chunk_by(fn {_, v} -> v end)
|> Enum.map(fn [{_, fid_or_free} | _] = list ->
{Enum.map(list, &elem(&1, 0)), fid_or_free}
end)
|> Enum.split_with(fn {_, id} -> id == :free end)
free_chunks = Enum.map(free_chunks, fn {bids, :free} -> {bids, length(bids)} end)
rev_files_chunks = :lists.reverse(files_chunks)
blocks = defrag(rev_files_chunks, free_chunks, [])
hash2(blocks)
end
defp defrag([{[low_bid | _] = bids, file_id} = h | rev_files_chunks], [{[high_free | _], _} | _] = free_chunks, acc)
when high_free < low_bid do
space = take_space(free_chunks, bids)
[bid | _] = bids
case space do
{[free_bid | _] = free_bids, free_chunks} when free_bid < bid ->
defrag(rev_files_chunks, free_chunks, [{free_bids, file_id} | acc])
_ ->
defrag(rev_files_chunks, free_chunks, [h | acc])
end
end
defp defrag(rest, _, acc) do
rest ++ acc
end
defp take_space(free_chunks, bids) do
take_space(free_chunks, length(bids), [])
end
defp take_space([{vids, larger_len} | rest], len, skipped) when len < larger_len do
{vids_used, vids_rest} = Enum.split(vids, len)
{vids_used, :lists.reverse(skipped, [{vids_rest, larger_len - len} | rest])}
end
defp take_space([{vids, same_len} | rest], same_len, skipped) do
{vids, :lists.reverse(skipped, rest)}
end
defp take_space([skip | rest], len, skipped) do
take_space(rest, len, [skip | skipped])
end
defp take_space([], _, _) do
nil
end
defp hash2(blocks) do
Enum.reduce(blocks, 0, fn
{bids, f}, acc when is_integer(f) -> Enum.reduce(bids, acc, fn b, acc -> acc + b * f end)
end)
end
end
1
billylanchantin
Not a very impressive golf today. There’s a lot of essential complexity here I failed to circumvent.
LOC: 39
defmodule Aoc2024.Day09 do
def part1(file) do
{blocks, frees, _} = parse(file)
n = Enum.reduce(blocks, 0, fn {_, range}, sum -> sum + Range.size(range) end)
blocks = Enum.flat_map(blocks, fn {id, range} -> Enum.map(range, &{id, &1}) end)
{left, right} = Enum.split_while(blocks, fn {_, index} -> index < n end)
right = Enum.zip(Enum.map(right, &elem(&1, 0)) |> Enum.reverse(), Enum.flat_map(frees, & &1))
Enum.reduce(left ++ right, 0, fn {a, b}, sum -> sum + a * b end)
end
def part2(file) do
{blocks, frees, _} = parse(file)
Enum.reduce(Enum.reverse(blocks), {frees, 0}, fn {id, br}, {fs, checksum} ->
s = Range.size(br)
{l, r} = Enum.split_while(fs, fn fr -> s > Range.size(fr) or fr.first > br.first end)
case r do
[fits | rest] ->
{o, p} = Range.split(fits, s)
{l ++ if(p.step == 1, do: [p | rest], else: rest), checksum + id * Enum.sum(o)}
[] ->
{fs, checksum + id * Enum.sum(br)}
end
end)
|> elem(1)
end
def parse(file) do
s = file |> File.stream!(1) |> Stream.reject(&(&1 == "\n"))
chunks = s |> Enum.map(&String.to_integer/1) |> Enum.chunk_every(2, 2) |> Enum.with_index()
Enum.reduce(chunks, {[], [], 0}, fn {[nb | rest], id}, {blocks, frees, c} ->
new_free = if((nf = List.first(rest) || 0) > 0, do: (c + nb)..(c + nb + nf - 1), else: ..)
{blocks ++ [{id, c..(c + nb - 1)}], frees ++ [new_free], c + nb + nf}
end)
end
end
1
jarlah
i liked it your solution. I failed part2 today and used your code as a basis to understand how you solved it. The gist of it which i really need to get it into my head is Enum.chunk_every. That was perfect for for this problem, coupled with with_index. I will see if i can refactor this another day, rewrite it with the core idea of blocks and ranges etc. probably with structs. To make it a) more readable and understandable and b) just because i like structs
0
seeplusplus
One reason I’ve started doing more this year in Livebook is that I can easily copy and paste my part 1 soln into a new cell and start hacking away at it to solve part 2. That came in handy for this one.
Part 1:
defmodule Fragmenter do
def parse_disk_map(map) do
map
|> String.to_charlist()
|> Stream.map(&(&1 - 48))
|> Stream.chunk_every(2)
|> Stream.with_index()
|> Enum.flat_map(fn {[used, free], id} ->
(for _ <- Stream.cycle([0]) |> Enum.take(used) do id end) ++ (for _ <- Stream.cycle([0]) |> Enum.take(free) do nil end)
{[used], id} ->
(for _ <- Stream.cycle([0]) |> Enum.take(used) do id end)
end)
end
@doc """
## Examples
iex> "2333133121414131402" |> Fragmenter.parse_disk_map() |> Fragmenter.defrag() |> Fragmenter.checksum()
1928
"""
def defrag(disk) do
cl_disk = disk |> Stream.with_index()
bak = cl_disk |> Enum.reverse() |> Enum.reject(&(elem(&1,0) == nil))
cl_disk
|> Enum.reduce(
{[], bak },
fn
{c, i}, {fwd, [{_, j} | _] = bak} when c != nil and i <= j ->
{ [c | fwd], bak}
{c, i}, {fwd, [{_, j} | _] = bak} when c != nil and i > j ->
{ [nil | fwd], bak}
{nil, i}, {fwd, [{c, j} | rest]} when i <= j ->
{ [c | fwd], rest }
{nil, i}, {fwd, [{_, j} | rest]} when i > j ->
{ [nil | fwd], rest }
end
) |> elem(0) |> Enum.reverse()
end
def checksum(disk) do
disk
|> Stream.with_index()
|> Stream.reject(&(elem(&1, 0) == nil))
|> Enum.reduce(
0,
fn {c, i}, acc -> acc + c*i end
)
end
end
Part 2:
defmodule Fragmenter2 do
def parse_disk_map(map) do
map
|> String.to_charlist()
|> Stream.map(&(&1 - 48))
|> Stream.chunk_every(2)
|> Stream.with_index()
|> Stream.flat_map(fn {[used, free], id} ->
[Stream.cycle([id]) |> Enum.take(used), Stream.cycle([nil]) |> Enum.take(free)]
{[used], id} ->
[Stream.cycle([id]) |> Enum.take(used)]
end)
|> Stream.reject(&(&1 == []))
end
def defrag(disk) do
files = disk |> Enum.into([])
x = Stream.flat_map(disk, &(&1)) |> Stream.reject(&(&1 == nil)) |> Enum.into(MapSet.new())
defrag(files |> :queue.from_list(), :queue.new(), x)
end
def merge_empty(file, empty) do
[file, empty |> Enum.take(Enum.count(empty) - Enum.count(file))]
end
def defrag(dq, fragged, x) do
if :queue.is_empty(dq) do
fragged |> :queue.to_list()
else
case :queue.get(dq) do
[] -> defrag(:queue.drop(dq), fragged, x)
[n | _] = file when n != nil ->
n_available? = MapSet.member?(x, n)
defrag(
:queue.drop(dq),
:queue.in(
if n_available? do
file
else
Stream.cycle([nil]) |> Enum.take(file |> Enum.count())
end,
fragged
),
x
)
[nil | _] = empty ->
fit_q = :queue.filter(
fn [n | _] = l -> MapSet.member?(x, n) and (l |> Enum.count()) <= (empty |> Enum.count())
and (l |> Enum.at(0) != nil)
end, dq)
cond do
fit_q |> :queue.is_empty() -> defrag(
dq |> :queue.drop(),
:queue.in(empty, fragged),
x
)
true ->
first_fit = fit_q |> :queue.get_r()
[first_fit, empty] = merge_empty(first_fit, empty)
defrag(
dq |> :queue.drop() |> then(&:queue.in_r(empty, &1)),
:queue.in(first_fit, fragged),
x |> MapSet.delete(first_fit |> Enum.at(0))
)
end
end
end
end
def checksum(disk) do
disk
|> Stream.flat_map(&(&1))
|> Stream.with_index()
|> Stream.reject(&(elem(&1, 0) == nil))
|> Enum.reduce(
0,
fn {c, i}, acc -> acc + c*i end
)
end
end
This is probably some of the ugliest Elixir I’ve ever written, but this one took me like 2.5hrs between part 1 and 2 to get right and I kept hitting stupid bugs. No clue if the use of :queue was necessary or even helpful here and I have yet to go back and try to optimize it (pt 2 takes about 3.5s on my machine, pt 1 is about 35ms).
Edit: I think @sevenseacat says it best:
I am not proud of the code I wrote today.
0
lud
I started with maps but in the end it’s the list version that is the faster for me. Around 40ms.
(but yeah my map version was probably just bad 
)
1
billylanchantin
I stand corrected! I think 40ms may be the thread leader.
I generally expect maps to perform better when the lists are sparse, but when the lists are dense it’s a toss-up. I’d just assumed that because mine was so slow (~4s) it was one of those cases but I didn’t check.
0
mwilsoncoding
Almost caught up. Posting part 1 for posterity:
#!/usr/bin/env elixir
defmodule Day9.Part1 do
@ascii_adjustment 48
defp parse(str) do
[{_size, _id} | _diskmap] =
diskmap =
str
|> String.trim()
|> to_charlist()
|> Enum.map(&(&1 - @ascii_adjustment))
|> Enum.with_index()
%{
empty_space: empty_space,
files: [{first_file_size, _ffid} = _file | _files] = files,
optimal_size: optimal_size
} =
diskmap
|> Enum.reduce(
%{},
fn {size, id} = item, acc ->
if rem(id, 2) == 0 do
acc
|> Map.update(:files, [item], fn files -> [item | files] end)
|> Map.update(:optimal_size, size, &(&1 + size))
else
acc
|> Map.update(:empty_space, [item], fn empty_space -> [item | empty_space] end)
end
end
)
|> Map.new(fn
{:empty_space = k, v} -> {k, v |> Enum.map(&elem(&1, 0)) |> Enum.reverse()}
{:files = k, v} -> {k, v |> Enum.reverse() |> Enum.map(&elem(&1, 0)) |> Enum.with_index()}
optimal_size -> optimal_size
end)
optimal_size = optimal_size - first_file_size
empty_space_count = empty_space |> Enum.count()
file_count = files |> Enum.count()
ends_with_space? = empty_space_count == file_count
empty_space =
if ends_with_space?,
do: empty_space |> List.delete_at(empty_space_count - 1),
else: empty_space
initial_insertion_index = 1
%{
files: files,
empty_space: empty_space,
optimal_size: optimal_size,
insertion_index: initial_insertion_index
}
end
defp pull([] = _files, _blocks), do: {[], []}
defp pull(files, 0 = _blocks), do: {[], files}
defp pull([{block_size, id} = file | files], blocks) do
block_diff = block_size - blocks
case block_diff do
x when x < 0 ->
{pulled_files, remaining_files} = pull(files, abs(block_diff))
{[file | pulled_files], remaining_files}
x when x > 0 ->
{[{blocks, id}], [{block_diff, id} | files]}
0 ->
{[{blocks, id}], files}
end
end
defp pull_from_end(files, blocks) do
{pulled, remaining} = pull(Enum.reverse(files), blocks)
{pulled, remaining |> Enum.reverse()}
end
defp optimize(%{
files: files,
empty_space: _empty_space,
optimal_size: nil,
insertion_index: _index
}),
do: files
defp optimize(%{
files: files,
empty_space: _empty_space,
optimal_size: optimal_size,
insertion_index: _index
})
when optimal_size <= 0,
do: files
defp optimize(%{
files: files,
empty_space: [],
optimal_size: _optimal_size,
insertion_index: _index
}),
do: files
defp optimize(%{
files: files,
empty_space: [empty_size | empty_spaces],
optimal_size: optimal_size,
insertion_index: index
}) do
next_optimal_size = optimal_size - empty_size
{files_to_insert, remaining_files} =
if next_optimal_size < 0,
do: pull_from_end(files, optimal_size),
else: pull_from_end(files, empty_size)
next_file_index = index + 1
next_optimal_size =
if next_file_index > remaining_files |> Enum.count() do
nil
else
next_optimal_size - (remaining_files |> Enum.at(index) |> elem(0))
end
file_count = files_to_insert |> Enum.count()
modified_files =
(remaining_files
|> Enum.take(index)) ++ files_to_insert ++ (remaining_files |> Enum.drop(index))
insertion_index = next_file_index + file_count
optimize(%{
files: modified_files,
empty_space: empty_spaces,
optimal_size: next_optimal_size,
insertion_index: insertion_index
})
end
def checksum(files) do
files
|> Enum.reduce(
{0, 0},
fn {block_size, id} = _chunk, {index, acc} ->
ids = for _ <- 0..(block_size - 1), do: id
acc =
acc +
(ids
|> Enum.with_index()
|> Enum.map(fn {id, i} ->
id * (i + index)
end)
|> Enum.sum())
{index + block_size, acc}
end
)
end
def solve() do
File.read!("09/input.txt")
|> parse()
|> optimize()
|> checksum()
|> elem(1)
|> IO.puts()
end
end
Day9.Part1.solve()
Still working on part 2
0