From 48fc8d0ffa3bfb766d28bce858eccb68fb0fdec5 Mon Sep 17 00:00:00 2001 From: Charles Cabergs Date: Fri, 10 Sep 2021 19:37:16 +0200 Subject: Added check for already sorted stack, Added special cases for length 3 stacks, Added test.sh benchmark and testing all permutations --- .gitignore | 1 + Makefile | 2 +- correction | 192 ++++++++++++++++++++++++++++++++++++++++++++++++++ src/checker/check.c | 30 ++++---- src/checker/checker.h | 3 +- src/checker/main.c | 2 +- src/common/common.h | 2 +- src/push_swap/sort.c | 104 ++++++++++++++++----------- test.sh | 41 ++++++++++- 9 files changed, 314 insertions(+), 63 deletions(-) create mode 100644 correction diff --git a/.gitignore b/.gitignore index 4bf4a20..b8d327f 100644 --- a/.gitignore +++ b/.gitignore @@ -1,6 +1,7 @@ *.o *.ghc *.dSYM +vgcore.* a.out tags diff --git a/Makefile b/Makefile index fe0cb95..10ef0e0 100644 --- a/Makefile +++ b/Makefile @@ -3,7 +3,7 @@ RM = rm -f LIBFT_DIR = libft CC = gcc -CCFLAGS = -I$(COMMON_DIR) -I$(LIBFT_DIR)/include -Wall -Wextra -Werror +CCFLAGS = -I$(COMMON_DIR) -I$(LIBFT_DIR)/include -Wall -Wextra #-Werror LDFLAGS = -L$(LIBFT_DIR) -lft SRC_DIR = src diff --git a/correction b/correction new file mode 100644 index 0000000..897f0de --- /dev/null +++ b/correction @@ -0,0 +1,192 @@ +PUSH_SWAP correction + +Partie obligatoire +Rappel : si a un moment ou un autre, le programme ne réagit pas correctement (bus error, segfault, etc..), ou bien si vous détectez une fuite mémoire, la soutenance est terminée et la note est 0. Pensez à utiliser les flags correspondants quand nécessaire. Cette consigne est active d'un bout à l'autre de la soutenance. + +Fuites mémoire +Pendant toute la durée de la soutenance, gardez un oeil sur la +quantité de mémoire utilisée par le push_swap (à l'aide de +top par exemple) pour detecter des anomalies, et vérifiez dans +le code que les allocations sont systématiquement libérées. +Dans le cas contraire il y a au moins une fuite mémoire, la +note du projet est 0. + Yes + No + +Gestion des erreurs +Dans cette section nous allons évaluer la bonne gestion des +erreurs de votre push_swap. +Si au moins l'un des tests échoue, aucun point n'est gagné +pour cette question. Passez à la question suivante. + +- Lancer push_swap avec des paramètres non numériques. Le programme +doit afficher "Error". +- Lancer push_swap avec un doublon dans les paramètres. Le programme +doit afficher "Error". +- Lancer push_swap avec seulement des nombres en paramètre, l'un d'entre +eux étant supérieur à MAXINT. Le programme doit afficher "Error". +- Lancer push_swap avec aucun paramètre. Le programme ne doit rien afficher, +se terminer, et le shell affiche son prompt. + Yes + No + +Push_swap - Identité +Nous allons évaluer dans cette section le comportement du +programme push_swap sur une liste de paramètres déja triés. +Effectuez les 3 tests suivants. Si l'un au moins de ces tests +échoue, cette section du barème est échouée et aucun point +n'est gagné, passez à la suivante. + +- Lancez "$>./push_swap 42". Le programme affiché doit être +vide (0 instruction). +- Lancez "$>./push_swap 0 1 2 3". Le programme affiché doit +être vide (0 instruction). +- Lancez "$>./push_swap 0 1 2 3 4 5 6 7 8 9". Le programme +affiché doit être vide (0 instruction). + Yes + No + +Push_swap - tests simples +Si le test suivant échoue, cette section du barème est +échouée et aucun point n'est gagné, passez à la suivante. +- Lancez "$>ARG="2 1 0"; ./push_swap $ARG | ./checker_OS $ARG". +Vérifiez que le programme checker affiche OK que la taille +du programme calculé par le programme push_swap est de 2 OU +3 instructions. Sinon le test est échoué. + Yes + No + +D'autres tests tout aussi simples +Si l'un des 2 tests suivants échoue, cette section du barème +est échouée et aucun point n'est gagné, passez à la +suivante. +- Lancez "$>ARG="1 5 2 4 3"; ./push_swap $ARG | ./checker_OS $ARG". Vérifiez que le programme checker affiche OK et que +la taille du programme calculé par le programme push_swap +est de 12 instructions au maximum. Sinon le test est +échoué. Kudos pour la personne évaluée si la taille +programme est de 8 instructions. +- Lancez "$>ARG="<5 params au choix>"; ./push_swap $ARG | ./checker_OS $ARG" en remplacant le placeholder par 5 valeurs +valides de votre choix. Vérifiez que le programme checker +affiche OK et que la taille du programme calculé par le +programme push_swap est de 12 instructions au maximum. Sinon +le test est échoué. Vous devez en particulier vérifier +avec ce test que le programme push_swap n'a pas été +programmé pour répondre correctement uniquement aux tests +de ce barème. Vous êtes encouragés à répéter ce test +avec plusieurs variantes avant de le valider. + Yes + No + +Push_swap - tests intermédiaires +Si le test suivant échoue, cette section du barème est +échouée et aucun point n'est gagné, passez à la suivante. +- Lancez "$>ARG="<100 params au choix>"; ./push_swap $ARG | ./checker_OS $ARG" en remplacant le placeholder par 100 valeurs +valides de votre choix. Vérifiez que le programme checker +affiche OK et mettez des points en fonction du nombre +d'instructions effectuées: +- Moins de 700: 5 +- Moins de 900: 4 +- Moins de 1100: 3 +- Moins de 1300: 2 +- Moins de 1500: 1 +Vous devez en particulier vérifier +avec ce test que le programme push_swap n'a pas été +programmé pour répondre correctement uniquement aux +tests de ce barème. Vous êtes encouragés à répéter +ce test avec plusieurs variantes avant de le valider. +Rate it from 0 (failed) through 5 (excellent) +Push_swap - tests avancés +Si le test suivant échoue, cette section du barème est +échouée et aucun point n'est gagné, passez à la suivante. +- Lancez "$>ARG="<500 params au choix>"; ./push_swap $ARG | ./checker_OS $ARG" en remplacant le placeholder par 500 valeurs +valides de votre choix (on vous appelle pas +Jean(ne)-Michel(le) Script pour rien). Vérifiez que le +programme checker affiche OK et mettez des points en +fonction du nombre d'instructions effectuées: +- Moins de 5500: 5 +- Moins de 7000: 4 +- Moins de 8500: 3 +- Moins de 10000: 2 +- Moins de 11500: 1 Vous devez en particulier vérifier +avec ce test que le programme push_swap n'a pas été +programmé pour répondre correctement uniquement aux +tests de ce barème. Vous êtes encouragés à répéter +ce test avec plusieurs variantes avant de le valider. +Rate it from 0 (failed) through 5 (excellent) + +Bonus + +Rappel : si a un moment ou un autre, le programme ne réagit pas correctement (bus error, segfault, etc..), la soutenance est terminée et la note est 0. Pensez à utiliser les flags correspondants. Cette consigne est active d'un bout à l'autre de la soutenance. Les bonus ne doivent être évalués que si et seulement si la partie obligatoire est PARFAITE. Par PARFAITE, on entend bien évidemment qu'elle est entièrement réalisée, qu'il n'est pas possible de mettre son comportement en défaut, même en cas d'erreur, aussi vicieuse soit-elle, de mauvaise utilisation, etc. Concrètement, cela signifie que si la partie obligatoire n'a pas obtenu TOUS les points pendant cette soutenance, les bonus doivent être intégralement IGNORÉS. + +Checker - gestion des erreurs +Nous allons évaluer dans cette section la gestion d'erreur du +programme checker. Effectuez les tests suivants. Si l'un au +moins de ces tests échoue, cette section du barème est +échouée et aucun point n'est gagné, passez à la suivante. +- Lancez checker avec des paramètres non numériques. Le +programme doit afficher "Error". +- Lancez checker avec 2 fois le même paramètre numérique. Le +programme doit afficher "Error". +- Lancez checker avec uniquement des paramètres numériques +dont l'un plus grand que MAXINT. Le programme doit afficher +"Error". +- Lancez checker sans aucun paramètre. Le programme doit rendre +la main et ne rien afficher. +- Lancez checker avec des paramètres valides, puis au moment +d'entrer les insctructions à exécuter, entrez des +instructions qui n'existent pas. Le programme doit afficher +"Error". +- Lancez checker avec des paramètres valides, puis au moment +d'entrer les insctructions à exécuter, entrez des +instructions valides, mais précédez les et terminez les avec +un ou plusieurs espaces. Le programme doit afficher "Error". + Yes + No + +Checker - tests des faux résultats +Nous allons évaluer dans cette section le comportement du +programme checker lorsque le programme lu ne trie pas la liste. +Effectuez les 2 tests suivants. Si l'un au moins de ces tests +échoue, cette section du barème est échouée et aucun point +n'est gagné, passez à la suivante. +N'oubliez pas d'appuyer sur ctrl+d pour arrêter la lecture une +fois que vous avez fini d'entrer les instructions. +- Lancez checker avec la commande "$>./checker 0 9 1 8 2 7 3 6 4 5" puis entrez les instructions suivantes avec un formatage +valide : [sa, pb, rrr]. Le programme checker doit afficher +"KO". +- Lancez checker avec une liste de paramètres valides de votre +choix, puis entrez les instructions de votre choix avec un +formatage valide, mais qui ne permettent pas de trier les +entiers. Le programme checker doit afficher "KO". Vous devez +en particulier vérifier avec ce test que le programme checker +n'a pas été programmé pour répondre correctement +uniquement aux tests de ce barème. Vous êtes encouragés à +répéter ce test avec plusieurs variantes avant de le +valider. + Yes + No + +Checker - test des résultats corrects +Nous allons évaluer dans cette section le comportement du +programme checker lorsque le programme lu trie la liste. +Effectuez les tests suivants. Si l'un au moins de ces tests +échoue, cette section du barème est échouée et aucun point +n'est gagné, passez à la suivante. +N'oubliez pas d'appuyer sur ctrl+d pour arrêter la lecture une +fois que vous avez fini d'entrer les instructions. +- Lancez checker avec la commande "$>./checker 0 1 2" puis +appuyez sur ctrl+d sans entrer d'instructions. Le programme +checker doit afficher "OK". +- Lancez checker avec la commande "$>./checker 0 9 1 8 2" puis +entrez les instructions suivantes avec un formatage valide : +[pb, ra, pb, ra, sa, ra, pa, pa]. Le programme checker doit +afficher "OK". +- Lancez checker avec une liste de paramètres valides de votre +choix, puis entrez les instructions de votre choix avec un +formatage valide qui permettent de trier les entiers. Le +programme checker doit afficher "OK". Vous devez en +particulier vérifier avec ce test que le programme checker +n'a pas été programmé pour répondre correctement +uniquement aux tests de ce barème. Vous êtes encouragés à +répéter ce test avec plusieurs variantes avant de le +valider. diff --git a/src/checker/check.c b/src/checker/check.c index 1459dc6..40550b5 100644 --- a/src/checker/check.c +++ b/src/checker/check.c @@ -6,12 +6,25 @@ /* By: cacharle +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2020/01/18 10:16:08 by cacharle #+# #+# */ -/* Updated: 2021/09/10 10:26:47 by charles ### ########.fr */ +/* Updated: 2021/09/10 15:36:14 by charles ### ########.fr */ /* */ /* ************************************************************************** */ #include "checker.h" +static t_bool stack_sorted(t_stack *stack) +{ + int i; + + if (stack_length(stack) < 2) + return (TRUE); + i = stack->top + 1; + while (--i > 0) + if (stack->elements[i] > stack->elements[i - 1]) + return (FALSE); + return (TRUE); +} + t_status check(t_stack *a, t_stack *b) { t_status read_status; @@ -75,7 +88,7 @@ t_status exec_action(char action_id[ACTION_ID_BUF_SIZE], int i; i = 0; - while (ft_strcmp(action_id, g_actions[i].id) != 0) + while (i < g_actions_size && ft_strcmp(action_id, g_actions[i].id) != 0) i++; if (i == g_actions_size) return (STATUS_ERROR); @@ -91,16 +104,3 @@ t_status exec_action(char action_id[ACTION_ID_BUF_SIZE], return (STATUS_ERROR); return (STATUS_SUCCESS); } - -t_bool stack_sorted(t_stack *stack) -{ - int i; - - if (stack_length(stack) < 2) - return (TRUE); - i = stack->top + 1; - while (--i > 0) - if (stack->elements[i] > stack->elements[i - 1]) - return (FALSE); - return (TRUE); -} diff --git a/src/checker/checker.h b/src/checker/checker.h index d049e21..638f43f 100644 --- a/src/checker/checker.h +++ b/src/checker/checker.h @@ -6,7 +6,7 @@ /* By: cacharle +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2020/01/18 10:16:12 by cacharle #+# #+# */ -/* Updated: 2021/09/10 10:26:37 by charles ### ########.fr */ +/* Updated: 2021/09/10 12:04:41 by charles ### ########.fr */ /* */ /* ************************************************************************** */ @@ -45,6 +45,5 @@ t_status check(t_stack *a, t_stack *b); t_status read_action(t_stack *a, t_stack *b); t_status exec_action(char action_id[ACTION_ID_BUF_SIZE], t_stack *a, t_stack *b); -t_bool stack_sorted(t_stack *stack); #endif diff --git a/src/checker/main.c b/src/checker/main.c index ca38105..394dddc 100644 --- a/src/checker/main.c +++ b/src/checker/main.c @@ -6,7 +6,7 @@ /* By: cacharle +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2020/01/18 10:16:14 by cacharle #+# #+# */ -/* Updated: 2021/09/10 10:33:05 by charles ### ########.fr */ +/* Updated: 2021/09/10 12:08:44 by charles ### ########.fr */ /* */ /* ************************************************************************** */ diff --git a/src/common/common.h b/src/common/common.h index c4efad8..d3cafc4 100644 --- a/src/common/common.h +++ b/src/common/common.h @@ -6,7 +6,7 @@ /* By: cacharle +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2020/01/18 11:20:54 by cacharle #+# #+# */ -/* Updated: 2021/09/10 10:33:19 by charles ### ########.fr */ +/* Updated: 2021/09/10 12:12:04 by charles ### ########.fr */ /* */ /* ************************************************************************** */ diff --git a/src/push_swap/sort.c b/src/push_swap/sort.c index 588dc54..b2d4838 100644 --- a/src/push_swap/sort.c +++ b/src/push_swap/sort.c @@ -6,7 +6,7 @@ /* By: cacharle +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2020/01/19 09:12:02 by cacharle #+# #+# */ -/* Updated: 2021/09/10 10:48:01 by charles ### ########.fr */ +/* Updated: 2021/09/10 19:35:34 by charles ### ########.fr */ /* */ /* ************************************************************************** */ @@ -17,42 +17,48 @@ static int frame_length(t_stack *st, int frame_index) return (stack_length(st) - frame_index); } -/* static void push_swap_sort3(t_stack *main, int main_frame) */ -/* { */ -/* #<{(| 1 < 2 < 3 |)}># */ -/* #<{(| 2 < 3 < 1 |)}># */ -/* #<{(| 3 < 1 < 2 |)}># */ -/* #<{(| 3 < 2 < 1 |)}># */ -/* #<{(| 2 < 1 < 3 |)}># */ -/* #<{(| 1 < 3 < 2 |)}># */ -/* */ -/* int a, b, c; */ -/* */ -/* a = main->elements[main->top]; */ -/* b = main->elements[main->top - 1]; */ -/* c = main->elements[main->top - 2]; */ -/* */ -/* if (a < b && b < c) */ -/* return ; */ -/* if (a < b && b > c) */ -/* stack_swap_print(main); */ -/* */ -/* if (a > b && b < c) */ -/* stack_swap_print(main); */ -/* if (a < b && b > c) */ -/* stack_swap_print(main); */ -/* if (a < b && b > c) */ -/* stack_swap_print(main); */ -/* if (a < b && b > c) */ -/* stack_swap_print(main); */ -/* } */ - -static int not_a_ternary(bool cond, int x, int y) +static void push_swap_sort3(t_stack *main) { - if (cond) - return (x); + int a, b, c; + + a = main->elements[main->top]; + b = main->elements[main->top - 1]; + c = main->elements[main->top - 2]; + + /* 2 3 1 rra */ + if (a < b && b > c && a > c) + stack_reverse_rotate_print(main); + + /* 3 1 2 ra */ + else if (a > b && b < c && a > c) + stack_rotate_print(main); + + /* 3 2 1 ra sa */ + else if (a > b && b > c && a > c) + { + stack_rotate_print(main); + stack_swap_print(main); + } + + /* 2 1 3 sa */ + else if (a > b && b < c && a < c) + stack_swap_print(main); + + /* 1 3 2 sa ra*/ + else if (a < b && b > c && a < c) + { + stack_swap_print(main); + stack_rotate_print(main); + } +} + + +static int stack_cmp(t_stack *stack, int x, int y) +{ + if (stack->tag == STACK_A) + return (x < y); else - return (y); + return (x > y); } /* @@ -87,8 +93,7 @@ static void push_swap_qsort_partition(t_stack *main, t_stack *tmp, frame_len = frame_length(main, main_frame) - 1; while (frame_len > 0) { - if (not_a_ternary(main->tag == STACK_A, - stack_peek(main) < pivot, stack_peek(main) > pivot)) + if (stack_cmp(main, stack_peek(main) , pivot)) stack_push_to_print(main, tmp); else { @@ -103,6 +108,20 @@ static void push_swap_qsort_partition(t_stack *main, t_stack *tmp, stack_reverse_rotate_print(main); } +static bool stack_frame_sorted(t_stack *stack, int frame_len) +{ + int i; + + i = 0; + while (i < frame_len - 1) + { + if (stack_cmp(stack, stack->elements[stack->top - 1 - i], stack->elements[stack->top - i])) + return false; + i++; + } + return true; +} + /* ** main : final stack where all sorted values will be stored ** tmp : temporary stack use to during partitionning @@ -122,18 +141,19 @@ static void push_swap_qsort_rec(t_stack *main, t_stack *tmp, { int tmp_frame_len; + /* printf("f: %d\n", main_frame); */ if (frame_length(main, main_frame) < 2) return ; + if (stack_frame_sorted(main, frame_length(main, main_frame))) + return ; + if (main->tag == STACK_A && stack_length(main) == 3) + return push_swap_sort3(main); if (frame_length(main, main_frame) == 2) { - if (not_a_ternary(main->tag == STACK_A, - main->elements[main->top] > main->elements[main->top - 1], - main->elements[main->top] < main->elements[main->top - 1])) + if (stack_cmp(main, main->elements[main->top - 1], main->elements[main->top])) stack_swap_print(main); return ; } - /* if (frame_length(main main_frame) == 3) */ - /* return push_swap_sort3(main, main_frame); */ push_swap_qsort_partition(main, tmp, main_frame); push_swap_qsort_rec(tmp, main, tmp_frame, stack_length(main)); stack_push_to_print(main, tmp); diff --git a/test.sh b/test.sh index 2f39818..d27aebc 100755 --- a/test.sh +++ b/test.sh @@ -54,7 +54,44 @@ assert_error() { assert "$1" "Error" } -if [ "$1" = "--error" ]; then +if [ "$1" = "--bench" ] +then + [ "$#" -ne 3 ] && echo 'Usage: ./test.sh --bench num_bench stack_len' && exit 1 + total=0 + num_bench="$2" + stack_len="$3" + for i in $(seq "$num_bench") + do + instruction_count="$(seq "$stack_len" | shuf | xargs ./push_swap | wc -l)" + total=$((total + instruction_count)) + printf "%4d: %7d, current average: %7d\n" "$i" "$instruction_count" $((total / i)) + done + printf "Final Total: %7d\n" "$total" + printf "Final Average: %7d\n" $((total / num_bench)) + exit 0 +fi + +if [ "$1" = "--perm" ] +then + [ -z "$2" ] && echo 'Usage: ./test.sh --perm stack_len' && exit 1 + stack_len="$2" + python <