Coding Katas: Insertion Sort

Writing tests for sorting algorithms are interesting. The main issue is that the tests would be the same regardless of which algorithm you chose:

  1. Given [1], sort returns [1]
  2. Given [1,2], sort returns [1,2]
  3. Given [2,1], sort returns [1,2]
  4. Given [1,2,3], sort returns [1,2,3]
  5. Given [2,1,3], sort returns [1,2,3]

In Test Driven Development, when writing code for a test, you are supposed to write the least amount of code necessary to make the current test pass. So if you are going to write algorithms for sorts. All sorting would be the same process:

To resolve the first and second tests all you need to return is the array given.

To resolve the third test, you can check if the first element in the array is bigger than the second, if it is, reverse the array, and return that, otherwise, return the array.

To answer the fifth test, you write the whole damned sorting solution. Whether you’re solving insertion sort, binary sort or quick sort — it doesn’t matter.

Since I wanted to write tests for sorting algorithms I decided that the best way is to think about the solution and incorporate that into my tests.

Insertion sort does what you would typically do if you have a hand of cards. You go from the beginning, each consecutive card that is out of order, you take out of your hand and place in the right spot.


So I built my tests for insertion sort to solve finding the correct spot for a new value in an array first, then implementing the sort was trivial.

Writing this in JavaScript meant that the insertion did not require moving each element over one in the array as it would in a language like Java. Once you have the position, you can remove the element from the array and put it back right where it goes.

Here are the tests I built. You can use my tests for insertion sort, or peruse my solution for insertion sort

  1. Can create InsertionSort object
  2. When 1 is given to [], getPositionForNewVal returns 0
  3. When 3 is given to [2,7,4], getPositionForNewVal returns 1
  4. When 9 is given to [2,4,7], getPositionForNewVal returns 3
  5. Insert 2 at index 0 into [2,4,6,3,5], should return [2,2,4,6,3,5]
  6. Insert 2 at last index into [2,4,6,3,5], should return [2,4,6,3,5,2]
  7. Insert 2 at index 2 into [2,4,6,3,5], should return [2,4,2,6,3,5]
  8. Slice index 0 from [2,4,6,3,5], should return [4,6,3,5]
  9. Slice index 2 from [2,4,6,3,5], should return [2,4,3,5]
  10. Slice index 5 from [2,4,6,3,5], should return [2,4,6,3,5]
  11. When [3,2,5,4,7,4] is given, sort returns [2,3,4,4,5,7]
  12. When [8682, 2602, 5961, 4659, 432, 8230, 111, 3921, 2841, 5913, 4876, 800, 6748, 5720, 4660, 327, 2305, 3571, 9919, 8277, 6168, 2305, 3359, 9292, 7043] is given, sort returns [111, 327, 432, 800, 2305, 2305, 2602, 2841, 3359, 3571, 3921, 4659, 4660, 4876, 5720, 5913, 5961, 6168, 6748, 7043, 8230, 8277, 8682, 9292, 9919]

Code Katas: Linked Lists

I explored in a previous post the idea of a coding kata. I explained that I thought that data structures, design patterns, and fundamental algorithms are ideal for such practice.

I think a good way to practice them is to start with the tests, and practice the kata from there. In this light, last week I put forward the tests for the Stack kata.

This week it’s Linked Lists.


A linked list is a data structure is a linear collection of data elements, called nodes. In it’s most basic form each node contains two pieces of information:

  • The data itself
  • A pointer that points to the next node

I came up with 20 tests (22 assertions) to implement this:

  1. New linked list init
  2. New linked list, next is null
  3. New Linked list, getLength is 0
  4. Add value once to list, getLength is 1
  5. Add value once, searchValueAt(0) returns value
  6. Add value once, searchValueAt(1) returns null
  7. Add two values, getLength is 2
  8. Add two values, searchValueAt(1) returns second value
  9. Add two values, searchValueAt(0) returns first value
  10. Remove node on empty list, length is 0
  11. Add value, remove node, length is 0
  12. Add value, remove node, list is empty
  13. Add value, remove node, add value, first is second value
  14. Add two values, remove second, length is 1
  15. Add two values, remove at third position, length is 2
  16. Add two values, remove second, first is value and next is empty
  17. Add two values, remove first, length is 1
  18. Add two values, remove first, first is second value
  19. Add three values, remove second, length is 2
  20. Add three values, remove second, first is value and second is third value

Here’s my implementation, but really I’m more interested in yours. Post a link to your repo below!

Image credit

Code Katas: The Stack

I explored in my previous post the idea of a coding kata. I expressed that I did not think just any exercise was worthy of being called a kata, because not all exercises are worth of practicing more than a few times. But there are concepts in computer science that are worth repeating again and again, to become a better programmer.

What brought this first to my attention was Uncle Bob’s screencast on the Stack kata where he demonstrated Test Driven Development implementing the Stack data structure.

