AOC 2020 Day 1 in CBM Basic

I implemented the Advent of Code 2020 Day 1 challenge in CBM BASIC on a real Commodore 64. I haven't done anything in Basic in a long time, and probably never did anything actually meaningful with it. Part 1 of the challenge was to take a list of numbers, find the two that summed to 2020, and then multiply those two numbers together. Part two was to perform part 1 but with three numbers instead of two.

Now I wanted to actually write the code on the Commodore 64 itself, but I gave myself some leniency. Instead of manually typing in all 200 entries of input data (and inevitably making a breaking mistake) I used Vim on my PC to format the DATA entries at the start of the code. I then dropped that onto a 1541 disk image, plopped it on an SD card, and used my SD2IEC to mount the SD card's image on the Commodore. The rest of the programming was done on the Commodore itself.

Here is my solution for Day 1 Part 1:

	  
10 DATA 1686,  1983,  1801, 1890, 1910, 1722, 1571, 1952, 1602, 1551, 1144
11 DATA 1208,  1335,  1914, 1656, 1515, 1600, 1520, 1683, 1679, 1800, 1889
12 DATA 1717,  1592,  1617, 1756, 1646, 1596, 1874, 1595, 1660, 1748, 1946
13 DATA 1734,  1852,  2006, 1685, 1668, 1607, 1677, 403 , 1312, 1828, 1627
14 DATA 1925,  1657,  1536, 1522, 1557, 1636, 1586, 1654, 1541, 1363, 1844
15 DATA 1951,  1765,  1872, 696,  1764, 1718, 1540, 1493, 1947, 1786, 1548
16 DATA 1981,  1861,  1589, 1707, 1915, 1755, 1906, 1911, 1628, 1980, 1986
17 DATA 1780,  1645,  741 , 1727, 524 , 1690, 1732, 1956, 1523, 1534, 1498
18 DATA 1510,  372 ,  1777, 1585, 1614, 1712, 1650, 702 , 1773, 1713, 1797
19 DATA 1691,  1758,  1973, 1560, 1615, 1933, 1281, 1899, 1845, 1752, 1542
20 DATA 1694,  1950,  1879, 1684, 1809, 1988, 1978, 1843, 1730, 1377, 1507
21 DATA 1506,  1566,  935 , 1851, 1995, 1796, 1900, 896 , 171,  1728, 1635
22 DATA 1810,  2003,  1580, 1789, 1709, 2007, 1639, 1726, 1537, 1976, 1538
23 DATA 1544,  1626,  1876, 1840, 1953, 1710, 1661, 1563, 1836, 1358, 1550
24 DATA 1112,  1832,  1555, 1394, 1912, 1884, 1524, 1689, 1775, 1724, 1366
25 DATA 1966,  1549,  1931, 1975, 1500, 1667, 1674, 1771, 1631, 1662, 1902
26 DATA 1970,  1864,  2004, 2010, 504 , 1714, 1917, 1907, 1704, 1501, 1812
27 DATA 1349,  1577,  1638, 1886, 1157, 1761, 1676, 1731, 2001, 1261, 1154
28 DATA 1769,  1529
100 DIM A(200)
110 FOR I=0TO199
120 READ A(I)
140 NEXT
150 FOR I=0TO199
160 B=A(I)
170 FOR J=0TO199
180 IF I=J THEN 210
190 C=A(J)
200 IF B+C=2020 THEN PRINT "!",B,C,B*C:STOP
210 NEXT J
220 NEXT I 
	  

I basically put all 200 numbers into data fields, and then defined an array large enough to read them into with DIM. Then I iterated over the array twice, checking each element against each other element to see if they summed to 2020. If they did, I printed them both and the product of the two found numbers and stopped further execution.

There weren't really any special tricks to this implementation except remembering that I shouldn't be checking whether a number could sum to 2020 with itself.

Then I got to move onto Part 2, and this is where things got interesting. Comparing any three numbers from the data meant the cognitively easiest way to solve the problem was a triple loop. This of course meant O(n^3) time, which the Commodore struggled with. I waited about an hour before I decided I could optimize just a little bit to speed up the search.

I figured that for three numbers to sum to 2020, they all had to be pretty small. Most likely they were most (if not all) three digits instead of four. So I figured I could sort the entry data to make the search finish probably near the start of the first layer of iteration. Keep in mind I didn't want to pre-sort the data, I wanted the Commodore to work with the same exact input set it had for Part 1. So I turned to the simplest sorting algorithm I could remember: bubble sort.

