FizzBuzz and the Roman Numeral Kata are the Same Thing!

"The same, sir."

-- Shakespeare, Coriolanus

Act IV, Scene III, Line 7

As Homer Simpson pointed out, "Coke and Pepsi are the same thing!"


Similarly I plan to show that the FizzBuzz and Roman Numeral katas are the same thing! 

First let's look at the rules of FizzBuzz.

f(x : int) : string

  if 3 | x and 5 | x then "FizzBuzz"
  if 3 | x then "Fizz"
  if 5 | x then "Buzz"
  default string x

*note, 3 | x reads 3 divides x, in other words x / 3 does not have a remainder

 In general we see that we have two (or three) rules and a default value, we are translating from the domain into the codomain following a set of rules, in other words we have a function.

How about the Roman Numeral kata?

f(x : int) : string

  fold

    roman-numerals : (int, string)

    lambda((x : int, m : string),

           (k : int, v : string)) : (int, string)

      while k | x then (x / k, concat m v)

    (x, default string) : (int, string)

Again we see a list of rules for translation.

The only real difference to FizzBuzz is the fold across the rules, but we've hinted at this in the FizzBuzz description above.  We stated that FizzBuzz has two (or three) rules, we can rewrite it using a fold with just the two rules using the fold to cover the "and" case.

We see the FizzBuzz and Roman Numeral as having the same shape which we use in the generalization in the "2 version".  Thus using the same function with a set of rules, a defaulting function, and a seed we create both the FizzBuzz and Roman Numeral kata from the same general function!

MapFold OR Set Phasers to Fun

"Back to our brother of England."
-- Shakespeare, Henry V
Act II, Scene IV, Line 115.1

One of the things I love about functional programming is you can tell a lot about how a function works by just looking at its type signature.  In F# 4.0 there is a new function to work with collections, here is it type signature:

('State -> 'T -> 'U * 'State) -> 'State -> C<'T> -> C<'U> * 'State

What do you think it does?

That's right this is a MapFold.  Looking at its full definition we see the following:

let mapFold<'T,'State,'Result> 
  (f:'State -> 'T -> 'Result * 'State) acc list =

How does this work?

Looking at F#'s unit tests we see the following test name:

let ``mapFold works like map + fold`` () =

MapFold works like a map with a fold to maintain state.  I know what you are thinking maintaining state is bad, that's why functional programming is easier to reason about.  This is very true, but this is not a mutable state, this is an evolving state.

Let us look at an example, the Coin Changer kata:



The Coin Changer kata simulates one of those machines which give you back coins at a store.  It takes a list of coin values and the amount of change to be given.

The Coin Changer kata is interesting since it has two things going on at the same time: 1) state and 2) list processing.  In the Coin Changer kata you must maintain the amount of change you have left to give along with the amount of each coin to be given back.  An example would be 99 cents with an US register, you would get back 3 quarters, 2 dimes, 0 nickels, and 4 pennies.

How would this example of 99 cents with an US register work with MapFold?

changeFor [25; 10; 5; 1] 99

We'll use s to hold the state, r to hold the result, and x to hold the current coin value we are looking at .

Processing the first value: x = 25, s = 99, r = [] resulting in s = 24, r = [3]
Second value: x = 10, s = 24, r = [3] resulting in s = 4, r = [3; 2]
Third: x = 5, s = 4, r = [3; 2] resulting in s = 4, r = [3; 2; 0]
Last: x = 1, s = 4, r = [3; 2; 0] resulting in s = 0, r = [3; 2; 0; 4]

There you have it, step-by-step through the Coin Changer kata using MapFold.

Guess what the source code to MapFold looks for the most part like what we just experienced.  Here it is:



We see that it loops through each member of the collection, applying the function given against the state and current member.  Once there are no more members it returns a tuple of the result along with the state.  For the Coin Changer kata we do not care about the state (maybe we could use it verify that we have 0 cents) so we just drop it and get the result using fst.

There you have it the Coin Changer kata and MapFold seem to be made for each other.

Data Structures Matters

"I see thee yet, in form as palpable"
-- Shakespeare, Macbeth
Act II, Scene I, Line 31 

