Push_Swap

友人が課題の記事を書いていたので、それに触発されてアウトプットすることで知識を定着させようと思い、この記事を書きました。また、この記事がこれから課題に取り組む方の一助になれば幸いです。初めての記事なので至らない点があるかと思いますが、よろしくお願いします。

余談ですが、私はアルゴリズムが苦手で、この課題で完全に手が止まりました（笑）。また、日本語の資料が少なく苦労しました。色々調べた結果、一般的なアルゴリズムを使用しないで満点を獲得する方法があったので、記事にします。

課題の概要

課題の詳細は省略しますが、この課題はコマンドライン引数として与えられた数字を、スタックAとスタックBの2つのスタックと特定の動作をする12種類のコマンドを使用して、スタックAに昇順になるようにソートする課題です。実行プログラムの求められるアウトプットは、数字をソートするコマンドを標準出力に改行して出力することです。このコマンド数が少なければ少ないほど、より優れたソート法として高得点を得ることができます。

コマンドの詳細については省略しますが、各コマンドの動きを確認するのは以下のサイトがおすすめです。貪欲法や奇数ソートなどの動きも視覚的に確認できます。

Push Swap Visualizer

ソートアルゴリズムの実装

ここではpushやswapなどの各コマンドを実装した後のソートアルゴリズムについて説明します。まず、記事のタイトル通り、一般的なソートアルゴリズムは使用しません。愚直に最適なコマンドを計算し、実行します。この課題は最終的な出力コマンド数のみが採点の対象であり、コマンド出力までにかかる計算量は関係ありません。

ソートの流れ

スタックAに全ての数字を格納する
スタックBに降順にプッシュする
スタックAにプッシュしていく（スタックはLIFOの構造です。降順に並んでいる数字をトップからプッシュすると、スタックAが自動的に昇順になります）
終了

以上です。

小さいソートケースの処理

ソートの実装前に、与えられた数字が3つの時のソートを実装します。3つの数字の並び方は6通りしかなく、この場合は直接ソートをした方が効率的です。以下に数字が3つの場合のソートの一例を示します。

void	sort_three(t_node **a)
{
	t_node	*max_node;

	max_node = find_max_node(*a);
	if (max_node == *a)
		rotate(a, "ra");
	else if ((*a)->next == max_node)
		rev_rotate(a, "rra");
	if ((*a)->nbr > (*a)->next->nbr)
		swap(a, "sa");
}

このsort_threeを使用し、数字が4つ以上与えられた場合は、スタックBを補助スタックとして使用します。

プッシュコストの計算

スタックA内に数字が4つ以上の場合、スタックAの先頭からスタックBにノードを2つプッシュします。（ただし、数字が4つの場合はスタックBにプッシュするノードは1つだけとなります。）

では以下のようにプログラムを実行したとして具体的に見ていきます。

./push_swap 5 2 7 1 6 3 9 4 8

まずコマンドラインに与えられた数字をスタックAに格納します。ソート前の初期状態です。

STACK_A           STACK_B

5
2
7
1
6
3
9
4
8

スタックAには4つ以上の数字があるため、スタックAからスタックBへ2回プッシュします。

STACK A          STACK B

7                2
1                5
6
3
9
4
8

次に、残りのスタックAからのプッシュコストを計算します。ここで、プッシュコストとは、スタック中でノードを移動し、別スタックへプッシュするまでに要するコマンドの総数のことです。例えばra、raを行った後にプッシュする場合、コマンドを2回使用しているのでプッシュコストは2となります。

以下の手順を踏みます。

現在のスタックAの全ての数字においてスタックBにプッシュする場合のコストを計算します
スタックAを一周して一番プッシュコストが低いものをスタックBにプッシュします
1と同様、残りのスタックA内の全ての数字において、スタックBにプッシュするコストを計算し、スタックAの残りの要素が3以下になるまでプッシュコスト計算→プッシュの流れを繰り返します

まず、このやり方はスタックAの現在のノードのプッシュ先となるターゲットノードと、そのターゲットノードにプッシュするコスト、そして一番コストが小さいかどうかの判定結果を格納するフラグを用意する必要があります。以下、ノードの設計の一例です。

typedef struct s_node
{
	int				nbr; //並び替えを行う数字
	int				index; //（後述）push_cost計算に使用
	struct s_node	*next; //リンクリストでスタックを実現しているため、次のノードへのポインタ
	struct s_node	*target_node; //プッシュ先のノード
	int				is_cheapest; //push_costが一番小さいかどうかを格納するフラグ
	int				push_cost; //プッシュまでに使用するコマンドの総数
	int				best_direction; //（後述）プッシュまでの回転方向
}					t_node;

