Algorithms.fsx

// sieve
let sieve (n:int64) =
    let rec aux (list: int64 list) = 
        match list with
        | [] -> []
        | hd::_ -> hd::aux (list |> List.filter (fun x -> x % hd <> 0L) )
    [2L .. n] |> aux

InteviewQuestions.fsx

// https://www.reddit.com/r/cscareerquestions/comments/20ahfq/heres_a_pretty_big_list_of_programming_interview/

// Find the most frequent integer in an array

let findMostFrequent arr =
    arr
    |> List.countBy (id)
    |> List.sortByDescending (snd)
    |> List.head
    |> fst

findMostFrequent [3;4;5;3;5;3;3;3;2;3]

// Find pairs in an integer array whose sum is equal to 10 (bonus: do it in linear time)
let rec removeItem acc arr item = 
    match arr with
    | x::xs -> if x = item then acc @ xs else x::removeItem acc xs item
    | [] -> acc


let rec removeFirst pred arr =
    match arr with
    | x::xs when pred x -> xs
    | x::xs -> x::removeFirst pred xs
    //| _ -> []

removeFirst (fun x -> x = 4) [2;2;3;3;4;4;5;5]
let findPairsSum10 arr =
    let getPairItem item arr =
        let maybePair = arr |> List.tryFind(fun x -> x = 10 - item)
        match maybePair with
        | Some pairItem -> 
            let newarr = removeFirst (fun x -> x = pairItem) arr
            (Some pairItem, newarr)
        | None -> (None, arr)

    let rec findPair acc arr =
        match arr with
        | x::xs -> 
            let maybePairItem = getPairItem x xs
            match maybePairItem with
            | Some pairItem, newarr -> findPair ((x, pairItem)::acc) newarr
            | None _, newarr -> findPair acc newarr
        | _ -> acc

    findPair [] arr

findPairsSum10 [3;4;5;2;5;8;7;3;2;37;]

// Given 2 integer arrays, determine of the 2nd array is a rotated version of the 1st array. 
// Ex. Original Array A={1,2,3,5,6,7,8} Rotated Array B={5,6,7,8,1,2,3}

let rec verifyRotation arr1 arr2 = 
    if arr1 = arr2 then true
    elif List.length arr1 <> List.length arr2 then false
    else 
        let rec rotateAndCheck secondList =
            let x::xs = secondList
            let rotated = xs @ [x]
            if arr1 = rotated then true
            elif rotated = arr2 then false
            else rotateAndCheck rotated

        rotateAndCheck arr2

verifyRotation [1;2;3;5;6;7;8] [5;6;7;8;1;2;3]

// Find the only element in an array that only occurs once
let findOnlyOneElementBy pred arr =
    arr 
    |> List.countBy pred
    |> List.filter (fun (key, count) -> count = 1)
    |> List.map (fst)
    |> List.item 0
    
findOnlyOneElementBy id [3;4;3;4;5;6;6;7;7;9;5]

// Implement binary search of a sorted array of integers
let rec binSearch target arr =
    match List.length arr with
      | 0 -> None
      | i -> let middle = i / 2
             printfn "%d" middle
             match  sign <| compare target arr.[middle] with
               | 0  -> Some(target)
               | -1 -> binSearch target arr.[..middle-1]
               | _  -> binSearch target arr.[middle+1..]


binSearch 7918 [1..10000000]

// euler

// 1. Multiples of 3 and 5
[1..999] |> List.filter(fun x -> x % 3 = 0 || x % 5 = 0) |> List.sum


// 2. Even Fibonacci numbers
let rec fib (acc: int list) (last1:int) (last2:int) = 
    let newNumber = last1 + last2
    let last2 = last1
    let last1 = newNumber
    
    if newNumber >= 4_000_000
    then last2::acc 
    else fib (last2::acc) last1 last2

(fib [1] 2 1) |> List.filter(fun x -> x % 2 = 0) |> List.sum

// 3. Largest prime factor
let rec findPrimeFactors acc factor (number:int64)  = 
    if factor = number then
        factor::acc
    elif number % factor = 0L then 
        findPrimeFactors (factor::acc) factor (number/factor) 
    else
        findPrimeFactors acc (factor+1L) number 

findPrimeFactors [] 2L 600851475143L

