Canon camera off-by-one image storage

While pulling the images from an Exif formatted Canon camera flash memory card I noticed this off-by-one error in the way the images are stored.

This is an interesting bug. Think about the code behind this problem for a moment. If we were writing this from scratch, we might start like this:

[Test]
public void Should_increment_the_image_number()
{
    _imageNumber = 0;
    int next = GetNextImageNumber();
    next.ShouldBeEqualTo(1);
    _imageNumber.ShouldBeEqualTo(1);
}

[Test]
public void Should_reset_the_image_number_to_1_given_9999()
{
    _imageNumber = 9999;
    int next = GetNextImageNumber();
    next.ShouldBeEqualTo(1);
    _imageNumber.ShouldBeEqualTo(1);
}

with implementation

private volatile int _imageNumber;

private int GetNextImageNumber()
{
    _imageNumber = _imageNumber + 1;

    if (_imageNumber > 9999)
    {
        _imageNumber = 1;
    }
    return _imageNumber;
}

Next we’ll want to handle incrementing the directory number.

[Test]
public void Should_increment_the_directory_number()
{
    _directoryNumber = 100;
    IncrementDirectoryNumber();
    _directoryNumber.ShouldBeEqualTo(101);
}

[Test]
public void Should_reset_the_directory_number_to_100_given_999()
{
    _directoryNumber = 999;
    IncrementDirectoryNumber();
    _directoryNumber.ShouldBeEqualTo(100);
}

with implementation

private volatile int _directoryNumber;

private void IncrementDirectoryNumber()
{
    _directoryNumber = _directoryNumber + 1;
    if (_directoryNumber > 999)
    {
        _directoryNumber = 100;
    }
}

Now when the image number crosses to the next 100 we have to increment the directory number.

[Test]
public void Should_increment_the_directory_number_when_the_image_number_goes_to_the_next_hundred()
{
    _imageNumber = 99;
    _directoryNumber = 100;
    int next = GetNextImageNumber();
    next.ShouldBeEqualTo(100);
    _imageNumber.ShouldBeEqualTo(100);
    _directoryNumber.ShouldBeEqualTo(101);
}

private int GetNextImageNumber()
{
    if (_imageNumber % 100 == 99)
    {
        IncrementDirectoryNumber();
    }
    _imageNumber = _imageNumber + 1;

    if (_imageNumber > 9999)
    {
        _imageNumber = 1;
    }
    return _imageNumber;
}

And lastly we need to build the file path.

[Test]
public void Should_get_path__100CANON_IMG_0002__starting_with_directory_number_100_and_image_number_1()
{
    _directoryNumber = 100;
    _imageNumber = 1;
    var path = GetNextImagePath();
    path.ShouldBeEqualTo(@"100CANON\IMG_0002");
    _directoryNumber.ShouldBeEqualTo(100);
    _imageNumber.ShouldBeEqualTo(2);
}

public string GetNextImagePath()
{
    return String.Format(
        @"{0:000}CANON\IMG_{1:0000}",
        _directoryNumber,
        GetNextImageNumber());
}

All tests pass so we’re done right? Nope. The following test fails (as expected) given the values from my image above.

[Test]
public void Should_get_path__320CANON_IMG_2000__starting_with_directory_number_319_and_image_number_1999()
{
    _directoryNumber = 319;
    _imageNumber = 1999;
    var path = GetNextImagePath();
    path.ShouldBeEqualTo(@"320CANON\IMG_2000");
    _directoryNumber.ShouldBeEqualTo(320);
    _imageNumber.ShouldBeEqualTo(2000);
}

Did you cringe/notice when we wrote the code that introduced the bug? If not, you might find the answers to this stack exchange question enlightening.

There are two routes to fixing this problem, the easy way and the correct way. The easy way is:

public string GetNextImagePath()
{
    var imageNumber = GetNextImageNumber();
    return String.Format(
        @"{0:000}CANON\IMG_{1:0000}",
        _directoryNumber,
        imageNumber);
}

