Can you do Advent of Code on 8-Bit Machines?
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!!):
Part 1
Part 2
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 2^24 take quite a while just to COUNT to. Even 2^16 in BASIC takes more than a minute just to loop through and not even do anything in each loop.
How long does 2^24 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 2^16 !!
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?
2^24 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 2^32 takes around 20 hours. I did it for the Terminator article research. You know, for science!