One of the katas we like to use at work while interviewing candidates is the Roman Numeral kata.  It is a simple kata in which you create a function which takes an integer and gives you back a string representing the roman numeral representation of the number.  It is fairly simple to explain but is deep enough to get a good idea of how the person works.

Here is a possible solution to the Roman Numeral kata in C#.



Looking at this solution we see a few things.  The solution is using C# 6.0 syntax but beyond that we see three major things.

1. translation are being applied using the higher order function Fold (in C# Aggregate)
2. mutation of the input value is used to maintain state through iterations
3. translations are held in a Dictionary

Let us look at the Dictionary data structure which is the main focus of this post.  In general a Dictionary is not ordered, now some implementations are ordered in the order in which the key value pairs are inserted (this is the case with the C# implementation), but this is not a property of the Dictionary data structure (see also the NIST entry).

Here is a possible solution to the Roman Numeral kata in Clojure.

Looking at this solution we see a few things.

1. translations are being applied using the higher order function Fold (in Clojure reduce) 
2. hash maps are used to maintain state through iterations
3. translations are held in a vector of vectors

We see that we cannot use a Dictionary (called maps in Clojure) to hold the translation.  Clojure's HashMap uses Phil Bagwell's Hash Array Mapped Trie which makes no claim about order, in fact we see that maps (and sets) are unordered while vectors (lists and seq) are ordered.  Since our algorithm requires that the translations be in the order we insert them we must use a data structure which preserves this order.  Thus we must used something that is ordered like a vector.

How about F#?  Here is a possible solution to the Roman Numeral kata in F#.

Looking at this solution we see a few things.

1. translations are being applied using the higher order function Fold (using F#'s List.fold)
2. tuples are used to maintain state through iterations
3. translations are held in a List

For the same reasons that we found in the Clojure solution we cannot use a Dictionary (called a Map in F#) since they are ordered by F#'s generic comparison and not in the ordered in which they were inserted.  Luckily we can use a List which is ordered.

There you have it, the Roman Numeral kata in three different languages.  Despite being a simple kata we have learned something about the Dictionary data structure, mainly that it does not have an order and thus should not be used in cases in which order matters.

Folding Up the Coin Changer Kata

"Whate'er the course, the end is the renown."
-- Shakespeare, All's Well That Ends Well
Act IV Scene IV, Line 36

Coin Changer Kata

The Coin Changer kata has three things which make it a good kata.

1. easy to understand
2. rich set of features
3. lots of realistic possible implementations

Even in today's cashless society, most people understand the idea of handing someone over some money and get change back.  This handing back of change requires the breaking down of the change over coins of different denominations.  Finding which coins to hand back has lots of possible implementations which translate over to things which programmers do every day.

The user story is very simple:

Given a collection of coins of different denominational value
When an amount of change is given
Then it will give back the number of coins for each denomination needed using the least amount of coins possible

A type signature for the function needed could look like the following:

changeFor(coins: int[], amount: int): int[]

We are expecting an array of integers which have different denomination of coins (in the US something like: [25, 10, 5, 1]) and the amount of change needed (something like: 99) giving a resulting array of integers showing how many of each denomination (something like: [3, 2, 0, 4]).

What would we need to be able to do this kata using just Fold?

We'll need to use a tuple (or something like one) to manage the state of the amount of change needed and the resulting array of integers.

Now lets look at an example using a typical full US register with quarters, dimes, nickels, and pennies.  We'll look at getting change for 99 cents.

First Memorize has (99, empty) and X has 25 giving the result of (24, [3]).

Next Memorize has (24, [3]) and X has 10 giving the result of (4, [3, 2]).

Then Memorize has (4, [3, 2]) and X has 5 giving the result of (4, [3, 2, 0]).

Last Memorize has (4, [3, 2, 0]) and X has 1 giving the result of (0, [3, 2, 0, 4]).

Finally obtaining the tuple item with the resulting array of integers to get the change.

Clojure

We see with the Clojure code that we seed with a map with a key for the :amount and one for the :result.  We fold over the coins using reduce destructing the memoize value into the amount and result.  We then just calculate the new amount using: amount % coin, follow by inserting the number of coins we get using: amount / coin.  We use cons to show off the coolness that is the thread-last macro (at least that is why I think I coded it this way, it was a little bit ago that I did the gist and I cannot remember why I code with cons over conj).

C#

We see with the C# code that we seed using a Tuple (which I think has very ugly syntax in C#).  We then fold over the coins using aggregate just like the Clojure code above.  We calculate the changer results and place them into a new Tuple which we return as the memoize.

ECMAScript 2015

In this ECAMScript 2015 example we use lodash's foldl to fold over the coins just like the two examples above.  The seed value is a simple JavaScript object with the members of amount and result given.  We are a bit dirty and mutate the memoize on each call with the changer results but we could argue that this is still "pure" since the mutation happens to an item which is created and used only in side the function.

ECMAScript 2015 and Immutable.js

Last we look at Facebook's open source Immutable.js.  We create an immutable List with the coins which we use to fold over the values using reduce.  The seed value we give it is a simple JavaScript array with an immutable List to hold the results and the amount passed in.  We could use an immutable Map if we wanted to keep it purely immutable.  Like this:



I am not a huge fan of stringly typed accessors, but I understand why they use them.  Both ways are good and would really come down to to performance and readability.

The End

Thus ends our tour of All You Need is Fold, but this is not the end of the uses of Fold, for Fold is universal.

Bro, Do You Even FizzBuzz?!?

"Do you bite your thumb at us, sir?"
-- Shakespeare, Romeo and Juliet
Act I, Scene I, Line 43

FizzBuzz as an interview kata has been getting a lot of bad press lately.  Part of the bad press has been around having to use modulus in the solution.  I am not sure how people have been explaining FizzBuzz in interviews, but you do not have to know anything about the mod operator in order to solve the problem.

Here is a solution in Clojure which does not use modulus.



This solution is using cycles and zip.  The odds are low of someone knowing how to use cycle and zip but not knowing modulus.  The point is that you do not need to know about modulus to do the kata.

In interviews I do, I'll tell the person about modulus if they get stuck.  The point of using a kata in an interview is to make sure that person who claims to be a programmer can actually program and that you can work with the person.

Still if the whole modulus thing has you worried, try the Roman Numeral kata.

Here is a solution in C# I did few minutes before an interview on Thursday (pro-tip, always make sure you can do the kata in short amount of time before you ask someone else to do it in an interview).



Again, the goal of the interview kata should be to see if the person can actually program and to see what they are like to work with.

"No, sir, I do not bite my thumb at you, sir. But
I bite my thumb, sir."

-- Shakespeare, Romeo and Juliet
Act I, Scene I, Lines 49-50

On Being Joyful By Contract

"How joyful am I made by this contract!"

-- Shakespeare, Henry VI Part I
Act III, Scene I, Line 144

I can think of no book that has had more impact on my career than The Pragmatic Programmer by Dave Thomas and Andy Hunt.  One of the tips in The Pragmatic Programmer that I sadly do not find myself using a lot is Design with Contracts.

Design with Contracts
Use contracts to document and verify that code does no more and no less than it claims to do.
-- Dave Thomas and Andrew Hunt, The Pragmatic Programmer

Clojure has pre: and post: assertion functions, let us look at an example of the pre: assertion function in a prime tester function.

We can easily see this is not the worlds greatest prime test function, but the point is to look at the pre: assertion function.

We see that in order to call this function we must have the following: 1) the argument used in the call must be a number (defined by number? as instance? Number) and 2) the argument used in the call must not be negative.  We see by the tests that if either pre: condition is broken an AssertionError is thrown.  Thus allowing us to assume in the body of the function that we have a number and that it is not negative.

If one designs with contracts then one can easily reason about a system since one knows what each part of the system can produce.

Always Bet on Math

"If we offend it is with our good will.
That you should think we come not to offend
But with good will. To show our simple skill,
That is the true beginning of our end."
-- Shakespeare, A Midsummer Night's Dream
Act V, Scene I, Lines 108-111

Last week at work we did Pascal's Triangle as part of our weekly Code Dojo.  We followed the animated image on the Wikipedia entry as our guide to the algorithm.



This worked OK and we were able to solve it fairly quickly with something similar to the C# entry on Rosetta Code.  Something like this:

        public static void CreateTriangle(int n) {
            if (n > 0) {
                for (int i = 0; i < n; i++) {
                    int c = 1;
                    Console.Write(" ".PadLeft(2 * (n - 1 - i)));
                    for (int k = 0; k <= i; k++) {
                        Console.Write("{0}", c.ToString().PadLeft(3));
                        c = c * (i - k) / (k + 1);
                    }
                    Console.WriteLine();
                }
            }
        }

This code works but it does not really give the reader of it any idea as to what the code is for.  In order for someone to be able to follow this code they would have to run the algorithm a few times (in their heads, on paper, ...) to prove to themselves that it actually works.

In Rich Hickey's talk, "Hammock Driven Development", he talks about taking time to think.  Which reminds me of a quote often misattributed to Einstein:

Some years ago the head of the Industrial Engineering Department of Yale University said, "If I had only one hour to solve a problem, I would spend up to two-thirds of that hour in attempting to define what the problem is."
-- Robert E. Finley and Henry R. Ziobro, The Manufacturing Man and His Job
as quoted by Garson O’Toole at http://quoteinvestigator.com/2014/05/22/solve/

Let us spend a few minutes looking into what the problem actually is.

If look further down in the Wikipedia entry we see the following.


taken from https://commons.wikimedia.org/wiki/File:PascalsTriangleCoefficient.svg

Awesome, Pascal's Triangle can be reduced to binomial coefficients!  Since it has been about 13 years since I got my degree in mathematics I'll need to look up how to use and solve a binomial coefficient.  Luckily MathWorld give use the following:

Great, now all we need to do is have a way to solve for factorials, which we can also find on MathWorld!

We are now all set to solve the problem.

Here is my solution in Clojure:


(I did this as part of my daily kata)

We see in the Clojure code that I TDDed my way into: first a function which will find factorials, then a function to solve for binomial coefficients, and finally I a function which will give Pascal's Triangle.  Solving the problem in this way gives us not only a readable solution which allows someone reading the code to follow the solution but now we have a function for factorials and one for binomial coefficients!

Do not misread this blog post I am not saying that the solution given in C# above is wrong or bad, but only that by spending time to research a problem can often given a much more rich solution to the problem.

As IBM would say, "Think".

taken from http://www-03.ibm.com/ibm/history/ibm100/images/icp/P496146V03975A59/us__en_us__ibm100__cult_think__think_sign__620x350.jpg

Leap Year kata OR How TDD Does Not Mean No Forethought

"Hence! home, you idle creatures, get you home:
Is this a holiday? What, know you not,
Being mechanical, you ought not walk

Upon a labouring day without the sign
Of your profession? Speak, what trade art thou?"
-- Shakespeare, Julius Caesar
Act I, Scene I, Lines 1-5

The Leap Year kata is interesting.  The real trick to the kata is not the leap year algorithm.  No, it is picking the test cases in such a way as to not cause you to have to write the whole thing at once.

Let us look at an implementation in Clojure.



We see that the key to picking test cases is to have an idea of the order in which you plan on writing your code.  How so?  In the first test case we pick leap years divisible by 400, then we pick non-leap years divisible by 100, then leap years divisible by 4, and then years which are not leap years.

Does setting up your test case with the algorithm in mind violate TDD?  I say no.  In fact I think Uncle Bob would say no.



TDD does not mean no architecture.  TDD does not mean no forethought.  No, TDD means no production code is written without a test and that only as much production code is written as what is needed to pass the current failing test.

In other words, TDD would want you to think about the leap year algorithm a head of time and pick test cases which will move along the algorithm.

Roman Numeral Kata in One Line with C#

"When in one line two crafts directly meet."
-- Shakespeare, Hamlet
Act III, Scene IV, Line 211

The idea of the Roman Numeral kata is that given a number between 1 and we'll say 4999, the number will be converted into the Roman numeral form.

f(1) = "I"
f(2) = "II"
f(3) = "III"
f(4) = "IV"
f(5) = "V"
...
f(4999) = "MMMMCMXCIX"

You can test a value using Google's search by typing the number and "to roman".  Try searching for "299 to roman" to test it out.

At work, we have been using the Roman Numeral kata for interviewing candidates.  The idea is that we get an idea of what it is like to work with the person and they get an idea of what it is like to work with us.  As an added bonus there is a good chance that we will learn something new from each other in the process.

On one such interview recently, we had a candidate do something rather interesting.  Typically a candidate will just start with a series of if statements, some candidates will replace the ifs with an associative data structure (called dictionary in C#), but most will not.  This candidate did a transformation of the input into a string of "I"s and then replace those with the Roman numeral.  They did not ended up finishing or even coming to a general pattern, but I found this idea interesting and ran with it coming up with a C# one liner.



We see in the code above a few different things.

To make this a REPL one liner we create a Func which takes an integer and returns a string, we then start the lambda expression with the bond variable of number.  (In the refactoring done on the candidates code this was all in a single return statement in a method not a Func variable, but when I redid it for this post I did it on the Mono REPL as a Func variable.)

Func<int, string> toRoman = (number) =>

After that we have our associative array, which allows us to look up each of the transformation that we will be doing, this is very useful since to add another transformation we just need to add an entry to the associative array.  (I've done this kind of thing in real world application but I normally will make the look up be a private member of the class.)

new Dictionary<int, string>


{


{1000,  "M"},


{ 900, "CM"},


{ 500,  "D"},


{ 400, "CD"},


{ 100,  "C"},


{  90, "XC"},


{  50,  "L"},


{  40, "XL"},


{  10,  "X"},


{   9, "IX"},


{   5,  "V"},


{   4, "IV"},


{   1,  "I"}


}

**Note, you do not need the "I" entry in the associative array do the the seed value of the fold, but we'll leave it in there since it is from the more general way of doing this kata.**

We then take this and run it through a fold (called Aggregate in C#).

.Aggregate(

In the seed value to the Aggregate we create a transformation string of the "I"s equal to the value given by the caller.

t(1) = "I"
t(2) = "II"
t(3) = "III"
t(4) = "IIII"
...
t(20) = "IIIIIIIIIIIIIIIIIIII"

To do this we use the string constructor that takes a character and the number of times you wish that character to repeat.

new string('I', number),

We then have the lambda of the Aggregate in which we simply take the current Key and Value from the associative array and call Replace on the transformed string replacing the number of "I"s given in the Value with the Roman numeral given in the Key.

(m, _) => m.Replace(new string('I', _.Key), _.Value));

This is not the "best" implementation of the Roman Numeral kata, but it is a one liner!



"The one I'll slay; the other slayeth me."
-- Shakespeare, A Midsummer Night's Dream

Act II, Scene I, Line 190

Leap Year in the Key of C#, F#, Haskell, and Scala

"Shall be their father's bail, and bane to those"
-- Shakespeare, Henry VI Part 2
Act V, Scene I, Line 120

Leap Year

Leap year, one of the time based banes of a programmers' existence.

The rules around if a year is a leap year are simple enough.

if year is divisible by 400 then

   is_leap_year

else if year is divisible by 100 then

   not_leap_year

else if year is divisible by 4 then

   is_leap_year

else

   not_leap_year

Most languages do have a built in check for Leap Years, but the point of the kata is to implement your own in order to learn something.  With that in mind let's look at few ways to solve this problem and see what we can learn.

C#

Note, if we want to do it the most efficient way possible we could just use the built in DateTime.IsLeapYear, but the point of the kata is to implement the algorithm yourself in order to learn something.



Here is an example using C# with NUnit for the testing.

We see that we can just implement the algorithm as a series of conditional statements.  We also see that with NUnit we can use the TestCase attribute which allows us to just give the input along with the expected result.  This kind of testing I feel leads to more readable test cases which focus on the data and not the steps needed.  Having a test case which focuses on the data is the right approach in my opinion for testing a pure calculation based function like this.

Haskell

Note, this looks a lot like the code on Rosetta Code for the TDD Haskell implementation of Leap Year, because it is the same code that I contributed there for that entry.



This Haskell solution uses pattern matching.  If you are new to pattern matching you can think of it as a switch statement.

With this style of pattern matching in Haskell we would get an error message if we call the function without a value which was covered, but the otherwise keyword at the end covers everything else so getting an exception would not happen.  Comparing this to the C# solution with a series of conditional statements the Haskell caller knows that every input is covered by the function whilst the C# call will have to hope that all input cases are covered.

Scala

Note, this is my third Scala kata ever, as such I need to look at this gist form Kingsley Davies in order to do the kata.



With the Scala solution we are again using pattern matching, but this time we are doing all of the testing in a tuple which we are matching against (note, we could have done this in the Haskell and below in the F# solution).  Using this style of pattern matching we are matching against a pattern but in this case I feel that the algorithm is hidden, as such for this function I do not think this is an improvement over the Haskell solution above (note, I did this on purpose to try out this approach with this solution to see what it would look like).

F#

This last solution using F# uses Active Pattern Matching.  Personally I find the Active Pattern Matching with a Maybe Monad very readable.  We can see that the algorithm states if the year is divisible by 400 we have leap year, but if it is divisible by 100 we do not.

Note, you can do this pattern in Scala and Haskell.

Conclusion

We see above 4 somewhat different ways to find if a year is a Leap Year.  All these approaches used unit testing frameworks along with TDD.  None of the solutions are the way to do it, but each look at the problem from a different point-of-view.

The Form of Katas

"Your honour with your form."
-- Shakespeare, Coriolanus
Act II, Scene 2, Line 142.1

Intro

Every work day around 6:30 AM you'll find me working on a Code Kata.  I find that this is one of my most inventive times of the day.  While doing my Code Kata I try out everything and anything.  I am truly free doing my Code Kata, I even allow myself to fail.

Around 6:55 AM my kata be it is good, bad, or some where in between comes to an end.  I get up and go make some coffee to start my work day.  (In case you are wondering, my kata takes place out side of my normal 8+ hour work day.  I write this since it has come up in talking with people at conferences about katas.)

Why do I do my Code Kata?  I have lots of reasons, but the main ones are the following:

1) I do a Code Kata everyday to get better.
2) I do a Code Kata everyday to try out new things.

I wrote about these in more details in an earlier post called "A Kata a Day".

What is a Code Kata

A Code Kata is simply, focus programming for the joy of programming.  Focus because you are working on getting better.  Joyous because you want to have fun doing it.  (Pro tip, if you do not like programming than why bother doing it?)  That is all.

I typical choose from a few simple katas that I know rather well.  I do this because I do not want the problem domain to get in the way of what I am focusing on.  What does this mean?  If I want to try out a new JavaScript framework then I do not want the problem domain of my kata to get in the way of learning how to use the framework.

FizzBuzz

The FizzBuzz kata is a very simple exercise yet has enough to it to be usable to vet candidates at an interview (we use this where I work to vet our candidates).

Examples

FizzBuzz(2) -> “2”

FizzBuzz(3) -> “Fizz”

FizzBuzz(5) -> “Buzz”

FizzBuzz(15) -> “FizzBuzz”

Rules

• If value is divisible by 3 then Fizz
• If value is divisible by 5 then Buzz
• If neither then give value as string

As you see you have one edge case with values which are divisible by both 3 and 5.  In fact one such edge case is the value 0 which cause issues in some languages like JavaScript in which 0 is a special value.  The great thing about FizzBuzz is that you can use it to try out new ideas like creating a RESTful FizzBuzz API.  Yep, FizzBuzz as a service!

Check out this slideshare from the most recent meeting of the Lake County .Net Users Group.  (Yeah I know I am a Co-Leader of said group and that link is to my Slideshare!  If I do not promote myself than who will?)

A Solution

Here is a solution using C# with LINQ.

Coin Changer

I first saw the Coin Changer kata at SCNA in a battle kata.  This is a great kata since you get to work with a collection of data.

Example

Changer.coins = [pennies]
Changer.for(3) -> [3]

Changer.coins = [dimes, nickels, pennies]
Changer.for(17) -> [1, 1, 2]

Changer.coins = [quarters, dimes, nickels, pennies]
Changer.for(99) -> [3, 2, 0, 4]

Changer.coins = [nickels, pennies]
Changer.for(99) -> [19, 4]

Rules

• Given coins of different values
• Find the number of coins given back for a given amount

This kata has a lot of interesting edge cases to it.  Like the following edge case, what should you do if you have only dimes and nickels but need to make change for 36 cents?

Again, check out this slideshare.

A Solution

Here is a solution using C# with LINQ.

Other Ideas for Your Next Code Katas

Looking for new ideas for your next kata?  Check out the following:

• Rosetta Code
• Dave Thomas' site CodeKata.com
• Uncle Bob's Bowling Game Kata

Happy coding.

A Kata A Day

"But such a day tomorrow as today."

-- Shakespeare, The Winter's Tale
Act I, Scene II, Line 64

"For ever and a day."
-- Shakespeare, As You Like It

Act IV, Scene I, Line 134

A Kata A Day  

Epictetus, the Stoic philosopher, was record to have said,

"Practice yourself, for heaven’s sake, in little things; and thence proceed to greater."

-- Epictetus, Discourses, Book 1, Chapter 18

Ever since Cory Foy's presentation at SCNA 2012 I have been doing a software kata at the start of every work day.  Yes, every single day with very few exceptions, even during the two weeks when I was putting in hellish overtime for a big release!  I find this practice is a great way to start the day.

Chong Kim recently blogged about using katas to improve one's coding.  I completely agree, in fact I have found that katas are a great way to learn new languages, styles, frameworks, ...

"Katas can stretch our abilities and, similar to how a kata would teach a martial artist to become comfortable with the uncomfortable, they help us write code we may not normally write."

-- Micah Martin

So far in my year experience of daily katas I have used katas to learn: F#, Haskell, Clojure, JavaScript, node.js, SpecFlow, Mocha, continuation passing style, ...  So what sir, that is just a list of random programming languages and testing frameworks, have you actually gained anything?!?  Hmmm, that is a very hard question to answer, in order to truly answer it I would need to have done an experiment in which we have two programmers with equal ability and have one start their day with a kata while the other one gets an extra 25 minutes of sleep.  I did not set up such an experiment when I start around a year ago.  To make you for this lack of planning how about if we do a thought experiment?  Thought experiments were good enough for Einstein after all.

Say we have two programmers of equal abilities.  Elvis would like to take his programming to the next level and as such will start each work day with a code kata.  Mel on the other hand would just like to get to Friday and as such will sleep an extra 25 minutes each day instead of doing a code kata.  In a work month there are about 21 days, so in one month Elvis would have done 21 different code katas.  After about 3 months that would be about 65 katas which is enough practice time to learn a new skill or two.  In one year Elvis would have gained about 8 new skills while Mel would have slept around an extra 108 hours.  With 8 new or reinforced skills Elvis would find that he is well on his way to rock star status.

"Practice does not make perfect. Only perfect practice makes perfect."
-- Vince Lombardi

Here is the rub, those katas need to be deliberate practice, meaning they need to have goals, they need to push your skills, they need to expand what you think you can do, they need to make you better.  Merely sitting down and coding for 25 minutes is not enough.  You need to be mindful as you practice.  You need to have goals of what you want to do and you need to stick to them!  Use your katas as experiments.  Go to Rosetta Code and try something you have never done before.  Look up different programming language paradigm on Wikipedia and try them.

The principal of linguistic relativity comes in two forms: "(i) the strong version that language determines thought and that linguistic categories limit and determine cognitive categories and (ii) the weak version that linguistic categories and usage influence thought and certain kinds of non-linguistic behavior".  Regardless of which version you follow, the conclusion of our needs is the same, you are what you consume/do.  If you have used Higher Order Functions before in a kata then when you see a problem which is perfect for applying them you'll use them.

There is debate around if Eskimos have more words for snow than other cultures, but Kenneth Iverson inventor of APL and ACM Turning award winner and Paul Graham (all around genius) both believe that language influences how you think about a problem.  Graham calls this the Blub Paradox.

"programming languages are not merely technologies, but habits of mind as well"
-- Paul Graham, Beating the Averages

The programming language that you use to try to solve a problem not only dictates how you go about solving a problem but how you actually think about the problem!  Don't believe me, write the Prime Factorization kata in an Object Oriented language and Functional language.  What is the first hurtle that you hit in an Object Oriented language when solving a behavioral based problem?  Is it what type of objects do I need?  Does that really make any sense to think of when you finding the prime factors of a number?!?

Letter Occurrence

"Machines take me by surprise with great frequency."
-- Alan Turning

I do a code kata a day to keep unemployment away.  Well I actually do it to learn F#, but the previous statement sounds better.  Recently I was on Rosetta Code looking for an idea and came across a letter frequency counting problem.

The problem is simple:

Given a string, count how many times each letter occurs in said string.

Not too hard of a problem, but how do we "best" solve this with a functional language?

What I would like to do, would be to group each letter together and then count the number of occurrences of each letter in the group.  To make it easier to test I'll place the results into a Map with the key being the letter and the value being the number of occurrences of the letter in the input string.

In F# if you want to do a Group By you'll have to use Seq.groupby which takes a function (in this case we can use the identity since we are not doing anything with the elements of the string) and a sequence (in this case the string).  It gives you a sequence of keys and the complete sequence of values (e.g. A * seq AAAA).  Once we have that we just need to make a tuple with the value as a string and the number of times the value occurs, we can use Seq.map to do this.  Last we just need to place these tuples into a Map.

let occurs str =

  str 

      |> Seq.groupBy (fun c -> c) 

      |> Seq.map (fun (c, n) -> (c.ToString(), Seq.length n)) 

      |> Map.ofSeq

With this simple function we can now count the number of times a letter occurs in a string (similar to the Hadoop Hello World type program).

Below you'll find the full code from the kata including the unit tests.  For comparison I did the same kata again in Javascript (again and always with unit tests).

In F# (with FsUnit):

open NUnit.Framework

open FsUnit

let occurs str =

  str |> Seq.groupBy (fun c -> c) |> Seq.map (fun (c, n) -> (c.ToString(), Seq.length n)) |> Map.ofSeq

[<Test>]

let ``Validate that "A" has 1 A occurence`` () =

  let result = Map.empty.Add("A", 1)

  occurs "A" |> should equal result

[<Test>]

let ``Validate that "AAA" has 3 A occurence`` () =

  let result = Map.empty.Add("A", 3)

  occurs "AAA" |> should equal result

[<Test>]

let ``Validate that "AB" has 1 A occurence and 1 B occurence`` () =

  let result = Map.empty.Add("A", 1).Add("B", 1)

  occurs "AB" |> should equal result

[<Test>]

let ``Validate that "ABBBCCA" has 2 A occurence, 3 B occurence, and 2 C`` () =

  let result = Map.empty.Add("A", 2).Add("B", 3).Add("C", 2)

  occurs "ABBBCCA" |> should equal result

You can find the F# source code here.

In Javascript (with QUnit):

function occurs(letters) {

          var countletters = {}, index = 0;

         

          return function counter() {

                   if (letters.length <= index) {

                     return countletters;

                   }

                  

                   return function incrument() {

                       var letter = letters[index++];

                             countletters[letter] ? countletters[letter] += 1 : countletters[letter] = 1;

                             return counter();

                   }();

          }();

}

test("Count a string with 1 A", function () {

          var actual, expected = {};

          expected["A"] = 1;

          actual = occurs("A");

          deepEqual(actual, expected);

});

test("Count a string with 2 A", function () {

          var actual, expected = {};

          expected["A"] = 2;

          actual = occurs("AA");

          deepEqual(actual, expected);

});

test("Count a string with 1 A and 1 B", function () {

          var actual, expected = {};

          expected["A"] = 1;

          expected["B"] = 1;

          actual = occurs("AB");

          deepEqual(actual, expected);

});

test("Count a string with 2 A and 2 B", function () {

          var actual, expected = {};

          expected["A"] = 2;

          expected["B"] = 2;

          actual = occurs("ABAB");

          deepEqual(actual, expected);

});

test("Count a string with 2 A and 2 B and 1 C", function () {

          var actual, expected = {};

          expected["A"] = 2;

          expected["B"] = 2;

          expected["C"] = 1;

          actual = occurs("ABCAB");

          deepEqual(actual, expected);

});

You can find the Javascript source code here.