The correct way is to remove the side effect so that the method becomes:

public string GetNextImagePath()
{
    IncrementImageNumber();
    return String.Format(
        @"{0:000}CANON\IMG_{1:0000}",
        _directoryNumber,
        _imageNumber);
}

… a coding problem you might use as a refactoring TDD Kata.

Read Full Post »

String Self-Referencing Index Kata

The self-referencing string indexer examines an input string and builds an array of index values for that input. The index is built according to rules as outlined below.

Create a String indexer with method int[] Index(string input)

1. return an empty array if the input is null
2. return an empty array if the input is empty
3. the index array should have the same number of elements as the input
4. the index array values should default to 0
5. the first value of the index array should always be -1
6. the second value of the index array should always be 0
7. when an input character is one position to the right of a character that is the same as the input character at that character’s corresponding index value then its corresponding index value should be 1 + the index value of the character to its left

example:

input = "aab" 
output = [-1,0,1]
	output[0] is -1 // rule 5
	output[1] is 0  // rule 6
	output[2] is 1  // rule 7 because input[2-1] == input[output[2-1]] => input[1] == input[0] => 'a' == 'a'

example:

input = "abcabda" 
output = [-1,0,0,0,1,2,0]
	output[0] is -1 // rule 5
	output[1] is 0  // rule 6
	output[2] is 0  // rule 4
	output[3] is 0  // rule 4
	output[4] is 1  // rule 7 because input[4-1] == input[output[4-1]] => input[3] == input[0] => 'a' == 'a'
	output[5] is 2  // rule 7 because input[5-1] == input[output[5-1]] => input[4] == input[1] => 'b' == 'b'
	output[6] is 0  // rule 4

You have implemented the table-building portion of the Knuth-Morris-Pratt substring search algorithm.

Read Full Post »

TDD Code Kata – Adder

This is a repeatable Test Driven Development coding exercise that can be used to hone your test-first, red-green-refactor programming skills.

Adder

This adder allows you to add two integers together via a limited interface:

• void SetValue(int value) – sets the value of the default register
• int GetValue() – returns the value in the default register
• void MakeOtherRegisterDefault() – makes the alternate register the default; the previous default
  register becomes the alternate
• void Add() – sums the values of the default and alternate registers into the default register

Implement support for each method and remember to refactor between tests if necessary.

You may find the following use cases useful. Start each with a new Adder.

• single instruction
  • GetValue() – should return 0
• two instructions
  • Add() then GetValue() – should return 0
  • MakeOtherRegisterDefault() then GetValue() – should return 0
  • SetValue(10) then GetValue() – should return 10
• three instructions
  • SetValue(10) then Add() then GetValue() should return 10
  • SetValue(10) then MakeOtherRegisterDefault() then GetValue() – should return 0
  • SetValue(10) then SetValue(20) then GetValue() – should return 20
• four instructions
  • SetValue(10) then Add() then Add() then GetValue() should return 10
  • SetValue(10) then Add() then MakeOtherRegisterDefault() then GetValue() should return 0
  • SetValue(10) then MakeOtherRegisterDefault() then Add() then GetValue() should return 10
  • SetValue(10) then MakeOtherRegisterDefault() then MakeOtherRegisterDefault() then GetValue() should return 10
• five instructions
  • SetValue(10) then Add() then MakeOtherRegisterDefault() then Add() then GetValue() should return 10
  • SetValue(10) then MakeOtherRegisterDefault() then Add() then Add() then GetValue() should return 20
  • SetValue(10) then MakeOtherRegisterDefault() then SetValue(5) then Add() then GetValue() should return 15

The final use case is the standard one that will be used when adding two numbers together e.g. 10 + 5:

1. SetValue(10)
2. MakeOtherRegisterDefault()
3. SetValue(5)
4. Add()
5. GetValue()

