Du kämpfst gegen ein ausgedehntes Netzwerk feindlicher Spione . Sie wissen, dass jeder Spion mindestens eine (manchmal mehrere) gefälschte Identität hat , die er gerne benutzt. Sie möchten wirklich wissen, mit wie vielen Spionen Sie tatsächlich zu tun haben.

Glücklicherweise Ihre Abwehrmittel ihre Arbeit tun und kann manchmal herausfinden , wenn zwei gefälschte Identitäten tatsächlich von demselben Feind Spion kontrolliert werden.

Das heißt:

• Ihre Agenten wissen jedoch nicht immer, wann zwei gefälschte Identitäten denselben Spion hinter sich haben
• Wenn Ihnen ein Agent sagt, dass zwei gefälschte Identitäten von demselben Spion kontrolliert werden, vertrauen Sie darauf, dass sie richtig sind.

Agentennachrichten

Agenten senden Ihnen kryptische Nachrichten, in denen Sie erfahren, welche Identitäten denselben Spion haben. Ein Beispiel:

Sie müssen mit 2 Agenten und 5 gefälschten Identitäten umgehen.

Der erste Agent sendet Ihnen eine Nachricht:

Red Red Blue Orange Orange

Das heißt, sie denken, es gibt 3 Spione:

• Der erste (rot) steuert die Identitäten 1 und 2
• der zweite (blau) kontrolliert Identität 3
• die dritte (orange) steuert die identitäten 4 und 5

Der zweite Agent sendet Ihnen eine Nachricht:

cat dog dog bird fly

Das heißt, sie denken, es gibt 4 Spione:

• Die erste (Katze) kontrolliert Identität 1
• der zweite (Hund) kontrolliert die Identitäten 2 und 3
• der dritte (Vogel) kontrolliert Identität 4
• die vierte (Fliege) kontrolliert die Identität 5

Kompilieren der Informationen, die wir sehen:

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

Das heißt, es gibt höchstens 2 Spione .

Anmerkungen

Identitäten, die demselben Spion gehören, müssen nicht aufeinanderfolgend sein, dh eine Nachricht wie:

dog cat dog

ist gültig.

Das gleiche Wort könnte auch von zwei verschiedenen Agenten verwendet werden - das bedeutet nichts, es ist nur ein Zufall, zB:

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

Eis wird von beiden Agenten verwendet - das Eis, das vom Iceersten Agenten verwendet wird, hat nichts mit den beiden Vorkommen des Eises zu tun, Icedas vom zweiten Agenten verwendet wird.

Herausforderung

Stellen Sie alle Informationen Ihrer Agenten zusammen und finden Sie heraus, wie viele feindliche Spione es tatsächlich gibt. (Um genauer zu sein, erhalten Sie die niedrigste Obergrenze, wenn Sie die begrenzten Informationen haben.)

Der kürzeste Code in Bytes gewinnt.

Eingangs- und Ausgangsspezifikation

Die Eingabe ist eine Liste von n Zeilen, die n Nachrichten von Agenten darstellen. Jede Zeile besteht aus k durch Leerzeichen getrennten Token, wobei k für alle Zeilen gleich ist. Token sind alphanumerisch und beliebig lang. Der Fall ist wichtig.

Die Ausgabe sollte eine einzelne Zahl sein, die die Anzahl der unterschiedlichen Spione darstellt, basierend auf den Informationen Ihrer Agenten.

Beispiele

Beispiel 1

Eingang:

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

Ausgabe:

2

Beispiel 2

Eingang:

Blossom Bubbles Buttercup
Ed Edd Eddy

Ausgabe:

3

Beispiel 3

Eingang:

Botswana Botswana Botswana
Left Middle Right

Ausgabe:

1

Beispiel 4

Eingang:

Black White
White Black

Ausgabe:

2

Beispiel 5

Eingang:

Foo Bar Foo
Foo Bar Bar

Ausgabe:

1

Beispiel 6

Eingang:

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

Ausgabe:

1

Beispiel 7

Eingang:

A B A C

Ausgabe:

3

Beispiel 8

Eingang:

A
B
C

Ausgabe:

1

Beispiel 9

Eingang:

X

Ausgabe:

1

Vorschlaghammer 0.5.1 , 16 15 Bytes

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

Dekomprimiert in diese Wolfram Language-Funktion (das Finale &ist implizit):

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

Probieren Sie es online!

