Advent of Code 2024 - Day 9

[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

[jarlah]

Ok so to summeraize, if I had thought about it. Chunked every, with index and use a map.

The reason why i didnt went for map is that I didnt see the value of it. But maps are much faster when it comes to finding the last id aka max id, because of the way its implemented. To find last element in list its bound to go through every single element to reverse it. Oh and List.update_at … i mean come one … Map.put …

So key take aways is: chunk, index, use maps even if its just for the index … for those who dont want to focus on speed, but have fun

[lud]

Yes I thought it would be slow because for part 2 I modify the free blocks list not only at the head, but lower in the linked list.

But I guess while slow, linked lists are highly optimized in Erlang.

I’d suggest you run my solution on your machine though. I know that @bjorng uses the time reported by mix test for instance. I use :timer.tc in my helper commands so it’s going to report lower times.

[jarlah]

oh and btw i did the refactoring i needed to understand all this … i combined best efforts from both @billylanchantin and @bjorng Map for the blocks for easy retrieval and focusing on getting checksum

jarlah/advent_of_code/blob/master/lib/2024/day_9/Part2.ex#L20

next on my list for this is to see if i can simplify the free ranges concept, but I might just continue on day 10. EDIT: i have dissected it completely. It now uses maps for both blocks and ranges.

[mwilsoncoding]

Takes a bit too long for my liking, but here’s my first pass a part 2. Changed my approach fundamentally. Spent way more time in the weeds than I thought- had to diagram some stuff before it made sense mentally.

#!/usr/bin/env elixir

defmodule Day9.Part2 do
  @ascii_adjustment 48

  defp parse(str) do
    analyzed_diskmap =
      str
      |> String.trim()
      |> to_charlist()
      |> Enum.map(&(&1 - @ascii_adjustment))
      |> Enum.with_index()
      |> Enum.reduce(
        [],
        fn {size, i}, acc ->
          if rem(i, 2) == 0 do
            [%{size: size, id: div(i, 2)} | acc]
          else
            [%{size: size} | acc]
          end
        end
      )
      |> Enum.reverse()

    ends_with_space? = not (analyzed_diskmap |> List.last() |> Map.has_key?(:id))

    analyzed_diskmap =
      if ends_with_space?,
        do: analyzed_diskmap |> List.delete_at((analyzed_diskmap |> Enum.count()) - 1),
        else: analyzed_diskmap

    analyzed_diskmap
  end

  defp swap_index(%{id: _id, size: size} = _file, file_index, diskmap) do
    case diskmap |> Enum.find_index(&(not Map.has_key?(&1, :id) and &1.size >= size)) do
      nil -> nil
      i when i > file_index -> nil
      i -> i
    end
  end

  defp swap(%{size: file_size} = _file, diskmap, file_index, swap_index) do
    %{size: empty_space} = diskmap |> Enum.at(swap_index)

    remaining_empty_space = empty_space - file_size

    if remaining_empty_space > 0 do
      diskmap
      |> List.update_at(swap_index, &Map.update!(&1, :size, fn _ -> remaining_empty_space end))
      |> Enum.slide(file_index, swap_index)
      |> List.insert_at(file_index, %{size: file_size})
    else
      # if no space left, swap file and space
      diskmap
      |> List.update_at(swap_index, &Map.update!(&1, :size, fn _ -> 0 end))
      |> Enum.slide(file_index, swap_index)
      |> List.insert_at(file_index + 1, %{size: file_size})
    end
  end

  defp combine_free_space([]), do: []
  defp combine_free_space([space] = _diskmap) when not is_map_key(space, :id), do: []
  defp combine_free_space([_file] = diskmap), do: diskmap

  defp combine_free_space([item_a, item_b | diskmap]) when not is_map_key(item_a, :id) and not is_map_key(item_b, :id) do
    combine_free_space([%{size: item_a.size + item_b.size} | diskmap])
  end

  defp combine_free_space([item | diskmap]), do: [item | combine_free_space(diskmap)]

  defp optimize(diskmap) do
    files_in_reverse =
      diskmap
      |> Enum.flat_map(fn item -> if Map.has_key?(item, :id), do: [%{id: item.id, size: item.size}], else: [] end)
      |> Enum.reverse()

    files_in_reverse
    |> Enum.reduce(
      diskmap,
      fn
        %{id: id} = file, diskmap ->
          file_index =
            diskmap
            |> Enum.find_index(&(Map.has_key?(&1, :id) and &1.id == id))
          case swap_index(file, file_index, diskmap) do
            nil ->
              diskmap

            swap_index ->
              swap(file, diskmap, file_index, swap_index)
              |> combine_free_space()
          end
      end
    )
  end

  def checksum(diskmap) do
    diskmap
    |> Enum.reduce(
      {0, 0},
      fn
        %{id: id, size: file_size} = _file, {index, acc} ->
          ids = for _ <- 0..(file_size - 1), do: id

          acc =
            acc +
              (ids
               |> Enum.with_index()
               |> Enum.map(fn {id, i} ->
                 id * (i + index)
               end)
               |> Enum.sum())

          {index + file_size, acc}
        %{size: empty_size}, {index, acc} -> {index + empty_size, acc}
      end
    )
  end

  def solve() do
    File.read!("09/input.txt")
    |> parse()
    |> optimize()
    |> checksum()
    |> elem(1)
    |> IO.puts()
  end
end

Day9.Part2.solve()

[MikeLindner]

Struggled with this one on part 2. Several failed approaches that I am chalking up to brain fatigue from tackling three days worths of problems after a regular work day to catch up on these. Neither part 1 or part 2 is very quick. 41 sec via mix test to run both parts so I must be missing some key ideas. Plenty to study on other’s solutions for sure, but here it is.

defmodule Aoc2024.Day9 do
  @moduledoc false

  # This is used ni
  @free "."

  def part1(file) do
    get_input(file)
    |> block_map()
    |> fragment()
    |> checksum()
  end

  defp get_input(file) do
    File.read!(file)
    |> String.split("\n", trim: true)
    |> Enum.map(&String.split(&1, "", trim: true))
    # The input should be all on one line, but just in case.
    |> List.flatten()
    |> Enum.map(&String.to_integer/1)
  end

  defp block_map(disk_map, id \\ 0) do
    # Create a list of one character per block as per the description.
    # Not very efficient for large disk maps. For part 2 I turned it into a
    # better structure.
    {files, free, rest} = pop2(disk_map, 0)

    List.duplicate(id, files) ++
      List.duplicate(@free, free) ++
      if rest == [] do
        []
      else
        block_map(rest, id + 1)
      end
  end

  defp fragment(blocks) do
    fragment(blocks, next_free(blocks, 0), next_file(blocks, length(blocks) - 1))
  end

  defp fragment(blocks, insert, index) do
    if insert >= index do
      blocks
    else
      id = Enum.at(blocks, index)

      blocks
      |> List.replace_at(insert, id)
      |> List.replace_at(index, @free)
      |> fragment(next_free(blocks, insert + 1), next_file(blocks, index - 1))
    end
  end

  defp checksum(blocks) do
    blocks
    |> Enum.with_index()
    |> Enum.reduce(0, fn {v, i}, sum ->
      if v == @free do
        sum
      else
        sum + v * i
      end
    end)
  end

  # Surely there's a built in way to do this that I haven't found.
  defp pop2([first | [second | rest]], _default) do
    {first, second, rest}
  end

  defp pop2([first | rest], default) do
    {first, default, rest}
  end

  defp next_free(blocks, index) do
    if Enum.at(blocks, index) == @free do
      index
    else
      next_free(blocks, index + 1)
    end
  end

  defp next_file(blocks, index) do
    if Enum.at(blocks, index) != @free do
      index
    else
      next_file(blocks, index - 1)
    end
  end

  def part2(file) do
    get_input(file)
    |> block_map()
    |> block_map2()
    |> defrag()
    |> calc_checksums()
    |> Enum.sum()
  end

  # Creates a map of maps from the basic list of characters to manage the free
  # chunks and data (file) chunks.
  defp block_map2(blocks) do
    blocks
    |> Enum.with_index()
    |> Enum.chunk_by(fn {block, _index} -> block end)
    |> Enum.reduce(%{}, fn chunk, memory ->
      {id, addr} = List.first(chunk)
      type = if id == @free, do: :free, else: :data
      size = length(chunk)

      value = %{
        addr: addr,
        id: id,
        size: size
      }

      if size == 0 do
        memory
      else
        Map.update(memory, type, Map.put(%{}, addr, value), fn curr ->
          Map.put(curr, addr, value)
        end)
      end
    end)
  end

  defp data_addresses(memory) do
    memory
    |> then(fn memory -> Map.keys(Map.get(memory, :data)) end)
    |> Enum.sort()
    |> Enum.reverse()
  end

  defp find_free_chunk(memory, req_size) do
    free = Map.get(memory, :free)

    Map.keys(free)
    |> Enum.sort()
    |> Enum.find_value(false, fn addr ->
      %{size: size} = Map.get(free, addr)

      if size >= req_size do
        addr
      else
        false
      end
    end)
  end

  defp defrag(memory) do
    data_addresses(memory)
    |> Enum.reduce(memory, fn addr, memory ->
      defrag(memory, addr)
    end)
  end

  defp defrag(memory, addr) do
    data_chunk = %{size: size} = Map.get(memory, :data) |> Map.get(addr)
    available_addr = find_free_chunk(memory, size)

    if available_addr == false or available_addr > addr do
      memory
    else
      allocate(memory, available_addr, addr, data_chunk)
      |> Map.update!(:data, fn data ->
        Map.delete(data, addr)
      end)
    end
  end

  defp allocate(memory, free_addr, data_addr, %{id: id, size: size}) do
    # Since we only move data from the later addresses to earlier we don't need
    # to bother consolidating newly freed chunks.
    memory
    |> Map.update!(:data, fn data ->
      Map.put(data, free_addr, %{addr: free_addr, id: id, size: size})
      |> Map.delete(data_addr)
    end)
    |> Map.update!(:free, fn free ->
      {free_chunk, updated_free_data} = Map.pop!(free, free_addr)

      if free_chunk.size > size do
        new_free_addr = free_chunk.addr + size

        new_free_chunk = %{
          addr: new_free_addr,
          id: @free,
          size: free_chunk.size - size
        }

        Map.put(updated_free_data, new_free_addr, new_free_chunk)
      else
        updated_free_data
      end
    end)
  end

  defp calc_checksums(memory) do
    # Only need to calculate the checksum for data sections (files) since free
    # blocks have a value of zero.
    memory
    |> then(fn memory -> Map.values(Map.get(memory, :data)) end)
    |> Enum.map(fn %{addr: addr, id: id, size: size} ->
      trunc((addr + addr + size - 1) / 2 * size * id)
    end)
  end
end

[ken-kost]

Yea, same. First attempt actually worked for part 1 but part 2 got stuck, so I tried different approaches yesterday and today but even part 1 wasn’t passing beyond test. I hate that, when test passes but input doesn’t, how am I supposed to debug this.
I referenced @lud 's solution to get through it, I like the recursive functions approach. Hopefully I learned something. Also question for lud: is there a reason you’re using :lists.reverse instead of Enum.reverse ?

[lud]

No that’s just a habit from my Erlang days a long time ago. I am not sure I ever tried to reverse anything but a list, so it makes sense that I remember that function to be in that module.

[lkuty]

Using an unbounded deque (double ended queue) for part 1 and putting all the blocks inside of it. That data structure has O(1) amortized access time to both ends of the queue. It is an interesting functional data structure (maybe present in Chris Okasaki’s book).

Not clever but fast enough. Part 2 uses two lists for files and free space with ranges but it is not fast enough probably because I sort the free blocks every time. I could just insert it at the right position and it might faster. Anyway, 1.2 sec is ok.

elixirc unbounded_deque.ex
$ ./day09.exs
Part 1: 6386640365805
Job done in 18531 µs
Part 2: 6423258376982
Job done in 1289240 µs

day09.ex:

#!/usr/bin/env elixir

# AoC 2024. day 9.

defmodule Part1 do
  def move_block(disk, nil, acc) do
    {value, disk} = UnboundedDeque.popleft(disk)
    case value do
      nil -> Enum.reverse(acc)
      _ ->
        move_block(disk, value, acc)
    end
  end
  def move_block(disk, value, acc) do
    case value do
      nil -> acc
      "." ->
        {value, disk} = UnboundedDeque.pop(disk)
        move_block(disk, value, acc)
      _ ->
        move_block(disk, nil, [value | acc])
    end
  end
end

# Part 1

# Populate an UnboundedDeque with all the file blocks and free space
# file? indicates if the next digit considered belongs to a file
{disk, _file_id, _file?} = File.read!("../day09.txt")
|> String.codepoints()
|> Enum.reduce({UnboundedDeque.new(), 0, true}, fn
  "\n", acc -> acc # ignore the newline at the end of the file
  x, {disk, file_id, file?} ->
    x = String.to_integer(x)
    cond do
      x == 0 ->
        {disk, file_id, !file?}
      file? ->
        {
          Enum.reduce(1..x, disk, fn _i, disk -> UnboundedDeque.append(disk, file_id) end),
          file_id+1, false
        }
      true ->
        {
          Enum.reduce(1..x, disk, fn _i, disk -> UnboundedDeque.append(disk, ".") end),
          file_id, true
        }
    end
end)

start = System.monotonic_time(:microsecond)
Part1.move_block(disk, nil, [])
|> Enum.with_index()
|> Enum.reduce(0, fn {id, pos}, sum -> sum+id*pos end)
|> IO.inspect(label: "Part 1")
elapsed = System.monotonic_time(:microsecond) - start
IO.puts "Job done in #{elapsed} µs"

# Part 2

defmodule Part2 do
  def move_files([], _free, acc), do: acc
  def move_files([file | files], free, acc) do
    case find_free_slot(free, {file_id, range} = file) do
      nil ->
        move_files(files, free, [file | acc])
      free_slot ->
        size = Range.size(range)
        new_file = {file_id, (free_slot.first..free_slot.first+size-1)}
        new_free_slot = free_slot.first+size..free_slot.last
        if new_free_slot.first <= new_free_slot.last do
          move_files(files, insert_free_slot(List.delete(free, free_slot), new_free_slot), [new_file | acc])
        else
          move_files(files, List.delete(free, free_slot), [new_file | acc])
        end
    end
  end
  defp find_free_slot([], _file), do: nil
  defp find_free_slot([x | free], {_file_id, range} = file) do
    if x.first < range.first && Range.size(range) <= Range.size(x),
      do: x,
      else: find_free_slot(free, file)
  end
  defp insert_free_slot(free, new_free_slot) do
    Enum.sort([new_free_slot | free])
  end
end

{files, free} = File.read!("../day09.txt")
|> String.codepoints()
|> Enum.reduce({[], [], true, 0, 0}, fn
  "\n", acc -> acc
  x, {files, free, file?, file_id, n} ->
    x = String.to_integer(x)
    cond do
      x == 0 ->
        {files, free, !file?, file_id, n}
      file? ->
        {[{file_id, (n..n+x-1)} | files], free, false, file_id+1, n+x}
      true ->
        {files, [(n..n+x-1) | free], true, file_id, n+x}
    end
end)
|> then(fn {files, free, _, _file_id, _n} -> {files, Enum.reverse(free)} end)

start = System.monotonic_time(:microsecond)
Part2.move_files(files, free, [])
|> Enum.reduce(0, fn {file_id, positions}, sum -> Enum.reduce(positions, sum, fn pos, sum -> sum+file_id*pos end) end)
|> IO.inspect(label: "Part 2")
elapsed = System.monotonic_time(:microsecond) - start
IO.puts "Job done in #{elapsed} µs"

unbounded_deque.ex:

defmodule UnboundedDeque do
  # Based on https://github.com/discord/deque
  defstruct size: 0, list1: [], list2: []
  def new(), do: %__MODULE__{}
  def size(%__MODULE__{size: size}), do: size

  def append(%__MODULE__{size: size, list2: list2}=deque, value) do
    %__MODULE__{deque | size: size+1, list2: [value|list2]}
  end

  def appendleft(%__MODULE__{size: size, list1: list1}=deque, value) do
    %__MODULE__{deque | size: size+1, list1: [value|list1]}
  end

  def pop(deque)
  def pop(%__MODULE__{list1: [], list2: []}=deque) do
    {nil, deque}
  end
  def pop(%__MODULE__{size: size, list2: [value|list2]}=deque) do
    {value, %{deque | size: size-1, list2: list2}}
  end
  def pop(%__MODULE__{size: size, list1: list1}=deque) do
    # We split the list in two to avoid bouncing back and forth
    # if we altern calls to pop and popleft.
    # Otherwise we could have set list2 to Enum.reverse(list1)
    {list1, list2} = reverse(list1, div(size, 2))
    %{deque | list1: list1, list2: list2} |> pop()
  end

  def popleft(deque)
  def popleft(%__MODULE__{list1: [], list2: []}=deque) do
    {nil, deque}
  end
  def popleft(%__MODULE__{size: size, list1: [value|list1]}=deque) do
    {value, %{deque | size: size-1, list1: list1}}
  end
  def popleft(%__MODULE__{size: size, list2: list2}=deque) do
    # we split the list in two to avoid bouncing back and forth
    # if we altern calls to pop and popleft
    # Otherwise we could have set list1 to Enum.reverse(list2)
    {list2, list1} = reverse(list2, div(size, 2))
    %{deque | list1: list1, list2: list2} |> popleft()
  end

  defp reverse(lst, n) do
    {lst1, lst2} = Enum.split(lst, n)
    {lst1, Enum.reverse(lst2)}
  end
end

[raytangRT]

not correct: 6345453697710
correct ans: 6377400869326

sadly, I have been stuck for a few day for Part 2, but I have no idea what’s wrong, any one have any idea?

defmodule Day9.Part2 do
  require Logger

  # 8780071174064 too high
  # 115897298587 too low
  
  def run(mode \\ :sample) do
    read(mode)
    |> fold()
    |> calculate_check_sum()
  end

  def calculate_check_sum(list) do
    list
    |> Enum.map(fn {{start, end_location}, file_id} ->
      Enum.map(start..end_location, fn i -> i * file_id end)
      |> Enum.sum()
    end)
    |> Enum.sum()
  end

  def read(mode \\ :sample) do
    file_path = if mode == :actual, do: "day9.txt", else: "day9.sample.txt"

    AOC.read_file(file_path)
    |> Enum.map(&String.graphemes/1)
    |> hd
    |> Enum.with_index()
    |> Enum.map(fn {c, idx} ->
      width = String.to_integer(c)

      cond do
        rem(idx, 2) == 0 ->
          {:file, div(idx, 2), width}

        width > 0 ->
          {:empty_space, 0, width}

        true ->
          nil
      end
    end)
    |> Enum.reject(&is_nil/1)
    |> Enum.map_reduce(0, fn item, idx ->
      width = elem(item, 2)
      {{idx, item}, idx + width}
    end)
    |> elem(0)
  end

  def fold(memory_blocks) do
    end_location = Enum.sort(memory_blocks, :desc) |> hd |> elem(0)

    files_to_fold =
      Enum.reject(memory_blocks, fn {_, {type, _, _}} -> type == :empty_space end)
      # Sort by file_id in descending order
      |> Enum.sort_by(fn {_, {:file, file_id, _}} -> -file_id end)

    empty_blocks =
      Enum.reject(memory_blocks, fn {_, {type, _, _}} -> type == :files end)
      |> BiMultiMap.new()

    Enum.reduce(files_to_fold, {%{}, empty_blocks}, fn {file_location_start,
                                                        {:file, file_id, file_width}},
                                                       {map, empty_blocks} ->
      ProgressBar.render(end_location - file_location_start, end_location)

      empty_slot = look_for_empty_space(empty_blocks, file_location_start, file_width)

      if is_nil(empty_slot) do
        {Map.put(map, file_location_start, {:file, file_id, file_width}), empty_blocks}
      else
        {slot_starting_idx, slot} = empty_slot
        empty_blocks = BiMultiMap.delete(empty_blocks, slot_starting_idx, slot)

        map = Map.put(map, slot_starting_idx, {:file, file_id, file_width})
        slot_width = elem(slot, 2)

        empty_blocks =
          if slot_width > file_width do
            BiMultiMap.put(
              empty_blocks,
              slot_starting_idx + file_width,
              {:empty_space, 0, slot_width - file_width}
            )
          else
            empty_blocks
          end

        {map, empty_blocks}
      end
    end)
    |> elem(0)
    |> Enum.sort()
    |> Enum.map(fn {idx, {_, file_id, width}} ->
      {{idx, idx + width - 1}, file_id}
    end)
  end

  def look_for_empty_space(empty_blocks, empty_space_before_idx, size) do
    max_slot_size = BiMultiMap.values(empty_blocks) |> Enum.map(&elem(&1, 2)) |> Enum.max()

    if size > max_slot_size do
      nil
    else
      slot_size_to_search = {:empty_space, 0, size}

      empty_spaces =
        BiMultiMap.get_keys(empty_blocks, slot_size_to_search)
        |> Enum.reject(&(&1 >= empty_space_before_idx))
        |> Enum.sort()

      if length(empty_spaces) == 0 do
        look_for_empty_space(empty_blocks, empty_space_before_idx, size + 1)
      else
        {hd(empty_spaces), slot_size_to_search}
      end
    end
  end
end

[stevensonmt]

Just realized I had set my Github repo to private b/c the AoC dev does not want input files public and I never remember to put it in the gitignore. So almost all my previous day’s solutions are not visible. lol.

Anyway here’s day 9 for me. Not fast enough really but gets the right answer. Could probably get a speed up by updating what the max_ndx for searching for files would be in part 2 to avoid searching indices that have already been moved.

defmodule Day9 do
  @test "2333133121414131402"

  @real File.read!(__DIR__ <> "/input.txt") |> String.trim("\n")

  def run(mode) do
    data =
      mode
      |> input()
      |> parse()

    part_1(data) |> IO.inspect(label: :part_1)
    part_2(data) |> IO.inspect(label: :part_2)
  end

  defp input(:test), do: @test
  defp input(:real), do: @real
  defp input(_), do: raise("Please use :test or :real as possible modes to run.")

  defp parse(input) do
    Stream.iterate(0, &(&1 + 1))
    |> Stream.intersperse(".")
    |> Enum.zip(String.graphemes(input) |> Enum.map(&String.to_integer/1))
  end

  defp part_1(data) do
    data
    |> compact()
    |> checksum()
  end

  defp part_2(data) do
    data
    |> into_map()
    |> compact_wo_frag()
    |> checksum_2()
  end

  defp compact(blocks) do
    blocks
    |> Enum.reduce_while({[], Enum.reverse(blocks)}, fn
      {".", space}, {acc, rev_blks} ->
        {:cont, move_blocks(space, rev_blks, acc)}

      {ndx, _blks}, {acc, [{ndx, remaining} | _] = _rev_blks} ->
        {:halt, append_blocks(acc, remaining, ndx)}

      {ndx, blks}, {acc, rev_blks} ->
        {:cont, {append_blocks(acc, blks, ndx), rev_blks}}
    end)
  end

  defp into_map(blocks) do
    blocks
    |> Enum.reduce({0, %{}}, fn {ndx_or_space, blks}, {last_dskmp_ndx, diskmap} ->
      max_ndx = last_dskmp_ndx + blks

      dm =
        Map.put(diskmap, last_dskmp_ndx, {blks, ndx_or_space})

      {max_ndx, dm}
    end)
  end

  defp compact_wo_frag({max_ndx, map}) do
    do_compact_wo_frag(0, max_ndx, map, %{})
  end

  defp do_compact_wo_frag(curr, max_ndx, _, acc) when curr > max_ndx, do: acc

  defp do_compact_wo_frag(curr, max_ndx, map, acc) do
    case Map.get(map, curr) do
      nil ->
        do_compact_wo_frag(curr + 1, max_ndx, map, acc)

      {blks, "."} ->
        move_files(blks, curr, max_ndx, max_ndx, map, acc)

      {blks, n} ->
        acc =
          0..(blks - 1)
          |> Enum.reduce(acc, fn i, a -> Map.put(a, curr + i, n) end)

        do_compact_wo_frag(curr + blks, max_ndx, map, acc)
    end
  end

  defp move_files(space, curr, search_ndx, max_ndx, map, acc) when curr >= search_ndx,
    do: do_compact_wo_frag(curr + space, max_ndx, map, acc)

  defp move_files(space, curr, search_ndx, max_ndx, map, acc) do
    case Map.get(map, search_ndx) do
      nil ->
        move_files(space, curr, search_ndx - 1, max_ndx, map, acc)

      {_, "."} ->
        move_files(space, curr, search_ndx - 1, max_ndx, map, acc)

      {blks, n} when blks == space ->
        acc =
          0..(blks - 1)
          |> Enum.reduce(acc, fn i, a -> Map.put(a, curr + i, n) end)

        do_compact_wo_frag(curr + blks, max_ndx, Map.delete(map, search_ndx), acc)

      {blks, n} when blks > space ->
        move_files(space, curr, search_ndx - 1, max_ndx, map, acc)

      {blks, n} ->
        acc =
          0..(blks - 1)
          |> Enum.reduce(acc, fn i, a -> Map.put(a, curr + i, n) end)

        move_files(
          space - blks,
          curr + blks,
          search_ndx - 1,
          max_ndx,
          Map.delete(map, search_ndx),
          acc
        )
    end
  end

  defp move_blocks(0, rev_blks, acc), do: {acc, rev_blks}

  defp move_blocks(space, [{".", _} | rest], acc), do: move_blocks(space, rest, acc)

  defp move_blocks(space, [{ndx, blks} | rest], acc) when blks > space do
    {append_blocks(acc, space, ndx), [{ndx, blks - space} | rest]}
  end

  defp move_blocks(space, [{ndx, blks} | rest], acc),
    do:
      move_blocks(
        space - blks,
        rest,
        append_blocks(acc, blks, ndx)
      )

  defp append_blocks(diskmap, blocks, ndx) do
    diskmap ++ (Stream.cycle([ndx]) |> Enum.take(blocks))
  end

  defp checksum(diskmap) do
    diskmap
    |> Enum.with_index()
    |> Enum.reduce(0, fn {id, pos}, acc -> acc + id * pos end)
  end

  defp checksum_2(diskmap) do
    diskmap
    |> Enum.reduce(0, fn {ndx, val}, sum -> sum + ndx * val end)
  end
end

Day9.run(:real)