Implementation variations to consider:

• make default and alternate separate fields
• use an int array to store default and alternate
• use a Stack to store default and alternate

Read Full Post »

TDD Code Kata – structural validation 2

This is a repeatable Test Driven Development coding exercise that can be used to hone your test-first, red-green-refactor programming skills.

Structural Validation 2

Start with an input validator and the method:

bool IsValid(string input)

This method will take a string input and return true if the string contains an input that is structurally correct according to the rules below, otherwise it will return false.

There are seven parts grouped by similar rules. You might choose to do one part a day, each day building on the previous day’s implementation.

Implement support for each of the rules in order and don’t read ahead. The rules are intended to build upon one another without contradiction i.e. once a rule makes the input invalid no other rule can make it valid again – the reverse is not true. Remember to refactor between tests if necessary.

1. The input is invalid if …
   1. it is empty
   2. it contains uppercase letters
   3. it contains numbers
   4. it contains symbols (other than period)
   5. it contains characters other than lower-case letters [a-z] and period (.)
   6. it contains more vowels (aeiou) than consonants e.g. amazonian
   7. the difference between the total number of consonants and the total number of vowels is greater than 1 e.g. anthology
   8. it contains only periods (.)
   9. it has more than 9 characters
   10. it has less than 9 characters

   my implementations: BDD style, NUnit only

2. Consonants. The input is invalid if …
   1. the first three characters are consonants and the next three characters are vowels e.g. btreeinfo
   2. the first three characters are consonants and the last three characters are vowels e.g. mysteriou
   3. the middle three characters are consonants and the last three characters are vowels e.g. hashtreei
   4. the first three characters are consonants and there are an equal number of consonants and vowels e.g. three.eat
   5. the middle three characters are consonants and there are an equal number of consonants and vowels e.g .airbrain
   6. the last three characters are consonants and there are an equal number of consonants and vowels e.g. air.eight
   7. the first, middle, and last characters (positions 1, 5, 9) are consonants and there are an equal number of consonants and vowels e.g. bee.steak
3. Vowels. The input is invalid if …
   1. the first three characters are vowels and the next three characters are consonants e.g. uuinstall
   2. the first three characters are vowels and the last three characters are consonants e.g. eairworth
   3. the middle three characters are vowels and the last three characters are consonants e.g. seriously
   4. the first three characters are vowels and there are more consonants than vowels e.g. eau.my.my
   5. the middle three characters are vowels and there are more consonants than vowels e.g. m.beaux.y
   6. the last three characters are vowels and there are more consonants than vowels e.g. my.my.eau
   7. the first, middle, and last characters are vowels and there are more consonants than vowels e.g. attribute
4. Apply the following transform to the input 741852963 . The digits represent the position (1-based) of the character in the original input. For example. If the input was yarmulkes the result would be kmyeuaslr . – The input is invalid if …
   1. the transformed input fails Part 2 rule 1 e.g. loaderror
   2. the transformed input fails Part 2 rule 2 e.g. moondance
   3. the transformed input fails Part 2 rule 3 e.g. existence
   4. the transformed input fails Part 2 rule 4 e.g. coal.oxes
   5. the transformed input fails Part 2 rule 5 e.g. after.ale
   6. the transformed input fails Part 2 rule 6 e.g. appear.in
   7. the transformed input fails Part 2 rule 7 e.g. air.lanes
5. This input is invalid if …
   1. the transformed input fails Part 3 rule 1 e.g. otherwise
   2. the transformed input fails Part 3 rule 2 e.g. afternoon
   3. the transformed input fails Part 3 rule 3 e.g. dangerous
   4. the transformed input fails Part 3 rule 4 e.g. in.ache.r
   5. the transformed input fails Part 3 rule 5 e.g. no.man.in
   6. the transformed input fails Part 3 rule 6 e.g. p.anti.no
   7. the transformed input fails Part 3 rule 7 e.g. guitarist
