Advent of Code 2024
Happy new year! This year’s resolution is to blog a little more frequently, so I thought I’d start with a retrospective of last December’s Advent of Code. I chose Fortran as my language (mostly 77, with a couple of forrays into 90 when I needed recursion). During Advent I managed to gain 41 out of 50 stars – one fewer than last year when I coded in Pascal. I have two part 2 problems left to finish (three if you count the 50th star for completing the other 49) and three problems not yet started.
The notes I made for each problem on a daily basis are in my repository with the code, so I won’t repeat them here. Instead, I’ll focus on what I learned or rediscovered.
It’s a long time since I wrote code for a living (1997) and most of that was C, rather than Fortran. I think the first thing I learned or rediscovered was that although I like writing code, I’m not especially good at it. Rather like my writing, it tends to be a little on the verbose side and somewhat unstructured.
Having said that, I was pleased with a number of things I achieved during the month. For the first day I wrote a small insertion sort subroutine that I reused on a couple of occasions. It’s certainly not the most efficient sorting algorithm, but it was more than sufficient for the purpose of completing the puzzles.
SUBROUTINE INSORT(LIST,NUM)
C Slow but useful insertion sort
C LIST is returned with the first NUM elements sorted
C in ascending order
INTEGER LIST(*),NUM
INTEGER J,K,TEMP
DO 20 J=2,NUM
TEMP=LIST(J)
K=J-1
DO 10 WHILE ((LIST(K).GT.TEMP).AND.(K.GE.1))
LIST(K+1)=LIST(K)
K=K-1
10 CONTINUE
LIST(K+1)=TEMP
20 CONTINUE
RETURN
ENDOn day 1 I was using Fortran 66 style DO loops with labels and CONTINUE statements, by the end I was using the Fortran 77 ENDDO statement instead (The company I worked for in the 1980s tended to use more Fortran 66 than 77 and I guess old habits are difficult to break.) Even when I used Fortran 90 style recursion I stuck with fixed format code. Another old habit that’s difficult to break!
I found it less of a struggle than I was expecting to deal with some of the whacky formats that the input data is provided in. Eventually I remembered how to use internal read and write statements. These make manipulating input data a lot simpler than the character by character parsing I had to adopt with Pascal last year. If you look at my code you can see the progression from using that approach in the early puzzles to much more elegant input handing later on in the month. Another lesson learned – practice helps!
There were a couple of minor points I rediscovered about Fortran 77 – the first being that string handling is poor, so most of the stringier problems had their input converted to numbers and then back to characters if necessary for the answer. Day 23, The LAN party, is an example of this approach.
The difficulties of string handling are partly offset by the complex number type – very useful for handling coordinates. On Day 13, The claw, they were used for this purpose, combined with some complex arithmetic in part 1 to find distances between points. Very satisfying!
For day 18 I wrote a version of the A* path following algorithm that I subsequently reused on day 20. Day 18’s version uses a zero heuristic (so in effect implements the Dijkstra algorithm). Day 20’s uses a Manhattan distance heuristic, as well as reversing the closed node search order, both of which considerably improve performance. The code is still a little scruffy, but seemed easier to implement than last year’s Pascal version.
Day 20 part 2 was one of the more enjoyable problems for me, as I managed to improve the execution time from a disastrous 6+ hours to a couple of seconds once I’d properly understood what the puzzle was asking me to do! Another lesson – read the question.
The other day I really enjoyed was day 11 – the plutotian pebbles. The vast majority of solutions I saw were recursive, using memoization. As I was still clinging onto the Fortran 77 standard for grim death at this point in the month, I wrote an iterative solution that doesn’t take until the heat death of the universe to work through 75 generations, at the expense of some additional temporary storage requirements. I guess you could say that it uses memoization after a fashion as well.
It’s not the neatest or cleanest code, but it works, so I’ve reproduced it below in all of its gory f77 goodness.
Here’s looking forward to this year’s challenges!
PROGRAM DAY11P2
C
COMMON /ADVENT/ NOW,FUTURE
INTEGER*8 NOW(0:9999,0:1),FUTURE(0:9999,0:1)
C
INTEGER*8 LIST(8),LEFT,RIGHT,TOTAL
INTEGER IDX,ITER,NOWPTR,FUTPTR
CHARACTER*40 STR
C
10 FORMAT(A)
20 FORMAT(A)
30 FORMAT(A,I4,A,I17)
40 FORMAT(5I12)
50 FORMAT(A,I17)
C
WRITE(*,10)"Advent of Code 2024 day 11, part 2"
WRITE(*,10)" "
OPEN(10,FILE="day11in.txt",STATUS="OLD",FORM="FORMATTED",
+ ACCESS="SEQUENTIAL",ACTION="READ")
C Read the input line into a temporary string
READ(10,FMT=20,ERR=100,END=100) STR
100 CONTINUE
CLOSE(10)
C Convert string to integers
CALL STR2INTARRAY(STR,8,LIST,TOTAL)
C Copy the list into the NOW 2D array
DO IDX=0,TOTAL-1
NOW(IDX,0)=LIST(IDX+1)
NOW(IDX,1)=1
ENDDO
C Update the pointer to the last filled space
NOWPTR=TOTAL-1
C Set iteration count to 1
ITER=1
DO WHILE (ITER.LE.75)
FUTPTR=-1
DO IDX=0,NOWPTR
CALL RULES(NOW(IDX,0),LEFT,RIGHT)
C>> WRITE(*,40)IDX,NOW(IDX,0),LEFT,RIGHT
CALL INSERT(LEFT,NOW(IDX,1),FUTPTR)
IF (RIGHT.NE.-1) CALL INSERT(RIGHT,NOW(IDX,1),FUTPTR)
ENDDO
C>> WRITE(*,*)"======================================"
C Copy future list to now list for next iteration
NOW=FUTURE
NOWPTR=FUTPTR
C Calculate the total number of stones after iteration
TOTAL=0
DO IDX=0,NOWPTR
C>> WRITE(*,40)IDX,FUTPTR,NOW(IDX,0),NOW(IDX,1)
TOTAL=TOTAL+NOW(IDX,1)
ENDDO
WRITE(*,30)"Stones after",ITER," iterations is",TOTAL
C We've finished this iteration
ITER=ITER+1
ENDDO
WRITE(*,10)" "
WRITE(*,50)"Result is",TOTAL
END
C
SUBROUTINE INSERT(VALUE,COUNT,ENDPTR)
INTEGER*8 VALUE,COUNT
INTEGER ENDPTR
C
COMMON /ADVENT/ NOW,FUTURE
INTEGER*8 NOW(0:9999,0:1),FUTURE(0:9999,0:1)
C
INTEGER IDX
C
DO IDX=0,ENDPTR
IF (FUTURE(IDX,0).EQ.VALUE) THEN
C We've already seen this value, increment count and exit
FUTURE(IDX,1)=FUTURE(IDX,1)+COUNT
GOTO 999
ENDIF
ENDDO
C New value, add 1 to the pointer to the end of the list
ENDPTR=ENDPTR+1
C and add the value to the end of the list, set count
FUTURE(ENDPTR,0)=VALUE
FUTURE(ENDPTR,1)=COUNT
C
999 CONTINUE
RETURN
END
C
SUBROUTINE RULES(VALUE,LEFT,RIGHT)
INTEGER*8 VALUE,LEFT,RIGHT
INTEGER DIGITS,NUMDIGITS
C
IF (VALUE.EQ.0) THEN
LEFT=1
RIGHT=-1
GOTO 999
ENDIF
C
DIGITS=NUMDIGITS(VALUE)
IF (MOD(DIGITS,2).EQ.0) THEN
LEFT=VALUE/(10**(DIGITS/2))
RIGHT=MOD(VALUE,(10**(DIGITS/2)))
ELSE
LEFT=VALUE*2024
RIGHT=-1
ENDIF
C
999 CONTINUE
RETURN
END
C
INTEGER FUNCTION NUMDIGITS(N)
INTEGER*8 N
INTEGER*8 TEST
C
TEST=N
NUMDIGITS=0
DO WHILE (TEST.GT.0)
TEST=TEST/10
NUMDIGITS=NUMDIGITS+1
ENDDO
C
RETURN
END
C
SUBROUTINE STR2INTARRAY(STR,MAXL,LIST,ELEMENTS)
CHARACTER*(*) STR
INTEGER MAXL
INTEGER*8 LIST(*), ELEMENTS
C
C Separates a list of MAXL integers stored in STR into the
C array LIST. The number of consecutive elements read from
C the start of the list is returned in ELEMENTS
C
C This method assumes STR does NOT start with a blank when
C passed to this subroutine, as blank in position 1 = end of
C string of values to parse OR if we're going to overflow
C the integer array (ELEMENTS values found = MAXL)
C
C Note that STR is destroyed by this subroutine!
C
INTEGER IDX
C Format assumes values in range -9,999,999 .. 99,999,999
5 FORMAT(I8)
C Zero the return array
DO 10 IDX=1,MAXL
LIST(IDX)=0
10 CONTINUE
C
ELEMENTS=0
100 CONTINUE
IDX=INDEX(STR,' ')
IF ((IDX.EQ.1).OR.(ELEMENTS.EQ.MAXL)) GOTO 999
C We have an integer value, put it in the next array element
ELEMENTS=ELEMENTS+1
READ(STR(1:IDX-1),5) LIST(ELEMENTS)
C And truncate the front of the string for the next value
STR(1:)=STR(IDX+1:)
GOTO 100
999 CONTINUE
RETURN
END