Vous combattez un vaste réseau d' espions ennemis . Vous savez que chaque espion a au moins une (parfois plusieurs) fausses identités qu’ils aiment utiliser. Vous aimeriez vraiment savoir à combien d'espions vous avez réellement affaire.

Heureusement, vos agents de contre-espionnage font leur travail et peuvent parfois déterminer si deux fausses identités sont réellement contrôlées par le même espion ennemi.

C'est-à-dire:

• Vos agents ne savent pas toujours quand deux fausses identités ont le même espion derrière elles, cependant
• Si un agent vous dit que deux fausses identités sont contrôlées par le même espion, vous avez l’impression qu’elles ont raison.

Messages de l'agent

Les agents vous envoient des messages cryptés vous indiquant quelles identités ont le même espion derrière elles. Un exemple:

Vous avez 2 agents et 5 fausses identités à traiter.

Le premier agent vous envoie un message:

Red Red Blue Orange Orange

Cela signifie qu'ils pensent qu'il y a 3 espions:

• le premier (en rouge) contrôle les identités 1 et 2
• le second (bleu) contrôle l'identité 3
• le troisième (Orange) contrôle les identités 4 et 5

Le deuxième agent vous envoie un message:

cat dog dog bird fly

Cela signifie qu'ils pensent qu'il y a 4 espions:

• le premier (chat) contrôle l'identité 1
• le second (chien) contrôle les identités 2 et 3
• le troisième (oiseau) contrôle l'identité 4
• le quatrième (mouche) contrôle l'identité 5

En compilant les informations, nous voyons:

Identities:   id1    id2    id3    id4    id5 
Agent 1:    |--same-spy--|       |--same-spy--|
Agent 2:           |--same-spy--|
Conclusion: |-----same-spy------||--same-spy--|

Cela signifie qu'il y a au plus 2 espions .

Remarques

Les identités appartenant au même espion ne doivent pas nécessairement être consécutives, c’est-à-dire un message du type:

dog cat dog

est valable.

En outre, le même mot peut être utilisé par deux agents différents - cela ne veut rien dire, c'est juste une coïncidence, par exemple:

Agent 1: Steam Water Ice
Agent 2: Ice Ice Baby

La glace est utilisée par les deux agents - l’ Iceutilisation par le premier agent n’est pas liée aux deux occurrences de celle Iceutilisée par le deuxième agent.

Défi

Compilez l'intelligence de tous vos agents et déterminez le nombre d'espions ennemis. (Pour être plus précis, obtenez la limite supérieure la plus basse compte tenu des informations limitées dont vous disposez.)

Le code le plus court en octets gagne.

Spécifications d'entrée et de sortie

L'entrée est une liste de n lignes, qui représentent n messages des agents. Chaque ligne est composée de k jetons séparés par des espaces, le même k pour toutes les lignes. Les jetons sont alphanumériques, de longueur arbitraire. L'affaire compte.

Le résultat devrait être un nombre unique, représentant le nombre d'espions distincts, basé sur les informations de vos agents.

Exemples

Exemple 1

Contribution:

Angel Devil Angel Joker Thief Thief
Ra Ra Ras Pu Ti N
say sea c c see cee

Sortie:

2

Exemple 2

Contribution:

Blossom Bubbles Buttercup
Ed Edd Eddy

Sortie:

3

Exemple 3

Contribution:

Botswana Botswana Botswana
Left Middle Right

Sortie:

1

Exemple 4

Contribution:

Black White
White Black

Sortie:

2

Exemple 5

Contribution:

Foo Bar Foo
Foo Bar Bar

Sortie:

1

Exemple 6

Contribution:

A B C D
A A C D
A B C C
A B B D

Sortie:

1

Exemple 7

Contribution:

A B A C

Sortie:

3

Exemple 8

Contribution:

A
B
C

Sortie:

1

Exemple 9

Contribution:

X

Sortie:

1

Sledgehammer 0.5.1 , 16 15 octets

⡡⠥⡀⡾⠥⢢⠍⣽⡷⣩⣅⡷⣡⢒⠅

Décompresse dans cette fonction Wolfram Language (la finale &est implicite):

