I'm a Staff Software Engineer at Cisco. I specialize in Python and Go, building functional, practical, and maintainable web systems leveraging Kubernetes and the cloud. Blog opinions are my own.
This one went surprisingly well! Still really fast, which I'm loving. And I got to make some more involved macros, which is fun.
Day11.h:
#ifndef AOC2020_DAY11_H
#define AOC2020_DAY11_H
#include <stdbool.h>
#include <stdlib.h>
#include "parsing.h"
/// Potential options for a seattypedefenum{SEAT_FLOOR,///< Seat goneSEAT_EMPTY,///< No one in seatSEAT_FULL,///< Seat occupied}SeatType;/// A grid of seats (1D, but to be indexed as 2D)typedefstruct{GridSizesize;SeatType*cells;}Grid;Grid*parse(constchar*filename);intpart1(constchar*filename);boolfirst_visible_full(SeatType*cells,intx,inty,intwidth,intheight,intxdir,intydir);intpart2(constchar*filename);intday11(void);#endif
Day11.c:
#include "Day11.h"
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
#include "parsing.h"
/// Parse the input file, a 2D grid of '.', '#', or 'L'.Grid*parse(constchar*filename){FILE*fp;fp=fopen(filename,"r");if(fp==NULL){printf("Couldn't open the file!\n");exit(EXIT_FAILURE);}GridSizesize=measure_grid(fp);SeatType*cells=(SeatType*)malloc(sizeof(SeatType)*size.height*size.width);for(inty=0;y<size.height;y++){for(intx=0;x<size.width;x++){switch(getc(fp)){case'.':cells[y*size.width+x]=SEAT_FLOOR;break;case'L':cells[y*size.width+x]=SEAT_EMPTY;break;case'#':cells[y*size.width+x]=SEAT_FULL;break;default:printf("Bad char.\n");exit(EXIT_FAILURE);}}getc(fp);// Burn newline}fclose(fp);Grid*grid=(Grid*)malloc(sizeof(Grid));grid->size=size;grid->cells=cells;returngrid;}/// Free a grid's memorystaticvoidfree_grid(Grid*grid){free(grid->cells);free(grid);}/// Change a grid one timestep based on the rules from part 1////// 1. An empty seat with no occupied seats around it gets filled./// 2. A full seat with >= 4 occupied neighbors gets departed./// 3. Floor... floor never changes.staticboolevolve_grid(Grid*grid){boolchanged=false;SeatTypenew_cells[grid->size.height*grid->size.width];SeatType*cells=grid->cells;GridSizesize=grid->size;/// Check if a given x, y coordinate seat is occupied#define FULL(_x, _y) (cells[(_y)*size.width + _x] == SEAT_FULL)
for(inty=0;y<grid->size.height;y++){for(intx=0;x<grid->size.width;x++){intidx=y*size.width+x;if(cells[idx]==SEAT_FLOOR){new_cells[idx]=SEAT_FLOOR;// Floor never changes, short circuitcontinue;}intoccupied=0;if(y>0&&FULL(x,y-1))occupied++;if(y<size.height-1&&FULL(x,y+1))occupied++;if(x>0&&FULL(x-1,y))occupied++;if(x<size.width-1&&FULL(x+1,y))occupied++;if(y>0&&x>0&&FULL(x-1,y-1))occupied++;if(y>0&&x<size.width-1&&FULL(x+1,y-1))occupied++;if(y<size.height-1&&x>0&&FULL(x-1,y+1))occupied++;if(y<size.height-1&&x<size.width-1&&FULL(x+1,y+1))occupied++;if(cells[idx]==SEAT_EMPTY&&occupied==0){new_cells[idx]=SEAT_FULL;changed=true;}elseif(cells[idx]==SEAT_FULL&&occupied>=4){new_cells[idx]=SEAT_EMPTY;changed=true;}else{new_cells[idx]=cells[idx];}}}#undef FULL
memcpy(grid->cells,new_cells,sizeof(SeatType)*size.width*size.height);returnchanged;}/// Check to see if the first visible chair in a given direction is full or not./// Skip over floor spaces, and stop at the edge of the grid.boolfirst_visible_full(SeatType*cells,intx,inty,intwidth,intheight,intxdir,intydir){intpx=x+xdir;intpy=y+ydir;SeatTypeval=SEAT_FLOOR;while(px>=0&&py>=0&&px<width&&py<height&&(val=cells[py*width+px])==SEAT_FLOOR){px+=xdir;py+=ydir;}return(val==SEAT_FULL);}/// Change a grid one timestep based on the rules from part 2////// 1. An empty seat with no occupied seats around it gets filled./// 2. A full seat with >= 5 occupied neighbors gets departed./// 3. Floor... floor never changes.////// For this one, "around it" means the first seat in that direction/// that isn't floor.staticboolevolve_grid2(Grid*grid){boolchanged=false;SeatTypenew_cells[grid->size.height*grid->size.width];SeatType*cells=grid->cells;GridSizesize=grid->size;/// Convenience macro for checking first_visible_full in a given direction#define SEE_FULL(xdir, ydir) \
(first_visible_full(cells, x, y, size.width, size.height, xdir, ydir))
for(inty=0;y<grid->size.height;y++){for(intx=0;x<grid->size.width;x++){intidx=y*size.width+x;if(cells[idx]==SEAT_FLOOR){new_cells[idx]=SEAT_FLOOR;// Floor never changescontinue;}intoccupied=0;if(SEE_FULL(-1,-1))occupied++;if(SEE_FULL(-1,0))occupied++;if(SEE_FULL(-1,1))occupied++;if(SEE_FULL(0,-1))occupied++;if(SEE_FULL(0,1))occupied++;if(SEE_FULL(1,-1))occupied++;if(SEE_FULL(1,0))occupied++;if(SEE_FULL(1,1))occupied++;if(cells[idx]==SEAT_EMPTY&&occupied==0){new_cells[idx]=SEAT_FULL;changed=true;}elseif(cells[idx]==SEAT_FULL&&occupied>=5){new_cells[idx]=SEAT_EMPTY;changed=true;}else{new_cells[idx]=cells[idx];}}}#undef SEE_FULL
memcpy(grid->cells,new_cells,sizeof(SeatType)*size.width*size.height);returnchanged;}/*
static void print_grid(Grid* grid) {
printf("\n");
for (int y = 0; y < grid->size.height; y++) {
for (int x = 0; x < grid->size.width; x++) {
switch (grid->cells[y * grid->size.width + x]) {
case SEAT_EMPTY: printf("L"); break;
case SEAT_FLOOR: printf("."); break;
case SEAT_FULL: printf("#"); break;
default: printf("Bad seat type.\n"); exit(EXIT_FAILURE);
}
}
printf("\n");
}
}
*//// Part one, how many seats occupied after steady state/// given the rules above?intpart1(constchar*filename){Grid*grid=parse(filename);while(evolve_grid(grid)){}intoccupied=0;intsize=grid->size.height*grid->size.width;for(inti=0;i<size;i++){if(grid->cells[i]==SEAT_FULL)occupied++;}free_grid(grid);returnoccupied;}/// Part two, how many seats occupied after steady state given/// the rules above?intpart2(constchar*filename){Grid*grid=parse(filename);while(evolve_grid2(grid)){}intoccupied=0;intsize=grid->size.height*grid->size.width;for(inti=0;i<size;i++){if(grid->cells[i]==SEAT_FULL)occupied++;}free_grid(grid);returnoccupied;}/// Run both partsintday11(){printf("====== Day 11 ======\n");printf("Part 1: %d\n",part1("data/day11.txt"));printf("Part 2: %d\n",part2("data/day11.txt"));returnEXIT_SUCCESS;}
COBOL, Friday night means I had time to do both parts.
IDENTIFICATION DIVISION.
PROGRAM-ID. AOC-2020-11-2.
AUTHOR. ANNA KOSIERADZKA.
ENVIRONMENT DIVISION.
INPUT-OUTPUT SECTION.
FILE-CONTROL.
SELECT INPUTFILE ASSIGN TO "d11.input"
ORGANIZATION IS LINE SEQUENTIAL.
DATA DIVISION.
FILE SECTION.
FD INPUTFILE.
01 INPUTRECORD PIC X(99).
WORKING-STORAGE SECTION.
01 FILE-STATUS PIC 9 VALUE 0.
01 WS-ARR OCCURS 93 TIMES.
05 WS-ROW PIC X OCCURS 98 TIMES.
01 WS-ARR-2 OCCURS 93 TIMES.
05 WS-ROW-2 PIC X OCCURS 98 TIMES.
01 DI PIC S9 VALUE 0.
01 DJ PIC S9 VALUE 0.
LOCAL-STORAGE SECTION.
01 N-ROWS UNSIGNED-INT VALUE 93.
01 N-COLS UNSIGNED-INT VALUE 98.
01 K-MAX UNSIGNED-INT VALUE 98.
01 I UNSIGNED-INT VALUE 1.
01 J UNSIGNED-INT VALUE 1.
01 K UNSIGNED-INT VALUE 1.
01 X UNSIGNED-INT VALUE 1.
01 Y UNSIGNED-INT VALUE 1.
01 OCCUPIED-ADJACENT UNSIGNED-INT VALUE 0.
01 OCCUPIED UNSIGNED-INT VALUE 0.
01 CHANGES UNSIGNED-INT VALUE 0.
PROCEDURE DIVISION.
001-MAIN.
OPEN INPUT INPUTFILE.
PERFORM 002-READ UNTIL FILE-STATUS = 1.
CLOSE INPUTFILE.
PERFORM 004-ONE-ROUND WITH TEST AFTER UNTIL CHANGES = 0.
PERFORM 008-COUNT-OCCUPIED.
DISPLAY OCCUPIED.
STOP RUN.
002-READ.
READ INPUTFILE
AT END MOVE 1 TO FILE-STATUS
NOT AT END PERFORM 003-PROCESS-LINE
END-READ.
003-PROCESS-LINE.
MOVE INPUTRECORD TO WS-ARR(I).
ADD 1 TO I.
004-ONE-ROUND.
MOVE 0 TO CHANGES.
PERFORM VARYING I FROM 1 BY 1 UNTIL I > N-ROWS
MOVE WS-ARR(I) TO WS-ARR-2(I)
END-PERFORM.
PERFORM VARYING I FROM 1 BY 1 UNTIL I > N-ROWS
AFTER J FROM 1 BY 1 UNTIL J > N-COLS
PERFORM 005-PROCESS-SEAT
END-PERFORM.
005-PROCESS-SEAT.
* - If a seat is empty (L) and there are no occupied seats
* adjacent to it, the seat becomes occupied.
* - If a seat is occupied (#) and four or more seats adjacent to
* it are also occupied, the seat becomes empty.
* - Otherwise, the seat's state does not change.
IF WS-ROW(I, J) = '.' THEN
EXIT PARAGRAPH
END-IF.
PERFORM 006-COUNT-OCCUPIED-ADJACENT.
IF WS-ROW(I, J) = 'L' AND OCCUPIED-ADJACENT = 0 THEN
MOVE '#' TO WS-ROW(I, J)
ADD 1 TO CHANGES
END-IF.
IF WS-ROW(I, J) = '#' AND OCCUPIED-ADJACENT > 4 THEN
MOVE 'L' TO WS-ROW(I, J)
ADD 1 TO CHANGES
END-IF.
006-COUNT-OCCUPIED-ADJACENT.
MOVE 0 TO OCCUPIED-ADJACENT.
PERFORM VARYING DI FROM -1 BY 1 UNTIL DI > 1
AFTER DJ FROM -1 BY 1 UNTIL DJ > 1
PERFORM 007-COUNT-OCCUPIED-ADJACENT-IN-DIRECTION
END-PERFORM.
IF WS-ROW-2(I, J) = '#' THEN
SUBTRACT 1 FROM OCCUPIED-ADJACENT
END-IF.
007-COUNT-OCCUPIED-ADJACENT-IN-DIRECTION.
PERFORM VARYING K FROM 1 BY 1 UNTIL K > K-MAX
COMPUTE X = I + K * DI
COMPUTE Y = J + K * DJ
IF X < 1 OR Y < 1 OR X > N-ROWS OR Y > N-COLS THEN
EXIT PERFORM
END-IF
IF WS-ROW-2(X, Y) = 'L' THEN
EXIT PERFORM
END-IF
IF WS-ROW-2(X, Y) = '#' THEN
ADD 1 TO OCCUPIED-ADJACENT
EXIT PERFORM
END-IF
END-PERFORM.
008-COUNT-OCCUPIED.
MOVE 0 TO OCCUPIED.
PERFORM VARYING I FROM 1 BY 1 UNTIL I > N-ROWS
AFTER J FROM 1 BY 1 UNTIL J > N-COLS
IF WS-ROW(I, J) = '#' THEN
ADD 1 TO OCCUPIED
END-IF
END-PERFORM.
Bit late today as I had to do yesterday first, due to teaching commitments and just to tired to sit down at 10pm to work on it yesterday :-)
Anyway, my first solution, which I won't post here, was very (very) slow, using just lists. So after see looking at comments reddit replaced lists with Map, with the key being the 2D index, it worked out pretty well. Of course, it would have been a lost faster in Rust or C++, just to two arrays, one for the current step, and one for the next, updating in place, and simply switching each step. However I'm trying to do as many of these using Haskell, as most of my other days use Rust and C++ and it's been fun returning to Haskell after quite a while. I feel I've learnt a lot just over these last few days, which always sees like a good outcome. Enough chat, my solution:
data=open("input10.txt","r").read().strip().split("\n")data=[list(row)forrowindata]defcount_adj_visible(row,col,prev,part1=False):s=0forrinc,colincin[(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]:r=rowc=colwhileTrue:r=r+rincc=c+colincif(r<0orr>=len(prev))or(c<0orc>=len(prev[row])orprev[r][c]=="L"):breakif(prev[r][c]=="#"):s+=1breakif(part1):breakreturnsdefsolve(table,part1=False):table=[row.copy()forrowintable]whileTrue:prev=[row.copy()forrowintable]forrowinrange(len(table)):forcolinrange(len(table[row])):if(table[row][col]!="."):n=count_adj_visible(row,col,prev,part1)if(n==0andprev[row][col]=="L"):table[row][col]="#"if(n>=(4ifpart1else5)andprev[row][col]=="#"):table[row][col]="L"if(prev==table):breakreturn"\n".join(["".join(row)forrowintable]).count("#")print("part 1 ans =",solve(data,part1=True))print("part 2 ans =",solve(data))
As the seats don't move, one can probably optimize the code by precomputing the neighbouring or visible seats, but waiting for 4 seconds was not boring enough for me to try it. So, I just count the number of adjacent or visible seats for each seat and then update the seating map.
Part 1:
Part 2:
Lots of code in this one, TIL about creating my generative iterators in Rust. Made me feel smart :). Boring parsing code is redacted. Full stuff on: github.com/benwtrent/advent-of-cod...
Well I had a little time while rewatching Buffy this evening with the kids and inspired by E. Choroba, I wrote a very (very) simple C++ program to generate an annimated GIF showing the process of set allocation. It uses the single header GIF library:
The input is a file which has the width and height on the first two lines, followed by the grid for each step. For example, the example given in the AOC description for today:
packagemainimport("bufio""fmt""os""strings""time""unicode/utf8")funcmain(){start:=time.Now()reader:=getInput("day11")grid:=[][]rune{}count:=1// get input and format it to [][]runeforline:=rangereader{iflen(grid)==0{grid=append(grid,[]rune{})for_,r:=rangestrings.Repeat(".",utf8.RuneCountInString(line)+2){grid[0]=append(grid[0],r)}}grid=append(grid,[]rune{})line="."+line+"."for_,r:=rangeline{grid[count]=append(grid[count],r)}count++}grid=append(grid,[]rune{})for_,r:=rangestrings.Repeat(".",len(grid[0])){grid[count]=append(grid[count],r)}gofunc(){resultPartOne:=partOne(copySliceSlice(grid))fmt.Printf("Puzzle 1 result: %d\n",resultPartOne)}()resultPartTwo:=partTwo(grid)fmt.Printf("Puzzle 2 result: %d\n",resultPartTwo)elapsed:=time.Since(start)fmt.Println("Run took:",elapsed)}funcpartOne(grid[][]rune)int{deepCopy:=copySliceSlice(grid)changeCoutner:=-1forchangeCoutner!=0{changeCoutner=0fory:=0;y<len(grid);y++{forx:=0;x<len(grid[y]);x++{ifgrid[y][x]=='#'{ifcheckAdjacent(deepCopy,y,x)>=4{changeCoutner++grid[y][x]='L'}}elseifgrid[y][x]=='L'{ifcheckAdjacent(deepCopy,y,x)==0{changeCoutner++grid[y][x]='#'}}}}ifchangeCoutner>0{deepCopy=copySliceSlice(grid)}}returngetOccupiedSeats(grid)}funccheckAdjacent(grid[][]rune,y,xint)int{positionsToCheck:=[][]int{{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}}hitCount:=0for_,pos:=rangepositionsToCheck{ifgrid[y+pos[0]][x+pos[1]]=='#'{hitCount++}}returnhitCount}funcpartTwo(grid[][]rune)int{deepCopy:=copySliceSlice(grid)changeCoutner:=-1forchangeCoutner!=0{changeCoutner=0fory:=0;y<len(grid);y++{forx:=0;x<len(grid[y]);x++{ifgrid[y][x]=='#'{ifcheckAdjacentPartTwo(deepCopy,y,x)>=5{changeCoutner++grid[y][x]='L'}}elseifgrid[y][x]=='L'{ifcheckAdjacentPartTwo(deepCopy,y,x)==0{changeCoutner++grid[y][x]='#'}}}}ifchangeCoutner>0{deepCopy=copySliceSlice(grid)}}returngetOccupiedSeats(grid)}funccheckAdjacentPartTwo(grid[][]rune,y,xint)int{positionsToCheck:=[][]int{{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}}hitCount:=0rows:=len(grid)colums:=len(grid[0])for_,pos:=rangepositionsToCheck{yToCheck:=y+pos[0]xToCheck:=x+pos[1]for(yToCheck>=0&&yToCheck<rows)&&(xToCheck>=0&&xToCheck<colums){ifgrid[yToCheck][xToCheck]=='#'{hitCount++ifhitCount==5{returnhitCount}break}elseifgrid[yToCheck][xToCheck]=='L'{break}yToCheck+=pos[0]xToCheck+=pos[1]}}returnhitCount}funccopySliceSlice(grid[][]rune)[][]rune{copyOfgrid:=make([][]rune,len(grid))fori:=0;i<len(grid);i++{sliceCopy:=make([]rune,len(grid[i]))copy(sliceCopy,grid[i])copyOfgrid[i]=sliceCopy}returncopyOfgrid}funcgetOccupiedSeats(grid[][]rune)int{counter:=0for_,row:=rangegrid{for_,r:=rangerow{ifr=='#'{counter++}}}returncounter}funcgetInput(pathstring)<-chanstring{c:=make(chanstring)gofunc(){file,err:=os.Open(path)iferr!=nil{panic("error in reading file: "+err.Error())}// scan filescanner:=bufio.NewScanner(file)forscanner.Scan(){c<-scanner.Text()}close(c)}()returnc}
Unfortunately I still have a runtime in total of round about 120ms.
Do you have any suggestions for a performance enhancement?
Oops, forgot to post yesterday. Pleased with how this one turned out, especially the unit tests.
This one went surprisingly well! Still really fast, which I'm loving. And I got to make some more involved macros, which is fun.
Day11.h:
Day11.c:
I used Haskell. Definitely not the most efficient or optimized solution:
COBOL, Friday night means I had time to do both parts.
Bit late today as I had to do yesterday first, due to teaching commitments and just to tired to sit down at 10pm to work on it yesterday :-)
Anyway, my first solution, which I won't post here, was very (very) slow, using just lists. So after see looking at comments reddit replaced lists with Map, with the key being the 2D index, it worked out pretty well. Of course, it would have been a lost faster in Rust or C++, just to two arrays, one for the current step, and one for the next, updating in place, and simply switching each step. However I'm trying to do as many of these using Haskell, as most of my other days use Rust and C++ and it's been fun returning to Haskell after quite a while. I feel I've learnt a lot just over these last few days, which always sees like a good outcome. Enough chat, my solution:
python solution for both part 1 and 2
As the seats don't move, one can probably optimize the code by precomputing the neighbouring or visible seats, but waiting for 4 seconds was not boring enough for me to try it. So, I just count the number of adjacent or visible seats for each seat and then update the seating map.

Part 1:
Part 2:
Lots of code in this one, TIL about creating my generative iterators in Rust. Made me feel smart :). Boring parsing code is redacted. Full stuff on: github.com/benwtrent/advent-of-cod...
Well I had a little time while rewatching Buffy this evening with the kids and inspired by E. Choroba, I wrote a very (very) simple C++ program to generate an annimated GIF showing the process of set allocation. It uses the single header GIF library:
The input is a file which has the width and height on the first two lines, followed by the grid for each step. For example, the example given in the AOC description for today:
Ruby. Initially assumed a toroidal grid and wasted a huge amount of time in the process. Part 1:
Part 2:
OOP in Ruby; I enjoyed writing this!
Hi guys!
I tried the problem with go.
Unfortunately I still have a runtime in total of round about 120ms.
Do you have any suggestions for a performance enhancement?
Best regards
My JavaScript walkthrough: