Walczysz z rozległą siecią szpiegów wroga . Wiesz, że każdy szpieg ma co najmniej jedną (czasem wielokrotną) fałszywą tożsamość, której lubią używać. Naprawdę chciałbyś wiedzieć, z iloma szpiegami faktycznie masz do czynienia.

Na szczęście twoi agenci kontrwywiadu wykonują swoją pracę i czasami mogą dowiedzieć się, kiedy dwie fałszywe tożsamości są faktycznie kontrolowane przez tego samego szpiega wroga.

To jest do powiedzenia:

• Twoi agenci nie zawsze wiedzą jednak, kiedy dwie fałszywe tożsamości mają za sobą tego samego szpiega
• Jeśli agent powie ci, że dwie fałszywe tożsamości są kontrolowane przez tego samego szpiega, masz nadzieję, że mają rację.

Wiadomości agenta

Agenci wysyłają ci tajemnicze wiadomości informujące, które tożsamości mają za sobą tego samego szpiega. Przykład:

Masz do czynienia z 2 agentami i 5 fałszywymi tożsamościami .

Pierwszy agent wysyła Ci wiadomość:

Red Red Blue Orange Orange

Oznacza to, że myślą, że są 3 szpiedzy:

• pierwszy (czerwony) kontroluje tożsamość 1 i 2
• drugi (niebieski) kontroluje tożsamość 3
• trzeci (pomarańczowy) kontroluje tożsamość 4 i 5

Drugi agent wysyła Ci wiadomość:

cat dog dog bird fly

Oznacza to, że myślą, że są 4 szpiedzy:

• pierwszy (kot) kontroluje tożsamość 1
• drugi (pies) kontroluje tożsamość 2 i 3
• trzeci (ptak) kontroluje tożsamość 4
• czwarty (mucha) kontroluje tożsamość 5

Kompilujemy informacje, które widzimy:

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

Oznacza to, że jest maksymalnie 2 szpiegów .

Notatki

Tożsamości należące do tego samego szpiega nie muszą być następujące po sobie, tzn. Wiadomość taka jak:

dog cat dog

jest ważny.

To samo słowo może być również używane przez dwóch różnych agentów - to nic nie znaczy, to tylko zbieg okoliczności, np .:

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

Lód jest używany przez oba agenty - Iceużywany przez pierwszego agenta nie jest związany z dwoma przypadkami Iceużycia przez drugiego agenta.

Wyzwanie

Zbierz wszystkie dane wywiadowcze swoich agentów i dowiedz się, ilu naprawdę jest szpiegów wroga. (Mówiąc ściślej, uzyskaj najniższą górną granicę, biorąc pod uwagę ograniczoną liczbę posiadanych informacji).

Najkrótszy kod w bajtach wygrywa.

Dane wejściowe i wyjściowe

Dane wejściowe to lista n linii, które reprezentują n wiadomości od agentów. Każda linia składa się z k oddzielonych spacjami tokenów, takich samych k dla wszystkich linii. Tokeny są alfanumeryczne, o dowolnej długości. Sprawa ma znaczenie.

Wynik powinien być pojedynczą liczbą, reprezentującą liczbę różnych szpiegów, na podstawie danych wywiadowczych twoich agentów.

Przykłady

Przykład 1

Wkład:

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

Wydajność:

2

Przykład 2

Wkład:

Blossom Bubbles Buttercup
Ed Edd Eddy

Wydajność:

3

Przykład 3

Wkład:

Botswana Botswana Botswana
Left Middle Right

Wydajność:

1

Przykład 4

Wkład:

Black White
White Black

Wydajność:

2

Przykład 5

Wkład:

Foo Bar Foo
Foo Bar Bar

Wydajność:

1

Przykład 6

Wkład:

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

Wydajność:

1

Przykład 7

Wkład:

A B A C

Wydajność:

3

Przykład 8

Wkład:

A
B
C

Wydajność:

1

Przykład 9

Wkład:

X

Wydajność:

1

Młot 0,5.1 , 16 15 bajtów

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

Dekompresuje się do tej funkcji języka Wolfram (wersja ostateczna &jest domyślna):

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

Wypróbuj online!

