Você está lutando contra uma extensa rede de espiões inimigos . Você sabe que cada espião tem pelo menos uma (às vezes várias) identidades falsas que eles gostam de usar. Você realmente gostaria de saber com quantos espiões está lidando.

Felizmente, seus agentes de contra-inteligência estão fazendo seu trabalho e, às vezes, podem descobrir quando duas identidades falsas são realmente controladas pelo mesmo espião inimigo.

Ou seja:

• Seus agentes nem sempre sabem quando duas identidades falsas têm o mesmo espião, no entanto
• Se um agente lhe disser que duas identidades falsas são controladas pelo mesmo espião, você confia que elas estão certas.

Mensagens do agente

Os agentes enviam mensagens enigmáticas informando quais identidades têm o mesmo espião por trás delas. Um exemplo:

Você tem 2 agentes e 5 identidades falsas para lidar.

O primeiro agente envia uma mensagem para você:

Red Red Blue Orange Orange

Isso significa que eles acham que existem três espiões:

• o primeiro (vermelho) controla as identidades 1 e 2
• o segundo (azul) controla a identidade 3
• o terceiro (laranja) controla as identidades 4 e 5

O segundo agente envia uma mensagem:

cat dog dog bird fly

Isso significa que eles acham que existem 4 espiões:

• o primeiro (gato) controla a identidade 1
• o segundo (cão) controla as identidades 2 e 3
• o terceiro (pássaro) controla a identidade 4
• o quarto (mosca) controla a identidade 5

Compilando as informações que vemos:

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

Isso significa que existem no máximo 2 espiões .

Notas

As identidades pertencentes ao mesmo espião não precisam ser consecutivas, ou seja, uma mensagem como:

dog cat dog

é válido.

Além disso, a mesma palavra pode ser usada por dois agentes diferentes - isso não significa nada, é apenas uma coincidência, por exemplo:

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

O gelo é usado pelos dois agentes - o Iceusado pelo primeiro agente não tem relação com as duas ocorrências Iceusadas pelo segundo agente.

Desafio

Compile as informações de todos os seus agentes e descubra quantos espiões inimigos existem realmente. (Para ser mais preciso, obtenha o limite superior mais baixo, considerando as informações limitadas que você possui.)

O código mais curto em bytes vence.

Especificação de entrada e saída

A entrada é uma lista de n linhas, que representam n mensagens de agentes. Cada linha consiste em k tokens separados por espaço, o mesmo k para todas as linhas. Os tokens são de comprimento alfanumérico e arbitrário. O caso é importante.

A saída deve ser um número único, representando o número de espiões distintos, com base nas informações dos seus agentes.

Exemplos

Exemplo 1

Entrada:

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

Saída:

2

Exemplo 2

Entrada:

Blossom Bubbles Buttercup
Ed Edd Eddy

Saída:

3

Exemplo 3

Entrada:

Botswana Botswana Botswana
Left Middle Right

Saída:

1

Exemplo 4

Entrada:

Black White
White Black

Saída:

2

Exemplo 5

Entrada:

Foo Bar Foo
Foo Bar Bar

Saída:

1

Exemplo 6

Entrada:

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

Saída:

1

Exemplo 7

Entrada:

A B A C

Saída:

3

Exemplo 8

Entrada:

A
B
C

Saída:

1

Exemplo 9

Entrada:

X

Saída:

1

Marreta 0.5.1 , 16 15 bytes

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

Descomprime nesta função da Wolfram Language (a final &está implícita):

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

Experimente online!

Transpose[StringSplit @ #1]: Divida cada sequência na lista de entrada e pegue as colunas (identidades de espionagem)

RelationGraph[Inner[Equal, ##1, Or] &, ...]: Construa o gráfico em que dois vértices compartilham uma aresta se pelo menos uma posição for igual (se eles forem classificados como o mesmo espião por algum agente amigo)

Length[ConnectedComponents[...]]: O número de componentes conectados é o limite superior do possível número de espiões.

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

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

Experimente online!

Quão?

$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   |
+---------+-------+-------+-------+-------+-------+-------+

Comentado

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éia , 19 bytes

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

Experimente online!

Recebe entrada como uma lista de linhas separadas por espaço (o rodapé é responsável por isso).

Nota: ḲŒQ)PSse não funcionar.

Python 3 , 132 162 154 139 135 bytes

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))

