42tokyoでの課題『Push_swap』をクリアしたため、その概要や実装方法などをまとめてみました！
取り組み期間：2024年4月23日～5月13日
コーディング時間：約60時間
目次
1. 42tokyoとは
2. Push_swap
3. 作成したプログラム
4. 工夫したことや苦労したこと
5. おわりに
6. 参考文献
1. 42tokyoとは
「クリエイティブな文化とテクノロジーが融合するエンジニア養成機関」
一言で表すとこんなところでしょうか。
気になった方は是非、ホームページをご覧ください。
以下42tokyoホームページより抜粋：https://42tokyo.jp/
42（フォーティーツー）は、フランス発のエンジニア養成機関です。
現在は、世界32カ国にて展開されており、2020年6月に東京校として 42 Tokyo を設立しました。
多くの企業の支援、寄付で支えられており、授業料は完全無料。
学生は、18歳以上であれば経歴を問わず入学することができ、
その後のキャリアは起業をしたり、就職するなど、自由です。
また、基礎カリキュラムを終えたら、他の42キャンパスに留学することも可能です。
革新的で、日々最新にアップデートされるカリキュラム。
世界中の学生たちが、今この瞬間も42でスキルを磨いています。
2. Push_swap
概要
以下、課題PDFより一部抜粋
The Push swap project is a very simple and a highly straightforward algorithm project: data must be sorted.
You have at your disposal a set of integer values, 2 stacks, and a set of instructions to manipulate both stacks.
Your goal? Write a program in C called push_swap which calculates and displays on the standard output the smallest program, made of Push swap language instructions, that sorts the integers received as arguments.
Easy?
We’ll see...
簡単に言えば、「数字を並べ替えろー！ソートしろーー！」という課題です。
この一文だけだとすごく簡単そうに聞こえますけど、、、
制約
プログラム作成にあたって以下のような制約が課せられています。
-
2つのスタック
Stack_a, Stack_bのみを使用してソートしなくてはならない -
スタック間の操作は以下の11個のコマンドしか使用してはならない
instructions Description sa Swap the first two elements of Stack_a sb Swap the first two elements of Stack_b ss Swap the first two elements of both Stack_a and Stack_b pa Move the first element of Stack_b to the top of Stack_a pb Move the first element of Stack_a to the top of Stack_b ra Rotate all elements of Stack_a up by one (the first element moves to the bottom) rb Rotate all elements of Stack_b up by one (the first element moves to the bottom) rr Rotate all elements of both Stack_a and Stack_b up by one rra Rotate all elements of Stack_a down by one (the last element moves to the top) rrb Rotate all elements of Stack_b down by one (the last element moves to the top) rrr Rotate all elements of both Stack_a and Stack_b down by one -
グローバル変数は使用してはならない
-
使用してよい標準関数は以下の5つのみである
read,write,malloc,free,exit -
入力値エラーや、メモリ確保のエラーなど、エラーハンドリングも適切に実装しなくてはならない
この他にも、いくつかの制約が課されていますが、本質的に重要な制約ではないため割愛します。
3. 作成したプログラム
ソースコードを貼っておきます。
コードの流れ
下処理
- コマンドライン引数より数列を受け取ります
- コマンドラインで受け取れるデータは
char型の配列であり、数字（int型）ではないため、受け取った数列をintの配列に格納します - その際、バリデーションチェック（数字かどうか、重複はないかなど）を行い、不適切な場合
errorを返し、プログラムを終了させます
- コマンドラインで受け取れるデータは
-
intの配列に格納された数字を、Stack_aに格納していきます
「どうせStack_aに格納するならintの配列に一度入れる必要ないじゃないか！」という声が聞こえてきそうです。
はい、その通りです（笑）
もともとこの後の操作で座標圧縮をする予定だったため、intの配列だと操作しやすかったのですが、座標圧縮が必要なくなったため不必要でした。
これで下処理は完了です。Stack_aに数字が格納され、Stack_bは空の状態です。
ソートアルゴリズム
ここから11個のコマンドのみを使用してソートしていきます。数字の個数によって使用するソートアルゴリズムを変えています。
理由は、個数が少なければ、ルールをべた書きで記述した方が、より少ない処理で済むからです。
3個以下の場合
- １個：何もしない
- ２個：必要ならSwap
- ３個：全パターンべた書き
ソースコード
void sort_len_3(t_stack *stack)
{
int max_data;
max_data = get_max_data(stack);
if (max_data == stack->top->data)
ra(stack);
else if (max_data == stack->top->next->data)
rra(stack);
if (stack->top->data > stack->top->next->data)
sa(stack);
}
if (len == 2)
sa(stack_a);
else if (len == 3)
sort_len_3(stack_a);
4個の場合
- 一番小さな数字をBへプッシュ
- 残った３個を上記３個のソートアルゴリズムを用いてソート
- Bにいる一番小さな数字をAへプッシュ
ソースコード
void sort_len_4(t_stack *stack_a, t_stack *stack_b)
{
sort_reverse(stack_a);
if (!pb(stack_a, stack_b))
{
free_stack(stack_a);
free_stack(stack_b);
error_print_exit();
}
sort_len_3(stack_a);
if (!pa(stack_a, stack_b))
{
free_stack(stack_a);
free_stack(stack_b);
error_print_exit();
}
}
5個以上の場合
-
BへAの先頭2つをプッシュ
-
Aが３個以下になるまでBへプッシュ
プッシュする際の条件
-
Bの最大以上か、最小以下ならBの最大の上にプッシュ
Bの最大が一番上にくるまでローテ -
それ以外は一番数字が近い、自分より少ない数字の上にプッシュ
上記２つの条件を満たすコマンド数が一番少なくて済むAを選択してプッシュする
-
-
Aが３個以下になったらAをソート
-
Bの全てをAへプッシュする
プッシュする際の条件（１の逆）
- Aの最大以上か、最小以下ならAの最小の上にプッシュ
- それ以外は一番数字が近い、自分より大きい数字の上にプッッシュ
上記2つの条件を満たすコマンド数が一番少なくて済むBを選択してプッシュする
-
Aが昇順になるまでローテーション
参考
Push Swap — A journey to find most efficient sorting algorithm
4. 工夫したことや苦労したこと
⑴構造体の定義
双方向連結循環リスト
この課題では、スタックの柔軟な操作（先頭の数字が最後にまわるなど）が求められるため、
- スタックの前後のポインタが参照できる「双方向連結」
- 先頭と末尾がつながっている（円卓のような）「循環」
の2つの機能を備えた双方向連結循環リストを採用しました。
typedef struct s_node
{
int data;
int index;
t_command command;
struct s_node *next;
struct s_node *prev;
} t_node;
typedef struct s_stack
{
t_node *top;
} t_stack;
この結果、スタック操作を直感的に行うことができるようになりました。
しかし、ノードを新しく作成するときに、malloc（ヒープメモリからのメモリ確保）を行うため、メモリリーク対策に苦労しました。
コマンド操作
私が使用したアルゴリズムでは、スタック間でプッシュを実行する際、各数字ごとに最適なコマンドを保存する必要があります。
そこで以下のような構造体を定義し、各数字ごとに必要なコマンドを記憶していきました。
typedef struct s_command
{
int all;
int ra;
int rra;
int rb;
int rrb;
int rr;
int rrr;
} t_command;
⑵コマンド量の削減
数字（データ）のプッシュを実行する際、コマンド操作が常に少なくて済む数字を選択することで、コマンド数の削減を図りました。
また、ra, rbが一回のプッシュで同時に登場する場合はrrを使用するなど、コマンドの最適化に努めました。
⑶自作ライブラリ
制約で記述した通り、ほぼすべての標準関数の使用が禁止されています。すなわち、使用したい関数は自作する必要があります。
そこで、以前自作したライブラリ「Libft」を使用しました。
5. おわりに
このプログラムを実装するにあたって、最終的には使用しなかったものの、座標圧縮やクイックソートなどのアルゴリズムの学習もすることができました。また、与えられた制約のもと、どのような構造体を定義すれば、コーディングがしやすいのか常に考える必要があったため、要件定義や設計の力も伸ばすことができたと思います。
これからも42tokyoで取り組んだ課題についてどんどんまとめていきます！