-
Notifications
You must be signed in to change notification settings - Fork 0
/
algo.c
130 lines (115 loc) · 3.42 KB
/
algo.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
/* ************************************************************************** */
/* */
/* ::: :::::::: */
/* algo.c :+: :+: :+: */
/* +:+ +:+ +:+ */
/* By: nde-maes <[email protected]> +#+ +:+ +#+ */
/* +#+#+#+#+#+ +#+ */
/* Created: 2018/12/10 14:27:30 by nde-maes #+# #+# */
/* Updated: 2019/01/07 13:13:43 by nde-maes ### ########.fr */
/* */
/* ************************************************************************** */
#include "fillit.h"
/*
** Check whether or not tetriminos can fit in the resulting square.
*/
int tet_can_fit_on_res(char **res, char **current_tet)
{
int line;
int col;
line = -1;
while (res[++line])
{
col = -1;
while (res[line][++col])
if (current_tet[line][col] != '.' && res[line][col] != '.')
return (0);
}
return (1);
}
/*
** Place the non-dot symbols (i.e. the tetriminos letter in our case)
** on the resulting square.
*/
void place_tet_on_res(char **res, char **current_tet)
{
int line;
int col;
line = -1;
while (res[++line])
{
col = -1;
while (res[line][++col])
if (current_tet[line][col] != '.')
res[line][col] = current_tet[line][col];
}
}
static int handle_move_tet(char **current_tet)
{
int dir;
dir = tetriminos_can_move(current_tet);
if (dir == 1)
move_tet_right(current_tet);
else if (dir == 2)
move_tet_down_left(current_tet);
else
{
free_sqr(current_tet);
return (1);
}
return (0);
}
/*
** This function recursively adds tetriminos in the `res` square.
**
** `resolve_rec` copies the tetriminos to avoid spoiling the ones it receives,
** which are well positionned on the top left corner.
** As far as the result square is concerned, we delete the 4 letters of the
** current node, if we need to go to the previous call of the function.
*/
static void resolve_rec(char **res, int dim, t_tet *tet, t_tet **tet_head)
{
char **current_tet;
current_tet = copy_tet_with_dim(tet->piece, dim);
while (1)
{
if (tet_can_fit_on_res(res, current_tet))
{
place_tet_on_res(res, current_tet);
if (!(tet->next))
{
print_sqr(res);
free_sqr(res);
free_sqr(current_tet);
free_lst(tet_head);
exit(0);
}
resolve_rec(res, dim, tet->next, tet_head);
delete_tet_on_res(res, tet->letter);
}
if (handle_move_tet(current_tet))
return ;
}
}
/*
** Entry point of the algo.
** A empty resulting square is created here, it is then passed to the recursive
** `resolve_rec` function which will fill it. At first the resulting square has
** a dimension of 4 because that's the smallest size possible it can have. If
** `resolve_rec` exits, a new resulting square with a dimension of 5 is created
** and passed to `resolve_rec`. So on till `resolve_rec` prints the most
** optimized square with all the tetriminos in it.
*/
void resolve(t_tet **tet_head, int res_starting_dim)
{
char **res;
int dim;
dim = res_starting_dim - 1;
while (++dim)
{
if (dim > res_starting_dim)
free_sqr(res);
res = create_empty_sqr(dim);
resolve_rec(res, dim, *tet_head, tet_head);
}
}