20
\$\begingroup\$

Challenge Description: An anagram is a word or phrase formed by rearranging the letters of another word or phrase. For example, "listen" and "silent" are anagrams. In this challenge, your task is to write a program or function that takes a list of strings as input and returns the unique anagrams.

Write a program or function that takes a list of strings as input and returns the unique anagrams, preserving the order of appearance. Your solution should handle lowercase letters (a-z) only.

Examples:

Input Output
["cat", "act", "tac", "dog", "god"] ["cat", "dog"]
["a", "ab", "abc", "abcd"] ["a", "ab", "abc", "abcd"]
["cat", "dog", "tac", "god", "act"] ["cat", "dog"]

The input list contains five strings. The strings "cat", "act", and "tac" are anagrams of each other, and "dog" and "god" are anagrams of each other. The output should contain only one representative from each group of anagrams, preserving the order of appearance. Hence, the output is ["cat", "dog"].

Requirements:

The input list can contain duplicate strings, and they should be considered as separate entities. The output should contain only one representative from each group of anagrams, preserving the order of appearance. The input list may contain an arbitrary number of strings. The input list and the output list can be empty.

This is , so the shortest solution in bytes is the winner.

Good luck!

\$\endgroup\$
8
  • 3
    \$\begingroup\$ Welcome to Code Golf! \$\endgroup\$ May 21, 2023 at 21:47
  • \$\begingroup\$ What is the source of this challenge? \$\endgroup\$
    – xnor
    May 21, 2023 at 22:08
  • 2
    \$\begingroup\$ I suggest adding test cases that contain words of different lengths, and test cases with some words that are no anagrams of any other word \$\endgroup\$
    – Luis Mendo
    May 21, 2023 at 23:37
  • 3
    \$\begingroup\$ I suggest adding a test case where anagrams are not all adjacent. \$\endgroup\$
    – chunes
    May 21, 2023 at 23:49
  • 3
    \$\begingroup\$ @LuisMendo, I read that to mean that the strings in the output must be in the same order as the appear in the input, but not necessarily be the first occurrence of each anagram in the input. Although, I do agree that the challenge does intend for us to output the first occurrence of each, it needs to be stated more clearly. \$\endgroup\$
    – Shaggy
    May 22, 2023 at 9:58

27 Answers 27

5
\$\begingroup\$

Jelly, 4 bytes

Ṣ€Ḣƙ

A monadic Link that accepts a list of lists and yields a list of lists containing the first of each anagram.

Try it online!

How?

Ṣ€Ḣƙ - Link: list of lists, Words
Ṣ€   - sort each word
   ƙ - group Words by sorted_words and apply to each:
  Ḣ  -   head
\$\endgroup\$
5
\$\begingroup\$

Ruby, 28 bytes

->l{l.uniq{|z|z.chars.sort}}

Try it online!

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

Vyxal, 32 bitsv1, 4 bytes

⁽sġvh

Try it Online!

Works well.

Explained

⁽sġvh
⁽sġ   # Group by sorting each word - groups based on first appearance of each word 
  vh  # Get the first word in each group 
\$\endgroup\$
4
\$\begingroup\$

05AB1E, 6 bytes

.¡{}€н

Try it online or verify all test cases.

Or alternatively:

