Skip to content

Instantly share code, notes, and snippets.

@joshuaebowling
Last active September 28, 2015 19:33
Show Gist options
  • Save joshuaebowling/e3ef015eb47d1056d761 to your computer and use it in GitHub Desktop.
Save joshuaebowling/e3ef015eb47d1056d761 to your computer and use it in GitHub Desktop.
var indexof, indexofSub;
indexof = function(haystack, needle) {
// Implementation?
var hayLen, isCompleteMatch, needleLen, result, match;
result = -1;
match = '';
hayLen = haystack['length'];
needleLen = needle['length'];
// this is the result when no loops occur
// if both needle and haystack aren't string-typed, return -1
if(typeof haystack !== 'string' || typeof needle !== 'string') {
return -1;
}
// if the needle is bigger than the haystack, it has no index
if(needleLen > hayLen) {
return -1;
}
// if the needle is so small it resides at the beginning
if(needle === '') {
return 0;
}
// at the first letter if they're identical
if(needle === haystack) {
return 0;
}
// controls whether loop will break or continue
isCompleteMatch = false;
// loop to put each needle letter in play
for(var needleCount = 0; needleCount < needleLen; needleCount++) {
// first check to see if our work is done, if so quit procesing
if(isCompleteMatch) break;
var isMatch, needleLetter;
needleLetter = needle[needleCount];
isMatch = false;
// loop to put each haystack letter in play against every needle
for(var hayCount = 0; hayCount < hayLen; hayCount++) {
var hayLetter;
hayLetter = haystack[hayCount];
isMatch = hayLetter === needleLetter;
if(isMatch) {
var needleLeft;
// this sets the loop length for checking for a complete match, since the match has begun
needleLeft = needleLen - needleCount;
// loop to check when a possible match is started
for(var nl = 0; nl < needleLeft; nl++) {
// first check to see if our work is done, if so quit procesing
if(isCompleteMatch) break;
if(needle[needleCount + nl] !== haystack[hayCount + nl]) {
// there's no reason to keep looking, break out of loop
break;
} else {
// there is a reason to keep looking
// push the current letter to the match
match += haystack[hayCount + nl];
// if we have a full match
// and
// we haven't had one so far, then ...
if(match === needle && !isCompleteMatch) {
// set the result and break out
result = hayCount;
// set isCompleteMatch so that we don't run this again and the outer loops will break
isCompleteMatch = true;
break;
}
}
}
} else {
// if its not then we need to reset match
match = '';
}
}
}
return result;
};
indexofSub = function(haystack, needle) {
// Implementation?
var hayLen, matched, needleLen, result, substr;
// this is the result when no loops occur
// if both needle and haystack aren't string-typed, return -1
if(typeof haystack !== 'string' || typeof needle !== 'string') {
return -1;
}
// set the length values since I'll use them at least once
hayLen = haystack['length'];
needleLen = needle['length'];
// if the needle is bigger than the haystack, it has no index
if(needleLen > hayLen) {
return -1;
}
// if the needle is so small it resides at the beginning
if(needle === '') {
return 0;
}
// set the values that the loop results depends on
result = -1;
matched = false;
for(var hc = 0; hc < hayLen; hc++) {
substr = haystack.substr(hc, needle.length);
match = substr === needle;
if(match) {
result = hc;
break;
}
}
return result;
};
function testimplharness(impl) {
console.log('testing impl:');
console.log(impl);
function testimpl(haystack, needle, expected) {
var received = impl(haystack, needle);
var status = (expected === received)
? "PASS"
: "FAIL";
console.log("%s: impl(\"%s\", \"%s\") => %d (expected %d)", status, haystack, needle, received, expected);
return (expected === received);
}
var all_passed = true;
all_passed = (testimpl("hello", "hel" , 0) && all_passed);
all_passed = (testimpl("hello", "hello", 0) && all_passed);
all_passed = (testimpl("foo", "bar" , -1) && all_passed);
all_passed = (testimpl("help", "hello", -1) && all_passed);
all_passed = (testimpl("hel", "hello", -1) && all_passed);
all_passed = (testimpl("foobar", "bar" , 3) && all_passed);
all_passed = (testimpl("foobarbaz", "baz" , 6) && all_passed);
all_passed = (testimpl("raaraa", "raa" , 0) && all_passed);
all_passed = (testimpl("raraa", "raa" , 2) && all_passed);
all_passed = (testimpl("hello", "" , 0) && all_passed);
all_passed = (testimpl("", "" , 0) && all_passed);
all_passed = (testimpl("", "a" , -1) && all_passed);
return all_passed;
};
[indexof, indexofSub].forEach(testimplharness);
@posita
Copy link

