C programming Help needed

Discuss how to write good code, break bad code, your current pet projects, or the best way to approach novel problems

Re: C programming Help needed

Post by tremor77 on Thu May 15, 2014 11:54 am
([msg=80722]see Re: C programming Help needed[/msg])

I think I might have an elegant solution. Lets say we have a matrix that looks like this:

0 1 2 0 0 0
0 0 0 2 2 1
0 1 1 0 0 1
1 0 1 0 1 0
0 0 3 3 0 0

now look at it like this

0 1 2 0 0 0
0 0 0 2 2 1
0 1 1 0 0 1
1 0 1 0 1 0
0 0 3 3 0 0

What we see is that in this matrix there are 5 distinct "emtpy" regions. If we can "map" those.. we have a way of quickly filling their values. So, create a function to map the empty regions. emptyRegion = [arrayOfCoords1, arrayOfCoords2...]

To do this without recursion we'll just to a 1 time through the matrix trip, and stash our results.. get each block in order and compare it to the previous block and build / compare to our empty region map as we walk through the matrix.

Function walks the matrix (1,1) -> (2,1) until it finds the first empty, then it creates the first emptyRegion. In this case coord(1,1) becomes emptyRegion[1]. Then we find the next empty coord.. we compare IT to all the coords in in existing empty regions.. if it matches a N,S,E,W rule we add it to THAT emptyRegion, otherwise we add it to a NEW emptyRegion. The secret is the realization that a coordinate can only ever be part of 1 empty region and that it will never match the N,S,E,W rule concept of some other empty region!

However there is 1 problem to this solution that calls for a small "solver". Lets build a tricky matrix

1 1 0 1 1 1
0 0 0 2 2 1
5 1 1 0 0 1
1 0 1 0 1 0
0 0 3 3 0 0

Coordinate 3,1 will be added to a new region, then we walk.. coordinate 1,2 will not match an existing region so he will be added to a new region also.. then walk, 2,2 will match the 2nd region, and uh-oh wtf!!!! 3,2 is going to match 2 regions!!! Simply.. we merge the regions at this point. If 1 coordinate matches 2 regions - then logically those 2 regions are connected and should be 1 region.. so we take region1 and region2 and make merge them. Then continue on.

Then when a user submits a fill request you get the empty region that contains that coordinate, and fill the whole region in a single swipe, then remove it from the array of empty regions, FTW! I'm probably going to dust off my decade old unused C skills and actually try to put this together just to see if I can still write C after all the damn Javascript I've been stuck in lately.

*Edit - Just realized C uses Cartesion coordinates so I have to reverse all my identifiers.. coords are (x,y) not (y,x) to the walk order is 1,1; 2,1; 3,1... edited in post. Now to remember how to build the equivalent of an array map in C

-- Thu May 15, 2014 12:57 pm --

I took the liberty of stubbing out a function that might accomplish mapping the regions.

Code: Select all
// Initialize an array for coordinates...
// best method? We don't know how many there will be...
int region;
// Function to walk the matrix and populate empty regions with empty coordinates
void walk_matrix(void){
    int x, y;
    for (y = 0; y < ROW; y++) {
        for (x = 0; x < COL; x++){
            if (a[x][y] == 0) {
           
                // Check regions
               
                // if a[x][y] matches coords in an existing region, add it to that region.
               
                // if a[x][y] matches coords in multiple regions, merge those regions into 1 region
               
                // if a[x][y] matches no regions, create a new region and add a[x][y] to it.
               
            }
        }
    }
}
User avatar
tremor77
Addict
Addict
 
Posts: 1098
Joined: Wed Mar 31, 2010 12:00 pm
Location: New York
Blog: View Blog (0)


Re: C programming Help needed

Post by hfakar on Thu May 15, 2014 1:48 pm
([msg=80723]see Re: C programming Help needed[/msg])

I wanted to hug you man... Im working on it thank you.
Secure? Come onnn...
hfakar
New User
New User
 
Posts: 7
Joined: Fri May 09, 2014 6:14 pm
Blog: View Blog (0)


Re: C programming Help needed

