// 2021-12-03
// Advent of Code 2021 Day 3
// Munashe

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <limits.h>

void printBinary(int decimal);
int reverseBits(int input, int bitWidth);
int invertBits(int input, int maskSize);
int compareBitColumn(int *array, int len, int col);
void sieve(int *result, int *input, int length, int col, int searchingMostCommon);

int main(void){
    int CAP = 1000;
    int width = 12;

    char buff[width];
    int numbers[CAP];

    char fileName[] = "input.txt";
    FILE *fp = fopen(fileName, "r");

    int count = 0;
    if(!fp) { fprintf(stderr, "Could not open %s\n", fileName); }
    while(fscanf(fp, "%s\n", buff) != EOF){
        numbers[count] = strtol(buff, NULL, 2);
        memset(&buff, 0, sizeof(buff[0])*width);
        ++count;
    }
    fclose(fp);

    //------------------------------------------------------------------------------------------------------
    // Part One
    int gamma = 0;
    for(int i = 0; i < width; ++i){ gamma = gamma << 1; gamma += compareBitColumn(numbers, count, i); }
    gamma = reverseBits(gamma, width);
    int epsilon = invertBits(gamma, width);

    printf("Power: %d\n", gamma * epsilon);

    //------------------------------------------------------------------------------------------------------
    // Part Two

    for(int i = 0; i < count; ++i){ numbers[i] = reverseBits(numbers[i], width); }

    int oxygen = 0;
    int scrubber = 0;
    int result = 0;

    sieve(&result, numbers, count, 0, 1);
    oxygen = reverseBits(result, width);

    sieve(&result, numbers, count, 0, 0);
    scrubber = reverseBits(result, width);;

    printf("Life Support: %d\n", oxygen * scrubber);
    return 0;
}

void printBinary(int decimal){
    printf("0b");
    for(int i = 0; i < 32; ++i){
        if(i % 8 == 0 && i != 0) { printf(" ");}
        printf("%c", decimal % 2 ? '1' : '0');
        decimal >>= 1;
    }
    printf("\n");
}

int reverseBits(int input, int bitWidth){
    int flipped = 0;
    for(int i = 0; i < bitWidth; ++i){
        flipped = flipped << 1; flipped += ((input >> i) & 1);
    }
    return flipped;
}

int invertBits(int input, int maskSize){
    return (~input) ^ (UINT_MAX << maskSize);
}

int compareBitColumn(int *array, int len, int col){
    int bitRatio = 0;
    for(int j = 0; j < len; ++j){
        if((array[j] >> col) & 1) { bitRatio++; } else { bitRatio--; }
    }
    return (bitRatio >= 0);
}

void sieve(int *result, int *input, int length, int col, int searchingMostCommon){
    if(length == 1){
        *result = input[0];
    } else {
        int *newStack = malloc(sizeof(input[0])*length);
        int newLength = 0;
        int mostCommon = compareBitColumn(input, length, col);;
        if(!searchingMostCommon) { mostCommon = (mostCommon == 1) ? 0 : 1; }
        for(int j = 0; j < length; ++j){
            if(mostCommon == 1){
                if((input[j] >> col) & 1) { newStack[newLength++] = input[j]; }
            } else {
                if(((input[j] >> col) & 1) == 0) { newStack[newLength++] = input[j]; }
            }
        }
        sieve(result, newStack, newLength, col+1, searchingMostCommon);
    }
}