12-12-2011 11:28 AM
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.txt)
Your program should accept as its first argument a string to find the social network of. EX1. time
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.
infile '/temp/input_levenshtein_distance.txt' truncover;
input dword $32.;
length count 8 fw word dword $32;
declare hash d(dataset:'dict');
declare hiter i1('d');
declare hash c(ordered:'a');
declare hiter i2('c');
declare hash o();
do while(not done);
if o.check(key:dword) ne 0 then
if complev(fw,dword)=1 then
put "Social network size for &win is:" n comma8.;
This challenge reposted from: http://www.codeeval.com/open_challenges/58/
12-13-2011 12:38 AM
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.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 */
12-13-2011 10:22 AM
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?
12-14-2011 12:22 AM
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();