# Find imperfect anagrams

The goal of this challenge is to write a program which takes a string (of any length) as input and displays anagrams (see these examples of anagrams) of this string, made by taking words in a dictionary (either individually or in pairs), but the anagrams don't need to be perfect.

An anagram is the result of a rearrangement of a set of characters:

• ABCD and CADB are perfect anagrams, all the characters are present in both strings
• ABCD and CADBEF are imperfect anagrams because the characters ABCD are present in both strings but the characters EF only exist in the second string

The dictionary contains 1949 words:

ability
able
aboard
etc.


By taking each word and each pair of distinct words we generate a list of candidates to compare against the input:

ability
ability able
ability aboard
ability ...
able
able aboard
able ...
...


The program must display only the strings from the previous list which are anagrams of the input string. In other words, the program needs to filter the candidates down to the imperfect anagrams of the input.

# Examples

## Input

Sample:

> your_program 85 "Meta Code Golf" ./dict.txt


You may take input from any method you like, be it command line arguments or stdin.

## Expected output

ExCLAiMED FOOT
FrEEDOM LOCATe


(if I didn't make any mistake in my code)

# Rules

## Input:

n string filepath


(You may take input from any method you like, be it command line arguments or stdin)

• The first input will be an integer n. This is a threshold to define the minimum percentage of characters which must be present in the string input and the anagrams. n will be between 0 and 100, inclusive
• The second input will be a string (a string with one or more words)
• The path to a file containing one word per line. The dictionary to use is available here (**), it contains 1949 common words (source). You have to save this file without the comments to keep one word per line

**: I chose to use only 1949 common words because the dictionaries like wamerican package (with Ubuntu it adds the /usr/share/dict/american-english file) contains about 100,000 words, this would lead to 10,000,000,000 possible combinations of 2 words. It may take to much time to compute in the context of code golfing. But a program which works with 2,000 words may still work with 100,000 words if someone wants to use all the words from a complete dictionary.

## Output:

• One matching anagram string per line. The matching letters between the input string and the anagram must be displayed in uppercase, and the non-matching letters must be lowercase. In the example, only 2 of the 3 e are in uppercase, because there are only 2 e in Meta Code Golf
• You must not display the same anagram twice (eg. ExCLAiMED FOOT and FOOT ExCLAiMED are both valid but they are only the result of a swap between the 2 words)

## Other rules:

• Comparison between input string and anagrams:
• Lower and upper-case characters are considered as the same character when searching the anagrams
• Non-letter characters (space), -, etc. are considered as one character
• Standard “loopholes” are forbidden
• Shortest code wins

# Similarity index and threshold

## Similarity index:

The similarity index (SI) is calculated by counting the number of times each character from a string appear in another string. So we have to compute 2 SIs if the 2 strings have different lengths.

### Examples

ABCD and CADB are perfect anagrams, the characters are identical, the SI is 100%

ABCD and CADBEF: - ABCD in CADBEF: the SI is 100% because all the characters of the first string exist in the second string - CADBEF in ABCD: the SI is 4/6 because ABCD are present in the second string (and not E and F)

You have to ensure that you compare the input with the word and the word with the input, otherwise the word AAABBBCCCDDDEEE (etc.) may match the vast majority of the words. So we have to check that the 2 SIs are greater or equal than the threshold in order to accept an anagram.

### Example of SI function (pseudo-code):

function SI(a, b) {
s_i = 0

foreach (character in a) {
if (character exists in b) {
remove the character in b /* avoid to find several times "AAAA" in "A" */
s_i++
}
}

return(s_i / length(a))
}


## Threshold

The threshold acts as a filter to display only the anagrams which SI is greater or equal than the threshold.

To apply the threshold, we must use this function twice:

if ((SI(input, candidate) >= threshold) && (SI(candidate, input) >= threshold)) {/* anagram is ok */}


### Examples:

Threshold = 100

> program 100 "explanation" ./dict.txt
EXPLANATION


There is only one result because there is no perfect anagram for Explanation, except the word itself.

Threshold = 90

> program 90 "explanation" ./dict.txt
ALONE PAINT
EXPLAIN NOT
EXPLANATION
NATION PALE


Threshold = 75

> program 75 "explanation" ./dict.txt
AbLE cONTAIN
AbLE NATION
AcT EXPLAIN
AcTION ALoNE
AcTION ANgLE
...


Threshold = 0

> program 0 "Meta Code Golf" ./dict.txt
AbILiTy
AbILiTy AblE
AbILiTy AbOard
...


It will display all the words and all the combination of words from the dictionary (because all the SIs are greater or equal than the threshold).

## Random example

> program 85 "Beyonce Knowles" ./dict.txt
BEtWEEN COLONY
COWBOY SENtENcE


I was inspired by a french TV program named Le Complot where they make funny correlations between two unrelated persons, ideas, etc. For example, they showed that the soccer player Pastore is an anagram of Apotres (the french word for Apostles) in order to link Zlatan Ibrahimovic to Catholic Church.

• Is it just me or even after reading the whole question, I am unsure of what the question is asking ? :| – Optimizer Oct 25 '14 at 16:15
• @Optimizer: the question is about creating a program to find fuzzy anagrams of an input string in a dictionary file. – A.L Oct 25 '14 at 16:17
• The explanation of what the percentage match means seems to assume that the original and the value being compared are the same length, but that's not the case in the examples. What precisely is the test? – Peter Taylor Oct 25 '14 at 16:54
• Seems like the threshold needs to be clarified more. – chilemagic Oct 25 '14 at 16:57
• IIRC, I had a function which count characters in common, I had to use it on input vs compared string, and compared vs input string then check if the 2 results were both greater than the threshold. – A.L Oct 25 '14 at 17:08

# Perl 5 - 166 158 146 143

4 of the new line characters are added for clarity (those following a semicolon).

$s.=lc"+s/$_/uc$&/e"for(i=pop)=~/[a-z]| (?!.* )/ig; /=pop; _=<>; s!.+!"&".join" & ",'=~/^|.+/g!ge; 100*evals</*length(_|i)||print"_ "for split' '  The array based candidate generation actually proved to be shorter than my original string substitution one. Kept the previous 153 version as its output order is exactly as in the examples (though it is not required). s.=lc"+s/_/uc$&/e"for($i=pop)=~/[a-z]| (?!.* )/ig;$z=pop;
100*eval$s<$z*length($_|$i)||print"$_ "for map{map$&." $_"x!/^$&\$/,@s=(@s,/.+/g)}<>


Usage:

perl ./a.pl 90 "explanation" <dict.txt


## Edit

This version should conform to the specification with regard to non letter characters.

• I tested it successfully, you win! Is there a reason it uses so much space (up to 400 MB)? – A.L Oct 31 '14 at 23:21

# Python 2, 375 ... 313

S=lambda a,b:1.*len([b.remove(q)for q in a if q in b])/len(a)
T=lambda a,b:min(S(a,b[:]),S(b,a[:]))
t,s,d=input()
for x in{' '.join(sorted([a,b]))for a in d for b in d}|set(d):
q=list(s.lower())
if T(list(x),q)*100>=t:print''.join([w,w.upper()][q.count(w)and not q.remove(w)]for w in x)


This expects slightly different input; like so: 90, "explanation", "dict.txt". If that's not allowed, I'll fix it.

Sample run, with stdin 90, "explanation", "dict.txt":

EXPLANATION
NATION PALE
EXPLAIN NOT
ALONE PAINT


This works by iterating through a set of all the possibilities, checking them. This is what makes it so slow.

S=lambda a,b:1.*len([b.remove(q)for q in a if q in b])/len(a) # define the SI function
lambda a,b:                                                 # define a lambda with 2 inputs
b.remove(q)for q in a if q in b          # for q in a, if q is in b, remove q from b
len([                               ])        # list.remove returns None, so collect all the removes and the resulting list will have len of the number of times we removed things
1.*len([b.remove(q)for q in a if q in b])/len(a) # 1.* converts the len to a float, so that when we divide by len(a), we get a float

T=lambda a,b:min(S(a,b[:]),S(b,a[:])) # Determine the min SI for both possibilities
S(a,b[:]),           # run S with a and a copy of b; since b gets removes called in S
S(b,a[:])  # run S with b and a copy of a
min(S(a,b[:]),S(b,a[:])) # get the min of those values

t,s,d=input()
d=open(d).read().split() # read the dict file and split it on newlines, creating a list of words

for x in{' '.join(sorted([a,b]))for a in d for b in d}|set(d): # iterate over possible word choices
[a,b]  for a in d for b in d          # create all possible pairs of words
sorted(     )                                # sort the list, making it so that ['exclaimed', 'foot'] and ['foot', 'exclaimed'] make the same element
' '.join(             )                               # combine the words with a space between
{                                            }         # turn into set; this is a set comprehension
|set(d)  # take the union of that set and the set of single words.
for x in                                                     : # this is what we iterate over

q=list(s.lower()) # we want to convert our string to lowercase, but we also want it as a list of characters because str doesn't have a remove function.

if T(list(x),q)*100>=t: # decide if the element of the set matches the threshold
print''.join([w,w.upper()][q.count(w)and not q.remove(w)]for w in x) # it does; now we print the correct output
[w,w.upper()]                               for w in x) # consider both the lower/uppercase versions of the char in the string
[q.count(w)and not q.remove(w)]            # if w appears at least once in the target string, we remove it from the target string, and do a logical negation on the None, resulting in True ie 1, so we choose uppercase
''.join(                                                      ) # join these elements back into a string
print                                                                # print the result