Length[ConnectedComponents[RelationGraph[Inner[Equal, ##1, Or] &,
    Transpose[StringSplit @ #1]]]] &

Essayez-le en ligne!

Transpose[StringSplit @ #1]: Scinder chaque chaîne de la liste d'entrée et prendre les colonnes (identités d'espionnage)

RelationGraph[Inner[Equal, ##1, Or] &, ...]: Construit le graphique où deux sommets partagent une arête si au moins une position est égale (s'ils sont classés comme étant le même espion par un agent ami)

Length[ConnectedComponents[...]]: Le nombre de composants connectés est la limite supérieure du nombre possible d'espions.

JavaScript (Node.js) ,  155 150 142  141 octets

a=>new Set((a=a.map(s=>s.split` `))[0].map((_,x)=>a.flat(m=1<<x).map(o=_=>a.map((b,y)=>b.map((w,i)=>m>>i&1|o[w+=y]?o[w]=m|=1<<i:0)))|m)).size

Essayez-le en ligne!

Comment?

$x$$m$$x$

+---------+-------+-------+-------+-------+-------+-------+
| x       |   0   |   1   |   2   |   3   |   4   |   5   |
+---------+-------+-------+-------+-------+-------+-------+
| 2**x    |   1   |   2   |   4   |   8   |  16   |  32   |
+---------+-------+-------+-------+-------+-------+-------+
| words   | Angel | Devil | Angel | Joker | Thief | Thief |
|         | Ra    | Ra    | Ras   | Pu    | Ti    | N     |
|         | say   | sea   | c     | c     | see   | cee   |
+---------+-------+-------+-------+-------+-------+-------+
| bitmask |  15   |  15   |  15   |  15   |  48   |  48   |
+---------+-------+-------+-------+-------+-------+-------+

Commenté

a =>                      // a[] = input
new Set(                  // we eventually convert the generated array into a set
  (a = a.map(s =>         // we first need to convert each line into
    s.split` `            // an array of words (*sigh*)
  ))                      //
  [0].map((_, x) =>       // for each word at position x in the first line:
    a.flat(m = 1 << x)    //   initialize a bitmask m with the x-th bit set and build an
                          //   array containing as many entries (N) as there are words in
                          //   the whole matrix
    .map(o =              //   the object o is used to store words
         _ =>             //   repeat N times to ensure that all relations are found:
      a.map((b, y) =>     //     for each line b[] at position y in a[]:
        b.map((w, i) =>   //       for each word w at position i in b[]:
          m >> i & 1 |    //         if the i-th bit is set in m (the relation already
                          //         exists)
          o[w += y] ?     //         or w + y is set in o (a relation exists in this line):
            o[w] =        //           set o[w + y] (the value doesn't matter as long as
                          //           it's non-zero)
              m |= 1 << i //           set the i-th bit in m
          :               //         else:
            0             //           do nothing
        )                 //       end of map() over the words
      )                   //     end of map() over the lines
    ) | m                 //   end of map() over all flatten entries; yield m
  )                       // end of map() over x
).size                    // return the size of the corresponding set

Gelée , 19 octets

ḲiⱮ`)ZŒc€ẎyⱮ@ƒƊÐLQL

Essayez-le en ligne!

Prend les entrées sous forme de liste de lignes séparées par des espaces (le pied de page en tient compte).

Note: ḲŒQ)PSne fonctionne pas .

Python 3 , 132 162 154 139 135 octets

def f(a):r=[*zip(*[map(b.index,b)for b in map(str.split,a)])];return sum(i==min(min(u)for u in r if min(w)in u)for i,w in enumerate(r))

Essayez-le en ligne!

Il s'agit d'une implémentation très compacte d'un algorithme graphique identifiant des grappes.

1. Pour chaque agent, nous créons une carte de profils et leurs alias, ce qui est l'indice le plus bas d'apparition: [map(b.index,b)for b in map(str.split,a)]. Ie [0,1,2,1,2]identifie trois espions, où le premier profil appartient à un, les deuxième et quatrième à un autre et le troisième et le cinquième au dernier. L'index du groupe est également l'index du premier profil du groupe.

2. En transposant cette matrice ( [*zip(*m...)]), nous obtenons une appartenance à un groupe pour chaque profil. Cela forme un graphe acyclique dirigé, car les index de groupe sont un sous-ensemble des index de profil, et tous les bords vont vers des index inférieurs ou égaux. Les profils correspondant au même espion forment maintenant un cluster sans connexion aux autres profils. Nous avons toujours des chemins en double, car les index de profil sont liés à plusieurs index de groupes.

3. Avec les boucles suivantes, nous réduisons le graphique en une forêt plate, dans laquelle tous les profils sont directement liés à l'indice le plus bas de leur arbre, à savoir la racine: min(min(u)for u in r if min(w)in u)

4. Enfin, le retour le nombre de racines dans la forêt, les indices liés à - dire eux - mêmes: return sum(i==...).

charbon , 49 43 octets

≔⪪Ｓ θＷＳ«≔⪪ι ιＦＬιＵＭθ⎇⁼λ§θκ§θ⌕ι§ικλ»ＩＬΦθ⁼κ⌕θι

Essayez-le en ligne! Le lien est vers la version verbeuse du code. Pourrait éventuellement économiser quelques octets en utilisant un format d’entrée encombrant. Explication:

≔⪪Ｓ θ

Entrez la liste du premier agent.

ＷＳ«

Répétez l'opération pour les agents restants.

≔⪪ι ι

Entrez leur liste.

ＦＬι

Boucle sur chaque index d'élément.

ＵＭθ⎇⁼λ§θκ§θ⌕ι§ικλ»

Recherchez le premier élément de la liste de cet agent avec la même identité et mettez à jour la liste du premier agent pour montrer qu'il s'agit de la même identité.

ＩＬΦθ⁼κ⌕θι

Comptez le nombre d'identités uniques restantes.

Gelée , 25 à 15 octets

ḲĠ)ẎfƇFQɗⱮQ$ÐLL

Essayez-le en ligne!

Un lien monadique prenant une liste de revendications d'agent séparant les espaces et renvoyant la limite supérieure la plus basse du nombre d'espions distincts.

Explication

  )              | For each list:
Ḳ                | - Split at spaces
 Ġ               | - Group indices of equal items
   Ẏ             | Tighten lists, so we have a single list of grouped indices
           $ÐL   | Repeat the following until no change:
        ʋⱮQ      | - Do the following as a dyad, mapping through each element of the uniquified list as the right argument
    fƇ           |   - Keep only those list members with one or more items matching the right argument
      F          |   - Flatten
       Q         |   - Uniquify
              L  | Finally take the length of the resultant list

Merci à @Arnauld et @JonathanAllan pour avoir identifié les problèmes liés aux versions précédentes et à @JonathanAllan pour avoir sauvegardé un octet! Si les spécifications d'entrée étaient assouplies pour permettre une liste de listes, cela économiserait un octet.

JavaScript (Node.js) , 120 octets

a=>a.map(l=>(s=l.split` `).map((w,i)=>r[o(i)]=o(s.indexOf(w)),o=i=>r[i]-i?o(r[i]):i),r=[])|r.map(g=(v,i)=>t+=v==i,t=0)|t

Essayez-le en ligne!

a=>a.map(l=>(                  // for each line
  (s=l.split` `).map((w,i)=>(  // for each words in line
    r[o(i)]=o(s.indexOf(w)),   // join(current index, first occurrence index)
  )),                          //   without updating nodes in path
  o=i=>r[i]-i?o(r[i]):i,       // a function to find root of some node
  r=[]                         // initial disjoint-set
))|
r.map(g=(v,i)=>t+=v==i,t=0)|   // count roots of tree
t                              // output

Décortiquer , 12 octets

LωomΣknṁoηkw

Essayez-le en ligne!

Explication

L'idée est de créer une liste de tous les groupes d'espions connus pour être la même personne, puis de fusionner progressivement les groupes qui se croisent jusqu'à atteindre un point fixe. Le résultat est le nombre de groupes restants qui n'ont pas pu être fusionnés.

LωomΣknṁoηkw  Implicit input: list of strings, say ["a bc a","b g g"]
       ṁ      Map and concatenate:
           w   Split at spaces: "a bc a" becomes ["a","bc","a"]
         ηk    Group indices by equality of elements: [[1,3],[2]]
              Result: [[1,3],[2],[1],[2,3]]
 ω            Iterate until result doesn't change:
     k         Group greedily by
      n        (non-emptiness of) intersection: [[[1,3],[1]],[[2],[2,3]]]
   mΣ          Concatenate each part: [[1,3,1],[2,2,3]]
              Result: [[1,3,1,2,2,3]]
L             Length: 1

Python 3 ,191 182 octets

Merci récursive

e=enumerate
def f(a):
	r=[list(map(b.index,b))for b in map(str.split,a)]
	for z in r:
		for i,v in e(z):
			for x in(i>v)*r:x[(i,x[i])[x[i]<i]]=z[v]
	return sum(i==v for i,v in e(z))

Essayez-le en ligne!

Ruby , 123 117 octets

Utilise une idée similaire à celle de la solution Python 3 de movatica mais calcule l'indice d'espionnage le plus faible pour chaque "arbre" d'une manière légèrement différente (en gardant une trace des profils précédents rencontrés, en recherchant un chevauchement s'il existe et en les combinant)

-6 octets de @GB.

->a,*b{a.map{|s|e=s.split;e.map{|i|e.index i}}.transpose.map{|e|b<<(b.find{|i|i-e!=i}||[])+e}
b.map(&:min).uniq.size}

Essayez-le en ligne!

Explication

->a,*b{                                             # Start lambda with input a, b=[]
       x=
         a.map{|s|                             }    # For each agent's report
                  e=s.split;                        # Split the words
                            e.map{|i|e.index i}     # Get spy number for each

   .transpose                                       # Transpose to get group membership
             .map{|e|                            }  # For each profile
                        (b.find{|i|i-e!=i}||[])     # Find a profile in b that overlaps
                                                    #  If one is not found, use []
                                               +e   # Add the profile onto the found one
                     b<<                            # Insert this modified profile into b

b.map(&:min)                                        # Get minimum of each modded profile
            .uniq                                   # Deduplicate
                 .size                              # Size of array
}                                                   # Implicit return

Python 2 , 229 221 octets

e=enumerate
def f(s):
 v=[];u=sum([(lambda a:[{i for i,x in e(a)if x==k}for k in set(a)])(a.split())for a in s.split('\n')],v)
 while u:
	x=u.pop()
	for i,y in e(u):
	 if x&y:u.pop(i);u+=[x|y];break
	else:v+=[x]
 return v

Essayez-le en ligne!

8 octets à wilkben .

Propre , 137 octets

import StdEnv,Text,Data.List
q=length
$l=q(iter(q l)(map flatten o groupBy isAnyMember)(transpose[[(s,n)\\s<-split" "z]\\z<-l&n<-[1..]]))

Essayez-le en ligne!

Associe les chaînes utilisées par les agents au numéro de ligne dans lequel elles apparaissent pour éviter toute égalité entre les agents, puis vérifie à plusieurs reprises si des expressions de position se chevauchent et compte le nombre d'ensembles résultants.

PHP , 271 octets

Cela ne fonctionnera pas si l'une des identités ne sont que des chiffres, car je stocke le "numéro d'espion" avec les identités. Je ne pense pas que ce ne serait pas difficile de résoudre ce problème.

$a=$argv;array_shift($a);if(count($a)==1)array_push($a,...$a);foreach($a as&$b)$b=explode(" ",$b);$c=array_map(null,...$a);foreach($c as&$d)foreach($d as$k=>$e){if(!$d[s])$d[s]=++$s;foreach($c as&$f)if($f[$k]==$e)$f[s]=$d[s];}echo count(array_unique(array_column($c,s)));

Essayez-le en ligne!

Explication

J'étais un peu perplexe en écrivant cela, mais cela fonctionne pour tous les cas de test!

$a=$argv;					//shorten the arguments variable
array_shift($a);				//removes the script name from the arguments variable
if(count($a)==1)array_push($a,...$a);		//the code needs at least 2 messages to run so if only 1 message duplicate it. "..." passes the stuff in the array rather than the array itself?
foreach($a as&$b)$b=explode(" ",$b);		//turns each string message into an array
$c=array_map(null,...$a);			//if you give array_map "null" for the callabck then it zips the arrays, turning a m by n 2D array into a n by m 2D array. this changes it from the messages being grouped to the identities being grouped
foreach($c as&$d)				//loop over the groups of identities
	foreach($d as$k=>$e)			//loop over the names the agents gave the identity and keep track of the key
	{
		if(!$d[s])$d[s]=++$s;		//if this identity doesn't have a "spy number" give it the next one
		foreach($c as&$f)		//loop over the groups of identities again
			if($f[$k]==$e)		//check if the agents gave any other identities this name 
				$f[s]=$d[s];	//if they did then give those the same "spy number"
	}
echo count(array_unique(array_column($c,s)));	//use array_column to get the "spy number" of each identity, remove duplicates using array_unique and then count the size of the array giving the upper limit of spies

Essayez-le en ligne!