A place to avoid

Recently I completed my Masters in Business Administration for Sustainable Business from Bainbridge Graduate Institute. After graduation, a number of the graduates decided to go on a trip. We selected Scottish Lakes High Camp as our destination.

The owners of this place, Don and Chris, were a nightmare to deal with. Part of our issue was that we had two young children. They insisted on "lapping" them along in their suburbans up the road"), instead of properly securing them in car seats. They refused to allow us to take our own vehicle, wasting time and effort in a parking lot simply to transfer people and cargo from our fully packed 4x4 into "theirs" - something that they had no rational explanation for (or bothered to provide). They also pointedly ignored multiple communications ahead of time as we prepared for our arrival and were hoping to have a few key questions answered. All in all, it made for a highly stressful situation and trip.

As a long time local mountain guide and former ranger, this is a gorgeous place and it's in a beautiful setting. That assertion excludes the owners however, who also are contributing to the air & noise pollution in the area by operating snowmobiles right up to (and sometimes crossing over into) the Alpine Lakes Wilderness (were I used to patrol, in fact). That makes this a place I'm wholeheartedly not recommending to anyone - avoid it like the plague.

Easy pause for console

I needed an easy way to pause my long running console application, and resume it at will. It turns out that doing so is pretty trivial, but it was a fun exercise that I wanted to share.

class Program

    {

        public static int s_nCounter = 0;



        static void Main(string[] args)

        {

            while (true)

            {

                CheckForPause();

                DoMyWork();

            }

        }



        private static void CheckForPause()

        {

            if (Console.KeyAvailable)

            {

                ConsoleKeyInfo key = Console.ReadKey(true);

                Console.WriteLine();

                Console.WriteLine("Program execution paused. Press any key to continue");

                Console.WriteLine();

                WaitForResume();

            }

        }



        static void WaitForResume()

        {

            while (!Console.KeyAvailable)

            {

                Thread.Sleep(1000);

            }

            ConsoleKeyInfo key = Console.ReadKey(true);

        }

   



        static void DoMyWork()

        {

            Console.CursorLeft = 0;

            Console.Write(s_nCounter++);

            Thread.Sleep(1000);

        }

    }

This is the example console app that continually writes a incrementing counter to the screen. At any time you can press any key. This key is stored in the input stream. The next time CheckForPause() is called, it looks at that stream to see if there's data waiting to be read. If so, it first consumes that key (ConsoleKeyInfo key = Console.ReadKey(true)), prints a message telling you it's paused, and then goes into an infinite loop waiting for another key press to resume progress. Note that you could easily read the key variable to determine which key was pressed, and make some branching decision based on that as well.

Determining which ListViewItem was clicked on in a ListView when executing a ContextMenu MenuItem

So I had need of utilizing a context menu inside a WPF ListView. I wanted to be able to right click an item, bring up the menu, then make a selection from the menu, and execute the appropriate method, using information from the item that was clicked. Seems simple, no?

In fact, I was unable to find any examples that did exactly that. Well, not entirely true. There were several people who suggested using the mouse right click event to monitor and record which item was clicked, and then reading that record. Messy. Ugly. Very non-WPF like. So I poked around a little bit more.

In the end, I now have two solutions - one utilizing commands, and another utilizing the DataContext. Both are clean and simple, and both work great for me.

First, the command solution. This one is a little more involved, but is certainly a little more powerful too. Via the CanExecute method you could dynamically determine which menu options in the context menu were usable, based on what was clicked. I don't do that here yet, but I'm going to be utilzing that feature in the future, which is why I've actually implemented this method instead of the DataContext one.

So I decided to try and implement a command solution.  I'm pretty pleased with how it's working now.



First, created my command:

    public static class CustomCommands

    {

        public static RoutedCommand DisplayMetadata = new RoutedCommand();

    }

Next in my custom listview control, I added a new command binding to the constructor:

    public SortableListView()

    {

        CommandBindings.Add(new CommandBinding(CustomCommands.DisplayMetadata, DisplayMetadataExecuted, DisplayMetadataCanExecute));

    }

And also there, added the event handlers:

    public void DisplayMetadataExecuted(object sender, ExecutedRoutedEventArgs e)

    {

        var nbSelectedItem = (MyItem)e.Parameter;



        // do stuff with selected item

    }



    public void DisplayMetadataCanExecute(object sender, CanExecuteRoutedEventArgs e)

    {

        e.CanExecute = true;

        e.Handled = true;

    }



