23
\$\begingroup\$

Monday Mini-Golf: A series of short challenges, posted (hopefully!) every Monday.
(Sorry this one's a little late.)

I'm sure most of you folks have heard of Levenshtein distance, an algorithm for calculating the distance between two strings. Well, this challenge is about implementing a similar algorithm of my own invention*, called anagram distance. The main difference is that the order of the characters doesn't matter; instead, only the characters that are unique to one string or the other are measured.

Challenge

The goal of the challenge is to write a program or function that takes in two strings and returns the anagram distance between them. The main way to do this is to use the following logic:

  1. Convert both strings to lowercase and (optionally) sort each one's characters alphabetically.
  2. While the strings contain at least one equal character, remove the first instance of this character from each string.
  3. Add the lengths of the remaining strings and return/output the result.

Example

If the inputs are:

Hello, world!
Code golf!

Then, lowercased and sorted, these become: (by JS's default sort; note the leading spaces)

 !,dehllloorw
 !cdefgloo

Removing all of the characters that are in both strings, we end up with:

,hllrw
cfg

Thus, the anagram distance between the original two strings = 6 + 3 = 9.

Details

  • The strings may be taken in any sensible format.
  • The strings will consist only of printable ASCII.
  • The strings themselves will not contain any whitespace other than regular spaces. (No tabs, newlines, etc.)
  • You need not use this exact algorithm, as long as the results are the same.

Test-cases

Input 1:

Hello, world!
Code golf!

Output 1:

9

Input 2:

12345 This is some text.
.txet emos si sihT 54321

Output 2:

0

Input 3:

All unique characters here!
Bdfgjkmopvwxyz?

Output 3:

42

Input 4:

This is not exactly like Levenshtein distance,
but you'll notice it is quite similar.

Output 4:

30

Input 5:

all lowercase.
ALL UPPERCASE!

Output 5:

8

Scoring

This is , so shortest valid code in bytes wins. Tiebreaker goes to submission that reached its final byte count first. The winner will be chosen next Monday, Oct 12. Good luck!

Edit: Congrats to the winner, @isaacg, using Pyth (again) for an astounding 12 bytes!

*If this algorithm has been used elsewhere and/or given another name, please let me know! I wasn't able to find it with a 20-minute search.

\$\endgroup\$
4
  • \$\begingroup\$ Describing the task as “write a program […] that [does stuff] using the following logic” to later add “You need not use this exact algorithm […]” is a tad contradictory. \$\endgroup\$
    – Édouard
    Oct 8, 2015 at 3:59
  • \$\begingroup\$ @Édouard True; thanks for pointing that out. I believe it's better now. \$\endgroup\$ Oct 8, 2015 at 13:04
  • \$\begingroup\$ It's already Tuesday again. ;) \$\endgroup\$ Oct 13, 2015 at 13:13
  • \$\begingroup\$ @MartinBüttner It's kinda hard to write a challenge while you're on the road without wi-fi. ;) Don't worry, I'll have a new one ready in a little bit. \$\endgroup\$ Oct 13, 2015 at 13:37

16 Answers 16

13
\$\begingroup\$

Pyth, 12 bytes

ls.-M.prR0.z

Test suite

The operation in question is equivalent to Pyth's bagwise subtraction operator, .-, applied in both directions. You could call it bagwise xor, I suppose.

The solution is:

.z: get input as list of 2 strings.

rR0: convert both to lowercase.

.p: Form all permutations, i.e. normal and reversed.

.-M: Map the .- operation over each ordering.

s: Concatenate the results.

l: Print the length.

\$\endgroup\$
1
  • \$\begingroup\$ And I thought all answers might be overly long.... Well done! \$\endgroup\$ Oct 7, 2015 at 1:48
8
\$\begingroup\$

JavaScript (ES7), 92 bytes

Defines an anonymous function.

To test, run the snippet below. You can edit the code and click 'Test' to compare its output with the original. (Leave a comment if you find an improvement!) Input is like "Hello, world!", "Code golf!" in the input box.

Thanks to @ETHproductions for saving 6 bytes!


(a,b)=>[for(v of a[t="toLowerCase"]())if((b=b[t]())==(b=b.replace(v,"")))v][l="length"]+b[l]
<!--                               Try the test suite below!                              --><strong id="bytecount" style="display:inline; font-size:32px; font-family:Helvetica"></strong><strong id="bytediff" style="display:inline; margin-left:10px; font-size:32px; font-family:Helvetica; color:lightgray"></strong><br><br><pre style="margin:0">Code:</pre><textarea id="textbox" style="margin-top:5px; margin-bottom:5px"></textarea><br><pre style="margin:0">Input:</pre><textarea id="inputbox" style="margin-top:5px; margin-bottom:5px"></textarea><br><button id="testbtn">Test!</button><button id="resetbtn">Reset</button><br><p><strong id="origheader" style="font-family:Helvetica; display:none">Original Code Output:</strong><p><div id="origoutput" style="margin-left:15px"></div><p><strong id="newheader" style="font-family:Helvetica; display:none">New Code Output:</strong><p><div id="newoutput" style="margin-left:15px"></div><script type="text/javascript" id="golfsnippet">var bytecount=document.getElementById("bytecount");var bytediff=document.getElementById("bytediff");var textbox=document.getElementById("textbox");var inputbox=document.getElementById("inputbox");var testbtn=document.getElementById("testbtn");var resetbtn=document.getElementById("resetbtn");var origheader=document.getElementById("origheader");var newheader=document.getElementById("newheader");var origoutput=document.getElementById("origoutput");var newoutput=document.getElementById("newoutput");textbox.style.width=inputbox.style.width=window.innerWidth-50+"px";var _originalCode=null;function getOriginalCode(){if(_originalCode!=null)return _originalCode;var allScripts=document.getElementsByTagName("script");for(var i=0;i<allScripts.length;i++){var script=allScripts[i];if(script.id!="golfsnippet"){originalCode=script.textContent.trim();return originalCode}}}function getNewCode(){return textbox.value.trim()}function getInput(){try{var inputText=inputbox.value.trim();var input=eval("["+inputText+"]");return input}catch(e){return null}}function setTextbox(s){textbox.value=s;onTextboxChange()}function setOutput(output,s){output.innerHTML=s}function addOutput(output,data){output.innerHTML+='<pre style="background-color:'+(data.type=="err"?"lightcoral":"lightgray")+'">'+escape(data.content)+"</pre>"}function getByteCount(s){return(new Blob([s],{encoding:"UTF-8",type:"text/plain;charset=UTF-8"})).size}function onTextboxChange(){var newLength=getByteCount(getNewCode());var oldLength=getByteCount(getOriginalCode());bytecount.innerHTML=newLength+" bytes";var diff=newLength-oldLength;if(diff>0){bytediff.innerHTML="(+"+diff+")";bytediff.style.color="lightcoral"}else if(diff<0){bytediff.innerHTML="("+diff+")";bytediff.style.color="lightgreen"}else{bytediff.innerHTML="("+diff+")";bytediff.style.color="lightgray"}}function onTestBtn(evt){origheader.style.display="inline";newheader.style.display="inline";setOutput(newoutput,"");setOutput(origoutput,"");var input=getInput();if(input===null){addOutput(origoutput,{type:"err",content:"Input is malformed. Using no input."});addOutput(newoutput,{type:"err",content:"Input is malformed. Using no input."});input=[]}doInterpret(getNewCode(),input,function(data){addOutput(newoutput,data)});doInterpret(getOriginalCode(),input,function(data){addOutput(origoutput,data)});evt.stopPropagation();return false}function onResetBtn(evt){setTextbox(getOriginalCode());origheader.style.display="none";newheader.style.display="none";setOutput(origoutput,"");setOutput(newoutput,"")}function escape(s){return s.toString().replace(/&/g,"&amp;").replace(/</g,"&lt;").replace(/>/g,"&gt;")}window.alert=function(){};window.prompt=function(){};function doInterpret(code,input,cb){var workerCode=interpret.toString()+";function stdout(s){ self.postMessage( {'type': 'out', 'content': s} ); }"+" function stderr(s){ self.postMessage( {'type': 'err', 'content': s} ); }"+" function kill(){ self.close(); }"+" self.addEventListener('message', function(msg){ interpret(msg.data.code, msg.data.input); });";var interpreter=new Worker(URL.createObjectURL(new Blob([workerCode])));interpreter.addEventListener("message",function(msg){cb(msg.data)});interpreter.postMessage({"code":code,"input":input});setTimeout(function(){interpreter.terminate()},1E4)}setTimeout(function(){getOriginalCode();textbox.addEventListener("input",onTextboxChange);testbtn.addEventListener("click",onTestBtn);resetbtn.addEventListener("click",onResetBtn);setTextbox(getOriginalCode())},100);function interpret(code,input){window={};alert=function(s){stdout(s)};window.alert=alert;console.log=alert;prompt=function(s){if(input.length<1)stderr("not enough input");else{var nextInput=input[0];input=input.slice(1);return nextInput.toString()}};window.prompt=prompt;(function(){try{var evalResult=eval(code);if(typeof evalResult=="function"){var callResult=evalResult.apply(this,input);if(typeof callResult!="undefined")stdout(callResult)}}catch(e){stderr(e.message)}})()};</script>

More about the test suite


How it works

//Define function w/ paramters a, b
(a,b)=>
     //lowercase a
     //for each character v in a:
     [for(v of a[t="toLowerCase"]())
          //lowercase b
          //remove the first instance of v in b
          //if b before removal equals b after removal (if nothing was removed):
          if((b=b[t]())==(b=b.replace(v,"")))
               //keep v in the array of a's values to keep
               v]
     //get the length of the computed array
     [l="length"]
     //add b's length
     +b[l]
     //implicitly return the sum
\$\endgroup\$
8
  • \$\begingroup\$ I'd been working on an array-based ES6 answer for an hour, and had only been able to get it down to 122. Seems I was looking in the wrong direction! +1 \$\endgroup\$ Oct 7, 2015 at 2:34
  • \$\begingroup\$ BTW, you could replace .join("")+b with .join``+b with no effect. \$\endgroup\$ Oct 7, 2015 at 2:35
  • 1
    \$\begingroup\$ Wow, where on earth did you get that test suite? It's brilliant! I wish I could +1 three or four more times.... \$\endgroup\$ Oct 7, 2015 at 2:46
  • \$\begingroup\$ @ETHproductions Thank you! :D I made the test suite myself, actually. Check out my meta post! \$\endgroup\$
    – jrich
    Oct 7, 2015 at 2:47
  • \$\begingroup\$ I +1'ed over there, hope it makes up for not being able to +5 here. ;) \$\endgroup\$ Oct 7, 2015 at 2:49
5
\$\begingroup\$

CJam, 23 19 bytes

2{'¡,lelfe=}*.-:z:+

Try it online in the CJam interpreter.

How it works

2{         }*        Do the following twice:
  '¡,                  Push the string of the first 161 Unicode charcters.
     lel               Read a line from STDIN and convert it to lowercase.
        fe=            Count the number of occurrences of each of the 160
                       characters in the lowercased line.
             .-      Vectorized subtraction; push the differences of the
                     occurrences of all 161 characters.
               :z    Apply absolute value to each difference.
                 :+  Push the sum of all results.
\$\endgroup\$
4
\$\begingroup\$

Ruby, 62

#!ruby -naF|
gets
p$F.count{|c|!$_.sub!(/#{Regexp.escape c}/i){}}+~/$/

There has to be a better way.

Edit: 57 chars thanks to iamnotmaynard investigating a path I was too lazy to.

#!ruby -naF|
gets.upcase!
p$F.count{|c|!$_.sub!(c.upcase){}}+~/$/
\$\endgroup\$
3
  • \$\begingroup\$ sub can take strings. Couldn't you use c.downcase instead of /#{Regexp.escape c}/i ? \$\endgroup\$ Oct 7, 2015 at 15:06
  • \$\begingroup\$ I'd have to downcase both strings (or upcase, equivalently.) \$\endgroup\$
    – histocrat
    Oct 7, 2015 at 15:32
  • \$\begingroup\$ Ah, of course. (Though it looks to me that doing so would still save you a couple bytes.) \$\endgroup\$ Oct 7, 2015 at 15:37
4
\$\begingroup\$

Python, 90 87 81 80 79 bytes

lambda a,b,s=str.lower:sum(abs(s(a).count(c)-s(b).count(c)))for c in{*s(a+b)}))

Python <3.5 version, 80 bytes

lambda a,b,s=str.lower:sum(abs(s(a).count(c)-s(b).count(c))for c in set(s(a+b)))

Explanation

For each character in a or b, count up the number of occurrences in each string, and add the (positive) difference.

Edit: Re-read rules, realized anonymous functions are acceptable, improved answer by getting rid of raw_input. First golf, please be gentle!

Thanks to sp3000 for the improvement of redefining str.lower and making me realize print was unnecessary. Also spaces. Still learning.

Using python >=3.5, there's a shorter way of defining sets, so a byte can be saved over previous versions.

\$\endgroup\$
0
3
\$\begingroup\$

Retina, 40 20 bytes

20 bytes saved thanks to Martin Büttner.

Place each line in its own file and replace the \n with a literal newline.

+i`(.)(.*\n.*)\1
$2
.
\$\endgroup\$
0
2
\$\begingroup\$

pb, 648 bytes

^w[B!0]{t[B]vb[T]^>}vb[-1]w[X!0]{<t[64]w[T!0]{w[B!0]{b[B-1]v}^[Y]t[T-1]}}w[B!-1]{w[B=0]{b[27]}t[26]w[T!0]{w[B!0]{b[B-1]v}^[Y]t[T-1]}>}b[0]w[X!0]{<w[B!0]{b[1]v}^[Y]w[B=0]{b[32]}w[B=1]{b[0]}}^w[B!0]{t[B]vb[B+T]^>}vb[1]<w[B!9]{t[B]b[0]vv<[X]w[B!0]{>}b[T]^^<[X]w[B!0]{>}<}b[0]<w[X!-1]{t[B]vb[1]^w[B!1]{>}vvw[X!-1]{w[B=T]{b[0]<[X]^w[B!1]{>}^b[0]vt[2]}<}^[Y]vw[B!1]{>}b[0]^<}t[0]w[B!1]{w[B!0]{t[T+1]b[0]}>}b[0]vvw[X!-1]{w[B!0]{t[T+1]b[0]}<}>b[11]^b[T]w[B!0]{vw[B!11]{>}t[B]b[0]>b[T]<[X]^t[B]b[0]vw[B!11]{>}<w[T!0]{t[T-1]b[B+1]w[B=11]{b[0]^<[X]b[B+1]vw[B!11]{>}<}}^<[X]}vw[B!11]{b[B+48]>}b[0]<w[B!0]{w[B!0]{>}<t[B]^^<[X]w[B!0]{>}b[T]<[X]vvw[B!0]{>}<b[0]<}

Takes input with a tab character separating the two strings.

This one was a doozy. Actually implementing the algorithm wasn't the hard part, that came relatively easily. But I had to do two things that are difficult to do in pb: Case insensitivity and itoa. I happened to have a program for converting to lowercase just lying around (itself 211 bytes long) and everything else was tacked onto the end to do the work for this challenge specifically.

You can watch this program run on YouTube! There are a couple things you should keep in mind if you do:

  • This version of the program is slightly modified, weighing in at 650 bytes. The only difference is that 255 is used as a flag value instead of -1, because trying to print chr(-1) crashes the interpreter when running in watch mode.
  • The input in that video is Hello, world! and Code golf.. This is slightly different than one of the example inputs in the challenge; I used it because it was short but modified it so the correct output would be 10 instead of 9. This is just to show off that the number is printed correctly even if it's multiple digits, which is hard in pb.
  • The interpreter is awful, and it shows here. Notably, the tab character throws off the spacing so things aren't lined up for large portions of the video, whenever a byte is set to 10 it shows a line break even though the language still considers it to be one "line", and the fact that it just moves the cursor to the start instead of clearing the screen means that there are occasionally a number of characters in the video that aren't even really there, they just never went away from when they were there. There are some protections against this in pbi but the fact that chr(10) isn't handled properly makes them largely useless here. All that being said, I think it's almost kind of beautiful to watch. It's a huge mess of horrible code interpreting other horrible code, pieces of it breaking down in front of your eyes, and yet everything works just enough to get the right answer. It looks like garbage is being printed but if you watch closely enough with knowledge of the source you can make out what it's doing and why at any point. I feel like Cypher when I watch this video: I... I don’t even see the code. All I see is blonde, brunette, red-head.

Without further ado, here's the code ungolfed.

### UNTIL FURTHER NOTICE, ALL CODE YOU SEE HERE   ###
### IS JUST A SIMPLE LOWERCASE PROGRAM. ALL INPUT ###
### IS PRINTED UNALTERED UNLESS ITS ASCII CODE IS ###
### IN [65, 90], IN WHICH CASE IT IS PRINTED WITH ###
### 32 ADDED TO IT.                               ###

^w[B!0]{t[B]vb[T]^>}    # Copy entire input to Y=0
                        # (If the program ended here, it would be cat!)
vb[-1]                  # Leave a flag at the end of the copy (important later)

# Next, this program will set each of those bytes to 0 or 32, then add the input again.
# A byte needs to be set to 32 iff it's in [65, 90].
# pb can't test > or <, only == and !=.
# A workaround:

# Set each byte to max((byte - 64), 0)



w[X!0]{<        # For each byte:
    t[64]         # Set T to 64 as a loop variable
    w[T!0]{       # While T != 0:
        w[B!0]{     # While the current byte not 0:
            b[B-1]v   # Subtract one from the current cell, then go down one
                      # (guaranteed to be 0 and kill the loop)
        }
        ^[Y]        # Brush is at Y=0 or Y=1 and needs to be at Y=0.
                    # ^[Y] always brings brush to Y=0
        t[T-1]      # T--
    }
}

# Bytes that are currently 0 need to be 0.
# Bytes that are currently in [27, inf) need to be 0.
# Bytes in [1, 26] need to be 32.

# Set bytes that are equal to 0 to 27
# The only groups that have to be worried about are >26 and =<26.

# Then set each byte to max((byte - 26), 0)

w[B!-1]{         # Until we hit the flag:
    w[B=0]{b[27]}   # Set any 0 bytes to 27
    t[26]           # T as loop variable again
    w[T!0]{         # While T != 0:
        w[B!0]{       # While the current byte not 0:
            b[B-1]v     # Subtract one from the current cell, then go down one
                        # (guaranteed to be 0 and kill the loop)
        }
        ^[Y]          # Brush is at Y=0 or Y=1 and needs to be at Y=0.
                      # ^[Y] always brings brush to Y=0
        t[T-1]        # T--
    }
>}
b[0]              # Clear the flag

# Set bytes that are equal to 0 to 32
# All others to 0

w[X!0]{<          # For each byte:
    w[B!0]{       # While the current byte not 0:
        b[1]v       # Set it to 1, then go down one
                    # (guaranteed to be 0 and kill the loop)
    }
    ^[Y]          # Back to Y=0 no matter what
    w[B=0]{b[32]} # Set 0 bytes to 32
    w[B=1]{b[0]}  # Set 1 bytes to 0
}

# Any byte that had a capital letter is now 32. All others are 0.
# Add the original values to the current values to finish.

^w[B!0]{          # For each byte OF ORIGINAL INPUT:
    t[B]vb[B+T]^>   # Add it to the space below
}

### ABOVE IS THE ENTIRE LOWERCASE PROGRAM. THE    ###
### REST OF THE CODE IMPLEMENTS THE ALGORITHM.    ###

vb[1]            # Leave a flag after the end, guaranteed to be further right
                 # than anything else

<w[B!9]{         # Starting from the end, until hitting a tab:
    t[B]b[0]        # Store the last byte and erase it
    vv<[X]          # Go down two columns and all the way to the left
    w[B!0]{>}       # Go right until reaching an empty space
    b[T]            # Print the stored byte
    ^^<[X]w[B!0]{>} # Go back to the end of the first line
    <
}

b[0]              # Erase the tab
<w[X!-1]{         # For each byte in the first line:
    t[B]            # Store that byte
    vb[1]           # Mark that byte to be found later
    ^w[B!1]{>}      # Find the flag at the end
    vvw[X!-1]{      # For everything in the other line:
        w[B=T]{       # If the current byte is the same as the saved byte:
            b[0]        # Set it to 0
            <[X]^       # Go to the beginning of line 2
            w[B!1]{>}   # Find the marker for where the program is working in line 1
            ^b[0]v      # Set that byte that the program is working on to 0
            t[2]        # Stay on line 2 and start looking for a 2 (will never appear)
                        # (If this block was entered, it basically breaks the outer loop.)
        }
        <
    }
    ^[Y]v           # Ensure that the brush is on Y=1
    w[B!1]{>}       # Find the marker for where the program is working in line 1
    b[0]^<          # Erase the marker and start working on the next byte
}

t[0]              # Set T to 0. It's going to be used for counting the remaining bytes.

w[B!1]{           # Until hitting the flag at the very right:
    w[B!0]{         # If the current byte is not 0:
        t[T+1]        # Add 1 to T
        b[0]          # Set the current byte to 0
    }
    >
}
b[0]              # Clear the flag

vvw[X!-1]{        # Same as above, but for Y=2
    w[B!0]{
        t[T+1]
        b[0]
    }
    <
}

# T now contains the number that needs to be printed!!
# Now, to print out a number in decimal...

>b[11]            # A flag that shows the end of the number
                  # (so 0 digits aren't confused for other empty spaces on the canvas)
^b[T]             # The number to be converted to digits
w[B!0]{           # While the number to be converted is not 0:
    vw[B!11]{>}     # Go to the flag
    t[B]b[0]>b[T]   # Move it right
    <[X]^t[B]b[0]   # Store the number to be converted to digits to T and clear its space on the canvas
    vw[B!11]{>}<    # Go to the left of the flag
    w[T!0]{         # While T is not 0:
        t[T-1]        # T--
        b[B+1]        # B++
        w[B=11]{      # If B is 10:
            b[0]        # Set it back to 0
            ^<[X]b[B+1]   # Add 1 to a counter to be converted after
            vw[B!11]{>}<  # Go back to continue converting T
        }
    }
^<[X]}

vw[B!11]{         # Add 48 to all digits to get correct ASCII value
    b[B+48]>
}

b[0]              # Clear the flag value, 0s now appear as 48 instead of 0 so it is unnecessary

<w[B!0]{          # While there are digits on Y=2:
    w[B!0]{>}<      # Go to the last one
    t[B]            # Save it to T
    ^^<[X]          # Go to (0, 0)
    w[B!0]{>}       # Go right until finding an empty space
    b[T]            # Print the digit in T
    <[X]vvw[B!0]{>} # Go to the end of Y=2
    <b[0]           # Erase it
    <               # Repeat until finished. :)
}
\$\endgroup\$
2
\$\begingroup\$

C++ 199 bytes

Uses an array to store the count of each character in the first string, minis the count in the second string. Next it finds the sum of the absolute values of the elements of the array: this is the distance.

Golfed:

#define L(c) c<91&c>64?c+32:c
int d(char*a,char*b){int l[128];int i=128,s=0;for(;i-->0;)l[i]=0;for(;a[++i];)l[L(a[i])]++;for(i=-1;b[++i];)l[L(b[i])]--;for(i=0;++i<128;)s+=i[l]>0?i[l]:-i[l];return s;}

Ungolfed:

#define L(c) (c<='Z' && c>='A' ? c+'a'-'A':c)
//convert to lower case
int dist(char a[],char b[]){
  int l[128];
  int i = 128, s = 0;
  
  for(;i-->0;)
    l[i]=0;
  
  for(;a[++i]!='\0';)
    l[L(a[i])]++;
  
  for(i=-1;b[++i]!='\0';)
    l[L(b[i])]--;
  
  for(i=0;++i<128;)
    s+=i[l]>0?i[l]:-i[l];
  
  return s;
}
\$\endgroup\$
1
\$\begingroup\$

PowerShell, 79 bytes

param($a,$b)$a=[char[]]$a.ToLower();$b=[char[]]$b.ToLower();(diff $a $b).Length

Almost the exact same code as my answer on Anagram Code Golf ... but ... I'm getting some weird behavior if I just snip off the -eq0 from that answer, so I wound up needing to explicitly .ToLower() and recast outside of the param declaration.+

Explanation also (mostly) copied from that answer -- Takes the two string inputs, makes them lowercase, and re-casts them as char-arrays. The diff function (an alias for Compare-Object) takes the two arrays and returns items that are different between the two. We leverage that by re-casting the return as an array with (), and then checking its length.

+For example, I was getting bogus results with param([char[]]$a,[char[]]$b)(diff $a $b).length on the all lowercase./ALL UPPERCASE! test. If I manually separated out the arrays (e.g., ran (diff ('a','l','l'...), it worked fine, but would fail every time there were capital/lowercase overlap with the casting. Everything I can read on the documentation states that diff is case-insensitive by default, so ... shrug???

\$\endgroup\$
1
  • \$\begingroup\$ Very odd. It isn't needed for any of the other cases (even with different case-sensitivity). \$\endgroup\$ Oct 7, 2015 at 18:42
1
\$\begingroup\$

Bash, 68 67 bytes

f()(fold -w1<<<"$1"|sort)
diff -i <(f "$1") <(f "$2")|grep -c ^.\ 

I think this works. Note the trailing space on the second line.

Test cases

$ ./anagram "Hello, world!" "Code golf!"
9
$ ./anagram "12345 This is some text." ".txet emos si sihT 54321"
0
$ ./anagram "All unique characters here!" "Bdfgjkmopvwxyz?"
42
$ ./anagram "This is not exactly like Levenshtein distance," "but you'll notice it is quite similar."
30
$ ./anagram "all lowercase." "ALL UPPERCASE!"
8
\$\endgroup\$
1
\$\begingroup\$

Perl, 52 46 bytes + 3 switches (a,F,n) = 55 49 bytes

# 49 bytes (prefix 'x' to all characters so that values() could be removed)
perl -naF -E 'END{$c+=abs for%a;say$c}$a{x.lc}+=2*$.-3 for@F'

# 55 bytes
perl -naF -E 'END{$c+=abs for values%a;say$c}$a{+lc}+=2*$.-3 for@F'

Takes input from STDIN with the input strings in their own lines, terminated by EOF.

Switches:

-aF splits each input line into characters and stores this into @F
-n  loop over all input lines
-E  Execute the script from the next arg

Code:

# %a is the hash counting the occurances of the lowercase characters
# $. has the line number. Thus, 2*$.-3 is -1 for line 1 and +1 for line 2
$a{+lc}+=2*$.-3 for @F

# In the end (assuming 2 lines have been read), sum up the absolute values
# from the hash %a. Note that if a character occured more times in string 1
# its value be negative, if more in string 2 then positive, otherwise 0.
END {
    $c+=abs for values %a;
    say $c
}
\$\endgroup\$
1
\$\begingroup\$

Bash + GNU utils, 53

S(){ sed 's/./\L&\n/g'|sort;};S>1;S|comm -3 1 -|wc -l

sed transforms to lowercase and splits the string into lines for sort. Since we need to do this twice I put it into a function. comm3 -3 filters out the relevant lines and wc -l produces the number.

Input is via STDIN; since two commands read sequentially, you have to send EOF (Ctrl-D) twice, between the strings and at the end. Overwrites file 1, if present.

\$\endgroup\$
1
\$\begingroup\$

Matlab, 91 bytes

function r=f(s,t)
s=lower(s);t=lower(t);u=unique([s t]);r=sum(abs(histc(s,u)-histc(t,u)));

Try it online.

This works as follows:

  1. Converts the strings to lower case.
  2. Finds the unique characters of the two strings together. That is, determines all characters that ever appear in the strings.
  3. Computes the histogram of each string. That is, for each string finds how many times each of the characters obtained in step 2 appears.
  4. Subtracts the histograms and takes the absolute value of the differences. This represents how many times a character appears in one string more than in the other.
  5. The result is the sum of those absolute differences.
\$\endgroup\$
2
  • \$\begingroup\$ This seems way too long-- are you sure it's optimal? \$\endgroup\$
    – lirtosiast
    Oct 7, 2015 at 20:50
  • \$\begingroup\$ @ThomasKwa No, not at all :-) \$\endgroup\$
    – Luis Mendo
    Oct 7, 2015 at 20:51
1
\$\begingroup\$

Jelly, 6 bytes

Œlœ^/L

Try it online!

\$\endgroup\$
0
\$\begingroup\$

F#, 134 126 bytes

let g=Seq.countBy Char.ToLower>>List.ofSeq
let f a b=g a@g b|>Seq.groupBy fst|>Seq.sumBy(snd>>Seq.map snd>>Seq.reduce(-)>>abs)

Explanation:

  1. Count the number of times each (lowercased) character appears in a and b separately.
  2. Group the counts together by their common character
  3. Reduce each group with the - operator, which has the following effect:

    • If only one value is found (i.e. the character appeared in only one input), that value is returned.
    • If two values are found (i.e. the character appeared in both inputs) subtract the second value from the first.
  4. Sum the absolute value of the values from the previous step.

\$\endgroup\$
0
\$\begingroup\$

Scala, 134 81 bytes

Thanks @ASCII-only for their work.

(s,t)=>{var k::l::_=List(s,t)map(_.toLowerCase.toBuffer)
((k--l)++(l--k)).length}

Try it online!

\$\endgroup\$
6

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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