2020 day 9 complete

2 files changed, 167 insertions, 1 deletions

diff --git a/2020/day-08/day-08.ipynb b/2020/day-08/day-08.ipynb
index 718373b..1cb060b 100644
--- a/2020/day-08/day-08.ipynb
+++ b/2020/day-08/day-08.ipynb
@@ -201,7 +201,7 @@
  ],
  "metadata": {
   "kernelspec": {
-   "display_name": "Racket (Trusted)",
+   "display_name": "Racket (trusted)",
    "language": "racket",
    "name": "racket-trusted"
   },
diff --git a/2020/day-09/day-09.ipynb b/2020/day-09/day-09.ipynb
new file mode 100644
index 0000000..e6f712b
--- /dev/null
+++ b/2020/day-09/day-09.ipynb
@@ -0,0 +1,166 @@
+{
+ "cells": [
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "### Advent of Code 2020\n",
+    "#### Day 9: Encoding Error\n",
+    "\n",
+    "In a list of integers, each number after the 25th should be the sum of two of the previous 25 numbers.\n",
+    "\n",
+    "1. What's the first number in the list that does not have this property?\n",
+    "2. The \"encryption weakness\" is the sum of the extrema in a contiguous range of numbers that sums up to the invalid number in part 1.  Find the encryption weakness.\n",
+    "\n",
+    "I'm using structural pattern matching for this solution, so no extra packages are required beyond the usual."
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 8,
+   "metadata": {
+    "vscode": {
+     "languageId": "racket"
+    }
+   },
+   "outputs": [],
+   "source": [
+    "#lang iracket/lang #:require racket\n",
+    "\n",
+    "(require advent-of-code\n",
+    "         threading)"
+   ]
+  },
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "The data is just a list of integers, so it's straightforward to process."
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 9,
+   "metadata": {
+    "vscode": {
+     "languageId": "racket"
+    }
+   },
+   "outputs": [],
+   "source": [
+    "(define preamble\n",
+    "  (~> (fetch-aoc-input (find-session) 2020 9) (string-split \"\\n\") (map string->number _)))"
+   ]
+  },
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "##### Part 1\n",
+    "\n",
+    "First, we bind the first 25 values to `head` and the 26th to `x`.\n",
+    "\n",
+    "In the `match` syntax, `list-no-order` binds `a` and `b` to the first pair of numbers from anywhere in the first 25 values that satisfies the `#:when` guard.  The exact pair doesn't matter; all we need to know is if it's valid and we can move on to the next test.\n",
+    "\n",
+    "If nothing satisfies the first clause, we've found our invalid number.  We're guaranteed to have an invalid number in the set, so we don't need to guard against `match-define-values` failing when there's fewer than 26 values to work with."
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 10,
+   "metadata": {
+    "vscode": {
+     "languageId": "racket"
+    }
+   },
+   "outputs": [
+    {
+     "data": {
+      "text/html": [
+       "<code>1038347917</code>"
+      ],
+      "text/plain": [
+       "1038347917"
+      ]
+     },
+     "execution_count": 10,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "(define (find-invalid-number xs)\n",
+    "  (match-define-values (head (list x _ ...)) (split-at xs 25))\n",
+    "  (match head\n",
+    "    [(list-no-order a b _ ...)\n",
+    "     #:when (= x (+ a b))\n",
+    "     (find-invalid-number (rest xs))]\n",
+    "    [_ x]))\n",
+    "\n",
+    "(define target-sum (find-invalid-number preamble))\n",
+    "target-sum"
+   ]
+  },
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "##### Part 2\n",
+    "\n",
+    "We can find the range with another match statement, this time looking for a sub-list that's at least two elements long and that satisfies the guard.  Everything after this is just arithmetic."
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 11,
+   "metadata": {
+    "vscode": {
+     "languageId": "racket"
+    }
+   },
+   "outputs": [
+    {
+     "data": {
+      "text/html": [
+       "<code>137394018</code>"
+      ],
+      "text/plain": [
+       "137394018"
+      ]
+     },
+     "execution_count": 11,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "(define (find-contiguous-range xs)\n",
+    "  (match xs\n",
+    "    [(list _ ... x ..2 _ ...)\n",
+    "     #:when (= (apply + x) target-sum)\n",
+    "     x]))\n",
+    "\n",
+    "(define target-range (find-contiguous-range preamble))\n",
+    "(+ (apply max target-range) (apply min target-range))"
+   ]
+  }
+ ],
+ "metadata": {
+  "kernelspec": {
+   "display_name": "Racket (trusted)",
+   "language": "racket",
+   "name": "racket-trusted"
+  },
+  "language_info": {
+   "codemirror_mode": "scheme",
+   "file_extension": ".rkt",
+   "mimetype": "text/x-racket",
+   "name": "Racket",
+   "pygments_lexer": "racket",
+   "version": "8.7"
+  },
+  "orig_nbformat": 4
+ },
+ "nbformat": 4,
+ "nbformat_minor": 2
+}