advent_of_code/elixir/livebook/2024/day9.livemd

AOC 2024 Day 9

Section

input = ""

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

Fragmenter.parse_disk_map(input)
|> Fragmenter.defrag()
|> Fragmenter.checksum()

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

Fragmenter2.parse_disk_map(input)
|> Fragmenter2.defrag()
|> Fragmenter2.checksum()