As a kata, it’s beautiful. It’s a fundamental concept that could be implemented in many different ways. Also, interestingly, it would be implemented differently in different languages. So there is a lot to explore here.

Before putting forward the tests Martin used, I’ll recap what a Stack is.

A stack works like a stack of plates.

  • The first items into the stack are the last items to be taken off.
  • If you have a limit to how many plates will fit on your shelf, you can’t fill it too high.
  • You can’t remove from a stack if it’s empty.

That’s basically it.

Here are the tests that Uncle Bob lays out in his screencast.

  1. Can create Stack object.
  2. Newly created stacks should be empty.
  3. After one push, stack size should be one.
  4. After one push and one pop, should be empty.
  5. When pushed passed limit, stack overflows.
  6. When popped passed limit, stack underflows.
  7. When two values are pushed then one is popped, size is one.
  8. When one is pushed one is popped.
  9. When one and two are pushed two and one are popped.
  10. When creating stack with negative size, should through IllegalCapacity.
  11. When creating stack with zero capacity, any push should overflow.
  12. When one is pushed, one is on top.
  13. When stack is empty, top throws empty.
  14. With zero capacity stack, top throws empty.
  15. Given stack with one two pushed, find one and two.
  16. Given a stack with no two, find two returns null.

In my implementation and the tests I used, I ignored everything relating to capacity (5,10,11,14) because I implemented my stack in JavaScript. I could implement overflows, but JavaScript does not require a capacity when instantiating an array.

Want to give it a shot yourself? Post your implementation in the comments.

Exploring Test Driven Code Katas

I’m fairly new to the term Code Kata; I haven’t read any books on the subject. Over the past few years I’ve seen them mentioned around the internet, but with the overuse of the martial arts terminology in coding — everyone’s a ninja — I chose to ignore it for the most part. When I did look into it, the ‘katas’ I saw seemed like a gimmick to sell mere coding exercises.

Kata is Japanese for ‘form.’ In martial arts, a kata is a collection of moves that are brought together for the purpose of raising and maintaining a student (or any practitioner) to a base level of competence. Sometimes a kata embodies an entire style of martial arts, so it’s far more than that simply a collection of moves, but I won’t get into that here.

Robert C. Martin (Uncle Bob) author of the seminal paper bringing together the SOLID principles, has a video series on his site — Clean Coders — aimed at educating developers towards writing better code.

In the “extras” for episode 4 Martin does the “Stack Kata” to demonstrate how Test Driven Development (TDD) can be implemented for most anything.

Watching the show feels like you’re watching Good Eats, but for coders. There are multiple personalities — all played by Martin — who argue with each other over the best way to accomplish something, there are backdrops from around the universe, his family take part. It’s endearing, and sometimes distracts from the content. Overall I would say that the content has helped me grow as a developer by leaps and bounds.

Having practiced martial arts, for years, the idea of the “Stack Kata” speaks to me. There are fundamental concepts, patterns, and principles that developers should go back to, that will improve the way they think about everything they do. With each iteration they understand the coding principles on a deeper level, which then resonates throughout the rest of their code.

The experience of performing a “basic” kata and then experiencing it on a completely different level of competence, is powerful. For that matter, when watching a master perform that same “basic” kata — you can see their mastery clearly.

According to Wikipedia the term ‘code kata’ was probably first coined by Dave Thomas, co-author of the book The Pragmatic Programmer. While I highly applaud the concept, I disagree with what he puts forward as what code katas should be.

In his intro to the concept, Thomas explains “A kata is an exercise in karate where you repeat a form many, many times, making little improvements in each.” But katas, really, are more fundamental than a mere exercise. A Kata is a ‘form’ or ‘pattern’ in Japanese — not an exercise. He states in that same intro that “Sometimes ‘kata’ isn’t quite the right word.” I think that might be because many of the ‘katas’ he suggests on that page are simply exercises, not foundational concepts.

I’m not opposed to exercises, but they don’t need to be practiced again and again.  It’s very possible that Thomas suggests katas that are far more fundamental elsewhere. I personally think data structures and design patterns are prime candidates to be excellent code katas. Maybe I’m just a purist.

Test Driven Code Katas

What are Test Driven Code Katas? Well, they’re code katas done TDD style. Given the tests, you perform the kata.

What makes Test Driven Code Katas powerful are that they lay out the path to take when practicing without giving away what how exactly the code should look.

Probably the most important part of developing tests first is writing the right tests. If you are given the tests, it detracts from the practice. However, at least for starting out, there is no better guide — even better than specs — then following a proper set of tests.

I’ve been exploring fundamental computer science terminology, concepts I missed as a self-taught developer. As I go through them, I’ll be posting my katas for all to enjoy and explore.

Join me

If you’d like to share your implementations along with me, I’d love to see them. Post a link to your github repo with your implementation below the kata. If you decided to write your own tests, I’d love to see other ideas on how to approach a problem.

Image credit