Code Katas

I discovered a site called Code Wars which I'm going to use to help me learn JavaScript and tighten up my programming in general. So I signed up and played around with one of the Katas on the site.

One of the things I noticed on the site was that you could use Vim or Emacs keys. Cool! So I dutifully started typing into their editor.

A keypress that is handy and almost automatic to me in Vim is CTRL-W. This keypress allows you to quickly delete the previous word. Unfortunately modern window managers and browsers have usurped that keypress to close out the browser window.

Yeah, so it closed out my browser. Don't do that.

(warning: Solution ahead. Stop reading if you want to play with this on your own.)

The kata that I was working on was to find the two lowest sums of an array (assuming the array has positive integers, etc.). In Python it's a pretty simple matter: sort the array and take the two elements off the front of the newly sorted array. Simple.

But they added this caveat: Don't change the original array.

As anyone who has ever done a sort on an array in Python knows, sort is destructive:

>>> foo = [3,5,2,7,8,0,6,2]
>>> foo.sort()
>>> foo
[0, 2, 2, 3, 5, 6, 7, 8]
>>>

(But there's something that I missed and learned. Hint: there's a difference between .sort() and sorted())

It felt like they were expecting me to not sort the array. Hm, that makes things a little more tricky and less Pythonic.

So I got to thinking, put on my BASIC programming language hat and wrote this masterpiece:

def sum_two_smallest_numbers(numbers):
    # Take the first number as the lowest number
    lowest = numbers[0]
    # Set the position of the lowest number
    lowest_position = 0

    for i in range(0, len(numbers)):
        if numbers[i] < lowest:
            lowest = numbers[i]
            lowest_position = i

    second_lowest_position = 0
    # Check for the case where the lowest position is the first number of the
    # array
    if second_lowest_position == lowest_position:
        second_lowest_position = len(numbers) - 1

    second_lowest = numbers[second_lowest_position]

    for i in range(0, len(numbers)):
        if i != lowest_position and numbers[i] < second_lowest:
            second_lowest = numbers[i]
            second_lowest_position = i

    return lowest + second_lowest


def main():
    print sum_two_smallest_numbers([5, 8, 12, 18, 22])

if __name__ == "__main__":
    main()

This code has problems: It's not Pythonic (it's essentially BASIC), it doesn't take advantage of any of the routines that Python gives you, it does two passes of the array.

It's not a great solution, but it works.

What's the first solution that I see?

def sum_two_smallest_numbers(numbers):
    sum(sorted(numbers)[:2])

Much more Pythonic, but does the sort affect the original array?

Turns out there's a difference between .sort() and sorted(). numbers.sort() replaces the original array (which is not what we want), but sorted(numbers) returns the sorted array. Learned something new there.

But is my solution a better solution? At first glance it isn't (lots more code to do something that a simple one-liner of Python handles with ease). Python's sorted() uses TimSort which is O(n) at best and O(n log n) at the average and worst cases. My code takes two passes at the array which is O(n+n) which reduces down to O(n) (if I'm remembering that right).

So my code (inelegant as it is) might be a better solution for larger sets of unordered data. Huh.

What's the lesson here? I'm not entirely sure. Katas are interesting problems and there's a wide variety of solutions on the site for CodeWars. To he honest I thought I had failed when I saw the short, Pythonic solution. But that's the real beauty of learning to code: sometimes the elegant solution isn't the best solution, and sometimes the ham-fisted solution might not be so bad after all.

But the most important lesson of all is that even programmers who think they know what they're doing need to practice and keep learning.


Comments !

links

social