From 5571128ccde9145b55276adc236667be871253f2 Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Sat, 4 Jan 2020 12:31:45 +0000 Subject: [PATCH] Day 19 done --- advent19/package.yaml | 60 +++++++++++++ advent19/src/advent19.hs | 95 ++++++++++++++++++++ data/advent19.txt | 1 + data/advent19a.txt | 1 + problems/day19.html | 182 +++++++++++++++++++++++++++++++++++++++ stack.yaml | 1 + 6 files changed, 340 insertions(+) create mode 100644 advent19/package.yaml create mode 100644 advent19/src/advent19.hs create mode 100644 data/advent19.txt create mode 100644 data/advent19a.txt create mode 100644 problems/day19.html diff --git a/advent19/package.yaml b/advent19/package.yaml new file mode 100644 index 0000000..4a6a56a --- /dev/null +++ b/advent19/package.yaml @@ -0,0 +1,60 @@ +# This YAML file describes your package. Stack will automatically generate a +# Cabal file when you run `stack build`. See the hpack website for help with +# this file: . + +name: advent19 +synopsis: Advent of Code +version: '0.0.1' + +default-extensions: +- AllowAmbiguousTypes +- ApplicativeDo +- BangPatterns +- BlockArguments +- DataKinds +- DeriveFoldable +- DeriveFunctor +- DeriveGeneric +- DeriveTraversable +- EmptyCase +- FlexibleContexts +- FlexibleInstances +- FunctionalDependencies +- GADTs +- GeneralizedNewtypeDeriving +- ImplicitParams +- KindSignatures +- LambdaCase +- MonadComprehensions +- MonoLocalBinds +- MultiParamTypeClasses +- MultiWayIf +- NegativeLiterals +- NumDecimals +- OverloadedLists +- OverloadedStrings +- PartialTypeSignatures +- PatternGuards +- PatternSynonyms +- PolyKinds +- RankNTypes +- RecordWildCards +- ScopedTypeVariables +- TemplateHaskell +- TransformListComp +- TupleSections +- TypeApplications +- TypeInType +- TypeOperators +- ViewPatterns + + +executables: + advent19: + main: advent19.hs + source-dirs: src + dependencies: + - base >= 2 && < 6 + - text + - containers + - intcode diff --git a/advent19/src/advent19.hs b/advent19/src/advent19.hs new file mode 100644 index 0000000..7543513 --- /dev/null +++ b/advent19/src/advent19.hs @@ -0,0 +1,95 @@ +import Debug.Trace + +import Intcode + +import qualified Data.Text.IO as TIO + +import qualified Data.Map.Strict as M +-- import Data.Map.Strict ((!)) +import Data.List + +newtype Position = Position (Integer, Integer) deriving (Ord, Eq, Show) -- x, y + +newtype Bounds = Bounds (Integer, Integer) deriving (Ord, Eq, Show) -- upper, lower + +type Beam = M.Map Integer Bounds + + +main :: IO () +main = do + text <- TIO.readFile "data/advent19.txt" + let mem = parseMachineMemory text + let machine = makeMachine mem + print $ part1 machine + print $ part2 machine + + +maxY = 50 :: Integer +xRange = [0..49] :: [Integer] +boxSize = 100 :: Integer + + +-- part1 :: Machine -> Integer +-- part1 machine = beamPresence +part1 machine = sum $ map cellsInRange $ M.elems beamPresence + where beamPresence = foldl' (traceBeam machine) M.empty xRange -- [0..49] @[Integer] + -- cir = map cellsInRange $ M.elems beamPresence + + +part2 machine = score $ head $ dropWhile (not . containsBox) corners +-- part2 machine = corners + where uppers = scanl' (traceUpper machine) 0 xs + lowers = scanl' (traceLower machine) (0, 0) xs + corners = zip (drop ((fromIntegral boxSize) - 1) uppers) lowers + xs = [0..] :: [Integer] + +containsBox (yt, (_xb, yb)) = yt + boxSize - 1 <= yb + +score (yt, (xb, _yb)) = xb * 10000 + yt + + +cellsInRange :: Bounds -> Integer +cellsInRange (Bounds (u, l)) = l' - u' + where u' = min u maxY + l' = min l maxY + + +traceBeam :: Machine -> Beam -> Integer -> Beam +-- traceBeam _machine beam x | trace ((show x) ++ " " ++ (show beam)) False = undefined +traceBeam machine beam x = M.insert x (Bounds (u', l')) beam + where Bounds (prevU, _prevL) = M.findWithDefault (Bounds (0, 0)) (x - 1) beam + (bic, _foundU) = beamInColumn machine x + u = head $ dropWhile (\y -> not $ tractorBeamAt machine x y) [prevU..] + l = head $ dropWhile (\y -> tractorBeamAt machine x y) [u..] + (u', l') = if prevU == 0 && bic == False + then (0, 0) + else (u, l) + +traceUpper :: Machine -> Integer -> Integer -> Integer +traceUpper machine prev x = u' + where (bic, _foundU) = beamInColumn machine x + u = head $ dropWhile (\y -> not $ tractorBeamAt machine x y) [prev..] + u' = if prev == 0 && bic == False + then 0 + else u + +traceLower :: Machine -> (Integer, Integer) -> Integer -> (Integer, Integer) +traceLower machine (_, prev) x = (x, l') + where (bic, foundU) = beamInColumn machine x + startU = max prev foundU + l = head $ dropWhile (\y -> tractorBeamAt machine x y) [startU..] + l' = if prev == 0 && bic == False + then 0 + else l - 1 + +tractorBeamAt :: Machine -> Integer -> Integer -> Bool +tractorBeamAt machine x y = (head output) == 1 + where (_, _, output) = runMachine [x, y] machine + + +beamInColumn :: Machine -> Integer -> (Bool, Integer) +beamInColumn machine x + | null fromTop = (False, 0) + | otherwise = (True, head fromTop) + where fromTop = dropWhile (\y -> not $ tractorBeamAt machine x y) [0..maxY] + diff --git a/data/advent19.txt b/data/advent19.txt new file mode 100644 index 0000000..f62408e --- /dev/null +++ b/data/advent19.txt @@ -0,0 +1 @@ +109,424,203,1,21102,1,11,0,1106,0,282,21101,18,0,0,1105,1,259,2102,1,1,221,203,1,21101,0,31,0,1105,1,282,21101,0,38,0,1105,1,259,20101,0,23,2,21202,1,1,3,21101,0,1,1,21101,57,0,0,1105,1,303,1202,1,1,222,21002,221,1,3,21001,221,0,2,21102,1,259,1,21101,0,80,0,1105,1,225,21101,0,175,2,21102,1,91,0,1106,0,303,2101,0,1,223,21001,222,0,4,21102,259,1,3,21101,225,0,2,21102,1,225,1,21102,1,118,0,1105,1,225,21002,222,1,3,21101,70,0,2,21101,0,133,0,1105,1,303,21202,1,-1,1,22001,223,1,1,21102,1,148,0,1105,1,259,2102,1,1,223,21002,221,1,4,21002,222,1,3,21102,24,1,2,1001,132,-2,224,1002,224,2,224,1001,224,3,224,1002,132,-1,132,1,224,132,224,21001,224,1,1,21101,195,0,0,105,1,109,20207,1,223,2,21002,23,1,1,21101,0,-1,3,21102,1,214,0,1106,0,303,22101,1,1,1,204,1,99,0,0,0,0,109,5,2102,1,-4,249,21202,-3,1,1,22102,1,-2,2,21201,-1,0,3,21101,0,250,0,1106,0,225,21201,1,0,-4,109,-5,2105,1,0,109,3,22107,0,-2,-1,21202,-1,2,-1,21201,-1,-1,-1,22202,-1,-2,-2,109,-3,2105,1,0,109,3,21207,-2,0,-1,1206,-1,294,104,0,99,21202,-2,1,-2,109,-3,2106,0,0,109,5,22207,-3,-4,-1,1206,-1,346,22201,-4,-3,-4,21202,-3,-1,-1,22201,-4,-1,2,21202,2,-1,-1,22201,-4,-1,1,22101,0,-2,3,21101,343,0,0,1105,1,303,1105,1,415,22207,-2,-3,-1,1206,-1,387,22201,-3,-2,-3,21202,-2,-1,-1,22201,-3,-1,3,21202,3,-1,-1,22201,-3,-1,2,21201,-4,0,1,21101,0,384,0,1105,1,303,1105,1,415,21202,-4,-1,-4,22201,-4,-3,-4,22202,-3,-2,-2,22202,-2,-4,-4,22202,-3,-2,-3,21202,-4,-1,-2,22201,-3,-2,1,21201,1,0,-4,109,-5,2106,0,0 diff --git a/data/advent19a.txt b/data/advent19a.txt new file mode 100644 index 0000000..8881e0a --- /dev/null +++ b/data/advent19a.txt @@ -0,0 +1 @@ +3,20,3,21,2,21,22,24,1,24,20,24,9,24,204,25,99,0,0,0,0,0,40,35,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1 diff --git a/problems/day19.html b/problems/day19.html new file mode 100644 index 0000000..543f2d9 --- /dev/null +++ b/problems/day19.html @@ -0,0 +1,182 @@ + + + + +Day 19 - Advent of Code 2019 + + + + + + + +