posita commented Sep 16, 2015

@joshuaebowling, try these:

(function () {
    function testindexof(haystack, needle, expected) {
        var received = indexof(haystack, needle);
        var status = (expected === received)
            ? "PASS"
            : "FAIL";
        console.log("%s: indexof(\"%s\", \"%s\") => %d (expected %d)", status, haystack, needle, received, expected);

        return (expected === received);
    }

    var all_passed = true;
    all_passed = (testindexof("hello",     "hel"  ,  0) && all_passed);
    all_passed = (testindexof("hello",     "hello",  0) && all_passed);
    all_passed = (testindexof("foo",       "bar"  , -1) && all_passed);
    all_passed = (testindexof("help",      "hello", -1) && all_passed);
    all_passed = (testindexof("hel",       "hello", -1) && all_passed);
    all_passed = (testindexof("foobar",    "bar"  ,  3) && all_passed);
    all_passed = (testindexof("foobarbaz", "baz"  ,  6) && all_passed);
    all_passed = (testindexof("raaraa",    "raa"  ,  0) && all_passed);
    all_passed = (testindexof("raraa",     "raa"  ,  2) && all_passed);
    all_passed = (testindexof("hello",     ""     ,  0) && all_passed);
    all_passed = (testindexof("",          ""     ,  0) && all_passed);
    all_passed = (testindexof("",          "a"    , -1) && all_passed);

    return all_passed;
})();

Can you write an implementation without using String.prototype.split (i.e., without using arrays at all)?

@joshuaebowling
Copy link
Author

@posita, I just saw this. I'm starting it now.

@joshuaebowling
Copy link
Author

@posita, here's the result

PASS: indexof("hello", "hel") => 0 (expected 0)
PASS: indexof("hello", "hello") => 0 (expected 0)
PASS: indexof("foo", "bar") => -1 (expected -1)
PASS: indexof("help", "hello") => -1 (expected -1)
PASS: indexof("hel", "hello") => -1 (expected -1)
PASS: indexof("foobar", "bar") => 3 (expected 3)
PASS: indexof("foobarbaz", "baz") => 6 (expected 6)
PASS: indexof("raaraa", "raa") => 0 (expected 0)
PASS: indexof("raraa", "raa") => 2 (expected 2)
PASS: indexof("hello", "") => 0 (expected 0)
PASS: indexof("", "") => 0 (expected 0)
PASS: indexof("", "a") => -1 (expected -1)

@joshuaebowling
Copy link
Author

@posita,

Below are the results for my last push.

PASS: indexof("hello", "hel") => 0 (expected 0)
PASS: indexof("hello", "hello") => 0 (expected 0)
PASS: indexof("foo", "bar") => -1 (expected -1)
PASS: indexof("help", "hello") => -1 (expected -1)
PASS: indexof("hel", "hello") => -1 (expected -1)
PASS: indexof("foobar", "bar") => 3 (expected 3)
PASS: indexof("foobarbaz", "baz") => 6 (expected 6)
PASS: indexof("raaraa", "raa") => 0 (expected 0)
PASS: indexof("raraa", "raa") => 2 (expected 2)
PASS: indexof("hello", "") => 0 (expected 0)
PASS: indexof("", "") => 0 (expected 0)
PASS: indexof("", "a") => -1 (expected -1)

@posita
Copy link

posita commented Sep 22, 2015

@joshuaebowling, this just tests String.prototype.search, does it not? How about your own indexof implementation? It looks like some of those tests still fail:

