project-euler/common.fs

module common

let allIntegers = Seq.unfold(fun i -> Some(i, i + 1)) 0

let allSquares = Seq.unfold(fun (square,odd) -> Some(square, (square+odd, odd+2))) (0,1)

let multiples n =
    let rec m ns =
        seq { 
            yield ns
            yield! m (ns + n)
        }
    m n

let divisorsWithRule rule len = 
    let d = Array.create (len + 1) [] // stores the divisors for each number by index
    seq {1..len} |> Seq.iter (fun i -> 
        seq { i .. i .. len } |> Seq.iter ( fun j ->
            if rule i j then d.[j] <- i :: d.[j]
            )
        )
    d

let divisors = divisorsWithRule (<>)
let divisorsInclSelf = divisorsWithRule (fun _ _ -> true)

let rec gcd(a,b) =
    if b > a then gcd (b,a) else
    match b with
    | 0 -> a
    | b -> gcd (b, a%b)

let rec gcdI(a:bigint,b:bigint) =
    if b > a then gcdI (b,a) else
    match b with
    | b when b = 0I -> a
    | b -> gcdI (b, a%b)

let primeArray max = 
    let d = Array.init (max + 1) (fun i -> i)
    seq {2..(max/2)} |> Seq.iter (fun i -> 
        seq { 0 .. i .. max } |> Seq.iter ( fun j ->
            if i <> j && j <> 0 then d.[j] <- -1
            )
        )
    d |> Array.filter ((<) 1)

let isPrimeFunByArray primes =
    let primeLookup =
        primes |> Array.map (fun p -> (p, true)) |> dict
    (fun n -> primeLookup.ContainsKey(n))

let isPrimeFunByMax max =
    primeArray max |> isPrimeFunByArray

let isPrimeI n =
    if n < 2I then false
    else
        let limit = float n |> sqrt |> fun x -> x + 1. |> (fun n -> bigint n)
        let rec loop d =
            match d with
            | limit -> true
            | d when n % d = 0I -> false
            | _ -> loop (d + 1I)
        loop 2I

let compositeArray max =
    let primes = primeArray max
    primes
    |> Seq.pairwise
    |> Seq.collect (fun (p1, p2) -> 
        seq { (p1+1) .. (p2 - 1) }
    )

let coprimeArray len =
    let c = Array.create (len + 1) []
    let d = divisors len
    d.[1] <- [1]
    let set1 = Set [1]
    for i in 2 .. len do
        let dis = Set d.[i]
        for j in 1 .. (i - 1) do
            //if not (Set.contains j dis) then
                let djs = Set d.[j]
                if Set.intersect dis djs = set1 then
                    c.[i] <- j :: c.[i]
    c


let crossMapList l1 l2 =
  seq { for el1 in l1 do
          for el2 in l2 do
            yield (el1, el2) }

let crossSelfMapList l =
  crossMapList l l

let crossMap f l1 l2 =
    crossMapList l1 l2 |> Seq.map (fun (el1, el2) -> f el1 el2)

let crossSelfMap f l =
  crossMap f l l

let rec permutations set =
    seq { 
        if Set.empty = set then yield [] else
        for s in set do
            let remaining = set |> Set.remove s
            for perm in (permutations remaining) do
                yield s :: perm
    }

let rec slottedPermutations slots =
    seq { 
        if List.empty = slots then yield [] else
        let set = List.head slots
        for s in set do
            for perm in (slottedPermutations (List.tail slots)) do
                yield s :: perm
    }

let combinations size set = 
    let rec combinations acc size set = seq {
        match size, set with 
        | n, x::xs -> 
            if n > 0 then yield! combinations (x::acc) (n - 1) xs
            if n >= 0 then yield! combinations acc n xs 
        | 0, [] -> yield acc 
        | _, [] -> () }
    combinations [] size (set |> List.ofSeq)

let fibinoci =
    let rec f (c, p) =
        seq { 
            yield c
            yield! f (c + p, c)
        }
    f (1I,0I)

let digitCount n =
    int (System.Math.Floor(System.Math.Log10 (float n)) + 1.0)

let mapChars f n =
    (string n).ToCharArray()
    |> Array.map f

let joinStrings =
    Array.map string
    >> Array.fold (fun acc i -> i + acc) ""

let numDigits =
    mapChars (string >> int)

let digitsNum (ds:int[]) =
    ds
    |> joinStrings
    |> int

let lastDigits d n =
    let s = string n
    s.Substring(s.Length - d)

let rec factorial n =
    match n with
    | 0 
    | 1 -> 1
    | _ -> n * factorial (n - 1)

let rec factorialI n =
    match n with
    | n when n = 0I -> 1I
    | n when n = 1I -> 1I
    | _ -> n * factorialI (n - 1I)

let takeIndexes ns input = 
    // Take only elements that we need to access (sequence could be infinite)
    let arr = input |> Seq.take (1 + Seq.max ns) |> Array.ofSeq
    // Simply pick elements at the specified indices from the array
    seq { for index in ns -> arr.[index] }

let arrayToRevSeq a =
    let len = (Array.length a) - 1
    seq {
        for i in len .. -1 .. 0  do
            yield a.[i]
    }

let array2DFromNested a =
    Array2D.init (Array.length a) (Array.length a.[0]) (fun i j -> a.[i].[j])

let strSplit t (str:string) = str.Split(',') |> Array.map t
let strSplitInt = strSplit int
let strSplitFloat = strSplit float

let isPanDigitalD digits =
    let len = Seq.length digits
    let range = Seq.forall (fun d -> d <= len && d > 0) digits
    let unique = Set.count (Set digits) = len
    range && unique

let isPanDigital n =
    isPanDigitalD (numDigits n)

let isPanDigitalGroup s =
    Seq.collect numDigits s |> isPanDigitalD

let letterValue (c:char) =
    int c - 64

let wordValue (w:string) =
    w.ToUpper()
    |> Seq.map letterValue
    |> Seq.sum

let floatWrap f n =
    let n = float n
    f n |> int64 |> (fun n -> bigint n)

let triangleNumber n =
    n |> floatWrap (fun n -> n / 2.0 * (n + 1.0))

let pentagonalNumber n =
    n |> floatWrap (fun n -> n / 2.0 * (3.0 * n - 1.0))

let hexagonalNumber n =
    n |> floatWrap (fun n -> n * (2.0 * n - 1.0))

let revString s =
    new string (s |> Seq.toArray |> Array.rev)

let isPalindrome s =
    s = revString s