Reversing List in groups of given size with F#

Problem Statement:

Given a list, write a function to reverse every K element when k is an input to the function.

Example:

Input: [1;2;3;4;5;6;7;8] and k = 3
Output:[3;2;1;6;5;4;8.7] 

In case of an empty list, it just returns [].

Solution with F#:

From the problem definition, the signature of reverseK is quite trivial:

val reverseK : x:int list -> k:int -> int list
view raw gistfile1.fs hosted with ❤ by GitHub

In order to implement this function, we have used int list list, which in essence, acts as an accumulator to store the intermediate results. In addition, for every Kth element, we are creating a new list (Line 5) and resetting counter i to zero for further processing.  In a sense, we are splitting the list in K chunks and reversing it.

let rec reverseK (x:int list) (k:int):int list=
let rec reverseKAux (x:int list) (acc:int list list) (i:int)=
match x with
| [] -> acc
| xhd::xtl when k=i ->
reverseKAux (xhd::xtl) ([]::acc) 0
| xhd::xtl ->
match acc with
| h::t -> reverseKAux xtl ((xhd::h)::t) (i+1)
| [] -> reverseKAux xtl ([xhd]::[]) (i+1)
in
reverseKAux x [[]] 0
|> List.rev
|> List.collect (fun x -> x)
view raw gistfile1.fs hosted with ❤ by GitHub

These results are afterwards reversed and flattened using List.rev and List.collect as shown in Line 13 and in Line 14.

Algorithmic Complexity:

Complexity of the above algorithm: O(n).

Solution with c:

An implementation of this problem in C is available here.

Output:

> reverseK [1;2;3;4;5;6;7;8] 3;;
val it : int list = [3; 2; 1; 6; 5; 4; 8; 7]
> reverseK [] 3;;
val it : int list = []
view raw gistfile1.fs hosted with ❤ by GitHub

Zip lists with F#

Problem Statement:

Zip two lists of Integers.

If the lists are of unequal length, return None; otherwise return Some of (int*int) list.

Solution:

Following naïve solution recurses over elements of the lists, and creates tuple, as part of the zip operation. If both lists are empty, it returns Some [].

let rec zipTwo (x:int list) (y: int list) : ((int*int) list) option =
match x,y with
| ([], []) -> Some []
| (xhd::xtl, yhd::ytl) ->
match zipTwo xtl ytl with
| None -> None
| Some lst -> Some ((xhd,yhd)::lst)
| (_,_) -> None
view raw gistfile1.fs hosted with ❤ by GitHub

The unequal length case is handled by the pattern outlined in line 8 , which simply returns None. Subsequent return calls of the recursion detect it and simply return None.

Thus, resultant signature of zipTwo is given by:

val zipTwo : x:int list -> y:int list -> (int * int) list option
view raw gistfile1.fs hosted with ❤ by GitHub

Output:

> zipTwo [] [];;
val it : (int * int) list option = Some []
> zipTwo [1;2] [2;4;8];;
val it : (int * int) list option = None
> zipTwo [1;2;3] [2;4;8];;
val it : (int * int) list option = Some [(1, 2); (2, 4); (3, 8)]
view raw gistfile1.fs hosted with ❤ by GitHub

SPOJ 2716. Maximal Quadrilateral Area (QUADAREA) with F#

Problem Definition

Details about this problem is available here.  Required Background Topic:  Cyclic quadrilateral.

Solution

Given that the length of the sides are {a,b,c,d}, the Maximal Quadrilateral Area is given by the following equation:

where semiperimeter s can be defined as follows.

let getMaxQuadrilateralArea (a,b,c,d) =
let s = 0.50 *(a+b+c+d)
System.Math.Sqrt((s-a)*(s-b)*(s-c)*(s-d))
let solveSpoj2716() =
let parseLine() =
let l = System.Console.ReadLine().Split()
(l.[0]|>float,l.[1]|>float,l.[2]|>float,l.[3]|>float)
let rec runTests currentTest maxAvailableTests =
if currentTest < maxAvailableTests then
parseLine()
|> getMaxQuadrilateralArea
|> printfn "%f"
runTests (currentTest+1) maxAvailableTests
in
match System.Console.ReadLine() |> System.Int32.TryParse with
| (true, i) when i > 0 -> runTests 0 i
| _ -> ()
solveSpoj2716()
view raw QUADAREA.fs hosted with ❤ by GitHub

