From d8bb6137b9335369903554c862660e84c285faa7 Mon Sep 17 00:00:00 2001 From: Lukas Jiriste Date: Thu, 29 Feb 2024 17:25:47 +0100 Subject: [PATCH] Implement detection of largest increasing subsequence This lowers the number of operations needed for sorting. We can leave an increasing subsequence inside A because the sorting algorithm before this commit just builded incresing sequence anyway. Leaving a number in stack A costs just one rotate, while pushing it to B costs at least an additional push back to A plus probably a bunch of rotates over it while trying to push other entries back to A. --- Makefile | 1 + src/checker.h | 5 +- src/circular_lis.c | 123 +++++++++++++++++++++++++++++++++++++++++++++ src/helpers.c | 40 ++++++++++++++- src/push.c | 23 ++++++--- src/stacks_mem.c | 4 +- 6 files changed, 186 insertions(+), 10 deletions(-) create mode 100644 src/circular_lis.c diff --git a/Makefile b/Makefile index 554bc7d..a1c984c 100644 --- a/Makefile +++ b/Makefile @@ -34,6 +34,7 @@ PUSHSOURCES := push.c \ helpers.c \ prepare.c \ find.c \ + circular_lis.c \ PUSHSOURCES := $(addprefix $(PUSHSRCDIR)/, $(PUSHSOURCES)) diff --git a/src/checker.h b/src/checker.h index 2288d79..d9aeec0 100644 --- a/src/checker.h +++ b/src/checker.h @@ -6,7 +6,7 @@ /* By: ljiriste +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2024/01/24 12:13:51 by ljiriste #+# #+# */ -/* Updated: 2024/02/29 10:27:01 by ljiriste ### ########.fr */ +/* Updated: 2024/02/29 16:27:28 by ljiriste ### ########.fr */ /* */ /* ************************************************************************** */ @@ -42,6 +42,7 @@ typedef struct s_command t_target target; } t_command; +void free_stack(t_stack *s); void init_stack(t_stack *s); void clean_up(t_stacks *s); /* @@ -67,10 +68,12 @@ void stack_rotate(t_stack *s, int amount); void stack_pop(t_stack *s); int stack_top(t_stack *s); +t_arr_stat get_circular_lis(t_stack *lis, t_stack *stack); int is_sorted(t_stack *s); int parse(int argc, char **argv, t_stack *s); void prepare_stacks(t_stacks *s, size_t ind_a, size_t ind_b); size_t cost(t_stacks *s, const size_t b_plus, const size_t a_plus); +size_t binary_search(t_vec *sorted, t_stack *stack, size_t val_ind); size_t find_best(t_stacks *s, t_vec *target_a_indeces); size_t find_target_ind(t_stack *stack, int val); size_t find_minind(t_stack *s); diff --git a/src/circular_lis.c b/src/circular_lis.c new file mode 100644 index 0000000..b1ccd9b --- /dev/null +++ b/src/circular_lis.c @@ -0,0 +1,123 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* circular_lis.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: ljiriste +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2024/02/27 15:18:21 by ljiriste #+# #+# */ +/* Updated: 2024/02/29 16:59:55 by ljiriste ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "checker.h" +#include "libft.h" + +static t_arr_stat reconstruct_lis(t_stack *lis, t_stack *stack, t_vec *lowest, t_vec *predecessors) +{ + size_t i; + size_t j; + size_t rotation; + t_arr_stat res; + + i = lowest->size - 1; + j = *(size_t *)ft_vec_access(lowest, i); + rotation = -j; + while (i > 0 && j != SIZE_MAX) + { + stack_rotate(stack, -(int)rotation); + res = stack_push(lis, stack_top(stack)); + if (res != success) + return (res); + rotation = j; + j = *(size_t *)ft_vec_access(predecessors, j); + rotation -= j; + } + return (success); +} + +static t_arr_stat get_lis_loop(t_stack *stack, t_vec *inds_of_lowest, t_vec *inds_of_predecessor) +{ + size_t i; + size_t new_ind; + t_arr_stat res; + static const size_t invalid = SIZE_MAX; + + i = 0; + while (i < stack->stack.size) + { + new_ind = binary_search(inds_of_lowest, stack, i); + if (new_ind == inds_of_lowest->size) + res = ft_vec_append(inds_of_lowest, &i); + else + *(size_t *)ft_vec_access(inds_of_lowest, new_ind) = i; + if (res != success) + break; + if (new_ind == 0) + res = ft_vec_append(inds_of_predecessor, &invalid); + else + res = ft_vec_append(inds_of_predecessor, ft_vec_access(inds_of_lowest, new_ind - 1)); + if (res != success) + break; + ++i; + } + return (res); +} + +/* This is the algorithm for finding the longest increasing subsequence + found on wikipedia adjusted for circular sequences (stack).*/ +static t_arr_stat get_lis(t_stack *lis, t_stack *stack, size_t ind) +{ + t_vec inds_of_lowest; + t_vec inds_of_predecessor; + const size_t stack_init_ind = stack->ind; + t_arr_stat res; + + ft_vec_init(&inds_of_lowest, sizeof(size_t)); + ft_vec_init(&inds_of_predecessor, sizeof(size_t)); + stack_rotate(stack, ind); + res = get_lis_loop(stack, &inds_of_lowest, &inds_of_predecessor); + if (res == success) + reconstruct_lis(lis, stack, &inds_of_lowest, &inds_of_predecessor); + ft_vec_free(&inds_of_lowest, NULL); + ft_vec_free(&inds_of_predecessor, NULL); + stack->ind = stack_init_ind; + return (res); +} + +static size_t lis_length(t_stack *stack) +{ + t_stack lis; + size_t res; + + init_stack(&lis); + if (get_lis(&lis, stack, 0) == success) + res = lis.stack.size; + else + res = 0; + free_stack(&lis); + return (res); +} + +t_arr_stat get_circular_lis(t_stack *lis, t_stack *stack) +{ + size_t max; + size_t max_ind; + size_t i; + size_t len_i; + + max = 0; + i = 0; + while (i < stack->stack.size) + { + len_i = lis_length(stack); + if (len_i > max) + { + max = len_i; + max_ind = i; + } + ++i; + stack_rotate(stack, 1); + } + return (get_lis(lis, stack, max_ind)); +} diff --git a/src/helpers.c b/src/helpers.c index ef0a1c3..ee17362 100644 --- a/src/helpers.c +++ b/src/helpers.c @@ -6,7 +6,7 @@ /* By: ljiriste +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2024/02/22 14:22:08 by ljiriste #+# #+# */ -/* Updated: 2024/02/24 14:09:17 by ljiriste ### ########.fr */ +/* Updated: 2024/02/29 16:20:32 by ljiriste ### ########.fr */ /* */ /* ************************************************************************** */ @@ -72,3 +72,41 @@ size_t cost(t_stacks *s, const size_t b_plus, const size_t a_plus) res = ft_mins(res, a_minus + b_plus); return (res); } + +static int unrolled_stack_access(t_stack *stack, size_t ind) +{ + int res; + + if (ind > SIZE_MAX - stack->ind) + ind -= SIZE_MAX; + ind += stack->ind; + ind %= stack->stack.size; + res = *(int *)ft_vec_access(&stack->stack, ind); + return (res); +} + +size_t binary_search(t_vec *sorted, t_stack *stack, size_t val_ind) +{ + const int val = unrolled_stack_access(stack, val_ind); + size_t hi; + size_t lo; + size_t mid; + + lo = 0; + hi = sorted->size; + mid = lo + (hi - lo) / 2; + while (lo != hi) + { + if (val > unrolled_stack_access(stack, *(size_t *)ft_vec_access(sorted, mid))) + { + lo = mid + 1; + } + else + { + hi = mid; + } + mid = lo + (hi - lo) / 2; + } + return (mid); +} + diff --git a/src/push.c b/src/push.c index fcf5b9d..8bc0fb5 100644 --- a/src/push.c +++ b/src/push.c @@ -6,7 +6,7 @@ /* By: ljiriste +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2024/01/24 13:17:32 by ljiriste #+# #+# */ -/* Updated: 2024/02/24 14:10:54 by ljiriste ### ########.fr */ +/* Updated: 2024/02/29 14:41:41 by ljiriste ### ########.fr */ /* */ /* ************************************************************************** */ @@ -91,14 +91,25 @@ void rotate_a_to_sort(t_stacks *s) void sort(t_stacks *s) { - int ind_a; - int ind_b; + int ind_a; + int ind_b; + t_stack lis; - while (s->a.stack.size > 3) + init_stack(&lis); + get_circular_lis(&lis, &s->a); + while (s->a.stack.size > lis.stack.size && s->a.stack.size > 3) { - print_push(s, b); + if (stack_top(&lis) == stack_top(&s->a)) + { + stack_rotate(&lis, 1); + print_rotate(s, a); + } + else + print_push(s, b); } - a_sort_three_or_less(s); + free_stack(&lis); + if (lis.stack.size < 3) + a_sort_three_or_less(s); while (s->b.stack.size > 0) { get_push_indeces(s, &ind_a, &ind_b); diff --git a/src/stacks_mem.c b/src/stacks_mem.c index dac4dc1..fe68df3 100644 --- a/src/stacks_mem.c +++ b/src/stacks_mem.c @@ -6,7 +6,7 @@ /* By: ljiriste +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2024/02/06 14:20:04 by ljiriste #+# #+# */ -/* Updated: 2024/02/06 14:22:06 by ljiriste ### ########.fr */ +/* Updated: 2024/02/29 11:10:56 by ljiriste ### ########.fr */ /* */ /* ************************************************************************** */ @@ -20,7 +20,7 @@ void init_stack(t_stack *s) return ; } -static void free_stack(t_stack *s) +void free_stack(t_stack *s) { ft_vec_free(&s->stack, NULL); s->ind = 0; -- 2.30.2