A man, a plan, a canal - Panama!

Whilst viewing Gary Daniels and Evan Goldring - Mock whiteboard problem I noticed a strange thing. In the video they show an mock interview question and try to answer it. As Evan says in the video and afterwards his solution was not the best one. After this everyone posted their attempt (15 pages of comments at the moment).

The strange thing? not one is right! why? Gary hints towards the end that the solution needs to handle white spaces correctly - in effect suggesting the the function should calculate palindromes on the basis of words rather than byte symmetry. I'm off course not suggesting that my solutions are correct either, as the definition of palindrome was not defined fully enough for anyone to be able to judge if an answer is correct.

My first attempt ignored this hint and just went for a straightforward symmetry test:

static bool isPalindromeFirst(string subject)
{
  bool result = false;

  if (subject != null)
  {
    int endOffset = subject.Length - 1;
    int midOffset = (int)Math.Ceiling(subject.Length / 2d);

    for (int startOffset = 0; startOffset < midOffset; startOffset++, endOffset--)
    {
      result = (subject[startOffset] == subject[endOffset]);
  
      if (!result)
        break;
    }
  }

  return result;
}

This solution appears generally correct for the byte symmetry approach, but I just don't feel happy with its lack of whitespace handling , so my second attempt is longer, but hopefully an evolutionary approach:

static bool isPalindrome(string subject)
{
  const int STEP_FORWARD = 1;
  const int STEP_BACKWARD = -STEP_FORWARD;
  const int BEFORE_START = -1;
  const int CHAR_AT_A_TIME = 1;
  const int COMPARE_EQUALS = 0;

  // assume its not a palindrome
  bool result = false;

  // how to compare
  CompareInfo ci = CultureInfo.CurrentCulture.CompareInfo;
  CompareOptions co =
    CompareOptions.IgnoreCase |
    CompareOptions.IgnoreKanaType |
    CompareOptions.IgnoreNonSpace |
    CompareOptions.IgnoreSymbols |
    CompareOptions.IgnoreWidth; |

  // null strings are not palindromes
  if (subject != null)
  {
    int AFTER_END = subject.Length;

    // single letter words are palindromes
    result = (AFTER_END == 1 && IsPalindromeChar(subject[0]));

    // start the comparison points at valid characters
    int startOffset = GetNextValidCharacter(subject, BEFORE_START, STEP_FORWARD, AFTER_END);
    int endOffset = GetNextValidCharacter(subject, AFTER_END, STEP_BACKWARD, BEFORE_START);

    while (startOffset < endOffset)
    {
      result = ci.Compare(subject, startOffset, CHAR_AT_A_TIME, subject, endOffset, CHAR_AT_A_TIME, co) == COMPARE_EQUALS;
  
      if (!result)
        break;

      // move the comparison points towards each other
      startOffset = GetNextValidCharacter(subject, startOffset, STEP_FORWARD, endOffset);
      endOffset = GetNextValidCharacter(subject, endOffset, STEP_BACKWARD, startOffset);
    }
  }

  return result;
}

static int GetNextValidCharacter(string subject, int offset, int step, int bound)
{
  if (offset != bound)
    offset += step;

  while (offset != bound && !IsPalindromeChar(subject[offset]))
    offset += step;

  return offset;
}

static bool IsPalindromeChar(char c)
{
  return char.IsLetter(c) || char.IsDigit(c);
}

ps I'm sure "a" is a palindrome, but I suspect "b" is not... however this would mean getting into recognising words and all that entails...

result of running:

'(null)' palindrome? False
'' palindrome? False
'.' palindrome? False
'..' palindrome? False
'.,.' palindrome? False
'a' palindrome? True
'ab' palindrome? False
'aa' palindrome? True
'aaa' palindrome? True
'abc' palindrome? False
'aba' palindrome? True
'abca' palindrome? False
'abba' palindrome? True
'aabccbaa' palindrome? True
'a man, a plan, a canal - panama' palindrome? True
'a man, a plan, a canal - panama!' palindrome? True
'A Man, a Plan, a Canal - Panama' palindrome? True
'A man, a plan, a canal - Panama!' palindrome? True
'A man, a plan, a canal - Panamá!' palindrome? True
'A ma;n, a plan, a canal - Panamá!' palindrome? True
'A ma;;n, a plan, a canal - Panamá!' palindrome? True
'A ma;n, a plan, a canal - Pa;namá!' palindrome? True
'A ma;;n, a plan, a canal - Pa;;namá!' palindrome? True
'A ma;;n, a plan, a canal - Pa;;;namá!' palindrome? True
'!A man, a plan, a canal - Panamá!' palindrome? True
'!A man, a plan, a canal - Panamá' palindrome? True
'!!A man, a plan, a canal - Panamá' palindrome? True
'A man, a plan, a canal - Panamá!!' palindrome? True
'1' palindrome? True
'12' palindrome? False
'11' palindrome? True
'122' palindrome? False
'121' palindrome? True
'1221' palindrome? True
'12.21' palindrome? True
'..12.21' palindrome? True
Press any key to continue...

Big-oh no notation

Whilst doing some revision for an exam I had to refresh myself on Big-Oh notation which showed me how much is taken for granted by documentation writers.

I refer of course to MSDN, which there appears to be little reference to this notation - the notable exception being "An Extensive Examination of Data Structures". Why does this matter? well if you are trying to work out what the order of magnitude of your code is then you need to know what the underlying framework is doing.

IMHO the collections classes and other such constructs should have their Big-Oh documented against them in the class library.

Poetry of motion: aquila

THE EAGLE

He clasps the crag with crooked hands;
Close to the sun in lonely lands,
Ringed with the azure world, he stands.

The wrinkled sea beneath him crawls;
He watches from his mountain walls,
And like a thunderbolt he falls.

By Alfred, Lord Tennyson

A regular timesaver

Got data that needs parsing with regular expressions? this is the tool to explore your expressions, and nicely generating your code as well!
RegexDesigner.NET

LINQ for XML

var xml = XElement.Load (@"test.XML");
XNamespace ns = "http://test.com/stuff"

var query =
    from node in xml.DescendantsAndSelf()
    group node by node.Name into groupedNode
    select new
    {
        Name = groupedNode.Key,
        Occurs = groupedNode.Count()
    };

query.Dump();


var countryCrossTabulation =
    from country in xml.DescendantsAndSelf(ns + "COUNTRY_NAME")
    group country by country.Value into countryCrosstab
    orderby countryCrosstab.Count() descending
    select new
    {
         Name = countryCrosstab.Key,
        Occurs = countryCrosstab.Count()
    };

countryCrossTabulation.Dump()

What goes plinq plinq fizz?

Got data that needs to be processed with LINQ, maybe a database or XML file?
LINQPad

couscous=devil's rice

I'm sorry it (couscous) is. A fake, wrong, bad version of rice.

Snippet Compiler

We all do it, create mini code projects just to test an idea or see how something works, pretty soon you end up with lots of little projects scattered over your hard disk and then you cna't find the example you want..

Have a look at Snippet Complier a tool I've rediscovered again - it does what it says on the tin and is great for building up a library of how to snippets...

It supports C#, VB.Net and javascript... Jeff has some other cool tools some with source code

Uxorious and Prolous

Chatting with the dead/alive cat's vet today we got onto the topic of what's the equivalent of Uxorious in terms of one's children.

There did not appear to be a quick answer to this, so as a holding position I'm going with a neologoliferated solution:

prolious: overly fond of offspring
though that actually might be a real word, so:

prolous: overly fond of child
though even that looks like a name

over to the cat's vet's friend...