【42 Tokyo】push_swapをターク(Turk)アルゴリズムで解いてみた

こんにちは、ウタです！

現在42Tokyoに通っておりゴリゴリと課題を進めております。
先日push_swapを提出しましたので、僕がどのように何を考えながらして作ったのかまとめていきます。

課題の概要

push_swapは簡単にいうとソートアルゴリズムを勉強する課題になっています。

ソートアルゴリズムは、データを整理・並び替えするためのアルゴリズムです。
機械学習で扱う大量のデータを、一定の規則に従って整列させるときなどに使われます。

引用 : https://zenn.dev/zenn/articles/markdown-guide

課題では、2つのスタック（AとB）と決められたオペレーションを使って、スタックAの整数を昇順に最小の操作回数でソートするC言語のプログラムを作成する課題です。
操作回数のベンチマークとしてはこんな感じ。

• 引数が100個なら700回未満
• 引数が500個なら5500回未満

コレがクリアできていたらこの課題は100点です！💯

オペレーションはこんな感じ。

• sa (swap a): スタックAの上位2つの要素を交換
• sb (swap b): スタックBの上位2つの要素を交換
• ss: saとsbを同時実行
• pa (push a): スタックBの先頭要素をスタックAの先頭に移動
• pb (push b): スタックAの先頭要素をスタックBの先頭に移動
• ra (rotate a): スタックAの全要素を上にシフト（先頭が末尾になる）
• rb (rotate b): スタックBの全要素を上にシフト（先頭が末尾になる）
• rr: raとrbを同時実行
• rra (reverse rotate a): スタックAの全要素を下にシフト（末尾が先頭になる）
• rrb (reverse rotate b): スタックBの全要素を下にシフト（末尾が先頭になる）
• rrr: rraとrrbを同時実行

図解で説明すると下記のような感じです。
引数として入ってきた数字を
（プログラム的には./push_swap 6 3 1 4 2 5 7のように実行されます）

初期状態のスタックA

下の画像のようにスタックAに昇順（小さい数字が上に）に並び替えます。

昇順にソート済みのスタックA

僕が選んだアルゴリズム

本課題の想定された最大引数は500個であり、この引数を持ってして候補に上がるアルゴリズムは下記になるかと思います。

アルゴリズム	内容	実装難易度	100要素オペレーション数	500要素オペレーション数
Turkアルゴリズム	最もコストの安い要素を毎回選択してソート	中級	500-700	4000-5500
基数ソート (Radix Sort)	ビット単位でスタックを分割してソート	中級〜上級	400-600	3000-4500
チャンクベース手法	数値を複数のチャンクに分けて段階的にソート	初級〜中級	600-800	5000-6500
LIS (最長増加部分列)	ソート済み部分をスタックAに残し、必要な部分のみ移動	上級	400-650	3500-5000
ハイブリッドアプローチ	スタックサイズに応じて異なるアルゴリズムを使い分け	上級	最適化可能	最適化可能

ベンチマーク目標: 100要素で700未満、500要素で5500未満

備考:

• 実装難易度は概算であり、個人の経験により異なる
• オペレーション数は実装方法により変動する

この中でも僕はTurkアルゴリズムを採用しました。
理由としては、僕の調査によると一番5500回を下回るのが確実そうだったからです。
結論から言うと、僕は引数500の時に5500回を下回ったり、下回らなかったりでした😅
実装方法だったりこうしておけばもっと手数減らせたかもなと思う部分は後述していますので参考にしていただければと思います。
ちなみに僕の周りでは基数ソートとチャンクベース手法が多かったです。Turkアルゴリズムでやっている人は少なかったですね、、、（それ故にあまり人に相談できない辛さは少しありました😅）

実装1 引数をパース

それでは実装に入っていきます。
最初に引数をスタックAにパースするところから始まるのですが、そこで僕が悩んだ箇所について紹介させてください。

本課題では2つのパターンでコマンドライン引数から値を受け取ります。

# パターン1 通常のケース
$>./push_swap 2 1 3 6 5 8

# パターン2 チェッカーを使用する場合
$>ARG="2 1 3 6 5 8"; ./push_swap $ARG | ./checker_OS $ARG

レビューを受ける際も上記の2パターンでテストされるので、どちらの引数のパターンにも対応させる必要があります。
また、バリデーションとして下記のようなケースを想定しなければなりません。

