aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Makefile4
-rwxr-xr-xrandom_stack.rb8
-rw-r--r--src/checker/check.c12
-rw-r--r--src/checker/checker.h10
-rw-r--r--src/checker/main.c34
-rw-r--r--src/common/common.h58
-rw-r--r--src/common/parse.c49
-rw-r--r--src/common/stack_core.c3
-rw-r--r--src/push_swap/main.c45
-rw-r--r--src/push_swap/push_swap.h29
-rw-r--r--src/push_swap/sort.c61
-rw-r--r--src/push_swap/stack_wrapper.c40
-rwxr-xr-xvisualizer.rb116
13 files changed, 401 insertions, 68 deletions
diff --git a/Makefile b/Makefile
index 8177f82..2e08fe0 100644
--- a/Makefile
+++ b/Makefile
@@ -12,7 +12,7 @@ COMMON_DIR = $(SRC_DIR)/common
CHECKER_NAME = checker
COMMON_HEADER = $(COMMON_DIR)/common.h
-COMMON_FILES = stack_core.c stack_op.c stack_helper.c
+COMMON_FILES = stack_core.c stack_op.c stack_helper.c parse.c
COMMON_SRC = $(addprefix $(COMMON_DIR)/,$(COMMON_FILES))
COMMON_OBJ = $(COMMON_SRC:.c=.o)
@@ -27,7 +27,7 @@ CHECKER_OBJ = $(CHECKER_SRC:.c=.o)
CHECKER_OBJ += $(COMMON_OBJ)
PUSH_SWAP_HEADER = $(PUSH_SWAP_DIR)/push_swap.h
-PUSH_SWAP_FILES = main.c
+PUSH_SWAP_FILES = main.c sort.c stack_wrapper.c
PUSH_SWAP_SRC = $(addprefix $(PUSH_SWAP_DIR)/,$(PUSH_SWAP_FILES))
PUSH_SWAP_OBJ = $(PUSH_SWAP_SRC:.c=.o)
PUSH_SWAP_OBJ += $(COMMON_OBJ)
diff --git a/random_stack.rb b/random_stack.rb
new file mode 100755
index 0000000..ab6ad35
--- /dev/null
+++ b/random_stack.rb
@@ -0,0 +1,8 @@
+#!/usr/bin/ruby
+
+if ARGV.length != 2
+ puts "Usage: #{$PROGRAM_NAME} start end"
+ exit
+end
+
+puts (ARGV[0]..ARGV[1]).to_a.shuffle.join(" ")
diff --git a/src/checker/check.c b/src/checker/check.c
index 125fdb7..bbe509f 100644
--- a/src/checker/check.c
+++ b/src/checker/check.c
@@ -6,7 +6,7 @@
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2020/01/18 10:16:08 by cacharle #+# #+# */
-/* Updated: 2020/01/19 07:11:05 by cacharle ### ########.fr */
+/* Updated: 2020/01/19 09:02:08 by cacharle ### ########.fr */
/* */
/* ************************************************************************** */
@@ -48,8 +48,8 @@ static t_action g_actions[] = {
{"sa", FLAG_ARG_A, {.arg_1 = &stack_swap}},
{"sb", FLAG_ARG_B, {.arg_1 = &stack_swap}},
{"ss", FLAG_ARG_A_B, {.arg_2 = &stack_swap_2}},
- {"pa", FLAG_ARG_A_B, {.arg_2 = &stack_push_to}},
- {"pb", FLAG_ARG_B_A, {.arg_2 = &stack_push_to}},
+ {"pa", FLAG_ARG_B_A, {.arg_2 = &stack_push_to}},
+ {"pb", FLAG_ARG_A_B, {.arg_2 = &stack_push_to}},
{"ra", FLAG_ARG_A, {.arg_1 = &stack_rotate}},
{"rb", FLAG_ARG_B, {.arg_1 = &stack_rotate}},
{"rr", FLAG_ARG_A_B, {.arg_2 = &stack_rotate_2}},
@@ -89,9 +89,9 @@ t_bool stack_sorted(t_stack *stack)
if (stack_length(stack) < 2)
return (TRUE);
- i = -1;
- while (++i < stack->top)
- if (stack->elements[i] > stack->elements[i + 1])
+ 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 877f669..808e408 100644
--- a/src/checker/checker.h
+++ b/src/checker/checker.h
@@ -6,7 +6,7 @@
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2020/01/18 10:16:12 by cacharle #+# #+# */
-/* Updated: 2020/01/19 06:30:04 by cacharle ### ########.fr */
+/* Updated: 2020/01/19 09:09:29 by cacharle ### ########.fr */
/* */
/* ************************************************************************** */
#include <stdio.h>
@@ -22,14 +22,6 @@
typedef enum
{
- STATUS_SUCCESS,
- STATUS_FAILURE,
- STATUS_ERROR,
- STATUS_EOF,
-} t_status;
-
-typedef enum
-{
FLAG_ARG_A,
FLAG_ARG_B,
FLAG_ARG_A_B,
diff --git a/src/checker/main.c b/src/checker/main.c
index 3b4b313..a0a08b2 100644
--- a/src/checker/main.c
+++ b/src/checker/main.c
@@ -6,26 +6,12 @@
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2020/01/18 10:16:14 by cacharle #+# #+# */
-/* Updated: 2020/01/19 08:37:03 by cacharle ### ########.fr */
+/* Updated: 2020/01/19 09:08:41 by cacharle ### ########.fr */
/* */
/* ************************************************************************** */
#include "checker.h"
-t_status has_dup(int *xs, size_t size)
-{
- int *tmp;
- t_status ret;
-
- if ((tmp = (int*)malloc(size * sizeof(int))) == NULL)
- return (STATUS_ERROR);
- ft_memcpy(tmp, xs, size * sizeof(int));
- ret = ft_is_set(tmp, size, sizeof(int), &ft_compar_int) ?
- STATUS_SUCCESS : STATUS_FAILURE;
- free(tmp);
- return (ret);
-}
-
int main(int argc, char **argv)
{
t_status s;
@@ -36,24 +22,8 @@ int main(int argc, char **argv)
return (0);
if ((a = stack_new(argc - 1)) == NULL)
return (1);
- while (--argc >= 1)
- {
- errno = 0;
- stack_push(a, ft_strict_atoi(argv[argc]));
- if (errno != 0)
- {
- ft_putendl_fd("Error", STDERR_FILENO);
- stack_destroy(a);
- return (1);
- }
- }
-
- if (has_dup(a->elements, stack_length(a)) != STATUS_SUCCESS)
- {
- ft_putendl_fd("Error", STDERR_FILENO);
- stack_destroy(a);
+ if (parse(argc, argv, a) != STATUS_SUCCESS)
return (1);
- }
if ((b = stack_new(stack_length(a))) == NULL)
{
stack_destroy(a);
diff --git a/src/common/common.h b/src/common/common.h
index 0cfd687..97881c8 100644
--- a/src/common/common.h
+++ b/src/common/common.h
@@ -6,7 +6,7 @@
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2020/01/18 11:20:54 by cacharle #+# #+# */
-/* Updated: 2020/01/19 06:43:24 by cacharle ### ########.fr */
+/* Updated: 2020/01/19 13:31:27 by cacharle ### ########.fr */
/* */
/* ************************************************************************** */
#include <stdio.h>
@@ -17,39 +17,61 @@
#include <stdlib.h>
#include "libft.h"
+typedef enum
+{
+ STATUS_SUCCESS,
+ STATUS_FAILURE,
+ STATUS_ERROR,
+ STATUS_EOF,
+} t_status;
+
+typedef enum
+{
+ STACK_NO_TAG,
+ STACK_A,
+ STACK_B
+} t_stack_tag;
+
typedef struct
{
- int *elements;
- int top;
-} t_stack;
+ int *elements;
+ t_stack_tag tag;
+ int top;
+} t_stack;
/*
** stack_core.c
*/
-t_stack *stack_new(int size);
-void stack_destroy(t_stack *stack);
-void stack_push(t_stack *stack, int n);
-void stack_pop(t_stack *stack);
-int stack_peek(t_stack *stack);
+t_stack *stack_new(int size);
+void stack_destroy(t_stack *stack);
+void stack_push(t_stack *stack, int n);
+void stack_pop(t_stack *stack);
+int stack_peek(t_stack *stack);
/*
** stack_op.c
*/
-void stack_swap(t_stack *stack);
-void stack_push_to(t_stack *from, t_stack *to);
-void stack_rotate(t_stack *stack);
-void stack_reverse_rotate(t_stack *stack);
+void stack_swap(t_stack *stack);
+void stack_push_to(t_stack *from, t_stack *to);
+void stack_rotate(t_stack *stack);
+void stack_reverse_rotate(t_stack *stack);
/*
** stack_helper.c
*/
-void stack_swap_2(t_stack *stack_a, t_stack *stack_b);
-void stack_rotate_2(t_stack *stack_a, t_stack *stack_b);
-void stack_reverse_rotate_2(t_stack *stack_a, t_stack *stack_b);
-t_bool stack_empty(t_stack *stack);
-int stack_length(t_stack *stack);
+void stack_swap_2(t_stack *stack_a, t_stack *stack_b);
+void stack_rotate_2(t_stack *stack_a, t_stack *stack_b);
+void stack_reverse_rotate_2(t_stack *stack_a, t_stack *stack_b);
+t_bool stack_empty(t_stack *stack);
+int stack_length(t_stack *stack);
+
+/*
+** parse.c
+*/
+
+t_status parse(int argc, char **argv, t_stack *a);
#endif
diff --git a/src/common/parse.c b/src/common/parse.c
new file mode 100644
index 0000000..b0415cd
--- /dev/null
+++ b/src/common/parse.c
@@ -0,0 +1,49 @@
+/* ************************************************************************** */
+/* */
+/* ::: :::::::: */
+/* parse.c :+: :+: :+: */
+/* +:+ +:+ +:+ */
+/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
+/* +#+#+#+#+#+ +#+ */
+/* Created: 2020/01/19 09:03:28 by cacharle #+# #+# */
+/* Updated: 2020/01/19 13:33:17 by cacharle ### ########.fr */
+/* */
+/* ************************************************************************** */
+
+#include "common.h"
+
+static t_status has_dup(int *xs, size_t size)
+{
+ int *tmp;
+ t_status ret;
+
+ if ((tmp = (int*)malloc(size * sizeof(int))) == NULL)
+ return (STATUS_ERROR);
+ ft_memcpy(tmp, xs, size * sizeof(int));
+ ret = ft_is_set(tmp, size, sizeof(int), &ft_compar_int) ?
+ STATUS_SUCCESS : STATUS_FAILURE;
+ free(tmp);
+ return (ret);
+}
+
+t_status parse(int argc, char **argv, t_stack *a)
+{
+ while (--argc >= 1)
+ {
+ errno = 0;
+ stack_push(a, ft_strict_atoi(argv[argc]));
+ if (errno != 0)
+ {
+ ft_putendl_fd("Error", STDERR_FILENO);
+ stack_destroy(a);
+ return (STATUS_FAILURE);
+ }
+ }
+ if (has_dup(a->elements, stack_length(a)) != STATUS_SUCCESS)
+ {
+ ft_putendl_fd("Error", STDERR_FILENO);
+ stack_destroy(a);
+ return (STATUS_FAILURE);
+ }
+ return (STATUS_SUCCESS);
+}
diff --git a/src/common/stack_core.c b/src/common/stack_core.c
index 6875862..bf766d4 100644
--- a/src/common/stack_core.c
+++ b/src/common/stack_core.c
@@ -6,7 +6,7 @@
/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2020/01/19 06:37:45 by cacharle #+# #+# */
-/* Updated: 2020/01/19 06:50:50 by cacharle ### ########.fr */
+/* Updated: 2020/01/19 13:33:08 by cacharle ### ########.fr */
/* */
/* ************************************************************************** */
@@ -24,6 +24,7 @@ t_stack *stack_new(int size)
return (NULL);
}
stack->top = -1;
+ stack->tag = STACK_NO_TAG;
return (stack);
}
diff --git a/src/push_swap/main.c b/src/push_swap/main.c
index 5019e79..b97feb3 100644
--- a/src/push_swap/main.c
+++ b/src/push_swap/main.c
@@ -1,4 +1,49 @@
+/* ************************************************************************** */
+/* */
+/* ::: :::::::: */
+/* main.c :+: :+: :+: */
+/* +:+ +:+ +:+ */
+/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
+/* +#+#+#+#+#+ +#+ */
+/* Created: 2020/01/19 09:09:59 by cacharle #+# #+# */
+/* Updated: 2020/01/19 13:37:26 by cacharle ### ########.fr */
+/* */
+/* ************************************************************************** */
+
+#include "push_swap.h"
+
int main(int argc, char **argv)
{
+ t_stack *a;
+ t_stack *b;
+
+ if (argc == 1)
+ return (0);
+ if ((a = stack_new(argc - 1)) == NULL)
+ return (1);
+ if (parse(argc, argv, a) != STATUS_SUCCESS)
+ return (1);
+ if ((b = stack_new(stack_length(a))) == NULL)
+ {
+ stack_destroy(a);
+ return (1);
+ }
+
+ a->tag = STACK_A;
+ b->tag = STACK_B;
+
+ push_swap_qsort(a, b);
+ /* push_swap_qsort(a, b); */
+ /* push_swap_qsort(a, b); */
+ /* push_swap_qsort(a, b); */
+ /* push_swap_qsort(a, b); */
+
+ /* printf("\na: "); */
+ /* stack_print(a); */
+ /* printf("b: "); */
+ /* stack_print(b); */
+
+ stack_destroy(a);
+ stack_destroy(b);
return 0;
}
diff --git a/src/push_swap/push_swap.h b/src/push_swap/push_swap.h
index 0e553e0..e22fa9a 100644
--- a/src/push_swap/push_swap.h
+++ b/src/push_swap/push_swap.h
@@ -1,4 +1,33 @@
+/* ************************************************************************** */
+/* */
+/* ::: :::::::: */
+/* push_swap.h :+: :+: :+: */
+/* +:+ +:+ +:+ */
+/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
+/* +#+#+#+#+#+ +#+ */
+/* Created: 2020/01/19 09:10:11 by cacharle #+# #+# */
+/* Updated: 2020/01/19 13:16:06 by cacharle ### ########.fr */
+/* */
+/* ************************************************************************** */
+
#ifndef PUSH_SWAP_H
# define PUSH_SWAP_H
+# include "libft.h"
+# include "common.h"
+
+/*
+** sort.c
+*/
+
+void push_swap_sort(t_stack *main, t_stack *tmp);
+
+/*
+** stack_wrapper.c
+*/
+
+void stack_swap_print(t_stack *stack);
+void stack_rotate_print(t_stack *stack);
+void stack_push_to_print(t_stack *from, t_stack *to);
+
#endif
diff --git a/src/push_swap/sort.c b/src/push_swap/sort.c
new file mode 100644
index 0000000..e1e738e
--- /dev/null
+++ b/src/push_swap/sort.c
@@ -0,0 +1,61 @@
+/* ************************************************************************** */
+/* */
+/* ::: :::::::: */
+/* sort.c :+: :+: :+: */
+/* +:+ +:+ +:+ */
+/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
+/* +#+#+#+#+#+ +#+ */
+/* Created: 2020/01/19 09:12:02 by cacharle #+# #+# */
+/* Updated: 2020/01/19 13:45:37 by cacharle ### ########.fr */
+/* */
+/* ************************************************************************** */
+
+#include "push_swap.h"
+
+/*
+ * pivot == stack top
+ * push pivot to B
+ * iterate over current partition and push < pivot onto B
+ *
+ *
+ *
+ */
+
+void stack_print(t_stack *stack)
+{
+ printf("> ");
+ for (int i = 0; i <= stack->top; i++)
+ printf("%2d | ", stack->elements[i]);
+ printf("\n");
+}
+
+void push_swap_qsort(t_stack *main, t_stack *tmp)
+{
+ int pivot;
+
+ if (stack_length(main) < 2) // if empty or one element, sorted
+ return ;
+ if (stack_length(main) == 2) // if 2 elements and wrong order, swap then sorted
+ {
+ if (stack_peek(main) > main->elements[0])
+ stack_swap_print(main);
+ return ;
+ }
+
+ pivot = stack_peek(main); // get pivot
+ stack_rotate_print(main); // hide pivot
+ while (stack_peek(main) != pivot) // iterate over every element that was bellow pivot in the stack
+ {
+ if (stack_peek(main) < pivot) // if lower than pivot, place it on tmp
+ stack_push_to_print(main, tmp);
+ else // else pass it
+ stack_rotate_print(main);
+ }
+ // main contain all > pivot and the pivot hiself,
+ // tmp contain all < pivot
+ push_swap_qsort(tmp, main); // sort the sub stack tmp
+ stack_push_to_print(main, tmp); // pass the pivot to tmp which is already sorted to sort sub stack main
+ push_swap_qsort(main, tmp); // sort main sub stack
+ while (!stack_empty(tmp)) // push all tmp stack on stack main
+ stack_push_to_print(tmp, main);
+}
diff --git a/src/push_swap/stack_wrapper.c b/src/push_swap/stack_wrapper.c
new file mode 100644
index 0000000..df44e23
--- /dev/null
+++ b/src/push_swap/stack_wrapper.c
@@ -0,0 +1,40 @@
+/* ************************************************************************** */
+/* */
+/* ::: :::::::: */
+/* stack_wrapper.c :+: :+: :+: */
+/* +:+ +:+ +:+ */
+/* By: cacharle <marvin@42.fr> +#+ +:+ +#+ */
+/* +#+#+#+#+#+ +#+ */
+/* Created: 2020/01/19 13:05:58 by cacharle #+# #+# */
+/* Updated: 2020/01/19 13:17:18 by cacharle ### ########.fr */
+/* */
+/* ************************************************************************** */
+
+#include "push_swap.h"
+
+void stack_swap_print(t_stack *stack)
+{
+ if (stack->tag == STACK_A)
+ ft_putendl("sa");
+ if (stack->tag == STACK_B)
+ ft_putendl("sb");
+ stack_swap(stack);
+}
+
+void stack_rotate_print(t_stack *stack)
+{
+ if (stack->tag == STACK_A)
+ ft_putendl("ra");
+ if (stack->tag == STACK_B)
+ ft_putendl("rb");
+ stack_rotate(stack);
+}
+
+void stack_push_to_print(t_stack *from, t_stack *to)
+{
+ if (to->tag == STACK_A)
+ ft_putendl("pa");
+ if (to->tag == STACK_B)
+ ft_putendl("pb");
+ stack_push_to(from, to);
+}
diff --git a/visualizer.rb b/visualizer.rb
new file mode 100755
index 0000000..343b46b
--- /dev/null
+++ b/visualizer.rb
@@ -0,0 +1,116 @@
+#!/usr/bin/ruby
+
+exit if ARGV.length < 1
+
+class Stack
+ attr_accessor :elements
+
+ def initialize(elements)
+ @elements = elements
+ end
+
+ def push(el)
+ @elements.push el
+ end
+
+ def pop
+ return if @elements.length < 1
+ @elements.pop
+ end
+
+ def peek
+ @elements[@elements.length - 1]
+ end
+
+ def swap
+ return if @elements.length < 2
+ first = pop
+ second = pop
+ push(first)
+ push(second)
+ end
+
+ def rotate
+ @elements.rotate! -1
+ end
+
+ def rotate_rev
+ @elements.rotate! 1
+ end
+
+ def to_s
+ @elements.map(&:to_s).join(" | ")
+ end
+end
+
+def green(s)
+ "\033[32m#{s}\033[0m"
+end
+
+def red(s)
+ "\033[31m#{s}\033[0m"
+end
+
+def print_stacks(a, b)
+ puts " A B\n"
+ puts "------------------------------"
+
+ a_str = ARGV.length.times.map { |i| ARGV.length - i }.map do |i|
+ unless a.elements[i].nil?
+ "| " + a.elements[i].to_s.ljust(2) + " " + green(("+" * a.elements[i]).ljust(10)) + "| "
+ else
+ "| #{green(' ' * 10)}| "
+ end
+ end
+ b_str = ARGV.length.times.map { |i| ARGV.length - i }.map do |i|
+ unless b.elements[i].nil?
+ b.elements[i].to_s.ljust(2) + " " + red(("+" * b.elements[i]).ljust(10)) + "|"
+ else
+ " #{red(' ' * 10)}|"
+ end
+ end
+
+ puts a_str.zip(b_str).map { |ab| ab[0] + ab[1] }.join("\n")
+ puts "------------------------------"
+ puts
+end
+
+
+a = Stack.new(ARGV.map(&:to_i))
+b = Stack.new([])
+
+# lines = $stdin.read.split("\n")
+
+$stdin.each_line do |op|
+ print_stacks(a, b)
+ op.strip!
+ puts "> #{op}"
+ case op
+ when "sa" then a.swap
+ when "sb" then b.swap
+ when "ss" then
+ a.swap
+ b.swap
+ when "pa" then
+ a.push b.peek
+ b.pop
+ when "pb" then
+ b.push a.peek
+ a.pop
+ when "ra" then a.rotate
+ when "rb" then b.rotate
+ when "rr" then
+ a.rotate
+ b.rotate
+ when "rra" then a.rotate_rev
+ when "rrb" then b.rotate_rev
+ when "rrr" then
+ a.rotate_rev
+ b.rotate_rev
+ else
+ puts "Error: wrong op"
+ exit
+ end
+end
+
+print_stacks(a, b)
generated by cgit (git 2.34.1) at 2026-05-16 02:19:16 +0000