DATA Step, Macro, Functions and more

Levenshtein Distance

Reply
Trusted Advisor
Posts: 1,300

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/


Attachment
Super User
Posts: 9,691

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
Posts: 9,691

Levenshtein Distance

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

It is very upset. :smileyshocked:

Trusted Advisor
Posts: 1,300

Levenshtein Distance

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

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
Posts: 9,691

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

Trusted Advisor
Posts: 1,300

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.

Ask a Question
Discussion stats
  • 5 replies
  • 1307 views
  • 0 likes
  • 2 in conversation