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';
            }
        }
    }
}

---

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.

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.

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

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.

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;
}

---

Quote:

---

Originally Posted by algorism

..., 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.