Transpose[StringSplit @ #1]: Podziel każdy ciąg na liście wejściowej i zabierz kolumny (tożsamości szpiegowskie)

RelationGraph[Inner[Equal, ##1, Or] &, ...]: Zbuduj wykres, na którym dwa wierzchołki dzielą krawędź, jeśli co najmniej jedna pozycja jest równa (jeśli są klasyfikowane przez tego samego agenta jako ten sam szpieg)

Length[ConnectedComponents[...]]: Liczba podłączonych komponentów jest górną granicą możliwej liczby szpiegów.

JavaScript (Node.js) ,  155 150 142  141 bajtów

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

Wypróbuj online!

W jaki sposób?

Dla każdej kolumny tworzymy maskę bitów połączonych kolumn (w tym ^tej kolumny). W końcu zwracamy liczbę różnych masek bitowych.$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   |
+---------+-------+-------+-------+-------+-------+-------+

Skomentował

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

Galaretka , 19 bajtów

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

Wypróbuj online!

Pobiera dane wejściowe jako listę oddzielonych spacjami wierszy (uwzględnia to stopka).

Uwaga: ḲŒQ)PSnie nie działa.

Python 3 , 132 162 154 139 135 bajtów

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

Wypróbuj online!

Jest to bardzo kompaktowa implementacja algorytmu grafowego identyfikującego klastry.

1. Dla każdego czynnika, tworzymy mapę profili i ich alias, który jest najniższy wskaźnik wygląd: [map(b.index,b)for b in map(str.split,a)]. To znaczy [0,1,2,1,2]identyfikuje trzech szpiegów, w których pierwszy profil należy do jednego, drugi i czwarty do drugiego, a trzeci i piąty do ostatniego. Indeks grupy jest także indeksem pierwszego profilu w grupie.

2. Transponując tę ​​macierz ( [*zip(*m...)]), otrzymujemy członkostwo w grupie dla każdego profilu. Tworzy to ukierunkowany, acykliczny wykres, ponieważ indeksy grupowe są podzbiorem indeksów profilu, a wszystkie krawędzie idą w kierunku indeksów niższych lub równych. Profile odpowiadające temu samemu szpiegowi tworzą teraz klaster bez połączeń z innymi profilami. Wciąż mamy jednak zduplikowane ścieżki, ponieważ indeksy profili są powiązane z indeksami wielu grup.

3. Za pomocą następujących pętli minimalizujemy wykres do płaskiego lasu, w którym wszystkie profile są połączone bezpośrednio z najniższym indeksem w drzewie, tj. Korzeniem: min(min(u)for u in r if min(w)in u)

4. Wreszcie zwraca liczbę korzeni w lesie, czyli wskaźniki związane z siebie: return sum(i==...).

Węgiel , 49 43 bajtów

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

Wypróbuj online! Link jest do pełnej wersji kodu. Mógłby zaoszczędzić kilka bajtów przy użyciu uciążliwego formatu wejściowego. Wyjaśnienie:

≔⪪Ｓ θ

Wprowadź listę pierwszego agenta.

ＷＳ«

Powtórz dla pozostałych agentów.

≔⪪ι ι

Wpisz ich listę.

ＦＬι

Pętla nad indeksem każdego elementu.

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

Znajdź pierwszy element na liście tego agenta o tej samej tożsamości i zaktualizuj listę pierwszego agenta, aby pokazać, że są one tej samej tożsamości.

ＩＬΦθ⁼κ⌕θι

Policz liczbę pozostałych unikalnych tożsamości.

Galaretka , 25 15 bajtów

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

Wypróbuj online!

Łącze monadyczne zawierające listę rozdzielających spacje oświadczeń agenta i zwracające najniższą górną granicę liczby różnych szpiegów.

Wyjaśnienie

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

Dzięki @Arnauld i @JonathanAllan za identyfikację problemów z poprzednimi wersjami oraz @JonathanAllan ponownie za zapisanie bajtu! Jeśli specyfikacja wejściowa została zmieniona, aby umożliwić listę list, zaoszczędziłoby to jeden bajt.

JavaScript (Node.js) , 120 bajtów

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

Wypróbuj 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

Łuska , 12 bajtów

LωomΣknṁoηkw

Wypróbuj online!

Wyjaśnienie

Chodzi o to, aby utworzyć listę wszystkich grup szpiegów, o których wiadomo, że to ta sama osoba, a następnie stopniowo łączyć przecinające się grupy, aż do osiągnięcia ustalonego punktu. Dane wyjściowe to liczba pozostałych grup, których nie można scalić.

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 bajty

Dziękuję rekursywnie

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

Wypróbuj online!

Ruby , 123 117 bajtów

Używa podobnego pomysłu do rozwiązania Movatica w języku Python 3, ale oblicza najniższy indeks szpiegowania dla każdego „drzewa” w nieco inny sposób (poprzez śledzenie wcześniej napotkanych profili, znajdowanie nakładki, jeśli istnieje, i łączenie ich)

-6 bajtów z @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}

Wypróbuj online!

Wyjaśnienie

->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 bajtów

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

Wypróbuj online!

8 bajtów dzięki za wilkben .

Czysty , 137 bajtów

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

Wypróbuj online!

Kojarzy ciągi używane przez agentów z numerem linii, w którym się pojawiają, aby zapobiec równości między agentami, a następnie wielokrotnie sprawdza, czy jakieś wyrażenia dla dowolnej pozycji nakładają się, i zlicza liczbę zestawów wynikowych.

PHP , 271 bajtów

To nie zadziała, jeśli którakolwiek z tożsamości to tylko liczby, ponieważ przechowuję „numer szpiegowski” wraz z tożsamościami. Nie sądzę jednak, żeby to było trudne.

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

Wypróbuj online!

Wyjaśnienie

Trochę zdezorientowałem się, pisząc to, ale działa to dla wszystkich przypadków testowych!

$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

Wypróbuj online!