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

<https://adventofcode.com/2020/day/9>

-}
module Main (main) where

import Advent.Format (format)
import Data.Vector.Unboxed (Vector)
import Data.Vector.Unboxed qualified as V

-- |
-- >>> :main
-- 18272118
-- 2186361
main :: IO ()
IO ()
main =
  do [Int]
inp <- [format|2020 9 (%d%n)*|]
     let v :: Vector Int
v = [Int] -> Vector Int
forall a. Unbox a => [a] -> Vector a
V.fromList [Int]
inp

     let target :: Int
target = Vector Int -> Int
part1 Vector Int
v
     Int -> IO ()
forall a. Show a => a -> IO ()
print Int
target

     let range :: Vector Int
range = Vector Int -> Int -> Int -> Vector Int
part2 Vector Int
v Int
0 Int
target
     Int -> IO ()
forall a. Show a => a -> IO ()
print (Vector Int -> Int
forall a. (Unbox a, Ord a) => Vector a -> a
V.minimum Vector Int
range Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Vector Int -> Int
forall a. (Unbox a, Ord a) => Vector a -> a
V.maximum Vector Int
range)

-- | Returns 'True' when no pair of numbers exists in the vector that
-- sums up to the given target value.
search :: Int -> Vector Int -> Bool
search :: Int -> Vector Int -> Bool
search Int
target Vector Int
haystack = [Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
and
  [ Vector Int
haystack Vector Int -> Int -> Int
forall a. Unbox a => Vector a -> Int -> a
V.! Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Vector Int
haystack Vector Int -> Int -> Int
forall a. Unbox a => Vector a -> Int -> a
V.! Int
j Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
target
  | Int
i <- [Int
0   .. Vector Int -> Int
forall a. Unbox a => Vector a -> Int
V.length Vector Int
haystack Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
2]
  , Int
j <- [Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1 .. Vector Int -> Int
forall a. Unbox a => Vector a -> Int
V.length Vector Int
haystack Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1]
  ]

-- | Find a number in the vector that is /not/ the sum of any pair of
-- numbers in the 25 elements preceding it.
part1 :: Vector Int -> Int
part1 :: Vector Int -> Int
part1 Vector Int
v
  | Int -> Vector Int -> Bool
search (Vector Int
v Vector Int -> Int -> Int
forall a. Unbox a => Vector a -> Int -> a
V.! Int
25) (Int -> Vector Int -> Vector Int
forall a. Unbox a => Int -> Vector a -> Vector a
V.take Int
25 Vector Int
v) = Vector Int
v Vector Int -> Int -> Int
forall a. Unbox a => Vector a -> Int -> a
V.! Int
25
  | Bool
otherwise = Vector Int -> Int
part1 (Vector Int -> Vector Int
forall a. Unbox a => Vector a -> Vector a
V.tail Vector Int
v)

-- | Find a contiguous subsequence of the given vector that sums to
-- the given target.
part2 ::
  Vector Int {- ^ remaining elements                -} ->
  Int         {- ^ leading elements used             -} ->
  Int         {- ^ remaining target value            -} ->
  Vector Int {- ^ subsequence matching target value -}
part2 :: Vector Int -> Int -> Int -> Vector Int
part2 Vector Int
v Int
n Int
acc =
  case Int -> Int -> Ordering
forall a. Ord a => a -> a -> Ordering
compare Int
acc Int
0 of
    Ordering
EQ | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
1 -> Int -> Vector Int -> Vector Int
forall a. Unbox a => Int -> Vector a -> Vector a
V.take Int
n Vector Int
v                              -- done
    Ordering
GT         -> Vector Int -> Int -> Int -> Vector Int
part2 Vector Int
v          (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (Int
acc Int -> Int -> Int
forall a. Num a => a -> a -> a
- Vector Int
v Vector Int -> Int -> Int
forall a. Unbox a => Vector a -> Int -> a
V.! Int
n)  -- use another element
    Ordering
_          -> Vector Int -> Int -> Int -> Vector Int
part2 (Vector Int -> Vector Int
forall a. Unbox a => Vector a -> Vector a
V.tail Vector Int
v) (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) (Int
acc Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Vector Int -> Int
forall a. Unbox a => Vector a -> a
V.head Vector Int
v) -- stop using an element