# Programming Challenges with functional programming in F#: Article #1 the Collatz conjecture

Hello and welcome to the first installment of posts on solving common programming challenges using functional programming in F#.
I've been in software development professionally for over ten years now. I've gained a lot of experience with many different programming languages. Object oriented design was my main tool of choice. Object oriented design while effective is not the only software design methodology available to you as a programmer. One of the most important lessons to be learned in software development in my opinion is to use the best tool for the job.
I've decided to learn functional programming in order to improve my problem solving skills. F# and functional programming requires a different approach to solving problems than other methodologies. Trying to solve problems using a new way of thinking is a great way to stimulate neuroplasticity and learn a new skill.
The 3n+1 programming challenge
The programming challenge that I chose to begin learning F# is called the 3n+1 problem. I discovered the challenge in the book "Programming Challenges: The Programming Contest Training Manual" by Steven S. Skiena and Miguel A. Revilla which you can find on amazon.com here
Here's the gist:
You start by creating an algorithm that accepts integer n as input. The algorithm will generate a sequence of numbers based on it's input. Starting with n, the algorithm will check to see if n is odd or even. if n is odd, then you will generate the next value in the sequence by calculating n * 3 + 1. If n is even, the next value in the sequence is n / 2. You will then repeat the process for each new value added to the sequence until n = 1.
Here is an example of the sequence generated when n = 22;
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
The cycle length is the length of the sequence generated for a given number. In this case, the cycle length is 16 because the sequence has 16 integers (including the input as well as the number 1).
Given two numbers i and j, you are to determine the maximum cycle length over all numbers between i and j including both start and end points.
Here are some examples:
i j max cycle length
1 10 20
100 200 125
201 210 89
900 1000 174
Let's start by discussing some of the fundamental differences between between the two solutions.
The C# solution
I've been working in C# for over a decade now. Naturally my instincts tell me to try to tackle this problem using object oriented design principles. So here is a solution that I design using C# and OOP.
CalculationResult.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ThreePlusOneCSharp
{
public class CalculationResult
{
public int InputValue { get; set; }
public List<int> ResultList { get; set; }
public int CycleLength
{
get
{
return ResultList.Count;
}
}
public CalculationResult()
{
this.ResultList = new List<int>();
}
}
}
Program.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ThreePlusOneCSharp
{
class Program
{
static void Main(string[] args)
{
int startRange = int.Parse(args[0]);
int endRange = int.Parse(args[1]);
int maxCycleLength = _CalculateMaxCycleLengthForRange(startRange, endRange);
Console.WriteLine("The max Cycle length for {0}..{1} is = '{2}'", args[0], args[1], maxCycleLength.ToString());
}
private static int _CalculateMaxCycleLengthForRange(int startRange, int endRange)
{
var cycleLengths = new List<int>();
for (int rangeIndex = startRange; rangeIndex <= endRange; rangeIndex++)
{
var calcResult = new CalculationResult();
calcResult.InputValue = rangeIndex;
calcResult.ResultList.Add(rangeIndex);
var result = _CalculateNextInput(calcResult);
cycleLengths.Add(result.CycleLength);
}
return cycleLengths.Max();
}
private static CalculationResult _CalculateNextInput(CalculationResult result)
{
result.ResultList.Add(result.InputValue);
if (result.InputValue % 2 == 0)
result.InputValue = (result.InputValue / 2);
else
result.InputValue = (result.InputValue * 3) + 1;
if (result.InputValue == 1)
return result;
return _CalculateNextInput(result);
}
}
}
As you can see, I created a class to hold the input value as well as a list of all new inputs generated for the specified input. I created a property called CycleLength which returns the count of the list of inputs generated. We use recursion to call _CalculateNextInput which allows us to keep up with the cycle length for the given input. The _CalculateMaxCycleLengthForRange routine will iterate through all numbers between i and j and keep a list of each cycle length. Once all integers in the range have been processed, we return the max cycle length from all cycle lengths in the list.
The F# solution
let rec generateSequence num =
seq {
yield num
if num <> 1 then
match num with
| x when x % 2 = 0 -> yield! generateSequence (x / 2)
| x -> yield! generateSequence ((x * 3) + 1)
}
let getMaxCycleLength range =
let valueSequences =
seq {
for number in range
do yield seq {
yield! generateSequence number
}
}
let cycleLengthSequence =
seq {
for sequence in valueSequences
do yield Seq.toList(sequence).Length
}
Seq.max(cycleLengthSequence)
[<EntryPoint>]
let main args =
let low, high =
int args.[0], int args.[1]
let input = [low .. high]
let cycleLength =
getMaxCycleLength input
System.Console.Write(" {0} ", cycleLength)
0
Conclusion
Join me for my next article where I will discuss in detail the two different implementations.