Part A is a simple 2SUM. We use Vector to speed up computation due to Part B.
solveA :: Vector Integer -> Integer
solveA = V.last . V.head . V.filter (not . isValid) . questions 25
questions :: Int -> Vector a -> Vector (Vector a)
questions l v = fmap (V.take (l + 1)) . iterateN (V.length v + 1 - l) V.tail $ v
isValid :: Vector Integer -> Bool
isValid v = if null v then False
else q - x `elem` pre || isValid vs
where l = V.length v - 1
(x, (vs, q)) = (V.head &&& V.tail &&& V.last) v
pre = V.take (l - 1) vs
We use Arrows here simply to make our computation look nicer and not apply functions to v everywhere in our tuple.
(&&&) :: (a -> b) -> (a -> c) -> a -> (b, c) is a nice combinator to use.
For Part B, we generate a list of prefix sums and then check for contiguous regions that sum to the target. Once we do,
we grab the Vector slice and sum the minimum and maximum values.
solveB :: Vector Integer -> Integer
solveB nums = head $ uncurry (+) . (minimum &&& maximum) . subl nums <$> regions
where target = solveA nums
ps = V.scanl (+) 0 nums
regions = filter ((==(-target)) . uncurry (-) . ((ps!) *** (ps!))) (pairs l)
subl v (i, j) = slice i (j - i) v
l = length nums
pairs :: Int -> [(Int, Int)]
pairs l = [(i, j) | i <- [0..l], j <- [i + 1..l]]
By using Vector instead of [], we are able to reduce our running time to 13ms with Integer (8ms with Int) vs
550ms with Int. Those O(1) lookups are important. Additionally, (***) :: (a1 -> b1) -> (a2 -> b2) -> (a1, a2) -> (b1,
b2) is another nice little combinator from Control.Arrow.