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!

Project Euler - Problem 49

Today we'll look at problem 49 in project euler:

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?

Simple, but interesting!

My strategy was to use my primes sieve to generate primes up to 10000, then look for series which were prime and permutations - brute force essentially.

The only piece of code I didn't have was a method to compare two numbers and evaluate if they were permutations of one another. So I came up with the following:

public static bool IsPermutation(int n1, int n2)

{

char[] ac1 = n1.ToString().ToCharArray();

char[] ac2 = n2.ToString().ToCharArray();

if (ac1.Length != ac2.Length) return false;

Array.Sort(ac1);

Array.Sort(ac2);

for (int i = 0; i < ac1.Length; i++)

if (ac1[i] != ac2[i]) return false;

return true;

}

Works well enough!

All that remains is some ugly nested loops and ifs:

var primes = CustomMath.Primes(10000);

for (int prime = 1489; prime < 10000; prime += 2)

{

if (primes[prime])

{

for (int nextPrime = prime + 2; nextPrime < 10000; nextPrime += 2)

{

int thirdPrime = 2 * nextPrime - prime;

if (thirdPrime.ToString().Length > 4) break;

if (primes[nextPrime] && primes[thirdPrime])

{

if (IsPermutation(prime, nextPrime) && IsPermutation(prime, thirdPrime))

{

var sb = new StringBuilder();

sb.Append(prime);

sb.Append(nextPrime);

sb.Append(thirdPrime);

return sb.ToString();

}

}

}

}

}

You'll notice I'm starting at 1489, the first odd digit above the given sequence. Yes, I did check from 1001 first, but it stopped after finding the sequence at 1487, so then I checked above that number. Runs in about 100ms.

For the curious, the next (and only other sequence) is:

2969

6299

9629

Project Euler - Problem 41

Project euler again! This time, a fun little one that looks for pandigital primes:

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?

My strategy here was to utilize my Primes function to generate a boolean array of primes, and then check possible numbers against it. I also needed to utilize a method that checked if a number was pandigital or not.

public static bool IsPandigital(Int64 num)

{

string strNum = num.ToString();

int size = strNum.Length;

if (strNum.Contains("0"))

return false;

char[] digits = new char[size];

for (int i = 1; i <= size; i++)

digits[i - 1] = char.Parse(i.ToString());

char[] chars = strNum.ToCharArray();

if (chars.Intersect(digits).Count() == size && chars.Distinct().Count() == size)

return true;

return false;

}

Pretty simple here. First does a quick check: if a number contains a 0, it's not pandigital. Then, based on the size of the number, figures out which digits it'll check for (ie a 4 digit number needs to have 1, 2, 3, and 4) and then checks that the number contains each of those digits, and each one only once.

Great! Now we're ready to go. The only remaining problem is that the largest pandigital number is 987,654,321 - almost 1 billion! That's a little bit too big for my boolean prime array to handle - it tops out around 300 million. Fortunately, we can eliminate 9 and 8 digit pandigital numbers as candidates for primality.

How do we do that? Well, one test for primality is to sum the digits of a number and find out if it's evenly divisible by 3. Since 9+8+7+6+5+4+3+2+1 = 45, which is divisible by 3, no 9 digit pandigital number is prime. Same for 8 digit pandigitals. Thus our ceiling is only 7,654,321 - just a little over 7 million!

Final code to get the answer:

public static ValueType Go()

{

// we can eliminate 9 and 8 digital pandigitals because their sum is divisble by three, and hence not prime.

var primes = CustomMath.Primes(7654321);

int nMax=0;

for (int i = 1; i < 7654321; i+= 2)

if (i < primes.Length)

if (primes[i] && CustomMath.IsPandigital(i))

nMax = i;

return nMax;

}

The answer is 7652413. This code runs a little bit more slowly than most - executing in 1422ms. I could probably optimize it futher, but it gets the job done well!

Project Euler - Problem 39

Today's project euler problem was quite interesting:

If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p <= 1000, is the number of solutions maximised

First off, for a right triangle with integer values, we know the following:

A = 2*x*n - x^2

B = 2*n^2 - 2*x*n

C = 2*n^2 - 2*x*n + x^2

Where x%2 = 1, and n>x

From this we can craft a simple formula for the perimeters of such triangles:

A+B+C = P = 4*n^2 - 2*x*n

What we need to do then, is for each potential value of x and n, figure out the perimeter and count. I create an integer array, where the index = P, and increment it everytime I get a P < 1000:

// calculate solutions

int[] solutions = new int[1001];

for (int x = 1; x < 1001; x += 2)

