UVa 10706. Number Sequence with F#

This post describes an algorithm to solve UVa 10706: Number Sequence problem from UVa OJ. Before outlining the algorithm, we first give an overview of this problem in the next section.

Interpretation

This is a straight-forward problem, which however, requires careful introspection. Our objective is to write a program that compute the value of a sequence , which is comprised of the number groups . Each consists of positive integers written one after another and thus, the first digits of are —

11212312341234512345612345671234567812345678912345678910123456789101112345678910

It is imperative to note that, the value of has the following range . Realize that, the maximum value of is indeed Int32.MaxValue. In the provided test cases, the values of are stated. We simply have to compute ; therefore, we are required to write a function that has following signature: . That is —

f: 10 --> S.[10] = 4
f: 8  --> S.[8]  = 2
f: 3  --> S.[3]  = 2

Note also that the maximum number of test cases is 25. Question for the reader: What is the maximum possible value of for the specified sequence , which is constituted of ?

We hope that by this time, it is clear where we are headed towards. In next section, we outline an algorithm to solve this problem. But, before moving further, we would like to recommend you to try to solve it yourselves first and then, read the rest of the post. By the way, we believe that the solution that we have presented next can be further optimized (or, even a better solution can be derived). We highly welcome your feedback regarding this.

Algorithm

Recall that, is constituted of number groups . In order to identify the digit located at the position of , we first determine the number group that digit is associated with and then, we figure out the digit from .

To do so, we first compute the length of each number group . Consider the number group till —

112123123412345123456…12345678910

As mentioned, this sequence is basically constituted of as shown below (with their respective lengths).

1                    --> 1 
1 2                  --> 2 
1 2 3                --> 3
1 2 3 4              --> 4
1 2 3 4 5            --> 5
1 2 3 4 5 6          --> 6
1 2 3 4 5 6 7        --> 7
1 2 3 4 5 6 7 8      --> 8
1 2 3 4 5 6 7 8 9    --> 9
1 2 3 4 5 6 7 8 9 10 --> 11

It implies that the length of can be computed from the length of as shown below.

Using Eq.1, we calculate the cumulative sum of each number group as follows.

Why do we calculate cumulative sum? The purpose in this is to be able to simply run a binary search to determine which number group the digit belongs to in time. For example, consider i=40.

1                    --> 1 
1 2                  --> 2 
1 2 3                --> 6 
1 2 3 4              --> 10
1 2 3 4 5            --> 15
1 2 3 4 5 6          --> 21
1 2 3 4 5 6 7        --> 28
1 2 3 4 5 6 7 8      --> 36 
1 2 3 4 5 6 7 8 9    --> 45
1 2 3 4 5 6 7 8 9 10 --> 56

Using binary search, we can find out that contains the digit. Then, using a linear search, we can simply derive the first four digits of to eventually find out the corresponding digit, 4.

Similarly, for i=55, we can figure out that the digit is indeed 1.

Implementation

Next, we outline a F# implementation of the stated algorithm. We start with computing the cumulative sums of the lengths as follows. Continue reading “UVa 10706. Number Sequence with F#”

Howard Mansell on F# Type Providers and the R Programming Language

In the following podcast, Howard Mansell talks about F# type provider and R programming language, which can be summarized as:

“F# 3.0 introduces an exciting and innovative new programming language feature – Type Providers. This functionality allows types that are dynamically generated during development to be used in statically typed code, bringing many of the benefits of dynamic languages to statically typed languages, without sacrificing the safety of static typing.

At BlueMountain, Howard has built and open-sourced a type provider that allows the functionality of the open-source R statistical package to be used from F# in a very fluid manner. This brings the broadest suite of statistical functionality available on any platform to F#. Howard introduces type providers and their (hitherto unexplored) uses for cross-language meta-programming. He also discusses some of the difficulties of bridging the strong static typing of F# with the loose dynamic typing of R” [1].

References

1 http://vimeo.com/49045879

UVa 136. Ugly Numbers

This blog-post is about UVa 136: Ugly Number, a trivial, but interesting UVa problem. The crux involves computing 1500^th Ugly number, where a Ugly number is defined as a number whose prime factors are only 2, 3 or 5. Following illustrates a sequence of Ugly numbers:

1,2,3,4,5,6,8,9,10,12,15...

Using F#, we can derive 1500^th Ugly Number in F#’s REPL as follows.

	seq{1L..System.Int64.MaxValue}
	\|> Seq.filter (isUglyNumber)
	\|> Seq.take 1500
	\|> Seq.last

view raw gistfile1.fs hosted with ❤ by GitHub

In this context, the primary function the determines whether a number is a Ugly number or not–isUglyNumber–is outlined as follows. As we can see, it is a naive algorithm that can be further optimized using memoization (as listed here).

	(*
	* :a:int64 -> b:bool
	*)
	let isUglyNumber (x:int64) :bool =
	let rec checkFactors (n_org:int64) (n:int64) lfactors =
	match n with
	\| 1L -> true
	\| _ ->
	match lfactors with
	\| [] -> false
	\| d::xs ->
	if isFactor n d then
	checkFactors n_org (n/d) lfactors
	elif n > d then
	checkFactors n_org n xs
	else
	false

	checkFactors x x [2L;3L;5L]

