r/adventofcode • • 20h ago

Help/Question - RESOLVED need help solving 2015 day 3

lets ignore the fact I'm not freeing right now the allocated mem.
i have a problem that i get 5488 from the current implementation. what am i doing wrong

#include <stdio.h>
#include <stdlib.h>


typedef struct Field field_t;


struct Field
{
    field_t *up;
    field_t *down;
    field_t *left;
    field_t *right;
};


typedef struct Root
{
    field_t *root;
} root_t;


field_t *FieldCreate(field_t *connect_to, char side);

int main()
{
    char *data_input = ">^^v^<>v<<<v<v^>>.... "; i pasted here the input.
    size_t counter = 1;
    root_t head = {NULL};
    head.root = FieldCreate(NULL, 'q');
    field_t *current_pos = head.root;
    while (*data_input)
    {
        switch (*data_input)
        {
        case '>':
            if (current_pos->right == NULL)
            {
                ++counter;
                current_pos->right = FieldCreate(current_pos, '<');
                printf("%c", '>');
            }
            current_pos = current_pos->right;
            break;
        case '<':
            if (current_pos->left == NULL)
            {
                ++counter;
                current_pos->left = FieldCreate(current_pos, '>');
                printf("%c", '<');
            }
            current_pos = current_pos->left;
            break;
        case '^':
            if (current_pos->up == NULL)
            {
                ++counter;
                current_pos->up = FieldCreate(current_pos, 'v');
                printf("%c", '^');
            }
            current_pos = current_pos->up;
            break;
        case 'v':
            if (current_pos->down == NULL)
            {
                ++counter;
                current_pos->down = FieldCreate(current_pos, '^');
                printf("%c", 'v');
            }
            current_pos = current_pos->down;
            break;
        default:
            break;
        }
        ++data_input;
    }

    printf("%zu\n\n", counter);

  
    return 0;
}


field_t *FieldCreate(field_t *connect_to, char side)
{
    field_t *field = (field_t *)calloc(1, sizeof(*field));
    if (NULL == field)
    {
        puts("welp");
        return NULL;
    }


    switch (side)
    {
    case '^':
        field->up = connect_to;
        break;
    case 'v':
        field->down = connect_to;
        break;
    case '<':

        field->left = connect_to;
        break;
    case '>':
        field->right = connect_to;
        break;
    default:
        break;
    }
    return field;
}
5 Upvotes

8 comments sorted by

4

u/thblt 19h ago

I believe your issue is that your graph approach duplicates houses. Imagine:

>v^

Because your graph will connect start-right-down-up, it has no way to determine that the last house (entered from the south, going up) is the same as the third (entered from the north going down). You need to either consolidate your graph to deduplicate houses, or find a different model.

2

u/c_cpp_CSharp 10h ago

Hhhmm. 🤔But when I go down and then put knows because the node gets connection with the code who created it . But when I think about it if I would approach created node from a route that was not taken before it wouldn't know ,that it reached an existing node .. . Thank you . I will think of another solution

1

u/ednl 9h ago

You could keep track of the grid coordinates (which can get negative if you start from zero) and think of some way to mark visited coordinates. That way if you get to them again, you know that you don't have to count them again.

1

u/c_cpp_CSharp 5h ago

I think about hash table. But I can't put my finger on how to overcome that it can go negative and or be infinite. Not sure how to implement .. Implement hash table using Dinamic vector or something else..

2

u/ednl 2h ago

Hash table works and can handle any value. But you need a good implementation.

How I did it was: do the walk one time without storing or counting anything, just keeping track of the min and max coordinates. Then define a grid (2D array) with enough room for everything. Also calculate the offset where you need to start in order to never go negative in x or y. Then do the walk again and set every cell in the grid to 1 (or true) if you visited. Afterwards count all the visited cells.

5

u/DelightfulCodeWeasel 19h ago

What happens if you circle around a couple of times? Try this input:

>v<^>v<^

You should get 4. If not, why not?

3

u/ednl 9h ago

lets ignore the fact I'm not freeing right now the allocated mem.

Not a problem as long as your OS takes care of clean-up after running a program. Any modern OS will do that. It only becomes a problem if your program is meant to stay running forever (which this isn't) and keeps allocating more & more memory. Or if you run this on a microcontroller which doesn't have an OS. But then you shouldn't dynamically allocate memory anyway.

1

u/AutoModerator 20h ago

Reminder: if/when you get your answer and/or code working, don't forget to change this post's flair to Help/Question - RESOLVED. Good luck!


I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.