battleship-combinatorics-0.0: Compute number of possible arrangements in the battleship game

Safe HaskellNone
LanguageHaskell98

Combinatorics.Battleship.Count.ShortenShip

Contents

Description

In this approach I construct the board row by row from the bottom to the top. In every step I maintain the necessary information in order to know, what ships and positions and orientations are allowed in the next row. This information is stored in the Frontier.

possible optimization: "meet in the middle" compute counts for 5x10 boards and put them together, problem: for a given frontier there are many other half boards that may match

Synopsis

Documentation

type CountMap w = T w Count Source #

count all possible fleets on a board with given width

asumTakeFrontier :: (Nat w, Alternative f) => T w -> Position -> Size w -> [f a] -> f a Source #

widthRange :: Nat w => Size w -> [Int] Source #

atEnd :: Size w -> Int -> Bool Source #

newShip :: T -> T -> ShipSize -> StateT (T w, T) [] () Source #

insertVertical :: Nat w => T -> Int -> Position -> StateT (T w, T) [] () Source #

nextFrontier :: Nat w => Size w -> CountMap w -> CountMap w Source #

In this approach, the fleet contains all ships also the ones at the frontier.

transitionFrontier :: Nat w => Size w -> T w -> T -> [(T w, T)] Source #

count :: Nat w => (Size w, Int) -> T -> Count Source #

count fleets with an upper bound

nextFrontierBounded :: Nat w => Size w -> T -> CountMap w -> CountMap w Source #

Here we save memory and speed up the computation in the following way: We stop searching deeper if

  1. the fleet becomes larger than the requested fleet ("larger" means, that for at least one ship size the number of ships is larger than in the requested fleet)
  2. the cumulated fleet becomes larger than the cumulated requested fleet This is necessary, since we do not know the final length of the vertical ships at the frontier.

In this approach, the fleet does not contain the vertical ships at the frontier.

transitionFrontierBounded :: Nat w => Size w -> T -> T w -> T -> [(T w, T)] Source #

countBounded :: Nat w => (Size w, Int) -> T -> Count Source #

nextFrontierTouching :: Nat w => Size w -> T -> CountMap w -> CountMap w Source #

This solves a different problem. In this variant the ships are allowed to touch each other.

transitionFrontierTouching :: Nat w => Size w -> T -> T w -> T -> [(T w, T)] Source #

countTouching :: Nat w => (Size w, Int) -> T -> Count Source #

canonicalFrontier :: Nat w => T w -> T w Source #

mergeSymmetricFrontiers :: Nat w => [(T w, fleet)] -> [(T w, fleet)] Source #

retrieve counts from count maps

countBoundedFromMap :: (C a, Storable a) => T -> T w a -> a Source #

tmpPath :: Int -> Path w a Source #

countExternalGen :: (C a, Storable a) => CountMap w -> (T -> Path w a -> T w a -> IO ()) -> Int -> T -> IO a Source #

reportCounts :: (C a, Storable a, Show a) => CountMap w -> (T -> Path w a -> T w a -> IO ()) -> Int -> T -> IO () Source #