I was already using a style selector to dynamically assign styles to the listview items, so instead of doing this in the xaml, I have to set the binding in the codebehind.  You could do it in the xaml as well though:





    public override Style SelectStyle(object item, DependencyObject container)

    {

        ItemsControl ic = ItemsControl.ItemsControlFromItemContainer(container);

        MyItem selectedItem = (MyItem)item;

        Style s = new Style();



        var listMenuItems = new List<MenuItem>();

        var mi = new MenuItem();

        mi.Header= "Get Metadata";

        mi.Name= "cmMetadata";

        mi.Command = CustomCommands.DisplayMetadata;

        mi.CommandParameter = selectedItem;

        listMenuItems.Add(mi);



        ContextMenu cm = new ContextMenu();

        cm.ItemsSource = listMenuItems;



        // Global styles

        s.Setters.Add(new Setter(Control.ContextMenuProperty, cm));

           

        // other style selection code



        return s;

    }



I like the feel of this solution much better than attempting to set a field on mouse click and try to access what was clicked that way.

 

Pretty nice! The other solution, using the DataContext, is virtually identical - in fact it requires even less code! You don't need to generate the commands or modify the constructor of your control. All you need to do is set the DataContext for the MenuItem to your item, and you're set. For me, that means doing it in the style selector. But it's quite easily done in the XAML as well if you aren't using a dynamic selection method like I am.