Experimente online!

Esta é uma implementação muito compacta de um algoritmo gráfico que identifica clusters.

1. Para cada agente, criamos um mapa de perfis e seus alias, que é o menor índice de aparência: [map(b.index,b)for b in map(str.split,a)]. Ou seja, [0,1,2,1,2]identifica três espiões, onde o primeiro perfil pertence a um, o segundo e o quarto a outro e o terceiro e o quinto ao último. O índice do grupo também é o índice do primeiro perfil no grupo.

2. Ao transpor essa matriz ( [*zip(*m...)]), obtemos uma associação de grupo para cada perfil. Isso forma um gráfico acíclico direcionado, porque os índices de grupo são um subconjunto dos índices de perfil e todas as arestas vão para índices inferiores ou iguais. Os perfis correspondentes ao mesmo espião agora formam um cluster sem conexões com os outros perfis. Ainda temos caminhos duplicados, porque os índices de perfil estão vinculados a vários grupos.

3. Com os seguintes loops, minimizamos o gráfico em uma floresta plana, onde todos os perfis são vinculados diretamente ao índice mais baixo em sua árvore, ou seja, a raiz: min(min(u)for u in r if min(w)in u)

4. Finalmente, retornar o número de raízes na floresta, ou seja, os índices ligados a si mesmos: return sum(i==...).

Carvão , 49 43 bytes

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

Experimente online! Link é a versão detalhada do código. É possível salvar alguns bytes usando um formato de entrada complicado. Explicação:

≔⪪Ｓ θ

Insira a lista do primeiro agente.

ＷＳ«

Repita o procedimento para os demais agentes.

≔⪪ι ι

Insira a lista deles.

ＦＬι

Loop sobre cada índice de elemento.

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

Encontre o primeiro elemento na lista deste agente com a mesma identidade e atualize a lista do primeiro agente para mostrar que eles têm a mesma identidade.

ＩＬΦθ⁼κ⌕θι

Conte o número de identidades únicas restantes.

Geléia , 25 15 bytes

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

Experimente online!

Um link monádico que obtém uma lista de reivindicações de agentes que separam o espaço e retorna o limite superior mais baixo do número de espiões distintos.

Explicação

  )              | 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

Agradecemos a @Arnauld e @JonathanAllan por identificar problemas nas versões anteriores e a @JonathanAllan novamente por salvar um byte! Se a especificação de entrada fosse relaxada para permitir uma lista de listas, isso economizaria um byte.

JavaScript (Node.js) , 120 bytes

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

Experimente online!

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

Casca , 12 bytes

LωomΣknṁoηkw

Experimente online!

Explicação

A idéia é criar uma lista de todos os grupos de espiões que são conhecidos por serem a mesma pessoa e, em seguida, mesclar progressivamente os grupos que se cruzam até que um ponto fixo seja alcançado. A saída é o número de grupos restantes que não puderam ser mesclados.

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 bytes

Obrigado recursivo

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))

Experimente online!

Ruby , 123 117 bytes

Usa uma idéia semelhante à solução Python 3 da movatica, mas calcula o menor índice de espião para cada "árvore" de uma maneira ligeiramente diferente (acompanhando os perfis encontrados anteriormente, encontrando uma sobreposição, se houver, e combinando-os)

-6 bytes 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}

Experimente online!

Explicação

->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 bytes

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

Experimente online!

8 bytes thx para wilkben .

Limpo , 137 bytes

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..]]))

Experimente online!

Associa as strings usadas pelos agentes ao número da linha em que aparecem para impedir a igualdade entre os agentes, depois verifica repetidamente se alguma frase de qualquer posição se sobrepõe e conta o número de conjuntos resultantes.

PHP , 271 bytes

Isso não funcionará se qualquer uma das identidades forem apenas números, pois eu armazeno o "número do espião" nas identidades. Eu não acho que seria difícil consertar isso.

$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)));

Experimente online!

Explicação

Meio que me confundi escrevendo isso, mas funciona para todos os casos de teste!

$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

Experimente online!