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

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

-}
module Main where

import Advent.Format (format)
import Data.List (sortBy, sort)
import Data.Maybe (listToMaybe)
import Data.Ord (comparing)

data Packages = Packages { Packages -> Int
pkgSum, Packages -> Int
pkgCount, Packages -> Int
pkgProduct :: !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, 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
  { pkgCount :: Int
pkgCount = Int
0
  , pkgSum :: Int
pkgSum = Int
0
  , pkgProduct :: Int
pkgProduct = Int
1
  }

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

instance Ord Packages where
  compare :: Packages -> Packages -> Ordering
compare = (Packages -> Int) -> Packages -> Packages -> Ordering
forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing Packages -> Int
pkgCount (Packages -> Packages -> Ordering)
-> (Packages -> Packages -> Ordering)
-> Packages
-> Packages
-> Ordering
forall a. Semigroup a => a -> a -> a
<> (Packages -> Int) -> Packages -> Packages -> Ordering
forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing Packages -> Int
pkgProduct (Packages -> Packages -> Ordering)
-> (Packages -> Packages -> Ordering)
-> Packages
-> Packages
-> Ordering
forall a. Semigroup a => a -> a -> a
<> (Packages -> Int) -> Packages -> Packages -> Ordering
forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing Packages -> Int
pkgSum

search :: Int -> [Int] -> Maybe Int
search :: Int -> [Int] -> Maybe Int
search Int
n [Int]
ps0 = [Int] -> Maybe Int
forall a. [a] -> Maybe a
listToMaybe ([Int] -> Maybe Int) -> [Int] -> Maybe Int
forall a b. (a -> b) -> a -> b
$
  do (Packages
pkg,[Int]
ps1) <- ((Packages, [Int]) -> (Packages, [Int]) -> Ordering)
-> [(Packages, [Int])] -> [(Packages, [Int])]
forall a. (a -> a -> Ordering) -> [a] -> [a]
sortBy (((Packages, [Int]) -> Packages)
-> (Packages, [Int]) -> (Packages, [Int]) -> Ordering
forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing (Packages, [Int]) -> Packages
forall a b. (a, b) -> a
fst) ([Int] -> [(Packages, [Int])]
start [Int]
ps0)
     Int -> [Int] -> [()]
forall {t}. (Eq t, Num t) => t -> [Int] -> [()]
moreGroups (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) [Int]
ps1
     Int -> [Int]
forall a. a -> [a]
forall (m :: * -> *) a. Monad m => a -> m a
return (Packages -> Int
pkgProduct Packages
pkg)
     
  where
  goal :: Int
goal = [Int] -> Int
forall a. Num a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum [Int]
ps0 Int -> Int -> Int
forall a. Integral a => a -> a -> a
`quot` Int
n

  moreGroups :: t -> [Int] -> [()]
moreGroups t
1 [Int]
_ = [()]
  moreGroups t
i [Int]
ps1 =
    do (Packages
_,[Int]
ps2) <- [Int] -> [(Packages, [Int])]
start [Int]
ps1
       t -> [Int] -> [()]
moreGroups (t
it -> t -> t
forall a. Num a => a -> a -> a
-t
1) [Int]
ps2

  start :: [Int] -> [(Packages, [Int])]
start = Packages -> [Int] -> [Int] -> [(Packages, [Int])]
aux Packages
noPackages [] ([Int] -> [(Packages, [Int])])
-> ([Int] -> [Int]) -> [Int] -> [(Packages, [Int])]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Int] -> [Int]
forall a. Ord a => [a] -> [a]
sort

  aux :: Packages -> [Int] -> [Int] -> [(Packages,[Int])]
  aux :: Packages -> [Int] -> [Int] -> [(Packages, [Int])]
aux Packages
a [Int]
qs [Int]
_ | Packages -> Int
pkgSum Packages
a Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
goal = [(Packages
a,[Int]
qs)]
  aux Packages
_ [Int]
_ [] = []
  aux Packages
a [Int]
_ (Int
p:[Int]
_) | Packages -> Int
pkgSum (Int -> Packages -> Packages
addPackage Int
p Packages
a) Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
goal = []
  aux Packages
a [Int]
qs (Int
p:[Int]
ps) = Packages -> [Int] -> [Int] -> [(Packages, [Int])]
aux (Int -> Packages -> Packages
addPackage Int
p Packages
a) [Int]
qs [Int]
ps
                 [(Packages, [Int])] -> [(Packages, [Int])] -> [(Packages, [Int])]
forall a. [a] -> [a] -> [a]
++ Packages -> [Int] -> [Int] -> [(Packages, [Int])]
aux Packages
a (Int
pInt -> [Int] -> [Int]
forall a. a -> [a] -> [a]
:[Int]
qs) [Int]
ps

main :: IO ()
IO ()
main =
  do [Int]
input <- [format|2015 24 (%u%n)*|]
     Maybe Int -> IO ()
forall a. Show a => a -> IO ()
print (Int -> [Int] -> Maybe Int
search Int
3 [Int]
input)
     Maybe Int -> IO ()
forall a. Show a => a -> IO ()
print (Int -> [Int] -> Maybe Int
search Int
4 [Int]
input)