BookmarkSubscribeRSS Feed
FriedEgg
SAS Employee

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
Ksharp
Super User

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
Super User

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

It is very upset. :smileyshocked:

FriedEgg
SAS Employee

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?

Ksharp
Super User

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
SAS Employee

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
Obsidian | Level 7

love the way to solve problem in hash. Thanks

Ready to join fellow brilliant minds for the SAS Hackathon?

Build your skills. Make connections. Enjoy creative freedom. Maybe change the world. Registration is now open through August 30th. Visit the SAS Hackathon homepage.

Register today!
How to Concatenate Values

Learn how use the CAT functions in SAS to join values from multiple variables into a single value.

Find more tutorials on the SAS Users YouTube channel.

Click image to register for webinarClick image to register for webinar

Classroom Training Available!

Select SAS Training centers are offering in-person courses. View upcoming courses for:

View all other training opportunities.

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