Fillit - Tetris Solver

The purpose of this program is to make the smallest possible square using tetriminos you give it. This was a group project of myself and one other teammate. I learned a lot about how recursive backtracking works through the making of the program.

Compiling

Run the makefile to create the executable file called fillit. If compiling on GNU/Linux make sure to have Clang installed.

Git Repo


Example

./fillit testfiles/[file]

Example of piece files:

.... .... ..## .##. .... .##. ..#. ..#. .... .... ..## .##. .... .... ..## .##. .... .... ..## .##. .... .... ..## .##. .... .... ..## .##. .... .... ..## .##.

Example of Output:

.AABB.. AACCB.. .CC.BDD .EE.DD. EEFFGG. .FFGGHH ....HH.

main.c

#include "fillit.h" int count_pieces(int *arr) { int i; i = 0; while ((i <= 26) && arr[i]) i++; return (i); } char **set_val_pieces(char **array, int piececount) { int i; int n; int p; i = 0; p = piececount; while (i < p) { n = 0; while (array[i][n] != 0) { if (array[i][n] == '#') array[i][n] = (i + 65); n++; } i++; } return (array); } int fillit(char **argv) { t_fillit storage; storage.array = ft_set_pieces(); if (!(storage.nums = readit(argv[1], storage.array))) { return (0); } storage.piececount = count_pieces(storage.nums); storage.tiniestsize = smallestboard(storage.piececount * 4); storage.board = makeboard(storage.tiniestsize); storage.pieces = ft_true_pieces(storage.nums, storage.piececount); storage.pieces = set_val_pieces(storage.pieces, storage.piececount); solve(storage.pieces, &storage.board, storage.piececount, storage.tiniestsize); free(storage.pieces); free(storage.board); return (1); } int main(int argc, char **argv) { if (argc == 1) { ft_putstr("usage: fillit [target_file]\n"); return (0); } else if (argc == 2) { if (!(fillit(argv))) ft_putstr("error\n"); } else ft_putstr("error\n"); return (0); }

read.c

nclude "fillit.h" int *do_reads(t_piece datastuff, int *p, char **pieces) { int i; i = ft_validate(datastuff.buf, pieces); if (i == -1) return (NULL); else if (i == 0) p[datastuff.count] = 19; else p[datastuff.count] = i; return (p); } int count_pound(char *str) { int i; int j; i = 0; j = 0; while (str[i] != '\0') { if (str[i] == '#') j++; i++; } return (j); } int count_n(char *str) { int i; int j; i = 0; j = 0; while (str[i] != '\0') { if (str[i] == '\n') j++; i++; } return (j); } int bufcheck(t_piece datastuff) { if ((!(datastuff.buf[0] == '#' || datastuff.buf[0] == '.')) || (!(datastuff.buf[19] == '\n')) || (count_pound(datastuff.buf) != 4)) return (0); return (1); } int *readit(char *file, char **pieces) { t_piece datastuff; int *piece; if (!(datastuff.fd = open(file, O_RDONLY))) return (0); if (!(piece = (int *)ft_memalloc(sizeof(int) * 27))) return (0); datastuff.count = 0; datastuff.n_count = 0; while ((datastuff.count <= 26) && (read(datastuff.fd, datastuff.buf, 21) != 0)) { if (!(bufcheck(datastuff))) return (0); if (!(piece = do_reads(datastuff, piece, pieces))) return (0); datastuff.n_count = datastuff.n_count + count_n(datastuff.buf); ft_bzero(datastuff.buf, 21); datastuff.count++; } if ((datastuff.count - 1) > 26 || datastuff.count == 0 || datastuff.n_count > ((datastuff.count * 5) - 1)) return (0); close(datastuff.fd); return (piece); }

solve.c