€{DÙkè

Try it online or verify all test cases.

Explanation:

        #  EXAMPLE INPUT: ["cat","tac","dog","god","act"]

.¡ }    # Group the words in the (implicit) input-list by:
  {     #  Sort the characters of the word
        #   STACK: [["cat","tac","act"],["dog","god"]]
    €   # Then map over each group of words:
     н  #  And only leave the first one
        #   STACK: ["cat","dog"]
        # (after which the list of remaining words is output implicitly)

€       # Map over each word of the (implicit) input-list:
 {      #  Sort the characters of the word
        #   STACK: ["act","act","dgo","dgo","act"]
  D     # Duplicate this list of individually sorted words
        #  STACK: ["act","act","dgo","dgo","act"],["act","act","dgo","dgo","act"]
   Ù    # Uniquify the copy list of strings
        #  STACK: ["act","act","dgo","dgo","act"],["act","dgo"]
    k   # Pop both, and get the indices of the remaining strings
        #  STACK: [0,2]
     è  # Use those indices to index into the (implicit) input-list of words
        #  STACK: ["cat","dog"]
        # (after which the list of remaining words is output implicitly)
\$\endgroup\$
3
\$\begingroup\$

APL (Dyalog Extended), 7 bytes

Anonymous tacit prefix function.

⊣/∧¨⊢⌸⊢

Try it online!

⊣/ the first elements of

∧¨ the each-sorted

⊢⌸ grouping of

 the argument

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

Nibbles, 4.5 bytes (9 nibbles)

.=~$~`<$/
.=~$~`<$/
 =~         # group
   $        # the input
    ~       # without sorting the groups
     `<$    # by the results of sorting each element
.           # then map over this list of lists
        /   # folding over each list
            # (implicitly) returning the left-hand argument
            # (so returning the first element of each)

enter image description here

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

JavaScript (ES6), 43 bytes

a=>a.filter(s=>a[q=[...s].sort()]?0:a[q]=1)

Try it online!

Alternate versions (same size)

a=>a.filter(([...s])=>a[s.sort()]?0:a[s]=1)

Try it online!

a=>a.filter(([...s])=>a[s.sort()]^(a[s]=1))

Try it online!

Commented

a =>          // a[] = input array
a.filter(s => // for each string s in a[]:
  a[          //   test a[q]:
    q =       //     where q[] is the array
      [...s]  //     made of the characters of s
      .sort() //     sorted in lexicographical order
  ] ?         //   if a[q] is already defined:
    0         //     discard this entry
  :           //   else:
    a[q] = 1  //     set a[q] and keep this entry
)             // end of filter()
\$\endgroup\$
5
  • 1
    \$\begingroup\$ I wondered if you could do away with the q variable, but my attempt ended up the same size \$\endgroup\$
    – Jo King
    May 21, 2023 at 23:51
  • \$\begingroup\$ I thought you could do ||= assignment to save bytes but I guess it doesn’t work on dynamically accessed object properties? You learn something everyday I guess \$\endgroup\$
    – noodle man
    May 22, 2023 at 11:37
  • \$\begingroup\$ @Jacob Do you mean a[...]||=1? That would always be truthy. I'm sensing I may be misunderstanding what you mean. \$\endgroup\$
    – Arnauld
    May 22, 2023 at 11:44
  • \$\begingroup\$ @Arnauld ah yes, now I see that would be a bug—but what surprised me was that it seemed to be a SyntaxError \$\endgroup\$
    – noodle man
    May 22, 2023 at 11:56
  • 1
    \$\begingroup\$ @Jacob You'd need ECMAScript 2021 or higher, which is not supported by TIO (that would work on ATO). \$\endgroup\$
    – Arnauld
    May 22, 2023 at 11:59
3
\$\begingroup\$

Perl 5 -nlF, 23 bytes

$k{"@{[sort@F]}"}||=say

Try it online!

Input and output are one word per line.

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

Pyth, 5 bytes

hM.gS

Try it online!

Explanation

hM.gSkQ    # implicitly add k and Q
           # implicitly assign Q = eval(input())
  .g  Q    # group Q by lambda k
    Sk     #   sort k
hM         # take the first element of each group
\$\endgroup\$
3
\$\begingroup\$

Husk, 2 bytes

üO

Try it online!

A not particularly clever solution, but seeing that Husk could solve this with half the bytes of other golfing languages I had to post it.

Explanation

üO
ü     Remove duplicates from the list, keyed on
 O       the sorted strings

Basically ü does exactly what we need for this challenge: for each value in the input list, discard it if it is the same as any previous value when a function is applied to it. The function we use for this comparison is here simply the sorting function.

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

Scala, 80 bytes

Golfed version. Try it online!

w=>{var s=Set[String]();w.filter(x=>if(s(x.sorted)) 0>1 else {s+=x.sorted;0<1})}

Ungolfed version. Try it online!

object Main {
  def main(args: Array[String]): Unit = {
    val list = List("cat", "act", "tac", "dog", "god")
    val distinctAnagrams = removeAnagrams(list)
    println(distinctAnagrams)
  }

  def removeAnagrams(words: List[String]): List[String] = {
    var seen = Map[String, Boolean]()
    words.filter { word =>
      val sortedWord = word.sorted
      if (seen.contains(sortedWord)) false
      else {
        seen += (sortedWord -> true)
        true
      }
    }
  }
}

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

Wolfram Language (Mathematica), 38 33 bytes

#&@@@#~GatherBy~Sort@*Characters&

Thanks to @att!
Try it online!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 33 \$\endgroup\$
    – att
    May 22, 2023 at 5:54
  • \$\begingroup\$ Thanks, i always forget about ~ \$\endgroup\$
    – lesobrod
    May 22, 2023 at 6:01
2
\$\begingroup\$

R, 70 bytes

\(x)x[match(unique(y<-sapply(x,\(s)intToUtf8(sort(utf8ToInt(s))))),y)]

Attempt This Online!

String manipulation isn't something R is good at.

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

Japt, 9 bytes

Could be 4 if Japt had a built-in for grouping without sorting.

üñ mÎñ@bX

Try it

üñ mÎñ@bX     :Implicit input of array U
ü             :Group & sort by
 ñ            :  Sorting
   m          :Map
    Î         :  First element
     ñ        :Sort by
      @       :Passing each X through the following function
       bX     :  First index of X in U
\$\endgroup\$
2
\$\begingroup\$

C# (Visual C# Compiler), 116 bytes

a=>a.Aggregate(new Dictionary<string,string>(),(d,i)=>{d.TryAdd(string.Concat(i.OrderBy(m=>m)),i);return d;}).Values

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ In .NET 7, we can save 6 bytes by using the method Order() instead of OrderBy(m=>m). Unfortunally, TIO doesn't work with this. \$\endgroup\$ May 23, 2023 at 12:56
2
\$\begingroup\$

Python 3, 91 bytes

def h(l):s=set();return[w for w in l if(x:=''.join(sorted(w)))not in s and (s.add(x) or 1)]

Attempt This Online

I wonder whether the filter expression can be shortened further.

\$\endgroup\$
2
  • 3
    \$\begingroup\$ 56. \$\endgroup\$
    – loopy walt
    May 22, 2023 at 15:23
  • \$\begingroup\$ @loopywalt Ouch, nice; I really need to up my lambda game. \$\endgroup\$
    – ojdo
    May 22, 2023 at 16:16
2
\$\begingroup\$

Haskell, 64 bytes

import Data.List
s=sort
a=map head.groupBy((.s).(==).s).sortOn s

Try it online!

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

Julia 1.0, 17 bytes

!x=unique(sort,x)

Try it online!

input and output are a list of lists of characters

28 bytes with a list of strings as input and output: Try it online!

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

C (gcc), 277 bytes

#define C(A,L)for(int i=A=0;L[i];L[i++]==t&&++A);
i,j,k,x,y,r,t;D(char*a,char*b){for(r=k=0;(t=a[k])||b[k];++k){if(!a[k]||!b[k]){++r;break;}C(x,a)C(y,b)x-y!=0&&++r;}}
main(int c,char**v){for(i=1;i<c;++i){for(j=i-1;j>0;--j){D(v[j],v[i]);if(r==0)goto B;}printf("%s ",v[i]);
B:1;}}

Try it online!

Readable version:

#define C(A,L)for(int i=A=0;L[i];L[i++]==t&&++A);

i,j,k,x,y,r,t;

D(char*a,char*b){
    for(r=k=0;(t=a[k])||b[k];++k){
        if(!a[k]||!b[k]){++r;break;}
        C(x,a)
        C(y,b)
        x-y!=0&&++r;
    }
}

main(int c,char**v) {
    for(i=1;i<c;++i){
        for(j=i-1;j>0;--j){
            D(v[j],v[i]);
            if(r==0)goto B;
        }
        printf("%s ",v[i]);
B:1;
    }
}

Explanation:

Not the most efficient approach but light on code: go through each item in the list (given as arguments), compare to each prior item using a difference function D, and print if none of them matched.

To check matching, the difference function goes through each character in the first string and counts the number of occurrences in either string of that character. If at any point either that number differs or we have finished processing one string while the other is still going, we consider the two non-matching.

To save bytes, I added the counting macro C, which accumulates into variable A the number of occurrences of global character t in list L.

-

C (gcc), 303 bytes (alternate answer)

typedef unsigned long long u;n,i,j,k,z;u t;u y(n){return n==1?1:z*y(n-1)+1;}s(char* v){for(k=t=0;v[k];++k)t+=y(v[k]-96);}main(int c,char *v[]){long f[c];for(i=1;i<c;++i)for(j=0;v[i][j];++j>z&&++z);for(i=1;i<c;++i){s(v[i]);for(j=n,k=0;j>0;--j){f[j-1]==t&&++k;}if(k)continue;printf("%s ",v[i]);f[n++]=t;}}

Try it online!

Readable version:

typedef unsigned long long u;
n,i,j,k,z;u t;
u y(n){return n==1?1:z*y(n-1)+1;}
s(char* v){for(k=t=0;v[k];++k)t+=y(v[k]-96);}
main(int c,char *v[]) {
    long f[c];
    for(i=1;i<c;++i)for(j=0;v[i][j];++j>z&&++z);
    for(i=1;i<c;++i){
        s(v[i]);
        for(j=n,k=0;j>0;--j){f[j-1]==t&&++k;}
        if(k)continue;
        printf("%s ",v[i]);
        f[n++]=t;
    }
}

Explanation:

For sufficiently short strings, this alternate approach will work. We are calculating a signature, which is something like a checksum but reserving non-overlapping number ranges for the potential counts of each letter, for each given list item. We go through the items and then, each time we encounter a novel signature, we print the item and store the signature.

These signatures as currently calculated get really large really fast, so this will only work for short words. Realizing this, I switched to the other approach, but still thought it was interesting enough to include.

I suspect that with a little more work, this could not only work for arbitrarily-long arguments, but also do so with a lighter footprint than the first approach!

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

Arturo, 32 bytes

$=>[gather&=>sort|map[k,v]->v\0]

Try it!

Collect input strings in a dictionary where the key is the sorted string and the value is a list of strings that sort to that key, then map each dictionary entry to its first value. Input is taken as a list of lists of code points.

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

Excel, 99 bytes

=LET(r,ROW(A:A),b,BYROW(A:A,LAMBDA(s,CONCAT(SORT(MID(s,r,1))))),FILTER(A:A,(b<>"")*MATCH(b,b,0)=r))

Note: This takes quite a long time to run on my weak machine and sometimes just locked Excel. For the sake of the screenshots below, I changed the range references from A:A to just A1:A10. The logic is all the same, though.

Input is one string per cell in column A.

  • LET(r,ROW(A:A) creates an array of values 1 to 1,048,576 and assigns it to the variable r.
  • b,BYROW(A:A,LAMBDA(s,CONCAT(SORT(MID(s,r,1))))) takes each string, splits it into pieces, sorts those pieces, and then combines them back into a string. The array of all these new, sorted strings is assigned to the variable b.
  • FILTER(A:A,(b<>"")*MATCH(b,b,0)=r) filters out the values where that result array b is blank and then only returns the strings from the input array where their index in the input matches the first instance of their sorted string in the sorted string array b.

Screenshot

There are probably shorter ways to do this and I welcome someone pointing them out.

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

PowerShell Core, 53 bytes

$args|?{($k="$($_|% t*y|sort)")-notin$s-and($s+=,$k)}

Try it online!

Takes the words arguments using splatting, returns a list or words.

It works by building a list of keys for each word by sorting its letters alphabetically:
e.g. cat has the key a c t
Then for each word $_, if the word's key $k is not in the list $s, add $k to $s and return $_

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

Factor + sets.extras, 22 bytes

[ [ sort ] unique-by ]

Factor has the perfect combinator for this, unique-by, which returns a list of the first unique values in a list after a function has been applied to each element. Requires Factor build ~2207+ for sort, hence this won't work on TIO or ATO.

enter image description here

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

Thunno 2, 4 bytes

ñṠ€h

Attempt This Online!

Explanation

ñṠ€h  # Implicit input
ñṠ    # Group by sorting
  €h  # First item of each
      # Implicit output
\$\endgroup\$
1
\$\begingroup\$

simply, 105 100 bytes

Yes, it's very long, but makes use of the built-in &marsagain.
(It's an anagram for &is_anagram, that happens to be 1 byte shorter.)

fn($x){$A=[]each$X in$x{$L=0each$a in$A if!$L$L=&marsagain($X$a)if!$L$A=&array_concat($A$X)}send$A;}

Defines an anonymous function that takes an array of strings and returns an array of strings.



Ungolfed

This is the same code, but ungolfed.

Code-like

anonymous function($words) {
    $anagrams = [];
    each $word in $words {
        $in_the_list = false;
        each $anagram in $anagrams {
            unless $in_the_list then {
                $in_the_list = &is_anagram($word, $anagram);
            }
        }
        
        unless $in_the_list then {
            $anagrams = &array_concat($anagrams, $word);
        }
    }
    
    return $anagrams;
};

English-like

Set the variable $fn to an anonymous function with arguments($words)
Begin.
    Set the variable $anagrams = [].
    Foreach $word in $words
    Begin.
        Set the variable $in_the_list to false.
        
        Foreach $anagram in $anagrams
        Begin.
            Unless $in_the_list then
            Begin.
                Set the variable $in_the_list to the result of calling the function &is_anagram with the arguments ($word, $anagram).
            End.
        End.
        
        Unless $in_the_list then
        Begin.
            Set the variable $anagrams to the result of calling the function &array_concat with the arguments ($anagrams, $word).
        End.
    End.
    
    Return the value of $anagrams.
End.

Both variants do the same.



Testing it

To test it, you have to assign it to a variable, E.g.:

$fn = fn($x){$A=[$x->0]each$X in$x{$L=0each$a in$A if!$L$L=&marsagain($X$a)if!$L$A=&array_concat($A$X)}send$A;};

// Copy-paste from the tests
$result = call $fn(["cat", "dog", "tac", "god", "act"]);

// Should output ["cat","dog"]
echo &json_encode($result);
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 20 bytes

WSF⬤υ⊙⁺ικ⁻№ιμ№κμ⊞υιυ

Try it online! Link is to verbose version of code. Takes input as a list of newline-terminated strings. Explanation:

WS

Repeat for each input string.

F⬤υ⊙⁺ικ⁻№ιμ№κμ

If none of the unique anagrams so far are anagrams of this string, then...

⊞υι

... add this string to the list of unique anagrams so far.

υ

Output the final list of unique anagrams.

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

Uiua SBCS, 9 bytes

▽◰⍚(⊏⍏.).

Try it!

▽◰⍚(⊏⍏.).
        .  # duplicate
  ⍚(⊏⍏.)   # sort each string
 ◰         # mark firsts
▽          # keep
\$\endgroup\$

Your Answer

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

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