• Do you use a round function for the threshold? 90% * 11 = 9,9. So 10 characters must be present in input and anagram, so you can change only one letter. Did you count the space as a character? For example in EXPLAIN TOrN you have 2 differences: space and r. – A.L Oct 26 '14 at 20:46
• @A.L That might be my problem; I was under the impression spaces were to be stripped before putting it into the SI. – Justin Oct 26 '14 at 20:47
• Is there a reason the results are displayed in descending order? I didn't mentioned in the rule so it's OK but I'm just wondering. – A.L Oct 26 '14 at 20:53
• @A.L Yes, although descending is coincidence; it could easily be in any order. I specifically didn't put it any order. This happens because I'm using Python's set, which is unordered, meaning ordered according to a hash. – Justin Oct 26 '14 at 20:54
• I can actually think of a (probably, definitely with big dictionaries) much more time-efficient method of doing this: start with the string we want to make, and generate all close anagrams, then check to see if each word in each close anagram is in the dictionary. – Justin Oct 27 '14 at 5:47

# Python 3 - 447

Again, this is one of these programs that takes a long time to test, but I'll add one of the test cases once it's done.

from sys import*
l=argv
e=''
t=[]
v=list
n='\n'
def s(a,b):
m=0;a=list(a)
for i in a:
if i in b:b.remove(i);m+=1
return m/len(a)*100
for i in g.split(n):
for j in(n+g).split(n):
a=i+' '+j if j!=''else i
b=l[2].lower();c='';d=v(b);w=set(b.split(' '))
t=l[1]
if(s(a,d)>=t)and(s(d,v(a))>=t):
if not w in t:
for k in a:
if k in d:d.remove(k);c+=k.upper()
else:c+=k
t.append(w)
e+=c+n
print(e)