// 4. Largest palindrome product
let isPalindromicNumber (number:int) =
    let strNumber = string number
    strNumber = System.String(Array.rev (strNumber.ToCharArray()))
isPalindromicNumber 123

let cartesian xs ys = 
    xs |> List.collect (fun x -> ys |> List.map (fun y -> x, y))

let biggestPalindrom =
    let tab = [100 .. 999] |> List.rev
    let data = cartesian tab tab 
    data 
    |> List.filter(fun (a, b) -> isPalindromicNumber (a*b))
    |> List.maxBy(fun (a,b) -> a*b)

// 5. Smallest multiple
// [1 .. 10] |> List.map(fun x -> 2520 / x)
let rec findSmallest number = 
    if Seq.forall(fun x -> number % x = 0) [|1 .. 20|]
    then number
    else findSmallest (number + 1)
findSmallest 9699690


(*
let isEvenlyDivided(n, m) = n % m = 0
let isEvenlyDividedByAll(n, numbers) = numbers |> Seq.forall (fun x -> isEvenlyDivided(n, x))

let findSmallestCommonMultiple(numbers) =
    let max = Array.max(numbers)
    Seq.unfold (fun x -> Some(x, x + 1)) 1
    |> Seq.map (fun x -> x * max)
    |> Seq.filter (fun x -> isEvenlyDividedByAll(x, numbers))
    |> Seq.head
 
findSmallestCommonMultiple [|1 .. 20|]
*)

// 6. Sum square difference
let calcDiff = 
    let a = [1 .. 100] |> List.sumBy(fun x -> x * x)
    let b = [1 .. 100] |> List.sum
    b * b - a

// 7. 10001st prime Sieve of Eratosthenes

let sieve (n:int64) =
    let rec aux (list: int64 list) = 
        match list with
        | [] -> []
        | hd :: tl -> hd :: aux (list |> List.filter (fun x -> x % hd <> 0L) )
    [2L .. n] |> aux

// fast primes
open System
open System.Collections

let getPrimes nmax =
    let sieve = new BitArray((nmax/2) + 1, true)
    let result = new ResizeArray<int>(nmax / 10)
    let upper = int (sqrt (float nmax))   
    
    if nmax > 1 then result.Add(2) 

    let mutable m = 1
    while 2 * m + 1 <= nmax do
       if sieve.[m] then
           let n = 2 * m + 1
           if n <= upper then 
               let mutable i = m
               while 2 * i < nmax do sieve.[i] <- false; i <- i + n
           result.Add n
       m <- m + 1
    
    result    

let result = getPrimes 1000000 
result.Item 10000

// theburningmonk solution
let findFactorsOf n  =
    let upperBound = int (sqrt (double(n)))
    [2..upperBound]
    |> Seq.filter (fun x -> n % x = 0)
 
let isPrime n  = Seq.isEmpty (findFactorsOf n)
let primeNumbers = Seq.unfold (fun x -> Some(x, x + 1)) 2 |> Seq.filter isPrime
primeNumbers |> Seq.item 10000

// 8. Largest product in a series
let largeDigitString = 
    "73167176531330624919225119674426574742355349194934\
    96983520312774506326239578318016984801869478851843\
    85861560789112949495459501737958331952853208805511\
    12540698747158523863050715693290963295227443043557\
    66896648950445244523161731856403098711121722383113\
    62229893423380308135336276614282806444486645238749\
    30358907296290491560440772390713810515859307960866\
    70172427121883998797908792274921901699720888093776\
    65727333001053367881220235421809751254540594752243\
    52584907711670556013604839586446706324415722155397\
    53697817977846174064955149290862569321978468622482\
    83972241375657056057490261407972968652414535100474\
    82166370484403199890008895243450658541227588666881\
    16427171479924442928230863465674813919123162824586\
    17866458359124566529476545682848912883142607690042\
    24219022671055626321111109370544217506941658960408\
    07198403850962455444362981230987879927244284909188\
    84580156166097919133875499200524063689912560717606\
    05886116467109405077541002256983155200055935729725\
    71636269561882670428252483600823257530420752963450"

let inputArr input = 
    input 
    |> Seq.toList
    |> List.map(fun c -> int64(c.ToString()))

