Sunday, July 10, 2011

Incorrectly Delivered Mail and Comparing Strings: Part 2 of Peter and the Postal Service

Strings are sequences of characters. In order for two strings to be identical, every character must match between the two strings. Thus, you can check whether two strings are identical by iterating over each position in the string and comparing the corresponding characters.


"Excuse me!" Peter shouted while running down the road after the mailman. "This letter is not addressed to me."


"It isn't?" asked the mailman. He looked annoyed at the interruption to his routine.


"No. It is not." confirmed Peter. "My name is Peter Fencer. This letter is for Paul Fencer"


"Eh... Sorry. They are close." replied the mailman.


"Close does not count!" objected Peter.


"Huh?" asked the mailman.


"When comparing two strings, you need to compare every single character. The two strings match if and only if every character is the same!" argued Peter.


The mailman looked at Peter skeptically. "Are you sure that you want to argue this with me?" he asked.


"I most certainly do." continued Peter. "Here is the algorithm you should be using:

IF the two strings are different lengths THEN one of them has extra (unmatched) characters at the end, so reject the match.

Otherwise, FOR EACH position in the string: compare the corresponding characters in each string. IF they are not the same, reject.

And if you reach the end of the strings without rejecting, then you have a match."


"Alright." said the mailman. "I will use that test from now on. What string do you want me to use for comparison?"


Peter smiled. He pulled out his new return address stamp, stamped a blank piece of paper, and handed it to the mailman. "This." he declared.


The mailman nodded and left.


For two blissful weeks everything seemed to go perfectly. Peter never had to chase the mailman down the street to return a piece of incorrectly addressed mail. Peter felt pride that he helped the mailman improve his job performance.


Then, Peter noticed that he was missing a very important letter from the head of the library association. He had been assured that it would arrive last week. He approached the mailman the next day.


"Excuse me. I am waiting for a letter from the library association. Have you seen it?" he asked.


"No. I have not seen anything from the library association that matched your address." answered the mailman. "There was something for a Petee Fencer, but not for Peter Fencer."


"Wait!" cried Peter. "That is me! It is obviously a typo. The 'r' probably looked like an 'e' on some list."


"That cannot be right. It does not pass the algorithm you gave me." argued the mailman innocently.



"Yes, but…" started Peter. He wanted to scream.


The mailman stood there politely smiling.


"Okay. New plan." started Peter. "Let me tell you about hamming distance…"


---------------------------


Learn more about strings by reading about Peter and his new address stamp.


Other updates: Illustrations added to "Hunting Dragons With Binary Search" and "President of the Heap".

1 comment:

  1. Nice post, you have indeed cover the topic with great details. I have also blogged my experience as comparator and comparable in java with example . let me know how do you find it.

    ReplyDelete

Note: Only a member of this blog may post a comment.