Post by tremor77 on Thu May 15, 2014 4:22 pm
([msg=80732]see Re: C programming Help needed[/msg])

hfakar wrote:I wanted to hug you man... Im working on it thank you.


If you want to thank me, let me know if you get it working and consider participating regularly on the HackThisSite forums! We're always looking for more intellectual conversations and talk about real programming from people who are learning and willing to learn, as opposed to the usual fair of "help me hack this" kind of questions. It's I who should thank you because I actually had to think about an answer for once.
User avatar
tremor77
Addict
Addict
 
Posts: 1098
Joined: Wed Mar 31, 2010 12:00 pm
Location: New York
Blog: View Blog (0)


Re: C programming Help needed

Post by hfakar on Thu May 15, 2014 7:26 pm
([msg=80735]see Re: C programming Help needed[/msg])

tremor77 wrote: It's I who should thank you because I actually had to think about an answer for once.
Well my friend thank you. Thats so kind of you. You have been huge help to me about thinking process.But i might need your further help. icouldnt get over it. I almost couldnt do anything, after you gave me a great algorithm.But i swear to you i worked on it at least 4 hours. But i still have errors all over the screen. I am thinking about walking through the matrix(Im using your algorithm )when it sees a nonzero element im trying to save it to another array but icant. it just gives me error. Access vialoation it says. How can we do this. Should i save those nonzero elements to an array or where?Or should i save the address of the nonzero element. Im stuck at in the beginning. Where i wanna solve is the function walk_matrix. the other part of the code is working (they are just donkey work)
Code: Select all
#include<stdio.h>
#include <time.h>
#include<stdlib.h>
#define ROW 8
#define COL 8
int a[COL][ROW];
int regions_1[ROW];
int column, row, value;
void check(int column, int row, int value);//im keeping it(it has algorithm of north, south vs)it is almost doing nothing
void matrix_printer(void);//for printing the matrix
void walk_matrix(void){
   int x, y, z;
   z = 0;
   for (x = 0; x < ROW; y++) {
      for (y = 0; y< COL; x++){
         if (a[x][y] != 1) {
            regions_1[z] = a[x][y]  ;
            z++;
         }
      }
   }
   for (x = 0; x < z; x++){
      printf("%d", regions_1[x]);
   }
}
int main(void){
   srand(time(NULL));
   int i, j, counter;//i,j and counter are all counters with different name
   
   printf("Initial Matrix\n\n");
   for (i = 0; i < COL; i++){//initial matrix
      for (j = 0; j < ROW; j++){
         a[i][j] = rand() %2;
         printf("%d  ", a[i][j]);
      }
      printf("\n");
   }
   for (i = 1; i < 20; i++){
      printf("Enter a coordinate and a value to point with order ==> column, row, value:");
      scanf("%d%d%d", &row, &column, &value);
      row = row - 1;
         column = column - 1;
      if (row == -1 || column == -1){
         printf("Terminated.\n");
         printf("The final matrix\n\n");
         matrix_printer();
         break;
      }
      else
      {
      if (column <= COL && row <= ROW){
         if (a[column][row] != 1){
            a[column ][row ] = value;
            check(column, row,value );
         }
         else{// in case the coordinate number is 1
            printf("It's border cell, please enter another coordinate\n");
         }

      }
      else{
         printf("Matrix size should fit to the size of %dx%d\n", COL, ROW);
      }
      matrix_printer();
      walk_matrix();
   }
   }

   
   system("pause");
}
void check(column, row, value){
   int north = a[column ][row -1];
   int south = a[column ][row+1];
   int west = a[column - 1][row ];
   int east = a[column+1][row ];
   if (north != 1){
      a[column ][row - 1] = value;
   }
   if (south != 1){
      a[column ][row+1] = value;
   }

   if (west != 1){
      a[column - 1][row ] = value;

   }
   if (east != 1){
      a[column+1][row ] = value;
   }
}
void matrix_printer(void){
   int counter, j;
   for (counter = 0; counter < COL; counter++){
      for (j = 0; j < ROW; j++){

         printf("%d  ", a[counter][j]);
      }
      printf("\n");
   }

}


-- Thu May 22, 2014 2:09 am --