let calcProdOfArray input = 
    input |> List.reduce(*)
   
let larges13Product (input: string) =
    let rec aux arr currentArr bestArr bestProd =
        match arr with
        | x::xs -> 
            let newProd = currentArr |> calcProdOfArray
            if newProd > bestProd 
            then aux xs (currentArr.[1..] @ [x]) currentArr newProd
            else aux xs (currentArr.[1..] @ [x]) bestArr bestProd 
        | _ -> (bestArr, bestProd)
    
    let arr = inputArr input
    aux arr [7L; 3L; 1L; 6L; 7L; 1L; 7L; 6L; 5L; 3L; 1L; 3L; 3L] [] 0L


let maxProduct input =
    input
    |> inputArr
    |> List.windowed(13)
    |> List.map (calcProdOfArray)
    |> List.max

//largeDigitString |> larges13Product 
maxProduct largeDigitString

// unfold exercises
Seq.unfold (fun state -> if (state > 20) then None else Some(state, state + 1)) 0 |> Seq.toList

let unfoldFib maxNumber (one, two) = 
    let nextNumber = one + two
    if (nextNumber > maxNumber) then None
    else Some(nextNumber, (two, nextNumber))
let fib maxNumber = Seq.unfold (unfoldFib maxNumber) (1,1)

fib 10000 |> Seq.toList

// 9. Special Pythagorean triplet

let pythaFun a b =
    (sqrt(double(a * a + b * b))) + a + b

[for x in 1.0 .. 1000.0 do
 for y in 1.0 .. (x - 1.0) do
 yield x, y]
 |> List.filter(fun (a, b) -> pythaFun a b = 1000.0)

// 10. Summation of primes

let findFactorsOf n  =
    let upperBound = int (sqrt (double(n)))
    [2..upperBound]
    |> Seq.filter (fun x -> n % x = 0)
 
let isPrime n  = Seq.isEmpty (findFactorsOf n)
let primeNumbers = Seq.unfold (fun x -> Some(x, x + 1)) 2 |> Seq.filter isPrime

primeNumbers
|> Seq.take 300
|> Seq.filter(fun x -> x < 2_000_000)

// 11. Largest product in a grid

let gridDataString =
"""08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48"""

let getGridData (input:string) = 
    let gridData = Array2D.create 20 20 0
    input.Split '\n'
    |> Array.iteri(fun y (row: string) -> 
        row.Split ' ' |> Array.map(int) |> Array.iteri (fun x elem -> Array2D.set gridData y x elem)
        )
    gridData

let grid11 = getGridData gridDataString 

// let verifyBounds arr x y =
//     Array2D.length1 arr > x && Array2D.length2 arr > y

let getRow4 arr x y =
    seq {
        for i in 0 .. 3 do
        yield Array2D.get arr y (x + i)
    }

let getCol4 arr x y =
    seq {
        for i in 0 .. 3 do
        yield Array2D.get arr (x + i) y
    }

let getDiagRight4 arr x y =
    seq {
        for i in 0 .. 3 do
        yield Array2D.get arr (x + i) (y + i)
    }

let getDiagLeft4 arr x y =
    seq {
        for i in 0 .. 3 do
        yield Array2D.get arr (x - i) (y + i)
    }

let getAllRow4 arr =
    seq {
        for x in 0 .. 19 do
            for y in 0 .. 16 do
                yield getRow4 arr y x
    }

let getAllCol4 arr =
    seq {
        for x in 0 .. 16 do
            for y in 0 .. 19 do
                yield getCol4 arr x y
    }

let getAllDiagRight4 arr =
    seq {
        for x in 0 .. 16 do
            for y in 0 .. 16 do
                yield getDiagRight4 arr y x
    }

let getAllDiagLeft4 arr =
    seq {
        for x in 0 .. 16 do
            for y in 3 .. 19 do
                yield getDiagLeft4 arr y x
    }

[
    yield! (getAllRow4 grid11 |> Seq.toList)
    yield! (getAllCol4 grid11 |> Seq.toList)
    yield! (getAllDiagRight4 grid11 |> Seq.toList)
    yield! (getAllDiagLeft4 grid11 |> Seq.toList)
]
|> List.map(fun x -> (x, Seq.reduce (*) x ))
|> List.maxBy snd