1. 引数なし
$> ./push_swap               # 何も表示せずプロンプトに戻る

2. 整数以外の文字列
$>./push_swap 1 2 abc 4      # 数字以外の文字列
$>./push_swap 1 2.5 3        # 小数点
$>./push_swap 1 2+ 3         # 不正な符号
$>./push_swap 1 "2 3" 4      # 空白を含む文字列

3. Intの範囲外
$>./push_swap 2147483648     # INT_MAX + 1
$>./push_swap -2147483649    # INT_MIN - 1
$>./push_swap 9999999999999  # 明らかに大きすぎる値

4. 重複した値
$>./push_swap 1 2 3 2 4      # 2が重複
$>./push_swap 5 5            # 同じ値が2つ
$>./push_swap 1 2 3 1        # 1が重複

5. 空文字列や不正な引数
$>./push_swap ""             # 空文字列
$>./push_swap 1 "" 3         # 空文字列が混在
$>./push_swap "   "          # 空白のみ

6. 符号のみや不完全な数値
$>./push_swap +              # 符号のみ
$>./push_swap -              # 符号のみ  
$>./push_swap 1 + 3          # 不完全な符号
$>./push_swap --5            # 二重符号
$>./push_swap ++3            # 二重符号

7. 先頭ゼロ（実装による）
$>./push_swap 01 02 03       # 先頭ゼロ（許可するかは実装次第）

これらの中で異なるパターンの引数をパースする部分とIntの範囲内かどうかのバリデーションが少し厄介だと感じました。

異なるパターンの引数

まずこちら。

# パターン1 通常のケース
$>./push_swap 2 1 3 6 5 8

# パターン2 チェッカーを使用する場合
$>ARG="2 1 3 6 5 8"; ./push_swap $ARG | ./checker_OS $ARG

パターン1だけの想定だったらどれだけ実装が楽なことか、、、
パターン2の想定をしないといけないので文字列をスペースで区切るsplitが必須になってきます。
splitで区切るやり方は、通常であればコマンドライン引数でacの値で判別するやり方を取るのがベストかと思います。

# 多分コレがベスト

int main(int ac, char **av) {
   char **args;
   
   if (ac <= 1) {
       // 引数なしの場合は何も表示せず正常終了
       return 0;  
   }
   
   if (ac == 2) {
       // パターン2: "./push_swap '2 1 3 6 5 8'" 
       // 文字列をスペースで分割する処理
       args = split_and_validate(av[1]);
   } else {
       // パターン1: "./push_swap 2 1 3 6 5 8"
       // 各引数をそのまま処理
       args = validate_args(ac - 1, &av[1]);
   }
   
   if (!args) {
       write(2, "Error\n", 6);
       return (1);
   }
   
   // ソート処理
   push_swap(args);
   
   // メモリ解放
   free_args(args);
   return (0);
}

このやり方だと処理速度は速くなるしわかりやすくもあるのですが、分岐が多くなったり共通で使えるバリデーションやパース用の関数の配置の仕方など悩んでしまい、結局全てsplitする手法を取りました。

# 僕のやり方(*実際のコードとは異なります。雰囲気だけでもわかってもらえれば)
int main(int ac, char **av)
{
    char **args;

    if (ac < 2)
        return (0);
    
    // 全引数をjoinしてからsplit
    args = join_and_split(av);
    if (!args || !validate_args(args))
    {
        write(2, "Error\n", 6);
        return (1);
    }
    
    // ソート処理
    push_swap(args);
    
    free_args(args);
    return (0);
}

入ってくる引数がスペース区切りの文字列でもそうでなくてもsplitしていくので引数が500個の時は結構時間かかります。しかし、本課題で見られるのは処理回数であって処理速度ではないので良いかなと。また、本題はやはりソートの実装なのでここにあまり時間をかけたくないと言う本音もあります😅

あんまり意味はないのですが、全splitすることで下記のようなパターンにも対応可能という利点もあります。

# パターン1 通常のケース
$>./push_swap 2 1 3 6 5 8

# パターン2 チェッカーを使用する場合
$>ARG="2 1 3 6 5 8"; ./push_swap $ARG | ./checker_OS $ARG

# パターン3 文字列と数字の混合パターン（ないと思うけど対応可能）
$>./push_swap 2 1 3 6 5 8 "9 10 0"

