2024 Day9

Day 9: Disk Fragmenter

Day 9: Disk Fragmenter

Part 1

コードの主な機能

1. parse_disk/1

   • 入力文字列を2文字ずつ区切って処理
   • 最初の数字はファイルサイズ、次の数字は空き容量
   • ファイルIDは0から順番に割り当て
   • 結果は {:file, id} と :free のリスト

2. compact/1

   • 右端のファイルから左端の空き領域へ移動を繰り返す
   • 移動可能なブロックがなくなるまで再帰的に実行

3. find_move/1

   • 次に移動すべきファイルと移動先を特定
   • 右端のファイルと左端の空き領域のペアを返す

4. rightmost_file_after_free/1とleftmost_free/1

   • 移動元のファイル位置と移動先の空き領域位置を探索

5. calculate_checksum/1

   • 各ファイルの位置×IDの総和を計算

処理の流れ

1. 入力例 “12345” の場合:

   入力: "12345"
   解析後: [file(0), free, free, file(1), free, free, free, free, file(2), free, free, free, free, free]
   圧縮後: [file(0), file(2), file(1), free, free, free, free, free, free, free, free, free, free, free]

2. チェックサム計算:

   • 各ファイルの位置×IDを合計
   • 空き領域は計算に含めない

このコードは、ファイルシステムの断片化を解消し、ファイルを左側に寄せる処理を実装しています。

defmodule AdventOfCode2024Day9Part1 do
  def solve(input) do
    input
    |> String.trim()
    |> parse_disk()
    |> compact()
    |> calculate_checksum()
  end

  defp parse_disk(input) do
    input
    |> String.graphemes()
    |> Enum.map(&String.to_integer/1)
    |> Enum.chunk_every(2)
    |> Enum.with_index()
    |> Enum.flat_map(fn {[file_size | rest], file_id} ->
      space_size = if rest == [], do: 0, else: hd(rest)
      file_blocks = List.duplicate({:file, file_id}, file_size)
      space_blocks = List.duplicate(:free, space_size)
      file_blocks ++ space_blocks
    end)
  end

  defp compact(blocks) do
    case find_move(blocks) do
      nil -> blocks
      {from, to} ->
        blocks
        |> List.update_at(to, fn :free -> Enum.at(blocks, from) end)
        |> List.update_at(from, fn _ -> :free end)
        |> compact()
    end
  end

  defp find_move(blocks) do
    case rightmost_file_after_free(blocks) do
      nil -> nil
      file_pos ->
        case leftmost_free(blocks) do
          nil -> nil
          free_pos when free_pos < file_pos -> {file_pos, free_pos}
          _ -> nil
        end
    end
  end

  defp rightmost_file_after_free(blocks) do
    blocks
    |> Enum.with_index()
    |> Enum.reverse()
    |> Enum.find_value(fn
      {{:file, _}, idx} ->
        if Enum.any?(blocks, &amp;(&amp;1 == :free)), do: idx
      _ -> nil
    end)
  end

  defp leftmost_free(blocks) do
    blocks
    |> Enum.with_index()
    |> Enum.find_value(fn
      {:free, idx} -> idx
      _ -> nil
    end)
  end

  defp calculate_checksum(blocks) do
    blocks
    |> Enum.with_index()
    |> Enum.reduce(0, fn
      {{:file, id}, pos}, sum -> sum + (pos * id)
      _, sum -> sum
    end)
  end
end

# Test with sample input
input = "2333133121414131402"
AdventOfCode2024Day9Part1.solve(input) |> IO.puts()

Part 2

主な変更点

Part 1との違いは、個別のブロックではなくファイル全体を一度に移動する点です。

コードの構造

1. データ構造

   • {id, size, position} のタプルでファイルを表現
   • id: ファイルID
   • size: ファイルサイズ
   • position: 開始位置

2. parse_input/1 と parse_blocks/3

   # 入力例: "12345" の場合
   # [{0,1,0}, {1,3,3}, {2,5,7}] のような形式に変換

3. compact/1

   • ファイルをIDの降順にソート
   • 各ファイルを左側の最も近い空き領域へ移動を試みる

4. try_move_file/2

   • ファイル全体が収まる空き領域を探す
   • 現在位置より左側にある場合のみ移動

5. find_space/3

   • MapSetを使用して使用中の領域を管理
   • ファイルサイズ分の連続した空き領域を探索

6. checksum/1

   • 各ファイルの位置×IDの総和を計算
   • ファイル内の各ブロックについて計算

処理の流れ例

入力: "12345"
1. 初期状態: 0..111....22222
2. ID=2から処理: 022111....2..
3. ID=1から処理: 022111222....

このアプローチにより、Part 1よりも効率的なディスク最適化が可能になります。

defmodule AdventOfCode2024Day9Part2 do
  def solve(input) do
    disk = parse_input(input)
    compact(disk) |> checksum()
  end

  defp parse_input(input) do
    input
    |> String.trim()
    |> String.graphemes()
    |> Enum.map(&String.to_integer/1)
    |> Enum.chunk_every(2)
    |> Enum.with_index()
    |> parse_blocks([], 0)
  end

  defp parse_blocks([], acc, _), do: Enum.reverse(acc)
  defp parse_blocks([{[size, space], id} | rest], acc, pos) do
    block = {id, size, pos}
    parse_blocks(rest, [block | acc], pos + size + space)
  end
  defp parse_blocks([{[size], id} | rest], acc, pos) do
    block = {id, size, pos}
    parse_blocks(rest, [block | acc], pos + size)
  end

  defp compact(disk) do
    disk
    |> Enum.sort_by(&elem(&1, 0), :desc)
    |> Enum.reduce(disk, &try_move_file(&1, &2))
  end

  defp try_move_file(file, disk) do
    {id, size, pos} = file
    case find_space(disk, size, pos) do
      nil -> disk
      new_pos when new_pos < pos ->
        disk
        |> Enum.map(fn
          {^id, s, _} -> {id, s, new_pos}
          other -> other
        end)
      _ -> disk
    end
  end

  defp find_space(disk, size, max_pos) do
    occupied = MapSet.new(
      for {_, s, p} <- disk,
          i <- p..(p + s - 1),
          do: i
    )

    0..max_pos
    |> Enum.find(fn start ->
      Enum.all?(start..(start + size - 1), &amp;(!MapSet.member?(occupied, &amp;1)))
    end)
  end

  defp checksum(disk) do
    for {id, size, pos} <- disk,
        p <- pos..(pos + size - 1),
        reduce: 0 do
      acc -> acc + (p * id)
    end
  end
end

# Test with sample input
input = "2333133121414131402"
IO.puts AdventOfCode2024Day9Part2.solve(input)