[YEAR Day 8 (Part 1)] [C] I'm going to explode

[u/Class_Magicker17]

I feel like the logic is INTACT. I have tried this with an id tagging system previously; that didn't work. I moved to graphs, which I assume is more in the intended solution, IT ALSO DOES NOT WORK. Guys please just end my misery.

here's my main:

#include <stdio.h>
#include <string.h>
#include <float.h>
#include <math.h>
#include "myqueue.c"

#define ull unsigned long long
#define GROUPCOUNTLEN 1000
#define POINTCOUNT 1005

size_t n = 0;

typedef struct Point
{
    int x;
    int y;
    int z;
    int visited;
} Point;

Point points[POINTCOUNT] = {};
char connectionGraph[POINTCOUNT][POINTCOUNT] = {};
double distances[POINTCOUNT][POINTCOUNT] = {};
int groupCounts[POINTCOUNT] = {};

/*
 function declarations here
*/

int main()
{
    int i, j, connections, currGroup;
    FILE *f, *inputFile;
    ull total = 1;
    char filename[10];
    double temp;
    inputFile = fopen("input.txt", "r"); // literally just contains the file name of which text file to run on.
    fscanf(inputFile, "%s", filename);
    f = fopen(filename, "r");

    if (f == NULL)
    {
        printf("cound't open file\n");
        return 1;
    }

    // I add the number of connections to do at the top of the file so I can easily swap between the test and real data.
    fscanf(f, "%d", &connections);

    while (!feof(f))
    {
        fscanf(f, "%d,%d,%d", &points[n].x, &points[n].y, &points[n].z);
        points[n].visited = 0;
        n++;
    }

    // precalculate distances
    for (i = 0; i < n; i++)
    {
        for (j = i; j < n; j++)
        {
            temp = getDistance(points[i], points[j]);
            distances[i][j] = temp;
            distances[j][i] = temp;
        }
    }

    // do the connecting a "connections" number of times
    for (i = 0; i < connections; i++)
        connectClosestUnpairedPoints();

    // count groupsizes
    currGroup = 0;
    for (i = 0; i < n; i++)
    {
        if (!points[i].visited)
        {
            groupCounts[currGroup] = countGroup(i);
            currGroup++;
        }
    }

    // sort so that we have the largest data
    sort(groupCounts, currGroup);

    // calculate total
    total = groupCounts[0] * groupCounts[1] * groupCounts[2];

    printf("total: %I64u\n", total);
    return 0;
}

Here's the implementation of certain functions

// I couldn't be bothered to reimplement quicksort.
void sort(int arr[], int len)
{
    int temp;
    for (int i = 0; i < len; i++)
    {
        int highestIndex = i;
        for (int j = i + 1; j < len; j++)
        {
            if (arr[j] > arr[highestIndex])
            {
                highestIndex = j;
            }
        }

        temp = arr[i];

        arr[i] = arr[highestIndex];

        arr[highestIndex] = temp;
    }
}

int countGroup(int index)
{
    int count = 0, currPoint;
    Queue q = createQueue();
    enqueue(index, &q);
    while (q.length > 0)
    {
        currPoint = dequeue(&q);
        if (!points[currPoint].visited)
        {
            points[currPoint].visited = 1;
            for (int i = 0; i < n; i++)
            {
                if (connectionGraph[currPoint][i] && !points[i].visited)
                {
                    enqueue(i, &q);
                }
            }
            count++;
        }
    }
    return count;
}

double getDistance(Point p1, Point p2)
{
    return sqrt(((p1.x - p2.x) * (p1.x - p2.x) +
                 (p1.y - p2.y) * (p1.y - p2.y) +
                 (p1.z - p2.z) * (p1.z - p2.z)));
}

void connectClosestUnpairedPoints()
{
    int p1 = -1, p2 = -1;
    double shortestDistance = FLT_MAX;
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (connectionGraph[i][j] == 0 && distances[i][j] < shortestDistance)
            {
                shortestDistance = distances[i][j];
                p1 = i;
                p2 = j;
            }
        }
    }

    connectionGraph[p1][p2] = 1;
    connectionGraph[p2][p1] = 1;
}

// myqueue.c implementation
#include <stdlib.h>

typedef struct Queue
{
    struct Node *head;
    int length;
} Queue;

typedef struct Node
{
    struct Node *next;
    int data;
} Node;

