module Combinatorics.Battleship.Count.Estimate (
   overlapping,
   occupying,
   ) where

import qualified Combinatorics.Battleship.Fleet as Fleet

import qualified Data.NonEmpty as NonEmpty


overlapping :: (Int,Int) -> Fleet.T -> Integer
overlapping :: (Int, Int) -> T -> Integer
overlapping (Int
width,Int
height) =
   [Integer] -> Integer
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
product ([Integer] -> Integer) -> (T -> [Integer]) -> T -> Integer
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
   ((Int, Int) -> Integer) -> [(Int, Int)] -> [Integer]
forall a b. (a -> b) -> [a] -> [b]
map
      (\(Int
size,Int
count) ->
         (Int -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
height Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Int -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int -> Int -> Int
forall a. Ord a => a -> a -> a
max Int
0 (Int
widthInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
sizeInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)) Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+
          Int -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
width Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Int -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int -> Int -> Int
forall a. Ord a => a -> a -> a
max Int
0 (Int
heightInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
sizeInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)))
            Integer -> Int -> Integer
forall a b. (Num a, Integral b) => a -> b -> a
^ Int
count) ([(Int, Int)] -> [Integer])
-> (T -> [(Int, Int)]) -> T -> [Integer]
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
   T -> [(Int, Int)]
Fleet.toList


{-
This takes into account
that every ship occupies spaces that cannot be used for other ships anymore.
We reduce the available area ship by ship
and then estimate the number of remaining positions for each ship.
Unfortunately, we do not know the shape of the area -
it depends on the position of the placed ships.
We work-around this problem by selecting rectangles
that have at least the required area.
This leads to an upper bound, given that a shape of a certain area
provides a maximum of ship positions if it is rectangular.
-}
occupying :: (Int,Int) -> Fleet.T -> Integer
occupying :: (Int, Int) -> T -> Integer
occupying (Int
width,Int
height) T
fleet =
   let sizes :: [Int]
sizes = [Int] -> [Int]
forall a. [a] -> [a]
reverse ([Int] -> [Int]) -> [Int] -> [Int]
forall a b. (a -> b) -> a -> b
$ T -> [Int]
Fleet.toSizes T
fleet
   in  [Integer] -> Integer
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
product ([Integer] -> Integer) -> [Integer] -> Integer
forall a b. (a -> b) -> a -> b
$ (Int -> Integer) -> [Int] -> [Integer]
forall a b. (a -> b) -> [a] -> [b]
map Int -> Integer
forall a. Integral a => a -> Integer
toInteger ([Int] -> [Integer]) -> [Int] -> [Integer]
forall a b. (a -> b) -> a -> b
$
       (Int -> Int -> Int) -> [Int] -> [Int] -> [Int]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith ((Int -> Int -> Int) -> Int -> Int -> Int
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((Int -> Int -> Int) -> Int -> Int -> Int)
-> (Int -> Int -> Int) -> Int -> Int -> Int
forall a b. (a -> b) -> a -> b
$ (Int, Int) -> Int -> Int -> Int
maxPositionsInArea (Int
widthInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1,Int
heightInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)) [Int]
sizes ([Int] -> [Int]) -> [Int] -> [Int]
forall a b. (a -> b) -> a -> b
$
       (Int -> Int -> Int) -> Int -> [Int] -> [Int]
forall b a. (b -> a -> b) -> b -> [a] -> [b]
scanl (-) ((Int
widthInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)Int -> Int -> Int
forall a. Num a => a -> a -> a
*(Int
heightInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1)) ([Int] -> [Int]) -> [Int] -> [Int]
forall a b. (a -> b) -> a -> b
$
       (Int -> Int) -> [Int] -> [Int]
forall a b. (a -> b) -> [a] -> [b]
map (\Int
size -> Int
2Int -> Int -> Int
forall a. Num a => a -> a -> a
*(Int -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
size Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)) [Int]
sizes

maxPositionsInArea :: (Int,Int) -> Int -> Int -> Int
maxPositionsInArea :: (Int, Int) -> Int -> Int -> Int
maxPositionsInArea (Int
maxWidth,Int
maxHeight) Int
area Int
size =
   T [] Int -> Int
forall a (f :: * -> *). (Ord a, Foldable f) => T f a -> a
NonEmpty.maximum (T [] Int -> Int) -> T [] Int -> Int
forall a b. (a -> b) -> a -> b
$ Int -> [Int] -> T [] Int
forall a (f :: * -> *). a -> f a -> T f a
NonEmpty.cons Int
0 ([Int] -> T [] Int) -> [Int] -> T [] Int
forall a b. (a -> b) -> a -> b
$
   ((Int, Int) -> [Int]) -> [(Int, Int)] -> [Int]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap
      (\(Int
width,Int
height) -> [(Int
widthInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
size)Int -> Int -> Int
forall a. Num a => a -> a -> a
*(Int
heightInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1), (Int
widthInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)Int -> Int -> Int
forall a. Num a => a -> a -> a
*(Int
heightInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
size)]) ([(Int, Int)] -> [Int]) -> [(Int, Int)] -> [Int]
forall a b. (a -> b) -> a -> b
$
   ((Int, Int) -> Bool) -> [(Int, Int)] -> [(Int, Int)]
forall a. (a -> Bool) -> [a] -> [a]
filter
      (\(Int
width,Int
height) ->
         Int
widthInt -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<=Int
maxWidth Bool -> Bool -> Bool
&& Int
heightInt -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<=Int
maxHeight
         Bool -> Bool -> Bool
||
         Int
heightInt -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<=Int
maxWidth Bool -> Bool -> Bool
&& Int
widthInt -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<=Int
maxHeight) ([(Int, Int)] -> [(Int, Int)]) -> [(Int, Int)] -> [(Int, Int)]
forall a b. (a -> b) -> a -> b
$
   Int -> [(Int, Int)]
rectangles Int
area

rectangles :: Int -> [(Int,Int)]
rectangles :: Int -> [(Int, Int)]
rectangles Int
area =
   ((Int, Int) -> Bool) -> [(Int, Int)] -> [(Int, Int)]
forall a. (a -> Bool) -> [a] -> [a]
takeWhile ((Int -> Int -> Bool) -> (Int, Int) -> Bool
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
(<=)) ([(Int, Int)] -> [(Int, Int)]) -> [(Int, Int)] -> [(Int, Int)]
forall a b. (a -> b) -> a -> b
$ (Int -> (Int, Int)) -> [Int] -> [(Int, Int)]
forall a b. (a -> b) -> [a] -> [b]
map (\Int
a -> (Int
a, Int -> Int -> Int
forall a. Integral a => a -> a -> a
divUp Int
area Int
a)) [Int
2..]

-- cf. numeric-prelude:Algebra.IntegralDomain.divUp
divUp :: (Integral a) => a -> a -> a
divUp :: a -> a -> a
divUp a
n a
m = - a -> a -> a
forall a. Integral a => a -> a -> a
div (-a
n) a
m