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

<https://adventofcode.com/2015/day/24>

>>> :{
:main +
"1
2
3
4
5
7
8
9
10
11
"
:}
99
44

-}
module Main (main) where

import Advent.Format (format)
import Advent (pickOne)
import Data.List (sortBy, sort, tails)
import Data.Ord (comparing)
import Advent.Queue (Queue)
import qualified Advent.Queue as Queue

-- order specifically chosen to get desired Ord instance
data Packages = Packages { Packages -> Int
pkgProduct, Packages -> Int
pkgSum :: !Int }
  deriving (Packages -> Packages -> Bool
(Packages -> Packages -> Bool)
-> (Packages -> Packages -> Bool) -> Eq Packages
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: Packages -> Packages -> Bool
== :: Packages -> Packages -> Bool
$c/= :: Packages -> Packages -> Bool
/= :: Packages -> Packages -> Bool
Eq, Eq Packages
Eq Packages =>
(Packages -> Packages -> Ordering)
-> (Packages -> Packages -> Bool)
-> (Packages -> Packages -> Bool)
-> (Packages -> Packages -> Bool)
-> (Packages -> Packages -> Bool)
-> (Packages -> Packages -> Packages)
-> (Packages -> Packages -> Packages)
-> Ord Packages
Packages -> Packages -> Bool
Packages -> Packages -> Ordering
Packages -> Packages -> Packages
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
$ccompare :: Packages -> Packages -> Ordering
compare :: Packages -> Packages -> Ordering
$c< :: Packages -> Packages -> Bool
< :: Packages -> Packages -> Bool
$c<= :: Packages -> Packages -> Bool
<= :: Packages -> Packages -> Bool
$c> :: Packages -> Packages -> Bool
> :: Packages -> Packages -> Bool
$c>= :: Packages -> Packages -> Bool
>= :: Packages -> Packages -> Bool
$cmax :: Packages -> Packages -> Packages
max :: Packages -> Packages -> Packages
$cmin :: Packages -> Packages -> Packages
min :: Packages -> Packages -> Packages
Ord, Int -> Packages -> ShowS
[Packages] -> ShowS
Packages -> String
(Int -> Packages -> ShowS)
-> (Packages -> String) -> ([Packages] -> ShowS) -> Show Packages
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> Packages -> ShowS
showsPrec :: Int -> Packages -> ShowS
$cshow :: Packages -> String
show :: Packages -> String
$cshowList :: [Packages] -> ShowS
showList :: [Packages] -> ShowS
Show)

noPackages :: Packages
noPackages :: Packages
noPackages = Packages
  { pkgSum :: Int
pkgSum     = Int
0
  , pkgProduct :: Int
pkgProduct = Int
1
  }

addPackage :: Int -> Packages -> Packages
addPackage :: Int -> Packages -> Packages
addPackage Int
p Packages
pkgs = Packages
  { pkgSum :: Int
pkgSum     = Packages -> Int
pkgSum   Packages
pkgs   Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
p
  , pkgProduct :: Int
pkgProduct = Packages -> Int
pkgProduct Packages
pkgs Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
p
  }

solve :: Int -> [Int] -> Int
solve :: Int -> [Int] -> Int
solve Int
n [Int]
input = Queue (Packages, [Int]) -> Int
go ((Packages, [Int]) -> Queue (Packages, [Int])
forall a. a -> Queue a
Queue.singleton (Packages
noPackages, [Int] -> [Int]
forall a. Ord a => [a] -> [a]
sort [Int]
input))
  where
    target :: Int
target = [Int] -> Int
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum [Int]
input Int -> Int -> Int
forall a. Integral a => a -> a -> a
`quot` Int
n

    go :: Queue (Packages, [Int]) -> Int
go = \case
      Queue (Packages, [Int])
Queue.Empty -> String -> Int
forall a. HasCallStack => String -> a
error String
"no solution"
      (Packages
pkg, [Int]
pkgs) Queue.:<| Queue (Packages, [Int])
q
        | Int
target Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Packages -> Int
pkgSum Packages
pkg -> Packages -> Int
pkgProduct Packages
pkg
        | Bool
otherwise -> Queue (Packages, [Int]) -> Int
go (Queue (Packages, [Int])
-> [(Packages, [Int])] -> Queue (Packages, [Int])
forall a. Queue a -> [a] -> Queue a
Queue.appendList Queue (Packages, [Int])
q [(Packages, [Int])]
more)
        where
          more :: [(Packages, [Int])]
more = [(Packages
pkg', [Int]
xs) | Int
x:[Int]
xs <- [Int] -> [[Int]]
forall a. [a] -> [[a]]
tails [Int]
pkgs, let pkg' :: Packages
pkg' = Int -> Packages -> Packages
addPackage Int
x Packages
pkg, then (a -> Bool) -> [a] -> [a]
(([Int], Packages) -> Bool)
-> [([Int], Packages)] -> [([Int], Packages)]
forall a. (a -> Bool) -> [a] -> [a]
takeWhile by Packages -> Int
pkgSum Packages
pkg' Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
target]

-- | Parse the input and print the solutions to both parts.
--
-- >>> :main
-- 11846773891
-- 80393059
main :: IO ()
IO ()
main =
 do input <- [format|2015 24 (%u%n)*|]
    print (solve 3 input)
    print (solve 4 input)