view raw gistfile1.fs hosted with ❤ by GitHub

After computing the 1500^th Ugly number in this manner, we submit the Java source code listed below. For complete source code. please visit this gist. Alternatively, this script is also available at tryfsharp.org for further introspection.

	class Main {
	public static void main(String[] args) {
	System.out.println("The 1500'th ugly number is 859963392.");
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Please leave a comment in case of any question or improvement of this implementation. Thanks.

Linq to Hadoop with F# Type Providers | via @TsunamiIDE

SPOJ 8545. Subset Sum (Main72) with Dynamic Programming and F#

The Subset Sum (Main72) problem, officially published in SPOJ, is about computing the sum of all integers that can be obtained from the summations over any subset of the given set (of integers). A naïve solution would be to derive all the subsets of the given set, which unfortunately would result in time complexity, given that is the number of elements in the set.

This post outlines a more efficient (pseudo-polynomial) solution to this problem using Dynamic Programming and F#. Additionally, we post C# code of the solution.

Note that we have solved a similar problem in Party Schedule (PARTY) with F# blog-post.

Interpretation¶

This problem provides a set of integers , and specifies the following constraints–

The size of the given set, i.e.,

, where the value of

is bounded by:

, the following condition holds:

Given this input, we would like to find all the integers: and is the sum of the items of any subset over . Afterward, we sum all these integers, and return it as the result to the problem instance.

In essence, we reduce this problem as follows: Given , can we express it using any subset over ? If yes, we include it in the solution set for summation. Interestingly, we realize that the stated problem is a special case of a more general problem called Subset Sum, given that the sum is .

Algorithm¶

What would be the maximum possible value for ? Indeed, is not practical at all, as can be bounded by the following upper limit: , i.e., the summation of all the items in . This observation effectively reduces the search space to , for a given .

It implies that a naïve algorithm would require to iterate all the subsets over and verify whether their sum is within . Recall that, due to its exponential time complexity, it is quite impractical .

Using dynamic programming technique, a pseudo-polynomial algorithm can be derived, as the problem has an inherent optimal substructure property. That is, a solution of an instance of the problem can be expressed as the solutions of its subproblems, as described next.

We define as the function that determines whether the summation over any subset can result in the integer . So, it yields if sum can be derived over any subset, otherwise, . Also, note that, and .

To define the recurrence, we describe in terms of its smaller subproblems as follows.

In Eq. (1), the first case refers to the fact that is larger than . Consequently, can not be included in the subset to derive . Then, the case 2 of Eq. (1) expresses the problem into two subproblems as follows: we can either ignore though , or we can include it. Using any case stated in Eq. (1), if we can derive i.e. = true, we can include it in the solution set.

As we can see overlapping subproblems, we realize that we can effectively solve them using a bottom-up dynamic programming approach. What about the base cases?

Using a table– dp, we can implement the stated algorithm as follows.

	let computeSubsetSum (set:int array, n:int, sum:int):int =
	// dp[i,j] = True, if subset of [0..i-1] sum
	// equals to :
	// j-set[i] => ith item is included
	// or
	// j => ith item is not included
	let dp:bool[,] = Array2D.zeroCreate (n+1) (sum+1)

	// This dp tries answer folloowing question, given a sum
	// j, whether we can derive it by summing any subset of
	// [0..i]. It computes this answer in bottom up manner,
	// hence, if starting from (i,j) if it can reach (i,0), the
	// answer is yes. Otherwise, if sum<>0 but i=0, then answer is
	// no due to the fact that, using any subsets, the sum cannot be
	// computed.

	// Therefore.
	// base case 1 : given sum = 0, answer is true
	// sum is zero with the provided set of items.
	// Hence, storing it as 0
	for i = 0 to n do
	dp.[i,0] <- true

	// base case 2 : sum <> 0 but OPT = empty -->
	// answer is false
	for j=1 to sum do
	dp.[0,j] <- false

	for i = 1 to n do
	let v_i = set.[i-1]
	for j = 1 to sum do
	dp.[i,j] <-
	if j - v_i < 0 then
	// we can't include i th item in OPT
	dp.[i-1,j]
	else
	dp.[i-1,j]\|\|dp.[i-1,j-v_i]

	let mutable result = 0
	for j=1 to sum do
	result <- result+
	( if dp.[n,j] = true then
	j
	else
	0
	)
	result

view raw SPOJ_MAIN72.fsx hosted with ❤ by GitHub

In essence, the N^th row in the table provides the set of integers that can be derived by summing over any subset . Thereby, we compute the summation of all these integers that satisfies subsum(N,j) = true, and returns it as the result.

Conclusion¶

Full source code of the solution can be downloaded from this gist. For C# source code, please visit following gist. Please leave a comment if you have any question/suggestion regarding this post.

Enough said… now, it’s time for a and a new problem. See you soon; till then, happy problem-solving!

Category: .Net Development