{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Advent of Code 2020\n",
    "#### Day 8: Handheld Halting\n",
    "\n",
    "A series of instructions consisting of jumps, accumulator increments and no-ops has an infinite loop, but changing one no-op to a jump or vice versa will allow it to run to completion.\n",
    "\n",
    "1. What's the value of the accumulator immediately before the instructions begin to loop?\n",
    "2. After fixing the wrong instruction, what's the value of the accumulator at the end of execution?\n",
    "\n",
    "No surprises in the preamble, just the usual AOC utility functions and the threading macros."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "#lang iracket/lang #:require racket\n",
    "(require advent-of-code\n",
    "         threading)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The instructions are in a text file that looks like\n",
    "```\n",
    "nop +0\n",
    "acc +1\n",
    "jmp +4\n",
    "acc +3\n",
    "jmp -3\n",
    "acc -99\n",
    "acc +1\n",
    "jmp -4\n",
    "acc +6\n",
    "```\n",
    "Since we need to keep track of which instructions to jump to, I've turned it into a hash table so each instruction is indexed starting at 0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<code>'((0 acc . 49) (1 jmp . 274) (2 acc . 49) (3 acc . 49) (4 jmp . 476) (5 jmp . 409) (6 jmp . 269) (7 jmp . 1) (8 acc . -11) (9 acc . 5))</code>"
      ],
      "text/plain": [
       "'((0 acc . 49) (1 jmp . 274) (2 acc . 49) (3 acc . 49) (4 jmp . 476) (5 jmp . 409) (6 jmp . 269) (7 jmp . 1) (8 acc . -11) (9 acc . 5))"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(define raw-instructions (~> (fetch-aoc-input (find-session) 2020 8) (string-split \"\\n\")))\n",
    "\n",
    "(define instruction-set\n",
    "  (for/hash ([instruction (in-list raw-instructions)] [i (in-naturals)])\n",
    "    (match-define (list op val) (string-split instruction))\n",
    "    (values i (cons (string->symbol op) (string->number val)))))\n",
    "\n",
    "(for/list ([i (in-range 10)])\n",
    "  (cons i (hash-ref instruction-set i)))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Part 1\n",
    "\n",
    "Now I write a little interpreter using structural pattern matching and recursion to execute the code.\n",
    "* If the program tried to execute an instruction on the line immediately after the last instruction, the program terminates normally. (This won't happen in part 1, but it's important for part 2.)\n",
    "* We track the line numbers that have been visited in each step.  If a number comes up a second time, that means we're about to start looping, so we break execution here.\n",
    "* `acc n` instructions increment the accumulator by `n` and go to the next line.\n",
    "* `jmp n` instructions skip up or down `n` instructions.\n",
    "* `nop n` instructions don't do anything besides go to the next line."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<code>'(looping . 1949)</code>"
      ],
      "text/plain": [
       "'(looping . 1949)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(define (execute code [acc 0] [line 0] [visited (set)])\n",
    "  (match (hash-ref code line 'terminated)\n",
    "    ['terminated (cons 'terminated acc)]\n",
    "    [_\n",
    "     #:when (set-member? visited line)\n",
    "     (cons 'looping acc)]\n",
    "    [(cons 'acc n) (execute code (+ acc n) (add1 line) (set-add visited line))]\n",
    "    [(cons 'jmp n) (execute code acc (+ n line) (set-add visited line))]\n",
    "    [(cons 'nop _) (execute code acc (add1 line) (set-add visited line))]))\n",
    "\n",
    "(execute instruction-set)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Part 2\n",
    "\n",
    "So far so good.  Now we're told that flipping exactly one `jmp` to a `nop` or vice versa will fix the code, so let's write a utility function to perform that flip, identify the potential candidates for the fix and get an idea of what our workload will be for this problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<code>305</code>"
      ],
      "text/plain": [
       "305"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(define (flip-op op)\n",
    "  (match op\n",
    "    [(cons 'jmp n) (cons 'nop n)]\n",
    "    [(cons 'nop n) (cons 'jmp n)]))\n",
    "\n",
    "(define instruction-count (hash-count instruction-set))\n",
    "(define flippable-bits\n",
    "  (filter (λ (i) (member (car (hash-ref instruction-set i)) '(jmp nop))) (range instruction-count)))\n",
    "\n",
    "(length flippable-bits)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There's only 305 cases to check, so just starting from the top and trying each possible swap in sequence should work fine, rather than trying to come up with some fancier backtracking algorithm.  `for/or` stops at the first non-falsy result, so we just have to wait for the first result that matches the `(cons 'terminated _)` pattern."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<code>'(terminated . 2092)</code>"
      ],
      "text/plain": [
       "'(terminated . 2092)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(for/or ([i (in-list flippable-bits)])\n",
    "  (define flipped-instruction-set (hash-update instruction-set i flip-op))\n",
    "  (match (execute flipped-instruction-set)\n",
    "    [(cons 'looping _) #f]\n",
    "    [(and success (cons 'terminated _)) success]))\n"
   ]
  }
 ],
 "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
}