#include "fillit.h" char **do_mallocs_and_populate(char *truepiece[20], int *vals, int count) { char **array; int i; if (!(array = (char **)ft_memalloc(sizeof(char *) * (count + 1)))) return (NULL); i = 0; while (i < count) { if (!(array[i] = (char *)ft_memalloc(sizeof(char) * 49))) return (NULL); ft_strcpy(array[i], truepiece[vals[i]]); i++; } return (array); } char **ft_true_pieces(int *arr, int count) { static char *truepiece[20]; truepiece[0] = "##\n##"; truepiece[1] = "#\n#\n#\n#"; truepiece[2] = "####"; truepiece[3] = ".#\n##\n#"; truepiece[4] = "##.\n.##"; truepiece[5] = ".##\n##"; truepiece[6] = "#.\n##\n.#"; truepiece[7] = "#..\n###"; truepiece[8] = ".#\n.#\n##"; truepiece[9] = "###\n..#"; truepiece[10] = "##\n#.\n#"; truepiece[11] = "..#\n###"; truepiece[12] = "#.\n#.\n##"; truepiece[13] = "###\n#"; truepiece[14] = "##\n.#\n.#"; truepiece[15] = ".#.\n###\n"; truepiece[16] = "#.\n##\n#"; truepiece[17] = "###\n.#"; truepiece[18] = ".#\n##\n.#"; truepiece[19] = "##\n##"; return (do_mallocs_and_populate(truepiece, arr, count)); } int placepieces(char **pieces, char *board, int piece, int total) { int i; int x; if (piece == -1) i = 0; else i = piece; x = -1; while (board[++x]) { if (board[x] == '.' && addpiece(pieces[i], board, x)) { if ((i + 1) == total) return (1); else if ((i + 1) != total) { if (placepieces(pieces, board, ++i, total)) return (1); } removepiece(pieces[i--], board); } removepiece(pieces[i], board); } return (0); } void solve(char **pieces, char **board, int total, int tiniestsize) { while (placepieces(pieces, *board, -1, total) == 0) { free(*board); *board = makeboard(tiniestsize++); } ft_putstr(*board); }

validate.c

#include "fillit.h" char **ft_set_pieces(void) { static char *valids[19]; valids[0] = "##..##"; valids[1] = "#...#...#...#"; valids[2] = "####"; valids[3] = "#..##..#"; valids[4] = "##...##"; valids[5] = "##.##"; valids[6] = "#...##...#"; valids[7] = "#...###"; valids[8] = "#...#..##"; valids[9] = "###...#"; valids[10] = "##..#...#"; valids[11] = "#.###"; valids[12] = "#...#...##"; valids[13] = "###.#"; valids[14] = "##...#...#"; valids[15] = "#..###"; valids[16] = "#...##..#"; valids[17] = "###..#"; valids[18] = "#..##...#"; return (valids); } int ft_validatestr(char *str, char **valid) { int n; n = 0; while (n <= 18) { if (!(ft_strcmp(str, valid[n]))) return (n + 1); n++; } return (-1); } int ft_validatehash(char *str) { int i; int hashcount; int dotcount; i = 0; hashcount = 0; dotcount = 0; while (str[i] != '\0') { if (str[i] == '#') hashcount++; if (str[i] == '.') dotcount++; i++; } if (hashcount == 4 && dotcount == 12) return (1); else return (0); } char *ft_removeline(char *str) { int i; int z; char *str2; i = 0; z = 0; str2 = ft_strnew(ft_strlen(str)); while (str[i] != '\0') { if (str[i] != '\n') { str2[z] = str[i]; z++; } i++; } free(str); return (str2); } int ft_validate(char *str, char **valid) { int i; i = 0; if (!(ft_validatehash(str))) return (-1); str = ft_strtrimalt(str); str = ft_removeline(str); i = ft_validatestr(str, valid); free(str); if (i >= 1) return (i - 1); return (-1); }

maptools.c

#include "fillit.h" int len_n(char *s) { int i; i = 0; while (s[i] != '\n') i++; return (i); } char *makeboard(int size) { char *board; int pos; int realsize; int stor; pos = 0; realsize = ((size + 1) * size); stor = 0; board = ft_strnew(realsize); ft_memset(board, '.', realsize); while (pos < size) { stor = stor + (realsize / size); board[stor - 1] = '\n'; pos++; } return (board); } int smallestboard(int i) { int size; size = 0; while (i > size * size) { size++; if (size > 46340) return (0); } return (size); }