Advent of Code

Neil Smith (AoC++) 38*

      /*2019*/

+ + + +
+ +

--- Day 19: Tractor Beam ---

Unsure of the state of Santa's ship, you borrowed the tractor beam technology from Triton. Time to test it out.

+

When you're safely away from anything else, you activate the tractor beam, but nothing happens. It's hard to tell whether it's working if there's nothing to use it on. Fortunately, your ship's drone system can be configured to deploy a drone to specific coordinates and then check whether it's being pulled. There's even an Intcode program (your puzzle input) that gives you access to the drone system.

+

The program uses two input instructions to request the X and Y position to which the drone should be deployed. Negative numbers are invalid and will confuse the drone; all numbers should be zero or positive.

+

Then, the program will output whether the drone is stationary (0) or being pulled by something (1). For example, the coordinate X=0, Y=0 is directly in front of the tractor beam emitter, so the drone control program will always report 1 at that location.

+

To better understand the tractor beam, it is important to get a good picture of the beam itself. For example, suppose you scan the 10x10 grid of points closest to the emitter:

+
       X
+  0->      9
+ 0#.........
+ |.#........
+ v..##......
+  ...###....
+  ....###...
+Y .....####.
+  ......####
+  ......####
+  .......###
+ 9........##
+
+

In this example, the number of points affected by the tractor beam in the 10x10 area closest to the emitter is 27.

