Thinking in LINQ: Harnessing the power of functional programing in .NET applications (2014)
Chapter 2. Series Generation
LINQ helps you generate series by using intuitive and readable code. In this chapter, you will see how to use several LINQ standard query operators (LSQO) to generate common mathematical and recursive series. All these queries are designed to run on LINQPad (www.linqpad.net) as C# statements.
Series generation has applications in many areas. Although the problems in this chapter may seem disconnected, they demonstrate how to use LINQ to solve diverse sets of problems. I have categorized the problems into six main areas: math and statistics, recursive series and patterns, collections, number theory, game design, and working with miscellaneous series.
The following problems are related to simple everyday mathematics and statistics.
2-1. Math and Statistics: Finding the Dot Product of Two Vectors
The dot product of two vectors is defined as the member-wise multiplication of their coefficients.
Problem
The problem is to write a function that finds the dot product of two vectors.
Solution
Use the Zip() standard query operator, passing it a function delegate that multiplies two values at the same location in the arrays.
Listing 2-1 generates the dot product of these two vectors. Figure 2-1 shows the result.
Listing 2-1. Finding a dot product
int[] v1 = {1,2,3}; //First vector
int[] v2 = {3,2,1}; //Second vector
//dot product of vector
v1.Zip(v2, (a,b) => a * b).Dump("Dot Product");
Figure 2-1. The dot product of two vectors {1, 2, 3} and {3, 2, 1}
How It Works
Zip() is a LINQ standard query operator that operates on two members at the same location (or index). The delegate passed to Zip() denotes the function used to generate a zipped single value from the members at the same index in two series. For a vector dot product, the function is a simple multiplication denoted by (a,b) => a * b.
2-2. Math and Statistics: Generating Pythagorean Triples
A Pythagorean triple is a tuple of three integers that can form the sides of a right-triangle.
Problem
Use LINQ to generate a Pythagorean triple.
Solution
The most common Pythagorean triple is {3, 4, 5}. The obvious scheme for generating more of these triples is to multiply an existing triple by some number. For example, multiplying {3, 4, 5} by 2 yields {6, 8, 10}—another Pythagorean triple. However, Babylonians came up with a more general formula for generating Pythagorean triples: The base and height assume the values of c * c –1 and 2 * c, respectively, where c represents a number greater than or equal to 2. The hypotenuse, the longest side of a right triangle, is always one greater than the square of that number (c).
Listing 2-2 generates Pythagorean triplets by using the old and simple Babylonian formula.
Listing 2-2. Generating Pythagorean triples with the Babylonian formula
Enumerable.Range(2,10)
.Select (c => new {Length = 2*c,
Height = c * c - 1,
Hypotenuse = c * c + 1})
.Dump("Pythagorean Triples");
This generates the output shown in Figure 2-2.
Figure 2-2. Pythagorean triplets generated by the Babylonian method
How It Works
This example uses an anonymous type. Note that the code doesn’t define a type with properties or fields named Length, Height, or Hypotenuse. However, LINQ doesn’t complain. LINQPad clearly shows that the type of the projected collection is anonymous. Check out the tool tip shown in Figure 2-3.
Figure 2-3. A tool tip that shows the projection of the anonymous type
This feature is useful because it saves you from having to create placeholder classes or using tuples. (The example could have used a Tuple<int,int,int> in place of the anonymous method, but using the anonymous type improves readability.) If, however, you project the result to aList<T> and then try to dereference it by using an index, you will see the properties Length, Height, and Hypotenuse as shown in Figure 2-4—just as if you had defined a strongly typed collection of some type with those public properties.
Figure 2-4. The properties of the anonymous type show up in IntelliSense
2-3. Math and Statistics: Finding a Weighted Sum
Finding vector dot products has real-world applications, the most common of which is finding a weighted sum.
Problem
Suppose every subject in an exam has a different weight. In such a setting, each student’s score is the weighted sum of the weight for each subject and the score obtained by the student in that subject. The problem here is to use LINQ to find the weighted sum.
Solution
Mathematically, the weighted sum is the sum of the coefficients of the vector dot product, which you can obtain easily with LINQ, by using Zip() and Sum(). Listing 2-3 shows the solution.
Listing 2-3. Finding a weighted sum
int[] values = {1,2,3};
int[] weights = {3,2,1};
//dot product of vector
values.Zip(weights, (value,weight) =>
value * weight) //same as a dot product
.Sum() //sum of the multiplications of values and weights
.Dump("Weighted Sum");
Figure 2-5 shows the results.
Figure 2-5. The weighted sum of two vectors
How It Works
The call to Zip() creates a dot product, while the call to Sum() adds the results of multiplying the values and weights.
2-4. Math and Statistics: Finding the Percentile for Each Element in an Array of Numbers
Percentile is a measure most often used to analyze the result of a competitive examination. It gives the percentage of people who scored below a given score obtained by a student.
Problem
Imagine you have a list of scores and want to find the percentile for each score. In other words, you want to calculate the percentage of people who scored below that score.
Solution
Listing 2-4 shows the solution.
Listing 2-4. Score percentile solution
int[] nums = {20,15,31,34,35,40,50,90,99,100};
nums
.ToLookup(k=>k, k=> nums.Where (n => n<k))
.Select(k => new KeyValuePair<int,double>
(k.Key,100*((double)k.First().Count()/(double)nums.Length)))
.Dump("Percentile");
The code creates a lookup table in which each score becomes a key, and the values for that key are all the scores less than the key. For example, the first key is 20, which has a single value: 15 (because 15 is the only score less than 20). The second key is 15, which has no values (because that’s the lowest score).
Next, the code creates a list of KeyValuePair objects, each of which contains the key from the lookup table, and a calculated percentile, obtained by multiplying the number of values that appear under each key in the lookup table by 100 and then dividing that by the number of scores (10 in this case).
This code generates the output shown in Figure 2-6.
Figure 2-6. Score and percentile obtained by students
Finding the rank of each mark is also simple, as you obtain rank from percentile. The student with the highest percentile gets the first rank, and the student with the lowest percentile gets the last rank, as shown in Listing 2-5.
Listing 2-5. Obtaining score ranking from percentile
int[] marks = {20,15,31,34,35,50,40,90,99,100};
marks
.ToLookup(k=>k, k=> marks.Where (n => n>=k))
.Select (k => new {
Marks = k.Key,
Rank = 10*((double)k.First().Count()/(double)marks.Length)
})
.Dump("Ranks");
Figure 2-7 shows the ranks of the students derived from the percentile.
Figure 2-7. Student rank derived from percentile
How It Works
This example uses a lookup table to find out the percentile. The keys in the lookup table hold the number, and the values are all those numbers that are smaller than that number. Later the code finds the percent of these values against the total number of items. That yields the percentile for the particular number represented by the key.
2-5. Math and Statistics: Finding the Dominator in an Array
A dominator is an element in an array that repeats in more than 50 percent of the array positions.
Problem
Assume you have the following array: {3, 4, 3, 2, 3, -1, 3, 3}. There are eight elements, and 3 appears in five of those. So in this case the dominator is 3. The problem is to use LINQ to find the dominator in an array.
Solution
The first algorithm that comes to mind to find a dominator has to loop through the array twice and thus has quadratic time complexity, but you can improve the efficiency by using a lookup. Listing 2-6 shows the solution.
Listing 2-6. Finding the array dominator
int[] array = { 3, 4, 3, 2, 3, -1, 3, 3};
array.ToLookup (a => a).First (a => a.Count() >
array.Length/2).Key.Dump("Dominator");
This generates the result shown in Figure 2-8.
Figure 2-8. The dominator of an array
How It Works
array.ToLookup (a => a) creates a lookup table in which the keys are the values. Because there are duplicates, there will be many values. However, you are interested in only the first value. So an item that has occurred more than array.Length / 2 times is the dominator. And you will find that dominator as the key of this element in the lookup table.
2-6. Math and Statistics: Finding the Minimum Number of Currency Bills Required for a Given Amount
Machines that process financial transactions involving cash, such as ATM machines or self-service grocery checkout stations, must be able to make change efficiently, providing users with the minimum number of bills required to add up to a specific amount.
Problem
Given all the currencies available in a country and an amount, write a program that determines the minimum number of currency bills required to match that amount.
Solution
Listing 2-7 shows the solution.
Listing 2-7. Finding minimum number of currency bills
//These are available currencies
int[] curvals = {500,100,50,20,10,5,2,1,1000};
int amount = 2548;
Dictionary<int,int> map = new Dictionary<int,int>();
curvals.OrderByDescending (c => c)
.ToList()
.ForEach(c => {map.Add(c,amount/c); amount = amount % c;});
map.Where (m => m.Value!=0)
.Dump();
When you run this query in LINQPad, you will see the output shown in Figure 2-9. The Key column shows the face value of various bills, while the Value column shows the number of those bills required to add up to the target value.
Figure 2-9. Output of the minimum currency bill count query
How It Works
The algorithm to find the minimum number of currency bills required is recursive. It is a continuous division of the value by the largest currency value that results in an integer greater than or equal to 1, repeated against the remainder until the value of the amount diminishes to zero.
amount/c (amount divided by c) calculates the number of currency bills required with value c. The remaining amount is the remainder, as calculated by amount % c.
The data is stored as a currency and currency count pair in the C# dictionary map. Each dictionary key is a currency bill face value, and the value is the number of such currency bills required to total the given amount, using the minimum number of currency bills. Thus, any nonzero value in the map is what you should look for. The LINQ query map.Where (m => m.Value!=0) does just that. And that’s about it!
LINQPad has a cool feature that sums up the values in the Value column. In this case, that summation is 8. That means it will require a minimum of eight currency bills to make 2,548.
The first call to OrderByDescending() makes sure that you start with the highest available currency value.
2-7. Math and Statistics: Finding Moving Averages
Finding a moving average is a problem that often arises in time series analysis, where it’s used to smooth out local fluctuations. A moving average is just what it says—an average that “moves.” In other words, it is the average of all elements that fall within a moving window of a predefined size. For example, suppose you have the numbers 1, 2, 3, 4, and the window size is 2. In that case, there are three moving averages: the average of 1 and 2, the average of 2 and 3, and the average of 3 and 4.
Problem
Create a program that finds the moving average of given window size.
Solution
Listing 2-8 shows the solution.
Listing 2-8. Finding a moving average
List<double> numbers = new List<double>(){1,2,3,4};
List<double> movingAvgs = new List<double>();
//moving window is of length 4.
int windowSize = 2;
Enumerable.Range(0,numbers.Count - windowSize + 1)
.ToList()
.ForEach(k => movingAvgs.Add(numbers.Skip(k).Take(windowSize).Average()));
//Listing moving averages
movingAvgs.Dump();
This generates the output shown in Figure 2-10.
Figure 2-10. The moving average of 1, 2, 3, 4 with window size 2
How It Works
The first step toward calculating the moving average is to find the moving sum. And to find the moving sum, you need to find the elements currently available under the window.
Figure 2-11 shows the movement of the sliding window as the gray rectangle in each row. The moving window slides across the array for a given window size of 2.
Figure 2-11. A sliding window over example input data for calculating the moving average
At first the sliding window has two elements: 1 and 2. Then it slides toward the right by one position. The movement of the sliding window can be described as follows: At first, no element is skipped and the 2 element is taken. Then the 1 element is skipped and the 2 element is taken, and so forth. Thus in general you can find the elements currently present in the sliding window by using the following LINQ query numbers.Skip(k).Take(windowSize), where k ranges from 0 to numbers.Count - windowSize + 1.
The LSQO Average() finds the average of the sequence. Thus all the moving averages are stored in listmovingAvgs.
2-8. Math and Statistics: Finding a Cumulative Sum
To find the growth of a variable, you have to measure it at regular intervals.
Problem
Let’s say you have a list of numbers that represent the value of some business entity, which varies year to year. You want to measure the growth percentage for that entity from year to year. Remember that the numbers in the list represent entity values for a particular year, not a cumulative amount up until that year. However, to measure growth, you need a value that represents the previous total. This value is called a cumulative sum. The problem is to write a function to find the cumulative sum of a given sequence by using LINQ standard query operators.
Solution
Listing 2-9 shows the solution.
Listing 2-9. Cumulative sum solution
List<KeyValuePair<int,int>> cumSums =
new List<KeyValuePair<int,int>>();
var range = Enumerable.Range(1,10);
range.ToList().ForEach( k => cumSums.Add(
new KeyValuePair<int,int>(k,range.Take(k).Sum())));
cumSums.Dump("Numbers and \"Cumulative Sum\" at each level");
This generates the output shown in Figure 2-12.
Figure 2-12. A sequence and the cumulative sum of the sequence at each stage
How It Works
The code is fairly self-explanatory. If you were to describe the cumulative sum (sometimes referred to as a cumsum) algorithm to your grandma, you might say, “Grandma, take the first element, then the sum of the the first two elements, then the sum of the first three elements, and so on until you run out of elements.” Now look at the code. Doesn’t it look just like that? To show a number and then the cumulative sum up to that number, I am using a List<KeyValuePair<int,int>>.
A pattern that can be expressed using a recurrence relation is known as a recursive pattern. For example, fractals are recursive patterns. Their entire fractal structure resembles the smallest building block. In the following problems, you will explore how to use LINQ to generate such patterns.
2-9. Recursive Series and Patterns: Generating Recursive Structures by Using L-System Grammar
Aristid Lindenmayer was a Hungarian biologist who developed a system of formal languages that are today called Lindenmayer systems, or L-systems (see http://en.wikipedia.org/wiki/L-system). Lindenmayer used these languages to model the behavior of plant cells. Today, L-systems are also used to model whole plants.
Problem
Lindenmayer described the growth of algae as follows: At first the algae is represented by an A. Later this A is replaced by AB, and B is replaced by A. So the algae grows like this. The letter n denotes the iteration:
n = 0 : A
n = 1 : AB
n = 2 : ABA
n = 3 : ABAAB
n = 4 : ABAABABA
n = 5 : ABAABABAABAAB
n = 6 : ABAABABAABAABABAABABA
n = 7 : ABAABABAABAABABAABABAABAABABAABAAB
The problem here is to simulate the growth of algae by using a functional programming approach.
Solution
Listing 2-10 simulates the growth of algae as described by an L-system.
Listing 2-10. Algal growth using L-system grammar
string algae = "A";
Func<string,string> transformA = x => x.Replace("A","AB");
Func<string,string> markBs = x => x.Replace("B","[B]");
Func<string,string> transformB = x => x.Replace("[B]","A");
int length = 7;
Enumerable.Range(1,length).ToList()
.ForEach ( k => algae = transformB(transformA(markBs(algae))));
algae.Dump("Algae at 7th Iteration");
This generates the algae at its seventh iteration, as shown in Figure 2-13.
Figure 2-13. Algae at its seventh iteration
How It Works
The trick is to identify which Bs to modify for the current iteration. Because A gets transformed to AB and B gets transformed to A, you need to do the transformation for A first, followed by the transformation of B. The code transformB(transformA(markBs(algae))) does that in the described order.
2-10. Recursive Series and Patterns Step-by-Step Growth of Algae
The previous example shows only the final stage of the algae. However, by modifying the example slightly, you can show the growth of the algae at each stage.
Problem
Modify the program in Listing 2-10 so that it shows the growth of the algae at each stage.
Solution
The bold code in Listing 2-11 shows the changes made to the previous example.
Listing 2-11. Algal growth shown by stages
string algae = "A";
Func<string,string> transformA = x => x.Replace("A","AB");
Func<string,string> markBs = x => x.Replace("B","[B]");
Func<string,string> transformB = x => x.Replace("[B]","A");
int length = 7;
Enumerable.Range(1,length)
.Select (k => new KeyValuePair<int,string>(
k,algae = transformB(transformA(markBs(algae)))))
.Dump("Showing the growth of the algae as described by L-System");
This shows the growth of the algae at each stage, as shown in Figure 2-14.
Figure 2-14. The growth of the algae at each iteration
How It Works
Unlike the previous version, this version stores the state of the algae at each stage, projected as a key/value pair, where the key represents the number of the iteration, and the value represents the stage of the algae at that iteration. Interestingly, the length of the algae string always forms a Fibonacci series. At the second iteration (the number 1 in the preceding output), the value of the algae is AB, so the length of the algae is 2. At the third iteration, the algae is ABA, and the length is 3. At the fourth iteration, the algae is ABAAB, and the length is 5 (the next Fibonacci number after 3), and so on.
You can project the length of the algae by using Listing 2-12; changes from the preceding example are shown in bold.
Listing 2-12. Projecting the length of algal strings
int length = 5;
Enumerable.Range(1,length)
.Select (k => new Tuple<int,string,int>(k,algae =
transformB(transformA(markBs(algae))),algae.Length))
.Dump("The length of the alage forms the Fibonacci Series");
This generates the output shown in Figure 2-15.
Figure 2-15. The length of the algae at each iteration forms the Fibonacci series
This table has three columns: Item1, Item2, and Item3. The first column, Item1, shows the serial number depicting the stage of the algae growth. Item2 shows the algae, and Item3 shows the length of the algae at that stage. At each stage, the length of the algae is a Fibonacci number.
2-11. Recursive Series and Patterns: Generating Logo Commands to Draw a Koch Curve
Logo is a computer language created for teaching programming. One of its features is turtle graphics, in which the programmer directs a virtual onscreen turtle to draw shapes by using simple commands such as turn left, turn right, start drawing, stop drawing, and so on.
Problem
You can generate several fractals, including the Sierpinksi Triangle, Koch curve, and Hilbert curve by using the L-system and a series of generated turtle graphics commands. These commands consist of constants and axioms. For example, here are the details to generate a Koch curve:
· Variables: F
· Constants: +, −
· Start: F
· Rules: (F → F+F−F−F+F) //This means at each iteration, "F" has to be replaced by "F+F-F-F+F"
Here, F means draw forward, plus (+) means turn left 90°, and minus (−) means turn right 90° (for a more complete explanation, see http://en.wikipedia.org/wiki/Turtle_graphics). The problem here is to generate a Koch curve and related patterns by using LINQ.
Solution
Listing 2-13 shows the code that generates the Logo commands to create a Koch curve.
Listing 2-13. Generate Logo commands to create a Koch curve
string koch = "F";
Func<string,string> transform = x => x.Replace("F","F+F-F-F+F");
int length = 3;
//Initialize the location and direction of the turtle
string command = @"home
setxy 10 340
right 90
";
//Finish it in the next line so a new line appears in the command
command += Enumerable.Range(1,length)
.Select (k => koch = transform(koch))
.Last()
.Replace("F","forward 15")
.Replace("+",Environment.NewLine + "Left 90" +
Environment.NewLine)
.Replace("-",Environment.NewLine + "Right 90" +
Environment.NewLine);
command.Dump();
How It Works
This generates the output partially shown in Figure 2-16.
Figure 2-16. The first few generated Logo commands to draw a Koch curve
Note To see how a Koch curve is drawn in Logo, go to http://logo.twentygototen.org/ and paste the generated command in the text box on the right-hand side. Then click Run Normally or Run Slowly to see how the curve is drawn. I have uploaded a demo. You can check it out at www.youtube.com/watch?v=hdSMPp607tI&feature=youtu.be.
2-12. Recursive Series and Patterns: Generating Logo Commands to Draw a Sierpinski Triangle
By following a pattern similar to that discussed in the previous section, you can generate Logo commands to draw Sierpinski triangles.
Problem
The rules to draw a Sierpinski triangle are as follows:
· Variables: A, B
· Constants: +, −
· Start: A
· Rules: (A → B − A − B), (B → A + B + A)
· Angle: 60°
Here, A and B both mean draw forward, a plus sign (+) means turn left by some angle, and a minus sign (−) means turn right by some angle. The problem here is to use LINQ to follow the rules and draw a Sierpinski triangle.
Solution
Listing 2-14 shows the code to generate the Logo commands that draw the Sierpinski triangle.
Listing 2-14. Generate Logo commands to draw a Serpinski triangle
string serpinskiTriangle = "A";
Func<string,string> transformA = x => x.Replace("A","B-A-B");
Func<string,string> markBs = x => x.Replace("B","[B]");
Func<string,string> transformB = x => x.Replace("[B]","A+B+A");
int length = 6;
Enumerable.Range(1,length)
.ToList()
.ForEach (k => serpinskiTriangle =
transformB(transformA(markBs(serpinskyTriangle))));
serpinskiTriangle
.Replace("A", "forward 5" + Environment.NewLine)
.Replace("B", "forward 5" + Environment.NewLine)
.Replace("+", "left 60" + Environment.NewLine)
.Replace("-", "right 60" + Environment.NewLine)
.Dump("LOGO Commands for drawing Serpinsky Triangle");
How It Works
You can follow the same structure to generate several other fascinating space-filling graphs such as the dragon curve or the Hilbert curve. To see these fractals generated at each iteration, visit www.kevs3d.co.uk/dev/lsystems/.
2-13. Recursive Series and Patterns: Generating Fibonacci Numbers Nonrecursively (Much Faster)
Generating a Fibonacci series is one of the classic recursive algorithms. You may already be familiar with the Fibonacci series; however, for the sake of completeness, here’s a brief explanation. The Fibonacci series is a recursive series in which each item is the sum of the previous two items in the series.
Problem
Here are the first few terms in the Fibonacci series: 1, 1, 2, 3, 5, 8, 13, 21. Generating those is simple enough. However, recursively calculating Fibonacci numbers takes quite some time and sometimes can cause overflow. By using a collection and saving the last two numbers to add, you can make it much faster. The problem here is to write some LINQ code that uses the faster method.
Solution
Listing 2-15 shows the solution. For each item in the initial range, the query checks to see if it’s less than or equal to 1. If so, it adds a 1 to the fibonacciNumbers list. Otherwise, it adds the sum of the last two numbers in the fibonacciNumbers list.
Listing 2-15. Generating Fibonacci numbers with LINQ
List<ulong> fibonacciNumbers = new List<ulong>();
Enumerable.Range(0,200)
.ToList()
.ForEach(k =>
fibonacciNumbers.Add(k <= 1 ? 1:
fibonacciNumbers[k-2] + fibonacciNumbers[k-1]));
fibonacciNumbers.Take(10).Dump("Fibonacci Numbers");
This displays the first ten Fibonacci numbers, as shown in Figure 2-17.
Figure 2-17. The first ten Fibonacci numbers
How It Works
The problem with recursion is that it’s stateless. In plain English, that means recursive algorithms are forgetful—they don’t remember what they calculated in previous iterations.
To solve this, you need a collection to hold the previously calculated values. After you have that collection, the next entry to be added is the sum of the two preceding elements denoted by fibonacciNumbers[k-2] and fibonacciNumbers[k-1].
The technique represented in the preceding example is a scheme to make this recursive program run faster. There are several such problems, and because the pattern of these problems is the same, you can create a common generic structure to generate the results.
2-14. Recursive Series and Patterns: Generating Permutations
Generating permutations of a sequence is important in several applications. The following code generates all permutations of a given string. However, the algorithm can be extended to use with any data type.
Problem
Generate permutations of a given sequence.
Tip For this code to work, you have to change the LINQPad language combo box to C# Program.
Solution
Listing 2-16 shows the solution.
Listing 2-16.
private HashSet<string> GeneratePartialPermutation(string word)
{
return new HashSet<string>(Enumerable.Range(0,word.Length)
.Select(i => word.Remove(i,1).Insert(0,word[i].ToString())));
}
void Main()
{
HashSet<string> perms = GeneratePartialPermutation("abc");
Enumerable.Range(0,2)
.ToList()
.ForEach
(
c=>
{
Enumerable.Range(0,perms.Count ())
.ToList()
.ForEach
(
i => GeneratePartialPermutation(
perms.ElementAt(i))
.ToList().ForEach(p=>perms.Add(p))
);
Enumerable.Range(0,perms.Count ())
.ToList()
.ForEach
(
i => GeneratePartialPermutation(new string
(perms.ElementAt(i).ToCharArray()
.Reverse().ToArray())
)
.ToList().ForEach(p=>perms.Add(p)));
});
perms.OrderBy (p => p).Dump("Permutations of 'abc'");
}
This generates the output shown in Figure 2-18.
Figure 2-18. Permutations of the string abc
How It Works
The first step in generating permutations is to generate rotated versions of the given sequence. To do this, you bring each character to the front, leaving the order of the other characters unchanged. That’s what the method GeneratePartialPermutation() does. So if the word is abcd,GeneratePartialPermutation() will return a set containing the items {"abcd", "bacd", "cabd", "dabc"}.
The next step is to generate the partial permutation for each of these and then the reverse of each. By running this process twice, you can ensure that you have traversed all possible permutations of the given string.
Finally, the code sorts the generated set of permutations alphabetically by using OrderBy().
2-15. Recursive Series and Patterns: Generating a Power Set of a Given Set
A power set is a set that contains all possible sets that can be created from the elements of the given set.
Problem
For the set {'a', 'b', 'c'}, the power set will be {"a", "ab", "bc", "ca", "abc"}. The problem is to write some LINQ code to generate the power set from any given set.
Solution
Listing 2-17 generates a power set from all the characters of a given string.
Listing 2-17. Create a power set from a given string
void Main()
{
string word = "abc";
HashSet<string> perms = GeneratePartialPermutation(word);
Enumerable.Range(0,word.Length).ToList().ForEach(x=>
Enumerable.Range(0,word.Length)
.ToList()
.ForEach( z=>
{
perms.Add(perms.ElementAt(x).Substring(0,z));
perms.Add(perms.ElementAt(x).Substring(z+1));
}));
perms.Select (p => new string(p.ToCharArray()
.OrderBy (x => x)
.ToArray()))
.Distinct()
.OrderBy (p =>p.Length )
.Dump("Power-set of 'abc'");
}
This code generates the power set of the string abc, as shown in Figure 2-19.
Figure 2-19. The power set of the set formed from the characters of the string abc
How It Works
This solution starts by creating the partial permutation list of the given word. Note that to get the elements of the power set, it is sufficient to split each partial permutation at each index and take the first and last token. For example, the word abc will generate these three element pairs: {"a", "bc"}, {"ab", "c"}, {"abc"}. By doing this for all the partial permutations, you are guaranteed to have generated all elements of the power set. However, this technique produces duplicate elements. Therefore, the final step sorts the characters of these tokens alphabetically and removes duplicates by using a Distinct() call. This leaves us with all the elements of the power set of the characters of the given word: abc, in this case.
We have all written code to manipulate in-memory collections by using a traditional loop-and-branch style. However, with LINQ, these types of manipulations become easy. In the following sections, some of these are solved using LINQ operators that appear often as subproblems in our code.
2-16. Collections: Picking Every nth Element
Picking every nth element from a given collection is a common problem that often appears as a subproblem of other problems such as shuffling or load distribution. The idea is to pick every nth element without dividing the index to figure out whether to include an entry.
Problem
Write an idiomatic LINQ query to find every nth element from a given sequence.
Solution
The code in Listing 2-18 shows the solution.
Listing 2-18. Picking every nth element from a given collection
int n = 20; //Pick every 20th element.
List<int> numbers = Enumerable.Range(1,100).ToList();
List<int> nthElements = new List<int>();
Enumerable.Range(0,numbers.Count()/n)
.ToList()
.ForEach(k => nthElements.Add(numbers.Skip(k*n).First()));
nthElements.Dump();
The output of the program is shown in Figure 2-20.
Figure 2-20. The result of picking every 20th element
How It Works
This example uses Skip() and First() in unison. This is idiomatic LINQ usage that you’ll find in many applications. If you want to pick every nth element, there will be exactly (numbers.Count()/n) + 1 elements after the pick, starting at the first index. In this case, the value fork ranges from 0 to 4. Thus the code snippet numbers.Skip (k*n).First() picks the first element after skipping k*n items from the left for all values of k starting at 0 and ending at 4. So when k is 1, the query skips the first 20 (because k*n is 20) elements, and then picks the next element (the 21st element in this case). This process continues until the end of the series.
2-17. Collections: Finding the Larger or Smaller of Several Sequences at Each Index
Finding the minimum or the maximum value at each location from several collections of the same length is useful for many applications.
Problem
Imagine that the numbers in some collections denote the bidding values for several different items. You want to find the maximum and minimum bid values for all the items. The problem is to write a generic LINQ query to find such values easily.
Solution
Listing 2-19 shows the solution.
Listing 2-19. Picking minimum or maximum values from multiple collections
List<int> bidValues1 = new List<int>(){1,2,3,4,5};
List<int> bidValues2 = new List<int>(){2,1,4,5,6};
bidValues1.Zip(bidValues2, (firstBid,secondBid) =>
Math.Max(firstBid,secondBid))
.Dump("Maximum bids");
bidValues1.Zip(bidValues2, (firstBid,secondBid) =>
Math.Min(firstBid,secondBid))
.Dump("Minimum bids");
This generates the output in Figure 2-21, which shows the minimum and maximum bid values at each stage.
Figure 2-21. Member-wise maximum and minimum values
This example uses only two collections; however, in a real setting, you might need to extract minimum and/or maximum values at one or more specified locations from many collections.
While the code shown so far works, LINQ provides a cleaner way to solve the problem (see Listing 2-20).
Listing 2-20. A better LINQ solution for picking minimum and maximum values from multiple collections
List<List<int>> allValues = new List<List<int>>();
List<int> bidValues1 = new List<int>(){1,2,3,4,5};
List<int> bidValues2 = new List<int>(){2,1,4,5,6};
List<int> bidValues3 = new List<int>(){4,0,6,8,1};
List<int> bidValues4 = new List<int>(){9,2,4,1,6};
//Add all collections in this list of collections.
allValues.Add(bidValues1);
allValues.Add(bidValues2);
allValues.Add(bidValues3);
allValues.Add(bidValues4);
//Showing the maximum values compared at each location for 4 collections
allValues
.Aggregate((z1,z2) => z1.Zip(z2,(x,y) => Math.Max(x,y)).ToList())
.Dump("Maximum values : Generalized Approach");
//Showing the minimum values compared at each location for 4 collections
allValues
.Aggregate((z1,z2) => z1.Zip(z2,(x,y) => Math.Min(x,y)).ToList())
.Dump("Minimum values : Generalized Approach");
The preceding code generates the output in Figure 2-22, which shows minimum and maximum bid amounts at each stage.
Figure 2-22. Maximum and minimum values from several collections at each location
How It Works
This is a little tricky. The solution aggregates a list of lists over their zipped values. It may take some time to wrap your head around this.
Consider the following code:
Aggregate((z1,z2) => z1.Zip(z2,(x,y) => Math.Min(x,y)).ToList())
Here, z1 and z2 are of type List<int>. The inner call to Zip() uses the minimum value at each location to find out what the result should be at that location. Thus, at each level of aggregation (which processes two lists at a time), you always have a collection that has the minimum values at each location for all the collections aggregated thus far, as shown in Figure 2-23.
Figure 2-23. How the minimum values get picked at each stage
These tables illustrate how the code finds the minimum number at each location and at each stage. The resulting collection, containing the minimum value at each location for the initial two lists, serves as the first argument in the next step. Changed values at each step are in the third column of the table.
Number theory has some fascinating examples of series generation in action. Most of us were taught programming using these examples. If you have been programming for a while, you likely are familiar with the number sequences described here. That choice is deliberate. I wanted to show how LINQ can help us approach the problem differently.
2-18. Number Theory: Generating Armstrong Numbers and Similar Number Sequences
In recreational mathematics, an Armstrong number is a topic of interest. An Armstrong number is a number that is the same as the sum of its digits raised to the power of three. For example, consider the number 153, as shown in Figure 2-24.
Figure 2-24. An Armstrong number
Note that the number is obtained by summing up all its digits raised to the power of three.
A Dudeney number is a positive integer that is a perfect cube, such that the sum of its decimal digits is equal to the cube root of the number. Consider the number 512. The sum of the digits in 512 is 8. And the cube of 8 is 512. Stated another way, the cube root of 512 is 8, which is the sum of the digits of 512.
A sum-product number is an integer that in a given base is equal to the sum of its digits times the product of its digits. Or, to put it algebraically, given an integer n that is l digit long in base b (with dx representing the xth digit), if the following condition shown in Figure 2-25
Figure 2-25. Equation of a sum-product number
A factorion is a natural number that equals the sum of the factorials of its decimal digits. For example, 145 is a factorion because 1! + 4! + 5! = 1 + 24 + 120 = 145.
Problem
Given a range, can you find all the Armstrong numbers, Dudeney numbers, sum-product numbers, or factorions in that range?
Solution
Because all these number definitions deal with the digits of integer numbers, you can first create a method to extract the individual digits of a number from a given integer. Listing 2-21 shows the code for an extension method that extracts digits from a given integer number.
Listing 2-21. Finding Armstrong numbers, Dudeney numbers, sum-product numbers, and factorions in a range
public static class NumberEx
{
public static IEnumerable<int> Digits(this int n)
{
List<char> chars = new List<char>() {'0','1','2','3','4','5','6','7','8','9'};
List<int> digits = new List<int>();
foreach (char c in n.ToString())
digits.Add(chars.IndexOf(c));
return digits.AsEnumerable();
}
}
void Main()
{
Enumerable.Range(0,1000)
.Where(k => k.Digits().Select (x => x * x * x).Sum() == k)
.Dump("Armstrong Numbers");
Enumerable.Range(0,1000)
.Where(k => {
var digits = k.Digits();
if(digits.Sum() * digits.Aggregate ((x,y) =>x*y) == k)
return true;
else
return false;
}).Dump("Sum Product Numbers");
Enumerable.Range(0,1000)
.Where (e => Math.Pow(e.Digits().Sum(),3) == e)
.Dump("Dudeney Numbers");
Enumerable.Range(1,1000)
.Where (e => e.Digits()
.Where (d => d > 0)
.Select(x =>Enumerable.Range(1,x)
.Aggregate((a,b) => a*b)) //Calculating factorial of each digit
.Sum() //Calculating summation of factorials
== e) //when summation matches number it's a factorion
.Dump("Factorions");
}
This generates the output shown in Figure 2-26.
Figure 2-26. Armstrong numbers and other similar numbers
How It Works
At the heart of these examples is the Digits() extension method that returns a List<int> containing the individual digits. For example, 153.Digits() returns a List<int> containing the values {1, 5, and 3}.
Let’s start with Armstrong numbers. The following code projects each digit of the number k as its cube, and then sums the projected values:
k.Digits().Select (x => x * x * x).Sum()
For example, if k is 153, then k.Digits().Select (x => x * x * x) returns {1 , 125, 27}, The Sum() operator totals these projected values. Because the sum of 1, 125, and 27 is 153, 153 is a valid Armstrong number. To find the sum-product numbers, you need to find the sum and the product of digits. digits.Sum() returns the sum of the digits, and digits.Aggregate ((x,y) =>x*y) finds the product of the digits. If the product of these two figures matches the number itself, you can declare that the number is a sum-product number.
The code for finding Dudeney numbers couldn’t be more straightforward. It is one of those perfect examples that shows how LINQ can make code look more intuitive and yet be more readable at the same time.
The code for finding factorions is a little trickier; however, the algorithm is simple. First, find all the digits of the number. Then discard all zeros because a factorial of zero doesn’t make sense. Then, for all such nonzero digits, go to that digit starting from 1. Multiply all the digits you encounter along the way. This will give you the factorial of each digit. If you want to avoid this step, you can precalculate and save the factorials of digits 1 to 9 in a dictionary. At the end, you sum these factorials. If the sum matches the number, that number is a factorion.
2-19. Number Theory: Generating Pascal’s Triangle Nonrecursively
In mathematics, Pascal’s triangle is a triangular array of the binomial coefficients. It is named after the French mathematician Blaise Pascal. The first few rows of the Pascal triangle are shown in Figure 2-27.
Figure 2-27. The first few rows of Pascal’s triangle
The structure is recursive. Apart from the first and the last column, every value is the sum of the elements just above it. For example, the 4 in the next-to-last row in Figure 2-27 is the result of adding 1 and 3 immediately above it. Classically, these number triangles are created by calling a function recursively, passing the row and column position. But as the number of rows increases, this method becomes very slow and may even throw an out-of-memory exception because the stack overflows. However, you can avoid the recursion by using extra storage.
Problem
The problem here is to avoid recursion by using external storage. In functional programming, this technique is known as memoization.
Listing 2-22 shows some code that generates the Pascal’s triangle without recursion. It’s much faster than the recursive version.
Solution
Listing 2-22 shows the solution.
Listing 2-22. Generating a Pascal’s triangle without recursion
List<Tuple<int,int,int>> pascalValues = new List<Tuple<int,int,int>>();
pascalValues.Add(new Tuple<int,int,int>(1,1,1));
pascalValues.Add(new Tuple<int,int,int>(2,1,1));
pascalValues.Add(new Tuple<int,int,int>(2,2,1));
for(int i=1;i<10;i++)
{
int currentRow = pascalValues.Last().Item1 + 1;
int currentCol = pascalValues.Last().Item2 + 1;
for(int j = 1;j<=currentCol;j++)
{
if(j==1 || j== currentCol)
pascalValues.Add(new Tuple<int,int,int>(currentRow,j,1));
else
pascalValues.Add(new Tuple<int,int,int>(currentRow,j,
pascalValues.First (v => v.Item1 == currentRow - 1 &&
v.Item2 == j - 1).Item3 +
pascalValues.First (v => v.Item1 == currentRow - 1 &&
v.Item2 == j).Item3 ));
}
}
//Show the table
pascalValues
.ToLookup(t=>t.Item1,t=>t.Item3.ToString())
.Select (t => t.Aggregate ((x,y) => x + " " + y ))
.Aggregate ((u,v) => u + Environment.NewLine + v)
.Dump("Pascal's Triangle");
This generates the output shown in Figure 2-28.
Figure 2-28. The first tenrows of Pascal’s triangle
How It Works
You can represent number triangles as a series of tuples, where each tuple stores the row, column, and the value at the row, col position. For example, you can use a List<Tuple<int,int,int>> in C# where the first item in the tuple represents the row, the second item represents the column, and the third/last item represents the value at that (row, col) position in the triangle.
These three lines store the first three items of the triangle:
pascalValues.Add(new Tuple<int,int,int>(1,1,1));
pascalValues.Add(new Tuple<int,int,int>(2,1,1));
pascalValues.Add(new Tuple<int,int,int>(2,2,1));
For the first and the last column, the value is always 1. The following code takes care of filling that correctly:
if(j==1 || j== currentCol)
pascalValues.Add(new Tuple<int,int,int>(currentRow,j,1));
Every other element is the sum of the element directly above it (same column, previous row) and the element diagonally above it (previous column, previous row). The following code obtains this value:
pascalValues.Add(new Tuple<int,int,int>(currentRow,j,
pascalValues.First (v => v.Item1 == currentRow - 1 && v.Item2 == j - 1).Item3 +
pascalValues.First (v => v.Item1 == currentRow - 1 && v.Item2 == j).Item3 ));
You can apply similar logic to generate all other number triangles.
2-20. Game Design: Finding All Winning Paths in an Arbitrary Tic-Tac-Toe Board
Most tic-tac-toe boards are 3×3 grids. Tic-tac-toe game implementations usually hard-code the winning paths in the code. However, if you want to create a game that uses an arbitrary-size tic-tac-toe board, you have to find out the winning paths at runtime—whenever the user changes the board size. Because tic-tac-toe boards are square, you can represent a 3×3 board by the integer 3.
Problem
Generate all winning paths of an arbitrarily sized tic-tac-toe board, starting the cell numbering at 1. For a 3×3 board, the cells range from 1 to 9. For a 4×4 board, cells range from 1 to 16.
Solution
Listing 2-23 shows the solution.
Listing 2-23. Generate winning paths for a tic-tac-toe board
int boardSize = 3;
var range = Enumerable.Range(1,boardSize*boardSize);
List<List<int>> winningPaths = new List<List<int>>();
//Horizontal Paths
Enumerable.Range(0,boardSize)
.ToList()
.ForEach(k => winningPaths.Add(range.Skip(k*boardSize)
.Take(boardSize).ToList()));
//Vertical Paths
Enumerable.Range(0,boardSize)
.ToList()
.ForEach(k => winningPaths.Add(winningPaths.Take(boardSize)
.Select(p => p[k]).ToList()));
//Diagonal Paths
//Main diagonal
winningPaths.Add(range.Where((r,i) =>
i % (boardSize + 1) == 0).ToList());
//reverse diagonal
winningPaths.Add(range.Where ((r,i) =>
i % (boardSize - 1) == 0).Skip(1).Take(boardSize).ToList());
//printing all the paths; one path on each line.
winningPaths.Select(x => x.Select (z => z.ToString()).Aggregate
((a,b)=> a.ToString () + " " + b.ToString() ))
.Dump("All winning paths for a Tic-Tac-Toe board of size 3");
This generates the output shown in Figure 2-29.
Figure 2-29. All winning paths of a 3×3 tic-tac-toe board
How It Works
Tic-tac-toe boards have four types of winning paths, as shown in Figure 2-30. Follow this hint to find how the code works.
Figure 2-30. The direction of all winning paths in a tic-tac-toe board
Finding horizontal paths is simple. At each stage, you need to take as many elements as the board size. So if the board size is 3×3, you have to take three elements at each stage. Skip() followed by Take() achieves that. This is a common technique. Whenever you want to skip a few elements at each stage and then take one or more, this LINQ idiom comes in handy.
For vertical paths, note that each element in each vertical path is selected from its respective index of the corresponding horizontal paths. Or in other words, vertical paths are a transposition of the matrix created from the horizontal paths.
Finding elements of the main diagonal path is also simple. Elements at the main diagonal appear at a gap of (boardSize + 1). In other words, elements of the main diagonal form an arithmetic progression (AP) with a difference of (boardSize + 1).
The code var range = Enumerable.Range(1,boardSize*boardSize); generates a range of all cell values. Subsequently, the code range.Where ((r,i) => i % (boardSize - 1) == 0) filters the range, skipping the first element, and then pickingboardSize elements, leaving you with the elements of the reverse diagonal.
2-21. Series in Game Design: Solving Go Figure
Go Figure is a puzzle to figure out a mathematical expression involving four unique digits (0 to 9), that evaluate to a given answer. For example, if the set of digits is {1, 2, 4, and 9} and the answer is 10, then (9 + 4) – (2 + 1) is a valid expression. The puzzle challenges players to use mathematical symbols (+, -, and *) and brackets to create an expression. Evaluating the expression results in the given answer.
Problem
Write a program that generates answers for a Go Figure puzzle.
Solution
The program in Listing 2-24 solves the puzzle.
Listing 2-24. Generating answers for a Go-Figure puzzle
//Assume the answer we want to reach is "10"
int answer = 10 ;
//And we want to create 10 using 1, 2, 4 and 9
List<int> set = new List<int>() {1,2,4,9};
List<KeyValuePair<int,string>> query =
set.SelectMany ((s,i) => set.Where (se => se!=s)
.Select (se => new KeyValuePair<int,string>
(se+s,se.ToString()+"+"+s.ToString()))).ToList();
query.AddRange(
set.SelectMany ((s,i) => set.Where (se => se!=s)
.Select (se => new KeyValuePair<int,string>
(se*s,se.ToString()+"*"+s.ToString()))));
query.AddRange(
set.SelectMany ((s,i) => set.Where (se => se!=s)
.Select (se => new KeyValuePair<int,string>
(se-s,se.ToString()+"-"+s.ToString()))));
List<string> expressions = new List<string>();
for(int i=0;i<query.Count();i++)
{
for(int j=0;j<query.Count ();j++)
{
if(i!=j)
{
if(!Regex.Matches(query[i].Value,"[0-9]")
.Cast<Match>()
.Select (m =>Convert.ToInt16(m.Value))
.OrderBy (m => m)
.Any(z => Regex.Matches(query[j].Value,"[0-9]")
.Cast<Match>()
.Select (m =>Convert.ToInt16(m.Value))
.OrderBy (m => m)
.Contains(z)))
{
if(query[i].Key + query[j].Key == answer)
{
expressions.Add("(" + query[i].Value + ") +
(" + query[j].Value +")");
break;
}
if(query[i].Key - query[j].Key == answer)
{
expressions.Add("(" + query[i].Value + ") -
(" + query[j].Value +")");
break;
}
if(query[i].Key * query[j].Key == answer)
{
expressions.Add("(" + query[i].Value + ")
* (" + query[j].Value +")");
break;
}
}
}
}
}
expressions.Dump("Expressions");
This generates the output shown in Figure 2-31.
Figure 2-31. All expressions that result in the answer
How It Works
At the core of this solution is the logic that calculates all the possible values that can be reached by adding, subtracting, or multiplying the given values in the set.
For example, the following code generates a list of key/value pairs, where the keys represent the summation and the values represent the expressions that resulted in the summation. For the given set {1, 4, 2, and 9}, one such entry in this list is represented by the following key and value combination: key = 5, value = 9 – 4.
List<KeyValuePair<int,string>> query =
set.SelectMany ((s,i) => set.Where (se => se!=s )
.Select (se => new KeyValuePair<int,string>(se+s,se.ToString()+"+"+s.ToString()))).ToList();
Similarly, other expressions and their resultant values are calculated and are added to the query. So when * is used between 9 and 4, you get 36 as the value and 9 * 4 as the expression. However, there isn’t any check to identify that 9 * 4 and 4 * 9 are same. Can you bring that in? That would be a good exercise.
After constructing the list of results and expressions, you need to iterate over the list to find the final expression that results in the given answer. However, you must avoid expressions that share the same digit. For example, if you choose 9 – 4 as the first part of the expression, you can’t subsequently use any expression containing either of those digits. The following code checks that.:
if(!Regex.Matches(query[i].Value,"[0-9]")
.Cast<Match>()
.Select (m =>Convert.ToInt16(m.Value))
.OrderBy (m => m)
.Any(z => Regex.Matches(query[j].Value,"[0-9]")
.Cast<Match>()
.Select (m =>Convert.ToInt16(m.Value))
.OrderBy (m => m)
.Contains(z)))
2-22. Miscellaneous Series: Finding Matching Pairs from Two Unsorted Collections
Assume you have two or more unsorted collections and you want to find a pair of entries from these collections that match.
Problem
Here’s a more concrete example. Imagine two arrays containing English words. You want to find words in one array that rhyme with one or more words in the other array. Further, for the purposes of this example, assume that if the last three letters of two words are identical, they probably rhyme. For example, rubble and bubble rhyme, and so do brush and rush. Obviously, this rule doesn’t work for all words. Remember that the solution shouldn’t involve sorting, because that can be computationally expensive—precisely what you should avoid.
Solution
Listing 2-25 shows the solution.
Listing 2-25. Finding matching pairs in two unsorted collections
//finding matching pairs
string[] words1 = {"orange", "herbal", "rubble", "indicative", "mandatory",
"brush", "golden", "diplomatic", "pace"};
string[] words2 = {"verbal", "rush", "pragmatic", "story", "race",
"bubble", "olden"};
//Checking whether the last three characters match.
//is a rudimentary way to tell if two words rhyme.
Func<string,string,bool> mightRhyme = (a,b) =>
a[a.Length-1]==b[b.Length - 1]
&& a[a.Length-2]==b[b.Length - 2]
&& a[a.Length-3]==b[b.Length - 3];
words1
.Select(w => new KeyValuePair<string,string>(w, words2.FirstOrDefault(wo => mightRhyme(w,wo))))
.Where(w => !String.IsNullOrEmpty(w.Value))
.Dump("Matching Pairs");
This query when run on LINQPad generates the output shown in Figure 2-32.
Figure 2-32. The result of matching pair extraction from unsorted collections
How It Works
At first glance, this problem seems to have a straightforward nested loop-based quadratic time solution. You just have to loop through the collections and find the matching pairs one at a time. The preceding code is just a LINQ implementation of this method.
words2.FirstOrDefault(wo => mightRhyme(w,wo) will return the matching pair for w in words2 or it will return null when there no matching pair exists. In this case, the binary predicate is the method mightRhyme, which takes two strings and returns true if their three trailing characters match.
Select(w => new KeyValuePair<string,string>(w, words2.FirstOrDefault(wo => mightRhyme(w,wo))))
This code generates an IEnumerable<KeyValuePair<string,string>>, where the keys hold each word in the array words1 and the values hold rhyming pairs found in the array words2, if any, or null if no matches exist.
The following code filters out pairs for which no rhyming was found:
Where (w => !String.IsNullOrEmpty(w.Value)) That leaves us with rhyming pairs.
2-23. Miscellaneous Series: Using a Lookup-Based Approach
The solution you have explored in this section works. However, it takes quadratic time because it has to loop through the other collection to find rhyming words. So this method is neither scalable nor efficient.
Fortunately, a linear-time solution exists. Because you are finding matching words by matching their last three letters, you can treat the three trailing characters from each word as a hash of each word. So bal is the hash of verbal. The word herbal also has the same ble hash.
Problem
Find pairs of possible rhymes in two lists using a lookup-based approach.
Solution
If you create a lookup table based on the hash (that is, just the last three characters of each word), then wherever the hashes match (a collision, in other words), you have a likely candidate for a rhyming pair. The following query generates the hash-based lookup table and finds potential rhyming words using the same two word lists used in the previous solution:
string[] words1 = {"orange", "herbal", "rubble", "indicative", "mandatory",
"brush", "golden", "diplomatic", "pace"};
string[] words2 = {"verbal", "rush", "pragmatic", "story", "race",
"bubble", "olden"};
words1
.Concat(words2)
.ToLookup(w => w.Substring(w.Length-3))
.Where(w => w.Count() >= 2)
.Select(w => w.Aggregate((m,n)=>m+", "+n))
.Dump("Showing rhyming pairs comma separated");
This generates the output shown in Figure 2-33.
Figure 2-33. Rhyming pair of words selected from two unsorted collections of words
How It Works
words1.Concat(words2) returns the list of all the words.
ToLookup (w => w.Substring(w.Length-3))) creates a lookup table, where the hash is the last three characters of each word. The lookup table looks like Figure 2-34.
Figure 2-34. A lookup table with a hash-key consisting of the last three characters of each word
Now take a close look at the table. The pairs that rhyme have two items. For example, brush and rush share the same hash—ush. So it will be sufficient to find those entries from the lookup table that contain two or more entries. That filtering operation is performed by the code Where (w => w.Count() >= 2). In the final stage, these filtered entries are projected as comma-separated values by Select(w => w.Aggregate((m,n)=>m+", "+n)).
2-24. Miscellaneous Series: Solving the FizzBuzz Challenge in a LINQ One-Liner
The FizzBuzz problem has been used as a litmus test of programming capability among aspiring programming job candidates, which—by itself—makes it worth a bit of study.
Problem
Write a program that prints the numbers from 1 to 100. But for multiples of 3, print Fizz instead of the number, and for the multiples of 5, print Buzz. For numbers that are multiples of both 3 and 5, print FizzBuzz.
Solution
Listing 2-26 shows the solution.
Listing 2-26. Solving the FizzBuzz Challenge with LINQ
List<string> fizzBuzzes = new List<string>();
Enumerable.Range(1,100).ToList().ForEach(k =>
fizzBuzzes.Add(k % 15 == 0 ? "FizzBuzz" : k % 5 == 0 ? "Buzz"
: k % 3 == 0 ? "Fizz"
: k.ToString()));
fizzBuzzes.Take(20).Dump(); //show the first 20 elements
This generates the output shown in Figure 2-35.
Figure 2-35. The first 20 elements of the FizzBuzz series
How It Works
Solving the FizzBuzz problem requires nothing but a straightforward if-else structure described by the following pseudo code:
If the number is divisible by 15
Replace with FizzBuzz
Else if the number is divisible by 5
Replace with Buzz
Else if the number is divisible by 3
Replace with Fizz
Else // for everything else
Don t do anything. Just show that number.
Using the ternary operator (? : ), you can write this logic in a single line of code. The following line does just that:
k % 15 == 0 ? "FizzBuzz" : k % 5 == 0 ? "Buzz" : k % 3 == 0 ? "Fizz" : k.ToString()
However, because 15 is a multiple of both 3 and 5, you can optimize for that and eliminate the division by 15. The next example demonstrates that.
2-25. Miscellaneous Series: Solving the FizzBuzz Challenge by Using Set Theory
The previous solution used division by 15. However, because 15 is a multiple of 3 and 5, you can avoid computationally expensive divisions by 15 by relying on the fact that sets divisible by 15 are also divisible by 3 and 5. This boils down to the following solution using set theory properties. The code might look a bit clumsy, but it will offer better performance for longer sequences because it avoids the unnecessary division by 15.
Problem
Rewrite the FizzBuzz Challenge code to eliminate the division by 15.
Solution
Listing 2-27 shows the solution.
Listing 2-27. Solving the FizzBuzz Challenge using set theory
var range = Enumerable.Range(1,40);
var mod3 = range.Where(e => e % 3 == 0);
var mod5 = range.Where(e => e% 5 == 0);
var mod15 = mod3.Intersect(mod5);
//Find numbers that are divisible by 3 but not by 5 or 15
mod3 = mod3.Except(mod15);
//Find numbers that are divisible by 5 but not by 3 or 15
mod5 = mod5.Except(mod15);
//Find integers that are not divisible by either 3 or 5
var neither = range.Except(mod3.Concat(mod5).Concat(mod15));
//Project each of these numbers as per the rule of the challenge.
neither.Select (n => new KeyValuePair<int,string>(n, n.ToString()))
.Concat(mod3.Select (m => new KeyValuePair<int,string>(m, "fizz")))
.Concat(mod5.Select (m => new KeyValuePair<int,string>(m, "buzz")))
.Concat(mod15.Select (m => new KeyValuePair<int,string>
(m, "fizzbuzz")))
//Sort the projected values as per the integer keys
.OrderBy (n => n.Key)
//But show the values only.
.Select (n => n.Value)
.Take(20) //showing first 20 elements
//Dump the result
.Dump ("Fizz Buzz Challenge");
How It Works
Although this solution looks overwhelmingly large compared to the previous version, it is simple. If you denote all numbers divisible by 3 as a set, and all numbers divisible by 5 as another set, then the intersection of these two sets will be the set of numbers divisible by 15.
//Creates a set of multiples of the number 3
var mod3 = range.Where (e => e % 3 == 0);
var mod5 = range.Where(e => e% 5 == 0); //does so for the number 5.
Except() returns elements present in one set but not in the other. Because the numbers divisible by 15 will be present in both sets, you can remove those items. The following lines of code do that:
//Find numbers that are divisible by 3 but not by 5 or 15
mod3 = mod3.Except(mod15);
//Find numbers that are divisible by 5 but not by 3 or 15
mod5 = mod5.Except(mod15);
So at this point, mod3 contains only elements divisible by 3, while mod5 contains elements only divisible by 5, and mod15 contains elements divisible by 15. The rest of the numbers in the range are not divisible by any of these numbers (3, 5, or 15). These numbers are found and stored in the variable neither.
The following line of code projects the integers and their corresponding values as per FizzBuzz rule:
IEnumerable<KeyVlauePair<int,string>>
neither.Select (n => new KeyValuePair<int,string>(n, n.ToString()))
.Concat(mod3.Select (m => new KeyValuePair<int,string>(m, "fizz")))
.Concat(mod5.Select (m => new KeyValuePair<int,string>(m, "buzz")))
.Concat(mod15.Select (m => new KeyValuePair<int,string>
(m, "fizzbuzz")))
OrderBy (n => n.Key) sorts this projected range of keys in ascending order. Finally, the values for the FizzBuzz series are projected by Select (n => n.Value).
Summary
Congratulations on finishing a long chapter! The problems here were selected to represent real-world applications while keeping variety and simplicity in mind. The key takeaway from this chapter is that you can apply LINQ to solve problems in several domains. The code in this chapter illustrates several idiomatic usages of LINQ. By now you should have a solid grasp of how to apply such LINQ idioms to generate several sequences. The advantage is that using LINQ operators makes your query look clean and concise. In the next chapter, you will see how to apply LINQ to solve several types of text-processing tasks.