{

for (int n = x + 1; ; n++)

{

int p = 4 * n * n - 2 * x * n;

if (p > 1000) break;

for (int m = p; m < 1001; m += p)

{

if (m > 1000) break;

solutions[m]++;

}

}

}

Now it's simple: just find out which perimeter value occurred the most:

// find the maximum count

int ans = 0;

int maxCount = 0;

for (int i = 0; i < 1001; i++)

{

if (solutions[i] > maxCount)

{

maxCount = solutions[i];

ans = i;

}

}

And we're done! The answer turns out to be P = 840. The code executes in < 1ms! Awesomeness!

Project Euler - Problem 38

Lately I've been mildly obsessed with projecteuler.net. Fun math problems! And it's been a good exercise in both my mathematical skills as well as my programming skills. Today I'd like to present some code I used to solve problem #38:

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

Knee deep already in project euler by now, I've already had to develop code for primes. This following snippet populates a boolean array with true/false, if the index is prime or not. Makes for very fast and easy prime checking! It generates the prime list based on a sieve method.

public static bool[] Primes(Int64 num)

{

bool[] abPrimes = new bool[num];

for (int i = 0; i < num; i++)

abPrimes[i] = true;

for (int i = 2; i < num; i++)

{

if (abPrimes[i])

{

int x = i << 1;

while (x < num)

{

abPrimes[x] = false;

x += i;

}

}

}

abPrimes[0] = false;

abPrimes[1] = false;

return abPrimes;

}

Anyhow, that's all I needed to complete this problem. But I thought I'd have a little fun and so I wrote code to deliver numbers that would be logically truncatable as primes. That is to say, they could start with 2,3,5,7,9, end in only 3 or 7, and contain 1,3,7,or 9 for middle digits.

Wielding a little recursion and yield return powa:

public static IEnumerable GetTruncatablePrimes()

{

var sb = new StringBuilder("1");

while (true)

{

foreach (var item in SetDigit(sb, 0))

yield return item;

sb.Insert(0, "0");

}

}

private static IEnumerable SetDigit(StringBuilder sb, int index)

{

string position = "";

if (index == 0)

position = "first";

else if (index == sb.Length - 1)

position = "last";

foreach (Int64 digit in GetPrimeDigits(position))

{

sb[index] = char.Parse(digit.ToString());

if (index != sb.Length - 1)

foreach (var item in SetDigit(sb, index + 1))

yield return item;

else

yield return Int64.Parse(sb.ToString());

}

}

private static IEnumerable GetPrimeDigits(string position)

{

int[] digits;

switch (position)

{

case "first":

digits= new[] { 2, 3, 5, 7, 9 };

break;

case "last":

digits = new[] {3, 7 };

break;

default:

digits = new[] { 1, 3, 7, 9 };

break;

}

foreach (int d in digits)

yield return d;

}

Now that I had a list of potential digits, I just needed to see if they were prime, and if their truncated versions were prime:

//Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

public static Int64 Go()

{

bool[] abPrimes = CustomMath.Primes(1000000);

Int64 sum = 0;

int counter = 0;

foreach (var prime in GetTruncatablePrimes())

{

// exceptions - single digits don't count

if (prime.ToString().Length <2)

continue;

if (abPrimes[prime])

{

// check left truncation

Int64 left = prime;

while (left.ToString().Length > 1 && abPrimes[left])

left = TruncateLeft(left);

// check right truncation

Int64 right = prime;

while (right.ToString().Length > 1 && abPrimes[right])

right = TruncateRight(right);

// check if both left and right truncation was successful

if (left.ToString().Length == 1 && abPrimes[left] && right.ToString().Length == 1 && abPrimes[right])

{

sum += prime;

if (++counter == 11)

break;

}

}

}

return sum;

}

private static Int64 TruncateLeft(Int64 number)

{

return Int64.Parse(number.ToString().Remove(0, 1));

}

private static Int64 TruncateRight(Int64 number)

{

return Int64.Parse(number.ToString().Remove(number.ToString().Length-1, 1));

}

And that's it! The entire deal runs in about 50ms. Generally speaking, all project euler problems are designed to be computable in under 1 minute - but I'm always looking for the absolutely fastest possible methods. I initally had some code in there to continue checking primality if the potential primes were outside the bounds of the array, but that proved unnecessary.

The only 11 primes that fit the bill are:

23

37

53

73

313

317

373

797

3137

3797

739397

Why

Lately I've become compulsive about plowing through the problems located at projecteuler.net. But this blog isn't all about those problems. It's mostly going to be a place where I can post whatever is going on at any particular time. There will be code, recipes, thoughts and questions.

Mostly this blog is for my own personal enjoyment. But if you do get something out of it, that's great!