>There are three possible edits that can be performed on a

>>59799931
Well its given in the problem that the strings are either one edit away or 0 - that is, identical. So I call strcmp() and if it says the strings are equal, they're 0 edits away, and if it says they're different, they're one edit away.

>>59800105
Doesn't strcmp stop when it reaches a difference? What if chars after that are different too?

>>59800152
Then the string would be more than one edit away, and the problem states that they can only be one or zero edits away.

>>59800177
But you wouldn't know if the chars after the stop were the same or different

Think of it like searching a tree. Each node is the possible action you can take. Each level in the tree uses the tails of the strings from the level above it. Then you can travel down the tree and return the minimum number of edits required to make the tails match.

Or you can think of each string as an n-dimensional vector. Then measure the distance between them.

bool is_one_away(std::string s1, std::string s2) {
    int diff = abs((int)(s1.length() - s2.length()));

    if(diff > 1)
        return false;

    int counts[128] = {0};

    for(int i = 0; i < s1.length(); i++) {
        counts[(int) s1[i]]++;
    }

    for(int i = 0; i < s2.length(); i++) {
        counts[(int) s2[i]]--;
    }

    int sum = 0;

    for(int i = 0; i < 128; i++) {
        sum += abs(counts[i]);
    }

    if(diff == 0) {
        if(sum > 2)
            return false;
    } else {
        if(sum > 1)
            return false;
    }
    
    return true;
}

>>59800177
No it doesn't?

>>59799931
if lengths differ by 2 then different.

if lengths are equal then count how many replaces you need.

if lengths differ by 1 then simply iterate through string and if there is a mismatch then jump over one index and keep comparing.

>>59800105
>>59800177
Wrong

>>59800254
>>59800593
Not valid answers in a whiteboard exam I'm afraid

Pranjeet shall be taking your place

>>59799931
LuL i applied to be Janitor but Okay

>>59799931
Levenshtein function, distance <= 1

>>59800670
> (((Levenshtein)))

>>59800670
Fired

#include<stdio.h>
/* define how your own insert,delete,replace procedure */
int x = 3;
int test(char* testee, char* tester, char chr){
    int fuckyou = 0;
    while( --x >= 0 || (fuckyou = strcmp(testee,tester)) != 0){
        switch(x){
            case 2:
                insert(testee,chr);
                break;
            case 1:
                delete(testee,chr);
                break;
            case 0:
                replace(testee,chr);
                break;
            }
        }
    return fuckyou;
}
int main(int argc, char** argv){
    if(argc!=4)
        return;
    char c = argv[argc-1][0];
    int ret = 0;
    ret = test(argv[1],argv[2],c)||test(argv[2],argv[1],c);
    return ret;
}

>>59799931
Given there are only two possibilities, it's quite simple

if string1 = string2:
  print "0 edits"
else:
  print "1 edit"

>programming

Sorry I seem to have misinterpreted the job description, I thought this was for engineers.

>>59800723
>>59800728
How could you have read the problem this wrong

>>59800670
>>59800681
>>59800691
It's literally CompSci 101.
The following is not my implementation because I'm lazy and I already did it from scratch years ago.

#define MIN3(a, b, c) ((a) < (b) ? ((a) < (c) ? (a) : (c)) : ((b) < (c) ? (b) : (c)))

int levenshtein(char *s1, char *s2) {
    unsigned int x, y, s1len, s2len;
    s1len = strlen(s1);
    s2len = strlen(s2);
    unsigned int matrix[s2len+1][s1len+1];
    matrix[0][0] = 0;
    for (x = 1; x <= s2len; x++)
        matrix[x][0] = matrix[x-1][0] + 1;
    for (y = 1; y <= s1len; y++)
        matrix[0][y] = matrix[0][y-1] + 1;
    for (x = 1; x <= s2len; x++)
        for (y = 1; y <= s1len; y++)
            matrix[x][y] = MIN3(matrix[x-1][y] + 1, matrix[x][y-1] + 1, matrix[x-1][y-1] + (s1[y-1] == s2[x-1] ? 0 : 1));

    return(matrix[s2len][s1len]);
}

printf("The strings are %d edit(s) from each other\n", levenshtein(a,b));

>>59800728
>sorry that should be ==

>>59800734
This is a whiteboard interview, you fuckstick, not a copy paste competition

FIRED

>>59800732
Check my code its correct. It checks if two strings are zero or single edit away from being equal.

>>59800746
I remembered the name of the algorithm instantly without external help and I know where to look it up, in my own personal notes, hand-written.

File: low quality tired frog.jpg (33KB, 575x556px) Image search: [Google]

33KB, 575x556px

Easy. Next.

function edits(a, b){
    return +((a == b)?!a:true)
}

File: 6f624f00e1e175f6ea3a22da6282b30c.jpg (54KB, 300x300px) Image search: [Google]

54KB, 300x300px

>>59799931
what was the question?

bool opIsAFaggot(const std::string &a, const std::string &b)
{
    switch(a.length() - b.length())
    {
    case 0:
        {
            auto m = std::mismatch(b.begin(), b.end(), a.begin());
            return m.first == b.end() || std::equal(m.first + 1, b.end(), m.second + 1);
        }

    case 1:
        {
            auto m = std::mismatch(b.begin(), b.end(), a.begin());
            return m.first == b.end() || std::equal(m.first, b.end(), m.second + 1);
        }

    case -1:
        {
            auto m = std::mismatch(a.begin(), a.end(), b.begin());
            return m.first == a.end() || std::equal(m.first, a.end(), m.second + 1);
        }

    default:
        return false;
    }
}