プッシュコストの計算について詳しく見ていきましょう。まず、スタックBにプッシュするためのプッシュ先を検討する必要があります。スタックAの全ての要素に対して、プッシュ先のスタックBで、ターゲットノード（プッシュ先）を定めます。スタックBには降順に並ぶようにプッシュします。そのため、ターゲットになるのはプッシュしたいAの数字より小さく、プッシュしたい数字との数値の差が最も小さいノードになります。もし、スタックAの要素より小さい値が存在しない場合は、スタックBの最大値をターゲットノードとします。文章だとわかりづらいので例を見ていきましょう。

STACK A          STACK B

7                2
1                5
6
3
9
4
8

まず7のターゲットノードは5です。（7より小さい要素は2と5ですが、7により近いのは5ですね。）次に1のターゲットノードは5です。（1より小さい値がないため、スタックBの最大値である5がターゲットノードになります。）このようにスタックA内の全ての要素のターゲットノードを定めます。

6→（5）
3→（2）
9→（5）
4→（2）
8→（5）

ターゲットノード計算の関数の具体例は以下になります。

void	find_target_a(t_node *a, t_node *b)
{
	t_node	*current_b;
	t_node	*target_node;
	long	closest_smaller_value;

	while (a)
	{
		closest_smaller_value = LONG_MIN;
		current_b = b;
		while (current_b)
		{
			if (current_b->nbr < a->nbr && current_b->nbr > closest_smaller_value)
			{
				closest_smaller_value = current_b->nbr;
				target_node = current_b;
			}
			current_b = current_b->next;
		}
		if (closest_smaller_value == LONG_MIN)
			a->target_node = find_max_node(b);
		else
			a->target_node = target_node;
		a = a->next;
	}
}

これでスタックAの全ての要素のターゲットノード(プッシュ先)が定まりました。次に、このターゲットノードにプッシュするためのプッシュコスト（ノード移動からプッシュまでに要するコマンドの総数）を計算します。スタックAの全ての要素に対してプッシュコストを計算します。

7を5めがけてプッシュ（スタックA内の移動なし➕スタックBをrrb）コスト1

1を5めがけてプッシュ（スタックAをra➕スタックBをrrb）コスト2

6を5めがけてプッシュ（スタックAをra、ra➕スタックBをrrb）コスト3

3を2めがけてプッシュ(スタックAをra、ra、ra➕スタックB内の移動なし)コスト3

9を5めがけてプッシュ（スタックAをrra、rra、rra➕スタックBをrrb）
→（rra、rra、rrr）スタックAとスタックBで両方ともリバースローテートして手数を減らしコスト3

4を2めがけてプッシュ（スタックAをrra、rra➕スタックB内の移動なし）コスト2

8を5めがけてプッシュ（スタックAをrra➕スタックBをrrb）
→（rrr）スタックAとスタックBで両方ともリバースローテートして手数を減らしコスト1

これでスタックAの全ての要素についてプッシュコストを計算することができました。この中でスタックのトップから確認し、一番プッシュコストの少ない要素をプッシュします。今回はコスト1の7をプッシュします。

STACK A          STACK B

1                7
6                5
3                2
9
4
8

もう一度プッシュの例を見ます。まずスタックA内の要素が3つより多いでスタックBにプッシュする必要があります。スタックA内の全ての要素にターゲットノードを定めます。プッシュしようとしているスタックAの数字より小さく、数値の差が最も小さいものが、ターゲットノードでした。（スタックAの数字より小さい値がない場合、スタックBの最大値がターゲットノードになります。）以下のようになります。

1→7
6→5
3→2
9→7
4→2
8→7

次にこのターゲットノードへのプッシュコストを計算します。

1を7めがけてプッシュ（スタックA内の移動なし + スタックB内の移動なし）コスト0

6を5めがけてプッシュ（スタックAをra➕スタックBをrb）
→（rr）スタックAとスタックBで両方ともローテートして手数を減らしコスト1

3を2めがけてプッシュ（スタックAをra, ra + スタックBをrrb）コスト3

9を7めがけてプッシュ（スタックAをrra, rra, rra + スタックB内の移動なし）コスト3

4を2めがけてプッシュ（スタックAをrra, rra + スタックBをrrb）
→（rrr）スタックAとスタックBで両方ともリバースローテートして手数を減らしコスト2

8を7めがけてプッシュ（スタックAをrra + スタックB内の移動なし）コスト1

これでスタックAの全ての要素についてプッシュコストを計算することができました。今回はコスト0の1をプッシュします。

ここまで見て勘の良い方はすでにお気づきかもしれません。プッシュコスト計算のキーポイントとなるのはプッシュするノードとプッシュ先のターゲットノードの位置です。ノードの位置がスタックの全体の中央より上の場合はrotateを、中央より下の場合はrev_rotateをした方がコストを抑えることができます。また、raとrbを両方行う場合はrrを、rraとrrbを両方行う場合はrrrを使用することでコストを抑えることができます。

