CODEWITHSUNDEEP
coverflowbuffer
Lou
Lou

Reputation: 117

how to read a large file (at most 2 000 000 000 char) and stock them

I'm trying to solve a problem, for that I have an input file containing a maze, I know how o solve the maze but I don't know how to stock the maze. I can't stock it in a char array because the file can be at most 2 billions char. I don't know how to stock the file without exploding the buffer... the file is read with the read command (fread isn't allowed).

Upvotes: 0

Views: 231

Answers (3)

guilleamodeo
guilleamodeo

Reputation: 380

From your description sounds like you need to read a maze and then store a copy of the solved maze.

Let's asume that your maze would be stored as a bi-dimensional array of chars, with one char representing bricks of walls -e.g. '*'- and another one being the open space -e.g. ' '-, so a small 8 x 8 maze might look like this: 


    ****** *
    *      *
    * **** *
    * *    *
    * *** **
    *   *  *
    *** ****
    *** ****

Then you need to do your solving, and store the maze with a char representing the steps of the path followed to solve it. Which -assuming the char is '+' , it will look like this:


    ******+*
    *++++++*
    *+ *** *
    *+ *   *
    *+*** **
    *+++*  *
    ***+****
    ***+****

It it was me -and being the goal to use little memory-, the first thing that I would do is to convert the maze to bits, where the asterisk would be represented by a 1 and the space by a 0. The resulting map would be 8 times smaller. Then I would do my solving but like I can't store the '+' in the map -bits can only have 2 values-, I would instead store the location of each of the steps on a linked list. Then I will save the output maze by reading every location of the map and checking it in the list, if it is there I will output a '+', otherwise I'll check the bit and output '*' if its 1, and ' ' if its 0.

Like this is a college project, I am not goign to give you all the code here -as you should write it yourself- but I'll give you enough clues on the form of some unoptimized code. ;-) 

struct pos {
    int x,y;
    struct pos *next;
};

struct pos *step_list=NULL;

#define MAZE_WIDTH_BITS  ((MAZE_WIDTH + 7) / 8)

unsigned char bitmaze[MAZE_HEIGHT][MAZE_WIDTH_BITS];

int getbit(int x,int y)
{
    unsigned char v = bitmaze[y][(x / 8)];


    v >>= 7 - (x % 8);
    return (v & 1);
}


void save_maze(FILE *fp)
{
    int x,y,found;
    struct pos *cur_step;

    for(y=0;y<MAZE_HEIGHT;y++)
    {
        for(x=0;x<MAZE_WIDTH;x++)
        {
            found=0;
            cur_step=step_list;
            while(cur_step && !found)
            {
                if(cur_step->x==x && cur_step->y==y)
                     found=1;
                else
                    cur_step=cur_step->prox;
            }
            if(found)
                fputc('+',fp);
            else
                fputc( getbit(x,y) ? '*' : ' ',fp);
        }
    }
}

Hope this help you. guilleamodeo.

Upvotes: 2

istovatis
istovatis

Reputation: 1408

Why don't you just allocate memory for 2000000000 char array? The only limit is your pc memory. If there is sufficient contiguous address space left, there is no problem.

You can try something like char *my_maze = (char*) malloc((2000000000 * sizeof(char)));

Upvotes: 0

Farouq Jouti
Farouq Jouti

Reputation: 1667

well you can use a linked list where each node contains a character, it will take a lot , A LOT , of space but it'll do it

Upvotes: 0

Related Questions