Intのバリデーション

続いて引数の数字がIntの範囲内かどうかをバリデートする処理を考えていきます。
コレに関してもatolと文字列として受け取るの2つ方法があります。

# 方法1 ft_atolを使う
int is_valid_int(char *str)
{
    long num = ft_atol(str);
    return (num >= INT_MIN && num <= INT_MAX);
}
*atolは「ascii to long」の意味です。atolならatoiよりも広範囲に数字を取得できます。

# 方法2 文字列として受け取り桁数でIntの範囲内か見る
int	ft_is_int(char *str)
{
	int	len;
	int	is_minus;

	is_minus = 0;

    // ここで符号を取り除き、マイナスフラグを立てておく
	if (*str == '-' || *str == '+')
	{
		if (*str == '-')
			is_minus = 1;
		str++;
	}
    // 全て数字かをチェック
	if (!is_all_digits(str))
		return (0);

    // 0埋めをスキップさせる
	while (*str == '0' && *(str + 1))
		str++;

	len = ft_strlen(str);
	if (len > 10)
		return (0); // 10桁以上だったら確実にintの範囲外
	if (len < 10)
		return (1); // 10桁以下だったら確実にintの範囲内

    // 丁度10桁だったら最大値と最小値を比較
    // マイナスだったら最小値と比較
	if (is_minus)
		return (ft_strncmp(str, "2147483648", len) <= 0); // intの最小値
    // プラスだったら最大値と比較
	else
		return (ft_strncmp(str, "2147483647", len) <= 0); // intの最大値
}

*どちらもざっくりしたコードで正しくはないので雰囲気として見てください🙇🏻💦

一つ目のft_atolを使用する方法がいいとは思うのですが、レビューする人が人間である以上longよりも大きい値を入力することも考えられました。じゃあ、ft_atoll（ascii to long long）にすればいいんじゃない？という声もあるかもしれないですが、こちらも同様にlong long以上を入力しようとするレビュアーがいないとも限らないです。パース前の引数を数字として扱おうとするとこのように最大値と最小値に苦しめられ続けるので、僕は方法2を取りました。

方法2では引数を文字列として扱います。
入ってきた文字列の符号を取り除いた後;

• 10桁以下であれば確実にIntの範囲内 → return 1✅;
• 10桁以上であれば確実にIntの範囲外 → return 0❌;
• 10桁丁度の場合
  • 負の数の場合「2147483648」と比較して小さければ return 1✅;
  • 正の数の場合「2147483647」と比較して小さければ return 1✅;

のようにしてバリデーションします。
途中まで実装できるかどうか怪しかったのですが、strcmpの存在を思い出してからはすんなり実装できました。この方法だと少し複雑ではあるのですが、実装が簡単でエラー漏れしにくいのかなと思います。
また、個人的にバリデーションする時もパースする時もft_atoiやft_atolなどを使用するのが二度手間に感じてしまい、こちらで実装することにしました。

実装2 タークアルゴリズムについて

そんなこんなでバリデーションを終え、引数を全て安全にスタックAにパースしてきました。
ここから前述したタークアルゴリズムについて解説していきます。

タークアルゴリズムの処理の流れは

1. スタックAから無条件で2つの要素をスタックBに移す
    * スタックBにmax/minの基準を作るため
2. スタックAの残りが3つになるまでスタックBに要素を移す
    * スタックBに移す際はスタックB内が降順になるように移動させる
    * 各要素についてスタックAとスタックBの回転コストを計算し、合計が最小の要素から移動させる
3. スタックAが3つになったら昇順にソートする
4. 降順にソートされたスタックBからスタックAに移す
5. 完成

となります。
コレだけで実装始められちゃう天才は以降の記事は必要ないので実装に取り掛かってください😅

スタックAからスタックBにプッシュ

図解で一つずつ解説していきます。

まずは初期状態

初期状態のスタックA

初期状態時点でスタックAに3つ以上要素がある場合は、問答無用でスタックBに2つプッシュします。

スタックAからスタックBに2つプッシュ

スタックBに「6」と「3」をプッシュ

スタックAの残りが3つになるまでスタックBに要素を移す

