Can you do Advent of Code on 8-Bit Machines?

Can you do Advent of Code on 8-Bit Machines?
Photo by Nick Fewings / Unsplash

There's a wonderful yearly online event called Advent Of Code (#adventofcode). Each day there are two code challenges that follow a holiday narrative. Some of them are easy, and some of them are quite difficult.

This year I've attempted to do as much of it as I can on 8-Bit Machines. Mostly Commodore 64 because it's what I know the best, and also what I like most to actually code on.

I've been posting them on Twitter on and off.

These code puzzles challenge my thinking and reasoning. The fact that they are holiday-themed and just plain fun makes them a must-do in December for many.

But how suitable are these old 8-Bit machines I love for this kind of task?

The answer is... well kinda suitable. Sometimes.

I've managed to complete around 60% of the challenges so far on 8 Bit machines. For the rest, I've "resorted" to Python on my MacBook Pro. Or my TI Nspire, just because.

Here are both parts of Day 8 on a Commodore PET (yay 1970s!!):

Some of the answers require a lot of memory, which we can get around by loading the data dynamically most of the time. But some of them require counts and calculations in the billions.  This is where the 1Mhz (give or take) family of 70s and 80s machines really struggle.

Day 7 was not gonna work on 40 year old hardware

My answer for Advent of Code Day 7 part two, which I did in Python was WAAAY too large for a 1Mzh machine.

My estimate for this to complete on a commodore was 23 DAYS

Counting large numbers

My beloved Commodore 64 runs a 6502 processor variant at just over 1Mhz. So numbers that get large like 224 take quite a while just to COUNT to. Even 216 in BASIC takes more than a minute just to loop through and not even do anything in each loop.

How long does 224 take just to count to? Let's find out.

If you're at all familiar with BASIC, you can even just use a stopwatch to find that

10 FOR I=0 TO 65535:NEXT

takes almost a minute and a half to complete. And that's only 216 !!

A small performance gain by blanking the screen

We CAN blank the screen on the Commodore 64 and get a little bit of a performance boost. The VIC chip steals cycles from the CPU so stopping the screen drawing will give us a little bit of a performance gain. This doesn't matter on a PET, VIC-20, or something like the Apple II, but on the C64, you get a couple of percentage points of performance over long loops.

We've gone over this in previous posts, but if you're not familiar we need to toggle bit 4 on register $D011 in hex or 53265 in decimal.

We can AND it with $EF / 239 to turn that bit off and OR it with $10 / 16 to turn it back on.

POKE 53265,PEEK(53265)AND 239 :REM SCREEN OFF

POKE 53265,PEEK(53265)OR 16 :REM SCREEN ON
;screen off
LDA $D011
AND #$EF
STA $D011

;screen on

LDA $D011
OR  #$10
STA $D011

Let's do it in BASIC and Assembly in a reasonable fashion

A "tidy" program to check these all at once would be something like:

10 FORJ=828TO910:READX:POKEJ,X:NEXT
15 PRINTCHR$(147);:PRINTCHR$(18);"  COMMODORE 64 COUNTING LARGE NUMBERS   "
20 TI$="000000"
25 PRINT:PRINT"COUNT TO 2^24 IN M/L..."
30 POKE251,0:POKE252,0:POKE253,0
40 SYS828
50 PRINTPEEK(251),PEEK(252),PEEK(253)
60 PRINT"TOOK"TI/60/60"MINUTES":PRINT
70 TI$="000000"
75 PRINT"COUNT TO 2^24 IN M/L SCREEN BLANKED..."
80 POKE251,0:POKE252,0:POKE253,0
85 POKE53265,PEEK(53265)AND239
90 SYS828
95 POKE53265,PEEK(53265)OR16
100 PRINTPEEK(251),PEEK(252),PEEK(253)
110 PRINT"TOOK"TI/60/60"MINUTES":PRINT
120 PRINT"COUNT TO 2^16 IN BASIC..."
130 TI$="000000"
140 FORI=0TO65535:NEXT
150 PRINT"TOOK"TI/60/60"MINUTES":PRINT
170 PRINT"COUNT TO 2^16 IN BASIC SCREEN BLANKED..."
180 TI$="000000"
190 POKE53265,PEEK(53265)AND239
200 FORI=0TO65535:NEXT
210 POKE53265,PEEK(53265)OR16
220 PRINT"TOOK"TI/60/60"MINUTES"
499 END
500 DATA 169,1,133,251,133,252,133,253,169,0,162,0,24,165,251
501 DATA 105,1,133,251,144,16,165,252,105,0,133,252,144,8,165
502 DATA 253,105,0,133,253,201,255,208,229,165,253,201,255
503 DATA 240,8,24,105,1,133,253,76,101,3,165,252,201,255,240
504 DATA 8,24,105,1,133,252,76,115,3,165,251,201,255,240,8
505 DATA 24,105,1,133,251,76,129,3,96,0

The assembly part "disassembled" is:

         *= $033c


result = $fb
       
         lda #0
         sta result
         sta result+1
         sta result+2

         .block
counter
         lda #$00

loop
         clc
         lda result
         adc #1
         sta result
         bcc ahead3
         lda result+1
         adc #$00
         sta result+1
         bcc ahead3
         lda result+2
         adc #$00
         sta result+2

         cmp #$ff
ahead3
         bne loop

         lda result+2
remain2  cmp #$ff
         beq ahead2
         clc
         adc #1
         sta result+2
         jmp remain2
ahead2


         lda result+1
remain1  cmp #$ff
         beq ahead1
         clc
         adc #1
         sta result+1
         jmp remain1
ahead1
         lda result
remain   cmp #$ff
         beq ahead
         clc
         adc #1
         sta result
         jmp remain
ahead

        rts
         .bend



So how long does it take just to count to 16 million anyway?

A while. And the machine language parts are just adding 1 to a Zero page address. In 2021 we're pretty spoiled with the compute power we have at our fingertips.

Relax!

I know, you're an assembly wizard and this could be faster. I'm already impressed.

So go and fix it ;-)

So the sorta-kinda answer to suitability makes sense

I think 14 days into it, 60% of 28 code tasks really designed with modern computers in mind is pretty respectable. It's been great fun to try and get these to work on old machines.

Even when I need to resort to 2.6Ghz and 16GB of RAM, it's still fun and I can't recommend this Advent of Code site enough.

Extra Credit Larger?

224 in BASIC takes a while...

and just for fun, PAL VIC-20

What about 232 ?

I happen to know that this same Machine Language routine with a byte added to count to 232 takes around 20 hours. I did it for the Terminator article research. You know, for science!