1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
|
<?php
$title = "AOC 2020 Day 1 in CBM Basic";
if (isset($early) && $early) {
return;
}
include($_SERVER['DOCUMENT_ROOT'] . '/includes/head.php');
?>
<p class="description">
I implemented the
<a href="https://adventofcode.com/2020">Advent of Code 2020</a> 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.
</p>
<p>
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 <code>DATA</code> 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.
</p>
<p>Here is my solution for Day 1 Part 1:</p>
<pre>
<code>
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
</code></pre>
<p>
I basically put all 200 numbers into data fields, and then defined an
array large enough to read them into with <code>DIM</code>. 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.
</p>
<p>
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.
</p>
<p>
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 <code>O(n^3)</code> 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.
</p>
<p>
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:
<a href="https://en.wikipedia.org/wiki/Bubble_sort">bubble sort</a>.
</p>
<p>Here is my solution for Day 1 Part 2:</p>
<pre>
<code>
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
</code>
</pre>
<p>
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
<code>FOR</code>-loop completed in another few minutes. My instinct was
right and two of the solution numbers were triple-digit.
</p>
<p>
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
<a href="https://github.com/mist64/cbmbasic"><code>cbmbasic</code></a>
interpreter, which is a neat native C64 Basic interpreter for modern
architectures. (Oh and I tested my samples on <code>cbmbasic</code> and
they finished instantaneously. It helps to have a
thousands-of-times-faster processor.)
</p>
<p>
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 <code>SEQ</code> 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 <code>PEEK</code>s and <code>POKE</code>s to check memory
locations for ASCII/PETSCII character codes. Or I could just put it off
til next year :)
</p>
|