SPOJ 24. Small factorials (FCTRL2) with F#

Problem Definition

You are asked to calculate factorials of some small positive integers.

Input

An integer t, 1<=t<=100, denoting the number of testcases, followed by t lines, each containing a single integer n, 1<=n<=100.

Output

For each integer n given at input, display a line with the value of n!

More details about the problem is available here.

Solution

open System
open System.Numerics
let init() = Array.init 158 (fun x -> if x = 0 then 1 else 0)
let minLength (a:int array) : int =
let rec m' (a:int array) i =
match a.[i-1] with
| 0 -> m' a (i-1)
| _ -> i
in
m' a a.Length
let toString' (a:int array) =
let s = System.Text.StringBuilder()
let mLength = minLength a
for i=(mLength-1) downto 0 do
s.Append(a.[i])|>ignore
s.ToString()
let (^*) multiplier (multiplicand:int array)=
let rec multiplyOPT (a:int array) b i acc length=
let l = Math.Min(length,a.Length)
if i< l then
let r = a.[i] * b + acc
a.[i] <- r%10
multiplyOPT a b (i+1) (r/10) length
else
a
in
multiplyOPT multiplicand multiplier 0 0 (multiplicand |>minLength |> (+) 2)
let factorial n =
let rec fac n r =
match n with
| 0 -> toString' r
| _ -> fac (n-1) (n^*r)
fac n (init())
let intFactorial (i : uint64) =
let rec f (i:uint64) (acc:uint64) =
match i with
| 0UL -> acc
| i -> f (i-1UL) (acc*i)
in
f i 1UL
let computeFactorial (n:int) =
if n > 20 then
factorial n
else
(intFactorial (n |> uint64)).ToString();
let solveSpoj24() =
let rec solveLines currentLine maxLines =
if currentLine < maxLines then
System.Console.ReadLine()
|> int
|> computeFactorial
|> printfn "%s"
solveLines (currentLine+1) maxLines
in
match Console.ReadLine() |> Int32.TryParse with
| (true, i) when i > 0 -> solveLines 0 i
| _ -> ()
solveSpoj24()
view raw FCTRL2.fs hosted with ❤ by GitHub

SPOJ 2906. GCD2 with F#

Problem Definition

Frank explained its friend Felman the algorithm of Euclides to calculate the GCD of two numbers. Then Felman implements it algorithm

int gcd(int a, int b)
{
	if (b==0)
		return a;
	else
		return gcd(b,a%b);
}

and it proposes to Frank that makes it but with a little integer and another integer that has up to 250 digits.

Your task is to help Frank programming an efficient code for the challenge of Felman.

Input

The first line of the input file contains a number representing the number of lines to follow. Each line consists of two number A and B ( and ).

Output

Print for each pair (A,B) in the input one integer representing the GCD of A and B.

More on this problem is available here.

Solution

Greatest common divisor is the largest number that divides both number without any reminder.  Thus, GCD is also called Highest Common Divisor (HCF), or  Greatest Common Factor  (GCF).

The main trick used in the solution lies in the mod' function, which effectively reduces the range of the numbers to , that is:

where is the outcome of mod' function .

Afterwards, a normal gcd function can simply be applied on to compute the result.

//Problem Statement : https://www.spoj.com/problems/GCD2/
open System
let parseLine() =
let line = System.Console.ReadLine().Split()
line.[0] |> int, line.[1] |> string
let rec gcd a b =
match b with
| 0 -> a
| _ -> gcd b (a%b)
// computes b%a
let mod' (b:string) (a:int)=
b.ToCharArray()
|> Array.fold (fun acc x -> ((acc*10 + (((int)x)-48))%a)) 0
let rec solveLines currentLine maxLines =
if currentLine < maxLines then
let num1,num2 = parseLine()
match num1,num2 with
| 0,_ -> printfn "%s" num2
| _ ->
mod' num2 num1
|> gcd num1
|> printfn "%d"
solveLines (currentLine+1) maxLines
let solveSpoj2906() =
match Console.ReadLine() |> Int32.TryParse with
| (true, i) when i > 0 -> solveLines 0 i
| _ -> ()
solveSpoj2906()
view raw gcd2.fs hosted with ❤ by GitHub