Mark Needham

Thoughts on Software Development

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!

Be Sociable, Share!

Written by Mark Needham

October 13th, 2009 at 7:00 am

Posted in Code Katas,Scala

Tagged with ,

  • What about this?

    def chop(needle : Int, haystack : Array[Int]) : Int = {
    if (haystack.length == 0) return -1
    val midPoint = haystack.length / 2
    val midValue = haystack(midPoint)

    if (midValue == needle)
    midPoint
    else if (needle -1
    case index => midPoint + 1 + index
    }
    }

    You can add the midPoint to the found index as the results are being returned up the call stack, rather than passing it as an argument on the way down.

  • Oops, last post was killed by the angle brackets. I’ll try again, but in any case I put the code here: http://gist.github.com/210041

    def chop(needle : Int, haystack : Array[Int]) : Int = {
    if (haystack.length == 0) return -1
    val midPoint = haystack.length / 2
    val midValue = haystack(midPoint)

    if (midValue == needle)
    midPoint
    else if (needle < midValue)
    chop(needle, haystack.slice(0, midPoint))
    else
    chop(needle, haystack.slice(midPoint + 1, haystack.length)) match {
    case -1 => -1
    case index => midPoint + 1 + index
    }
    }

  • Pingback: Tweets that mention Scala: Code Kata #2 – Karate Chop – Array Slicing Attempt at Mark Needham -- Topsy.com()

  • @Raph – I really like that last bit of your solution where you pattern match on the recursive call, very cool.

    I’m thinking of maybe trying this kata again and trying to make the tests pass as I go rather than hacking in the edge cases at the end to see what it comes up with.

  • Pingback: Latest karate news – Scala: Code Kata #2 – Karate Chop – Array Slicing Attempt at Mark …()

  • Alan Kent

    Doesn’t slice() return a copy of the sub-array (and so would be slow)? Should it be using .view(offset,len) instead? (Or did slice() change in Scala 2.8 so it used to be fine, but now slice() returns a copy so view() should be used instead?)