digg

Binary Chop Shop in Scala
on November 03, 2009 @ 02:25 AM

In an effort to start learning Scala again (i started in the summer then got busy) I decided to tackle a simple yet fun code kata from Dave Thomas called karate chop

I ended up using Specs to make sure I passed Dave Thomas’s test criteria. I’m sure my below two solutions (recursive and while loop) are quite clunky compared to someone who’s familiar with Scala, but the goal of this was to get something running and passing. In a week or two I’ll revisit again after learning some more things about Scala and hopefully be able to tidy things up a bit.

Anyways, here’s my code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

class BinaryChopShop {
  def chopRecursive(target: Int, list: List[Int], args: Int*): Int = {
    if(list.isEmpty) return -1;

    val offset = if(args.isEmpty) 0 else args.first;

    if(list.size == 1){
      return if(list.first == target) offset else -1; 
    } else {
      val index = list.size / 2;
      val value = list(index);
  
      if(target < value)
        return chopRecursive(target, list.slice(0, index), offset);
      else
        return chopRecursive(target, list.slice(index, list.size), offset + index);
    }
  }
  
  def chopWhile(target: Int, list: List[Int]):Int = {
    var nlist = list;
    var offset = 0;

    while(!nlist.isEmpty){
      if(nlist.size == 1){
        return if(nlist.first == target) offset else -1;
      }
      
      val index = nlist.size / 2;
      val value = nlist(index);
      
      if(target == value) return index + offset;
      if(target < value){
        nlist = nlist.slice(0, index);
      } else {
        offset += index
        nlist = nlist.slice(index, nlist.size);
      }
    }
    return -1;
  }  
}
0 comments | Filed Under: | read on