From 83edb77d74bb339f3e1324a51039c78ac503db90 Mon Sep 17 00:00:00 2001 From: Charles Date: Wed, 24 Jul 2019 18:46:39 +0200 Subject: bsq and c13 passed --- bsq/.gitignore | 2 - bsq/Makefile | 37 ++++++----- bsq/algo.c | 74 ++++++++++++++++++++++ bsq/auteur | 2 +- bsq/bsq | Bin 0 -> 13776 bytes bsq/helper.c | 132 ++++++++++++++++++++++++++++++++++++++++ bsq/include.h | 98 +++++++++++++++++++++++++++++ bsq/includes/include.h | 63 ------------------- bsq/main.c | 37 +++++++++++ bsq/parse.c | 91 +++++++++++++++++++++++++++ bsq/parse_helper.c | 101 ++++++++++++++++++++++++++++++ bsq/srcs/helper.c | 62 ------------------- bsq/srcs/main.c | 20 ------ bsq/srcs/parse.c | 42 ------------- bsq/terrain.c | 78 ++++++++++++++++++++++++ bsq/tests/generate.pl | 21 ------- bsq/utils.c | 87 ++++++++++++++++++++++++++ c13/ex00/ft_btree.h | 10 +-- c13/ex01/btree_apply_prefix.c | 9 +-- c13/ex01/ft_btree.h | 8 +-- c13/ex02/btree_apply_infix.c | 9 +-- c13/ex02/ft_btree.h | 8 +-- c13/ex03/btree_apply_suffix.c | 9 +-- c13/ex03/ft_btree.h | 8 +-- c13/ex04/btree_insert_data.c | 16 ++--- c13/ex04/ft_btree.h | 10 +-- c13/ex05/btree_search_item.c | 20 +++++- c13/ex05/ft_btree.h | 8 +-- c13/ex06/btree_level_count.c | 33 ++++++++++ c13/ex06/ft_btree.h | 8 +-- c13/ex07/btree_apply_by_level.c | 0 c13/ex07/ft_btree.h | 8 +-- c13/ft_btree.h | 23 ------- c13/main.c | 90 +++++++++++++++++++++++++++ 34 files changed, 922 insertions(+), 302 deletions(-) delete mode 100644 bsq/.gitignore create mode 100644 bsq/algo.c create mode 100755 bsq/bsq create mode 100644 bsq/helper.c create mode 100644 bsq/include.h delete mode 100644 bsq/includes/include.h create mode 100644 bsq/main.c create mode 100644 bsq/parse.c create mode 100644 bsq/parse_helper.c delete mode 100644 bsq/srcs/helper.c delete mode 100644 bsq/srcs/main.c delete mode 100644 bsq/srcs/parse.c create mode 100644 bsq/terrain.c delete mode 100755 bsq/tests/generate.pl create mode 100644 bsq/utils.c delete mode 100644 c13/ex07/btree_apply_by_level.c delete mode 100644 c13/ft_btree.h create mode 100644 c13/main.c diff --git a/bsq/.gitignore b/bsq/.gitignore deleted file mode 100644 index d7756c2..0000000 --- a/bsq/.gitignore +++ /dev/null @@ -1,2 +0,0 @@ -a.out -*.o diff --git a/bsq/Makefile b/bsq/Makefile index 11cddfa..106b4d5 100644 --- a/bsq/Makefile +++ b/bsq/Makefile @@ -6,41 +6,50 @@ # By: cacharle +#+ +:+ +#+ # # +#+#+#+#+#+ +#+ # # Created: 2019/07/19 12:09:54 by cacharle #+# #+# # -# Updated: 2019/07/19 15:18:19 by cacharle ### ########.fr # +# Updated: 2019/07/24 17:47:26 by cacharle ### ########.fr # # # # **************************************************************************** # -OUT = bsq -SRCDIR = srcs -SRC = $(SRCDIR)/main.c +NAME = bsq +SRC = main.c algo.c helper.c terrain.c parse.c parse_helper.c utils.c OBJ = $(SRC:.c=.o) -INCLUDES = includes/include.h +INCLUDES = include.h -CC = gcc -CCFLAGS = -Wall -Wextra #-Werror -LDFLAGS = -Iincludes +CC = cc +CCFLAGS = -Wall -Wextra -Werror ARGS = 10 10 2 .PHONY: all -all: $(OUT) +all: $(NAME) -$(OUT): $(OBJ) - $(CC) $(CCFLAGS) $(LDFLAGS) -o $@ $^ +$(NAME): $(OBJ) + $(CC) $(CCFLAGS) -o $@ $^ %.o: %.c $(INCLUDES) - $(CC) $(CCFLAGS) $(LDFLAGS) -c -o $@ $< + $(CC) $(CCFLAGS) -c -o $@ $< .PHONY: clean +clean: rm -f $(OBJ) .PHONY: fclean fclean: clean - rm -f $(OUT) + rm -f $(NAME) .PHONY: re re: fclean all .PHONY: generate generate: - ./tests/generate.pl ${ARGS} + @./tests/generate.pl ${ARGS} + +.PHONY: test +test: all + @./tests/generate.pl ${ARGS} > ./tests/boardtest + @./$(NAME) ./tests/boardtest + +.PHONY: flex +flex: + @./tests/generate.pl 360 80 100000 > tests/printable + @./bsq ./tests/printable diff --git a/bsq/algo.c b/bsq/algo.c new file mode 100644 index 0000000..df4bc85 --- /dev/null +++ b/bsq/algo.c @@ -0,0 +1,74 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* algo.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: samzur +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2019/07/22 12:32:19 by samzur #+# #+# */ +/* Updated: 2019/07/24 09:38:57 by samzur ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include "include.h" + +int ft_min(int nb1, int nb2, int nb3) +{ + int minimum; + + minimum = nb1; + if (minimum > nb2) + minimum = nb2; + if (minimum > nb3) + minimum = nb3; + return (minimum); +} + +t_cell solve(t_terrain *terrain) +{ + t_cell result; + int x; + int y; + + y = -1; + result.y = 0; + result.x = 0; + result.value = 0; + while (++y < terrain->rows) + { + x = -1; + while (++x < terrain->columns) + { + if (terrain->matrix[y][x] > OBSTACLE && x != 0 && y != 0) + terrain->matrix[y][x] = 1 + ft_min(terrain->matrix[y - 1][x], + terrain->matrix[y][x - 1], terrain->matrix[y - 1][x - 1]); + if (terrain->matrix[y][x] > result.value) + { + result.value = terrain->matrix[y][x]; + result.y = y; + result.x = x; + } + } + } + return (result); +} + +void solve_and_complete(t_terrain *terrain) +{ + t_cell result; + int row; + int column; + + result = solve(terrain); + column = result.x; + while (column >= (result.x - result.value + 1)) + { + row = result.y; + while (row >= (result.y - result.value + 1)) + { + terrain->matrix[row][column] = FILLED; + row--; + } + column--; + } +} diff --git a/bsq/auteur b/bsq/auteur index ab605b4..6cb1cd5 100644 --- a/bsq/auteur +++ b/bsq/auteur @@ -1 +1 @@ -samzur:cacharle +cacharle:samzur diff --git a/bsq/bsq b/bsq/bsq new file mode 100755 index 0000000..a3a16b1 Binary files /dev/null and b/bsq/bsq differ diff --git a/bsq/helper.c b/bsq/helper.c new file mode 100644 index 0000000..0b2e935 --- /dev/null +++ b/bsq/helper.c @@ -0,0 +1,132 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* helper.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: cacharle +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2019/07/19 15:19:53 by cacharle #+# #+# */ +/* Updated: 2019/07/24 17:59:52 by cacharle ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include +#include +#include "include.h" + +/* + ** Dynamic allocation of buffer +*/ + +char *read_file(int fildes) +{ + char *buf; + char *file; + int file_size; + int read_size; + int buf_size; + + buf_size = INIT_BUF_SIZE; + file_size = 0; + file = NULL; + if ((buf = malloc(sizeof(char) * buf_size)) == NULL) + return (NULL); + while ((read_size = read(fildes, buf, buf_size))) + { + if (read_size < 0) + return (NULL); + if ((file = ft_memcat(file, buf, file_size, read_size)) == NULL) + return (NULL); + file_size += read_size; + buf_size *= GROWTH_FACTOR; + if ((buf = realloc_buf(buf, buf_size)) == NULL) + return (NULL); + } + free(buf); + return (file); +} + +/* + ** Reallocate a bigger memory space for file to write what in the buffer +*/ + +char *ft_memcat(char *file, char *buf, int file_size, + int read_size) +{ + int i; + char *file_clone; + + if ((file_clone = malloc(sizeof(char) * (file_size + 1))) == NULL) + return (NULL); + i = -1; + while (++i < file_size) + file_clone[i] = file[i]; + free(file); + if ((file = malloc(sizeof(char) * (file_size + read_size + 1))) == NULL) + return (NULL); + i = 0; + while (i < file_size) + { + file[i] = file_clone[i]; + i++; + } + free(file_clone); + while (i < file_size + read_size) + { + file[i] = buf[i - file_size]; + i++; + } + file[i] = '\0'; + return (file); +} + +/* + ** Reallocate a new buffer and free the old one +*/ + +char *realloc_buf(char *buf, int buf_size) +{ + free(buf); + if ((buf = (char*)malloc(sizeof(char) * buf_size)) == NULL) + return (NULL); + return (buf); +} + +/* + ** Return the n number of a string and return it as an int +*/ + +int ft_natoi(char *str, unsigned int n) +{ + int nb; + unsigned int i; + + nb = 0; + i = 0; + while (str[i] && i < n) + { + if (str[i] < '0' || str[i] > '9') + return (-1); + i++; + } + if (i == 0) + return (-1); + i = 0; + while (str[i] && i < n) + { + nb *= 10; + nb += str[i++] - '0'; + } + if (nb == 0) + return (-1); + return (nb); +} + +/* + ** Print one character in the standard output +*/ + +void ft_putchar(char c) +{ + write(STDOUT_FILENO, &c, 1); +} diff --git a/bsq/include.h b/bsq/include.h new file mode 100644 index 0000000..be8daf0 --- /dev/null +++ b/bsq/include.h @@ -0,0 +1,98 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* include.h :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: cacharle +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2019/07/19 13:17:32 by cacharle #+# #+# */ +/* Updated: 2019/07/24 11:51:17 by samzur ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#ifndef INCLUDE_H +# define INCLUDE_H + +# define TRUE 1 +# define FALSE 0 +# define INIT_BUF_SIZE 2 +# define GROWTH_FACTOR 2 +# define EMPTY 1 +# define OBSTACLE 0 +# define FILLED -1 + +typedef struct s_terrain +{ + int rows; + int columns; + int **matrix; +} t_terrain; + +typedef struct s_parsed_terrain +{ + char empty; + char obstacle; + char filled; + t_terrain *terrain; +} t_parsed_terrain; + +typedef struct s_cell +{ + int y; + int x; + int value; +} t_cell; + +/* +** helper.c - previously made functions +*/ + +char *read_file(int fildes); +char *ft_memcat(char *file, char *buf, int file_size, + int read_size); +char *realloc_buf(char *buf, int buf_size); +int ft_natoi(char *str, unsigned int n); +void ft_putchar(char c); + +/* +** algo.c - solve the thing +*/ + +int ft_min(int nb1, int nb2, int nb3); +t_cell solve(t_terrain *terrain); +void solve_and_complete(t_terrain *terrain); + +/* +** parse.c - map parsing +*/ + +int parse_file(char *filename, t_parsed_terrain *pterrain); +int parse_fildes(int fildes, t_parsed_terrain *pterrain); +int parse(char *file, t_parsed_terrain *pterrain); + +/* +** parse_helper.c - parse.c sub functions +*/ + +int *set_row(char *file, t_parsed_terrain *pterrain, int y); +int set_dimensions(char *file, t_parsed_terrain *pterrain); +int parse_header(char *file, t_parsed_terrain *pterrain); + +/* +** terrain.c - terrain manipulation +*/ + +void destroy_terrain(t_terrain *terrain); +void print_terrain(t_parsed_terrain *parsed_terrain); +int terrain_to_string(t_parsed_terrain *pterrain, char *str); + +/* +** utils.c - random stuff I need to put somewhere +*/ + +void parse_stdin_print(void); +void parse_file_print(char *filename); +int count_lines(char *file); +int ft_line_len(char *str); + +#endif diff --git a/bsq/includes/include.h b/bsq/includes/include.h deleted file mode 100644 index d505857..0000000 --- a/bsq/includes/include.h +++ /dev/null @@ -1,63 +0,0 @@ -/* ************************************************************************** */ -/* */ -/* ::: :::::::: */ -/* include.h :+: :+: :+: */ -/* +:+ +:+ +:+ */ -/* By: cacharle +#+ +:+ +#+ */ -/* +#+#+#+#+#+ +#+ */ -/* Created: 2019/07/19 13:17:32 by cacharle #+# #+# */ -/* Updated: 2019/07/19 15:55:03 by cacharle ### ########.fr */ -/* */ -/* ************************************************************************** */ - -#ifndef INCLUDE_H -# define INCLUDE_H - -# define TRUE 1 -# define FALSE 0 -# define EMPTY 0 -# define OBSTACLE 1 - -struct s_square -{ - int size; - int x; - int y; -}; - -struct s_terrain -{ - char empty; - char fill; - char obstacle; - int size; - char *file; -} - -typedef struct s_terrain t_terrain; -typedef struct s_square t_square; -typedef int t_bool; - -/* -** solve.c - Solve the thing (yes) -*/ - - -/* -** parse.c - Input parsing -** Put file in string, parse it and check if it's valid -*/ - -t_bool check_input(char *input); - -/* -** helper.c - function already made -*/ - -int read_file(int fildes, char **file); -char *ft_memcat(char *file, char buf[BUF_SIZE], int file_size, - int read_size); - - - -#endif diff --git a/bsq/main.c b/bsq/main.c new file mode 100644 index 0000000..f981f25 --- /dev/null +++ b/bsq/main.c @@ -0,0 +1,37 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* main.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: cacharle +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2019/07/19 11:01:32 by cacharle #+# #+# */ +/* Updated: 2019/07/24 14:50:39 by cacharle ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include +#include +#include "include.h" + +int main(int argc, char **argv) +{ + int i; + t_parsed_terrain *pterrain; + + pterrain = NULL; + if (argc == 1) + { + parse_stdin_print(); + return (0); + } + i = 1; + while (i < argc) + { + parse_file_print(argv[i]); + if (i != argc - 1) + ft_putchar('\n'); + i++; + } + return (0); +} diff --git a/bsq/parse.c b/bsq/parse.c new file mode 100644 index 0000000..38be033 --- /dev/null +++ b/bsq/parse.c @@ -0,0 +1,91 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* parse.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: cacharle +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2019/07/19 15:23:43 by cacharle #+# #+# */ +/* Updated: 2019/07/24 12:19:39 by samzur ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include +#include +#include +#include "include.h" + +/* +** open the file, pass it to parse_fildes +*/ + +int parse_file(char *filename, t_parsed_terrain *pterrain) +{ + int fildes; + + if ((fildes = open(filename, O_RDONLY)) < 0) + return (-1); + if (parse_fildes(fildes, pterrain) < 0) + { + close(fildes); + return (-1); + } + if (close(fildes) < 0) + return (-1); + return (0); +} + +/* +** read file designated by fildes in `file`, pass it to parse, +** free the file string +** return -1 in case of error, 0 otherwise +*/ + +int parse_fildes(int fildes, t_parsed_terrain *pterrain) +{ + char *file; + + if ((file = read_file(fildes)) == NULL) + return (-1); + if (parse(file, pterrain) < 0) + { + free(file); + return (-1); + } + free(file); + return (0); +} + +/* +** parse the file string, initialise pterrain attributes +** return -1 in case of error, 0 otherwise +*/ + +int parse(char *file, t_parsed_terrain *pterrain) +{ + int y; + int i; + + if ((pterrain->terrain = (t_terrain*)malloc(sizeof(t_terrain))) == NULL) + return (-1); + if ((i = parse_header(file, pterrain)) < 0) + { + free(pterrain->terrain); + return (-1); + } + if (set_dimensions(&file[i], pterrain) < 0 || (pterrain->terrain->matrix = + (int**)malloc(sizeof(int*) * pterrain->terrain->rows)) == NULL) + { + free(pterrain->terrain); + return (-1); + } + y = -1; + while (++y < pterrain->terrain->rows) + if ((pterrain->terrain->matrix[y] = set_row(file, pterrain, y)) == NULL) + { + destroy_terrain(pterrain->terrain); + free(pterrain); + return (-1); + } + return (0); +} diff --git a/bsq/parse_helper.c b/bsq/parse_helper.c new file mode 100644 index 0000000..56d0f6d --- /dev/null +++ b/bsq/parse_helper.c @@ -0,0 +1,101 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* parse_helper.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: cacharle +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2019/07/23 19:24:06 by cacharle #+# #+# */ +/* Updated: 2019/07/24 12:04:33 by samzur ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include +#include "include.h" + +/* +** initialise the `y` row of the matrix +*/ + +int *set_row(char *file, t_parsed_terrain *pterrain, int y) +{ + int i; + int x; + int *row; + + if ((row = (int*)malloc(sizeof(int) * pterrain->terrain->columns)) == NULL) + return (NULL); + i = ft_line_len(file) + 1; + i += (ft_line_len(&file[i]) + 1) * y; + x = 0; + while (x < pterrain->terrain->columns) + { + if (file[i] == pterrain->empty) + row[x] = EMPTY; + else if (file[i] == pterrain->obstacle) + row[x] = OBSTACLE; + i++; + x++; + } + return (row); +} + +/* +** set dimensions of the terrain and check they correspond with the terrain, +** also check the character used for the cell types +** return -1 in case of error, 0 otherwise. +*/ + +int set_dimensions(char *file, t_parsed_terrain *pterrain) +{ + int i; + int j; + int first_line_len; + int line_len; + + first_line_len = ft_line_len(file); + if (first_line_len == 0) + return (-1); + i = 0; + while (file[i]) + { + line_len = ft_line_len(&file[i]); + if (line_len != first_line_len) + return (-1); + j = -1; + while (++j < line_len) + if (file[i + j] != pterrain->empty + && file[i + j] != pterrain->obstacle) + return (-1); + i += line_len + 1; + } + pterrain->terrain->columns = first_line_len; + return (0); +} + +/* +** Parse header and check if everything is ok (number, obstacles, duplicates) +*/ + +int parse_header(char *file, t_parsed_terrain *pterrain) +{ + int i; + + i = ft_line_len(file); + if (i < 4) + return (-1); + pterrain->filled = file[--i]; + pterrain->obstacle = file[--i]; + pterrain->empty = file[--i]; + if (pterrain->filled == pterrain->obstacle + || pterrain->filled == pterrain->empty + || pterrain->obstacle == pterrain->empty) + return (-1); + if ((pterrain->terrain->rows = ft_natoi(file, i)) < 0) + return (-1); + i = ft_line_len(file) + 1; + if (pterrain->terrain->rows != count_lines(&file[i]) + || pterrain->terrain->rows == 0) + return (-1); + return (i); +} diff --git a/bsq/srcs/helper.c b/bsq/srcs/helper.c deleted file mode 100644 index d1fe8bc..0000000 --- a/bsq/srcs/helper.c +++ /dev/null @@ -1,62 +0,0 @@ -/* ************************************************************************** */ -/* */ -/* ::: :::::::: */ -/* helper.c :+: :+: :+: */ -/* +:+ +:+ +:+ */ -/* By: cacharle +#+ +:+ +#+ */ -/* +#+#+#+#+#+ +#+ */ -/* Created: 2019/07/19 15:19:53 by cacharle #+# #+# */ -/* Updated: 2019/07/19 15:19:56 by cacharle ### ########.fr */ -/* */ -/* ************************************************************************** */ - -#include -#include -#include -#include "include.h" - -int read_file(int fildes, char **file) -{ - char buf[BUF_SIZE]; - int file_size; - int read_size; - - file_size = 0; - while ((read_size = read(fildes, buf, BUF_SIZE))) - { - if (read_size < 0) - return (-1); - *file = ft_memcat(*file, buf, file_size, read_size); - file_size += read_size; - } - return (file_size); -} - -char *ft_memcat(char *file, char buf[BUF_SIZE], int file_size, - int read_size) -{ - int i; - char *file_clone; - - if ((file_clone = malloc(sizeof(char) * (file_size + 1))) == NULL) - return (NULL); - i = -1; - while (++i < file_size) - file_clone[i] = file[i]; - free(file); - if ((file = malloc(sizeof(char) * (file_size + read_size + 1))) == NULL) - return (NULL); - i = 0; - while (i < file_size) - { - file[i] = file_clone[i]; - i++; - } - free(file_clone); - while (i < file_size + read_size) - { - file[i] = buf[i - file_size]; - i++; - } - return (file); -} diff --git a/bsq/srcs/main.c b/bsq/srcs/main.c deleted file mode 100644 index 637ac13..0000000 --- a/bsq/srcs/main.c +++ /dev/null @@ -1,20 +0,0 @@ -/* ************************************************************************** */ -/* */ -/* ::: :::::::: */ -/* main.c :+: :+: :+: */ -/* +:+ +:+ +:+ */ -/* By: cacharle +#+ +:+ +#+ */ -/* +#+#+#+#+#+ +#+ */ -/* Created: 2019/07/19 11:01:32 by cacharle #+# #+# */ -/* Updated: 2019/07/19 13:35:23 by cacharle ### ########.fr */ -/* */ -/* ************************************************************************** */ - -#include "include.h" - -int main(int argc, char **argv) -{ - - - return (0); -} diff --git a/bsq/srcs/parse.c b/bsq/srcs/parse.c deleted file mode 100644 index 8c4af3a..0000000 --- a/bsq/srcs/parse.c +++ /dev/null @@ -1,42 +0,0 @@ -/* ************************************************************************** */ -/* */ -/* ::: :::::::: */ -/* parse.c :+: :+: :+: */ -/* +:+ +:+ +:+ */ -/* By: cacharle +#+ +:+ +#+ */ -/* +#+#+#+#+#+ +#+ */ -/* Created: 2019/07/19 15:23:43 by cacharle #+# #+# */ -/* Updated: 2019/07/19 15:55:31 by cacharle ### ########.fr */ -/* */ -/* ************************************************************************** */ - -#include "include.h" - -t_bool check_input(char *input) -{ - char *line; - int i; - - i = 0; - while (input[i] != '\n') - i++; - if (i < 4) - return (FALSE); - parsed.fill = input[i--]; - parsed.obstacle = input[i--]; - parsed.empty = input[i--]; - // parsed.size = // atoi smth - while (*input != '\n') - input++; - i = 0; - while (input[i]) - { - while (input[i] != '\n') - { - - } - if (i != parsed.size - - - } -} diff --git a/bsq/terrain.c b/bsq/terrain.c new file mode 100644 index 0000000..b2ef10a --- /dev/null +++ b/bsq/terrain.c @@ -0,0 +1,78 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* terrain.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: cacharle +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2019/07/23 08:56:45 by cacharle #+# #+# */ +/* Updated: 2019/07/24 12:06:11 by samzur ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include +#include +#include "include.h" + +/* +** Free the terrain +*/ + +void destroy_terrain(t_terrain *terrain) +{ + int y; + + if (terrain == NULL) + return ; + if (terrain->matrix == NULL) + return ; + y = 0; + while (y < terrain->rows) + { + if (terrain->matrix[y] == NULL) + break ; + free(terrain->matrix[y++]); + } + free(terrain->matrix); +} + +void print_terrain(t_parsed_terrain *pterrain) +{ + int terrain_len; + char *terrain_str; + + terrain_str = (char*)malloc(sizeof(char) * pterrain->terrain->rows + * (pterrain->terrain->columns + 1)); + terrain_len = terrain_to_string(pterrain, terrain_str); + write(STDOUT_FILENO, terrain_str, terrain_len); + free(terrain_str); +} + +int terrain_to_string(t_parsed_terrain *pterrain, char *str) +{ + int i; + int j; + int str_index; + + str_index = 0; + i = 0; + while (i < pterrain->terrain->rows) + { + j = 0; + while (j < pterrain->terrain->columns) + { + if (pterrain->terrain->matrix[i][j] >= EMPTY) + str[str_index] = pterrain->empty; + else if (pterrain->terrain->matrix[i][j] == OBSTACLE) + str[str_index] = pterrain->obstacle; + else if (pterrain->terrain->matrix[i][j] == FILLED) + str[str_index] = pterrain->filled; + j++; + str_index++; + } + i++; + str[str_index] = '\n'; + str_index++; + } + return (str_index); +} diff --git a/bsq/tests/generate.pl b/bsq/tests/generate.pl deleted file mode 100755 index 27bd35f..0000000 --- a/bsq/tests/generate.pl +++ /dev/null @@ -1,21 +0,0 @@ -#!/usr/bin/perl - -use warnings; -use strict; - -die "program x y density" unless (scalar(@ARGV) == 3); - -my ($x, $y, $density) = @ARGV; - -print "$y.ox\n"; -for (my $i = 0; $i < $y; $i++) { - for (my $j = 0; $j < $x; $j++) { - if (int(rand($y) * 2) < $density) { - print "o"; - } - else { - print "."; - } - } - print "\n"; -} diff --git a/bsq/utils.c b/bsq/utils.c new file mode 100644 index 0000000..2fa9d29 --- /dev/null +++ b/bsq/utils.c @@ -0,0 +1,87 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* utils.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: cacharle +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2019/07/23 19:19:56 by cacharle #+# #+# */ +/* Updated: 2019/07/24 14:50:31 by cacharle ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include +#include +#include "include.h" + +/* +** Solve terrain (from Stdin), print and free it when it's done +*/ + +void parse_stdin_print(void) +{ + t_parsed_terrain *pterrain; + + pterrain = malloc(sizeof(t_parsed_terrain)); + if (parse_fildes(STDIN_FILENO, pterrain) < 0) + write(STDOUT_FILENO, "map error\n", 10); + else + { + solve_and_complete(pterrain->terrain); + print_terrain(pterrain); + destroy_terrain(pterrain->terrain); + } + free(pterrain); +} + +/* +** Solve terrain (from a file), print and free it when it's done +*/ + +void parse_file_print(char *filename) +{ + t_parsed_terrain *pterrain; + + pterrain = malloc(sizeof(t_parsed_terrain)); + if (parse_file(filename, pterrain) < 0) + write(STDOUT_FILENO, "map error\n", 10); + else + { + solve_and_complete(pterrain->terrain); + print_terrain(pterrain); + destroy_terrain(pterrain->terrain); + } + free(pterrain); +} + +/* +** count the number of line of a file +*/ + +int count_lines(char *file) +{ + int counter; + + counter = 0; + while (*file) + { + if (*file == '\n') + counter++; + file++; + } + return (counter); +} + +/* +** strlen until '\n' or '\0' +*/ + +int ft_line_len(char *str) +{ + int counter; + + counter = 0; + while (str[counter] && str[counter] != '\n') + counter++; + return (counter); +} diff --git a/c13/ex00/ft_btree.h b/c13/ex00/ft_btree.h index 3af177e..7d55f1a 100644 --- a/c13/ex00/ft_btree.h +++ b/c13/ex00/ft_btree.h @@ -6,7 +6,7 @@ /* By: cacharle +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2019/07/17 19:29:12 by cacharle #+# #+# */ -/* Updated: 2019/07/21 18:19:33 by cacharle ### ########.fr */ +/* Updated: 2019/07/24 12:09:35 by cacharle ### ########.fr */ /* */ /* ************************************************************************** */ @@ -15,9 +15,11 @@ typedef struct s_btree { - struct s_btree *left; - struct s_btree *right; - void *item; + struct s_btree *left; + struct s_btree *right; + void *item; } t_btree; +t_btree *btree_create_node(void *item); + #endif diff --git a/c13/ex01/btree_apply_prefix.c b/c13/ex01/btree_apply_prefix.c index 530d698..a1edd28 100644 --- a/c13/ex01/btree_apply_prefix.c +++ b/c13/ex01/btree_apply_prefix.c @@ -6,17 +6,18 @@ /* By: cacharle +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2019/07/21 18:28:07 by cacharle #+# #+# */ -/* Updated: 2019/07/21 18:37:15 by cacharle ### ########.fr */ +/* Updated: 2019/07/24 13:49:17 by cacharle ### ########.fr */ /* */ /* ************************************************************************** */ +#include #include "ft_btree.h" -void btree_apply_prefix(t_btree *root, void (*applyf)(void *)) +void btree_apply_prefix(t_btree *root, void (*applyf)(void *)) { if (root == NULL) return ; (*applyf)(root->item); - btree_apply_prefix(root->left); - btree_apply_prefix(root->right); + btree_apply_prefix(root->left, applyf); + btree_apply_prefix(root->right, applyf); } diff --git a/c13/ex01/ft_btree.h b/c13/ex01/ft_btree.h index 3af177e..a1b6269 100644 --- a/c13/ex01/ft_btree.h +++ b/c13/ex01/ft_btree.h @@ -6,7 +6,7 @@ /* By: cacharle +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2019/07/17 19:29:12 by cacharle #+# #+# */ -/* Updated: 2019/07/21 18:19:33 by cacharle ### ########.fr */ +/* Updated: 2019/07/24 12:10:09 by cacharle ### ########.fr */ /* */ /* ************************************************************************** */ @@ -15,9 +15,9 @@ typedef struct s_btree { - struct s_btree *left; - struct s_btree *right; - void *item; + struct s_btree *left; + struct s_btree *right; + void *item; } t_btree; #endif diff --git a/c13/ex02/btree_apply_infix.c b/c13/ex02/btree_apply_infix.c index 3ff3278..c05cbd6 100644 --- a/c13/ex02/btree_apply_infix.c +++ b/c13/ex02/btree_apply_infix.c @@ -6,17 +6,18 @@ /* By: cacharle +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2019/07/21 18:28:07 by cacharle #+# #+# */ -/* Updated: 2019/07/23 21:09:53 by cacharle ### ########.fr */ +/* Updated: 2019/07/24 13:49:17 by cacharle ### ########.fr */ /* */ /* ************************************************************************** */ +#include #include "ft_btree.h" -void btree_apply_infix(t_btree *root, void (*applyf)(void *)) +void btree_apply_infix(t_btree *root, void (*applyf)(void *)) { if (root == NULL) return ; - btree_apply_infix(root->left); + btree_apply_infix(root->left, applyf); (*applyf)(root->item); - btree_apply_infix(root->right); + btree_apply_infix(root->right, applyf); } diff --git a/c13/ex02/ft_btree.h b/c13/ex02/ft_btree.h index 3af177e..2a1506a 100644 --- a/c13/ex02/ft_btree.h +++ b/c13/ex02/ft_btree.h @@ -6,7 +6,7 @@ /* By: cacharle +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2019/07/17 19:29:12 by cacharle #+# #+# */ -/* Updated: 2019/07/21 18:19:33 by cacharle ### ########.fr */ +/* Updated: 2019/07/24 12:10:39 by cacharle ### ########.fr */ /* */ /* ************************************************************************** */ @@ -15,9 +15,9 @@ typedef struct s_btree { - struct s_btree *left; - struct s_btree *right; - void *item; + struct s_btree *left; + struct s_btree *right; + void *item; } t_btree; #endif diff --git a/c13/ex03/btree_apply_suffix.c b/c13/ex03/btree_apply_suffix.c index 6d5c3b2..5c00f37 100644 --- a/c13/ex03/btree_apply_suffix.c +++ b/c13/ex03/btree_apply_suffix.c @@ -6,17 +6,18 @@ /* By: cacharle +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2019/07/21 18:37:33 by cacharle #+# #+# */ -/* Updated: 2019/07/21 18:38:10 by cacharle ### ########.fr */ +/* Updated: 2019/07/24 13:49:17 by cacharle ### ########.fr */ /* */ /* ************************************************************************** */ +#include #include "ft_btree.h" -void btree_apply_suffix(t_btree *root, void (*applyf)(void *)) +void btree_apply_suffix(t_btree *root, void (*applyf)(void *)) { if (root == NULL) return ; - btree_apply_suffix(root->left); - btree_apply_suffix(root->right); + btree_apply_suffix(root->left, applyf); + btree_apply_suffix(root->right, applyf); (*applyf)(root->item); } diff --git a/c13/ex03/ft_btree.h b/c13/ex03/ft_btree.h index 3af177e..f847890 100644 --- a/c13/ex03/ft_btree.h +++ b/c13/ex03/ft_btree.h @@ -6,7 +6,7 @@ /* By: cacharle +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2019/07/17 19:29:12 by cacharle #+# #+# */ -/* Updated: 2019/07/21 18:19:33 by cacharle ### ########.fr */ +/* Updated: 2019/07/24 12:10:57 by cacharle ### ########.fr */ /* */ /* ************************************************************************** */ @@ -15,9 +15,9 @@ typedef struct s_btree { - struct s_btree *left; - struct s_btree *right; - void *item; + struct s_btree *left; + struct s_btree *right; + void *item; } t_btree; #endif diff --git a/c13/ex04/btree_insert_data.c b/c13/ex04/btree_insert_data.c index 0999cab..e04514f 100644 --- a/c13/ex04/btree_insert_data.c +++ b/c13/ex04/btree_insert_data.c @@ -6,20 +6,20 @@ /* By: cacharle +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2019/07/21 18:43:18 by cacharle #+# #+# */ -/* Updated: 2019/07/23 20:49:48 by cacharle ### ########.fr */ +/* Updated: 2019/07/24 14:18:29 by cacharle ### ########.fr */ /* */ /* ************************************************************************** */ #include #include "ft_btree.h" -// this is half shit -void btree_insert_data(t_btree **root, void *item, int (*cmpf)(void *, void *)) +void btree_insert_data(t_btree **root, void *item, + int (*cmpf)(void *, void *)) { if (*root == NULL) - *root = btree_create_elem(item); - if ((*cmpf)((*root)->item, item) < 0) - btree_insert_root(&(*root)->left, item, cmpf); - else if ((*cmpf)((*root)->item, item) > 0) - btree_insert_root(&(*root)->right, item, cmpf); + *root = btree_create_node(item); + else if ((*cmpf)(item, (*root)->item) < 0) + btree_insert_data(&(*root)->left, item, cmpf); + else + btree_insert_data(&(*root)->right, item, cmpf); } diff --git a/c13/ex04/ft_btree.h b/c13/ex04/ft_btree.h index 3af177e..0572243 100644 --- a/c13/ex04/ft_btree.h +++ b/c13/ex04/ft_btree.h @@ -6,7 +6,7 @@ /* By: cacharle +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2019/07/17 19:29:12 by cacharle #+# #+# */ -/* Updated: 2019/07/21 18:19:33 by cacharle ### ########.fr */ +/* Updated: 2019/07/24 12:11:28 by cacharle ### ########.fr */ /* */ /* ************************************************************************** */ @@ -15,9 +15,11 @@ typedef struct s_btree { - struct s_btree *left; - struct s_btree *right; - void *item; + struct s_btree *left; + struct s_btree *right; + void *item; } t_btree; +t_btree *btree_create_node(void *item); + #endif diff --git a/c13/ex05/btree_search_item.c b/c13/ex05/btree_search_item.c index b5d7114..a714e0c 100644 --- a/c13/ex05/btree_search_item.c +++ b/c13/ex05/btree_search_item.c @@ -6,11 +6,27 @@ /* By: cacharle +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2019/07/23 20:49:54 by cacharle #+# #+# */ -/* Updated: 2019/07/23 21:09:10 by cacharle ### ########.fr */ +/* Updated: 2019/07/24 14:15:46 by cacharle ### ########.fr */ /* */ /* ************************************************************************** */ -void *btree_search_item(t_btree *root, void *data_ref, int (*cmpf)(void *, void *)) +#include +#include "ft_btree.h" + +void *btree_search_item(t_btree *root, void *data_ref, + int (*cmpf)(void *, void *)) { + void *tmp; + if (root == NULL) + return (NULL); + tmp = btree_search_item(root->left, data_ref, cmpf); + if (tmp != NULL) + return (tmp); + if ((*cmpf)(root->item, data_ref) == 0) + return (root->item); + tmp = btree_search_item(root->right, data_ref, cmpf); + if (tmp != NULL) + return (tmp); + return (NULL); } diff --git a/c13/ex05/ft_btree.h b/c13/ex05/ft_btree.h index 3af177e..61ef7b6 100644 --- a/c13/ex05/ft_btree.h +++ b/c13/ex05/ft_btree.h @@ -6,7 +6,7 @@ /* By: cacharle +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2019/07/17 19:29:12 by cacharle #+# #+# */ -/* Updated: 2019/07/21 18:19:33 by cacharle ### ########.fr */ +/* Updated: 2019/07/24 12:15:59 by cacharle ### ########.fr */ /* */ /* ************************************************************************** */ @@ -15,9 +15,9 @@ typedef struct s_btree { - struct s_btree *left; - struct s_btree *right; - void *item; + struct s_btree *left; + struct s_btree *right; + void *item; } t_btree; #endif diff --git a/c13/ex06/btree_level_count.c b/c13/ex06/btree_level_count.c index e69de29..5f83662 100644 --- a/c13/ex06/btree_level_count.c +++ b/c13/ex06/btree_level_count.c @@ -0,0 +1,33 @@ +/* ************************************************************************** */ +/* */ +/* ::: :::::::: */ +/* btree_level_count.c :+: :+: :+: */ +/* +:+ +:+ +:+ */ +/* By: cacharle +#+ +:+ +#+ */ +/* +#+#+#+#+#+ +#+ */ +/* Created: 2019/07/24 11:51:34 by cacharle #+# #+# */ +/* Updated: 2019/07/24 12:28:45 by cacharle ### ########.fr */ +/* */ +/* ************************************************************************** */ + +#include +#include "ft_btree.h" + +int btree_level_count(t_btree *root) +{ + int left_level; + int right_level; + + if (root == NULL) + return (0); + left_level = 0; + right_level = 0; + if (root->left != NULL) + left_level = btree_level_count(root->left); + if (root->right != NULL) + right_level = btree_level_count(root->right); + if (left_level >= right_level) + return (1 + left_level); + else + return (1 + right_level); +} diff --git a/c13/ex06/ft_btree.h b/c13/ex06/ft_btree.h index 3af177e..398e060 100644 --- a/c13/ex06/ft_btree.h +++ b/c13/ex06/ft_btree.h @@ -6,7 +6,7 @@ /* By: cacharle +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2019/07/17 19:29:12 by cacharle #+# #+# */ -/* Updated: 2019/07/21 18:19:33 by cacharle ### ########.fr */ +/* Updated: 2019/07/24 12:16:54 by cacharle ### ########.fr */ /* */ /* ************************************************************************** */ @@ -15,9 +15,9 @@ typedef struct s_btree { - struct s_btree *left; - struct s_btree *right; - void *item; + struct s_btree *left; + struct s_btree *right; + void *item; } t_btree; #endif diff --git a/c13/ex07/btree_apply_by_level.c b/c13/ex07/btree_apply_by_level.c deleted file mode 100644 index e69de29..0000000 diff --git a/c13/ex07/ft_btree.h b/c13/ex07/ft_btree.h index 3af177e..88a3bbd 100644 --- a/c13/ex07/ft_btree.h +++ b/c13/ex07/ft_btree.h @@ -6,7 +6,7 @@ /* By: cacharle +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2019/07/17 19:29:12 by cacharle #+# #+# */ -/* Updated: 2019/07/21 18:19:33 by cacharle ### ########.fr */ +/* Updated: 2019/07/24 12:19:36 by cacharle ### ########.fr */ /* */ /* ************************************************************************** */ @@ -15,9 +15,9 @@ typedef struct s_btree { - struct s_btree *left; - struct s_btree *right; - void *item; + struct s_btree *left; + struct s_btree *right; + void *item; } t_btree; #endif diff --git a/c13/ft_btree.h b/c13/ft_btree.h deleted file mode 100644 index 3af177e..0000000 --- a/c13/ft_btree.h +++ /dev/null @@ -1,23 +0,0 @@ -/* ************************************************************************** */ -/* */ -/* ::: :::::::: */ -/* ft_btree.h :+: :+: :+: */ -/* +:+ +:+ +:+ */ -/* By: cacharle +#+ +:+ +#+ */ -/* +#+#+#+#+#+ +#+ */ -/* Created: 2019/07/17 19:29:12 by cacharle #+# #+# */ -/* Updated: 2019/07/21 18:19:33 by cacharle ### ########.fr */ -/* */ -/* ************************************************************************** */ - -#ifndef FT_BTREE_H -# define FT_BTREE_H - -typedef struct s_btree -{ - struct s_btree *left; - struct s_btree *right; - void *item; -} t_btree; - -#endif diff --git a/c13/main.c b/c13/main.c new file mode 100644 index 0000000..16e7ebb --- /dev/null +++ b/c13/main.c @@ -0,0 +1,90 @@ +#include +#include "ex00/ft_btree.h" +#include "ex00/btree_create_node.c" +#include "ex01/btree_apply_prefix.c" +#include "ex02/btree_apply_infix.c" +#include "ex03/btree_apply_suffix.c" +#include "ex04/btree_insert_data.c" +#include "ex05/btree_search_item.c" +#include "ex06/btree_level_count.c" + +void f_print(void *d); +int cmp(void *x, void *y); +int equal(void *x, void *y); + +int main() +{ + int a = 1; + int b = 2; + int c = 3; + int d = 4; + int e = 5; + int big = 1000; + int bigger = 10000; + t_btree *t = btree_create_node(&a); + t_btree *l = btree_create_node(&b); + t_btree *r = btree_create_node(&c); + t->left = l; + t->right = r; + + printf("%d %p %p\n", *(int*)t->item, t->left, t->right); + printf("%d %p %p", *(int*)l->item, l->left, l->right); + + printf("\n-----------------\n"); + btree_apply_prefix(t, &f_print); + + printf("\n-----------------\n"); + btree_apply_infix(t, &f_print); + + printf("\n-----------------\n"); + btree_apply_suffix(t, &f_print); + + printf("\n-----------------\n"); + t_btree *sorted = NULL; + btree_insert_data(&sorted, &c, &cmp); + btree_insert_data(&sorted, &a, &cmp); + btree_insert_data(&sorted, &b, &cmp); + btree_insert_data(&sorted, &e, &cmp); + btree_insert_data(&sorted, &d, &cmp); + btree_insert_data(&sorted, &big, &cmp); + btree_insert_data(&sorted, &big, &cmp); + /*btree_insert_data(&sorted, &bigger, &cmp);*/ + btree_apply_prefix(sorted, &f_print); + + printf("\n-----------------\n"); + t_btree *empty = NULL; + t_btree *one = btree_create_node(&a); + printf("%p\n", btree_search_item(empty, &a, &equal)); + printf("%p\n", (int*)btree_search_item(empty, &a, &equal)); + printf("%d\n", *(int*)btree_search_item(sorted, &a, &equal)); + printf("%d\n", *(int*)btree_search_item(sorted, &big, &equal)); + /*printf("%d\n", *(int*)btree_search_item(sorted, &bigger, &equal));*/ + + printf("\n-----------------\n"); + printf("%d\n", btree_level_count(sorted)); + printf("%d\n", btree_level_count(t)); + printf("%d\n", btree_level_count(empty)); + printf("%d\n", btree_level_count(one)); +} + +void f_print(void *d) +{ + printf("%d ", *(int*)d); + fflush(stdout); +} + +int cmp(void *x, void *y) +{ + if (*(int*)x < *(int*)y) + return -1; + if (*(int*)x > *(int*)y) + return 1; + return 0; +} + +int equal(void *x, void *y) +{ + if (*(int*)x == *(int*)y) + return 0; + return 1; +} -- cgit