summaryrefslogtreecommitdiff
path: root/posts/2020-12-04-aoc-2020-day-1-in-cbm-basic.html
diff options
context:
space:
mode:
author53hornet <atc@53hor.net>2021-07-28 10:58:58 -0400
committer53hornet <atc@53hor.net>2021-07-28 10:58:58 -0400
commitbfaccc32571df8a02f69518d8864244efba3b5b5 (patch)
treecc71a44054af00e73d0db2a1c79c347db3f31327 /posts/2020-12-04-aoc-2020-day-1-in-cbm-basic.html
parentdd75b4a341925e4ba3408b018941241d4317dd9f (diff)
download53hor-bfaccc32571df8a02f69518d8864244efba3b5b5.tar.xz
53hor-bfaccc32571df8a02f69518d8864244efba3b5b5.zip
php site, templating and partials, faster index generation
Diffstat (limited to 'posts/2020-12-04-aoc-2020-day-1-in-cbm-basic.html')
-rw-r--r--posts/2020-12-04-aoc-2020-day-1-in-cbm-basic.html231
1 files changed, 0 insertions, 231 deletions
diff --git a/posts/2020-12-04-aoc-2020-day-1-in-cbm-basic.html b/posts/2020-12-04-aoc-2020-day-1-in-cbm-basic.html
deleted file mode 100644
index 66aabd2..0000000
--- a/posts/2020-12-04-aoc-2020-day-1-in-cbm-basic.html
+++ /dev/null
@@ -1,231 +0,0 @@
-<!DOCTYPE html>
-<html lang="en">
- <head>
- <link rel="stylesheet" href="/includes/stylesheet.css" />
- <meta charset="utf-8" />
- <meta name="viewport" content="width=device-width, initial-scale=1" />
- <meta
- property="og:description"
- content="The World Wide Web pages of Adam Carpenter"
- />
- <meta property="og:image" content="https://nextcloud.53hor.net/index.php/s/Nx9e7iHbw4t99wo/preview" />
- <meta property="og:site_name" content="53hor.net" />
- <meta property="og:title" content="AOC 2020 Day 1 in CBM Basic" />
- <meta property="og:type" content="website" />
- <meta property="og:url" content="https://www.53hor.net" />
- <title>53hornet ➙ AOC 2020 Day 1 in CBM Basic</title>
- </head>
-
- <body>
- <nav>
- <ul>
- <li>
- <a href="/">
- <img alt="home" src="/includes/icons/home-roof.svg" />
- Home
- </a>
- </li>
- <li>
- <a href="/info.html">
- <img alt="information" src="/includes/icons/information-variant.svg" />
- Info
- </a>
- </li>
- <li>
- <a href="https://git.53hor.net">
- <img alt="git" src="/includes/icons/git.svg" />
- Repos
- </a>
- </li>
- <li>
- <a href="/software.html">
- <img alt="software" src="/includes/icons/floppy-variant.svg" />
- Software
- </a>
- </li>
- <li>
- <a type="application/rss+xml" href="/rss.xml">
- <img alt="rss" src="/includes/icons/rss.svg" />
- RSS
- </a>
- </li>
- </ul>
- </nav>
-
- <article>
- <h1>AOC 2020 Day 1 in CBM Basic</h1>
-
- <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>
- </article>
- </body>
-</html>