7
\$\begingroup\$

According to Alexa rankings, the top 10 websites are:

google.com
youtube.com
facebook.com
baidu.com
yahoo.com
wikipedia.org
amazon.com
twitter.com
qq.com
google.co.in

Being the top 10 visited websites, these are probably also the top 10 misspelled websites [Citation Needed].

Your task

Your goal is to write a program or function that accepts a string containing a misspelled domain name, and outputs all domain names on the top 10 list that are spelled similarly.

Rules

  • Each input may be up to three characters off from a correct website. A changed character may a substitution (cat -> cot), addition (cat -> cant), or removal (cat -> at).
  • Moving a letter counts as two characters changed (the deletion of one character and the addition of another)
  • The input will only include the characters a-z, period, and dash
  • The name of a website does not include the http(s):// or the www. The websites are exactly as listed above.
  • The program must print out all websites that match the input.
  • Case doesn't matter. The test cases will be presented as lower case, but if your program requires upper case, that's fine too.
  • As always, no standard loopholes.
  • This is , so shortest answer in bytes wins!

Some test cases

(Input followed by outputs)

yahoo.com
yahoo.com (no change for correct spelling)

goggle.com
google.com

wikipedia.organ
wikipedia.org

bidua.cm
baidu.com

.om
qq.com

google.co.i
google.com and google.co.in

google.com
google.com and google.co.in

twipper.com
twitter.com

yahoo.org
yahoo.com

amazing.com
amazon.com

factbook.co
facebook.com

ki-pedia.org
wikipedia.org

google.co.india
google.co.in

goo.com
google.com

aol.com
qq.com

qqzon.com
qq.com and amazon.com

Leaderboards

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

# Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

# Ruby, <s>104</s> <s>101</s> 96 bytes

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

# Perl, 43 + 2 (-p flag) = 45 bytes

You can also make the language name a link which will then show up in the leaderboard snippet:

# [><>](http://esolangs.org/wiki/Fish), 121 bytes

var QUESTION_ID=87174,OVERRIDE_USER=41505;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

\$\endgroup\$
  • \$\begingroup\$ I think "outputs the correct version" would be clearer if it said that every possible correct version must be output, as the rules later say. \$\endgroup\$ – xnor Aug 1 '16 at 2:33
  • \$\begingroup\$ @xnor How's this? I also added some corner cases to the test suite. \$\endgroup\$ – Daniel M. Aug 1 '16 at 2:38
  • \$\begingroup\$ Looks good. Are the inputs limited to printable ASCII? In particular, can there be spaces or newlines? \$\endgroup\$ – xnor Aug 1 '16 at 2:52
  • \$\begingroup\$ @xnor Good point; I'll clarify that \$\endgroup\$ – Daniel M. Aug 1 '16 at 2:53
  • \$\begingroup\$ @xnor The input will only include the characters a-z, period, and dash \$\endgroup\$ – Daniel M. Aug 1 '16 at 2:56
6
\$\begingroup\$

Mathematica, 167 166 bytes

Saved one byte thanks to Martin Ender

iSelect[{"google.com","youtube.com","facebook.com","baidu.com","yahoo.com","wikipedia.org","amazon.com","twitter.com","qq.com","google.co.in"},#~EditDistance~i<4&]

Defines a pure function that returns a list of urls.

The is this

This answer uses the same method as my NodeJS answer.

\$\endgroup\$
4
\$\begingroup\$

Nim, 229 205 185 174 bytes

import strutils,sequtils,future
s=>"googlexyoutubexfacebookxbaiduxyahooxwikipedia.org amazonxtwitterxqqxgoogle.co.in".replace("x",".com ").split.filterIt it.editDistance(s)<4

Yep, Nim has a builtin for Levenshtein distance (although it requires an import), which is what the question described.

Defines an anonymous procedure, which must be passed to a testing procedure to be used. An testing program is provided below:

import strutils,sequtils,future
proc test(d: string -> seq[string]) = echo d #[Your input here]#
test(s=>"googlexyoutubexfacebookxbaiduxyahooxwikipedia.org amazonxtwitterxqqxgoogle.co.in".replace("x",".com ").split.filterIt it.editDistance(s)<4)
\$\endgroup\$
  • \$\begingroup\$ Woah, I haven't seen Nim in the wild in a while. That's awesome that it's still an active language. \$\endgroup\$ – Morgan Thrapp Aug 1 '16 at 15:35
  • \$\begingroup\$ @MorganThrapp I just discovered it. It's a good language for golfing (if you can use a lambda), what with the builtins and the number of ways to call a proc. \$\endgroup\$ – Copper Aug 1 '16 at 15:43
  • \$\begingroup\$ Nice! I played around with it a bit last year and really liked it, I never did any golfing with it though. \$\endgroup\$ – Morgan Thrapp Aug 1 '16 at 15:44
3
\$\begingroup\$

JavaScript (ES6), 240 bytes

f=
s=>`google.com,youtube.com,facebook.com,baidu.com,yahoo.com,wikipedia.org,amazon.com,twitter.com,qq.com,google.co.in`.split`,`.filter(t=>[...s].map((u,i)=>(q=p=i+1,w=w.map((v,j)=>p=Math.min(++p,q-(u==t[j]),q=++v))),w=[...[...t].keys()])|p<4)
;
<input oninput=o.textContent=f(this.value).join`\n`><pre id=o>

\$\endgroup\$
2
\$\begingroup\$

NodeJS, 163 161 151 bytes

10 bytes saved thanks to Copper's Nim solution

x=>"google youtube facebook baidu yahoo wikipedia.org,amazon twitter qq google.co.in".replace(/ /g,".com,").split`,`.filter(y=>require("leven")(x,y)<4)

Try it on Tonic

Defines an anonymous function that returns an array of urls.

This solution uses Levenshtein distance, which happens to be exactly what was described by the rules. This answer just selects the urls from an array based on if their Levenshtein distance is small enough.

\$\endgroup\$
2
\$\begingroup\$

Python, 216 200 193 183 bytes

import editdistance as e
i=raw_input()
print[n for n in"googlexyoutubexfacebookxbaiduxyahooxamazonxtwitterxqqxgoogle.co.in wikipedia.org".replace('x','.com ').split()if e.eval(i,n)<4]

The module editdistance calculates the Levenshtein distance, which is the straightforward implementation of what the challenge was asking for.

EDIT: Saved 3 bytes thanks to @shooqie

EDIT 2: Saved another 10 bytes thanks to @shooqie and @Frank

\$\endgroup\$
  • \$\begingroup\$ split() (without the space character) does the same thing (at least in Python 3) \$\endgroup\$ – shooqie Aug 4 '16 at 17:47
  • \$\begingroup\$ @shooqie Yup, that works, thanks. Moving the list inside of the print statement instead of declaring a variable saves a few bytes too. \$\endgroup\$ – Theo Aug 4 '16 at 18:37
  • \$\begingroup\$ You could save a few characters by writing "import editdistance as e" and then calling e.eval rather than writing editdistance again. \$\endgroup\$ – Frank Aug 4 '16 at 18:52
  • \$\begingroup\$ You can remove the space between in and "googlexyoutube..." and split() and if (again, it works in Python 3). Also, in Python 2 you can omit parentheses when calling print \$\endgroup\$ – shooqie Aug 4 '16 at 19:10
  • \$\begingroup\$ One last thing: print [...] -> print[...] and I noticed you're only using i in one place, why not e.eval(raw_input(),n)<4 then? Also, consider using input() instead of raw_input() since you only need a str. \$\endgroup\$ – shooqie Aug 4 '16 at 19:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.