6. From here on any input that isn’t explicitly valid is invalid. The input is valid if it passes all rules in parts 1-5 and any one of the following:
   1. the first three characters are all consonants e.g. pyromania
   2. the middle three characters are all consonants e.g. anonymous
   3. the last three characters are all consonants e.g. aquaducts
   4. the first, middle, and last characters are all consonants e.g. bluejeans
   5. the first three characters are all vowels e.g. aaah.hhha
   6. the middle three characters are all vowels e.g. h.haaa..h
   7. the last three characters are all vowels e.g. ahh.hhaaa
   8. the first, middle, and last characters are all vowels e.g. ahh.ahhaa
7. apply Part 6 rules to the transformed input. The input is valid if it passes all rules in parts 1-5 and any one of the following:
   1. the transformed input passes Part 6 rule 1 e.g. gladiator
   2. the transformed input passes Part 6 rule 2 e.g. invisible
   3. the transformed input passes Part 6 rule 3 e.g. genealogy
   4. the transformed input passes Part 6 rule 4 e.g. bonedevil
   5. the transformed input passes Part 6 rule 5 e.g. aahah.ahh
   6. the transformed input passes Part 6 rule 6 e.g. hah.aahah
   7. the transformed input passes Part 6 rule 7 e.g. hhaa.ahha
   8. the transformed input passes Part 6 rule 8 e.g. haa.ahahh

Verify that the word celestial is a valid input.
Verify that the word tictactoe is an invalid input.

The code you have written should return true for legal, winning tic-tac-toe boards using the characters x, o, and period(.) for empty squares. The rules assume x moves first. The code should also return false given inputs that represent impossible, incomplete, and tie games.

Read Full Post »

TDD Code Kata – credit card number validator

This is a repeatable Test Driven Development coding exercise that can be used to hone your test-first, red-green-refactor programing skills.

Credit card number validator

Start with a simple card number validator. Add the method:

bool IsValid(string number)

This method will take a string input and return true if the string contains a structurally correct credit card number, otherwise it will return false.

Implement support for each of the statements below in order and don’t read ahead. Remember to refactor between tests if necessary.

1. An empty card number is invalid.
2. Card numbers contain only digits.
3. A card number cannot contain more than 16 digits.
4. A card number cannot contain less than 13 digits.

   The last digit of the card number is a check digit. The check digit is determined by using all the digits in the card number including the check digit to calculate a sum. This calculated value is the checksum.

5. When the card number is prefixed with zeros to be exactly 16 digits long the checksum includes the sum of all digits that have an odd index (0-based).

   For example, given the card number 0101010101010101 the checksum would be the sum of the 1’s (i.e. 1*8 = 8 ) because these digits are all at odd-numbered indexes into the card number.

6. When the card number is prefixed with zeros to be exactly 16 digits long the checksum also includes the sum of the substitution digits for all card number digits that have an even index (0-based). Use the card number digit as an index into “0246813579” to get the substitution digit to add to the checksum.

   For example, given the card number 4060101010101010 the checksum would include the sum of the substitution digits for 4 and 6 and the 1’s because these digits are all at even-numbered indexes into the card number. The substitution values added to the checksum in this case would be 8 (substitution digit at index 4 is 8 ) and 3 (substitution digit at index 6 is 3) and six 2’s (substitution digit at index 1 is 2) – i.e. 8 + 3 + 6*2 = 23.

7. The last digit of the checksum for a valid card number must be zero.

   For example, a checksum of 8 + 23 = 31 is invalid. This means the card number 4161111111111111 is structurally invalid. Card number 4566111111111111 has a checksum of 5+6+6*1+23 = 17+23 = 40. The last digit of this checksum is zero so this card number is structurally valid.

Lastly, verify that one of your own credit card numbers IsValid() according the code you have produced.

Read Full Post »