From c46213b57944279fec8d7e910a4ff75a346dafaa Mon Sep 17 00:00:00 2001
From: Neil Smith <neil.git@njae.me.uk>
Date: Thu, 23 Dec 2021 11:26:56 +0000
Subject: [PATCH] Done day 20

---
 advent-of-code21.cabal |   5 +
 advent20/Main.hs       | 115 ++++++++++++++++++++++
 data/advent20.txt      | 102 ++++++++++++++++++++
 data/advent20a.txt     |   7 ++
 problems/day20.html    | 212 +++++++++++++++++++++++++++++++++++++++++
 5 files changed, 441 insertions(+)
 create mode 100644 advent20/Main.hs
 create mode 100644 data/advent20.txt
 create mode 100644 data/advent20a.txt
 create mode 100644 problems/day20.html

diff --git a/advent-of-code21.cabal b/advent-of-code21.cabal
index f92f871..7134dcd 100644
--- a/advent-of-code21.cabal
+++ b/advent-of-code21.cabal
@@ -201,3 +201,8 @@ executable advent19
   import: common-extensions, build-directives
   main-is: advent19/Main.hs
   build-depends: linear, text, attoparsec, containers, multiset
+
+executable advent20
+  import: common-extensions, build-directives
+  main-is: advent20/Main.hs
+  build-depends: linear, mtl, containers
diff --git a/advent20/Main.hs b/advent20/Main.hs
new file mode 100644
index 0000000..fbc4fb6
--- /dev/null
+++ b/advent20/Main.hs
@@ -0,0 +1,115 @@
+-- Writeup at https://work.njae.me.uk/2021/12/18/advent-of-code-2021-day-16/
+
+
+import Control.Monad.State.Strict
+import Control.Monad.Reader
+-- import Control.Monad.Writer
+import Control.Monad.RWS.Strict
+import Data.List
+import Data.Ix
+import Data.Maybe
+
+import qualified Data.Set as S
+import Linear (V2(..), (^+^))
+
+type Pixel = V2 Int -- row, column
+
+data Image = Image 
+  { grid :: S.Set Pixel
+  , distantPixel :: Bool
+  , explicitRegion :: (Pixel, Pixel)
+  } deriving (Eq, Show)
+
+type Enhancement = [Bool]
+
+type ImageEnhancer = RWS Enhancement [Int] Image
+
+main :: IO ()
+main = 
+  do  text <- readFile "data/advent20.txt"
+      let (enhancement, image) = parse text
+      print $ part1 enhancement image
+      print $ part2 enhancement image
+
+-- part1 enhancement image = s
+--   where (s, image', _) = runRWS (enhanceImage 2) enhancement image
+
+part1 enhancement image = fst $ evalRWS (enhanceImage 2) enhancement image
+
+part2 enhancement image = fst $ evalRWS (enhanceImage 50) enhancement image
+
+enhanceImage :: Int -> ImageEnhancer Int
+enhanceImage 0 = do image <- get
+                    return $ S.size $ grid image
+enhanceImage n = do newImage
+                    enhanceImage (n - 1)
+
+newImage :: ImageEnhancer ()
+newImage =
+  do  image <- get
+      let region = explicitRegion image
+      let region' = expandRegion region
+      let heres = range region'
+      let distant = distantPixel image
+      newPixelStates <- mapM newPixel heres
+      let grid' = S.fromList $ catMaybes newPixelStates
+      enhancement <- ask
+      let distant' = if distant then (last enhancement) else (head enhancement)
+      put $ Image {grid = grid', distantPixel = distant', explicitRegion = region'}
+
+
+showImage :: Image -> String
+showImage image = 
+  unlines $ [ [showPixel (V2 r c) | c <- [minC..maxC] ] | r <- [minR..maxR]]
+  where (V2 minR minC, V2 maxR maxC) = explicitRegion image
+        g = grid image
+        showPixel here = if here `S.member` g then '█' else ' '
+
+newPixel :: Pixel -> ImageEnhancer (Maybe Pixel)
+newPixel here =
+  do  stencil <- findStencil here
+      let i = intify stencil
+      enh <- ask
+      return $ if enh!!i then Just here else Nothing
+
+findStencil :: Pixel -> ImageEnhancer [Bool]
+findStencil here = 
+  do  let nbrs = map (here ^+^) neighbours
+      g <- gets grid
+      d <- gets distantPixel
+      r <- gets explicitRegion
+      return $ map (findContents g d r) nbrs
+
+findContents :: S.Set Pixel -> Bool -> (Pixel, Pixel) -> Pixel -> Bool
+findContents grid distant region here 
+  | inRange region here = here `S.member` grid
+  | otherwise           = distant
+
+
+neighbours :: [Pixel]
+neighbours = [V2 r c | r <- [-1, 0, 1], c <- [-1, 0, 1]]
+
+expandRegion :: (Pixel, Pixel) -> (Pixel, Pixel)
+expandRegion ((V2 r0 c0), (V2 r1 c1)) = (V2 (r0 - 1) (c0 - 1), V2 (r1 + 1) (c1 + 1))
+
+parse text = (enhancement, image)
+  where ls = lines text
+        enhancement = [ c == '#' | c <- head ls]
+        image = mkImage $ drop 2 ls
+
+
+mkImage :: [String] -> Image
+mkImage rows = Image { grid = grid, distantPixel = False
+                     , explicitRegion = ((V2 0 0), (V2 maxRow maxCol))
+                     }
+  where maxRow = length rows - 1
+        maxCol = (length $ head rows) - 1
+        grid = S.fromList [V2 r c | r <- [0..maxRow], c <- [0..maxCol], (rows!!r)!!c == '#']
+
+
+intify pixels = foldl' addBit 0 pixels
+  where addBit w b = (w * 2) + (if b then 1 else 0)
+
+-- wordify :: BS.BitString -> Integer
+-- wordify bs = foldl' addBit 0 $ BS.to01List bs
+--   where addBit w b = (w * 2) + (fromIntegral b)
diff --git a/data/advent20.txt b/data/advent20.txt
new file mode 100644
index 0000000..e1398e1
--- /dev/null
+++ b/data/advent20.txt
@@ -0,0 +1,102 @@
+#.#.##.#.#....#.#.#......###.#....####.#...###..#...#.#.###.#...#.#...##..#.#.#.##..#......#..#...#..#.###...####....#.#....#...#.##.#####.##..#####..###..###.#.##.#####..#..#..######..######.####.####....#.#..####..#...##..#..#.#.##.##.##.##.#.##..##..###....###.###.##..#...#.##..#.#..####.......#...###..#....##..#..##.#..##..#..##.###..##.#.##...#..###.###...###...#.#######.....#.##..#......#....#.#..##..##..#..####.#.#.##..##.##.#..#.##..#.......#.####.#.##..#..........#.#.#..##.##......##..#.##..#.####.
+
+.#..####..#.####.####...#.##..##.##....#..#####..#.#......##....#.#.#..####...###..#..#.#.##.##...##
+#...##.......##..#....##.####.....####..#.#.....#.#.#........#.#######.#.##...####.#.#...#.###...###
+###..##.#.#.#.#....##....#.#.#.##..#.##..##.##.##.#.##...##..####.....###.#.#.#.#....#......###..##.
+###......#.##.....#......##..######.######.##..........#.#..#.#.########.####.###.#.#...#.##.##.##..
+.###.#.#......######.####......#..##....#..#...###...#####..####..###.#####..###...####.#.###.#.###.
+#.#..##.....#...###...#.##.#..#.#.#.......#.##.###....###.###.#..###...#.#..#...#..###..##.###.##...
+#####.#.##..#.##..####.....#.#.#.#....###....##.######.##...###....###.##.#...#....####.##.#.###..#.
+.##...##.#....##.#..#......####.#..#.##...##...#.##.....#.#.#.###.###.##.#.##.#.###..#..#..###......
+.....#....#..#..####.####..#..#........#....#.#.##.######.#..#...##.###.#.#....#..#.#....##....##.##
+..#...####.#.#.....##.#.##.#.#...##..####.#.###.#..#.###...#.#.....###....#..#..#.#########..####.##
+.#..###.#.....#..#.....#.##.##..#.#####..############.#..#.#.###........#.##....#...#.#.#....#.#..##
+.#.#..#####.####.#.##...#.#.##....##..#.#.#..#.#.##.##.#..##....##.##.###....#.##..#.#####..####..##
+#...##......#####..##...#.....##..#..##......#.#######.#.##..###.#..###..#.#.#.#.#.###.#.##.#.####..
+##..#...####.#..#....#..#..##......##.##....##.#..#.#.##.###.#.#.....#.#..##.###.#####.#..#.#####.##
+#..###.#.###.##......#.####.....####.##....#.....###.#.#######.#..##.#.###.##...###....##.#.####...#
+..#.###.##.#.#.#..##..####.....#.##.##.##....##.####..#.###..####...#...#.#..##.##...#...#.#.##.####
+##...#.##.#######..##.##.#####.......#..#..##.#....#.####..#.##.##...###.#....#....#.##.##.####..##.
+##...##.###.#.#.#.#.##.##....#.####.###..#..#.#.##..###.##..#.#.#.##.#####.####..###...#.....###..#.
+#..#.#####...#...#...#...##.##.##..##.###..###.####.......#.#####.###..###.#.###....#.####...#.#.#..
+#######..####.#.........#.##.###.##.##..####...#....#..###.##....#.#.....##.####..##.#.##..#.#.#...#
+..###.#..#.#..#.#.#..#...#.#....#..###.#.###.#..#..#...#####..#......###.#.#..#..#.#.##....#.#.#..#.
+#.....###...#...###.....###....#.################.##..##..#...###.##.#....#....##.#.#.#..##.#.##..##
+.#.###....##.#.##..#.#######..####....#.####.#.#.####..##.#####..#...#.#.######.###..#.##...#..##.##
+..#.#.##.#.#.#......#.#...#..#...#.##.#..##.#####.###....###.####..####.#....##.#########.....##..#.
+.#.##..#.##...#.##.#.##.#.#.#.##...###.##.#.#####..##.#..##.#.##.#.....#..##.##..##..#..#.#.##.##...
+.#...#.##......##.#..##.#.#...#.##.##.####...###..#..###..........#.#.#.#.##.##.##.##..####..#.#.###
+........###..##...##..##.#.###....#.#......##..####.#####....#...#...##.....##.##.#..#...#####...###
+#..###.#.##.#.#.##.....#.###.#.###.#####.#..#.#..##..###..##.##...#...##.#...#.#..#..#.##...#.##...#
+##....##...#####.....#..#..#.....##.##..#......###.##...#..#.######.#..#.######..#..#.#.....#....#..
+#...#.#..##..##.#....#.#..#...##.#####..####.###.##...#.###...#.##.#.##.#.#...###.##.####..###.#.###
+.#..##.#.###..####.#..#..##.#..#.##.#.#...#.##.#.###.##..###.#.##..##..#..#.#.###.##.###.#..#..##.#.
+#....#.####..##.#..#.###.####..#.######.#.##.#.###...##...#.#..#.##.##....###...#.#..#.#...#..######
+###.#..##..#######.##..#.#..#.###..##.#..####.#.###.#.#.##.#....#......#...#.#.##.#...###.#.##.#....
+.#.#####..##..#.##.....##..##.#....##.##.##..##.####.#...##..##...#...####..####.#.##...#...#....#..
+...#.###...##..##...#.#..####..#.###..###.###.......#####..##..###.##..##.#.....####....#.###.#..###
+#.#..##..#####.#.##.#..####....#...#..####.#.##....#..#..#.##.##.#.##..#..#.#.#..#####..##...#.#..#.
+..#..###...#.#......##########..#.....#.....#.###....###..#.#..###.#..###..#.#...#.##....###...#.#.#
+#.#...#.##..#..##...#######.##.##.#####...#####..#...#....#....#..#.#.##.#...........###.##.###...##
+.#..#.#.###..#....##..#..##.##..#.##..####..#...####.##..#..#####...#.###..#..##.#...##..#.#.#.###.#
+###..#..#####..#....#.##....##.#...........###..##...##.##..#....##.###..##.#.#.#..#..##..###...##..
+.#...##.#.#...##.###..##.#.#.########..####.#.#.#.##.#..#.#####...#.#...####...#.##.##.###...#....#.
+#####..#.#..######...#....##.#..#.##..#...#####...#....####..###.#..#..###......###.#.....###.######
+.##.#....#...#.##.#.######..#....##..#.###...##..######.#####..##.####.##...#.....###..###.##..#..##
+..###.##...#.###.#..####....###....#.##.#..##..#..#.#...#.##.......####.#....##.#....#...###...#.#..
+##..##.###..#....##.##...#....#.#####.#...#.#.#.###.#.##.#####.#...##....#....##..##.##..##.##.#..##
+#...###.#.#.##..........##...#..#####.#...###.##...#...###.##.##...####.##.........#.#######.#.#.#..
+..#....##...##.#.#..##.#...#.######.##.###.###..#..##.#........##..###...#.##..#######.##.....##.##.
+.#.##.##.#..#...#.#.##.#..##.##..#..###.##.###.#.###..##.###.#..##.#.....###.#.#.###...#########.#.#
+..#.##.#..###..##..#..##.#...#..##..##..#..#.#....#..##.#...#...##..#....#..##.#...#.##.#.########..
+#..####..####..##.#.##..####.#.#.#..#.....###.###..#....#.#####..####.#.....#...#....###.#.#.......#
+.###.#...#.###..#......#..#..####.##...###...##...##...#.#..#....###......###.....#.####...##.#.##.#
+##..#.#.......##..####.#..#...#.##..###...#.....##..#....#..###.......#####...##.###.#####..#..###..
+..#.#.##.#.#.##.##.####.##.#.#.......#..##.#.#.##....#.##.####..#######..##.#....#..#.##....####....
+.#..#..#........####..#.#.#.######.###.#...#.#.#..#.#......##..#.#...####..#.#.#.#..#....##.#.#..#.#
+.###.#...#......###.######.#....#######..#.##...###..#.##..#..###.##.#.....#.######..##.#.#...####..
+#.#.##..###....#.....#..###..#.#.###.#...##.#.#..##.#.#####.#..##.....#.#####.#..#..##.####.##....#.
+.#####....###..#..##..###.####...###..#.######..#####.##..#.####....#.#..###.#.#...#..#.#.##.#.#..##
+..#####.#..#.######..#.##.##..#.##...#.####...####..#..#.###....##.#...#.##.#.#.#.#......#...##..##.
+.#.#....#...#####..#.#.....#.#####..#..#..........##.#..###...#.#...#########....##.##..##.#..##..##
+##....#.#...##.....##.#.#..#...####.###.......#####.#..####.#..###..##..##.#..##.#.###....#.##..#.#.
+#.#..#..#.#..#.#####..#..###.#.###..##.#.#.##...####..#.#...#.##...##.####..##.###....######.#.##...
+###..#.#..##.....#..##.#.#.##.##.##.##.#.##.##..###..##.....###..###.###..###.#..#....#.#......#...#
+##....#.#..#.####.##......##...###.#...#.###..##.#..#.##..##...#.##.........##.####.###..######..###
+####..#....##.#####.#...#.##.....#..#....######..#......###.#..##....#.#.###.###.#######.#.#....###.
+#####.#.#####.###.#..#.#######.#.#.#.####.#####.####.##..#.########..###..#.#####.#.#.##..#..##...#.
+#.......#....#.##.#...##.....#...#######..#.##...##.#...##.#.#.##..###.##..#.#.#..#.#.###...###..#..
+.###.##......#..#....#.#.####.#.##.##.#..##...###.#...#.#...##.###.#.###.###..#..#.#..#..#...###...#
+####.#.##..##.##.#..##....##....##...#...#...#.######.#...#...##.#.##..#.##.##..##..#.##...##..##.#.
+###.###.##.#...##.##....#..####.#...#.#....#######..##.#.##.###..###.#..#..#..#.##.#..###..#.#######
+#.##...#########...#.#.#..##.#....##..#.#..##.#..####....##.#.#.###.#..#..#.#..##...#..###.###.#...#
+##..#.##....#....####...#.#.#...###.#....##.#.###...#..#.####..##.#.###...###..###..#.##..#.##.##...
+###.#.##..#.#.#.#######.####.#.####.#####...#....#..##.###..#...#.#..####..###.##.....#....##.....#.
+.######..#.##.#####.#.##.#...#...#..#####....#.....#.####.###..#...#.##..###.#.##.###.#...#.#..##.#.
+.#.#.##.###..#..#..###.#.#.#.#####..##.#...#..#.....#.###....####..#.#..#.#......#.##.#.###.#...#...
+#####..#.##..####.###...##...#.###..#.##.###..####..####.#.###########.##.#...###.###.######..#..#.#
+.##.#.##...#.##.##.#.##..#..##.##..#....#.#.##.##.....#.#.#..#..####.###.#..#..###.....#.###...##.#.
+#####....###...#..#..##.#..#..#.##.#.#.#..##.##.####.###..###.#.#.##..##.#...###.#..#.##.#.#.#.#..##
+####...#.##...##.#.....#...#####.##...###.#.#.#.#..##.#...#.#..#.#.###...#.##.#...#..###.##.####....
+##.####.#.##.###..#...#..####.###....###.#.#.####.#..##.#.#.#.##.#.#####.##..#..##.#.#######...#..##
+.....#...#.#####...#........#.#...####.#.#.#.#.#..##.#.##.##.........#...###...###.#.....#...#....##
+......##.#####..##...##.####.#.###.##..#.#..#..##.####....###.#.......#.##...#...#.###.##.#.#####..#
+....##.###..#####.##.#..####.#.....#.##.###.##..#######.###..##...#...##....###.##..###...#.....#..#
+####.#.#....##...####..#.#.#.##..#.#.#.....#...#.#.##.#..##......###.#...##...######..#####.#....###
+##..#......#..##.###...#..#.#..###.###.##...####.....#.#...#..##....#...#.#...##....#..##......##.#.
+#..###....##.###.##.#......#.....###...#..#####..###..#..#.#.##..#.##....###..##.#...####..##.#####.
+...##..#.###..#...##.##.###.###.#....#.###.####.#...#.#####.##.#...#..##.####.#.##.#.#...#.#..#.#..#
+.#......#####..#..###.###.......#.##.#..#....##.###.##.#....##.#.#######..##..#....#..#.###.##.#####
+...#..##..#..####.###...#...##..####.#####..#..###...##.##.##...#..#.###...##.#....#.####..##..#.###
+####.#.#..##..###..#...###...##...#.#####.###.#.#..#.##..##...##..###.....###.##.###....#..##.###..#
+#.###.######..#.#..###..##....####.###.###.###.#####..###.#.#..###.#.####.###...##.##.###..##.#.#.#.
+####.....#......#......#.#.#####.#...#..#.##...#####..#..########..#####.##..###...####..#..#.#.#.##
+..#...#...#####...##.#.#.#..##..#..#.#......##.#####...#...###..###...#.####.#.#.#.#.#.....#..##.###
+.###...#...#.###.#.#...#..##..#..###.###.#.#..##..#.....##...##.####...###..#.....#.##...##..#.##...
+###...####.#.#......#####.#.##.#####.#.#####...##.##..#...#.####..#..##.#.##.#...#..#.#.#.#.#.###..#
+....#####.###.##..#.#..#####..###..#..###..###..#...####.####.##..####.##..#.#.###.###..###..######.
+##.##..#....#.#..#.##.##.###....#.#########.#.#...#..###.#..###..#....##.#..#.##..###.###.#...##....
+#.##.##.###.....####.###.#.#...#####..#.##.###.##.#....##.##.###.#...#.###..#..##.####.#...#...##...
+.....#####.........#..#..#...##....#....###.#.###.#######..##....###.##.........###.#.##..##...###..
+..###..####.##.#.#..##..#..#.#.##.####...##..#..###...#......#..######.####....###.#.###.#.##.##.#..
+.####.#####.##.#.####......###....#.#......#.#.##...##...#..#.#..##...#..##.#...##..###.###.##.##.##
\ No newline at end of file
diff --git a/data/advent20a.txt b/data/advent20a.txt
new file mode 100644
index 0000000..000a554
--- /dev/null
+++ b/data/advent20a.txt
@@ -0,0 +1,7 @@
+..#.#..#####.#.#.#.###.##.....###.##.#..###.####..#####..#....#..#..##..###..######.###...####..#..#####..##..#.#####...##.#.#..#.##..#.#......#.###.######.###.####...#.##.##..#..#..#####.....#.#....###..#.##......#.....#..#..#..##..#...##.######.####.####.#.#...#.......#..#.#.#...####.##.#......#..#...##.#.##..#...##.#.##..###.#......#.#.......#.#.#.####.###.##...#.....####.#..#..#.##.#....##..#.####....##...##..#...#......#.#.......#.......##..####..#...#.#.#...##..#.#..###..#####........#..####......#..#
+
+#..#.
+#....
+##..#
+..#..
+..###
\ No newline at end of file
diff --git a/problems/day20.html b/problems/day20.html
new file mode 100644
index 0000000..ebfc7d9
--- /dev/null
+++ b/problems/day20.html
@@ -0,0 +1,212 @@
+<!DOCTYPE html>
+<html lang="en-us">
+<head>
+<meta charset="utf-8"/>
+<title>Day 20 - Advent of Code 2021</title>
+<!--[if lt IE 9]><script src="/static/html5.js"></script><![endif]-->
+<link href='//fonts.googleapis.com/css?family=Source+Code+Pro:300&subset=latin,latin-ext' rel='stylesheet' type='text/css'/>
+<link rel="stylesheet" type="text/css" href="/static/style.css?26"/>
+<link rel="stylesheet alternate" type="text/css" href="/static/highcontrast.css?0" title="High Contrast"/>
+<link rel="shortcut icon" href="/favicon.png"/>
+</head><!--
+
+
+
+
+Oh, hello!  Funny seeing you here.
+
+I appreciate your enthusiasm, but you aren't going to find much down here.
+There certainly aren't clues to any of the puzzles.  The best surprises don't
+even appear in the source until you unlock them for real.
+
+Please be careful with automated requests; I'm not a massive company, and I can
+only take so much traffic.  Please be considerate so that everyone gets to play.
+
+If you're curious about how Advent of Code works, it's running on some custom
+Perl code. Other than a few integrations (auth, analytics, social media), I
+built the whole thing myself, including the design, animations, prose, and all
+of the puzzles.
+
+The puzzles are most of the work; preparing a new calendar and a new set of
+puzzles each year takes all of my free time for 4-5 months. A lot of effort
+went into building this thing - I hope you're enjoying playing it as much as I
+enjoyed making it for you!
+
+If you'd like to hang out, I'm @ericwastl on Twitter.
+
+- Eric Wastl
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+-->
+<body>
+<header><div><h1 class="title-global"><a href="/">Advent of Code</a></h1><nav><ul><li><a href="/2021/about">[About]</a></li><li><a href="/2021/events">[Events]</a></li><li><a href="https://teespring.com/stores/advent-of-code" target="_blank">[Shop]</a></li><li><a href="/2021/settings">[Settings]</a></li><li><a href="/2021/auth/logout">[Log Out]</a></li></ul></nav><div class="user">Neil Smith <a href="/2021/support" class="supporter-badge" title="Advent of Code Supporter">(AoC++)</a> <span class="star-count">40*</span></div></div><div><h1 class="title-event">&nbsp;&nbsp;&nbsp;<span class="title-event-wrap">var y=</span><a href="/2021">2021</a><span class="title-event-wrap">;</span></h1><nav><ul><li><a href="/2021">[Calendar]</a></li><li><a href="/2021/support">[AoC++]</a></li><li><a href="/2021/sponsors">[Sponsors]</a></li><li><a href="/2021/leaderboard">[Leaderboard]</a></li><li><a href="/2021/stats">[Stats]</a></li></ul></nav></div></header>
+
+<div id="sidebar">
+<div id="sponsor"><div class="quiet">Our <a href="/2021/sponsors">sponsors</a> help make Advent of Code possible:</div><div class="sponsor"><a href="https://jb.gg/AoC2021tips" target="_blank" onclick="if(ga)ga('send','event','sponsor','sidebar',this.href);" rel="noopener">JetBrains</a> - Get ready to jingle with Advent of Code in Kotlin! Have fun, learn new things, and win prizes. Believe in magic with Kotlin. Happy holidays! https://jb.gg/AoC</div></div>
+</div><!--/sidebar-->
+
+<main>
+<script>window.addEventListener('click', function(e,s,r){if(e.target.nodeName==='CODE'&&e.detail===3){s=window.getSelection();s.removeAllRanges();r=document.createRange();r.selectNodeContents(e.target);s.addRange(r);}});</script>
+<article class="day-desc"><h2>--- Day 20: Trench Map ---</h2><p>With the scanners fully deployed, you turn their attention to mapping the floor of the ocean trench.</p>
+<p>When you get back the image from the scanners, it seems to just be random noise. Perhaps you can combine an image enhancement algorithm and the input image (your puzzle input) to clean it up a little.</p>
+<p>For example:</p>
+<pre><code>..#.#..#####.#.#.#.###.##.....###.##.#..###.####..#####..#....#..#..##..##
+#..######.###...####..#..#####..##..#.#####...##.#.#..#.##..#.#......#.###
+.######.###.####...#.##.##..#..#..#####.....#.#....###..#.##......#.....#.
+.#..#..##..#...##.######.####.####.#.#...#.......#..#.#.#...####.##.#.....
+.#..#...##.#.##..#...##.#.##..###.#......#.#.......#.#.#.####.###.##...#..
+...####.#..#..#.##.#....##..#.####....##...##..#...#......#.#.......#.....
+..##..####..#...#.#.#...##..#.#..###..#####........#..####......#..#
+
+#..#.
+#....
+##..#
+..#..
+..###
+</code></pre>
+<p>The first section is the <em>image enhancement algorithm</em>. It is normally given on a single line, but it has been wrapped to multiple lines in this example for legibility. The second section is the <em>input image</em>, a two-dimensional grid of <em>light pixels</em> (<code>#</code>) and <em>dark pixels</em> (<code>.</code>).</p>
+<p>The image enhancement algorithm describes how to enhance an image by <em>simultaneously</em> converting all pixels in the input image into an output image. Each pixel of the output image is determined by looking at a 3x3 square of pixels centered on the corresponding input image pixel. So, to determine the value of the pixel at (5,10) in the output image, nine pixels from the input image need to be considered: (4,9), (4,10), (4,11), (5,9), (5,10), (5,11), (6,9), (6,10), and (6,11). These nine input pixels are combined into a single binary number that is used as an index in the <em>image enhancement algorithm</em> string.</p>
+<p>For example, to determine the output pixel that corresponds to the very middle pixel of the input image, the nine pixels marked by <code>[...]</code> would need to be considered:</p>
+<pre><code># . . # .
+#[. . .].
+#[# . .]#
+.[. # .].
+. . # # #
+</code></pre>
+<p>Starting from the top-left and reading across each row, these pixels are <code>...</code>, then <code>#..</code>, then <code>.#.</code>; combining these forms <code>...#...#.</code>. By turning dark pixels (<code>.</code>) into <code>0</code> and light pixels (<code>#</code>) into <code>1</code>, the binary number <code>000100010</code> can be formed, which is <code>34</code> in decimal.</p>
+<p>The image enhancement algorithm string is exactly 512 characters long, enough to match every possible 9-bit binary number. The first few characters of the string (numbered starting from zero) are as follows:</p>
+<pre><code>0         10        20        30  <em>34</em>    40        50        60        70
+|         |         |         |   <em>|</em>     |         |         |         |
+..#.#..#####.#.#.#.###.##.....###.<em>#</em>#.#..###.####..#####..#....#..#..##..##
+</code></pre>
+<p>In the middle of this first group of characters, the character at index 34 can be found: <code>#</code>. So, the output pixel in the center of the output image should be <code>#</code>, a <em>light pixel</em>.</p>
+<p>This process can then be repeated to calculate every pixel of the output image.</p>
+<p>Through advances in imaging technology, the images being operated on here are <em>infinite</em> in size. <em>Every</em> pixel of the infinite output image needs to be calculated exactly based on the relevant pixels of the input image. The small input image you have is only a small region of the actual infinite input image; the rest of the input image consists of dark pixels (<code>.</code>). For the purposes of the example, to save on space, only a portion of the infinite-sized input and output images will be shown.</p>
+<p>The starting input image, therefore, looks something like this, with more dark pixels (<code>.</code>) extending forever in every direction not shown here:</p>
+<pre><code>...............
+...............
+...............
+...............
+...............
+.....#..#......
+.....#.........
+.....##..#.....
+.......#.......
+.......###.....
+...............
+...............
+...............
+...............
+...............
+</code></pre>
+<p>By applying the image enhancement algorithm to every pixel simultaneously, the following output image can be obtained:</p>
+<pre><code>...............
+...............
+...............
+...............
+.....##.##.....
+....#..#.#.....
+....##.#..#....
+....####..#....
+.....#..##.....
+......##..#....
+.......#.#.....
+...............
+...............
+...............
+...............
+</code></pre>
+<p>Through further advances in imaging technology, the above output image can also be used as an input image! This allows it to be enhanced <em>a second time</em>:</p>
+<pre><code>...............
+...............
+...............
+..........#....
+....#..#.#.....
+...#.#...###...
+...#...##.#....
+...#.....#.#...
+....#.#####....
+.....#.#####...
+......##.##....
+.......###.....
+...............
+...............
+...............
+</code></pre>
+<p>Truly incredible - now the small details are really starting to come through. After enhancing the original input image twice, <code><em>35</em></code> pixels are lit.</p>
+<p>Start with the original input image and apply the image enhancement algorithm twice, being careful to account for the infinite size of the images. <em>How many pixels are lit in the resulting image?</em></p>
+</article>
+<p>Your puzzle answer was <code>5225</code>.</p><article class="day-desc"><h2 id="part2">--- Part Two ---</h2><p>You still can't quite make out the details in the image. Maybe you just didn't <a href="https://en.wikipedia.org/wiki/Kernel_(image_processing)" target="_blank">enhance</a> it <span title="Yeah, that's definitely the problem.">enough</span>.</p>
+<p>If you enhance the starting input image in the above example a total of <em>50</em> times, <code><em>3351</em></code> pixels are lit in the final output image.</p>
+<p>Start again with the original input image and apply the image enhancement algorithm 50 times. <em>How many pixels are lit in the resulting image?</em></p>
+</article>
+<p>Your puzzle answer was <code>18131</code>.</p><p class="day-success">Both parts of this puzzle are complete! They provide two gold stars: **</p>
+<p>At this point, you should <a href="/2021">return to your Advent calendar</a> and try another puzzle.</p>
+<p>If you still want to see it, you can <a href="20/input" target="_blank">get your puzzle input</a>.</p>
+<p>You can also <span class="share">[Share<span class="share-content">on
+  <a href="https://twitter.com/intent/tweet?text=I%27ve+completed+%22Trench+Map%22+%2D+Day+20+%2D+Advent+of+Code+2021&amp;url=https%3A%2F%2Fadventofcode%2Ecom%2F2021%2Fday%2F20&amp;related=ericwastl&amp;hashtags=AdventOfCode" target="_blank">Twitter</a>
+  <a href="javascript:void(0);" onclick="var mastodon_instance=prompt('Mastodon Instance / Server Name?'); if(typeof mastodon_instance==='string' && mastodon_instance.length){this.href='https://'+mastodon_instance+'/share?text=I%27ve+completed+%22Trench+Map%22+%2D+Day+20+%2D+Advent+of+Code+2021+%23AdventOfCode+https%3A%2F%2Fadventofcode%2Ecom%2F2021%2Fday%2F20'}else{return false;}" target="_blank">Mastodon</a
+></span>]</span> this puzzle.</p>
+</main>
+
+<!-- ga -->
+<script>
+(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
+(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
+m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
+})(window,document,'script','//www.google-analytics.com/analytics.js','ga');
+ga('create', 'UA-69522494-1', 'auto');
+ga('set', 'anonymizeIp', true);
+ga('send', 'pageview');
+</script>
+<!-- /ga -->
+</body>
+</html>
\ No newline at end of file
-- 
2.34.1