php site, templating and partials, faster index generation

1 files changed, 179 insertions, 0 deletions

diff --git a/posts/2020-12-04-aoc-2020-day-1-in-cbm-basic.php b/posts/2020-12-04-aoc-2020-day-1-in-cbm-basic.php
new file mode 100644
index 0000000..5196d2c
--- /dev/null
+++ b/posts/2020-12-04-aoc-2020-day-1-in-cbm-basic.php
@@ -0,0 +1,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>