>>59800760
>There are three possible edits that can be performed on a string.
>1. Insert a char.
>2. Delete a char.
>3. Replace a char.

>if string1 == string2:
> print "0 edits"
>else:
> print "1 edit"

input : abcd abcdef
output: 1 edit

Two edits needed (two inserts of single chars)

>>59800800
>abcd abcdef
output false
>since it requires two edits. either ad 'e' 'f' to string 1 or delete 'e' 'f' to from string 1
YOU ARE DUMB.

>>59800791
I think I read it wrong, so here is the variant that tells you the number of differences, or -1 if it's more than 2.

int opIsAFaggot(const std::string &a, const std::string &b)
{
    switch(a.length() - b.length())
    {
    case 0:
        {
            auto m = std::mismatch(b.begin(), b.end(), a.begin());
            return m.first == b.end() ? 0 : (std::equal(m.first + 1, b.end(), m.second + 1) ? 1 : -1); 
        }

    case 1:
        {
            auto m = std::mismatch(b.begin(), b.end(), a.begin());
            return (m.first == b.end() || std::equal(m.first, b.end(), m.second + 1) ? 1 : -1;
        }

    case -1:
        {
            auto m = std::mismatch(a.begin(), a.end(), b.begin());
            return (m.first == a.end() || std::equal(m.first, a.end(), m.second + 1)) ? 1 : -1;
        }

    default:
        return -1;
    }
}

>>59800847
I mean using

if string1 = string2:
print "0 edits"
else:
print "1 edit"

It will output "1 edit" which is wrong

>>59799931

Enjoy curry stinking up your break room and piles of shit in the parking lot.

File: bossy women.jpg (28KB, 661x542px) Image search: [Google]

28KB, 661x542px

>>59800723
THIS CODE IS CORRECT NOOBS. ^_^

>>59800908
It doesn't even do what the problem asks.

>>59800863
>>59800435
Hired

>>59799931

TL;DR: Do my homework for me, or else I'll fail my CS101 class.

>>59800863
This is just way too confusing

>>59800867
No, it's right, because the problem says we're only given data where the difference is 0 or one character.

>>59800946
So this is how you do it. Will reformat it so it doesn't show up on archive and try it later on.

>>59800732
You are an idiot, or if you're op, you don't know how to write a question.

Based on the question asked above, >>59800728
and >>59800105 or correct.

If they aren't, then learn to English, Pajeet, because that's the question you asked. Seemed fucking stupid, but you asked it.

>>59801142
No it doesn't.

>>59801222
Nowhere does it say this >>59801142

Don't feel like writing it out in full but there's a really simple way to do this.

Will write in shitty pseudocode.

if length(string1) = length(string2):
    if hamming_distance(string1, string2) == 0 or 1:
        return true
elif length(string1) != length(string2):
    look for the lowest index where string1 != string2:
        insert the next index from the longer string:
            if hamming_distance(string1, string2) == 0:
                return true
else return false

>>59801648
If(function that does everything returns true)
return true

Wow really great job dude

Fired

>>59799931
Classic dynamic programming exercise.
Just do the Wagner–Fischer algorithm and check if the result is 1 or 0 or something else.

>>59799931
Did I do it right?

def ed(s1,s2):
    n1,n2 = len(s1),len(s2)
    if n1 > n2:
        n1,s1,n2,s2 = n2,s2,n1,s1
    return 1 >= n2 - n1 + min(sum(s1[j-i] != s2[j] for j in range(i,i+n1)) for i in range(n2-n1+1))

>>59801690
It doesn't return true you fucking moron, it returns the hamming distance.

>>59801726
0 for readability

>>59801234
It doesn't say that the input will only be one or zero edits away, but it also doesn't say what to do in the case that it isn't. If the data is more than one edit away, any answer is vaild.

>>59801234
>determine if they are one or 0 edit away.
this expands to: determine if the strings are one edit away OR determine if the strings are 0 edit(s) away.

You want something different you give me another fucking question mcnulty

>>59800177
>>59800199
maximum recursion depth exceeded

>>59800105
This is the correct answer. Read the question carefully.

>>59801690

def hamming_dist(s1, s2):
    return sum([0 if s1[i] == s2[i] else 1 for i in range(len(s1))])


def edit_dist(s1, s2):
    if len(s1) == len(s2):
        h = hamming_dist(s1,s2)
        if h == 1 or h == 0:
            return True
    elif abs(len(s1) - len(s2)) == 1:
        L = [s1, s2]
        L.sort(key=len)
        totalH = hamming_dist(L[0], L[1][0:-1]) + hamming_dist(L[0], L[1][1:])
        if totalH == len(L[0]) - 1 or totalH == len(L[1]) - 1:
            return True
    else:
        return False

There you go. I actually found kind of a cool property of hamming distances while working on this. The sum of the hamming distances when the shorter string is compared to the front half, and the back half of the longer string, is equal to the length of the shorter string -1 or the length of the longer string -1 iff. 1 a remove exists that will make the strings equivalent.

That's the idea behind the slicing.