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
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..]
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