So this is my code. It works.
Code: Select all
#include <stdio.h>
#include <stdlib.h>
 
 
#define column 12
#define row 12
 
struct stackNode{
    int* data;
    struct stackNode *nextPtr;
};
 
 
typedef struct stackNode StackNode;
typedef StackNode *StackNodePtr;
 
StackNodePtr stackPtr = NULL;
 
 
int isEmpty(StackNodePtr topPtr){
    return topPtr == NULL;
}
int* pop(StackNodePtr *topPtr){
    StackNodePtr tempPtr;
    int popValue;
 
    tempPtr = *topPtr;
    popValue = (*topPtr)->data;
    *topPtr = (*topPtr)->nextPtr;
    free(tempPtr);
    return popValue;
}
void push(StackNodePtr *topPtr, int* info){
    StackNodePtr newPtr;
 
    newPtr = malloc(sizeof(StackNode));
    if (newPtr != NULL){
        newPtr->data = info;
        newPtr->nextPtr = *topPtr;
        *topPtr = newPtr;
    }
}
void clear(void)
{
    while (getchar() != '\n');
}
void displayArray(int matrix[][column]){
    int k, i;
    for (k = 0; k < row; k++){
        for (i = 0; i < row; i++)
            printf("%c ", matrix[k][i]);
        printf("\n");
 
    }
}
void fill(int a[][column], int x, int y, int val){
    int *n;
 
    if (a[x][y] == val)
        return;
 
    int counter = 1;
 
 
    push(&stackPtr, &a[x][y]);
 
    while (!isEmpty(stackPtr)){
        n = pop(&stackPtr);
 
         
 
        if (*n == 48){
            *n = val;
            if (*(n + 1) == 48)
                push(&stackPtr, n + 1);
            if (*(n - 1) == 48)
                push(&stackPtr, n - 1);
            if (*(n + 1 * row) == 48)
                push(&stackPtr, n + 1 * row);
            if (*(n - 1 * row) == 48)
                push(&stackPtr, n - 1 * row);
             
        }
    }
}
void fillrecursive(int a[][column], int x, int y, int val){
 
    if (a[x][y] == val)
        return;
    else if (a[x][y] != 48)
        return;
    else
    {
        a[x][y] = val;
        fill(a, x, y + 1, val);
        fill(a, x + 1, y, val);
        fill(a, x, y - 1, val);
        fill(a, x - 1, y, val);
    }
}
void toascii(int matrix[][column]){
    int i, k;
    for (k = 0; k < row; k++){
        for (i = 0; i < column; i++){
            if (matrix[k][i] == 0)
                matrix[k][i] = 48;
            else if (matrix[k][i] == 1)
                matrix[k][i] = 49;
        }
    }
}
 
int main(){
 
 
    int k, i;
    int emptycell;
    int matrix[row][column] = {
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0 },
        { 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0 },
        { 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0 },
        { 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0 },
        { 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0 },
        { 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0 },
        { 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 }
 
 
    };
 
 
    toascii(matrix);
 
 
    puts("Initial Matrix: \n");
    displayArray(matrix);
 
    int x, y;
    char val;
 
 
    for (;;){
 
 
        printf("Enter value to color and Row-Column between 1-%d: ", row);
        scanf("%c%d%d", &val, &x, &y);
        clear();
        if (x <= 0 || y <= 0)
            break;
 
        x--, y--;
 
 
        while (matrix[x][y] == 1){
            printf("You can't change color of line. Enter again: ");
            scanf("%d%d", &x, &y);
 
        }
        while (x > row || y > column){
            printf("Out of matrix. Enter again: ");
            scanf("%d%d", &x, &y);
        }
 
        fill(matrix, x, y, val);
        puts("\nColored Matrix: ");
        displayArray(matrix);
 
 
    }
    puts("\nTerminated");
 
    return 0;
 
}
Secure? Come onnn...
hfakar
New User
New User
 
Posts: 7
Joined: Fri May 09, 2014 6:14 pm
Blog: View Blog (0)


Previous

Return to Programming

Who is online

Users browsing this forum: No registered users and 0 guests