I've been somewhat frugal with memory by using an out-of-core algorithm for each solution so far. Fido's code didn't discover any bugs.
Code: Select all
/* Advent of Code 2022 Day 5 Camp Cleanup
Written December 2022 by Eric Olson */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <fcntl.h>
#include <string.h>
#ifdef LINUX
#include <time.h>
static struct timespec tic_start;
void tic(){
clock_gettime(CLOCK_MONOTONIC_RAW,&tic_start);
}
float toc(){
struct timespec tic_stop;
clock_gettime(CLOCK_MONOTONIC_RAW,&tic_stop);
float sec=tic_stop.tv_sec-tic_start.tv_sec;
return sec+(tic_stop.tv_nsec-tic_start.tv_nsec)*1.0e-9;
}
#endif
#ifndef LINUX
int tstart;
void tic(){
tstart=time_us_32();
}
float toc(){
return (float)(time_us_32()-tstart)/1000000.0;
}
#endif
#define BUFSZ 128
#define UGBSZ 32
struct fpspec {
int fd,a,b,m;
char c[BUFSZ],u[UGBSZ];
struct fpspec *r;
};
struct fpspec rroot;
struct fpspec *fproot;
char *psindex(char *s,int c){
do {
if(*s==c) return s;
} while(*++s);
return 0;
}
char *fierror;
struct fpspec *fpopen(char *fn,char *mode){
int m=0;
if(psindex(mode,'r')) m|=1;
if(psindex(mode,'w')) m|=2;
if(!m){
printf("Invalid mode %s to open file %s!\n",mode,fn);
exit(1);
}
switch(--m){
case 0:
m=O_RDONLY; break;
case 1:
m=O_WRONLY; break;
case 2:
m=O_RDWR; break;
}
int fd=open(fn,m);
if(fd<0){
printf("Unable to open %s for mode %s!\n",fn,mode);
exit(1);
}
struct fpspec *fp,*fpo;
for(fp=&rroot;fp;fpo=fp,fp=fp->r){
if(fp->fd==0||fp->fd==fd){
fp->fd=fd;
fp->a=0; fp->b=0; fp->m=0;
return fp;
}
}
fp=(struct fpspec *)malloc(sizeof(struct fpspec));
if(!fp){
printf("Can't allocate memory for fpspec!\n");
exit(1);
}
fpo->r=fp;
fp->fd=fd;
fp->a=0; fp->b=0; fp->m=0;
fp->r=0;
return fp;
}
int fpgetc(struct fpspec *fp){
if(fp->m) return fp->u[--fp->m];
if(fp->a>=fp->b){
if(fp->fd<0) return -1;
fp->a=0;
fp->b=read(fp->fd,fp->c,BUFSZ);
}
if(fp->a<fp->b){
return fp->c[fp->a++];
}
return -1;
}
char *fpgets(char *s,int n,struct fpspec *fp){
int i=0;
--n;
for(i=0;i<n;i++){
int c=fpgetc(fp);
if(c<=0||c=='\n'||c=='\r'){
if(c<=0&&!i) return 0;
s[i]=0;
return s;
}
s[i]=c;
}
s[n]=0;
return s;
}
void fpugetc(int c,struct fpspec *fp){
if(fp->a>0) fp->c[--fp->a]=c;
else if(fp->m<UGBSZ) fp->u[fp->m++]=c;
else {
printf("Unget buffer overflow fpugetc!\n");
exit(1);
}
}
int fpputc(int c,struct fpspec *fp){
if(fp->fd<0) return -1;
char b=c;
return write(fp->fd,&b,1);
}
int fpclose(struct fpspec *fp){
return close(fp->fd);
}
int mydigit(int c){
if(c>='0'&&c<='9') return c-'0';
return -1;
}
char myletter(int c){
if(c>='A'&&c<='Z') return c-'A';
return -1;
}
char *getint(int *n,char *s){
*n=0;
for(;;){
int d=mydigit(*s);
if(d<0) return s;
*n=*n*10+d;
++s;
}
}
char *bparse(char *s){
if(!strncmp(s," ",3)) return s+3;
return s;
}
char *lparse(int *c,char *s){
if(s[0]=='['){
*c=myletter(s[1]);
if(*c>=0){
if(s[2]==']'){
return s+3;
}
}
}
return s;
}
struct dogll {
struct dogll *a,*b;
int x;
};
#define SMAX 10
struct dogll head[SMAX],tail[SMAX];
void llbins(struct dogll *l0,struct dogll *l1){
struct dogll *l2=l0->b;
l1->a=l0; l1->b=l2;
l2->a=l1; l0->b=l1;
}
void llains(struct dogll *l1,struct dogll *l2){
struct dogll *l0=l2->a;
l1->a=l0; l1->b=l2;
l2->a=l1; l0->b=l1;
}
void ddrem(struct dogll *l1){
struct dogll *l0=l1->a;
struct dogll *l2=l1->b;
l0->b=l2; l2->a=l0;
}
void cleanup(){
int i;
for(i=0;i<SMAX;i++){
struct dogll *l0=&head[i],*l1;
for(l0=l0->b;l0->b;l0=l1){
l1=l0->b; free(l0);
}
}
for(i=0;i<SMAX;i++){
head[i].b=&tail[i];
tail[i].a=&head[i];
}
}
char buf[128];
char *decode(){
int i;
for(i=0;i<SMAX;i++){
struct dogll *l0=&head[i];
l0=l0->b;
if(!l0->b) break;
buf[i]=l0->x+'A';
}
buf[i]=0;
return buf;
}
void doinit(struct fpspec *fp){
char *s,*t;
int c,i;
for(i=0;i<SMAX;i++){
head[i].b=&tail[i];
tail[i].a=&head[i];
}
for(;;){
s=fpgets(buf,128,fp);
if(!s) {
printf("Reached end before initializing\n");
exit(1);
}
for(i=0;i<SMAX;i++){
s=lparse(&c,t=s);
if(s>t){
struct dogll *l1=(struct dogll *)malloc(sizeof(struct dogll));
l1->x=c;
llains(l1,&tail[i]);
} else {
s=bparse(s);
}
if(s==t){
if(!strncmp(s," 1 ",3)){
s=fpgets(buf,128,fp);
}
return;
}
if(*s==' ') s++;
if(!*s) break;
}
}
}
char *mstring(char *w,char *s){
int n=strlen(w);
if(!strncmp(w,s,n)) return s+n;
printf("Unable to match %s starting %s\n",w,s);
exit(1);
}
void pmove(int *n,int *f,int *t,char *s){
s=mstring("move ",s);
s=getint(n,s);
s=mstring(" from ",s);
s=getint(f,s); --(*f);
s=mstring(" to ",s);
s=getint(t,s); --(*t);
}
void part1(char *fn){
struct fpspec *fp=fpopen(fn,"r");
if(!fp){
printf("Unable to open %s for reading!\n",fn);
exit(1);
}
doinit(fp);
char *s;
for(;;){
int j,n,f,t;
s=fpgets(buf,128,fp);
if(!s) break;
pmove(&n,&f,&t,s);
for(j=0;j<n;j++){
struct dogll *l1=head[f].b;
ddrem(l1);
llbins(&head[t],l1);
}
}
printf("Part 1 The reversed crates are %s\n",decode());
cleanup();
fpclose(fp);
}
void part2(char *fn){
struct fpspec *fp=fpopen(fn,"r");
if(!fp){
printf("Unable to open %s for reading!\n",fn);
exit(1);
}
doinit(fp);
char *s;
for(;;){
int j,n,f,t;
s=fpgets(buf,128,fp);
if(!s) break;
pmove(&n,&f,&t,s);
if(f==t) continue;
struct dogll *l2=head[t].b;
for(j=0;j<n;j++){
struct dogll *l1=head[f].b;
ddrem(l1);
llains(l1,l2);
}
}
printf("Part 2 The correct crates are %s\n",decode());
cleanup();
fpclose(fp);
}
void dowork(){
char *fn="day05.txt";
part1(fn);
part2(fn);
}
int main(){
printf("Advent of Code 2022 Day 5 Camp Cleanup\n\n");
tic();
dowork();
printf("\nTotal execution time %g seconds.\n",toc());
return 0;
}
Someone bought up all the dog treats and is scalping them on Amazon. At 346 lines of code I hope the dog developer does not expect to get paid per line.
