UVa 100. The 3n+1 Problem: Solving with a Brute-force Algorithm

The UVa 100: The 3n+1 Problem is about collatz problem, which we have discussed in details in a recent post. The following Java code describes a brute-force algorithm to solve this problem. In addition, a memoization technique is incorporated to reduce redundant computations and thereby, to enhance efficiency of this brute-force algorithm.

Please leave a comment if you have any query. Thank you.


See Also

see Collatz Problem a.k.a. 3n+1 ProblemCollatz Problem a.k.a. 3n+1 Problem.
see UVa 371. Ackermann FunctionUVa 371. Ackermann Function.

Advertisements

Collatz Problem a.k.a. 3n+1 Problem

This post focuses on Collatz problem, which is also known as, among others, the 3n+1 problem, and  the Syracuse problem.

Outline. We begin by introducing Collatz conjecture; afterwards, we presents an algorithm to solve the problem (UVa 100 or SPOJ 4073) published in both UVa and SPOJ. The primary advantage of having it in SPOJ is that we can use F# to derive a simple and elegant solution; at the same time, we can verify it via SPOJ’s online judge.

Background: Collatz Conjecture

Collatz problem, also known as problem, concerns the iterates generated by the repeated applications of following the function: Given a positive integer,

image which implies that if is even, it returns , otherwise . This function is called Collatz function. Consider, for instance, , the generated iterates are following:. This sequence is referred to as Collatz sequence, or hailstone numbers.

Collatz conjecture, which is credited to Luther Collatz at the University of Hamburg, asserts that for any positive integer , the repeated applications of the Collatz function, i.e., eventually produces value ; that is,  , where denotes application of . Considering , it follows: .

The generated sequence of iterates: is called the Collatz-trajectory of . For instance, beginning from , the resulted sequence converged to as follows: . Therefore, Collatz-trajectory of 26 is . Note that, although Collatz problem is based on this simple concept, it is intractably hard. So far, it has been verified for by Leaven and Vermeluen.

Algorithm Design: 3n+1 problem

In the rest of this post, we intend to solve the problem, which is essentially a restricted or bounded version of the Collatz problem.

Interpretation. It restricts the iteration by exiting as soon as the Collatz sequence reaches to value 1 at . For = 26, the resulting Collatz sequence is therefore: , and length of the sequence is i.e., 11. This problem asks to compute the largest Collatz sequence that results from any integer between and , which are provided as inputs. Note that, the value of and are both positive integers: .

Implementation. We first apply a naïve brute-force algorithm to solve this problem, which computes the length of the sequence for each integer from to , and returns the maximum length found.  It is worth noting that-

noun_project_6482 A naïve brute-force algorithm redundantly computes sequences again and again. Consider =13 and =26. For = 26, we also compute the sequence for 13 that has already  been computed during = 13.

noun_project_6482 We must apply a tail-recursive implementation to compute the sequence, as naïve implementation might results in stack overflow.

As we shall see next, we have optimized the naïve implementation considering the above observations. First, we define function, nextCollatz, that returns next integer of the Collatz sequence, given an integer . In effect, it computes from as follows.

Using the algorithm outlined in collatzSeqLength, the length of the Collatz sequence is computed for any given integer .

It includes the following optimizations over the naïve implementation we stated earlier:

 noun_project_8551  Memorization has been incorporated to effectively optimize the algorithm by avoiding redundant computations of the sequence and its length, which in turn provides a faster algorithm than its naïve counterpart, albeit with the cost of additional space.

noun_project_8551 Tail-recursive algorithm enables computation of Collatz sequence with larger .

noun_project_8551 Continuation-passing-style  has been applied in this algorithm to accommodate, and to combine tail-call optimization with memorization.

The following snippet demonstrates how the maximum sequence length is obtained by invoking collatzSeqLength for each integer between the given  and .

Complete source code of this problem can be found in this gist. Following IDEONE page (with sample inputs and outputs) has been provided to further play with the code (in case of the unavailability of F# in local system).  Java source code is also available for this problem.

Try solving Euler Problem 14, which resembles this problem and based on these stated concepts. Please leave a comment if you have any question/suggestion regarding this post. Happy coding!


See Also

see UVa 371. Ackermann FunctionUVa 371. Ackermann Function.
see UVa100. 3n+1 ProblemUVa 100. 3n+1 Problem.

SPOJ 97. Party Schedule (PARTY) with F#

The Party Schedule problem, published in SPOJ website, is about deriving an optimal set of parties that maximizes fun value, given a party budget: and parties: where each party have an entrance cost , and is associated with a fun value .

In this post, we discuss how to solve this problem by first outlining an algorithm, and afterwards, by implementing that using F#.

Background

This problem is a special case of  Knapsack problem. Main objective of this problem is to select a subset of parties that maximizes fun value, subject to the restriction that the budget must not exceed .

More formally, we are given a budget as the bound. All parties have costs and values . We have to select a subset such that is as large as possible, and subject to the following restriction —

Furthermore, an additional constraint: “do not spend more money than is absolutely necessary” is applied, which implies following. Consider two parties and ; if and , then we must select instead of .

Algorithm

Attempt 1

The definition of this problem suggests a recursive solution. However, a naïve recursive solution is quite impractical in this context, as it requires exponential time due to the following reason: a naïve recursive implementation applies a top-down approach that solves the subproblems again and again.

Attempt 2

Next, we select dynamic programming technique to solve this problem. So, we have to define a recurrence that expresses this problem in terms of its subproblems, and therefore it begs the answer of the following question:

What are the subproblems? We have two variants: and , i.e. available budget and number of parties. We can derive smaller subproblems, by modifying these variants; accordingly, we define-

It returns the maximum value over any subset where . Our final objective is to compute , which refers to the optimal solution, i.e., maximal achievable fun value from budget and parties.

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

How can we express this problem using its subproblems? Let’s denote to be the optimal subset that results in . Consider party and note following.

  1. It , then . Thus, using the remaining budget and the parties , we seek the optimal solution.
  2. Otherwise, then . Since is not included, we haven’t spent anything from .

Obviously, when , we apply the 2nd case. Using the above observations, we define the recurrence as follows–

daum_equation_1361040769378

where the base conditions can be rendered as below. daum_equation_1361045229580

Using the above recurrence, we can compute for all parties and for costs . In essence, we build the OPT table, which consists of rows and columns, using a bottom-up approach as stated in the following algorithm.

Implementation

Following code builds the OPT table using the stated algorithm.

In effect, it does two things: builds OPT table and afterwards, returns the OPT(n,C) and associated optimal cost (due to the constraint “do not spend more money than is absolutely necessary” discussed in background section)  as a tuple (see Line 16). Following function computes the optimal cost.

Complexity.  as each requires time.

For the complete source code, please check out this gist,  or visit its IDEONE page to play with the code. Please leave a comment if you have any question or suggestion regarding the algorithm/implementation.

 
Happy coding!


See Also

see SPOJ 8545. Subset Sum (Main72) with Dynamic Programming and F#SPOJ 8545. Subset Sum (Main72) with Dynamic Programming and F#.
see UVa 10664. LuggageUVa 10664. Luggage.

Project Euler 04. Largest Palindrome Product with F#

Problem Definition

Available at Largest Palindrome Product

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.


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.


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 :

daum_equation_1359460361956

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.

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.