Levenshtein Distance

[FriedEgg]

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/

[Ksharp]

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

[Ksharp]

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

It is very upset. :smileyshocked:

[FriedEgg]

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?

[Ksharp]

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

[FriedEgg]

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.

[EC189QRW]

love the way to solve problem in hash. Thanks