Contents tagged with F#
-
Solving SPOJ 346. Bytelandian Gold Coins (COINS) with Dynamic Programming and F#
The Bytelandian Gold Coins problem, officially published in SPOJ, is centered around computing the maximum dollars that can be exchanged for a Bytelandian gold coin. In this post, we outline a solution to this problem with memoization and F#.
Interpretation
The problem definition enforces following rules to perform the exchange. Consider, a Bytelandian gold coin--
It can be exchanged to three other coins, i.e.,coins. Thus, coin
value in bytelandian gold coins.
Alternatively, Our objective is to derive an algorithm that maximizes the dollars exchanged from the gold coin -
Solving Subset Sum 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...(read more)
-
Levenshtein Distance with F#
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 ...(read more)
-
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... continue reading.
-
UVa 136. Ugly Numbers with F#
This blog-post is about UVa 136: Ugly Number, a trivial, but interesting UVa problem. The crux involves computing 1500th 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:
-
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... continue reading.
-
F#: Computing Length of a List (Tail Recursive)
The code snippets listed below defines a function to compute the length of a give list using F#. Note that these functions are also known polymorphic function, as they work with any type of list (as shown in the output).
