{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Advent of Code 2022\n",
    "#### Day 8: Treetop Tree House\n",
    "\n",
    "For a rectangular grid of trees of varying heights,\n",
    "\n",
    "**Part 1.** How many trees are visible (not blocked by same-height or taller trees in their row or column) from outside the patch?\n",
    "\n",
    "**Part 2.** What's the tree with the best \"scenic score\" (the product of the number of trees it can see in each cardinal direction)?\n",
    "\n",
    "For this solution, I didn't use any packages besides the standard distribution and `advent-of-code`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "vscode": {
     "languageId": "racket"
    }
   },
   "outputs": [],
   "source": [
    "(require racket\n",
    "         advent-of-code)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Part 1\n",
    "\n",
    "I built this array as a hashtable with a coordinate struct as the key and the tree height as the value, which makes it easy to check if a particular location falls outside the grid."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "vscode": {
     "languageId": "racket"
    }
   },
   "outputs": [],
   "source": [
    "(struct posn (r c) #:transparent)\n",
    "\n",
    "(define (make-tree-grid data)\n",
    "  (for*/hash ([(row r) (in-indexed data)] [(col c) (in-indexed (in-string row))])\n",
    "    (values (posn r c) (string->number (string col)))))\n",
    "\n",
    "(define tree-grid (make-tree-grid (in-lines (open-aoc-input (find-session) 2022 8))))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A tree is visible if there aren't any other trees as tall as it or taller blocking the visibility in at least one of the cardinal directions.  We check in a particular direction by repeatedly stepping outwards from the original coordinate and checking if we've found a blocking tree yet.\n",
    "\n",
    "The `for/first` returns `#true` if it finds a blocking tree and `#false` if it runs out of trees to check, and the result is negated to turn it into a predicate about whether the tree can see (and be seen from) outside."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "vscode": {
     "languageId": "racket"
    }
   },
   "outputs": [],
   "source": [
    "(define (can-see-to-outside? p height dr dc h)\n",
    "  (match-define (posn r c) p)\n",
    "  (not (for/first ([n (in-naturals 1)]\n",
    "                   #:do [(define p* (posn (+ r (* n dr)) (+ c (* n dc))))]\n",
    "                   #:break (not (hash-has-key? h p*))\n",
    "                   #:when (<= height (hash-ref h p*)))\n",
    "         #true)))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we need a function to check the four cardinal directions and see if at least one of them is unblocked."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "vscode": {
     "languageId": "racket"
    }
   },
   "outputs": [],
   "source": [
    "(define (visible-in-any-direction? p height h)\n",
    "  (for*/or ([dr (in-list '(-1 0 1))] [dc (in-list '(-1 0 1))] #:when (= 1 (abs (+ dr dc))))\n",
    "    (can-see-to-outside? p height dr dc h)))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, add 1 to the count for every tree that's visible:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "vscode": {
     "languageId": "racket"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<code>1733</code>"
      ],
      "text/plain": [
       "1733"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(define (count-visible-trees trees)\n",
    "  (for/sum ([(tree-posn height) (in-hash trees)])\n",
    "           (cond\n",
    "             [(visible-in-any-direction? tree-posn height trees) 1]\n",
    "             [else 0])))\n",
    "\n",
    "(count-visible-trees tree-grid)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Part 2\n",
    "\n",
    "Now we're searching for the tree with the most interior visibility, which is the product of how far we can look in each cardinal direction before running out of visible trees. \n",
    "\n",
    "The search is similar, except now we're calculating a score instead of just checking a predicate. We walk one step at a time, increment the counter and check each tree; if we find a blocking tree, we return the counter, and if we run out of trees to check we break and return the previous counter value.  If there aren't any trees in a direction and the `for` body is never evaluated, `for/last` returns `#false`, which is equivalent to a visibility of 0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "vscode": {
     "languageId": "racket"
    }
   },
   "outputs": [],
   "source": [
    "(define (scenic-score-in-direction p height dr dc h)\n",
    "  (match-define (posn r c) p)\n",
    "  (define score\n",
    "    (for/last ([n (in-naturals 1)]\n",
    "               #:do [(define p* (posn (+ r (* n dr)) (+ c (* n dc))))]\n",
    "               #:break (not (hash-has-key? h p*))\n",
    "               #:final (<= height (hash-ref h p*)))\n",
    "      n))\n",
    "  (if (not score) 0 score))\n",
    "\n",
    "(define (scenic-score p height h)\n",
    "  (for*/product ([dr (in-list '(-1 0 1))] [dc (in-list '(-1 0 1))] #:when (= 1 (abs (+ dr dc))))\n",
    "                (scenic-score-in-direction p height dr dc h)))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With these functions written, calculate each tree's score and find the maximum:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "vscode": {
     "languageId": "racket"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<code>284648</code>"
      ],
      "text/plain": [
       "284648"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(define (find-best-scenic-score trees)\n",
    "  (apply max\n",
    "         (for/list ([(tree-posn height) (in-hash trees)])\n",
    "           (scenic-score tree-posn height trees))))\n",
    "\n",
    "(find-best-scenic-score tree-grid)"
   ]
  }
 ],
 "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,
  "vscode": {
   "interpreter": {
    "hash": "916dbcbb3f70747c44a77c7bcd40155683ae19c65e1c03b4aa3499c5328201f1"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}