function testimplharness(impl) {
    console.log('testing impl:');
    console.log(impl);

    function testimpl(haystack, needle, expected) {
        var received = impl(haystack, needle);
        var status = (expected === received)
            ? "PASS"
            : "FAIL";
        console.log("%s: impl(\"%s\", \"%s\") => %d (expected %d)", status, haystack, needle, received, expected);

        return (expected === received);
    }

    var all_passed = true;
    all_passed = (testimpl("hello",     "hel"  ,  0) && all_passed);
    all_passed = (testimpl("hello",     "hello",  0) && all_passed);
    all_passed = (testimpl("foo",       "bar"  , -1) && all_passed);
    all_passed = (testimpl("help",      "hello", -1) && all_passed);
    all_passed = (testimpl("hel",       "hello", -1) && all_passed);
    all_passed = (testimpl("foobar",    "bar"  ,  3) && all_passed);
    all_passed = (testimpl("foobarbaz", "baz"  ,  6) && all_passed);
    all_passed = (testimpl("raaraa",    "raa"  ,  0) && all_passed);
    all_passed = (testimpl("raraa",     "raa"  ,  2) && all_passed);
    all_passed = (testimpl("hello",     ""     ,  0) && all_passed);
    all_passed = (testimpl("",          ""     ,  0) && all_passed);
    all_passed = (testimpl("",          "a"    , -1) && all_passed);

    return all_passed;
}

testimplharness(indexof);
false
testing impl:
function indexof()
PASS: impl("hello", "hel") => 0 (expected 0)
PASS: impl("hello", "hello") => 0 (expected 0)
PASS: impl("foo", "bar") => -1 (expected -1)
PASS: impl("help", "hello") => -1 (expected -1)
PASS: impl("hel", "hello") => -1 (expected -1)
PASS: impl("foobar", "bar") => 3 (expected 3)
PASS: impl("foobarbaz", "baz") => 6 (expected 6)
PASS: impl("raaraa", "raa") => 0 (expected 0)
FAIL: impl("raraa", "raa") => 3 (expected 2)
FAIL: impl("hello", "") => -1 (expected 0)
FAIL: impl("", "") => -1 (expected 0)
PASS: impl("", "a") => -1 (expected -1)

@joshuaebowling
Copy link
Author

@posita,
It looks like I may have given you the impression that I had worked out the issue with my first attempt. But I haven't done that. I can rewrite the this attempt to pass these tests if you would like?

The reason I've come to this condsion is this line in your response:
testimplharness(indexof); where indexof was the name assigned to my first attempt.

@posita
Copy link

posita commented Sep 22, 2015

@posita,
It looks like I may have given you the impression that I had worked out the issue with my first attempt. But I haven't done that. I can rewrite the this attempt to pass these tests if you would like?

@joshuaebowling, that would be ideal. Thanks! My apologies for tweaking the test harness on you.

@joshuaebowling
Copy link
Author

@posita,
Are you saying that the function named indexofNoSplit:

  1. should be renamed to indexof for the requirement to be fulfilled?
  2. should not be used as an answer?
  3. should be used as an answer along with another answer using the test harness for each?

Please don't apologize, I'll integrate into the gist.
Thanks so much for your responses.

@posita
Copy link

posita commented Sep 22, 2015

No. 2 is correct for your current implementation. Alternately, you can pretend that, in our "perverse" (make-believe) environment, neither String.prototype.indexOf nor String.prototype.search exist.

When I previously asked:

Can you write an implementation without using String.prototype.split (i.e., without using arrays at all)?

What I meant was:

Can you write an implementation without using String.prototype.split (i.e., without using arrays at all) _and without calling String.prototype.indexOf, String.prototype.search, Array.prototype.indexOf, Array.prototype.find, etc._?

In other words, I'd like see how you handle the low-level iteration, state management, etc. Your stab at indexof was a good start (exactly the kind if direction I was looking for). What I'd like to see is a similar approach, just without calling String.prototype.split.

Please let me know if this makes sense.

@joshuaebowling
Copy link
Author

@posita,
I've implemented a solution that conforms to your above description. Here are the results from my tests.
testing impl:
[Function]
PASS: impl("hello", "hel") => 0 (expected 0)
PASS: impl("hello", "hello") => 0 (expected 0)
PASS: impl("foo", "bar") => -1 (expected -1)
PASS: impl("help", "hello") => -1 (expected -1)
PASS: impl("hel", "hello") => -1 (expected -1)
PASS: impl("foobar", "bar") => 3 (expected 3)
PASS: impl("foobarbaz", "baz") => 6 (expected 6)
PASS: impl("raaraa", "raa") => 0 (expected 0)
PASS: impl("raraa", "raa") => 2 (expected 2)
PASS: impl("hello", "") => 0 (expected 0)
PASS: impl("", "") => 0 (expected 0)
PASS: impl("", "a") => -1 (expected -1)

@posita
Copy link

posita commented Sep 23, 2015

