Partage

# Fill_The_Void: Issue

## Need help!

30 juillet 2021 à 20:00:01

In this project, I have given a set of Tetrominoes, and I have to find a way to assemble them in the smallest possible square. Here is a glance at the way I am solving this problem using C language.\

• Validating the input :
• Moving the Tetrimino to the top-most left-most positions to find the suitable solution
• Checking every line to check if there is only “.” and “#” character
• If the number of '#' is greater than 4 exit
• Check if there are missed lines between the Tetriminoes
• Checking every piece against a list of valid Tetriminoes
• Each array stores a total of 16 parameters (whether a “#” or “.” )
• Before storing the valid block into my linked list, first I shift the block to the top-left corner
• If the list doesn’t match any of the given (valid) lists, then return an error and quit simply
• If we validated the Tetrominoes, we can then put them into a linked list\
• Storing the arrays into a linked list: Then I will store the arrays into a linked a list\
1. – How can I fill it using a recursive backtracking algorithm?

• In our problem it’s kind of easy to express the problem recursively I’m going to give an example for this: Say we have two pieces:
. . . .
. # # .
. # # .
. . . .
----LINE----
. . . .
# # # .
. . . #
. . . .
When my program first started, the first piece is filled in the top left like this:
A A . .
A A . .
. . . .
. . . .
Still won’t fit? So I will keep shifting the piece through each possible space(left, right, up, down) on the square till it will fit.
• The keys to backtracking here are the choice I make, which is shifting the first Tetriminoe, once I express that I recurse in that decision, if the decision doesn’t work I come back and I undo it and make another choice, we explore, we undo, we made another choice.
• To figure out the efficient solution, we have to find the smallest square to start with, which is: starting size = number of Teteriminoes * 2
• I tried to code the whole code without any mistake. But it doesn't work, here my C code:
• #include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <stdbool.h>
#include "Fill_the_void.h"

//create a new node
t_tet* create(char data)
{
t_tet* new_node = (t_tet*)malloc(sizeof(t_tet));
if(new_node = NULL)
{
printf("Error creating a new node");
exit(0);
}
new_node->data = data;
new_node->next = NULL;
return new_node;
}

//Push an element into the stack
t_node* push(t_node* head, char data)
{
t_node* new_node = (t_node*)malloc(sizeof(new_node));
if(new_node == NULL)
{
exit(0);
}
new_node->data = data;
}
//Count the elements of the linked list
{
t_tet* temp = head;
int c = 0;
while(temp != NULL)
{
c++;
temp = temp->next;
}
return c;
}
//Add a new node at the end of the linked list
t_tet* append(t_tet* head, char data)
{
t_tet* temp = head;
while(temp->next != NULL)
temp = temp->next;
t_tet* new_node = create(data);
temp->next = new_node;
}

//Create a linked of tetriminos
t_tet* create_list(char block)
{
t_tet* head = NULL;
for(int i = 0; i < 16; i++)
{
}
}
//Convert linked list to array
{
int len = count(head);
char* arr = malloc(len * sizeof(char));
int index = 0;
t_tet* curr = head;
while (curr != NULL) {
arr[index++] = curr->data;
curr = curr->next;
}
return arr;
}
//Moving the Tetrimino the to the top-most left position
void moving_Tetrimino(char array[])
{
int k = 0;
for(int i = 0; i < sizeof(*array); i++)
{
if(array[i] > 0)
{
k = i;
break;
}
}
for(int i = 0; i < sizeof(*array); i++)
{
array[i] = array[i-k-1];
}
}
int counting_tetriminos(t_tet *tet)
{
int k = 0;
t_tet *temp;
temp = tet;
while(temp != NULL)
{
k++;
temp = temp->next;
}
k++;
return k;
}
int counting_blocks(char *character)
{
int k = 0;
if(!character)
return 0;
while(*character)
{
if (*character == '#')
k++;
character++;
}
return k;
}
int check_char(char *character)
{
if(!character)
return 0;
while(*character)
{
if (*character != 0  && *character != '#')
return 0;
character++;
}
return 1;
}
//Compare two arrays
_Bool compare_arrays(char array[])
{
for(int i = 1; i < sizeof(*array); i++)
{

if(array[i] =! I_1[i] || array[i] != I_2[i] || array[i] != O[i] || array[i] != T_2[i] || array[i] != T_3[i] || array[i] != T_4[i] || array[i] != L_1[i] || array[i] != L_2[i] || array[i] != L_3[i] || array[i] != L_4[i] || array[i] != Z_1[i] || array[i] != Z_2[i])
return false;
return true;
}
}
int check_tetrimino(char array[])
{
if(compare_arrays(array) == 1)
return 1;
return 0;
}
//Find the assignment location
int assign_loc(char array[], int s, int j)
{
s = array_size;
int i = j;
while(i < array_size)
{
if(array[i] == 0)
return j;
i++;
}
}
//A function to assign a block to an empty space
t_node* assign_tet(t_node* stack, char array_1[], char array_2[], int i)
{
int j = 0;
while(j != i)
{
stack = push(stack, array_1[j]);
j++;
}
stack = push(stack, '#');
return stack;
}
//Recursive function to check if the assignment does work or not, if so return the solution
t_node* recur_assign(char array_1[], char array_2[], int k)
{
k = assign_loc(array_1, array_size, 0);
t_node* stack = NULL;
stack = assign_tet(stack, array_1, array_2, k);
return recur_assign(array_1, array_2, assign_loc(array_1, array_size, k));
}
//Check if the assignment is valid
_Bool check_assign(char array_1[], char array_2[])
{
int j = 0;
char* array = malloc(16 * sizeof(char));
while(j < array_size)
{
if(array_1[j] == '#')
array[j] == 0;
if(array_1[j] == 0)
{
if(counting_blocks(array) <= 4)
array[j] == '#';
else
array[j] == 0;
}
j++;
}
if(compare_arrays(array) && array == array_2)
return true;
else
return false;
}
//Create a function to shift a Tetrimino
void shift_left(char array[])
{
if(array[0] == array[4] == array[8] == array[12] == '#')
return;
for(int i = 0; i < 16; i++)
array[i-1] = array[i];
}
void shift_right(char array[])
{
if(array[3] == array[7] == array[11] == array[15] == '#')
return;
for(int i = 0; i < 16; i++)
array[i] = array[i+1];
}
void shift_up(char array[])
{
if(array[0] == array[1] == array[2] == array[3] == '#')
return;
for(int i = 0; i < 16; i++)
array[i] = array[i-4];
}
void shift_down(char array[])
{
if(array[12] == array[13] == array[14] == array[15] == '#')
return;
for(int i = 0; i < 16; i++)
array[i] = array[i+4];
}
//Return the solution
t_node* solve(char array_1[], char array_2[], int k)
{
t_node* stack = NULL;
if(check_assign)
stack = recur_assign(array_1, array_2, k);
else
{
shift_left(array_2);
stack = solve(array_1, array_2, k);
shift_right(array_2);
stack = solve(array_1, array_2, k);
shift_up(array_2);
stack = solve(array_1, array_2, k);
shift_down(array_2);
stack = solve(array_1, array_2, k);
}
return stack;
}
//Print solution
void display(t_node* stack)
{
int k = 0;
if(stack == NULL)
{
return;
}
t_node* temp = stack;
printf("Stack : ");
while(temp != NULL)
{
printf("%d  ", temp->data);
k++;
if(k > 4)
{
printf("\n");
k = 0;
}
temp = temp->next;
}
}
//Free list
void liberer(t_tet* L)
{
while(L != NULL)
{
t_tet* temp = L;
L = L->next;
free(temp);
}
}
{
char *cptr;
if (cptr = fgets(in, 10, stdin))
{
while(*cptr == ' ' || *cptr == '\t')
cptr++;
return cptr;
}
else
return 0;
}
//Check if it is an empty line
int check_line(char* ptr)
{
while(*ptr==' ' || *ptr=='\t' || *ptr=='\n' || *ptr=='\r')
ptr++;
if(*ptr=='\0')
return 1;
return 0;
}
int main (int argc, char **argv)
{
char* arr_1 = malloc(16 * sizeof(char));
char* arr_2 = malloc(16 * sizeof(char));
t_tet* list = NULL;
if (argc != 2)
printf("usage: %s is provided,filename is not provided", argv[0]);
else
{
FILE *file = fopen(argv[1], "r");
if ( file == 0 )
{
printf("Could not open file\n");
}
else
{
char x;
while((x = fgetc(file)) != EOF)
{
printf("%c", x);
list = create_list(x);
if(x == ' ');
{
arr_1 = listTo_array(list);
liberer(list);
}
}
list = create_list(x);
arr_2 = listTo_array(list);
}
}
moving_Tetrimino(arr_1);
moving_Tetrimino(arr_2);
t_node* sol = solve(arr_1, arr_2, 0);
display(sol);
}
And this is the file.h:
• #ifndef Fill_the_void
#define Fill_the_void

int const array_size = 16;
struct s_tet
{
char data;
struct s_tet *next;
};
typedef struct s_tet t_tet;

struct s_node
{
char data;
struct s_node* next;
};
typedef struct s_node t_node;

t_node* push(t_node* head, char data);
t_tet* create(char data);
t_tet* append(t_tet* head, char data);
t_tet* create_list(char block);
void moving_Tetrimino(char *array);
int counting_tetriminos(t_tet* tet);
int counting_blocks(char *character);
int check_char(char *character);
_Bool compare_arrays(char *array);
int check_tetrimino(char *array);
int assign_loc(char *array, int s, int j);
t_node* assign_tet(t_node* stack, char *array_1, char *array_2, int i);
t_node* recur_assign(char *array_1, char *array_2, int k);
_Bool check_assign(char *array_1, char *array_2);
t_node* solve(char *array_1, char *array_2, int k);
void display(t_node* stack);
//int check_line(char *ptr);

# define I_1 (char[16]) {'#',0,0,0,'#',0,0,0,'#',0,0,0,'#',0,0,0}
# define I_2 (char[16]) {'#','#','#','#',0,0,0,0,0,0,0,0,0,0,0,0}
# define O (char[16]) {'#','#',0,0,'#','#',0,0,0,0,0,0,0,0,0,0}
# define T_1 (char[16]) {'#','#','#',0,0,'#',0,0,0,0,0,0,0,0,0,0}
# define T_2 (char[16]) {'#',0,0,0,'#','#',0,0,'#',0,0,0,0,0,0,0}
# define T_3 (char[16]) {0,'#',0,0,'#','#',0,0,0,'#',0,0,0,0,0,0}
# define T_4 (char[16]) {0,'#',0,0,'#','#','#',0,0,0,0,0,0,0,0,0}
# define L_1 (char[16]) {'#','#','#',0,'#',0,0,0,0,0,0,0,0,0,0,0}
# define L_2 (char[16]) {'#','#',0,0,0,'#',0,0,0,'#',0,0,0,0,0,0}
# define L_3 (char[16]) {'#',0,0,0,'#',0,0,0,'#','#',0,0,0,0,0,0}
# define L_4 (char[16]) {0,0,0,'#','#','#','#',0,0,0,0,0,0,0,0,0}
# define Z_1 (char[16]) {0,'#',0,0,'#','#',0,0,'#',0,0,0,0,0,0,0}
# define Z_2 (char[16]) {'#','#',0,0,0,'#','#',0,0,0,0,0,0,0,0,0}

#endif
and finally here is the Tetrminoes.txt that I choose to start with:
• ....
....
.##.
.##.

..##
...#
...#
....
I stack with problem for too long and I would really appreciate it a lot for any kind of help. Sorry if this was a bit long for you. Thaaaankss!!

TheCosmos

## Fill_The_Void: Issue

× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
• Editeur
• Markdown