From 84afbdb87015a01bc7fbdca65810e3d5469bb89b Mon Sep 17 00:00:00 2001 From: Lukas Jiriste Date: Wed, 24 Jan 2024 14:44:15 +0100 Subject: [PATCH 1/1] Start the project, implement checker --- .gitignore | 3 + .gitmodules | 3 + Libft | 1 + Makefile | 71 +++++++++++ src_checker/actions.c | 55 +++++++++ src_checker/checker.c | 198 +++++++++++++++++++++++++++++++ src_checker/checker.h | 56 +++++++++ src_checker/stack_manipulation.c | 67 +++++++++++ src_push/push.c | 19 +++ 9 files changed, 473 insertions(+) create mode 100644 .gitignore create mode 100644 .gitmodules create mode 160000 Libft create mode 100644 Makefile create mode 100644 src_checker/actions.c create mode 100644 src_checker/checker.c create mode 100644 src_checker/checker.h create mode 100644 src_checker/stack_manipulation.c create mode 100644 src_push/push.c diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..b8eaf4c --- /dev/null +++ b/.gitignore @@ -0,0 +1,3 @@ +checker +push_swap +*.o diff --git a/.gitmodules b/.gitmodules new file mode 100644 index 0000000..626d139 --- /dev/null +++ b/.gitmodules @@ -0,0 +1,3 @@ +[submodule "Libft"] + path = Libft + url = git://ljiriste.work/Libft diff --git a/Libft b/Libft new file mode 160000 index 0000000..a4212a0 --- /dev/null +++ b/Libft @@ -0,0 +1 @@ +Subproject commit a4212a0f1de2cf7553f3cde8931c90fe006f3cd4 diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..b5dfb58 --- /dev/null +++ b/Makefile @@ -0,0 +1,71 @@ +CC := gcc +#CFLAGS = -std=c99 -Wall -Wextra -Werror -Wpedantic +CFLAGS = -Wall -Wextra -Werror -Wpedantic + +RM := rm -f + +SUBPROJECTS := Libft + +INCDIR := src_checker +SUBINCDIR := $(addsuffix /inc, $(SUBPROJECTS)); +INCLUDE := $(addprefix -I, $(INCDIR) $(SUBINCDIR)) + +CHECKSRCDIR := src_checker + +CHECKSOURCES := checker.c \ + actions.c \ + stack_manipulation.c \ + +CHECKSOURCES := $(addprefix $(CHECKSRCDIR)/, $(CHECKSOURCES)) + +CHECKOBJECTS := $(CHECKSOURCES:.c=.o) + +PUSHSRCDIR = src_push + +PUSHSOURCES := push.c \ + +PUSHSOURCES := $(addprefix $(PUSHSRCDIR)/, $(PUSHSOURCES)) + +PUSHOBJECTS := $(PUSHSOURCES:.c=.o) + +OBJECTS := $(PUSHOBJECTS) $(CHECKOBJECTS) + +NAME := push_swap checker + +all : $(NAME) + +debug : CFLAGS += -g +debug : $(NAME) + +push_swap : $(PUSHOBJECTS) Libft/libft.a + $(CC) $(CFLAGS) -o $@ $^ + +checker : $(CHECKOBJECTS) Libft/libft.a + $(CC) $(CFLAGS) -o $@ $^ + +# Libft is not dependant on all subprojects (only itself) +# but this shouldn't be a problem, as the project needs to download all anyway +Libft/libft.a : | $(SUBINCDIR) +ifneq (,$(findstring debug, $(MAKECMDGOALS))) + $(MAKE) -C Libft debug +else + $(MAKE) -C Libft +endif + +%.o : %.c + $(CC) $(CFLAGS) -o $@ -c $< $(INCLUDE) + +%/inc : + git submodule update --init $($@%/inc=%) + +clean : + $(RM) $(OBJECTS) + $(foreach proj, $(SUBPROJECTS), $(MAKE) -C $(proj) clean) + +fclean : + $(RM) $(OBJECTS) + $(RM) $(NAME) + $(foreach proj, $(SUBPROJECTS), $(MAKE) -C $(proj) fclean) + +re : fclean + $(MAKE) all diff --git a/src_checker/actions.c b/src_checker/actions.c new file mode 100644 index 0000000..19d55ff --- /dev/null +++ b/src_checker/actions.c @@ -0,0 +1,55 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* actions.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: ljiriste +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2024/01/24 11:46:02 by ljiriste #+# #+# */ +/* Updated: 2024/01/24 13:49:25 by ljiriste ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "checker.h" + +void action_rotate(t_stacks *s, t_target target) +{ + if (target == a || target == both) + stack_rotate(&s->a, 1); + if (target == b || target == both) + stack_rotate(&s->b, 1); + return ; +} + +void action_reverse_rotate(t_stacks *s, t_target target) +{ + if (target == a || target == both) + stack_rotate(&s->a, -1); + if (target == b || target == both) + stack_rotate(&s->b, -1); + return ; +} + +void action_swap(t_stacks *s, t_target target) +{ + if (target == a || target == both) + stack_swap(&s->a); + if (target == b || target == both) + stack_swap(&s->b); + return ; +} + +void action_push(t_stacks *s, t_target target) +{ + if ((target == a || target == both) && s->b.stack.size != 0) + { + stack_push(&s->a, stack_top(&s->b)); + stack_pop(&s->b); + } + if ((target == b || target == both) && s->a.stack.size != 0) + { + stack_push(&s->b, stack_top(&s->a)); + stack_pop(&s->a); + } + return ; +} diff --git a/src_checker/checker.c b/src_checker/checker.c new file mode 100644 index 0000000..a2c6994 --- /dev/null +++ b/src_checker/checker.c @@ -0,0 +1,198 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* checker.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: ljiriste +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2024/01/24 10:31:06 by ljiriste #+# #+# */ +/* Updated: 2024/01/24 14:41:00 by ljiriste ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "checker.h" +#include "libft.h" +#include + +#define COMMANDS_NUM 11 + +static int command_parse(const char *input, t_command *command) +{ + const size_t len = ft_strlen(input); + const char *com_str[COMMANDS_NUM] = {"sa", "sb", "ss", "pa", "pb", "ra", "rb", "rr", "rra", "rrb", "rrr"}; + size_t i; + + i = 0; + while (1) + { + if (!ft_strcmp(input, com_str[i++])) + break ; + if (i == COMMANDS_NUM) + return (1); + } + if (len == 3) + command->action = action_reverse_rotate; + else if (input[0] == 's') + command->action = action_swap; + else if (input[0] == 'p') + command->action = action_push; + else if (input[0] == 'r') + command->action = action_rotate; + if (input[len - 1] == 'a') + command->target = a; + else if (input[len - 1] == 'b') + command->target = b; + else + command->target = both; + return (0); +} + +static void execute(t_command command, t_stacks *s) +{ + command.action(s, command.target); + return ; +} + +static int interpret(t_stacks *s) +{ + char *input; + t_command command; + + input = get_next_line(0); + while (input) + { + input[ft_strlen(input) - 1] = '\0'; + if (command_parse(input, &command)) + { + free(input); + return (1); + } + execute(command, s); + free(input); + input = get_next_line(0); + } + return (0); +} + +void init_stack(t_stack *s) +{ + ft_vec_init(&s->stack, sizeof(int)); + s->ind = 0; + return ; +} + +void free_stack(t_stack *s) +{ + ft_vec_free(&s->stack, NULL); + s->ind = 0; + return ; +} + +int is_sorted(t_stack *s) +{ + const size_t start_ind = s->ind; + int prev; + int cur; + + prev = stack_top(s); + stack_rotate(s, 1); + while (s->ind != start_ind) + { + cur = stack_top(s); + if (cur <= prev) + return (0); + prev = cur; + stack_rotate(s, 1); + } + return (1); +} + +int is_int(const char *str) +{ + char *test; + + test = ft_itoa(ft_atoi(str)); + if (ft_strcmp(str, test)) + { + free(test); + return (0); + } + free(test); + return (1); +} + +int contains(int new, t_stack *s) +{ + const size_t start_ind = s->ind; + int cur; + + if (s->stack.size == 0) + return (0); + cur = stack_top(s); + if (cur == new) + return (1); + stack_rotate(s, 1); + while (s->ind != start_ind) + { + cur = stack_top(s); + if (cur == new) + return (1); + stack_rotate(s, 1); + } + return (0); +} + +int parse(int argc, char **argv, t_stack *s) +{ + size_t i; + int new; + + if (argc == 1) + return (1); + i = 1; + while (i < (size_t)argc) + { + if (!is_int(argv[i])) + return (1); + new = ft_atoi(argv[i]); + if (contains(new, s)) + return (1); + stack_push(s, new); + stack_rotate(s, 1); + ++i; + } + return (0); +} + +void clean_up(t_stacks *s) +{ + free_stack(&s->a); + free_stack(&s->b); + return ; +} + +int main(int argc, char **argv) +{ + t_stacks s; + + init_stack(&s.a); + init_stack(&s.b); + if (parse(argc, argv, &s.a)) + { + clean_up(&s); + ft_printf("Error.\n"); + return (1); + } + if (interpret(&s)) + { + clean_up(&s); + ft_printf("Error.\n"); + return (1); + } + if (is_sorted(&s.a) && s.b.stack.size == 0) + ft_printf("OK\n"); + else + ft_printf("KO\n"); + clean_up(&s); + return (0); +} diff --git a/src_checker/checker.h b/src_checker/checker.h new file mode 100644 index 0000000..ab16b7e --- /dev/null +++ b/src_checker/checker.h @@ -0,0 +1,56 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* checker.h :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: ljiriste +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2024/01/24 12:13:51 by ljiriste #+# #+# */ +/* Updated: 2024/01/24 12:21:55 by ljiriste ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#ifndef CHECKER_H +# define CHECKER_H + +# include "libft.h" + +typedef struct s_stack +{ + t_vec stack; + size_t ind; +} t_stack; + +typedef struct s_stacks +{ + t_stack a; + t_stack b; +} t_stacks; + +typedef enum e_target +{ + a, + b, + both, +} t_target; + +typedef void(t_action(t_stacks *s, t_target target)); + +typedef struct s_command +{ + t_action *action; + t_target target; +} t_command; + +t_action action_push; +t_action action_swap; +t_action action_rotate; +t_action action_reverse_rotate; + +void stack_push(t_stack *s, int el); +void stack_swap(t_stack *s); +void stack_rotate(t_stack *s, int amount); +void stack_pop(t_stack *s); +int stack_top(t_stack *s); + +#endif //CHECKER_H diff --git a/src_checker/stack_manipulation.c b/src_checker/stack_manipulation.c new file mode 100644 index 0000000..5003b62 --- /dev/null +++ b/src_checker/stack_manipulation.c @@ -0,0 +1,67 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* stack_manipulation.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: ljiriste +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2024/01/24 11:48:47 by ljiriste #+# #+# */ +/* Updated: 2024/01/24 13:59:25 by ljiriste ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "checker.h" +#include "libft.h" + +// conversions are meh +// maybe it would be better to have size_t amount and third arg for direction +void stack_rotate(t_stack *s, int amount) +{ + if (s->stack.size == 0) + return ; + while (amount < 0) + amount += s->stack.size; + if (s->ind > SIZE_MAX - (size_t)amount) + s->ind -= s->stack.size; + s->ind = (s->ind + amount) % s->stack.size; + return ; +} + +// Not great, because one does not know whether +// result of zero is error +int stack_top(t_stack *s) +{ + if (s->stack.size == 0) + return (0); + return (*(int *)ft_vec_access(&s->stack, s->ind)); +} + +void stack_pop(t_stack *s) +{ + if (s->stack.size == 0) + return ; + ft_vec_forget(&s->stack, s->ind); + if (s->stack.size > 0) + s->ind %= s->stack.size; + return ; +} + +void stack_push(t_stack *s, int el) +{ + ft_vec_insert(&s->stack, &el, s->ind); + return ; +} + +void stack_swap(t_stack *s) +{ + int tmp; + + if (s->stack.size <= 1) + return ; + tmp = stack_top(s); + stack_pop(s); + stack_rotate(s, 1); + stack_push(s, tmp); + stack_rotate(s, -1); + return ; +} diff --git a/src_push/push.c b/src_push/push.c new file mode 100644 index 0000000..5184574 --- /dev/null +++ b/src_push/push.c @@ -0,0 +1,19 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* push.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: ljiriste +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2024/01/24 13:17:32 by ljiriste #+# #+# */ +/* Updated: 2024/01/24 13:18:17 by ljiriste ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "libft.h" + +int main(void) +{ + ft_printf("TODO: Implement push_swap.\n"); + return (0); +} -- 2.30.2