@joshuaebowling, Thanks for the update. I have a couple questions based on your latest solution:

  1. What is the efficiency ("big-O") of your approach? Can you make it more efficient?

  2. In your current solution, is the following (from line 20) necessary, given the subsequent loop?

        // at the first letter if they're identical
        if(needle === haystack) {
            return 0;
        }
  3. If a match exists, but where needle does not exactly match haystack, what are the performance implications of the above comparison?

  4. Does bracket notation [] work with String types? What is the result in different browsers/environments?

@joshuaebowling
Copy link
Author

@posita,
Please find my responses to your questions below:

  1. What is the efficiency ("big-O") of your approach? Can you make it more efficient?

    • I believe it's O(N * (N-1) * (N-2)) or O(N3) depending on desired precision, where N is maximum length of a String in given environment/browser, but I'm not certain of notation here.
    • I'll look into it and push any new implementations. I suspect I may be able to cut out one of those loops. Also, I suspect there may be other ways entirely of accomplishing this altogether.
  2. In your current solution, is the following (from line 20) necessary, given the subsequent loop?

    // at the first letter if they're identical
    if(needle === haystack) {
        return 0;
    }
    • No it isn't necessary in the sense that the result of indexof would be same without this block of code, per the tests. My understanding is that doing a strict equality comparison here, ahead of running the loops, would cut down on processing time should needle and haystack turn out to be strictly equivalent.
  3. If a match exists, but where needle does not exactly match haystack, what are the performance implications of the above comparison?

    • I'm not perfectly certain of what you mean by "where needle does not exactly match haystack", so I'm interpreting your question as having to do with these variables being type mismatched. If haystack and needle do not match in type, then the for loops will run, potentially missing some of the performance gains of avoiding the loops where possible; however, this would only be relevant if haystack and needle had the same value, but were different types (for example, haystack = 'test'; and needle = ['test'];). Incidentally, if the variables were set to these values, then the for loop wouldn't return a result that would satisfy each test, as both variables need to be String typed. Thus, I observed that doing type checks on both needle and haystack could boost performance and I have implemented this change.
  4. Does bracket notation [] work with String types? What is the result in different browsers/environments?

    • To my knowledge, it works in all environments except Internet Explorer 7.

@joshuaebowling
Copy link
Author

@posita,
I wrote another implementation forsaking two of the loops, I used String.prototype.substr to do this. I'm not sure whether this would be a higher-level function or not vis-a-vis these exercises, but I can state that my code still has to "look for" the match. Thus, this solution has the feeling of extending indexOf functionality from substr, so it would seem that substr is lower level than indexOf, search, etc.

Also, I updated the invocation of the test harness so both implementations are tested.

Here are my results:
testing impl:
[Function]
PASS: impl("hello", "hel") => 0 (expected 0)
PASS: impl("hello", "hello") => 0 (expected 0)
PASS: impl("foo", "bar") => -1 (expected -1)
PASS: impl("help", "hello") => -1 (expected -1)
PASS: impl("hel", "hello") => -1 (expected -1)
PASS: impl("foobar", "bar") => 3 (expected 3)
PASS: impl("foobarbaz", "baz") => 6 (expected 6)
PASS: impl("raaraa", "raa") => 0 (expected 0)
PASS: impl("raraa", "raa") => 2 (expected 2)
PASS: impl("hello", "") => 0 (expected 0)
PASS: impl("", "") => 0 (expected 0)
PASS: impl("", "a") => -1 (expected -1)
testing impl:
[Function]
PASS: impl("hello", "hel") => 0 (expected 0)
PASS: impl("hello", "hello") => 0 (expected 0)
PASS: impl("foo", "bar") => -1 (expected -1)
PASS: impl("help", "hello") => -1 (expected -1)
PASS: impl("hel", "hello") => -1 (expected -1)
PASS: impl("foobar", "bar") => 3 (expected 3)
PASS: impl("foobarbaz", "baz") => 6 (expected 6)
PASS: impl("raaraa", "raa") => 0 (expected 0)
PASS: impl("raraa", "raa") => 2 (expected 2)
PASS: impl("hello", "") => 0 (expected 0)
PASS: impl("", "") => 0 (expected 0)
PASS: impl("", "a") => -1 (expected -1)

@posita
Copy link

posita commented Sep 28, 2015

@joshuaebowling, substr is okay. Let's hope the VM has some memory copying optimizations to create the sub-strings. Also, be aware that you've probably introduced an implicit loop for the comparison (substr === needle).

I would have preferred to see a two-loop solution using brackets [] or charAt, but this works. 👍

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment