The StackOverflow community rocks!

Recently I stumbled upon a site called HackerRank. Before I go into why this relates to StackOverflow I want to briefly explain HackerRank. HackerRank is a site where you are challenged to solve a problem in pretty much any language you want. You have to take a program that gets an input and gives a desired output based on a problem. The site will then run your code against some test cases and determine if your code passes that problem.

HackerRank gets very addictive quickly. The problems start off easy such as add two numbers to get you used to how it all works but they ramp up pretty fast.

For a while now I’ve had a passing interest in F#. I’ve used the language to solve Project Euler problems in that past. HackerRank in my view is a better Project Euler the reason I think this is because with the Project Euler problems many of them can be brute forced on today’s hardware. Meaning you can solve them in a way that the author didn’t quite intend. The other issue with some of the problems is they are deep in maths. So deep in maths that I sometimes needed to spend quite a bit of time reading up on advanced algebra just to get to the point where I could start the problem. As much as I enjoyed this it detracted from the problem solving. Anyway I digress, I decided that HackerRank would be an excellent way to learn F#.

I was trying to write a function allIndexOf that takes two strings and returns a list of integers of the first positions of all of the occurrences of the second string in the first string. I couldn’t get my function to compile in F# so I posted this question on StackOverflow. Within 2 minutes someone had posted the answer that I missing a set of parentheses due to the way that F# binds it’s function arguments. Now is cool that you can get an answer within 2 minutes. What was even more amazing and blew me away was that someone then in the comments took the time to point out a bug in my function.

Here is my original function see if you can spot the bug:

let allIndexOf (str:string) (c:string) =
    let rec inner (s:string) l =
        match (s.IndexOf(c), (s.IndexOf(c)+1) = s.Length) with
        | (-1, _) -> l
        | (x, true) -> x::l
        | (x, false) -> inner(s.Substring(x+1) x::l)
    inner str []

Not only that but they made this F# Fiddle showing my function with some inputs and why it was wrong and also giving 3 ways to do the function. Using comprehension, recursion with an accumulator and recursion with a continuation.

The bug was that during the recursive call to “inner” if it matched then the value that x would be bound to would not be the index of the next occurrence of the string in the original string but the truncated string. To fix this in my version of the code I just needed to pass along the amount of string that was missing so this could be added on to x.

Fixed code:

let allIndexOf (str:string) (c:string) =
    let rec inner (s:string) l offset =
        match (s.IndexOf(c), (s.IndexOf(c)+1) = s.Length) with
        | (-1, _) -> l
        | (x, true) -> (x+offset)::l
        | (x, false) -> inner(s.Substring(x+1)) ((x+offset)::l) (x+1)
    inner str [] 0

Now this code is actually inefficient due to the fact I am creating a new string upon each recursive call. This is something Sehnsucht points out on StackOverlow. I think it says a lot about the dev community that people are willing to firstly give up their time to answer your questions but also that they will go the extra mile to point out where you are going wrong and how you can improve.

If you have some spare time why not get on StackOverflow and pay it back…

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s