+

However, you'll need to scan a larger area to understand the shape of the beam. How many points are affected by the tractor beam in the 50x50 area closest to the emitter? (For each of X and Y, this will be 0 through 49.)

+
+

Your puzzle answer was 169.

--- Part Two ---

You aren't sure how large Santa's ship is. You aren't even sure if you'll need to use this thing on Santa's ship, but it doesn't hurt to be prepared. You figure Santa's ship might fit in a 100x100 square.

+

The beam gets wider as it travels away from the emitter; you'll need to be a minimum distance away to fit a square of that size into the beam fully. (Don't rotate the square; it should be aligned to the same axes as the drone grid.)

+

For example, suppose you have the following tractor beam readings:

+
#.......................................
+.#......................................
+..##....................................
+...###..................................
+....###.................................
+.....####...............................
+......#####.............................
+......######............................
+.......#######..........................
+........########........................
+.........#########......................
+..........#########.....................
+...........##########...................
+...........############.................
+............############................
+.............#############..............
+..............##############............
+...............###############..........
+................###############.........
+................#################.......
+.................########OOOOOOOOOO.....
+..................#######OOOOOOOOOO#....
+...................######OOOOOOOOOO###..
+....................#####OOOOOOOOOO#####
+.....................####OOOOOOOOOO#####
+.....................####OOOOOOOOOO#####
+......................###OOOOOOOOOO#####
+.......................##OOOOOOOOOO#####
+........................#OOOOOOOOOO#####
+.........................OOOOOOOOOO#####
+..........................##############
+..........................##############
+...........................#############
+............................############
+.............................###########
+
+

In this example, the 10x10 square closest to the emitter that fits entirely within the tractor beam has been marked O. Within it, the point closest to the emitter (the only highlighted O) is at X=25, Y=20.

+

Find the 100x100 square closest to the emitter that fits entirely within the tractor beam; within that square, find the point closest to the emitter. What value do you get if you take that point's X coordinate, multiply it by 10000, then add the point's Y coordinate? (In the example above, this would be 250020.)

+
+

Your puzzle answer was 7001134.

Both parts of this puzzle are complete! They provide two gold stars: **

+

At this point, you should return to your Advent calendar and try another puzzle.

+

If you still want to see it, you can get your puzzle input.

+

You can also this puzzle.

+
+ + + + + + \ No newline at end of file diff --git a/stack.yaml b/stack.yaml index f4b4817..9ea2285 100644 --- a/stack.yaml +++ b/stack.yaml @@ -56,6 +56,7 @@ packages: - advent16 - advent17 - advent18 +- advent19 # Dependency packages to be pulled from upstream that are not in the resolver. -- 2.34.1