Here is my solution for Day 1 Part 2:

	  
10 DATA 1686,  1983,  1801, 1890, 1910, 1722, 1571, 1952, 1602, 1551, 1144
11 DATA 1208,  1335,  1914, 1656, 1515, 1600, 1520, 1683, 1679, 1800, 1889
12 DATA 1717,  1592,  1617, 1756, 1646, 1596, 1874, 1595, 1660, 1748, 1946
13 DATA 1734,  1852,  2006, 1685, 1668, 1607, 1677, 403 , 1312, 1828, 1627
14 DATA 1925,  1657,  1536, 1522, 1557, 1636, 1586, 1654, 1541, 1363, 1844
15 DATA 1951,  1765,  1872, 696,  1764, 1718, 1540, 1493, 1947, 1786, 1548
16 DATA 1981,  1861,  1589, 1707, 1915, 1755, 1906, 1911, 1628, 1980, 1986
17 DATA 1780,  1645,  741 , 1727, 524 , 1690, 1732, 1956, 1523, 1534, 1498
18 DATA 1510,  372 ,  1777, 1585, 1614, 1712, 1650, 702 , 1773, 1713, 1797
19 DATA 1691,  1758,  1973, 1560, 1615, 1933, 1281, 1899, 1845, 1752, 1542
20 DATA 1694,  1950,  1879, 1684, 1809, 1988, 1978, 1843, 1730, 1377, 1507
21 DATA 1506,  1566,  935 , 1851, 1995, 1796, 1900, 896 , 171,  1728, 1635
22 DATA 1810,  2003,  1580, 1789, 1709, 2007, 1639, 1726, 1537, 1976, 1538
23 DATA 1544,  1626,  1876, 1840, 1953, 1710, 1661, 1563, 1836, 1358, 1550
24 DATA 1112,  1832,  1555, 1394, 1912, 1884, 1524, 1689, 1775, 1724, 1366
25 DATA 1966,  1549,  1931, 1975, 1500, 1667, 1674, 1771, 1631, 1662, 1902
26 DATA 1970,  1864,  2004, 2010, 504 , 1714, 1917, 1907, 1704, 1501, 1812
27 DATA 1349,  1577,  1638, 1886, 1157, 1761, 1676, 1731, 2001, 1261, 1154
28 DATA 1769,  1529
100 DIM A(200)
110 FOR I=0TO199
120 READ A(I)
140 NEXT
141 GOSUB 300
150 FOR I=0TO199
160 B=A(I)
170 FOR J=0TO199
180 IF J=I THEN 250
190 C=A(J)
200 FOR K=0TO199
210 IF K=I OR K=J THEN 240
220 D=A(K)
230 IF B+C+D=2020 THEN PRINT "!",B,C,D,B*C*D:STOP
240 NEXT K
250 NEXT J
260 NEXT I
300 REM BUBBLE SORT
301 X=200
310 N=200
320 FOR I=0TON-2
330 FOR J=0TON-I-2
340 X=A(J):Y=A(J+1)
350 IF X>Y THEN A(J)=Y:A(J+1)=X
360 NEXT : NEXT
370 RETURN 
	  
	  

I added a subroutine starting on line 300 to perform a basic bubble sort on top of the original array of data. Now bubble sort isn't fast by any means, but the Commodore was able to finish it in a couple of minutes. And the results were worth it because the subsequent triple FOR-loop completed in another few minutes. My instinct was right and two of the solution numbers were triple-digit.

So there you have it, Advent of Code 2020 Day 1 in Commodore 64 Basic V2. You can run these samples on real hardware of course, or in an emulator. You can also run them with the cbmbasic interpreter, which is a neat native C64 Basic interpreter for modern architectures. (Oh and I tested my samples on cbmbasic and they finished instantaneously. It helps to have a thousands-of-times-faster processor.)

I was going to keep going with the challenge and finish them all in CBM basic for fun, but the Day 2 input data set was 1000 entries. No problem, I can just read them from a SEQ file. The only blocker I realized was the challenge requires string character counting, which I don't think there's a function for in CBM basic. Maybe I have to do a few PEEKs and POKEs to check memory locations for ASCII/PETSCII character codes. Or I could just put it off til next year :)