day03_02.c (4115B)
1 #if 0 2 # Self-building c file. Invoke like: `./file.c` 3 outdir=out 4 input=$(basename "$0") 5 output="$outdir"/$(basename "$0" .c) 6 if [ "$input" -nt "$output" ]; 7 then 8 mkdir --parents "$outdir" || exit 9 echo "Building ${output}." || exit 10 clang -std=c11 -Wall -Wextra -pedantic -Wno-unused-function -I../../amlibs/ "$input" -o "$output" || exit 11 fi 12 if [ "$1" = "-r" ]; 13 then 14 ./"$output" "$@" 15 fi 16 exit 17 #endif 18 19 #include <errno.h> 20 #include <inttypes.h> 21 #include <stdio.h> 22 #include <stdlib.h> 23 #include <string.h> 24 25 _Noreturn void assert_fail(const char *expr, const char *file, int line, const char *func) { 26 fprintf(stderr, "%s:%d: %s: Assertion failed: '%s'\n", file, line, func, expr); 27 abort(); 28 } 29 30 #define AM_ENABLE_ASSERT 1 31 #define AM_ASSERT_FAIL(expr, file, line, func) assert_fail(expr, file, line, func) 32 #include "am_base.h" 33 #include "am_memory.h" 34 #include "am_list.h" 35 #include "am_string.h" 36 37 Str open_file(MemArena *arena, char *path) { 38 FILE *f = fopen(path, "r"); 39 assert(f); 40 41 s32 error = fseek(f, 0L, SEEK_END); 42 assert(!error); 43 44 s64 size = ftell(f); 45 assert(size >= 0); 46 rewind(f); 47 48 u8 *buf = am_mem_arena_push(arena, size); 49 assert(buf); 50 51 size_t items_read = fread(buf, 1, size, f); 52 assert(items_read == (size_t)size); 53 54 error = fclose(f); 55 assert(!error); 56 57 return am_str(buf, size); 58 } 59 60 int compare_u64(const void *a, const void *b) { 61 u64 num_a = *((u64 *)a); 62 u64 num_b = *((u64 *)b); 63 if (num_a == num_b) { 64 return 0; 65 } else if (num_a < num_b) { 66 return -1; 67 } else { 68 return 1; 69 } 70 } 71 72 u64 filter_by_bit_frequency(u64 *numbers, u64 num_numbers, u64 number_width, bool most_popular) { 73 u64 first = 0; 74 u64 opl = num_numbers; 75 76 u64 digit = 0; 77 while (opl - first > 1) { 78 assert(digit < number_width); 79 80 //printf("Candidates for digit %" PRIu64 "\n", digit); 81 //for (u64 i = first; i < opl; i++) { 82 // char buf[64] = {0}; 83 // for (size_t digit_i = 0; digit_i < number_width; digit_i++) { 84 // buf[digit_i] = ((numbers[i] >> (number_width - 1 - digit_i)) & 1) + '0'; 85 // } 86 // printf("%4" PRIu64 ": %-4" PRIu64 " %s\n", i, numbers[i], buf); 87 //} 88 89 for (u64 i = first; i < opl; i++) { 90 if (((numbers[i] >> (number_width - 1 - digit)) & 1)) { 91 if ((i - first) > ((opl - first) / 2)) { 92 // Zero is more frequent 93 most_popular ? (opl = i) : (first = i); 94 } else { 95 // One is more or equally frequent 96 most_popular ? (first = i) : (opl = i); 97 } 98 assert(first < opl); 99 break; 100 } 101 } 102 103 digit++; 104 } 105 assert(opl - first == 1); 106 return numbers[first]; 107 } 108 109 int main(void) { 110 MemArena a = am_mem_arena_create(am_mem_base_allocator_malloc()); 111 Str input = open_file(&a, "day03_input.txt"); 112 StrList lines = am_str_split(&a, input, (u8 *)"\n", 1); 113 114 u64 num_numbers = lines.node_count; 115 u64 *numbers = AM_MEM_ARENA_PUSH_ARRAY(&a, u64, num_numbers); 116 assert(numbers); 117 memset(numbers, 0, num_numbers); 118 119 u64 width = lines.first->s.size; 120 { 121 u64 numbers_i = 0; 122 for (StrListNode *line = lines.first; line; line = line->next) { 123 assert(line->s.size == width); 124 for (u64 i = 0; i < width; i++) { 125 numbers[numbers_i] |= (line->s.str[i] == '1') << (width - i - 1); 126 } 127 numbers_i++; 128 } 129 } 130 131 qsort(numbers, num_numbers, sizeof(u64), &compare_u64); 132 133 u64 o2_generator_rating = filter_by_bit_frequency(numbers, num_numbers, width, true); 134 u64 co2_scrubber_rating = filter_by_bit_frequency(numbers, num_numbers, width, false); 135 136 //printf("Oxygen Generator Rating: %" PRIu64 "\n", o2_generator_rating); 137 //printf("CO2 Scrubber Rating: %" PRIu64 "\n", co2_scrubber_rating); 138 printf("Life Support Rating: %" PRIu64 "\n", o2_generator_rating * co2_scrubber_rating); 139 140 am_mem_arena_release(&a); 141 return 0; 142 }