スタックAの上下への回転とスタックBの上下への回転を考えると4パターンの回転が考えられます。各パターンの計算方法ですが、スタックの各ノードにインデックスを振り、そのインデックスを足し算することで計算できます。注目するべきはスタックABとも上回転の場合は、raとrbのrrを使用してコストを1とすることができます。その逆であるスタックABとも下回転の場合はrraとrrbの代わりにrrrを使用してコストを1とすることができます。以下はスタックの各ノードへインデックスを振る関数とノードが取りうる4パターンの計算例です。

//スタックの各ノードにindexを振る関数
void    set_index_stack(t_node *top)
{
    int     i;
    t_node  *current;

    if (!top)
        return ;
    current = top;
    i = 0;
    while (current)
    {
        current->index = i;
        current = current->next;
        i++;
    }
}
//ノードの4方向への移動コストの計算
//スタックAをrotate、スタックBもrotate
int calc_cost_up_up(t_node *a)
{
    return ft_max(a->index, a->target_node->index);
}

//スタックAをrev_rotate、スタックBもrev_rotate
int calc_cost_down_down(t_node *a, int len_a, int len_b)
{
    return ft_max(len_a - a->index, len_b - a->target_node->index);
}

//スタックAをrotate、スタックBをrev_rotate
int calc_cost_up_down(t_node *a, int len_b)
{
    return a->index + (len_b - a->target_node->index);
}

