Summary:
This project will make you sort data on a stack, with a limited set of instructions, using the lowest possible number of actions. To succeed you’ll have to manipulate various types of algorithms and choose the one (of many) most appropriate solution for an optimized data sorting.
요약 :
당신은 가능한 적은 행동을 취하여 제한된 조건으로 스택에 있는 데이터를 정렬할 것입니다. 성공을 위해 당신은 다양한 알고리즘들을 잘 다뤄야 하고, 최적화된 정렬을 위한 가장 적절한 해결책을 선택해야 합니다.
Introduction
The Push_swap project is a very simple and highly effective algorithm project: data will need to be sorted. You have at your disposal a set of int values, 2 stacks and a set of instructions to manipulate both stacks.
Push_swap 프로젝트는 매우 단순하고 고효율 알고리즘 프로젝트입니다. : 데이터는 정렬되야할 것입니다. 당신은 두 개의 스택과 두 개의 스택을 조절하는 명령어, 초기값들을 가집니다.
Your goal ? Write a program in C called push_swap which calculates and displays on the standard output the smallest program using Push_swap instruction language that sorts the integer arguments received.
당신의 목표 ? int값 정렬을 위해 push_swap명령어를 사용하는 가장 가벼운 프로그램의 표준출력을 계산하고 보여주는 push_swap 프로그램을 C언어로 작성하십시오.
Goals
To write a sorting algorithm is always a very important step in a coder’s life, because it is often the first encounter with the concept of complexity.
정렬 알고리즘을 쓰는 것은 코더 인생에 있어서 가장 중요한 단계입니다. 왜냐하면 이것은 복잡성 개념의 첫 단계이기 때문입니다.
Sorting algorithms, and their complexities are part of the classic questions discussed during job interviews. It’s probably a good time to look at these concepts because you’ll have to face them at one point.
정렬 알고리즘들과 이것들의 복잡성은 면접에서 거론되는 클래식한 질문의 일부분입니다. 당신은 한번에 많은 알고리즘들을 접할 수 있기 때문에 이번 과제를 수행하는 시간은 당신에게 좋은 시간이 될 것입니다.
The learning objectives of this project are rigor, use of C and use of basic algorithms. Especially looking at the complexity of these basic algorithms.
이 프로젝트의 학습 목표는 C를 사용하고 기본적은 알고리즘을 사용하는 것입니다. 특히 이 기본적인 알고리즘들의 복잡성을 고려해야합니다.
Sorting values is simple. To sort them the fastest way possible is less simple, especially because from one integers configuration to another, the most efficient sorting algorithm can differ
정렬 값은 단순합니다. 이것 들을 가장 빠른 방법으로 정렬하는 것은 덜 단순합니다. 정수 세트마다 가장 효율적인 알고리즘이 다를 수 있기 때문입니다.
General Instructions
- This project will only be corrected by actual human beings. You are therefore free to organize and name your files as you wish, although you need to respect some requirements listed below.
이 프로젝트는 사람에 의해서 짜여질 것입니다. 그러므로 당신이 밑의 특정 조건들을 존중할지라도 당신 마음대로 파일 이름들을 지정할 수 있습니다. - The executable file must be named push_swap.
실행파일은 반드시 push_swap이어야 합니다. - You must submit a Makefile. That Makefile needs to compile the project and must contain the usual rules. It can only recompile the program if necessary.
당신은 Makefile을 제출해야만 합니다. 제출된 Makefile은 프로젝트를 컴파일하고 특정 규칙을 포함해야만 합니다. 이것은 반드시 프로그램을 recompile할 수 있어야합니다. - If you are clever, you will use your library for this project, submit also your folder libft including its own Makefile at the root of your repository. Your Makefile will have to compile the library, and then compile your project.
만약 당신이 영리하다면 당신은 당신의 라이브러리를 사용할 것이고, 당신의 repo root에 Makefile과 함께 libft를 제출할 것입니다. 당신의 Makefile은 라이브러리를 컴파일 해야하고, 당신의 프로젝트를 컴파일 해야합니다. - Global variables are forbidden.
전역변수는 금지됩니다. - Your project must be written in C in accordance with the Norm.
당신의 프로젝트는 Norm을 준수하여 C로 작성되어야 합니다. - You have to handle errors in a sensitive manner. In no way can your program quit in an unexpected manner (Segmentation fault, bus error, double free, etc).
당신은 에러를 민감하게 다뤄야 합니다. 프로그램이 예기치않는 방식으로 종료되면 안됩니다. - Neither program can have any memory leaks.
프로그램은 어떤 메모리누수도 있으면 안됩니다. - Within your mandatory part you are allowed to use the following functions:
필수파트안에서 당신이 사용할 수 있는 함수는 다음과 같습니다:
write, read, malloc, free, exit
Mandatory part
Game rules
- The game is composed of 2 stacks named a and b.
게임은 a, b 두개의 스택으로 구성됩니다. - a contains a random number of either positive or negative numbers without any duplicates.
A 스택은 어떤 복제도 없이 양수 음수 임의의 값을 포함합니다. - b is empty
B 스택은 비어있습니다. - The goal is to sort in ascending order numbers into stack a.
목표는 A stack의 숫자들을 오름차순으로 정렬하는 것입니다. - To do this you have the following operations at your disposal:
이를 위해 다음과 같은 작업을 수행할 수 있습니다. - sa : swap a - swap the first 2 elements at the top of stack a. Do nothing if there is only one or no elements.
sa : swap a - stack a의 상위 두개 원소를 바꿔줍니다. 원소가 없거나 한개만 있을경우, 어떤 동작도 있으면 안됩니다. - sb : swap b - swap the first 2 elements at the top of stack b. Do nothing if there is only one or no elements.
sb : swap b - stack b의 상위 두개 원소를 바꿔줍니다. 원소가 없거나 한개만 있을경우, 어떤 동작도 있으면 안됩니다. - ss : sa and sb at the same time.
ss : sa, sb를 동시에 - pa : push a - take the first element at the top of b and put it at the top of a. Do nothing if b is empty.
pa : push a - stack b의 상위 첫번째 원소를 stack a 최상위 원소로 넣습니다. stack b가 비어있을 경우, 어떤 동작도 있으면 안됩니다. - pb : push b - take the first element at the top of a and put it at the top of b. Do nothing if a is empty.
pb : push b - stack a의 상위 첫번째 원소를 stack b 최상위 원소로 넣습니다. stack a가 비어있을 경우, 어떤 동작도 있으면 안됩니다. - ra : rotate a - shift up all elements of stack a by 1. The first element becomes the last one.
ra : rotate a - stack a의 모든 원소를 1씩 위로 이동합니다. 첫번째 원소는 마지막 원소가 됩니다. - rb : rotate b - shift up all elements of stack b by 1. The first element becomes the last one.
rb : rotate b - stack b의 모든 원소를 1씩 위로 이동합니다. 첫번째 원소는 마지막 원소가 됩니다. - rr : ra and rb at the same time.
ra와 rb를 동시에 - rra : reverse rotate a - shift down all elements of stack a by 1. The last element becomes the first one.
rra : reverse rotate a - stack a의 모든 원소를 1씩 아래로 이동합니다. 마지막 원소는 첫번째 원소가 됩니다. - rrb : reverse rotate b - shift down all elements of stack b by 1. The last element becomes the first one.
rrb : reverse rotate b - stack b의 모든 원소를 1씩 아래로 이동합니다. 마지막 원소는 첫번째 원소가 됩니다. - rrr : rra and rrb at the same time.
rra와 rrb를 동시에
The “push_swap” program
- You have to write a program named push_swap which will receive as an argument
the stack a formatted as a list of integers. The first argument should be at the top of the stack (be careful about the order)
int의 리스트로 형성된 스택을 인자로 받을 push_swap 프로그램을 작성해야 합니다. - The program must display the smallest list of instructions possible to sort the stack a, the smallest number being at the top.
프로그램은 가장 작은 수가 top에 오도록 stack a를 정렬하기 위해 가장 적은 명렁어 리스트를 보여줘야 합니다. - Instructions must be separaed by a ’\n’ and nothing else.
명령어는 개행으로 분리되어야만 합니다. - The goal is to sort the stack with the minimum possible number of operations. During defence we’ll compare the number of instructions your program found with a maximum number of operations tolerated. If your program either displays a list too big or if the list isn’t sorted properly, you’ll get no points.
목표는 가능한 적은 작업으로 스택을 정렬하는 것입니다. defence 동안 프로그램이 찾은 명령 수와 허용되는 최대 작업 수를 비교할 것입니다. 만약 당신의 프로그램이 너무 많은 명령 수를 보여주거나 제대로 정렬을 안해준다면, 어떤 점수도 못받을 것입니다. - In case of error, you must display Error followed by a ’\n’ on the standard error. Errors include for example: some arguments aren’t integers, some arguments are bigger than an integer, and/or there are duplicates.
오류가 발생한 경우 오류를 표시하고 표준 오류에 개행을 표시해야합니다. 에러는 다음 예시를 포함합니다:
특정 인자가 integer가 아닐경우, 특정 인자의 크기가 integer보다 클 경우, 인자의 중복이 있을 경우. - During the defence we’ll provide a binnary to properly check your program.
defence 동안 우리는 당신의 프로그램을 알맞게 확인하기 위해 binnary를 제공할 것입니다. - If the program checker_OS displays KO, it means that your push_swap came up with a list of instructions that doesn’t sort the list. The checker_OS program is available in
the resources of the project on the intranet. You can find in the bonus section of this document a description of how it works.
checker_OS가 KO를 출력한다면, push_swap 프로그램이 출력한 명령어들이 list를 제대로 정렬하지 못했다는 것을 의미합니다. checker_OS는 인트라넷의 프로젝트에서 resource로 이용이 가능합니다. 당신은 check가 어떻게 동작하는지 bonus section에서 확인할 수 있습니다.
Bonus Part
- We will look at your bonus part if and only if your mandatory part is EXCELLENT. This means that your must complete the mandatory part, beginning to end, and your error management needs to be flawless, even in cases of twisted or bad usage. If that’s not the case, your bonuses will be totally IGNORED.
우리는 mandatory part가 완벽한 경우에만 bonus part를 볼 것입니다. 이는 mandatory part 처음부터 끝까지 완성해야하고 오류관리가 되어 있어야 함을 의미합니다. 만약 그렇지 않다면 bonus part는 전부 무시될 것입니다.
checker program
- Write a program named checker, which will get as an argument the stack a formatted as a list of integers. The first argument should be at the top of the stack (be careful about the order). If no argument is given checker stops and displays nothing.
intergers의 리스트로 구성된 스택을 인자로 받을 checker라는 이름의 프로그램을 작성하십시오. 첫 번째 인자는 스택의 top이 되어야 합니다.(순서에 유의하세요.) 만약 인자가 없을 경우 checker는 멈추고 아무것도 출력하지 않습니다. - checker will then wait and read instructions on the standard input, each instruction will be followed by ’\n’. Once all the instructions have been read, checker will execute them on the stack received as an argument.
checker는 기다렸다가 표준 입력으로 instructions을 읽을 것입니다. 각 instruction은 뒤에 개행문자가 따라옵니다. 일단 instructions을 받으면 checker는 인자로 받은 스택들에 instructions을 적용시켜 실행할 것입니다. - If after executing those instructions, stack a is actually sorted and b is empty, then checker must display "OK" followed by a ’\n’ on the standard output. In every other case, checker must display "KO" followed by a ’\n’ on the standard output.
만약 instructions이 실행된 후에 스택이 정렬되고 b 스택이 비어져 있다면, checker는 개행문자가 뒤에 따라오는 "OK"를 표준출력으로 출력해야 합니다. 다른 모든 경우엔 checker는 개행이 뒤에 따라오는 "KO"를 표준출력으로 출력해야 합니다. - In case of error, you must display Error followed by a ’\n’ on the standard error. Errors include for example: some arguments are not integers, some arguments are bigger than an integer, there are duplicates, an instruction don’t exist and/or is incorrectly formatted.
error의 경우, 당신은 개행이 뒤에 따라오는 "ERROR"를 표준출력으로 출력해야 합니다. error는 다음과 같은 경우를 포함합니다:
특정 인자들이 integer가 아닐 때, 특정 인자들이 integer 범위를 넘어갈 때, 인자의 중복이 있을 때, instruction이 존재하지 않거나, 부정확한 형식일 때.
