Mark Needham

Thoughts on Software Development

Archive for the ‘code-kata’ tag

Scala: Code Kata #2 – Karate Chop – Array Slicing Attempt

with 6 comments

In my continued attempts to learn a bit of Scala I’ve been trying out the 2nd of Dave Thomas’ code katas – Karate Chop – while using an array slicing approach.

I’ve tried out the iterative approach to this problem in Java about a year ago and it ends up being quite verbose so I thought the array slicing one would be much more concise.

I didn’t drive any of the solutions I worked on from the tests – in fact I only got all the tests provided by Dave Thomas running right at the end which was probably a mistake in retrospect.

My first solution didn’t really work at all – it resulted in an ‘ArrayIndexOutOfBoundsException’ for pretty much any input where the ‘needle’ wasn’t the middle value:

def chop(needle : Int, haystack : Array[Int]) : Int  = {
	val middleIndex = haystack.length / 2
	if(haystack(middleIndex) == needle)
		return middleIndex
	else if(haystack(middleIndex) < needle) 
		return chop(needle, haystack.slice(0, middleIndex))
	else
		return chop(needle, haystack.slice(middleIndex + 1, haystack.length))
}

It turns out that the logic is actually the wrong way around – if we find that ‘haystack(middleIndex)’ is less than ‘needle’ then we want to be looking at the 2nd half of the array and not the first half!

Attempt number two addressed this problem:

def chop(needle : Int, haystack : Array[Int]) : Int = {
	val midpoint = haystack.length/2
	val valueAtMidpoint = haystack(midpoint)
 
	if(valueAtMidpoint == needle) return midpoint
	else if(valueAtMidpoint > needle) return chop(needle, haystack.slice(0, midpoint))
	else return chop(needle, haystack.slice(midpoint, haystack.length))
}

The problem with this solution is that if the ‘needle’ is in the second half of the array then it will end up reporting us the wrong position with respect to the whole array – we will just get the position of the ‘needle’ in the remaining array.

This suggested to me that I would probably need to make use of an inner function to keep track of how many items had been discarded whenever we realised that the item was in the second half of the array.

We could then add that value to the final index position if the ‘needle’ was found in the array:

def chop(needle : Int, haystack : Array[Int]) : Int = {	
	def chopInner(discardedItems : Int, innerHay : Array[Int]) : Int = {	
		val midpoint = innerHay.length/2
		val originalMidpoint = midpoint + discardedItems
		val valueAtMidpoint = innerHay(midpoint)
 
		if(valueAtMidpoint == needle)  
			originalMidpoint
		else if(valueAtMidpoint > needle)  
			chopInner(0, innerHay.slice(0, midpoint))
		else  
			chopInner(originalMidpoint, innerHay.slice(midpoint, innerHay.length))
	}
	chopInner(0, haystack)
}

This solution will find the position of ‘needle’ if that value exists in the ‘haystack’ but if the value isn’t in the list we end up in an infinite recursion and if the list is empty then we end up with an ‘ArrayIndexOutOfBoundsException’ when we try to get the value of the midpoint.

My truly hacky solution which solves these two problems looks like this:

def chop(needle : Int, haystack : Array[Int]) : Int = {	
	def chopInner(discardedItems : Int, innerHay : Array[Int]) : Int = {	
		if(innerHay.length == 0) 	
			return -1
 
		val midpoint = innerHay.length/2
		val originalMidpoint = midpoint + discardedItems
		val valueAtMidpoint = innerHay(midpoint)
 
		if(valueAtMidpoint == needle)  
			originalMidpoint
		else if(valueAtMidpoint > needle)  
			chopInner(0, innerHay.slice(0, midpoint))
		else if(innerHay.length == 1)  
			-1
		else  
			chopInner(originalMidpoint, innerHay.slice(midpoint, innerHay.length))
	}
	chopInner(0, haystack)
}

I converted Dave Thomas’ tests into ‘specs‘ tests using the following regular expression:

Find:

assert_equal\((.*),[ ]+chop\((.),[ ]+\[(.*)\]\)\)

Replace:

chop($2, Array($3)) mustBe $1

I then adapted my colleague Sam Newman’s bigvisiblewall project so that I could make use of the ant script he’s setup which makes specs and ant play nicely together.

All the tests pass but there must be a cleaner solution than what I’ve ended up with – I think another attempt will be required!

Written by Mark Needham

October 13th, 2009 at 7:00 am

Posted in Code Katas,Scala

Tagged with ,

Learnings from Code Kata #1

without comments

I’ve been reading My Job Went To India and one of the chapters midway through the second section talks about the value of practicing coding using code katas.

I’ve not tried doing these before but I thought it would be an interesting activity to try out.

The Kata

Code Kata One – Supermarket Pricing

What I learnt

  • As this kata is not supposed to be a coding exercise I started out just modeling ideas in my head about how I would do it before I realised that this wasn’t working as an effective way for me to learn. I decided to try and test drive some of my ideas to see whether they would actually work or not.

    It also gave me the chance to play around with git – I put the code I wrote on github – and re-commence my battle with buildr.

  • Having decided to fire up IntelliJ and try out some of my ideas in code I realised that test driving straight away wasn’t going to work well – I hadn’t spent enough time designing the objects that I wanted to test. I still wanted to try out my ideas in code though so I spent about ten minutes roughly coding out how I expected it to work before using a test driven approach to drive out the (admittedly simple) algorithms.

    While Test Driven Development is a very effective technique for driving out object interactions and ensuring code correctness, it was good to have a reminder that there still needs to be some up front design work before diving in.

  • One of the mistakes I made early on was over engineering my solution – I saw an opportunity to put one of my favourite patterns, the double dispatch pattern into the code. I did this straight away before stepping back and realising that it wasn’t really needed in this instance.

    Speaking to a couple of my colleagues about this the next day they reiterated the need to keep it simple.

  • I consider myself to be reasonably competent when it comes to object modeling – it is certainly something I enjoy doing – so I found it a bit disheartening that I struggled quite a bit to come up with solutions to this problem. I decided to return to the book and re-read the chapter. It had this to say:

    Looking back on it now, I see that the awkward feeling I got from these experiences was a good sign

    I was stretching my mental muscles and building my coding chops… if I sit down to practice coding and nothing but elegant code comes out, I’m probably sitting somewhere near the center of my current capabilities instead of the edges, where a good practice session should place me.

    It reminded me about an article I read earlier this year about ‘the expert mind‘ which talks of the value of effortful study.

    Ericsson argues that what matters is not experience per se but “effortful study,” which entails continually tackling challenges that lie just beyond one’s competence.

    This makes sense to me – we don’t improve that much by doing activities which we already know how to but equally we don’t want to be overwhelmed by the difficulty of the activity.

    While this task was difficult I think that reading most of Object Design prior to coming across this kata made it a bit easier than it would have otherwise been.

  • One unusual thing for me while I was trying out this exercise was that I wasn’t pairing with someone else. I think this made it more difficult as I didn’t have anyone to bounce ideas off and sub optimal solutions weren’t getting rejected as quickly due to the I had a longer feedback cycle. On the other hand, it provided good practice for improving my ability to spot unworkable ideas more quickly.
  • I really wanted to write the bits of code I wrote in a completely object oriented way. This meant having no getters on any of the classes which forced me to think much more about the responsibility of each object. Although I wrote very little code in this instance, this is a practice that will be useful for me when coding in other situations. I had a bit of difficulty trying to keep the code well encapsulated while also allowing it to describe the domain concepts but hopefully this is something that will become easier the more I practice.

Written by Mark Needham

October 18th, 2008 at 7:47 pm

Posted in Code Katas

Tagged with