{-# Language QuasiQuotes #-}
{-|
Module      : Main
Description : Day 17 solution
Copyright   : (c) Eric Mertens, 2021
License     : ISC
Maintainer  : emertens@gmail.com

<https://adventofcode.com/2021/day/17>

Launch probes to hit a target.

This solution relies on the target being in quadrant IV.
You could do the math for the other quadrants, but I didn't
bother!

Boundary conditions:

* x velocity must be non-negative to hit things
  in quadrant IV
* x velocity must not be more than @xhi@ or the
  probe will miss on the first timestep.
* y velocity can't be more than @ylo@ or it will
  miss on the first time step.
* y velocity can't be more than @-ylo@ or it will
  skip right past the target on its way back down.

-}
module Main (main) where

import Advent.Format (format)
import Control.Monad (when)

-- | The state of a traveling probe
data Probe = P !Int !Int !Int !Int -- ^ x-position y-position x-velocity y-velocity
  deriving Int -> Probe -> ShowS
[Probe] -> ShowS
Probe -> String
(Int -> Probe -> ShowS)
-> (Probe -> String) -> ([Probe] -> ShowS) -> Show Probe
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> Probe -> ShowS
showsPrec :: Int -> Probe -> ShowS
$cshow :: Probe -> String
show :: Probe -> String
$cshowList :: [Probe] -> ShowS
showList :: [Probe] -> ShowS
Show

-- | Advance the probe one timestep
step :: Probe -> Probe
step :: Probe -> Probe
step (P Int
x Int
y Int
vx Int
vy) = Int -> Int -> Int -> Int -> Probe
P (Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
vx) (Int
yInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
vy) (Int
vxInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int -> Int
forall a. Num a => a -> a
signum Int
vx) (Int
vyInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)

-- | >>> :main
-- 10585
-- 5247
main :: IO ()
IO ()
main =
  do (Int
xlo,Int
xhi,Int
ylo,Int
yhi) <- [format|2021 17 target area: x=%d..%d, y=%d..%d%n|]
     Bool -> IO () -> IO ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int
xlo Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 Bool -> Bool -> Bool
|| Int
yhi Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0) (String -> IO ()
forall a. String -> IO a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"I didn't do enough math for this case")

     let ys :: [Int]
ys = [Int
y | Int
vx <- [Int
0 .. Int
xhi], Int
vy <- [Int
ylo .. -Int
ylo], Just Int
y <- [Int -> Int -> Int -> Int -> Int -> Int -> Maybe Int
sim Int
xlo Int
xhi Int
ylo Int
yhi Int
vx Int
vy]]
     Int -> IO ()
forall a. Show a => a -> IO ()
print ([Int] -> Int
forall a. Ord a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
maximum [Int]
ys)
     Int -> IO ()
forall a. Show a => a -> IO ()
print ([Int] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length  [Int]
ys)

-- | Run a simulation returning the maximum height seen if
-- the probe ever succeeds in hitting the target.
--
-- >>> sim 20 30 (-10) (-5) 6 9
-- Just 45
sim ::
  Int {- ^ target x lo -} ->
  Int {- ^ target x hi -} ->
  Int {- ^ target y lo -} ->
  Int {- ^ target y hi -} ->
  Int {- ^ initial x velocity -} ->
  Int {- ^ initial y velocity -} ->
  Maybe Int {- ^ maximum height if successful -}
sim :: Int -> Int -> Int -> Int -> Int -> Int -> Maybe Int
sim Int
xlo Int
xhi Int
ylo Int
yhi Int
vx0 Int
vy0 = Int -> Probe -> Maybe Int
go Int
0 (Int -> Int -> Int -> Int -> Probe
P Int
0 Int
0 Int
vx0 Int
vy0)
  where
    go :: Int -> Probe -> Maybe Int
go Int
best p :: Probe
p@(P Int
x Int
y Int
_ Int
_)
      | Int
y Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
ylo Bool -> Bool -> Bool
|| Int
x Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
xhi                     = Maybe Int
forall a. Maybe a
Nothing -- too far
      | Int
xlo Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
x, Int
x Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
xhi, Int
ylo Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
y, Int
y Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
yhi = Int -> Maybe Int
forall a. a -> Maybe a
Just Int
best
      | Bool
otherwise                              = Int -> Probe -> Maybe Int
go (Int -> Int -> Int
forall a. Ord a => a -> a -> a
max Int
y Int
best) (Probe -> Probe
step Probe
p)