Rubik.Cube.Coord

Encoding cube projections as Int coordinates.

Explicit dictionary passing style: using a class would require explicit type annotations anyway.

Raw coordinates

type RawCoord' = Int

newtype RawCoord a

Encoding to an efficient datatype for which it is possible to build tables instead of computing functions.

Constructors

RawCoord

Fields

unRawCoord :: RawCoord'

Instances

Eq (RawCoord a)

Ord (RawCoord a)

Show (RawCoord a)

NFData (RawCoord a)

Binary (RawCoord a)

Newtype (RawCoord a) Int

newtype RawVector a b

Constructors

RawVector

Fields

unRawVector :: Vector b

newtype RawMove a

Constructors

RawMove

Fields

unRawMove :: Vector RawCoord'

Instances

Eq (RawMove a)

Ord (RawMove a)

Show (RawMove a)

NFData (RawMove a)

Binary (RawMove a)

Newtype (RawMove a) (Vector Int)

(!$) :: RawMove a -> RawCoord a -> RawCoord a

(!.) :: Unbox b => RawVector a b -> RawCoord a -> b

Dictionaries

class RawEncodable a where

Encoding dictionary.

Probably synonymous with instances for both (Enum a, Bounded a).

inRange (range d) $ encode x
encode . decode == id
decode . encode == id

A special constructor for dictionaries of product types is particularly useful to create tables of functions if their actions on every projection are independent.

Methods

range :: proxy a -> Int

Number of elements that can be converted. Their values are to lie in [0 .. range c - 1].

encode :: a -> RawCoord a

decode :: RawCoord a -> a

Instances

RawEncodable UDEdgePermu2

8! = 40320

RawEncodable UDSlicePermu2

4! = 24

RawEncodable UDSlice

12C4 = 495

RawEncodable UDSlicePermu

12! / 8! = 11880

RawEncodable EdgeOrien

2^11 = 2048

RawEncodable EdgePermu

12! = 479001600

A bit too much to hold in memory.

Holds just right in a Haskell Int (maxInt >= 2^29 - 1).

RawEncodable CornerOrien

3^7 = 2187

RawEncodable CornerPermu

The number of elements of every set is given.

8! = 40320

(RawEncodable a, RawEncodable b) => RawEncodable (a, b)

Instances

encodeEdgeOrien' :: Vector Int -> Int

numUDS :: Int

numUDE :: Int

flatCoord :: (RawEncodable a, RawEncodable b) => RawCoord a -> RawCoord b -> RawCoord (a, b)

splitCoord :: (RawEncodable a, RawEncodable b) => RawCoord (a, b) -> (RawCoord a, RawCoord b)

Table building

type Endo a = a -> a

Endofunctions

endoVector :: RawEncodable a => Endo a -> RawMove a

Lift an endofunction to its coordinate representation, the dictionary provides a RawCoord encoding.

That is, we construct a vector v such that, basically,

decode (v ! encode x) == f x

So function application becomes simply vector indexing.

cubeActionToEndo :: CubeAction a => Cube -> Endo a

The cubeAction method is partially applied to a Cube and turned into an Endo function.

The 'CA a' type argument controls the refinement of the endofunction.

moveTable :: (CubeAction a, RawEncodable a) => Cube -> RawMove a

Composition of endoVector and cubeAction.

symToEndo :: (Cube -> a -> a) -> Cube -> Endo a

symTable :: RawEncodable a => (Cube -> a -> a) -> Cube -> RawMove a

Miscellaneous

checkCoord :: RawEncodable a => proxy a -> Bool

Checks over the range range that:

encode . decode == id

randomRawCoord :: forall a m. (MonadRandom m, RawEncodable a) => m (RawCoord a)

Helper

Fixed base

encodeBase :: Int -> [Int] -> Int

If all (elem [0 .. b-1]) v then v is the base b representation of encode b v such that its least significant digit is head v.

For any n, encodeBase b is a bijection from lists of length n with elements in [0 .. b-1] to [0 .. b^n - 1]

encodeBaseV :: Int -> Vector Int -> Int

Vector version of encodeBase.

decodeBase :: Int -> Int -> Int -> [Int]

len is the length of the resulting vector

encodeBase b . decodeBase b len == id
decodeBase b len . encodeBase b == id

Factorial radix

encodeFact :: Int -> [Int] -> Int

Input list must be a k-permutation of [0 .. n-1].

encodeFact is a bijection between k-permutations of [0 .. n-1] and [0 .. (fact n / fact (n-k)) - 1].

decodeFact :: Int -> Int -> Int -> [Int]

Inverse of encodeFact.

encodeFact n . decodeFact n k == id -- k <= n
decodeFact n k . encodeFact n == id -- on k-permutations

Binomial enumeration

cSum :: Int -> Int -> Int

cSum k z == sum [y `choose` k | y <- [k .. z-1]]

requires k < cSum_mMaz and z < cSum_nMaz.

cSum_mMax :: Int

Bound on arguments accepted by cSum

cSum_nMax :: Int

Bound on arguments accepted by cSum

encodeCV :: Vector Int -> Int

encodeCV <y 0 .. y k> == encodeCV <y 0 .. y (k-1)> + cSum k (y k)

where c is a k-combination, that is a sorted list of k nonnegative elements.

encodeCV is in fact a bijection between increasing lists (of non-negative integers) and integers.

Restriction: k < cSum_mMax, y k < cSum_nMax.

decodeCV :: Int -> Int -> Vector Int

Inverse of encodeCV.

The length of the resulting list must be supplied as a hint (although it could technically be guessed).