Thread: 10 Kinds of People Problem

  1. #1
    Registered User
    Join Date
    May 2015
    Posts
    228

    10 Kinds of People Problem

    A full description of The problem is on this website: 10 Kinds of People – Kattis, Kattis

    The way I'm going about solving this problem is using recursion and in each call, looking to see if I can move North, South, East and West in a depth search manner.

    When I submitted my solution, I got 23/25 cases but it was too slow unfortunately so now I need to try to optimize my code so that it can run quicker. What I think is causing my program to run slow is the fact that I'm resetting the grid each time I'm done trying to find a path for a binary or decimal user.

    Unfortunately, this is something I need to do because I insert an asterisk each time I visit a cell so that I know I've been there and I need to restore the map to its original condition because it may be the case that I visit that cell again when trying to find a different path. Any ideas on how to better approach this?


    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    #define BINARY 0
    #define DECIMAL 1
    
    char **initGrid(const int, const int);
    void findBinOrDecPath(char **, char, int *, int, int, const int, const int, const int, const int);
    void resetGrid(char **, const int, const int, char);
    
    
    int main()
    {
        int numOfRows, numOfColumns, numOfQueries, startingX, startingY, destX, destY, typeOfPath = -1, i;
        char **grid;
    
        scanf("%d %d", &numOfRows, &numOfColumns);
    
        grid = initGrid(numOfRows, numOfColumns);
    
        scanf(" %d", &numOfQueries);
    
        for(i = 0; i < numOfQueries; i++)
        {
             scanf("%d %d %d %d", &startingX, &startingY, &destX, &destY);
    
            findBinOrDecPath(grid, '0', &typeOfPath, startingX - 1, startingY - 1, destX - 1, destY - 1, numOfRows,  numOfColumns);
            resetGrid(grid, numOfRows, numOfColumns, '0');
    
            if(typeOfPath != 0)
            {
                findBinOrDecPath(grid, '1', &typeOfPath, startingX - 1, startingY - 1, destX - 1, destY - 1, numOfRows,  numOfColumns);
                resetGrid(grid, numOfRows, numOfColumns, '1');
    
                if(typeOfPath == 1)
                {
                    printf("decimal");
                }
                else
                    printf("neither");
            }
            else
                printf("binary");
    
            typeOfPath = -1;
    
            printf("\n");
        }
    
        free(grid);
    
        return 0;
    }
    
    
    char **initGrid(const int numOfRows, const int numOfColumns)
    {
        char **grid;
        char *data;
        int i, j;
    
        const size_t row_pointers_bytes = numOfRows * sizeof (char *);
        const size_t row_elements_bytes = numOfColumns * sizeof (char);
        grid = malloc(row_pointers_bytes + numOfRows * row_elements_bytes);
    
        data = (char *)grid + row_pointers_bytes;
    
        for(i = 0; i < numOfRows; i++)
            grid[i] = data + i * numOfColumns;
    
        for(i = 0; i < numOfRows; i++)
        {
            for(j = 0; j < numOfColumns; j++)
            {
                scanf(" %c", &grid[i][j]);
            }
        }
    
        return grid;
    }
    
    
    void findBinOrDecPath(char **grid, char typeOfUser, int *typeOfPath, int startingX, int startingY, const int destX, const int destY,
                          const int numOfRows, const int numOfColumns)
    {
        if(grid[startingX][startingY] != typeOfUser)
        {
            return;
        }
    
        if(startingX == destX && startingY == destY)
        {
            if(typeOfUser == '0')
            {
                *typeOfPath = BINARY;
            }
            else
                *typeOfPath = DECIMAL;
        }
    
        if(startingX - 1 >= 0 && grid[startingX - 1][startingY] == typeOfUser && grid[startingX - 1][startingY] != '*')
        {
            grid[startingX][startingY] = '*';
            findBinOrDecPath(grid, typeOfUser, typeOfPath, startingX - 1, startingY, destX, destY, numOfRows, numOfColumns);
        }
    
        if(startingX + 1 < numOfRows && grid[startingX + 1][startingY] == typeOfUser && grid[startingX + 1][startingY] != '*')
        {
            grid[startingX][startingY] = '*';
            findBinOrDecPath(grid, typeOfUser, typeOfPath, startingX + 1, startingY, destX, destY, numOfRows, numOfColumns);
        }
    
        if(startingY + 1 < numOfColumns && grid[startingX][startingY + 1] == typeOfUser && grid[startingX][startingY + 1] != '*')
        {
            grid[startingX][startingY] = '*';
            findBinOrDecPath(grid, typeOfUser, typeOfPath, startingX, startingY + 1, destX, destY, numOfRows, numOfColumns);
        }
    
        if(startingY - 1 >= 0 && grid[startingX][startingY - 1] == typeOfUser && grid[startingX][startingY - 1] != '*')
        {
            grid[startingX][startingY] = '*';
            findBinOrDecPath(grid, typeOfUser, typeOfPath, startingX, startingY - 1, destX, destY, numOfRows, numOfColumns);
        }
    }
    
    
    void resetGrid(char **grid, const int numOfRows, const int numOfColumns, char typeOfUser)
    {
        int i, j;
    
        for(i = 0; i < numOfRows; i++)
        {
            for(j = 0; j < numOfColumns; j++)
            {
                if(grid[i][j] == '*' && typeOfUser == '0')
                {
                    grid[i][j] = '0';
                }
                else if(grid[i][j] == '*' && typeOfUser == '1')
                {
                    grid[i][j] = '1';
                }
            }
        }
    }
    Last edited by deathslice; 09-02-2016 at 05:40 PM.

  2. #2
    and the hat of copycat stevesmithx's Avatar
    Join Date
    Sep 2007
    Posts
    587
    First, Great job, the code is easy on the eyes.

    Second, Are you sure that the 2/25 cases are failing due to time limit exceeded and not due to a wrong answer? If yes, since you are iterating through all rows and columns for a reset, how about memcpy-ing the whole initialized 2D array each time when you need a reset and see what it does to the performance. If it doesn't, I would try memoization. When that too fails, I would assume probably a more efficient algorithm exists to solve the problem.

  3. #3
    Registered User
    Join Date
    May 2015
    Posts
    228
    Yes, the result that I get is time exceed for the second to last case. Alright, I'll use the memcpy function and report back my results.
    Last edited by deathslice; 09-02-2016 at 07:28 PM.

  4. #4
    Registered User
    Join Date
    Jun 2015
    Posts
    1,640
    Here is a somewhat more "efficient" version of your algorithm, but I doubt it will pass the tests. Try it and let me know.
    Code:
    #include <stdio.h>
    
    int walk(char m[][1000], int r, int c, int r1, int c1, int r2, int c2) {
        if (r1 == r2 && c1 == c2) return 1;
        int ret = 1;
        char sym = m[r1][c1];
        m[r1][c1] = '*';
        if (r1 > 0     && m[r1 - 1][c1]     == sym) if (walk(m, r, c, r1 - 1, c1,     r2, c2)) goto success;
        if (r1 < r - 1 && m[r1 + 1][c1]     == sym) if (walk(m, r, c, r1 + 1, c1,     r2, c2)) goto success;
        if (c1 > 0     && m[r1]    [c1 - 1] == sym) if (walk(m, r, c, r1,     c1 - 1, r2, c2)) goto success;
        if (c1 < c - 1 && m[r1]    [c1 + 1] == sym) if (walk(m, r, c, r1,     c1 + 1, r2, c2)) goto success;
        ret = 0;
    success:
        m[r1][c1] = sym;
        return ret;
    }
    
    int main(void) {
        char m[1000][1000];
        int r, c; // 1 <= r,c <= 1000
    
        scanf("%d%d", &r, &c);
        for (int ir = 0; ir < r; ir++)
            scanf("%s", m[ir]);
    
        int n;
        scanf("%d", &n); // 0 <= n <= 1000
        for (int in = 0; in < n; in++) {
            int r1, c1, r2, c2;  // 1 <= r1,r2 <= r; 1 <= c1,c2 <= c
            scanf("%d%d%d%d", &r1, &c1, &r2, &c2);
            r1--; c1--; r2--; c2--;
            if (m[r1][c1] != m[r2][c2])
                printf("neither\n");
            else if (walk(m, r, c, r1, c1, r2, c2))
                printf(m[r1][c1]=='1' ? "decimal\n" : "binary\n");
            else
                printf("neither\n");
        }
    
        return 0;
    }
    Consider the mind-bending inefficiency of this algorithm (testing every possible path).
    You should try something like A* search

  5. #5
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    I am too sleepy to understand the code posted; but, if I understand the problem correctly the end cell and the starting cell needs to be the same value.
    If it is NOT you can output neither without all the work that is needed if the are the same value.
    Depending on the data that might cut the time down a lot.

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  6. #6
    Registered User
    Join Date
    Jun 2015
    Posts
    1,640
    I decided to actually test my program at the kattis site. Your program is much more efficient than I initially thought. It blows mine out of the water!

    This is due to not erasing the asterisk every time but only at the end. I changed mine to do the same. I also changed it to dynamically allocate the matrix (like you do) in order to take advantage of any cache efficiencies this might yield due to the smaller data structure.

    It does no better than yours, however. I still wonder if something like A* is the way to go.
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    int walk(char **m, int r, int c, int r1, int c1, int r2, int c2) {
        if (r1 == r2 && c1 == c2) return 1;
        char sym = m[r1][c1];
        m[r1][c1] = '*';
        return ((r1     > 0 && m[r1 - 1][c1]     == sym && walk(m, r, c, r1 - 1, c1,     r2, c2))
            ||  (r1 + 1 < r && m[r1 + 1][c1]     == sym && walk(m, r, c, r1 + 1, c1,     r2, c2))
            ||  (c1     > 0 && m[r1]    [c1 - 1] == sym && walk(m, r, c, r1,     c1 - 1, r2, c2))
            ||  (c1 + 1 < c && m[r1]    [c1 + 1] == sym && walk(m, r, c, r1,     c1 + 1, r2, c2)));
    }
    
    int main(void) {
        int r, c; // 1 <= r,c <= 1000
        scanf("%d%d", &r, &c);
    
        char **m, *saved, *data;
        m = malloc(r * sizeof *m + r * c);
        saved = malloc(r * c);
        data = (char*)m + r * sizeof *m;
        for (int ir = 0; ir < r; ir++) {
            m[ir] = data + ir * c;
            scanf("%s", m[ir]);
        }
        memcpy(saved, data, r*c);
    
        int n;
        scanf("%d", &n); // 0 <= n <= 1000
    
        for (int in = 0; in < n; in++) {
            int r1, c1, r2, c2;  // 1 <= r1,r2 <= r; 1 <= c1,c2 <= c
            scanf("%d%d%d%d", &r1, &c1, &r2, &c2);
            r1--; c1--; r2--; c2--;
            char sym = m[r1][c1];
            if (sym != m[r2][c2])
                printf("neither\n");
            else if (walk(m, r, c, r1, c1, r2, c2))
                printf(sym=='1' ? "decimal\n" : "binary\n");
            else
                printf("neither\n");
            memcpy(data, saved, r*c);
        }
    
        free(saved);
        free(m);
        return 0;
    }

  7. #7
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    Quote Originally Posted by algorism View Post
    ..., however. I still wonder if something like A* is the way to go.
    http://cboard.cprogramming.com/redir...arch_algorithm
    I never heard of A*; it it does sound like it might be a way to solve it.
    Maybe, I will try and see if I can get it to solve the problem tomorrow.
    I have no idea how hard it will be to implement.

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Different kinds of main() function
    By Bryan_James in forum C++ Programming
    Replies: 2
    Last Post: 07-08-2016, 07:57 AM
  2. Different kinds of machines
    By Satya in forum C Programming
    Replies: 1
    Last Post: 04-24-2014, 09:52 PM
  3. Is it truly "of the people, for the people, by the people"
    By vasanth in forum A Brief History of Cprogramming.com
    Replies: 30
    Last Post: 02-21-2003, 05:44 AM
  4. IT people - weird genius or simply narrow-minded, antisocial, lazy people
    By Carlos in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 10-11-2001, 05:00 AM

Tags for this Thread