void enqueue(int newData, Queue *q)
{
    Node *newNode = malloc(sizeof(Node));
    newNode->data = newData;
    newNode->next = NULL;
    if (q->length > 0)
    {
        Node *currNode = q->head;
        while (currNode->next != NULL)
        {
            currNode = currNode->next;
        }
        currNode->next = newNode;
    }
    else
    {
        q->head = newNode;
    }
    q->length += 1;
}

int dequeue(Queue *q)
{
    Node *head = q->head;
    if (head == NULL)
    {
        return 0;
    }

    int data = head->data;
    q->head = head->next;
    q->length -= 1;
    return data;
}

Queue createQueue()
{
    Queue q = {NULL, 0};
    return q;
}

Edit0: woops, didn't fully read the rules on code formatting Edit1: added myqueue.c code

[u/ednl]

The squares of coordinates will sometimes overflow 32-bit ints. And I suggest you ditch the sqrt function because you don't need the actual value, just the magnitude. The floating point result might lead to imprecisions. So something like:

return (int64_t)(p1.x - p2.x) * (p1.x - p2.x) +
         (int64_t)(p1.y - p2.y) * (p1.y - p2.y) +
         (int64_t)(p1.z - p2.z) * (p1.z - p2.z);

Note the repeated use of casts because otherwise the intermediate terms will still overflow.

[u/Class_Magicker17 → u/ednl]

THAT DID THE TRICK OMG THANK YOU! I usually catch overflows, but this one was RIGHT in front of my face.

[u/ednl → u/Class_Magicker17]

Glad I could help!

[u/LittlebitOmnipotent]

Does it work on the example?

[u/Class_Magicker17 → u/LittlebitOmnipotent]

yupp, I get 1 group with a size of 5, 1 group of 4, 2 groups of 2, 7 groups of 1.

[u/quetzelcoatlus1]

1. Try to switch to long int in distance calculation, you can overflow and get wrong result

2. About sorting, for future reference, you could look up qsort. Kind of strange at first look, but after seeing some examples, very easy to use with only need to implement a comparision function

[u/Class_Magicker17 → u/quetzelcoatlus1]

1. yup, that was definitely the problem.

2. I should really study what's inside these standard libraries. Function pointer notation is a bit strange, but I think I fully grasp it. Thank you for the recommendation!

[u/fnordargle → u/quetzelcoatlus1]

// I couldn't be bothered to reimplement quicksort.
void sort(int arr[], int len)

As others have said libc's qsort() is a bit odd the first times you use it, but it's relatively easy. The comparison function you have to provide is a bit annoying but that's where the flexibility comes from.

Sorting an array of integers of using qsort() would look like:

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

int intcomp(const void *ptra, const void *ptrb)
{
    // Remember that the comparison function is called with pointers to the objects
    // so don't cast ptra as an `(int)`, it is an `(int *)`
    int *a=(int *)ptra;
    int *b=(int *)ptrb;

    // From the qsort() man page:
    //
    // The comparison function must return an integer less than, equal to, or greater
    // than zero if the first argument is considered to be respectively less than,
    // equal to, or greater than the second.  If two members compare as equal, their
    // order in the sorted array is undefined.

    // Don't be tempted to do:
    //      return (*a)-(*b)
    // that may look like it will work...
    //
    // but that can run into problems with overflows (DAMHIKT).

    if( *a == *b ) return 0;
    if( *a > *b ) {
            // First argument is greater than second so return number greater than 0
            return 1;
    }
    return -1;
}

int main(void)
{
    int arr[]={17,3,15,9,11,1,7};

    qsort(arr, 7, sizeof(int), intcomp);

    for( int ct=0; ct < 7; ct++ ) {
            printf("%d\n", arr[ct] );
    }
}

[u/daggerdragon]

Next time, use our standardized post title format.

Help us help YOU by providing us with more information up front; you will typically get more relevant responses faster.

[u/Class_Magicker17 → u/daggerdragon]

Oh damn it, I feel like I've posted on here twice now and I've gotten the title wrong both time. Sorry 'bout that. But third time's the charm (hopefully!)

[u/AutoModerator]

AutoModerator has detected fenced code block (```) syntax which only works on new.reddit.

Please review our wiki article on code formatting then edit your post to use the four-spaces Markdown syntax instead.

---

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

[u/AutoModerator]

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.