Code Kata 2 - Introduction

A binary chop (sometimes called the more prosaic binary search) finds the position of value in a sorted array of values. It achieves some efficiency by halving the number of items under consideration each time it probes the values: in the first pass it determines whether the required value is in the top or the bottom half of the list of values. In the second pass in considers only this half, again dividing it in to two. It stops when it finds the value it is looking for, or when it runs out of array to search. Binary searches are a favorite of CS lecturers.

This Kata is straightforward. Implement a binary search routine (using the specification below) in the language and technique of your choice. Tomorrow, implement it again, using a totally different technique. Do the same the next day, until you have five totally unique implementations of a binary chop. (For example, one solution might be the traditional iterative approach, one might be recursive, one might use a functional style passing array slices around, and so on).

Today I have written three methods so far. There has been a tremendous learning. May be this is why they say deliberate practice helps in programming.

Firstly I generated a random array of numbers and a random element to find in that array.

> library(testthat)
> set.seed(1977)
> MAX <- 10000
> N <- 1000
> x <- ceiling(sample.int(MAX, N))
> token <- x[sample.int(N, 1)]
> input <- sort(x)

Given this input , I went about coding three methods

Method 1

> chop1 <- function(input, token) {
     if (length(input) == 0) {
         return(-1)
     }
     idx <- sum((input == token) * seq(1, length(input), 1))
     return(ifelse(idx > 0, idx, -1))
 }

Testing Method 1

> expect_that(chop1(c(), 3), equals(-1))
> expect_that(chop1(c(1), 3), equals(-1))
> expect_that(chop1(c(1), 1), equals(1))
> expect_that(chop1(c(1, 3, 5), 1), equals(1))
> expect_that(chop1(c(1, 3, 5), 3), equals(2))
> expect_that(chop1(c(1, 3, 5), 5), equals(3))
> expect_that(chop1(c(1, 3, 5), 0), equals(-1))
> expect_that(chop1(c(1, 3, 5), 2), equals(-1))
> expect_that(chop1(c(1, 3, 5), 4), equals(-1))
> expect_that(chop1(c(1, 3, 5), 6), equals(-1))
> expect_that(chop1(c(1, 3, 5, 7), 1), equals(1))
> expect_that(chop1(c(1, 3, 5, 7), 3), equals(2))
> expect_that(chop1(c(1, 3, 5, 7), 5), equals(3))
> expect_that(chop1(c(1, 3, 5, 7), 7), equals(4))
> expect_that(chop1(c(1, 3, 5, 7), 0), equals(-1))
> expect_that(chop1(c(1, 3, 5, 7), 2), equals(-1))
> expect_that(chop1(c(1, 3, 5, 7), 4), equals(-1))
> expect_that(chop1(c(1, 3, 5, 7), 6), equals(-1))
> expect_that(chop1(c(1, 3, 5, 7), 6), equals(-1))

Learnings - Method 1

  • This was the first function I was coding in R after a very long time. Infact after 2 months or so. So, my hands were very rusty to begin with. It seemed like I was coding a foreign language after all. In one way , just to get my hands type the syntax took some time
  • which.min returns the index of the miniumum element in the array. It does not try to compare it with some external element
  • which compares the array to an external list
  • Incase which does not find the element it returns integer(0), something that i could not lay my hands on
  • I figured out a better way when I added up all the boolean values to check whether the element is present in the list or not
  • I wrestled with the fact that the element might be completely missing in the array and finally found a single statement that can give the result.
  • Experimented with testthat package from Hadley Wickam. I was completely at loss of words, language, memory when it came to testing. I forgot the last time I had written any test code. May be it was atleast 6 months ago. When I started playing around with testthat I realized that it was one of the most beautiful package.It is so intutively straightforward to test stuff. I played around with the code, read some article on the net on the usage of testthat.
  • This practice session was helpful in getting grips with testthat.

Method 2

