diff options
Diffstat (limited to 'aoc2020/day-09/day-09.ipynb')
-rw-r--r-- | aoc2020/day-09/day-09.ipynb | 166 |
1 files changed, 0 insertions, 166 deletions
diff --git a/aoc2020/day-09/day-09.ipynb b/aoc2020/day-09/day-09.ipynb deleted file mode 100644 index e6f712b..0000000 --- a/aoc2020/day-09/day-09.ipynb +++ /dev/null @@ -1,166 +0,0 @@ -{ - "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 -} |