movepiece.c

#include "fillit.h" char get_letter(char *piece) { while (*piece) { if (ft_isupper(*piece)) return (*piece); piece++; } return (0); } int addpiece_ext(char *piece, char *board, int i, t_data dims) { while (piece[dims.p] && board[i]) { while (i < dims.max_size && piece[dims.p] && piece[dims.p] != '\n') { if (board[i] == '.') board[i++] = piece[dims.p++]; else if (piece[dims.p] == dims.letter) return (0); else { dims.p++; i++; } dims.mod++; } if (piece[dims.p] == '\n') dims.p++; if (!piece[dims.p]) return (1); i += dims.row_len - dims.mod; if (i >= dims.max_size) return (0); dims.mod = 0; } return (0); } int addpiece(char *piece, char *board, int i) { t_data dims; dims.max_size = ft_strlen(board); dims.row_len = len_n(board) + 1; dims.letter = get_letter(piece); dims.p = 0; dims.mod = 0; while (piece[dims.p] && piece[dims.p] == '.') { dims.p++; dims.mod++; } if (addpiece_ext(piece, board, i, dims) == 1) return (1); return (0); } char *removepiece(char *piece, char *board) { int n; int i2; n = 0; i2 = 0; while (board[n] != '\0') { while (piece[i2] == '.') i2++; if (board[n] == piece[i2]) board[n] = '.'; n++; } return (board); }

ft_strtrimalt.c

#include "fillit.h" static int whatspace(int c) { if ((c == '.' || c == '\n')) return (1); return (0); } static char strspace(char const *s) { int i; int z; i = 0; z = 0; while (s[i] != '\0') { if ((s[i] == '.' || s[i] == '\n')) z++; i++; } if (i == z) return (1); return (0); } char *ft_strtrimalt(char const *s) { size_t front; size_t back; size_t z; char *middle; if (!s || !ft_strlen(s)) return ((char*)s); if (strspace(s) == 1) return (ft_strnew(1)); front = 0; back = ft_strlen(s) - 1; z = 0; while (whatspace(s[front])) front++; while (whatspace(s[back]) != 0) back--; z = back - front + 1; if (!(middle = ft_strnew(z + 1))) return (NULL); return (ft_strncpy(middle, &s[front], z)); }

fillit.h

#ifndef FILLIT_H # define FILLIT_H # include "libft/libft.h" # include <fcntl.h> # include <sys/types.h> # include <sys/uio.h> typedef struct s_piece { int fd; int count; char *tmp; char buf[22]; int n_count; } t_piece; typedef struct s_data { int max_size; int row_len; char letter; int p; int mod; } t_data; typedef struct s_fillit { char **pieces; int *nums; char **array; char *board; int piececount; int tiniestsize; } t_fillit; int *readit(char *file, char **pieces); int ft_validate(char *str, char **valid); char *ft_strtrimalt(char const *s); char **ft_set_pieces(void); char *makeboard(int size); int addpiece(char *piece, char *board, int i); char *removepiece(char *piece, char *board); int smallestboard(int i); int len_n(char *s); char **ft_true_pieces(int *arr, int count); void solve(char **pieces, char **board, int total, int tiniestsize); #endif

Makefile

NAME = fillit CC = clang CFLAGS = -Wall -Werror -Wextra -I $(HEADERS) -o $(NAME) SRC = main.c read.c maptools.c movepiece.c solve.c validate.c ft_strtrimalt.c LIBFT_DIR = libft LIBS = libft/libft.a OBJ = $(SRC:.c=.o) HEADERS = . all: $(NAME) $(LIBS): make -C $(LIBFT_DIR) $(NAME): $(SRC) $(LIBS) $(CC) $(CFLAGS) $(SRC) $(LIBS) clean: $(MAKE) -C $(LIBFT_DIR) clean rm -f $(OBJ) fclean: clean $(MAKE) -C $(LIBFT_DIR) fclean rm -f $(NAME) re: fclean all