Project Euler 04. Largest Palindrome Product with F#

Problem Definition

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 * 99.

Find the largest palindrome made from the product of two 3-digit numbers.

Implementation

We have to find out a palindrome p such that —

where both a and b are three digit number. To do so, we first define a function that checks whether a number (e.g., p) is a palindrome.

	let ispalindrom (x:int):bool =
	let s = x.ToString()
	s = (s \|> (fun x -> new string(x.ToCharArray() \|> Array.rev)))

view raw ispalindrom.fs hosted with ❤ by GitHub

Then, we iterate over all the tuples (a,b) of three digit numbers e.g., [100..999] that satisfy the following equation.

Finally, we check if a*b is a palindrome and get the largest palindrome, as outlined below.

	seq{
	for x in 100..999 do
	for y in x..999 do
	if ispalindrom (xy) then yield (xy)}
	\|> Seq.max

view raw euler04.fs hosted with ❤ by GitHub

Would/did you solve it differently? Please let me know your opinion in the comment section below.

Happy problem solving …

problem solving

SPOJ 6219. Edit Distance (EDIST) with F#

This problem can be solved using dynamic programming with memoization technique. In essence, it is about computing the Edit Distance, also known as, Levenshtein Distance between two given strings.

Definition

Edit Distance—a.k.a “Lavenshtein Distance”–is the minimum number of edit operations required to transform one word into another. The allowable edit operations are letter insertion, letter deletion and letter substitution.

Implementation

Using Dynamic Programming, we can compute the edit distance between two string sequences. But for that, we need to derive a recursive definition of Edit Distance. We denote the distance between two strings as D, which can be defined using a recurrence as follows.

Case 1 : Both and are empty strings, denoted as :

Case 2 : Either or is :

Case 3 : Both and are not :

Here , where is the last character of and contains rest of the characters. Same goes for . We define edit distance between and using a recurrence and in term of and .

can be defined as the minimum, or the least expensive one of the following three alternatives stated in the above equation.

Substitution: If , then the overall distance is simply . Otherwise, we need a substitution operation that replaces with , and thus, the overall distance will be .
Insertion: Second possibility is to convert to by inserting in . In this case, the distance will be . Here, +1 is the cost of the insert operation.
Deletion: Last alternative is to convert to by deleting from that costs +1. Then the distance become .

As this is a ternary recurrence, it would result in an exponential run-time, which is quite impractical. However, using the dynamic programming with memoization, this recurrence can be solved using a 2D array. The code to solve this problem is outline below.

	let computeEditDistance (source:string,target:string) =
	let height,width = (source.Length, target.Length)
	let grid: int [,] = Array2D.zeroCreate<int> (height+1) (width+1) // 2D Array for memoization

	for h = 0 to height do
	for w = 0 to width do
	grid.[h,w] <-
	match h,w with
	\| h,0 -> h // case 1 and 2
	\| 0, w -> w
	\| h, w ->
	let s,t = source.[h-1],target.[w-1]
	let substitution = grid.[h-1,w-1]+(if s = t then 0 else 1)
	let insertion = grid.[h,w-1] + 1
	let deletion = grid.[h-1,w] + 1
	min (insertion, deletion, substitution) // case 3
	grid.[height,width]

view raw gistfile1.fs hosted with ❤ by GitHub

As shown in line 14, the distance grid.[h,w] can be computed locally by taking the min of the three alternatives stated in the recurrence (computed in line 11,12, 13). By obtaining the locally optimum solutions, we eventually get the edit distance from grid.[s.length, t.length].

Complexity: Run-time complexity: . Lets denote the lengths of both strings as . Then, the complexity become . Space complexity is also same.

Complete source code is outlined in the next page.

Pages: 12

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

Computing bound of a List with F#

Following code snippet shows how to compute bound (i.e the min and max elements) of a List using F#.

	let rec bound (lst:int list) : (int*int) option =
	match lst with
	\| [] -> None // Empty List
	\| xhd::xtl ->
	match bound xtl with
	\| None -> Some (xhd,xhd) // List with only 1 element
	\| Some (x,y) ->
	Some ((if x>xhd then xhd else x), (if y<xhd then xhd else y))

view raw bound.fs hosted with ❤ by GitHub

Solution outlined here is quite trivial and use the pattern matching facilities of F#. In case of an empty list (line 3), it returns None; otherwise, it returns the bound as Some (int*int) (line 8).

Therefore, the signature of bound is given by-

val bound : lst:int list -> (int * int) option

view raw gistfile1.fs hosted with ❤ by GitHub

Output of bound –

	> bound [1;2;3;4];;
	val it : (int * int) option = Some (1, 4)
	> bound [1];;
	val it : (int * int) option = Some (1, 1)
	> bound [];;
	val it : (int * int) option = None

view raw gistfile1.fs hosted with ❤ by GitHub