Ryan is an engineer in the Sacramento Area with a focus in Python, Ruby, and Rust. Bash/Python Exercism mentor. Coding, physics, calculus, music, woodworking. Looking for work!
Whew! I think in any other language, this would have been a lot smaller and less verbose, but C made me work it all out loop by loop. It's so much code. My eyes are crossed.
But it works great! I got foiled right at the end by a "not big enough output type" bug that had my answer overflowing and becoming too small. And did a butt ton of debugging and going in the wrong direction before slapping my head and hitting a bunch of undos.
Anyways, I'm pretty happy about how it finally turned out. There were a lot of moving pieces and I think I handled them, if not algorithmically quickly, at least cleanly and readably. And it's still pretty fast.
Also, I love strtok. That is all.
#include "Day16.h"
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
#include "parsing.h"
typedefstruct{charname[25];intmin1;intmax1;intmin2;intmax2;}Field;/// A field line is of the pattern:/// <name>: <min1>-<max1> or <min2>-<max2>Fieldparse_field_line(char*line){Fieldf={{0},0,0,0,0};char*name=strtok(line,":");char*min1=strtok(NULL,"-");char*max1=strtok(NULL," ");strtok(NULL," ");char*min2=strtok(NULL,"-");char*max2=strtok(NULL,"\n");strcpy(f.name,name);f.min1=atoi(min1);f.max1=atoi(max1);f.min2=atoi(min2);f.max2=atoi(max2);returnf;}Field*parse_fields(FILE*fp,int*count){*count=count_lines_until_blank(fp);Field*fields=(Field*)malloc(sizeof(Field)**count);charline[100];for(inti=0;i<*count;i++){memset(line,0,100);fgets(line,100,fp);fields[i]=parse_field_line(line);}returnfields;}int*parse_my_values(FILE*fp,intfield_count){int*my_values=(int*)malloc(sizeof(int)*field_count);for(inti=0;i<field_count;i++){fscanf(fp,"%d",&my_values[i]);getc(fp);}returnmy_values;}int**parse_tickets(FILE*fp,intfield_count,int*row_count){size_tpos=ftell(fp);*row_count=count_lines(fp);fseek(fp,pos,SEEK_SET);int**rows=(int**)malloc(sizeof(int*)**row_count);for(inti=0;i<*row_count;i++){rows[i]=(int*)malloc(sizeof(int)*field_count);for(intj=0;j<field_count;j++){fscanf(fp,"%d",&rows[i][j]);getc(fp);}}returnrows;}/// Decides if a value is valid in at least one field.staticboolis_valid(intvalue,Field*fields,intfield_count){for(inti=0;i<field_count;i++){Fieldf=fields[i];if((f.min1<=value&&f.max1>=value)||(f.min2<=value&&f.max2>=value)){returntrue;}}returnfalse;}/// Shifts the file pointer cursor forward n lines.voidconsume_lines(FILE*fp,intn){intnewlines=0;charc;while(newlines<n){c=getc(fp);if(c=='\n'){newlines++;}}}/// Add up all of the invalid numbers from the nearby tickets.intpart1(constchar*filename){FILE*fp;fp=fopen(filename,"r");if(fp==NULL){printf("Could not open file.\n");exit(EXIT_FAILURE);}// Parse the fileintfield_count;Field*fields=parse_fields(fp,&field_count);consume_lines(fp,5);introw_count;int**values=parse_tickets(fp,field_count,&row_count);// Add up all of the invalid values on each nearby ticketinttotal=0;for(inti=0;i<row_count;i++){for(intj=0;j<field_count;j++){if(!is_valid(values[i][j],fields,field_count)){total+=values[i][j];}}}// Clean up and returnfclose(fp);free(fields);for(inti=0;i<row_count;i++)free(values[i]);free(values);returntotal;}/// Returns true if a ticket contains any invalid numbersboolcontains_invalid(int*numbers,Field*fields,intfield_count){for(inti=0;i<field_count;i++){if(!is_valid(numbers[i],fields,field_count))returntrue;}returnfalse;}voiddrop_invalid_tickets(int**tickets,introw_count,Field*fields,intfield_count){// Drop any nearby tickets with any invalid numbersfor(inti=0;i<row_count;i++){if(contains_invalid(tickets[i],fields,field_count)){free(tickets[i]);tickets[i]=NULL;}}}/// Creates a boolean grid where the rows represent fields and the/// columns represent columns on a ticket. A `true` represents that/// that column could still possibly be represented by that field's rules/// and all tickets so far have adhered to that field's rules in that/// column.bool**create_possibility_grid(intfield_count){bool**possibilities=(bool**)malloc(sizeof(bool*)*field_count);for(inti=0;i<field_count;i++){possibilities[i]=(bool*)malloc(sizeof(bool)*field_count);for(intj=0;j<field_count;j++){possibilities[i][j]=true;}}returnpossibilities;}/// Prune down the possibility values. If a ticket has a value in/// a column that breaks a rule, that rule can't apply to that column/// for any ticket.voidrule_out_possibilities(bool**possibilities,int**tickets,introw_count,Field*fields,intfield_count){for(inti=0;i<row_count;i++){if(tickets[i]==NULL)continue;for(intj=0;j<field_count;j++){for(intk=0;k<field_count;k++){Fieldf=fields[k];intval=tickets[i][j];possibilities[k][j]&=((f.min1<=val&&f.max1>=val)||(f.min2<=val&&f.max2>=val));}}}}/// Count the number of `true` cells in a row.intcount_possibles(bool**possibilities,introw,intfield_count){intcount=0;for(inti=0;i<field_count;i++){if(possibilities[row][i])count++;}returncount;}/// Find the one (and there will be only one) column index where the/// cell in that row is `true`.intfind_possible(bool**possibilities,introw,intfield_count){for(inti=0;i<field_count;i++){if(possibilities[row][i])returni;}return-1;}/// Find the one row (and there will always be exactly one) that/// only has one column still true. Assign that column to that field/// and remove that as a possibility from all other fields.voidassign_decided_field(int*assignments,intfield_count,bool**possibilities){for(introw=0;row<field_count;row++){if(count_possibles(possibilities,row,field_count)!=1){continue;}intcol=find_possible(possibilities,row,field_count);assignments[row]=col;// Set all other rows to false for this columnfor(intk=0;k<field_count;k++){possibilities[k][col]=false;}return;}printf("Couldn't find a decided row.\n");exit(EXIT_FAILURE);}/// Discover which fields go to which columns on the ticket by process/// of elimination. Multiply any values on my own ticket together/// if the associated field starts with 'departure'longpart2(constchar*filename){FILE*fp;fp=fopen(filename,"r");if(fp==NULL){printf("Could not open file.\n");exit(EXIT_FAILURE);}// Parse fileintfield_count;Field*fields=parse_fields(fp,&field_count);consume_lines(fp,2);int*my_values=parse_my_values(fp,field_count);consume_lines(fp,2);introw_count;int**tickets=parse_tickets(fp,field_count,&row_count);// Preprocess tickets and possibilitiesdrop_invalid_tickets(tickets,row_count,fields,field_count);bool**possible_fields=create_possibility_grid(field_count);rule_out_possibilities(possible_fields,tickets,row_count,fields,field_count);// Narrow down and assign columns by process of elimination.// Assumes there will always be exactly one row each iteration// With only one possible assignment.intassignments[field_count];for(inti=0;i<field_count;i++){assign_decided_field(assignments,field_count,possible_fields);}// Product up the departure columnslongtotal=1;for(inti=0;i<field_count;i++){if(strncmp(fields[i].name,"departure",9)==0){total*=my_values[assignments[i]];}}// Clean up and return.fclose(fp);free(fields);for(inti=0;i<field_count;i++)free(possible_fields[i]);free(possible_fields);for(inti=0;i<row_count;i++)free(tickets[i]);free(tickets);free(my_values);returntotal;}intday16(){printf("====== Day 16 ======\n");printf("Part 1: %d\n",part1("data/day16.txt"));printf("Part 2: %ld\n",part2("data/day16.txt"));returnEXIT_SUCCESS;}
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
Whew! I think in any other language, this would have been a lot smaller and less verbose, but C made me work it all out loop by loop. It's so much code. My eyes are crossed.
But it works great! I got foiled right at the end by a "not big enough output type" bug that had my answer overflowing and becoming too small. And did a butt ton of debugging and going in the wrong direction before slapping my head and hitting a bunch of undos.
Anyways, I'm pretty happy about how it finally turned out. There were a lot of moving pieces and I think I handled them, if not algorithmically quickly, at least cleanly and readably. And it's still pretty fast.
Also, I love
strtok
. That is all.