BookmarkSubscribeRSS Feed
SAS Employee

Levenshtein Distance

Levenshtein Distance

Description:

Two words are friends if they have a Levenshtein distance of 1 (For details see http://en.wikipedia.org/wiki/Levenshtein_distance). That is, you can add, remove, or substitute exactly one letter in word X to create word Y. A word’s social network consists of all of its friends, plus all of their friends, and all of their friends’ friends, and so on. Write a program to tell us how big the social network for the word 'hello' is, using this word list attached (input_kevenshtein_dstance[1].txt)

Input sample:

Your program should accept as its first argument a string to find the social network of.  EX1. time

Output sample:

Print out how big the social network for the word 'hello' is. e.g. The social network for the words 'causes' and 'abcde' is 7630 and 7632 respectively.

Below is my solution.  I would not consider it to be efficient, it is just my first try, it works but needs rethinking.

%let input=causes;

%let win=%sysfunc(lowcase(%sysfunc(compress(&input,,p))));

data dict;

infile '/temp/input_levenshtein_distance[1].txt' truncover;

input dword \$32.;

run;

data _null_;

length count 8 fw word dword \$32;

declare hash d(dataset:'dict');

d.definekey('dword');

d.definedata('dword');

d.definedone();

declare hiter i1('d');

declare hash c(ordered:'a');

c.definekey('count');

c.definedata('word');

c.definedone();

c.add(key:1,data:"&win");

declare hiter i2('c');

declare hash o();

o.definekey('word');

o.definedata('word');

o.definedone();

o.add(key:"&win",data:"&win");

i2.first();

done=0;

n=1;

do while(not done);

fw=word;

i1.first();

do while(i1.next()=0);

if o.check(key:dword) ne 0 then

do;

if complev(fw,dword)=1 then

do;

n+1;

c.add(key:n,data:dword);

o.add(key:dword,data:dword);

end;

end;

end;

done=i2.next();

end;

put "Social network size for &win is:" n comma8.;

run;

This challenge reposted from: http://www.codeeval.com/open_challenges/58/

6 REPLIES 6
Super User

Levenshtein Distance

It is very interesting. Which remind me a Question posted by sas_Form which attracted lots of eyes.

This is very like sas_Form's.

BTW. I like the website : https://www.codeeval.com/

```%let word=causes;

data dic;
infile 'c:\input_levenshtein_distance[1].txt';
input word \$40.;
run;
data _null_;
if 0 then set dic;
declare hash ha(hashexp:20,dataset:'dic');
declare hiter hi('ha');
ha.definekey('word');
ha.definedata('word');
ha.definedone();

length _word k \$ 40 obs 8;
declare hash _ha(ordered:'Y');
declare hiter _hi('_ha');
_ha.definekey('obs');
_ha.definedata('_word');
_ha.definedone();
obs=1;_word="&word";_ha.add();

rc=_hi.first();
do while(rc=0);
rcc=hi.first();
do while(rcc=0);
if complev(word,_word)=1 then do; k=word;obs+1; _ha.add(key:obs,data:word);found=1;end;
rcc=hi.next();
if found then do;rx=ha.remove(key:k);found=0;end;
end;
rc=_hi.next();
end;
putlog "The social network for the words &word is "  obs ;
stop;
run;

/*  2168  */

```

Ksharp

Super User

Levenshtein Distance

I can't register at https://www.codeeval.com/.

It is very upset. :smileyshocked:

SAS Employee

Levenshtein Distance

Yes, it is technically a job posting site for companies in the U.S.

Thanks for your reply.  One thing I do not understand is that whenever I try to use the remove() method on a hash object which I have designated a iterator object it does not work.  I need to double check what my issue was.  Maybe I was trying to call remove on the iterator object itself and not the originating hash?

Super User

Levenshtein Distance

Hash iteration Object has such remove method. Only Hash Table Object itself has.

You can't remove the current item in Hash Table, You need hi.next() to make pointer to move to next item ,then delete it. Of course . Don't forget use return code:  rc=ha.remove();

Ksharp

SAS Employee

Levenshtein Distance

I looked back at my code, I was accidently trying to call remove method on hiter object, not the originating hash object.  Dumb mistake to not have caught.

Obsidian | Level 7

Re: Levenshtein Distance

love the way to solve problem in hash. Thanks

Discussion stats
• 6 replies
• 3597 views
• 1 like
• 3 in conversation