summaryrefslogblamecommitdiff
path: root/posts/2020-12-04-aoc-2020-day-1-in-cbm-basic.html
blob: 66aabd2cfa8d88547597a878465486de13ba3339 (plain) (tree)
1
2
3
4
5
6
7
8
9
10
               
                







                                                                          
                                                                                                          











                                                                      
                                                                  



                
                               
                                                                                   
                


              
                                          
                                                           
                 


              
                                   
                                                                           
                    



                                                        
                                                           


               



















































































































































































                                                                                
<!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>