2つプッシュした後は、コスト計算をしながらスタックBに要素をプッシュしていきます。
コスト計算の際は、現在のスタックAの位置からスタックB内の降順に移動させるまでのオペレーション回数を計算していきます。例外として、最大値と最小値は両方とも、スタックBの現在の最大値の上に配置します。

スタックAの「1」の移動コスト計算

まず上から見ていきましょう。
スタックAの「1」の移動コスト計算をしていきます。
「1」は最小値なのでスタックBの最大値「6」の上に配置されます。従ってrb → pbとなり、コストは2です。

スタックAの「1」をスタックBにプッシュするときのコストは2

スタックAの「4」の移動コスト計算

続いてスタックAの「4」の移動コスト計算をしていきます。
「4」のターゲットとなるノードは「3」なので、スタックBにプッシュした時に「4」→「3」となればいいわけです。なので、ra → pbとなり、コストは2になります。

スタックAの「4」をスタックBにプッシュするときのコストは2

スタックAの「2」の移動コスト計算

次のスタックAの「2」の移動コスト計算をします。
「2」は最小値なのでスタックBの最大値「6」の上に配置されます。従ってra → ra → rb → pbとなります。raとrbが同時に行われる場合はrrで一つのオペレーションとして扱えるので、rr → ra → pbとなり、コストは3になります。

スタックAの「2」をスタックBにプッシュするときのコストは3

スタックAの「5」の移動コスト計算

スタックAの「5」の移動コスト計算をします。
「5」のターゲットとなるノードは「3」なので、rra → rra → pbとなり、コストは3になります。

スタックAの「5」をスタックBにプッシュするときのコストは3

スタックAの「7」の移動コスト計算

最後にスタックAの「7」の移動コスト計算をします。
「7」は最大値なのでスタックBの最大値「6」の上に配置されます。従ってrra → rb → pbとなります。コストは3です。

スタックAの「5」をスタックBにプッシュするときのコストは3

計算結果（1回目）

計算の結果、最小コスト2の「1」をスタックBにプッシュします。

スタックAの「1」をスタックBにプッシュ

このようにしてコストを計算し、スタックAの中身が3になるまで続けます。

計算結果（2回目）

2回目の計算結果は下記のようになります。

2回目の計算結果

「4」が最小コストなので「4」をスタックBにプッシュします。

「4」をスタックBにプッシュ

残り3つになったスタックAを「昇順」にソート

さて、ここでスタックAの要素が残り3つになりました。
ここでスタックBへプッシュする処理を終了し、次の処理に移ります。

次の処理ではこの3つの要素を昇順に並び替えます。
といっても要素が3つだと6パターンしか存在せず、最大オペレーション数も簡単です。

要素が3つの時の6パターン

1. 「123」の場合 → ソート済み、何もしない
2. 「132」の場合 → rra → sa
3. 「213」の場合 → sa
4. 「231」の場合 → rra
5. 「312」の場合 → ra
6. 「321」の場合 → ra → sa

今回の例だと「2」「5」「7」が残っており、既にソート済みなので何もしません。

スタックBからスタックAに要素を戻す

スタックAが3つの要素でソートされたら、次はスタックBに保存されている要素を降順から昇順に変換しながらスタックAに戻していきます。

スタックBからスタックAへのプッシュバック処理

現在の状態はこのようになっています。

スタックAがソート済み、スタックBに降順で要素が保存されている状態

スタックBからスタックAに要素を戻す際のポイントは、スタックA内での正しい挿入位置を見つけることです。各要素について、スタックA内のどの位置に挿入すれば昇順が維持されるかを計算し、その位置までスタックAを回転させてからプッシュします。

スタックBの「4」をスタックAに戻す

まず、スタックBの一番上にある「4」をスタックAに戻します。
「4」は「2」より大きく「5」より小さいので、「5」の直前に配置する必要があります。
現在「5」はスタックAの2番目（index 1）にあるので、「5」を一番上に持ってくるためにraを1回実行します。

ra実行

その後、paで「4」をスタックAにプッシュします。

pa実行

スタックBの「3」をスタックAに戻す

次に、スタックBの「3」をスタックAに戻します。
「3」は「2」より大きく「4」より小さいので、「4」の直前に配置する必要があります。
現在「4」はスタックAの一番上にあるので、回転は不要です。直接paで「3」をプッシュできます。

pa実行

スタックBの「1」をスタックAに戻す

