Practicing Via Kata
One of the things I practiced a lot when I was first learning to be a developer was algorithms.
(I should probably keep that trend up if I want to stay a good developer, too…)
My favorite kind of practice is called the kata, an homage to the Japanese word meaning “form”. In programming circles, it was coined by Dave Thomas of Pragmatic Programmer fame, though you may have heard it uttered by Robert Martin as well. Coding kata are short programming challenges designed to stimulate mental processes and act as a sort of “warm-up” before real development is done. Nowadays, some of them are quite complicated and long. My preferred site for a repository of katas is Codewars.
The Kumite
Codewars features a secondary type of practice called kumite (pronounced KOO-mee-tay) – literally “grappling hands”, a very apt title, as you’ll see. In this variant, challengers compete against each other for the shortest, most efficient, or in general cleverest solution. To do this, they fork the solution to an existing kata and post their changes for others to see. Once that’s done, new challengers are free to fork the new solution and continue iteration.
It’s important to note that kumite are usually very small in focus and target a specific data structure, algorithm, or even just a small part of a data structure or algorithm. A good example of the size of a typical kumite might be the ever-present FizzBuzz challenge.
Why It Matters
Because they’re so small, I think it’s a really great practice tool. Not only do you get to bounce ideas off of other developers and engineers, but you get to use the language you’re working with in unique and sometimes weird ways. It doesn’t always have practical applications in terms of translating to useful production code, but it is nice to know what’s going on under the hood in case something goes wrong.
Let’s look at three different types of kumite that you might encounter.
In all the below examples, I’ve provided links to the kumite that I’m quoting. Feel free to create a Codewars account (I’m not affiliated) and play along! These are not necessarily the most optimized solutions.
Shortest Solution (AKA Code Golf)
Low score wins! The shortest solution kumite is by far the most common type of kumite you’ll encounter. Challengers take a snippet of code (or occasionally a prompt), and attempt to write the shortest piece of code that satisfies the test case. Solutions start out fairly readable and rapidly devolve into far more complicated code as programmers eschew best practices in favor of shortcuts and language quirks.
As mentioned above, a classic example of a shortest solution kumite might be the FizzBuzz challenge.
To start, a naive approach might be given:
def fizz_buzz(n):
if (n == 1):
return str(1)
elif (n == 2):
return str(2)
elif (n == 3):
return 'Fizz'
elif (n == 4):
return str(4)
elif (n == 5):
return 'Buzz'
# . . .
elif (n == 15):
return 'FizzBuzz'
# . . . ad nauseum
Next we might optimize slightly with some modulo:
def fizz_buzz(n):
if (n % 15 == 0):
return 'FizzBuzz'
elif (n % 5 == 0):
return 'Buzz'
elif (n % 3 == 0):
return 'Fizz'
else
return str(n)
This is nicer, for sure, but it’s far from the shortest. How do you feel about nested ternary operators?
def fizz_buzz(n):
return "FizzBuzz" if n % 15 == 0 else "Fizz" if n % 3 == 0 else "Buzz" if n % 5 == 0 else str(n)
Yikes! This is starting to look a little more confusing. But it can still be made shorter! I’ll leave that as an exercise to the reader.
Let’s take a look at a slightly more complicated example, where I used some interesting language tricks to shorten some code.
In this example, the task is to create a function called solve that takes an array as an argument and rearrange the values so that the first max value is followed by the first minimum, followed by second max value then second min value, etc. A link to the challenge description could make this clearer.
Here’s the first kumite solution that passed all the test cases:
def solve(arr)
[arr.sort.reverse, arr.sort].transpose.flatten.uniq
end
Looks like this takes the array and sorts it first in reverse order, then in normal standard order. The transpose function merges the two arrays into a 2D array (for instance [[1, 2, 3], [4, 5, 6]].transpose returns [[1, 4], [2, 5], [3, 6]]). Next, the flatten call does what you’d expect and returns an array in one dimension, before uniq removes any duplicate integers.
Now let’s look at my solution (I like to leave the old solution as a comment to compare size):
def solve(a)
# [arr.sort.reverse, arr.sort].transpose.flatten.uniq
a.sort!.reverse.zip(a).flatten.uniq
end
Notice in the first solution there’s two calls to array.sort(). My solution is able to get rid of one of them by using sort!, which mutates the array in place. I also use a different function, zip, instead of transpose purely because it has a shorter name and there’s no comma or space like in the array in the first solution. Functionally, it produces the same intermediate array as described for the first solution. And finally, you gotta use a single letter variable name. Low score wins.
It’s worth noting we can take this even further. Codewars allows you to add your own preloaded code. With that, we can open up Ruby’s Array class and redefine all the function names to use a single variable:
# Preloaded Code:
class Array
def C;sort!;end
def H;reverse;end
def E(a);zip a;end # Note the lack of parentheses!
def T;flatten;end # That would add a character!
def !;uniq;end
end
# Code
def solve(a)
# [arr.sort.reverse, arr.sort].transpose.flatten.uniq
# a.sort!.reverse.zip(a).flatten.uniq
a.C.H.E(a).T.!
end
As you can probably tell, this is considered cheating.
Most Efficient Solution
Efficiency challenges are rare, but they bring with them the highest value and benefit to participants. These types of kumites typically have some sort of benchmarking included in their test cases so you can compare who is “winning”. Results can be quite unexpected.
Let’s take a look at an example. Here, we generate a 10,000 strings of random size between 500 and 999 characters comprised of the digits 0 through 9. Our task is to define a solution that sums all the digits in the string, and do so in the most time efficient way possible.
Here’s all the setup and solution code:
require 'benchmark'
strings = []
10000.times do
string = Array.new(rand(500..1000)) do rand(10) end.join
strings << string
end
def solution1(s) s.chars.sum(&:to_i) end
def solution2(s) s.sum - s.size * 48 end
def solution3(s) s.sum do |x| x - 48 end end
def solution4(s) s.sum do |x| x - '0' end end
def solution5(s) s.sum { |x| x - '0' } end
def solution6(s) s.sum { |x| x - ?0 } end
Benchmark.bmbm do |x|
x.report do strings.each(&method(:solution1)) end # farekkusu
x.report do strings.each(&method(:solution2)) end # ttakuru88
x.report do strings.each(&method(:solution3)) end # steffan153 (test code author)
x.report do strings.each(&method(:solution4)) end # rowcased
x.report do strings.each(&method(:solution5)) end # pawptart
x.report do strings.each(&method(:solution6)) end # steffan153
end
puts "<PASSED::>" # prevent from saying failed tests
And here’s the output of that benchmark:
Rehearsal ------------------------------------
1.254070 0.000000 1.254070 ( 1.254210)
0.010379 0.000000 0.010379 ( 0.010393)
0.009801 0.000000 0.009801 ( 0.009814)
0.009901 0.000000 0.009901 ( 0.009912)
0.009633 0.000000 0.009633 ( 0.009647)
0.009587 0.000000 0.009587 ( 0.009599)
--------------------------- total: 1.303371sec
user system total real
1.247248 0.000000 1.247248 ( 1.247404)
0.010282 0.000000 0.010282 ( 0.010289)
0.009955 0.000000 0.009955 ( 0.009959)
0.010083 0.000000 0.010083 ( 0.010090)
0.009674 0.000000 0.009674 ( 0.009684)
0.009495 0.000000 0.009495 ( 0.009498)
Let’s start with the first solution. This is a classic idiomatic Ruby approach:
def solution1(s) s.chars.sum(&:to_i) end
This solution generates an array of characters from the string, then calls the sum function, which loops through the array and executes its block function on each element before adding the value to the total. If you’re not familiar with Ruby, the following code is identical and maybe easier to follow:
['1', '2', '3'].sum(&:to_i) #=> 6
['1', '2', '3'].sum { |element| element.to_i } #=> 6
Looking back at the benchmark, this took over a second (1.25) to run! That makes sense, since it’s iterating through the string for the chars function as well as sum.
Moving on:
def solution2(s) s.sum - s.size * 48 end
This is clearly way faster but this is not intuitive at all.
First of all, although s.sum and s.chars.sum look similar, they are not the same. The sum function for the string class sums the character code for each character, not the value (if it’s an integer). For instance, '1234'.sum would return 202, which makes sense because the character codes are 49, 50, 51, and 52 respectively. So from there, we can see that the second half of the function is simply offsetting each character by 48 (character code 0).
Nice!
def solution3(s) s.sum do |x| x - 48 end end
Now we’re really starting to get optimized. Here, the solution passes a block to the string’s sum function with the offset as an integer.
def solution4(s) s.sum do |x| x - '0' end end
Same thing here, but apparently subtracting a string literal is a little faster.
def solution5(s) s.sum { |x| x - '0' } end
And my solution is another incremental improvement where curly braces are a tiny bit faster than do .. end.
def solution6(s) s.sum { |x| x - ?0 } end
The final solution! Pretty neat that this turned out to be the fastest iteration. I can honestly say I’ve never used the ?0 syntax before!
Again, it’s not super important that I know the absolute fastest syntax for summing up strings of integers, but it is good practice nonetheless. We ended up duking it out over 1/10,000 of a second (0.0001) to come up with the best solution here.
Cleverest Solution
These are the most enjoyable to me. I like to try weird things to see what does and doesn’t work. They aren’t always the shortest or the fastest, but I always learn something about the language I’m working with when attempting a clever solution.
Here’s some good examples.
Return the smallest square that can fit in two identical rectangles, but my solution adds the challenge of removing any if statements or conditionals (branchless programming):
def minimal_square(a, b):
# This solution abuses the fact that we can multiply by True/False:
# For instance, 1 * True = 1 and 1 * False = 0
#
# A step further:
# (a * (a > b ) + b * ( b >= a )) is equivalent to max(a, b)
#
# And:
# (a * ( a < b ) + b * ( b <= a )) is equivalent to min(a, b)
#
# Putting it all together, the following is equivalent to:
# max(min(a,b)*2,max(a,b))**2
side = (((a*(a<b)+b*(b<=a))*2)*(((a*(a<b)+b*(b<=a))*2)>(a*(a>b)+b*(b>=a))))+\
((a*(a>b)+b*(b>=a))*(((a*(a<b)+b*(b<=a))*2)<=(a*(a>b)+b*(b>=a))))
return side**2
Return 100:
def returnhundred
one = Array.new(100, 100)
hundred = 1
one[hundred]
end
Print Hello, World! in ASCII art:
# Preloaded Code:
require 'base64'
HELLO_WORLD = 'IF8gICBfICAgICAgXyBfICAgICAgICAgICAgICAgICAgICAgICAgICAgICBf
ICAgICBfIF8gCnwgfCB8IHwgX19ffCB8IHwgX19fICAgIF9fICAgICAgX19f
X18gIF8gX198IHwgX198IHwgfAp8IHxffCB8LyBfIFwgfCB8LyBfICBcICBc
IFwgL1wgLyAvIF8gXHwgJ19ffCB8LyBfYCB8IHwKfCAgXyAgfCAgX18vIHwg
fCAoXykgfCAgIFwgViAgViAvIChfKSB8IHwgIHwgfCAoX3wgfF98CnxffCB8
X3xcX19ffF98X3xcX19fKCApICAgXF8vXF8vIFxfX18vfF98ICB8X3xcX18s
XyhfKQogICAgICAgICAgICAgICAgICAgIHwv'
def print(message)
puts Base64.decode64(message)
return 'Hello, World!'
end
# Code:
def hello_world
print(HELLO_WORLD)
end
Wrap Up
Practicing coding is great to level up your career. It doesn’t have to be extremely stressful. Do some kumite and see how you stack up to other people! You’ll learn a lot by trying new things and looking at other people’s code!
That’s all for now. Thanks for reading!