## Edit

The latest edit accounts for the rule that states that you must not print different arrangements of the two words.

# R - 512 (= 29!)

v=function(a){unlist(strsplit(tolower(a),""))}
s=function(a,b){
s=0;for(l in a){if(l%in%b){b=b[-(which(l==b)[1])];s=(s+1)}};s/length(a)}
r=function(v,j){p=c();for(l in v){if(l%in%j){j=j[-(which(l==j)[1])]
o=toupper(l)}else{o=tolower(l)};p=c(p,o)};cat(p,"\n",sep="")}
a=commandArgs(T);j=v(a[2]);k=(as.integer(a[1])/100);
d=scan(a[3],what='raw',sep="\n",quiet=T);
for(w in d){t=v(w);if((s(t,j)>=k)&&(s(j,t)>=k)){r(t,j)};
for(x in d[-1]){w2=paste(w,x,sep=" ");t=v(w2)
if((s(t,j)>=k)&&(s(j,t)>=k)){r(t,j)}};d=d[-1]}


## Ungolfed

get_array = function (a) {unlist(strsplit(tolower(a),""))}

# calculate similarity index of 2 strings
get_s = function (a, b) {
s = 0
for (letter in a) {
if (letter %in% b) {
b = b[-(which(letter == b)[1])]
s = (s + 1)
}
}
return(s / length(a))
}

# output
get_result = function (var_string, input) {
output = c()

for (letter in var_string) {
if (letter %in% input) {
input = input[-(which(letter == input)[1])]
o = toupper(letter)
}
else
{
o = tolower(letter)
}
output = c(output, o)
}
cat(o, "\n",sep="")
}

# get arguments
a = commandArgs(T)
input = get_array(a[2])
threshold = (as.integer(a[1]) / 100)
dict = scan(a[3], what='raw', sep="\n", quiet=T)

# iterate through all the words from the dictionary
for (w in dict)
{
t = get_array(w)

# the word only
if (
(get_s(t, input) >= threshold)
&&
(get_s(input, t) >= threshold)
)
{
get_result(t, input)
}

# the word + another word
for (x in dict[-1]) {
w2 = paste(w, x, sep=" ")
t = get_array(w2)
if (
(get_s(t, input) >= threshold)
&&
(get_s(input, t) >= threshold)
)
{
get_result(t, input)
}
}

dict = dict[-1] # remove the word once it has be permuted with all the other words
}