PUSH_SWAP（42tokyo）

42tokyoでの課題『**Push_swap**』をクリアしたため、その概要や実装方法などをまとめてみました！
取り組み期間：2024年4月23日～5月13日
コーディング時間：約60時間

# 目次
[1. 42tokyoとは](#1-42tokyoとは)
[2. Push_swap](#2-push_swap)
[3. 作成したプログラム](#3-作成したプログラム)
[4. 工夫したことや苦労したこと](#4-工夫したことや苦労したこと)
[5. おわりに](#5-おわりに)
[6. 参考文献](#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...

簡単に言えば、「**数字を並べ替えろー！ソートしろーー！**」という課題です。
この一文だけだとすごく簡単そうに聞こえますけど、、、

## 制約
プログラム作成にあたって以下のような制約が課せられています。
1. 2つのスタック`Stack_a, Stack_b`のみを使用してソートしなくてはならない

1. スタック間の操作は以下の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 |
1. グローバル変数は使用してはならない
1. 使用してよい標準関数は以下の5つのみである
    `read`, `write`, `malloc`, `free`, `exit`
1. 入力値エラーや、メモリ確保のエラーなど、エラーハンドリングも適切に実装しなくてはならない

この他にも、いくつかの制約が課されていますが、本質的に重要な制約ではないため割愛します。

# 3. 作成したプログラム
ソースコードを貼っておきます。

https://github.com/jayjayjay-hub/42_push_swap/tree/master

## コードの流れ
### 下処理
1. コマンドライン引数より数列を受け取ります
    1. コマンドラインで受け取れるデータは`char`型の配列であり、数字（`int`型）ではないため、受け取った数列を`int`の配列に格納します
    1. その際、バリデーションチェック（数字かどうか、重複はないかなど）を行い、不適切な場合`error`を返し、プログラムを終了させます
1. `int`の配列に格納された数字を、Stack_aに格納していきます
:::note warn
「**どうせStack_aに格納するなら`int`の配列に一度入れる必要ないじゃないか！**」という声が聞こえてきそうです。
はい、その通りです（笑）
もともとこの後の操作で座標圧縮をする予定だったため、`int`の配列だと操作しやすかったのですが、座標圧縮が必要なくなったため不必要でした。
:::

これで下処理は完了です。Stack_aに数字が格納され、Stack_bは空の状態です。

## ソートアルゴリズム
ここから11個のコマンドのみを使用してソートしていきます。数字の個数によって使用するソートアルゴリズムを変えています。
理由は、個数が少なければ、ルールをべた書きで記述した方が、より少ない処理で済むからです。

### 3個以下の場合
1. １個：何もしない
2. ２個：必要ならSwap
3. ３個：全パターンべた書き
<details><summary>ソースコード</summary>

```C
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);
```
</details>

### 4個の場合
1. 一番小さな数字をBへプッシュ
2. 残った３個を上記３個のソートアルゴリズムを用いてソート
3. Bにいる一番小さな数字をAへプッシュ
<details><summary>ソースコード</summary>

```C
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();
	}
}
```
</details>

### 5個以上の場合
1. **BへAの先頭2つをプッシュ**
1. **Aが３個以下になるまでBへプッシュ**
    
    プッシュする際の条件
    
    - Bの最大以上か、最小以下ならBの最大の上にプッシュ
        Bの最大が一番上にくるまでローテ
        
    - それ以外は一番数字が近い、自分より少ない数字の上にプッシュ
    
    上記２つの条件を満たすコマンド数が一番少なくて済むAを選択してプッシュする
    
2. **Aが３個以下になったらAをソート**
3. **Bの全てをAへプッシュする**
    
    プッシュする際の条件（１の逆）
    
    - Aの最大以上か、最小以下ならAの最小の上にプッシュ
    - それ以外は一番数字が近い、自分より大きい数字の上にプッッシュ
    
    上記2つの条件を満たすコマンド数が一番少なくて済むBを選択してプッシュする
    
4. **Aが昇順になるまでローテーション**

参考
[Push Swap — A journey to find most efficient sorting algorithm](https://medium.com/@ayogun/push-swap-c1f5d2d41e97)

# 4. 工夫したことや苦労したこと
## ⑴構造体の定義
### 双方向連結循環リスト
この課題では、スタックの柔軟な操作（先頭の数字が最後にまわるなど）が求められるため、

- スタックの前後のポインタが参照できる「**双方向連結**」
- 先頭と末尾がつながっている（円卓のような）「**循環**」

の2つの機能を備えた**双方向連結循環リスト**を採用しました。
```C
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`（ヒープメモリからのメモリ確保）を行うため、メモリリーク対策に苦労しました。

### コマンド操作
私が使用したアルゴリズムでは、スタック間でプッシュを実行する際、各数字ごとに最適なコマンドを保存する必要があります。
そこで以下のような構造体を定義し、各数字ごとに必要なコマンドを記憶していきました。
```C
typedef struct s_command
{
	int		all;
	int		ra;
	int		rra;
	int		rb;
	int		rrb;
	int		rr;
	int		rrr;
}	t_command;
```

## ⑵コマンド量の削減
数字（データ）のプッシュを実行する際、コマンド操作が常に少なくて済む数字を選択することで、コマンド数の削減を図りました。

また、`ra`, `rb`が一回のプッシュで同時に登場する場合は`rr`を使用するなど、コマンドの最適化に努めました。

## ⑶自作ライブラリ
制約で記述した通り、ほぼすべての標準関数の使用が禁止されています。すなわち、使用したい関数は自作する必要があります。
そこで、以前自作したライブラリ「**Libft**」を使用しました。

https://github.com/jayjayjay-hub/libft

# 5. おわりに
このプログラムを実装するにあたって、最終的には使用しなかったものの、座標圧縮やクイックソートなどのアルゴリズムの学習もすることができました。また、与えられた制約のもと、どのような構造体を定義すれば、コーディングがしやすいのか常に考える必要があったため、要件定義や設計の力も伸ばすことができたと思います。

これからも42tokyoで取り組んだ課題についてどんどんまとめていきます！


# 参考文献
- [Push Swap — A journey to find most efficient sorting algorithm](https://medium.com/@ayogun/push-swap-c1f5d2d41e97)