//スタックAをrev_rotate、スタックBをrotate
int calc_cost_down_up(t_node *a, int len_a)
{
    return (len_a - a->index) + a->target_node->index;

そして、この4パターンの内、最もコストの小さいものを、そのノードのプッシュコストとして設定します。

void calc_push_cost(t_node *a, int len_a, int len_b)
{
    int cost_up_up;
    int cost_down_down;
    int cost_up_down;
    int cost_down_up;

    cost_up_up = calc_cost_up_up(a);
    cost_down_down = calc_cost_down_down(a, len_a, len_b);
    cost_up_down = calc_cost_up_down(a, len_b);
    cost_down_up = calc_cost_down_up(a, len_a);

    a->push_cost = ft_min(ft_min(cost_up_up, cost_down_down), ft_min(cost_up_down, cost_down_up));

    if (a->push_cost == cost_up_up) a->best_direction = UP_UP;
    else if (a->push_cost == cost_down_down) a->best_direction = DOWN_DOWN;
    else if (a->push_cost == cost_up_down) a->best_direction = UP_DOWN;
    else a->best_direction = DOWN_UP;
}

void calc_all_push_costs(t_node *a, t_node *b)
{
    t_node *current;
    int len_a;
    int len_b;

    current = a;
    len_a = stack_len(a);
    len_b = stack_len(b);
    while (current)
    {
        calc_push_cost(current, len_a, len_b);
        current = current->next;
    }
}

また、実際にプッシュする際はプッシュコスト計算時に判明した、最も手数が少なくなるパターンでプッシュします。そのため、プッシュコストを設定した際の（すなわち4パターン中最適とした）パターンを構造体に保持しておき、計算の際に使用します。

私は次のようにENUMを宣言して使用しました。

enum e_direction {
    UP_UP,
    DOWN_DOWN,
    UP_DOWN,
    DOWN_UP
};

ここまででスタックA中の全てのノードのプッシュ先であるターゲットノードの設定と、そのターゲットノードにプッシュするためにはどの回転が最適か、そしてプッシュに使用するコマンドの総数であるプッシュコストを計算することができました。次にスタックAの中からプッシュコストが最も小さいノードをマークします。（ここでは構造体のis_cheapestフラグを1にすることで実装しています。）

void	mark_cheapest_node(t_node *top)
{
	long	cheapest_cost;
	t_node	*cheapest_node;
	t_node	*current;

	if (!top)
		return ;
	current = top;
	cheapest_cost = LONG_MAX;
	while (current)
	{
		if (current->push_cost < cheapest_cost)
		{
			cheapest_cost = current->push_cost;
			cheapest_node = current;
		}
		current = current->next;
	}
	if (cheapest_node)
		cheapest_node->is_cheapest = 1;
}

そしてスタックAの中でプッシュコストが最も小さいノードを構造体に設定した回転方法をもとに回転してプッシュします。これらの一連の操作をスタックAの要素が3になるまで行い、残ったスタックAの3つの要素は先述のsort_threeでソートします。ここまでの動作をコードで見ていきましょう。

void	sort_stacks(t_node **a, t_node **b)
{
	int	len_a;

	len_a = stack_len((*a));
	if (len_a-- > 3 && !is_sorted(*a))
		push(b, a, "pb");
	if (len_a-- > 3 && !is_sorted(*a))
		push(b, a, "pb");
	while (len_a-- > 3 && !is_sorted(*a))
	{
		set_index_both_stack(*a,*b);
		find_target_a(*a, *b);
		calc_all_push_costs(*a,*b);
		mark_cheapest_node(*a);
		move_a_to_b(a, b);
	}
	sort_three(a); // ここまで説明終了
	while (*b)
	{
		set_index_both_stack(*a,*b);
		find_target_b(*a, *b);
		move_b_to_a(a, b);
	}
	min_on_top(a);
}

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

続いてスタックBからスタックAへのプッシュを見ていきましょう。文章だとわかりづらいので、先ほどのソートを進めた状態から確認しましょう。

STACK A          STACK B

3                8
4                7
9                6
                 5
                 2
                 1

ここでスタックBは降順に、スタックA内もsort_threeでソートされています。スタックBにはすでに降順になっているため先ほどのようなプッシュコストの計算は不要ですが、順番に注意しながらプッシュバックする必要があります。

ソートを進めて確認しましょう。昇順になるようにプッシュバックするため、8を9の上にプッシュしたいですよね。そのためにスタックBのプッシュしたい現在の要素においてターゲットノード（プッシュ先）を定めます。この例だと8を9の上にプッシュしたいのでターゲットノードは9になります。このターゲットノードの求め方はプッシュしたい現在の数字より大きく、プッシュしたい数字との数値の差が最も小さいノードです。もしスタックBの値より大きい要素が存在しない場合は、スタックAの最小値がターゲットノードになります。プッシュ前にこのターゲットノードの位置がトップにあるかを確認し、トップにない場合はスタックを回転をしてからプッシュする必要があります。

8を9の上にプッシュするため、スタックAをrraしてからプッシュします。ここでも注意したいのがターゲットノードの位置がスタックの中央より上にあるか下にあるかによってraかrraを選択します。

STACK A          STACK B

3                8
4                7
9                6
                 5
                 2
                 1

STACK A   STACK B
  8        7
  9        6
  3        5
  4        2
           1

続いて7のターゲットノードは8です。8がすでに一番上にあるため7をプッシュします。

これらのスタックAへのプッシュバックを進めると次のようになります。

STACK A   STACK B

  5        2
  6        1
  7
  8
  9
  3
  4

2のターゲットノードは3になり、3はスタックの中央より下にあるためrraを2回行ってプッシュします。

STACK A   STACK B

  2        1
  3        
  4        
  5
  6
  7
  8
  9

最後に1をプッシュして完成です！

最終調整

最後にもう一つだけ実装するべき関数があります。降順にプッシュしたスタックAをプッシュバックしても、最小値が一番上にくる保証はありません。そのため、最小値がトップでない場合はスタックAを回転する必要があります。スタックA内の最小ノードがトップでない場合、回転をする関数を実装します。ここでも最小ノードのスタック内の位置によってraもしくはrraを選択することで最適化します。

下記が一例です。

void min_node_on_top(t_node **top)
{
    t_node *min_node;
    int stack_size;

    min_node = find_min_node(*top);
    stack_size = stack_len(*top);
    set_index_stack(*top);
    while ((*top) != min_node)
    {
        if (min_node->index <= (stack_size - 1) / 2)
            rotate(top, "ra");
        else
            rev_rotate(top, "rra");
    }
}

以上でソートの実装は終了です。最後に全体のソートロジックについてもう一度お話しします。

初期化と準備:

スタックAに数字を読み込みます。スタックBは空の状態で開始します。

ソート処理振り返り

スタックAから2つの要素をスタックBにプッシュします（スタックAの長さが3より大きい場合）
スタックAからスタックB内でターゲット位置を見つけ、各要素のプッシュコストを計算し、最もコストの小さい要素を選び、スタックBにプッシュします。（スタックAの長さが3になるまで）
スタックAに3つの要素が残ったら、それらを直接ソートします
スタックBの要素をスタックAにプッシュします、必要に応じてスタックAを回転させます
最小値が一番上に来るようにスタックAを回転させます

以上になります。拙い説明でしたが、ここまで読んでくださり本当にありがとうございます。Push_Swapは個人的に本当に苦戦したので、この課題に取り組む方のお役に立てれば幸いです。記事を書くことでコードの理解もとても深まりました。この記事を書くにあたって、同期のコードを見せていただいたり、記事の内容を確認していただいたりしました。この場を借りてお礼申し上げます。また、この課題に取り組まれた先人の記事をとても参考にさせていただきました。以下に参考文献として記載いたします。

参考文献

おすすめテスター

https://github.com/gemartin99/Push-Swap-Tester