Advent of Code 2022 Day 13 Solution in C: Sorting and parsing nested list

Question

Link to Original Problem: Advent of Code 2022 Day 13

Question Summary:

The task involves sorting and parsing nested lists, with two parts:

1. Determine pairs in the correct order and calculate the sum of their indices.
2. Sort all lists ignoring pairings, then locate the indices of additional elements [[2]] and [[6]] and find their product.

*note the question uses 1-indexing for both parts

Example Input:

[1,1,3,1,1]
[1,1,5,1,1]
[[1],[2,3,4]]
[[1],4]
[9]
[[8,7,6]]
[[4,4],4,4]
[[4,4],4,4,4]
[7,7,7,7]
[7,7,7]
[]
[3]
[[[]]]
[[]]
[1,[2,[3,[4,[5,6,7]]]],8,9]
[1,[2,[3,[4,[5,6,0]]]],8,9]

Example Solution:

• Part 1: Pairs 1, 2, 4, and 6 are in the correct order. The sum of their indices is 13.
• Part 2: Sorting results in:

[]
[[]]
[[[]]]
[1,1,3,1,1]
[1,1,5,1,1]
[[1],[2,3,4]]
[1,[2,[3,[4,[5,6,0]]]],8,9]
[1,[2,[3,[4,[5,6,7]]]],8,9]
[[1],4]
[[2]]
[3]
[[4,4],4,4]
[[4,4],4,4,4]
[[6]]
[7,7,7]
[7,7,7,7]
[[8,7,6]]
[9]

We locate [[2]] at index 10 and [[6]] at index 14, resulting in a product of 140.

Approach:

1. Getting input file name from command-line arguments.
2. Opening of file.
3. Convert input string to a linked list structure.
4. Implement comparison function to determine ordering.
5. Utilize qsort for sorting the array.
6. Locate indices of elements [[2]] and [[6]].

Implementation:

• Data Structure: Node struct representing a nested linked list.
• Parsing: parseString2List function returning a pointer to the head node, number of characters parsed, and success status.
• Comparison: compare function returning -1 for a < b, 0 for a == b, and 1 for a > b.
• Printing: printList function print out the nested structure (for debugging).

Full Code:

#include <errno.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node Node;
typedef struct Package Package;
void calculate(FILE *file);
int compare(const void *a, const void *b);
Node *createNode(char type, int value);
int fileOpener(int argc, char *argv[], FILE **file);
void freeList(Node *n);
void getFileDimension(FILE *file, int *dimension);
Package parseString2List(char *c);
void printList(Node *n);
int main(int argc, char *argv[]) {
 FILE *file = NULL;
 if (!fileOpener(argc, argv, &file)) {
 return 1;
 }
 calculate(file);
 return 0;
}
typedef struct Node {
 union {
 int i;
 struct Node *list;
 } data;
 char dataType;
 struct Node *next;
} Node;
typedef struct Package {
 bool success;
 int charParsed;
 Node *node;
} Package;
void calculate(FILE *file) {
 int dimension[2];
 getFileDimension(file, dimension);
 int max_width = dimension[0];
 int height = dimension[1];
 const int SIZE = ((height + 4) * 2) / 3;
 char buf[max_width];
 Package p;
 Node *listOfList[SIZE];
 int i = -1;
 int j = 0;
 int answer1 = 0;
 int answer2 = 1;
 Package temp_package = parseString2List("[[2]]");
 Node *FLAG1 = temp_package.node;
 temp_package = parseString2List("[[6]]");
 Node *FLAG2 = temp_package.node;
 while (fgets(buf, sizeof buf, file) != NULL) {
 i++;
 if (i % 3 == 2) {
 continue;
 }
 j = i * 2 / 3 + i % 3;
 p = parseString2List(buf);
 if (!p.success) {
 return;
 }
 listOfList[j] = p.node;
 ;
 if (j % 2 != 0) {
 if (compare(listOfList[j - 1], listOfList[j]) <= 0) {
 answer1 += (i / 3) + 1;
 }
 }
 }
 printf("%d\n", answer1);
 listOfList[j + 1] = FLAG1;
 listOfList[j + 2] = FLAG2;
 qsort(listOfList, SIZE, sizeof(Node *), &compare);
 for (i = 0; i < SIZE; i++) {
 if (listOfList[i] == FLAG1) {
 answer2 *= (i + 1);
 } else if (listOfList[i] == FLAG2) {
 answer2 *= (i + 1);
 }
 freeList(listOfList[i]);
 }
 printf("%d\n", answer2);
}
int compare(const void *a, const void *b) {
 Node *nodeA = (Node *)a;
 Node *nodeB = (Node *)b;
 if (a == NULL && b == NULL) {
 return 0;
 } else if (a == NULL) {
 return -1;
 } else if (b == NULL) {
 return 1;
 }
 if (nodeA->dataType == 'i' && nodeB->dataType == 'i') {
 if (nodeA->data.i < nodeB->data.i)
 return -1;
 else if (nodeA->data.i > nodeB->data.i)
 return 1;
 else
 return compare(nodeA->next, nodeB->next);
 }
 if (nodeA->dataType == 'i') {
 Node newNode = {.dataType = 'l', .data.list = nodeA, .next = NULL};
 return compare(&newNode, nodeB);
 }
 if (nodeB->dataType == 'i') {
 Node newNode = {.dataType = 'l', .data.list = nodeB, .next = NULL};
 return compare(nodeA, &newNode);
 }
 int r = compare(nodeA->data.list, nodeB->data.list);
 if (r != 0) {
 return r;
 }
 return compare(nodeA->next, nodeB->next);
}
Node *createNode(char type, int value) {
 Node *node = calloc(1, sizeof(Node));
 if (node == NULL) {
 perror("Memory allocation error");
 exit(EXIT_FAILURE);
 }
 node->dataType = type;
 if (type == 'i') {
 node->data.i = value;
 }
 return node;
}
int fileOpener(int argc, char *argv[], FILE **file) {
 if (argc == 1) {
 printf("No file has been provided\n");
 return 0;
 }
 *file = fopen(argv[1], "r");
 if (*file == NULL) {
 perror("Error opening file");
 return 0;
 }
 return 1;
}
void freeList(Node *n) {
 while (n != NULL) {
 Node *temp = n;
 n = n->next;
 if (temp->dataType == 'l') {
 freeList(temp->data.list);
 }
 free(temp);
 }
}
void getFileDimension(FILE *file, int *dimension) {
 char c;
 int max_width = 0;
 int width = 0;
 int height = 1;
 fseek(file, 0, SEEK_SET);
 while ((c = fgetc(file)) != EOF) {
 if (c == '\n') {
 height++;
 if (width > max_width) {
 max_width = width + 3;
 }
 width = 0;
 } else {
 width++;
 }
 }
 if (width > max_width) {
 max_width = width + 3;
 }
 dimension[0] = max_width;
 dimension[1] = height;
 fseek(file, 0, SEEK_SET);
}
Package parseString2List(char *c) {
 int length = strlen(c);
 Package package = {.success = false, .charParsed = 0, .node = NULL};
 if (c[0] != '[' && c[length - 1] != ']') {
 return package;
 }
 Node *current = NULL;
 Node *head = NULL;
 int i = 1;
 while (i < length) {
 if (c[i] == '[') {
 Package temp = parseString2List(&c[i]);
 if (!temp.success) {
 package.charParsed = i + temp.charParsed;
 return package;
 }
 Node *nestedList = temp.node;
 Node *newNode = createNode('l', 0);
 if (current == NULL) {
 head = newNode;
 } else {
 current->next = newNode;
 }
 newNode->data.list = nestedList;
 current = newNode;
 i += (temp.charParsed + 1);
 } else if (c[i] == ',' || c[i] == ' ') {
 i++;
 } else if (c[i] == ']') {
 package = (Package){.success = true, .charParsed = i, .node = head};
 return package;
 } else {
 char *end;
 errno = 0;
 long number = strtol(&c[i], &end, 10);
 if (*end == '0円') {
 fprintf(stderr, "Error parsing integer\n");
 freeList(head);
 return package;
 }
 Node *newNode = createNode('i', (int)number);
 if (current == NULL) {
 head = newNode;
 } else {
 current->next = newNode;
 }
 current = newNode;
 i = end - c;
 }
 }
 package.charParsed = i;
 fprintf(stderr, "List never terminated\n");
 freeList(head);
 return package;
}
void printList(Node *n) {
 printf("[");
 while (n != NULL) {
 if (n->dataType == 'l') {
 printList(n->data.list);
 } else {
 printf("%d", n->data.i);
 }
 if (n->next != NULL) {
 printf(", ");
 }
 n = n->next;
 }
 printf("]");
}

Usage:

gcc -o aoc aoc.c
./aoc input.txt

Please provide feedback and suggestions for improvement.

• CPlus: if (a == NULL && b == NULL) { return 0; } else if (a == NULL) { return -1; } else if (b == NULL) { return 1; } -> if (!(a && b)) return !b - !a;

Answer 1

Separate the list implementation from the main translation unit:

Currently, the list can not be used in any other program. Move it to a separate source file and include its corresponding header in the main program.

Define main() at the end of the translation unit:

If we define main() at the end, we wouldn't require all the forward declarations of the functions.

Extra arguments to main():

fileOpener() checks whether at least 2 arguments were provided to the program, but what when more than 2 are provided? Currently, one can pass around INT_MAX arguments to the program.

Prefer standard exit status values to non-standard ones:

Use EXIT_FAILURE and EXIT_SUCCESS from stdlib.h to signify failure and success respectively.

Eliminate redundant function calls:

fseek(file, 0, SEEK_SET);

does nothing at the beginning of calculate(), as the file position indicator is already at the beginning of the file.

As of the second call, it can be replaced with rewind(file).

Read the file in large chunks:

Currently you're reading it byte by byte, and whilst that has the benefit of not having to allocate anything, reading it in bigger chunks (4-64 Kib) should prove to be faster.

Use sizeof *ptr instead of sizeof (type) in calls to malloc() and family:

#if 0
Node *node = calloc(1, sizeof(Node));
#else
Node *node = calloc(1, sizeof *node);
#endif

It will reduce maintenance headaches if you ever change the type of node.

strlen() returns size_t, not int:

int length = strlen(c);

The compiler would have complained about this if you had enabled warnings. Specify -Wextra -Werror -Wpedantic to gcc.

Use const for data that is not modified:

In:

Package parseString2List(char *c) {

c remains unmodified. Therefore, it should be declared as:

Package parseString2List(const char *c) {