次に、スタックBの「1」をスタックAに戻します。
「1」は最小値なので、スタックAの最小値「2」の直前に配置されるべきです。
「2」はスタックAの最後にあるので、「2」を一番上に持ってくるためにrraを1回実行します。

rraを実行

その後、paで「1」をスタックAにプッシュします。

paを実行

スタックBの「6」をスタックAに戻す

最後に、スタックBの「6」をスタックAに戻します。
「6」は「7」より小さいので、「7」の直前に配置する必要があります。
「7」を一番上に持ってくるためにrraを行います。

rraを実行

その後paで「6」をプッシュします。

paを実行

最終調整

スタックBからスタックAにプッシュし終わった段階で、まだ昇順にソートされていないので、ra raを実行してスタックAを昇順にします。

ra raを実行

コレでソートが完了しました。

改善点について

コレで僕が実装したタークアルゴリズムの全容は概ね解説できたかと思います！
長かったですね、、、😅 ここまで読んでくれた方がいたら大変嬉しいです＾＾
（個人的に図の作り替えに時間がかかりましたね💦）

ちなみに本課題の僕のスコアは97点でした。引数が500の時にオペレーション数が5500を上回ってしまうことがあったのでこのスコアになりました。
あと50回少なく実装できていたら100点だったかと思います。

コレらを踏まえてこうしておけば100点になっていたのではないかという惜しかった点を2点あげて行きます。

改善点1 プッシュバックの際にもコスト計算を使う

見出しの通りなのですが、スタックBからスタックAにプッシュバックする時にもコスト計算をし、一番安いコストの要素から移動させる手法を取ればオペレーション数が減ったのではないかと考えています。
現状僕の実装では、プッシュバックの際にはスタックBの上から順番に処理を行っていますが、これが引数が増えるほど無駄が増えていって5500回を上回る事例のトリガーになっていると推測しています。

ただ、実装にも少し時間が必要だったしより複雑になると思い諦めてしまいました、、、

改善点2 スタックAからプッシュする際の残りを3→20に設定する

こちらレビュー中に提案してもらった方法で試していない分確実性はないのですが、やってみても良かったなと思っています。
僕のレビューをしてくださった方のご友人も僕と同じソート方法で実装しており、僕と同じように何回かに1回は5500回を上回ってしまうのに悩んでいたそうで。その方がスタックAからプッシュする際に残りが20になるまでプッシュするやり方に変えたところ5500回を確実に下回ることができたそうです。

スタックAが20個になった時点のソートを追加実装する必要はありますが、試してみる価値はあったかなと。

まとめ

push_swapプロジェクトを通して、ソートアルゴリズムの奥深さと実装の難しさを改めて実感しました。

学んだこと

アルゴリズムの選択の重要性
複数のソートアルゴリズムを比較検討し、ベンチマーク目標に対してTurkアルゴリズムを選択しました。実装難易度と効率のバランスを考慮した選択でしたが、結果として500要素で5500回を下回ったり上回ったりと、完璧ではありませんでした。

実装の細かな判断が結果を左右する
引数のパース方法やバリデーション手法など、一見些細に思える部分でも、保守性や効率性に大きく影響することを学びました。特にsplitを使った統一的な処理は、コードの可読性を高める良い判断だったと思います。

理論と実装のギャップ
アルゴリズムの理論を理解していても、実際にコードで実装するとなると様々な細かい判断が必要でした。コスト計算の最適化や、最大値・最小値の配置ルールなど、実装で学ぶことが多くありました。
今後への活かし方
今回の経験を踏まえて、今後のプロジェクトでは以下の点を意識していきたいと思います：

• 事前の設計をより入念に行う: アルゴリズムの選択段階でより多くの検証を行う
• 実装前のプロトタイピング: 小規模なテストで方向性を確認してから本実装に入る
• パフォーマンス測定の習慣化: 定期的にベンチマークを取り、改善点を早期発見する

97点という結果は悔しくもありましたが、その分多くの学びを得られたプロジェクトでした。次回は100点を目指して、より効率的なアルゴリズムの実装に挑戦していきたいと思います！
42Tokyoでの学習はまだまだ続きますが、このpush_swapプロジェクトで得た経験を活かして、今後の課題にも取り組んでいきます💪
最後まで読んでいただき、ありがとうございました！
何か質問やコメントがあれば、気軽にお声かけください😊