aoc2019/d1-10/day6.c

//
// Created by red on 07/12/19.
//

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

#define CHUNK_SIZE 16
typedef struct node {
  int label;
  struct node** children;
  size_t num_children;
} node;

typedef struct forest {
  int* list_labels; // list of all node labels that exist somewhere in the tree
  size_t num_nodes; // amount of nodes
  struct node** trees;
  size_t num_trees;
} forest;

//return a zero-initialized node
node* init_node(int label) {
  node* v = malloc(sizeof(node));
  v->num_children = 0;
  v->children = calloc(CHUNK_SIZE, sizeof(node*));
  v->label = label;
  return v;
}

void add(node* head, node* child, int label_parent) {
  if (head->label == label_parent) {
    if (head->num_children >= CHUNK_SIZE) printf("Max number of children reached, array reallocation not implemented\n");
    head->children[head->num_children] = child;
    head->num_children++;
  } else for (size_t i = 0; i < head->num_children; i++) {
    add(head->children[i], child, label_parent);
  }
}

void print_tree(node* head) {
  if (head->num_children == 0) {
    printf("Node %x, no children\n", head->label); return;
  }
  printf("Children of node %x:", head->label);
  for (size_t i = 0; i < head->num_children; i++) {
    printf(" %x", head->children[i]->label);
  }
  printf("\n");
  for (size_t i = 0; i < head->num_children; i++) {
    print_tree(head->children[i]);
  }
}

node* read_file(char* filename) {
  FILE* file = fopen(filename, "r");
  char desc_str[7];
  fscanf(file, "%s", desc_str);
  int label_parent = (desc_str[0] << 16) + (desc_str[1] << 8) + desc_str[2];
  int label = (desc_str[4] << 16) + (desc_str[5] << 8) + desc_str[6];
  node* head = init_node(label_parent);
  add(head, init_node(label), label_parent);
  for (;;) {
    if (fscanf(file, "%s", desc_str) == EOF) break;
    label_parent = (desc_str[0] << 16) + (desc_str[1] << 8) + desc_str[2];
    label = (desc_str[4] << 16) + (desc_str[5] << 8) + desc_str[6];
    add(head, init_node(label), label_parent);
    if (head->label == label) {
      node* nhead = init_node(label_parent);
      add(nhead, head, label_parent);
      head = nhead;
    }
  }
  return head;
}

int count_nodes(node* head, int depth) {
  int sum = depth;
  for (size_t i = 0; i < head->num_children; i++) {
    sum += count_nodes(head->children[i], depth+1);
  }
  return sum;
}

int main(int argc, char **argv) {
  char* filename = argv[1];
  node* head = read_file(filename);
  int orbits = count_nodes(head, 0);
  print_tree(head);
  printf("no. orbits: %d\n", orbits);
}