README.ru.md

push_swap

Цель данного проекта отсортировать данные в стеке, по определенным правилам, с использованием минимально возможного количества действий.

Описание основной части

Программа push_swap принимает на вход множество int значений, сортирует их используя определённые правила и выводит список команд, которые были выполнены. Чтобы сделать это нужно придумать алгоритм и реализовать его.

Правила

У нас есть 2 стека a и b. Изначально:

• a - содержит случайное число из положительных или отрицательных чисел без дубликатов
• b - пустой

Задача заключается в том, чтобы отсортировать в порядке возрастания числа в стеке a. В нашем распоряжении есть следующие команды:

• sa - swap a - поменять местами первые 2 элемента на вершине стека a. Ничего не делать, если там только один или ни одного элемента
• sb - swap b - поменять местами первые 2 элемента на вершине стека b. Ничего не делать, если там только один или ни одного элемента
• ss - одновременное выполнение swap a и swap b
• pa - push a - взять первый элемент в вершине b и поместить его в вершину a. Ничего не делать, если b пуст
• pb - push b - взять первый элемент в вершине a и поместить его в вершину b. Ничего не делать, если a пуст
• ra - rotate a - сдвинуть вверх все элементы стека a на 1. Первый элемент становится последним
• rb - rotate b - сдвинуть вверх все элементы стека b на 1. Первый элемент становится последним
• rr - одновременное выполнение rotate a и rotate b
• rra - reverse rotate a - сдвинуть вниз все элементы стека a на 1. Последний элемент становится первым
• rrb - reverse rotate b - сдвинуть вниз все элементы стека b на 1. Последний элемент становится первым
• rrr - одновременное выполнение reverse rotate a и reverse rotate b

Пример работы push_swap

Входные параметры и вывод реализованной программы:

$> ./push_swap 2 1 3 6 5 8
sa
pb
pb
pb
sa
pa
pa
pa

Алгоритм

Для выполнения проекта, использовался следующий алгоритм.

Но для безупречной работы, пришлость внести некоторые дополнения.

Описание бонусной части

Если вы уверены что алгоритм работает идеально, можно приступить к бонусу. Нужно написать собственный checker, повторяющий поведение стандартного checker_OS.

Пример работы checker

Входные параметры и вывод реализованной программы:

$> ./checker 2 1 3 6 5 8
sa
pb
pb
pb
sa
pa
pa
pa
OK

Оценка от moulinette