Advent of Code 2024を解いてみる[1日目 Part1]

少し出遅れましたが、今年もAoCの時期になりました。
いつもはただ解いて終わりにしていましたが、今年は寄り道して調べ物をしながら問題に取り組もうと思います。
「ここはこうしたほうがいいんじゃないか」「ここは違うような」というコメントがあればぜひ教えてください！

それでは早速・・・

1日目の問題 (https://adventofcode.com/2024/day/1)

Part1

Example Input:
3 4
4 3
2 5
1 3
3 9
3 3

Within each pair, figure out how far apart the two numbers are; you'll need to add up all of those distances. For example, if you pair up a 3 from the left list with a 7 from the right list, the distance apart is 4; if you pair up a 9 with a 3, the distance apart is 6.

In the example list above, the pairs and distances would be as follows:

The smallest number in the left list is 1, and the smallest number in the right list is 3. The distance between them is 2.
The second-smallest number in the left list is 2, and the second-smallest number in the right list is another 3. The distance between them is 1.
The third-smallest number in both lists is 3, so the distance between them is 0.
The next numbers to pair up are 3 and 4, a distance of 1.
The fifth-smallest numbers in each list are 3 and 5, a distance of 2.
Finally, the largest number in the left list is 4, while the largest number in the right list is 9; these are a distance 5 apart.
To find the total distance between the left list and the right list, add up the distances between all of the pairs you found. In the example above, this is 2 + 1 + 0 + 1 + 2 + 5, a total distance of 11!

Your actual left and right lists contain many location IDs. What is the total distance between your lists?

突際に頭に浮かんだのは...
0. Inputを左のリストと右のリストに分ける（下処理）
1. 左のリストと右のリストをソートでそれぞれ並び替える
2. 並べ替えられた左のリストを元にループを回して、左右のアイテムの絶対値を足していく

一番効率的かはわかんないけど、これでいけそう。ということで実装に移ります。

0. Inputを左のリストと右のリストに分ける（下処理）

index.js

const parseInput = (lists) => {
  const lines = lists.trim().split("\n");

  const leftSide = [];
  const rightSide = [];

  lines.forEach((line) => {
    const [left, right] = line.trim().split(/\s+/);
    leftSide.push(Number(left));
    rightSide.push(Number(right));
  });

  return [leftSide, rightSide];
};

const [leftList, rightList] = parseInput(input);

1. 左のリストと右のリストをクイックソートでそれぞれ並び替える

index.js

// Sort each list
leftList.sort((a, b) => a - b);
rightList.sort((a, b) => a - b);

2. 並べ替えられた左のリストを元にループを回して、左右のアイテムの絶対値を足していく

index.js

let totalDistance = 0;

leftList.forEach((id, index) => {
  const distance = Math.abs(id - rightList[index]);
  totalDistance += distance;
});

console.log("Total Distance: ", totalDistance);

目視でコードを確認した後に、与えられたinputで走らせるとPASSしました。
ということで、1日目のPart１はとりあえず自力で解くことができました。

コード全体はこちらから
https://github.com/epmt6528/aoc-2024/blob/main/day1/index.js

寄り道 - 計算量

時間計算量

ソート

各リストを昇順にソートする部分がこのアルゴリズムの最も計算量が高い部分です。ソートには通常、O(nlogn)の計算量がかかる。（nはリストの長さ）２つのリストをソートするため、O(nlogn + mlogm)(mは２つ目のリストの長さ)。但し、この問題では２つのリストの長さは同じようなので、O(2nlogn)、つまり、O(nlogn)とできる。

差の計算

ソート後に各要素を順番にペアリングして差を計算する部分は、リストの長さに比例する計算量、すなわちO(min(n,m))。但し、この問題では２つのリストの長さは同じようなので、O(2n)、つまり、O(n)。
したがって、全体の時間計算量はO(nlogn+n)。実際には、ソートの計算量が支配的なので、ほとんどの場合でO(nlogn)に近い計算時間がかかる。

空間計算量

ソートはリストを「その場で」操作するため、追加のメモリをほとんど必要としません。（ただし、一部のソートアルゴリズムでスタックメモリが少し使われることがあるそうです）。
入力リスト自体を除けば、アルゴリズムの空間計算量はO(1)です。

寄り道 - JavaScriptのsortメソッドとカスタムクイックソートの効率性の比較

最近、クイックソートなるものを見かけたのでJSのsortとどちらが効率的なのかを調べてみました。

JavaScriptのsorメソッド　計算量: O(nlogn) 空間計算量: O(n)

V8などのモダンなJavaScriptエンジンではTimsortを使っているらしい。

Timsort

Timsortは2002年にTim PetersがPythonのソートアルゴリズムとして設計したマージソートと挿入ソートのハイブリッドアルゴリズム。
Timsortは配列をrunという部分的に整列済みのセグメントに分割して、これらのrunをマージしていくことで全体をソートする。
1. runの検出...配列の要素を順に調べ、増加または減少の連続部分列をrunとして検出
2. runのソート...runが短い場合は挿入ソートを使用してソート。（挿入ソートは小規模データに強いらしい）
3. runのマージ...runが十分に整列済みになったら、マージソートを使用してrun同士を統合

カスタムクイックソート　計算量: O(nlogn) 空間計算量: O(n)

const quickSort = (array) => {
  if (array.length < 2) return array;

  const pivot = array[array.length - 1];
  const left = array.filter((el) => el < pivot);
  const right = array.filter((el) => el > pivot);
  const middle = array.filter((el) => el === pivot);

  return [...quickSort(left), ...middle, ...quickSort(right)];
};

クイックソートは配列をピボットを基準に分割して再帰的に処理する。データが既に整列済みで最後の要素をピボットにすると計算量が増えてします。(O(n^2))

まとめ

JavaScriptのsortメソッドは、最適化された実装で、カスタムクイックソートよりも効率的で信頼性がある。特に大きなデータセットや実際のアプリケーションではsortを使うべき。
クイックソートの実装は学習目的や特殊なソートロジックが必要な場合に限って有用。

以上が1日目のPart 1でした。