Book Errata Page: The C# Helper Top 100

[The C# Helper Top 100]

This is the errata page for my book The C# Helper Top 100, The 100 most popular posts at csharphelper.com. If you find mistakes, please post them here in the Leave a Reply box at the bottom of the page.

If you have questions, thoughts, or suggestions, please post them on the book’s Questions and Discussion page.



[ OverviewTable of ContentsQuestions and DiscussionErrataSource Code ]

[ Buy at: CreateSpaceBarnes & NobleAmazon ]


Follow me on Twitter   RSS feed   Donate




Posted in .NET, algorithms, books, C#, C# programming | Tagged , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , | 2 Comments

Book Discussion Page: The C# Helper Top 100

[The C# Helper Top 100]

This is a discussion page for my book The C# Helper Top 100, The 100 most popular posts at csharphelper.com. Please post questions, thoughts, and suggestions here in the “Leave a Reply” box at the bottom of the page. I will moderate posts and reply as appropriate.



[ OverviewTable of ContentsQuestions and DiscussionErrataSource Code ]

[ Buy at: CreateSpaceBarnes & NobleAmazon ]


Follow me on Twitter   RSS feed   Donate




Posted in .NET, algorithms, books, C#, C# programming | Tagged , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , | 2 Comments

Table of Contents: The C# Helper Top 100

[The C# Helper Top 100]

This is a brief summary of the book’s table of contents.

Introduction
Part I. Serialization
1. Read a CSV File into an Array (1)
2. Use JSON to Serialize and Deserialize Objects (49)

Part II. Graphing
3. Draw a Graph in WPF (2)
4. Use Transformations to Draw a Graph in WPF (88)
5. Draw a Graph with Labels in WPF (85)
6. Zoom on a Graph in WPF (60)
7. Draw a Simple Histogram (37)

Part III. Text Processing
8. Convert Between Cases (3)
9. Convert Between Cases, Part 2 (66)
10. Format File Sizes (35)
11. Convert between Byte Arrays and Hex Strings (57)
12. Remove Nonprintable ASCII Characters (84)

Part IV. DataGridView
13. Bind a DataTable to a DataGridView Control (4)
14. Handle DataGridView Errors (52)
15. Add Rows to an Unbound DataGridView Control (9)
16. Set DataGridView Column Styles (95)

Part V. Microsoft Office Integration
17. Read Data from Excel (5)
18. Write Data into Excel (6)
19. Create a Word Document (10)
20. Add a Picture to a Word Document (25)

Part VI. WPF
21. Move and Resize Rectangles at Runtime in WPF (7)
22. Make a Blinking Label in WPF (21)
23. Understand Event Bubbling and Tunneling in WPF (75)

Part VII. Graphics
24. Draw in a Paint Event Handler (26)
25. Draw on a Bitmap (29)
26. Double Buffer (93)
27. Draw and Move Line Segments (8)
28. Animate Bouncing Balls (20)
29. Align Drawn Text (31)
30. Get Font Metrics (77)
31. Draw Rotated Text (79)
32. Render Polygons and Polylines in WPF (89)
33. Use Linear Gradient Brushes in Windows Forms (91)
34. Draw Justified Text (97)

Part VIII. Image Processing
35. Optimize JPEG Compression Levels (19)
36. Convert an Image to Grayscale (71)
37. Compare Images to Find Differences (36)
38. Select an Area in an Image (30)
39. Crop a Picture (42)
40. Select an Area in a Scaled Image (48)
41. Draw a Mandelbrot Fractal (24)
42. Set an Image’s Pixels in WPF (65)
43. Save a Bitmap into a File in WPF (90)

Part IX. Cryptography
44. Encrypt and Decrypt Files (11)
45. Use a Cryptographic Random Number Generator (38)

Part X. Dialogs
46. Let the User Select a Folder (12)
47. Display a Password Dialog (62)

Part XI. Internet
48. Get Stock Prices (13)
49. Generate and Display HTML (43)
50. Get File Size and Modification Time on an FTP Server (50)
51. Get Weather Forecasts (61)

Part XIII. Miscellaneous Controls
52. Make a Checked Group Box (14)
53. Find Controls by Name (68)
54. Select ListBox Values Containing Target Text (80)
55. Fit a RichTextBox to Its Contents (100)

Part XIV. Geometry
56. See Where Two Lines Intersect (15)
57. Find the Distance Between a Point and a Line Segment (44)
58. See Where Two Circles Intersect (18)
59. See Where a Line and Circle Intersect (58)
60. See If a Point Lies Inside a Polygon (22)
61. Calculate a Polygon’s Area (40)
62. Find a Polygon’s Centroid (55)
63. See if a Polygon is Convex (83)

Part XV. Algorithms
64. Generate Permutations of Objects (16)
65. Generate a Round Robin Tournament Schedule (70)
66. Draw a Family Tree (82)

Part XVI. Three-Dimensional Programs
67. Rotate a Three-Dimensional Cube With WPF (27)
68. Apply Textures to a Three-Dimensional Cube (78)
69. Draw a Smooth Surface (47)
70. Draw a Data Surface That Has an Altitude Map (94)
71. Draw Three-Dimensional Line Segments (81)
72. Draw a Wireframe (17)

Part XVII. ListView and TreeView
73. Display Icons in a ListView Control (72)
74. Use ListView Groups (23)
75. Sort a ListView Control on the Column Clicked (39)
76. Print ListView Contents (54)
77. Load a TreeView with XML Data (28)

Part XVIII. System Interactions
78. Get Detailed Printer Information (32)
79. Combine and Resolve Relative Paths (51)
80. Play System Sounds (73)
81. Get a Disk Drive’s Serial Number (99)

Part XIX. Mathematics
82. Solve a System of Equations (64)
83. Find a Linear Least Squares Fit (67)
84. Find a Polynomial Least Squares Fit (33)
85. Sieve of Eratosthenes (63)
86. Factor Numbers (74)
87. Convert Between Bases (92)

Part XX. Multimedia
88. Display and Load Animated GIFs (34)
89. Control a Video with the WPF MediaElement Control (86)

Part XXI. Interoperability
90. Make a C# DLL for Use with Excel (41)
91. Drag and Drop Images (46)
92. Copy, Cut, and Paste Parts of Images to the Clipboard (53)
93. Copy and Paste Data in Multiple Formats (59)

Part XXII. Printing
94. Print Data in Rows and Columns (87)
95. Print Multiple Pages (96)

Part XXIII. Miscellany
96. Use a TypeConverter with a PropertyGrid (45)
97. Display Unicode Symbols (56)
98. Make a Countdown Timer (69)
99. Use a BackgroundWorker (76)
100. Measure Elapsed Time (98)


[ OverviewTable of ContentsQuestions and DiscussionErrataSource Code ]

[ Buy at: CreateSpaceBarnes & NobleAmazon ]


Follow me on Twitter   RSS feed   Donate




Posted in .NET, algorithms, books, C#, C# programming | Tagged , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , | 2 Comments

New Book: The C# Helper Top 100

[The C# Helper Top 100]

I’m happy to announce my latest book, The C# Helper Top 100, The 100 most popular posts at csharphelper.com. It describes the 100 most popular posts on the C# Helper web site.

This is my 32nd book and my second first self-published book.

The C# Helper web site (csharphelper.com) receives thousands of visitors every day. This practical guide describes the 100 most commonly visited posts in the C# Helper library of tips, tricks, and example programs for C# developers.

Some of the examples make it easier to handle common tasks that developers perform every day. Other examples deal with more problematic subjects that developers encounter only occasionally. Because those challenges are less common, developers often don’t have ready solutions. To make matters worse, coverage in general C# books is sparse or non-existent.

The C# Helper Top 100 provides complete examples demonstrating 100 useful tips and techniques. Each example includes a simple, easy-to-understand explanation together with a working example program that you can download from the book’s web site.

100 example programs demonstrating useful and interesting techniques in such topics as:

  • 3-D Programs
  • Cryptography
  • Serialization
  • Algorithms
  • Graphics
  • Image Processing
  • Printing
  • Mathematics
  • Graphing
  • Geometry
  • DataGridView, ListView, TreeView
  • Microsoft Office Integration
  • Much, much more!


    Follow me on Twitter   RSS feed   Donate




    Posted in .NET, algorithms, books, C#, C# programming | Tagged , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , | Leave a comment

    Change image resolution in C#

    [resolution]

    This example shows how to change an image’s resolution. It’s another example I created to help while writing books. Computers usually work with images that have a resolution of 96 pixels per inch (PPI). Printers and publishers often require images with higher resolution such as 300 dots per inch (DPI). This example shows how to convert an image from one resolution to another. While I was at it, I also decided to make the program change the image’s size if you want to do so.

    When you invoke the File menu’s Open command, the following code executes.

    private void mnuFileOpen_Click(object sender, EventArgs e)
    {
        if (ofdOriginal.ShowDialog() == DialogResult.OK)
        {
            OriginalBitmap = new Bitmap(ofdOriginal.FileName);
            pictureBox1.Image = OriginalBitmap;
            using (Graphics gr = Graphics.FromImage(OriginalBitmap))
            {
                txtDpiX.Text = gr.DpiX.ToString();
                txtDpiY.Text = gr.DpiY.ToString();
            }
            txtWidth.Text = OriginalBitmap.Width.ToString();
            txtHeight.Text = OriginalBitmap.Height.ToString();
            mnuFileSaveAs.Enabled = true;
        }
    }

    This code displays an Open File Dialog to let you select an image file. If you pick a file and click Open, the program loads the file into a bitmap. It creates a Graphics object associated with the bitmap and uses its DpiX and DpiY properties to display the original image’s resolution. It also displays the bitmap’s Width and Height.

    To change the image’s resolution or dimensions, simply type into the textboxes. Then when you invoke the File menu’s Save As command, the following code executes.

    private void mnuFileSaveAs_Click(object sender, EventArgs e)
    {
        if (sfdNew.ShowDialog() == DialogResult.OK)
        {
            int old_wid = OriginalBitmap.Width;
            int old_hgt = OriginalBitmap.Height;
            int new_wid = int.Parse(txtWidth.Text);
            int new_hgt = int.Parse(txtHeight.Text);
    
            using (Bitmap bm = new Bitmap(new_wid, new_hgt))
            {
                Point[] points =
                {
                    new Point(0, 0),
                    new Point(new_wid, 0),
                    new Point(0, new_hgt),
                };
                using (Graphics gr = Graphics.FromImage(bm))
                {
                    gr.DrawImage(OriginalBitmap, points);
                }
                float dpix = float.Parse(txtDpiX.Text);
                float dpiy = float.Parse(txtDpiY.Text);
                bm.SetResolution(dpix, dpiy);
                SaveImage(bm, sfdNew.FileName);
                SystemSounds.Beep.Play();
            }
        }
    }

    This code displays a Save File Dialog. If you select a file and click Save, the code reads the new values in the textboxes. It then creates a bitmap that has the new dimensions. It creates an associated Graphics object and uses its SetResolution method to set the new bitmap’s resolution. Finally the method saves the new bitmap.

    For information on the SaveImage method that saves the file, see the post Save images with an appropriate format depending on the file name’s extension in C#.


    Download Example   Follow me on Twitter   RSS feed   Donate




    Posted in image processing | Tagged , , , , , , , , , , , , , | Leave a comment

    Examine the unique words in a Microsoft Word file in C#

    [unique words]

    This example is a modification of the earlier post List the unique words in a Microsoft Word file in C#. That program reads the words in a Microsoft word file, sorts them, and then displays the unique words in a list box.

    I sometimes use that program to look for spelling errors in the books that I write. It’s sometimes hard to notice that Word has flagged a particular word as misspelled. I can use the previous example to make a list of all of the words and then look for any that are misspelled.

    I’m working on a new book now (I’ll post details in the next few weeks) and I decided to modify that example to make it more useful. This version adds two new features.

    First, it writes the unique words into a file. I can then copy and paste its contents into a new Microsoft Word document and let Word check the individual words for spelling errors.

    Second, this version splits words that are in Pascal case or camel case. For example, a piece of code might contain the word “PreviwMouseDown.” This kind of typo is particularly difficult to detect because Microsoft Word flags all Pascal and camel case words as spelling errors so it becomes too easy to ignore the warnings. The program splits this word into “Previw Mouse Down.” Now when Word flags the first part “Previw” as an error, it’s much easier to see that this really is misspelled.

    The following code shows how the program processes the indicated file’s words.

    // List the words in the file.
    private void btnListWords_Click(object sender, EventArgs e)
    {
        Cursor = Cursors.WaitCursor;
    
        // Get the file's text.
        FileInfo file_info = new FileInfo(txtFile.Text);
        string extension = file_info.Extension.ToLower();
        string txt;
        if ((extension == ".doc") ||
            (extension == ".docx"))
        {
            txt = GrabWordFileWords(txtFile.Text);
        }
        else
        {
            txt = File.ReadAllText(txtFile.Text);
        }
    
        // Use regular expressions to replace characters
        // that are not letters or numbers with spaces.
        Regex reg_exp = new Regex("[^a-zA-Z0-9]");
        txt = reg_exp.Replace(txt, " ");
    
        // Split the text into words.
        string[] words = txt.Split(
            new char[] { ' ' },
            StringSplitOptions.RemoveEmptyEntries);
    
        // Use LINQ to get the unique words.
        var word_query =
            (from string word in words
             orderby word
             select ToProperCase(word)).Distinct();
    
        // Display the result.
        string[] result = word_query.ToArray();
        File.WriteAllText("words.txt",
            string.Join(Environment.NewLine, result));
        lstWords.DataSource = result;
        lblSummary.Text = result.Length + " words";
        Cursor = Cursors.Default;
    }

    This code uses the GrabWordFileWords method described in the earlier post to get the words contained in the file. (See that post for details.)

    Next the code uses a regular expression to convert special characters such as _ and & into spaces. It then uses the string class’s Split method to divide the text into words separated by spaces.

    The program then uses a LINQ query to call the ToProperCase method described shortly for each of the words. It selects the result of that method and orders the results by the words. (It probably should order them by ToProperCase(word), but it probably doesn’t make much difference to the ordering.)

    The program finishes by displaying the results in a list box and writing the words into a file.

    The following code shows the ToProperCase method.

    private string ToProperCase(string word)
    {
        string result = word[0].ToString();
        for (int i = 1; i < word.Length; i++)
        {
            char ch = word[i];
            if (char.IsUpper(ch)) result += " ";
    
            result += ch.ToString();
        }
        return result;
    }

    This method creates a result string and adds the input word’s first character to it. The code then loops through the word’s remaining characters. When it sees a capital letter, it adds a space to the result before that letter. The code then adds the letter to the result.

    After it finishes processing the word’s letters, the method returns the finished result.

    (Out of the 6,600+ words discovered by the program, this program helped me identify a dozen or so typos that might otherwise have been missed.)


    Download Example   Follow me on Twitter   RSS feed   Donate




    Posted in files, Office, strings, Word | Tagged , , , , , , , , , , , , , | Leave a comment

    Find random prime numbers in C#

    [prime]

    The example Probabilistically determine whether a number is prime in C# explains an algorithm for determining whether a number is prime with any desired level of certainty. After you add that method to your algorithmic toolkit, finding large prime numbers is easy. Simply pick a large random number and see if it’s prime. Then repeat until you find a prime.

    The following code shows how this example finds prime numbers. (I’ve modified it slightly to remove progress reporting statements.)

    // Probabilistically find a prime number within the range [min, max].
    private int FindPrime(int min, int max, int num_tests)
    {
        // Try random numbers until we find a prime.
        for ( ; ; )
        {
            // Pick a random odd p.
            int p = Rand.Next(min, max + 1);
            if (p % 2 == 0) continue;
    
            // See if it's prime.
            if (IsProbablyPrime(p, num_tests)) return p;
        }
    }

    This method enters an infinite loop. Each time through the loop, it picks a random number in the desired range. If the number is even, the loop continues with no further testing. (The primality test will determine that even numbers are not prime, but it can be slow so there’s no need to be blindly stupid here. Note that the program is looking for large primes so it doesn’t need to consider the value 2.)

    If the number is not even, the program calls the IsProbablyPrime method described in the previous post. If IsProbablyPrime returns true, then this method returns the candidate number, which is probably prime.

    Now when you need to find large primes p and q for use with the RSA algorithm, you can simply call this method twice.

    There’s one other important issue to think about here: how long will it take this method to find large primes? After all, this wouldn’t be a very useful algorithm if it took a million years to find a prime. Fortunately the “prime number theorem” states that primes are everywhere dense. That means in every part of the number line there are a lot of primes, so it won’t take you too long to pick one randomly. In one set of 10 trials, the program picked as few as 1 and as many as 23 random numbers to find a prime, but on average it needed only 10.9 random numbers to find a prime.

    When the program runs, it can usually discard several non-primes very quickly. It only needs to try a couple of random tests in the IsProbablyPrime method to decide that a number is composite. When it picks a number that actually is prime, the program takes longer because it must perform all of the tests you requested to achieve the desired level of certainty.

    My book Essential Algorithms: A Practical Approach to Computer Algorithms contains more information about primality testing, prime number finding, and RSA. To see a description and table of contents, go here.


    Download Example   Follow me on Twitter   RSS feed   Donate




    Posted in algorithms, mathematics | Tagged , , , , , , , , , , , , , | Leave a comment

    Determine whether a number is prime in C#

    [prime]

    This is a cool little algorithm that uses some clever mathematics. This algorithm and several related algorithms are described in my book Essential Algorithms: A Practical Approach to Computer Algorithms. I think it’s a really good book (and it’s gotten very good reviews) so if you’re interested in this sort of thing (or other algorithms), check it out!

    The example also demonstrates a crucial technique in C# programming when you’re performing integer arithmetic.

    Before I describe the program, you should know a bit about why it’s important to decide whether a number is prime.

    Some modern cryptographic algorithms (in particular RSA) rely on large prime numbers. Without going into all of the details, in RSA you pick two large prime numbers p and q and publish their product n = p × q for everyone to see.

    Now suppose your friend Alice wants to meet you for lunch at her favorite restaurant but doesn’t want to invite Bill, who’s a really annoying conversationalist, always orders something really expensive, and then demands to split the bill equally. Alice uses the public value n to encrypt the invitation and sends it to you.

    Unfortunately Bill works in your company’s IT department and he intercepts the message. If he can figure out what p and q are, he can decipher the invitation and show up unexpectedly. Basically the security of RSA depends on the fact that it’s hard to factor products of large primes p and q.

    If p and q are small, say only a few billion, Bill can easily write a program to try all possible prime factors up to the square root of n and eventually figure out what p and q are. To prevent that, you need to use really big prime numbers. Instead of using 32-bit ints or 64-bit longs, you might use 100-bit integers. The product n will have 200 bits and its square root will have 100 bits. (It will be around 1.3×1030.) Even if Bill has a computer that can test 1 trillion (109) factors per second, it would take him roughly 1.3×1030 / 109 = 1.3 × 1021 seconds or about 4 × 1013 years to find p and q. By then you and Alice will be safely done with lunch.

    Unfortunately if it takes Bill a long time to factor n, then it will also take you a long time to use factoring to determine whether p and q are prime. Fortunately there are tests that you can use to determine whether a number is prime without actually factoring it. That’s where this example begins.

    “Fermat’s little theorem” says that, if P is prime and 1 ≤ n < P, then nP-1 = 1 mod P. In other words, if you raise n to the P-1 power and take the result modulo P, the result is 1.

    For example, suppose P = 7. Then:

    • 16 mod 7 = 1 mod 7 = 1
    • 26 mod 7 = 64 mod 7 = 1
    • 36 mod 7 = 729 mod 7 = 1
    • 46 mod 7 = 4,096 mod 7 = 1
    • 56 mod 7 = 15,625 mod 7 = 1
    • 66 mod 7 = 46,656 mod 7 = 1

    Now suppose you want to know if p is prime. Pick a random number n with 1 ≤ n < P and apply Fermat’s little theorem. If p really is prime, then the result will always be 1 no matter what n you pick. It can be shown (but not by me) that if p is composite (non-prime), then there is at least a 50% chance that the n you pick will make np-1 ≠ 1 mod p. An n that makes Fermat’s little theorem fail in this way is called a “Fermat witness” because it proves that p is not prime.

    Of course there’s also a chance that you’ll be unlucky and the random n you pick satisfies Fermat’s little theorem even though p is composite. Such a value is called a “Fermat liar” because implies that p is prime when it really isn’t.

    After you know these facts, the algorithm for primality testing is relatively simple. Pick a bunch of random values n and see if they satisfy Fermat’s little theorem. If any of them are Fermat witnesses, then you know that p is composite. (Although you still don’t know p’s factors.) If you pick K values for n and they all satisfy Fermat’s little theorem, then there is only a 1/2K chance that p is composite and every value n you tried was a Fermat liar.

    Now you can pick as many n as you like to get any desired degree of certainty. For example, if you use 10 values for n and they all claim p is prime, there is only a 1/210 ≈ 0.00098 chance that p is really composite. If those odds aren’t good enough, try 20 values for n. If they all claim p is prime, there’s only a 1/220 ≈ 0.00000095 chance that p is composite. If that’s still not good enough, try 100 values for n and there will be only a 1/2100 ≈ 7.9 × 10-31 chance that p is actually composite. (In contrast the odds of you being struck by lightning is a whopping 9 × 10-7 per year, roughly a million million million million times greater.)

    This is an example of a probabilistic algorithm. You can never be completely sure the result is correct, but you can use as many test values as you like to achieve whatever degree of certainty you want.

    The following IsProbablyPrime method is the key to this example. (I’ve removed some progress reporting code to keep things simple.)

    // Perform tests to see if a number is (probably) prime.
    private Random Rand = new Random();
    private bool IsProbablyPrime(int p, int num_tests)
    {
        checked
        {
            // Perform the tests.
            for (int i = 0; i < num_tests; i++)
            {
                // Pick a number n in the range (1, p).
                long n = Rand.Next(2, p);
    
                // Calculate n ^ (p - 1).
                long result = n;
                for (int power = 1; power < p - 1; power++)
                {
                    result = (result * n) % p;
                }
    
                // If the final result is not 1, p is not prime.
                if (result != 1) return false;
            }
        }
    
        // If we survived all the tests, p is probably prime.
        return true;
    }

    The code performs the desired number of tests. For each test, the code picks a random n and then raises it to the p-1 power modulus p. If the result is 1 not for any value of n, the code returns false to indicate that p is definitely not prime.

    If the method finishes all of the tests, it concludes that p is probably prime.

    After it decides whether the number is prime, the program factors the number to make sure it was correct. To see how that code works, see the example Find a number’s prime factors in C#.

    There are a couple of C# issues here. First, the method uses a checked block. If a C# program encounters an integer error while performing an arithmetic operation, it normally does not signal an error. Instead it gets a nonsensical result and continues running as if nothing has gone wrong. In this example, if result * n is too big, the program causes an integer overflow, the new result is some sort of garbage (probably a large negative number), and the test is invalid.

    The checked block makes the program throw an exception if it encounters an integer arithmetic error.

    This program uses long integers to perform its calculations and only handles values up to 100 million so it can use larger values without causing an integer overflow.

    Another issue to consider is that these values are pretty small by cryptographic standards, so the attacker Bill can easily factor them. (With a computer, not by hand.) In a real application you would need to use much larger numbers. The System.Numerics namespace defines a BigInteger structure that can do this in Framework version 4.0 and later. The version of Visual Studio I used for this example doesn’t support that version, so it uses the long data type. You can rewrite the application if you like. This example is really just to show how it all works.

    A final issue is that it can take a while to raise a test value n to the p-1 power if p is really large. Fortunately there’s a clever algorithm called “fast exponentiation” that lets you do this more quickly. See my book for a description of that algorithm.

    In my next post, I’ll explain how you can use the algorithm described here to find large prime numbers. It’s fairly simple, so you may want to try to figure it out yourself before you read that post.

    Again, my book contains more information about primality testing, prime number finding, and RSA. To see a description and table of contents, go here.


    Download Example   Follow me on Twitter   RSS feed   Donate




    Posted in algorithms, mathematics | Tagged , , , , , , , , , , , , , , , | 2 Comments

    Iterate over items in an array with unknown dimensions in C#


    [dimensions]

    This example shows how you can iterate over the items in an array that has an unknown number of dimensions. When it starts, the program executes the following code.

    private void Form1_Load(object sender, EventArgs e)
    {
        string[, ,] values =
        {
            {
                { "(0, 0, 0)", "(0, 0, 1)", "(0, 0, 2)", "(0, 0, 3)", },
                { "(0, 1, 0)", "(0, 1, 1)", "(0, 1, 2)", "(0, 1, 3)", },
            },
            {
                { "(1, 1, 0)", "(1, 1, 1)", "(1, 1, 2)", "(1, 0, 3)", },
                { "(1, 1, 0)", "(1, 1, 1)", "(1, 1, 2)", "(1, 1, 3)", },
            },
            {
                { "(2, 1, 0)", "(2, 1, 1)", "(2, 1, 2)", "(2, 0, 3)", },
                { "(2, 1, 0)", "(2, 1, 1)", "(2, 1, 2)", "(2, 1, 3)", },
            },
        };
        
        // Display the values.
        txtValues.Text = GetArrayValueString(values);
        txtValues.Select(0, 0);
    }

    This code creates a three-dimensional array of integers. It then calls the following GetArrayValueString method to get a string representation of the array’s values and displays the result.

    // Return a string showing the array's values.
    private string GetArrayValueString(Array array)
    {
        string result = "";
    
        // Get the array's rank (number of dimensions).
        int rank = array.GetType().GetArrayRank();
    
        // Get the upper bounds for the array's dimensions.
        int[] counts = new int[rank];
        for (int i = 0; i < rank; i++)
        {
            counts[i] = array.GetUpperBound(i) + 1;
        }
    
        // Make an array to show the current indices.
        int[] indices = new int[rank];
    
        // Recursively list the items at the first dimension.
        result = ListItemsForDimension(array, counts, indices, 0);
    
        // Replace the very last , with a ;.
        int last_comma_pos = result.LastIndexOf(",");
        result = result.Substring(0, last_comma_pos) + ";\r\n";
    
        return result;
    }

    This code gets the array’s type object and then uses that object’s GetArrayRank method to determine how many dimensions the array has. This example’s array has three dimensions, although the method works for arrays with any number of dimensions.

    Next the code makes a counts array to hold the number of items in each dimension. It loops over the dimensions, uses the GetUpperBound method to get each dimension’s count, and saves the count in the counts array.

    Because you don’t know the number of dimensions when you’re writing the code, you can’t use normal array indexing to plug numbers into the program to get values. For example, you can’t say array[1, 2, 3] because you don’t know the array has 3 dimensions.

    To get values from the array, you need to use the array’s GetValue method passing it an array of indices. To get the value at position [1, 2, 3], you would pass into the method an array that contains the indices 1, 2, and 3.

    To prepare to do this, the GetArrayValueString method creates an indices array. As the program recurses, it fills in entries in this array. When it is at the end of the series of recursive calls, this array holds an index for every dimension in the array, so the program can pass it to the GetValue method.

    Having created the indices array, the GetArrayValueString method calls ListItemsForDimension passing it the array of values, the counts array holding the count for each dimension, the currently empty indices array, and 0 to indicate that ListItemsForDimension should work with the array’s first dimension.

    The result returned by ListItemsForDimension ends with a comma and a new line. To make the result look like a valid C# array initializer, the code replaces the final comma with a semi-colon.

    The following code shows the recursive ListItemsForDimension method.

    // Recursively list the items for the indicated dimension.
    private string ListItemsForDimension(Array array,
        int[] counts, int[] indices, int dimension)
    {
        string indent = new string(' ', dimension * 4);
    
        // See if this is the innermost dimension.
        if (dimension == counts.Length - 1)
        {
            string result = indent + "{ ";
    
            // Loop over the indices for this dimension.
            for (int i = 0; i < counts[dimension]; i++)
            {
                // Set the index for this item.
                indices[dimension] = i;
    
                // Get the item's value.
                result += "\"" + array.GetValue(indices).ToString() + "\", ";
            }
    
            result += "},\r\n";
            return result;
        }
        else
        {
            string result = indent + "{\r\n";
            
            // Loop over the indices for this dimension.
            for (int i = 0; i < counts[dimension]; i++)
            {
                // Set the index for this item.
                indices[dimension] = i;
    
                // Recursively list the sub-items.
                result += ListItemsForDimension(array,
                    counts, indices, dimension + 1);
            }
    
            result += indent + "},\r\n";
            return result;
        }
    }

    The ListItemsForDimension method returns a string showing the items in the array where the indices before the indicated dimension are stored in the indices array. For example, suppose the array has 4 dimensions, dimension = 2 and indices = [2, 1, 3, 4]. Because dimension = 2, only the first two entries in the indices array matter. In that case ListItemsForDimension should return a representation of the values array[2, 1, x, y] where x and y vary over all of the possible values for their dimensions.

    To do this, ListItemsForDimension first creates a string that it can use to indent its results. It then checks whether dimension indicates the array’s final dimension.

    If this is the last dimension, the code loops over the allowed index values for the final dimension. For each index value, it sets the last entry in the indices array. At that point, every entry in indices is filled in, so those values represent a particular position in the array. The code passes the indices array to the array’s GetValue method to get the value at that position and adds it to the result string. After it has looped over all of the index values for this dimension, the code adds a closing bracket to the result string and returns it.

    If this is not the last dimension, the ListItemsForDimension method adds an opening bracket to the result string and starts a new line. It then loops over the index values allowed for this dimension. For each index, it saves the index in the next position in the indices array and then calls itself recursively to get a representation of the values where that dimension is set. It adds the returned result to its result string and continues for the other allowed index values. After it has added representations for of the allowed index values, the ListItemsForDimension method finishes its own representation by adding a closing bracket and returns the result.

    To make sure this works, I copied the result, pasted it into the example program’s code, and ran the program again. The output was the same as before so I know the program displays the array’s values properly.

    This example shows how you can loop over the items in an array with unknown dimensions. It is easier to use a foreach loop to iterate over the items. For example, the following code displays all of the values in the array in the Console window.

    foreach (string value in values) Console.WriteLine(value);

    Unfortunately the code inside the loop doesn’t know what dimensions correspond to each value. For example, it wouldn’t know each item’s row number.

    This example simply displays the array’s contents. In a real program you would need to do something application-specific with the values.


    Download Example   Follow me on Twitter   RSS feed   Donate




    Posted in algorithms, arrays, syntax | Tagged , , , , , , , , , , , , , | 2 Comments

    Solution to puzzle: Zero rows and columns in an array in C#

    This post gives four solutions to Puzzle: Zero rows and columns in an array in C#. If you want to try the puzzle for yourself, see that post before you read this one.

    This is a fairly long post, but it’s also fairly simple.

    The obvious thing to try is to simply loop over the entries in the array and, when you find an entry that is zero, zero out the row an column containing that entry. Unfortunately that destroys information that you will need later. For example, suppose entry [3, 5] is 0. Then you need to zero out row 3 and column 5. Later when you consider entry [4, 5], that entry is 0 but you can’t tell whether it is 0 because it was originally zero or because you set it to 0 when you visited entry [3, 5].

    The most obvious solution is to make a second array. That array can either indicate where the 0s are in the original array or where they belong in the result. The first solution available for download uses the following code to demonstrate the first approach approach.

    private void ZeroRowsAndColumns(int[,] values)
    {
        // Make an array to hold values
        // indicating where there are zeros.
        bool[,] is_zero = new bool[
            values.GetUpperBound(0) + 1,
            values.GetUpperBound(1) + 1];
    
        // Set is_zero for values that are 0.
        for (int row = 0; row <= values.GetUpperBound(0); row++)
        {
            for (int col = 0; col <= values.GetUpperBound(1); col++)
            {
                is_zero[row, col] = (values[row, col] == 0);
            }
        }
    
        // Zero out the appropriate rows and columns.
        for (int row = 0; row <= values.GetUpperBound(0); row++)
        {
            for (int col = 0; col <= values.GetUpperBound(1); col++)
            {
                // See if this entry in the original array is zero.
                if (is_zero[row, col])
                {
                    // Zero out this entry's row and column.
                    for (int r = 0; r <= values.GetUpperBound(0); r++)
                    {
                        values[r, col] = 0;
                    }
                    for (int c = 0; c <= values.GetUpperBound(1); c++)
                    {
                        values[row, c] = 0;
                    }
                }
            }
        }
    }

    The code makes an array of Booleans named is_zero that is big enough to hold an entry for each of the values in the original array. (Note that the code assumes that Boolean arrays are initialized to hold false in every entry. This is true in C#.)

    The program then loops through the original array and sets the corresponding Boolean value to true for the original entries that are 0. The code then loops over the Boolean array and, when it finds an entry that is true (indicating that the original array had a 0 in that position), the code zeros out the corresponding row and column.

    There is a slight improvement you can make to this algorithm. Suppose you are looping through the Boolean array and you find that is_zero[3, 5] is true. In that case you next zero out row 3 and column 5. As you do that, this version checks the is_zero entry for the items that it is zeroing. While zeroing out column 5, suppose you find that entry [1, 5] is true. In that case, the program already zeroed out column 5 when it considered is_zero[1, 5] so it doesn’t need to zero out that column again.

    The second solution uses the following code to avoid re-zeroing a row or column if it has already done so. That saves some time if there are lots of zeros in the same row or column.

    // Insert the algorithm here.
    private void ZeroRowsAndColumns(int[,] values)
    {
        // Make an array to hold values
        // indicating where there are zeros.
        bool[,] is_zero = new bool[
            values.GetUpperBound(0) + 1,
            values.GetUpperBound(1) + 1];
    
        // Set is_zero for values that are 0.
        for (int row = 0; row <= values.GetUpperBound(0); row++)
        {
            for (int col = 0; col <= values.GetUpperBound(1); col++)
            {
                is_zero[row, col] = (values[row, col] == 0);
            }
        }
    
        // Zero out the appropriate rows and columns.
        for (int row = 0; row <= values.GetUpperBound(0); row++)
        {
            for (int col = 0; col <= values.GetUpperBound(1); col++)
            {
                // See if this entry in the original array is zero.
                if (is_zero[row, col])
                {
                    // Zero out the column.
                    // If this is the first row or this column has
                    // not already been zeroed, zero it out.
                    if ((row == 0) || (!is_zero[0, col]))
                    {
                        for (int r = 0; r <= values.GetUpperBound(0); r++)
                        {
                            values[r, col] = 0;
                        }
                    }
                    else
                    {
                        Console.WriteLine("Skipping column " +
                            col.ToString() + ".");
                    }
    
                    // Zero out the row.
                    // If this is the first column or this row has
                    // not already been zeroed, zero it out.
                    if ((col == 0) || (!is_zero[row, 0]))
                    {
                        for (int c = 0; c <= values.GetUpperBound(1); c++)
                        {
                            values[row, c] = 0;
                        }
                    }
                    else
                    {
                        Console.WriteLine("Skipping row " +
                            row.ToString() + ".");
                    }
    
                    // Set is_zero to mark the row and column as zeroed.
                    is_zero[row, 0] = true;
                    is_zero[0, col] = true;
                }
            }
        }
        Console.WriteLine("Done");
    }

    This version uses the first row and column in is_zero to remember if the program has already zeroed out a row or column. After it zeros out row r and column c, it sets is_zero[r, 0] and is_zero[0, c] to true. Later, when the program must zero out column C, it checks is_zero[0, C]. If that entry is true, then this column has already been zeroed out so the program doesn’t need to do it again. Similarly when the program must zero out row R, it checks is_zero[R, 0] and, if that value is true, the code doesn’t need to zero out row R again.

    The trickiest part here is that the code must always zero out a column if the program is considering row 0 and vice versa because at that point is_zero holds information about whether the original value is 0 and not information about whether the row/column has been zeroed.

    This optimization saves some time if there are lots of 0s in the same row or column, but it still requires that you allocate and initialize the is_zero array. If the original array has M rows and N columns, then the new array has M * N entries. Unless the array is enormous, this extra space won’t be a big deal, but you can do better.

    The book Cracking the Coding Interview by Gayle Laakmann McDowell points out that you can use two one-dimensional arrays to indicate which rows and columns should be zeroed. You pass through the values array once to initialize the new arrays. Then you pass through the new arrays zeroing out the appropriate rows and columns.

    The third solution available for download uses the following code to demonstrate this approach.

    private void ZeroRowsAndColumns(int[,] values)
    {
        // Make arrays to hold values
        // indicating where there are zeros.
        bool[] row_is_zero = new bool[values.GetUpperBound(0) + 1];
        bool[] col_is_zero = new bool[values.GetUpperBound(1) + 1];
    
        // Set is_zero for values that are 0.
        for (int row = 0; row <= values.GetUpperBound(0); row++)
        {
            for (int col = 0; col <= values.GetUpperBound(1); col++)
            {
                if (values[row, col] == 0)
                {
                    row_is_zero[row] = true;
                    col_is_zero[col] = true;
                }
            }
        }
    
        // Zero out the appropriate rows.
        for (int row = 0; row <= values.GetUpperBound(0); row++)
        {
            if (row_is_zero[row])
            {
                for (int c = 0; c <= values.GetUpperBound(1); c++)
                {
                    values[row, c] = 0;
                }
            }
        }
    
        // Zero out the appropriate columns.
        for (int col = 0; col <= values.GetUpperBound(1); col++)
        {
            if (col_is_zero[col])
            {
                for (int r = 0; r <= values.GetUpperBound(0); r++)
                {
                    values[r, col] = 0;
                }
            }
        }
    }

    The code creates two arrays row_is_zero and col_is_zero to indicate whether a particular row or column should be zeroed. (Note that this code again assumes that Boolean arrays are initialized to hold false in every entry.) The code then loops through the values array, setting the row_is_zero and col_is_zero values to true for rows and columns that should be zeroed. Finally the code uses the two arrays to decide which rows and columns should be zeroed and zeros them.

    If the values array has M rows and N columns, then this solution requires only M + N additional space. Like the previous solution, it also avoids zeroing the same row or column twice.

    After a bit of thought, I realized you could do even better by using the first row and column of the values array to store the information in the row_is_zero and col_is_zero arrays. The only catch is what happens if there is a 0 in the first row or column. In that case, you would set values[0, 0] to 0. That would indicate that both the first row and column should be zero and that may not be the case.

    For example, consider the following values:

    5 7 9 0 8
    4 7 3 9 1
    2 3 2 5 1

    The entry values[0, 3] so the code should set values[0, 0] to 0 to indicate that the first row should be zeroed, but that would also indicate that the first column should be zeroed and that’s incorrect.

    To avoid losing information about the first row and column, the program must create and initialize two new Boolean variables. After that, it can use the first row and column to remember which columns and rows should be zeroed

    The following code demonstrates this approach.

    private void ZeroRowsAndColumns(int[,] values)
    {
        // See if the first row should be zero.
        bool row0_is_zero = false;
        for (int col = 0; col <= values.GetUpperBound(1); col++)
        {
            if (values[0, col] == 0)
            {
                row0_is_zero = true;
                break;
            }
        }
    
        // See if the first column should be zero.
        bool col0_is_zero = false;
        for (int row = 0; row <= values.GetUpperBound(0); row++)
        {
            if (values[row, 0] == 0)
            {
                col0_is_zero = true;
                break;
            }
        }
    
        // Copy zeros into the first row and column.
        for (int row = 1; row <= values.GetUpperBound(0); row++)
        {
            for (int col = 1; col <= values.GetUpperBound(1); col++)
            {
                if (values[row, col] == 0)
                {
                    values[row, 0] = 0;
                    values[0, col] = 0;
                }
            }
        }
    
        // Zero out the required rows.
        for (int row = 1; row <= values.GetUpperBound(0); row++)
        {
            if (values[row, 0] == 0)
            {
                // Zero out this row.
                for (int c = 1; c <= values.GetUpperBound(1); c++)
                {
                    values[row, c] = 0;
                }
            }
        }
    
        // Zero out the required columns.
        for (int col = 1; col <= values.GetUpperBound(1); col++)
        {
            if (values[0, col] == 0)
            {
                // Zero out this column.
                for (int r = 1; r <= values.GetUpperBound(0); r++)
                {
                    values[r, col] = 0;
                }
            }
        }
    
        // If the first row should be zero, zero it out.
        if (row0_is_zero)
        {
            for (int c = 0; c <= values.GetUpperBound(1); c++)
            {
                values[0, c] = 0;
            }
        }
    
        // If the first column should be zero, zero it out.
        if (col0_is_zero)
        {
            for (int r = 0; r <= values.GetUpperBound(0); r++)
            {
                values[r, 0] = 0;
            }
        }
    }

    This version also uses only 2 extra Boolean variables instead of M + N or M * N extra pieces of memory so it uses the least extra space.

    However, this code is longer than the previous solutions because it needs to handle the first row and column as special cases. The code is still fairly simple so it’s not too hard to read.


    Download Example   Follow me on Twitter   RSS feed   Donate




    Posted in arrays, games | Tagged , , , , , , , , , | 3 Comments