Transpose[StringSplit @ #1]: Teile jede Zeichenkette in der Eingabeliste auf und nimm die Spalten (Spionidentitäten)

RelationGraph[Inner[Equal, ##1, Or] &, ...]: Konstruiere den Graphen, in dem zwei Eckpunkte eine Kante teilen, wenn mindestens eine Position gleich ist (wenn sie von einem befreundeten Agenten als derselbe Spion klassifiziert wurden).

Length[ConnectedComponents[...]]: Die Anzahl der verbundenen Komponenten ist die Obergrenze für die mögliche Anzahl der Spione.

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

Probieren Sie es online!

Wie?

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

Kommentiert

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

Jelly , 19 Bytes

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

Probieren Sie es online!

Nimmt Eingaben als Liste mit durch Leerzeichen getrennten Zeilen (die Fußzeile berücksichtigt dies).

Hinweis: ḲŒQ)PSfunktioniert nicht .

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

Probieren Sie es online!

Dies ist eine sehr kompakte Implementierung eines Graph-Algorithmus, der Cluster identifiziert.

1. Für jeden Agenten, erstellen wir eine Karte von Profilen und deren Alias, das der niedrigste Index der Erscheinung ist: [map(b.index,b)for b in map(str.split,a)]. Dh [0,1,2,1,2]identifiziert drei Spione, wobei das erste Profil zu einem gehört, das zweite und vierte zu einem anderen und das dritte und fünfte zu dem letzten. Der Gruppenindex ist auch der Index des ersten Profils in der Gruppe.

2. Durch die Transposition dieser Matrix ( [*zip(*m...)]) erhalten wir eine Gruppenmitgliedschaft für jedes Profil. Dies bildet einen gerichteten, azyklischen Graphen, da die Gruppenindizes eine Teilmenge der Profilindizes sind und alle Kanten zu niedrigeren oder gleichen Indizes weisen. Profile, die demselben Spion entsprechen, bilden jetzt einen Cluster ohne Verbindungen zu den anderen Profilen. Es gibt jedoch immer noch doppelte Pfade, da Profilindizes mit mehreren Gruppenindizes verknüpft sind.

3. Mit den folgenden Schleifen minimieren wir den Graphen auf eine flache Gesamtstruktur, in der alle Profile direkt mit dem niedrigsten Index in ihrem Baum, dh der Wurzel, verknüpft sind: min(min(u)for u in r if min(w)in u)

4. Schließlich gibt die Anzahl der Wurzeln in dem Wald, dh Indizes selbst verbunden: return sum(i==...).

Kohle , 49 43 Bytes

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

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Könnte möglicherweise ein paar Bytes sparen, wenn ein umständliches Eingabeformat verwendet wird. Erläuterung:

≔⪪Ｓ θ

Geben Sie die Liste des ersten Agenten ein.

ＷＳ«

Wiederholen Sie dies für die restlichen Agenten.

≔⪪ι ι

Geben Sie ihre Liste ein.

ＦＬι

Schleife über jeden Elementindex.

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

Suchen Sie das erste Element in der Liste dieses Agenten mit derselben Identität und aktualisieren Sie die Liste des ersten Agenten, um anzuzeigen, dass es sich um dieselbe Identität handelt.

ＩＬΦθ⁼κ⌕θι

Zählen Sie die Anzahl der verbleibenden eindeutigen Identitäten.

Jelly , 25 15 Bytes

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

Probieren Sie es online!

Ein monadischer Link, der eine Liste von durch Leerzeichen getrennten Agenten-Ansprüchen erstellt und die unterste obere Schranke der Anzahl unterschiedlicher Spione zurückgibt.

Erläuterung

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

Vielen Dank an @Arnauld und @JonathanAllan für die Identifizierung von Problemen mit früheren Versionen und nochmals an @JonathanAllan für das Speichern eines Bytes! Wenn die Eingabespezifikation gelockert würde, um eine Liste von Listen zuzulassen, würde dies ein Byte sparen.

JavaScript (Node.js) , 120 Byte

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

Probieren Sie es 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

Schale , 12 Bytes

LωomΣknṁoηkw

Probieren Sie es online!

Erläuterung

Die Idee ist, eine Liste aller Gruppen von Spionen zu erstellen, von denen bekannt ist, dass sie dieselbe Person sind, und dann sich überschneidende Gruppen schrittweise zusammenzuführen, bis ein fester Punkt erreicht ist. Die Ausgabe ist die Anzahl der verbleibenden Gruppen, die nicht zusammengeführt werden konnten.

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

Danke rekursiv

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

Probieren Sie es online!

Ruby , 123 bis 117 Bytes

Verwendet eine ähnliche Idee wie die Python 3-Lösung von movatica , berechnet jedoch den niedrigsten Spionageindex für jeden "Baum" auf eine etwas andere Art und Weise (indem Sie zuvor aufgetretene Profile verfolgen, eine Überlappung finden, falls vorhanden, und diese kombinieren).

-6 Bytes von @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}

Probieren Sie es online!

Erläuterung

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

Probieren Sie es online!

8 Bytes Danke an Wilkben .

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

Probieren Sie es online!

Verknüpft die von den Agenten verwendeten Zeichenfolgen mit der Zeilennummer, die in angezeigt wird, um die Gleichheit zwischen Agenten zu verhindern, und überprüft dann wiederholt, ob sich Phrasen für eine Position überlappen, und zählt die Anzahl der resultierenden Mengen.

PHP , 271 Bytes

Dies funktioniert nicht, wenn es sich bei einer der Identitäten nur um Zahlen handelt, da ich die "Spionage-Nummer" mit den Identitäten speichere. Ich glaube nicht, dass es schwierig wäre, das zu beheben.

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

Probieren Sie es online!

Erläuterung

Irgendwie verwirrte mich das zu schreiben, aber es funktioniert für alle Testfälle!

$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

Probieren Sie es online!