public override Style SelectStyle(object item, DependencyObject container) { ItemsControl ic = ItemsControl.ItemsControlFromItemContainer(container); MyItem selectedItem = (MyItem)item; Style s = new Style(); var listMenuItems = new List(); var mi = new MenuItem(); mi.Header= "Get Metadata"; mi.Name= "cmMetadata"; mi.Click = cmMetadata_Click; mi.DataContext = selectedItem listMenuItems.Add(mi); ContextMenu cm = new ContextMenu(); cm.ItemsSource = listMenuItems; // Global styles s.Setters.Add(new Setter(Control.ContextMenuProperty, cm)); // other style selection code return s; }

private void cmMetadata_Click(object sender, RoutedEventArgs e) { var nbSelectedItem = (sender as MenuItem).DataContext as MyItem; // do stuff with selected item }

That's it! Notice the only difference is the lack of the command. And instead of setting the Command and CommandParameter properties for my menu item, I instead set the DataContext property and bind the click event.

I hope this code saves you the troubles I had figuring this out!

UPDATE: Yes I see that the code is extraordinarily malformatted. Blogspot is relly a poor place to post code samples, it appears.

Select Non-Distinct with Linq!

So earlier today I had a large collection and I wanted to select items from it which were essentially duplicates in some way. Getting distinct items from a collection in C# is easy:

var result = MyCollection.Distinct();

Getting the opposite, in sense, is a little trickier. At first I wrote the following:

var result = from Item a in MyCollection

where MyCollection.Count(b=> b.Id = a.Id) > 1

select a;

Which works! Unfortunately, it was way too slow. The code above will enumerate through the collection for every item in the collection, resulting in O(n^2) processing time. Since my collection had 13k items in it, that meant 169,000,000 enumerations. Yikes!

The solution I came up with was to utilize the grouping ability of linq. So I first grouped my collection by the Id, checked which groups have a count greater than 1 and select those, then utilize selectmany to flatten the enumerables into one!

private IEnumerable<Item> GetDuplicates()

{

return (from Item a in MyCollection

group a by a.Id into g

where g.Count() > 1

select g).SelectMany(g => g.AsEnumerable());

}

Great! However, this is still not optimal. The SelectMany unfortunately results in another layer of enumeration. Iterating through the groups manually, as in the following code, results in a roughly 4 fold performance improvement over the linq query above:

private IEnumerable<Item> GetDuplicates()

{

var results = from Item a in MyCollection

group a by a.Id into g

where g.Count() > 1

select g;

foreach (var group in results)

foreach (var item in group)

yield return item;

}

The result is we now only iterate through the collection once, and then the grouping once. The problem goes from being O(n^2) to < O(2n)!

Now you know how to get duplicate items from you collections. Enjoy!

Project Euler - Problem 51

This was a fun one.

By replacing the 1^st digit of *57, it turns out that six of the possible values: 157, 257, 457, 557, 757, and 857, are all prime.

By replacing the 3^rd and 4^th digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.

Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.

At first I came up with a method involving recursing iterator functions to generate masks and replace the digits, which worked great, except it was slow (80 seconds to find the answer!). It checked all possibilites, for all primes. While easily scalable (would work on numbers > 10 digits), it certainly wasn't practical.

So I then I boiled down the problem and simplified it a bit more. First off:

• The number of replacement digits MUST equal 3. Why? Because the sum of the digits of a prime must not be evenly divisible by 3. Replacing digits one or two at a time allows for a maximum family size of 7. Since the sum of the digits of a prime when replaced 3 at a time will always not be divisble by 3, this is the only way to avoid this issue.
• Second, generating digit masks and permutations is unnecessary. This is the biggest time saver. As long as the digit count is less than 10, we can simply go through a prime listing, and for each prime, replace digits that repeat (3 times per the above rule) with other digits and test for primality.

That said, here's the code. I create a boolean prime sieve, then iterate through primes. I perform a full set of digit replacements on each character that repeats 3 times, and count the result.

public static ValueType Go()

{

var primes = M.Primes(1000000);

for (int i = 10; i < 1000000; i++)

{

if (primes[i])

{

string strPrime = i.ToString();

foreach (char c in strPrime.ToCharArray().Distinct())

{

if (strPrime.Replace(c.ToString(), "").Length != strPrime.Length - 3)

continue;

var listPrimes = new List();

for (int j = 0; j < 10; j++)>

{

int newNum = int.Parse(strPrime.Replace(c.ToString(), j.ToString()));

if (primes[newNum] && newNum.ToString().Length == strPrime.Length)

listPrimes.Add(newNum);

}

if (listPrimes.Distinct().Count() == 8)

return listPrimes.Min();

}

}

}

return 0;

}

The result?

121313

which has family members:

222323,

323333,

424343,

525353,

626363,

727373,

828383,

929393

Voila! Code executes brilliantly, in 80ms.

Project Euler - Problem 50

Horray! Number 50! I've advanced to "level 2" on project euler!

Additionally, it appears I spoke to soon about the easy nature of recent problems! This one was very interesting and took me several attempts to get right. Here's the problem:

The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

My initial approach was to create my prime sieve up to 1000000, then iterate through each prime between 1000 and 1000000, and check for the ability to sum up to that prime number from lower primes. I assumed that in order to maximize the sequence length, the initial prime would be less than 100. Unfortunately this resulted in looping essentially 100,000,000 times, doing a simple summation calculation. The result was that I got the right answer, but it took over a minute to do so! Under project euler rules, the problems are designed to be solved in less than a minute. So back to the drawing board!

The better way was to create an array of prime summations, and then search through the various combinations in that array to find the maximum prime. Since by the time you hit prime # 548, your consecutive sum at that point is breaking 1 million, so that narrows the summation search down to measly ~300,000 iterations - much better!

So first generate my sieve:

var primes = CustomMath.Primes(1000000);

Then I went about creating the prime sum array, which was easy enough:

// create array of prime sums

var prime_sums = new List<int&gt();

prime_sums.Add(0);

prime_sums.Add(2);

int sum = 2;

for (int prime = 2; true; prime++)

{

if (primes[prime])

{

sum += prime;

prime_sums.Add(sum);

}

if (sum > 1000000) break;

}

Next, I searched through the resulting array to find the longest combo resulting in a prime:

int consecCount = 0;

int maxPrime = 0;

// find longest consecutive sequence that is prime

for (int i = 0; i < prime_sums.Count; i++)

{

for (int j = i + consecCount; j < prime_sums.Count; j++)

{

int diff = prime_sums[j] - prime_sums[i];

if (diff < 1000000 && primes[diff])

{

if (j - i > consecCount)

{

consecCount = j - i;

maxPrime = diff;

}

}

}

}

And that does it! The new code gives the correct answer - 997663 - in less than 40ms! What a relief! :)

Project Euler - Problem 48

After posting about Problem 49 and realizing it wasn't really all that interesting, I decided to backtrack a bit and post my solution to Problem 48 as well, which is a more interesting problem.

The series, 1¹ + 2² + 3³ + ... + 10¹⁰ = 10405071317.

Find the last ten digits of the series, 1¹ + 2² + 3³ + ... + 1000¹⁰⁰⁰.

Unfortunately C# can't handle large numbers like those required to perform a calculation such as 1000^1000. For earlier project euler problems I had built a few quick hack methods (BigMultiply and BigAdd) to calculate the results of operations on large numbers. But those are slow and we actually don't need them here. The key to doing this problem efficiently is to realize that since we only want the last 10 digits, those are the only digits we ever care about, throughout all operations.

Thusly....

public static ValueType Go()

{

Int64 seriesSum = 0;

for (Int64 i = 1; i < 1001; i++)

{

Int64 currentPower = i;

for (Int64 power = i; power > 1; power--)

{

currentPower = currentPower * i;

// only need last 10 digits

string pow = currentPower.ToString();

if (pow.Length > 10)

currentPower = Int64.Parse(pow.Substring(pow.Length - 10));

}

seriesSum += currentPower;

// only need last 10 digits

string sum = seriesSum.ToString();

if (sum.Length > 10)

seriesSum = Int64.Parse(sum.Substring(sum.Length - 10));

}

return seriesSum;

}

...and voila! Takes a mere 340ms to get the answer: 9110846700.

In general the problems lately have been quite trivial, so I haven't been posting solutions. Here's hoping something more intriguing shows up!