> chop2 <- function(input, token, start = 0) {
     n <- length(input)
     if (n == 0 || input[n] < token) {
         return(-1)
     }
     if (n == 1 & input[n] != token) {
         return(-1)
     }
     if (n == 2 & input[1] == token) {
         return(1 + start)
     }
     if (n == 2 & input[2] == token) {
         return(2 + start)
     }
     mid <- ifelse(n%%2 == 0, n/2, (n + 1)/2)
     if (input[mid] < token) {
         return(chop2(input[(mid + 1):n], token, start + mid))
     }
     if (input[mid] > token) {
         return(chop2(input[1:mid], token, start))
     }
     if (input[mid] == token) {
         return(start + mid)
     }
 }

Testing Method 2

> expect_that(chop2(c(), 3), equals(-1))
> expect_that(chop2(c(1), 3), equals(-1))
> expect_that(chop2(c(1), 1), equals(1))
> expect_that(chop2(c(1, 3, 5), 1), equals(1))
> expect_that(chop2(c(1, 3, 5), 3), equals(2))
> expect_that(chop2(c(1, 3, 5), 5), equals(3))
> expect_that(chop2(c(1, 3, 5), 0), equals(-1))
> expect_that(chop2(c(1, 3, 5), 2), equals(-1))
> expect_that(chop2(c(1, 3, 5), 4), equals(-1))
> expect_that(chop2(c(1, 3, 5), 6), equals(-1))
> expect_that(chop2(c(1, 3, 5, 7), 1), equals(1))
> expect_that(chop2(c(1, 3, 5, 7), 3), equals(2))
> expect_that(chop2(c(1, 3, 5, 7), 5), equals(3))
> expect_that(chop2(c(1, 3, 5, 7), 7), equals(4))
> expect_that(chop2(c(1, 3, 5, 7), 0), equals(-1))
> expect_that(chop2(c(1, 3, 5, 7), 2), equals(-1))
> expect_that(chop2(c(1, 3, 5, 7), 4), equals(-1))
> expect_that(chop2(c(1, 3, 5, 7), 6), equals(-1))

Learnings - Method 2

  • This was the method that took an enormous time to code. My mind had forgotten to write recursive code. I was completely left clueless and I struggled for a lot of time before I could get the method working.
  • One of the biggest lesson learnt is that I need to work and code Python algorithms

Method 3

> chop3 <- function(input, token) {
     for (i in seq_along(input)) {
         if (input[i] == token) {
             return(i)
         }
     }
     return(-1)
 }

Testing Method 3

> expect_that(chop3(c(), 3), equals(-1))
> expect_that(chop3(c(1), 3), equals(-1))
> expect_that(chop3(c(1), 1), equals(1))
> expect_that(chop3(c(1, 3, 5), 1), equals(1))
> expect_that(chop3(c(1, 3, 5), 3), equals(2))
> expect_that(chop3(c(1, 3, 5), 5), equals(3))
> expect_that(chop3(c(1, 3, 5), 0), equals(-1))
> expect_that(chop3(c(1, 3, 5), 2), equals(-1))
> expect_that(chop3(c(1, 3, 5), 4), equals(-1))
> expect_that(chop3(c(1, 3, 5), 6), equals(-1))
> expect_that(chop3(c(1, 3, 5, 7), 1), equals(1))
> expect_that(chop3(c(1, 3, 5, 7), 3), equals(2))
> expect_that(chop3(c(1, 3, 5, 7), 5), equals(3))
> expect_that(chop3(c(1, 3, 5, 7), 7), equals(4))
> expect_that(chop3(c(1, 3, 5, 7), 0), equals(-1))
> expect_that(chop3(c(1, 3, 5, 7), 2), equals(-1))
> expect_that(chop3(c(1, 3, 5, 7), 4), equals(-1))
> expect_that(chop3(c(1, 3, 5, 7), 6), equals(-1))
> expect_that(chop3(c(1, 3, 5, 7), 6), equals(-1))

Learnings - Method 3

  • For some reason I ventured to look at the coding that Hadley followed for his reshape package and was really surprised that my coding style was pathetic to say the least. I did not follow any proper coding standards and I was left aghast that after coding 1800 odd hours, my code was like an ugly intestine with no proper reason for whatever was on the screen.
  • I think this codekata is an eye opener for me as it shows that I need to put in an enormous amount of practice hours from now on. Most importantly it should be on a daily basis.
  • It is all a state of mind. I have nothing going on in my mind except the way to code stuff.