Anda sedang memerangi jaringan mata-mata musuh yang luas . Anda tahu bahwa setiap mata-mata memiliki setidaknya satu (kadang-kadang banyak) identitas palsu yang mereka suka gunakan. Anda benar-benar ingin tahu berapa banyak mata-mata yang Anda hadapi sebenarnya.

Untungnya, agen kontra-intelijen Anda melakukan pekerjaan mereka dan kadang - kadang dapat mengetahui kapan dua identitas palsu sebenarnya dikendalikan oleh mata-mata musuh yang sama.

Artinya:

• Agen Anda tidak selalu tahu kapan dua identitas palsu memiliki mata-mata yang sama di belakang mereka
• Jika seorang agen memberi tahu Anda dua identitas palsu dikendalikan oleh mata-mata yang sama, Anda yakin itu benar.

Pesan agen

Agen mengirimi Anda pesan rahasia yang memberi tahu Anda identitas mana yang memiliki mata-mata yang sama di belakangnya. Sebuah contoh:

Anda memiliki 2 agen dan 5 identitas palsu untuk ditangani.

Agen pertama mengirimi Anda pesan:

Red Red Blue Orange Orange

Ini berarti mereka berpikir ada 3 mata-mata:

• yang pertama (Merah) mengontrol identitas 1 dan 2
• yang kedua (Biru) mengontrol identitas 3
• yang ketiga (Oranye) mengontrol identitas 4 dan 5

Agen kedua mengirimi Anda pesan:

cat dog dog bird fly

Ini berarti mereka berpikir ada 4 mata-mata:

• yang pertama (kucing) mengontrol identitas 1
• yang kedua (anjing) mengontrol identitas 2 dan 3
• yang ketiga (burung) mengontrol identitas 4
• yang keempat (terbang) mengontrol identitas 5

Kompilasi intel yang kita lihat:

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

Ini berarti ada paling banyak 2 mata-mata .

Catatan

Identitas yang dimiliki oleh mata-mata yang sama tidak harus berturut-turut, yaitu pesan seperti:

dog cat dog

adalah benar.

Juga, kata yang sama dapat digunakan oleh dua agen yang berbeda - itu tidak berarti apa-apa, itu hanya kebetulan, misalnya:

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

Es digunakan oleh kedua agen - yang Icedigunakan oleh agen pertama tidak terkait dengan dua kejadian yang Icedigunakan oleh agen kedua.

Tantangan

Kompilasi semua intel agen Anda dan cari tahu berapa banyak mata-mata musuh yang ada. (Untuk lebih tepatnya, dapatkan batas atas terendah, mengingat informasi terbatas yang Anda miliki.)

Kode terpendek dalam byte menang.

Input dan Output spec

Input adalah daftar n baris, yang mewakili n pesan dari agen. Setiap baris terdiri dari k token yang dipisahkan ruang, sama k untuk semua baris. Token adalah alfanumerik, panjang arbitrer. Kasus penting.

Outputnya harus berupa angka tunggal, mewakili jumlah mata-mata yang berbeda, berdasarkan intel agen Anda.

Contohnya

Contoh 1

Memasukkan:

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

Keluaran:

2

Contoh 2

Memasukkan:

Blossom Bubbles Buttercup
Ed Edd Eddy

Keluaran:

3

Contoh 3

Memasukkan:

Botswana Botswana Botswana
Left Middle Right

Keluaran:

1

Contoh 4

Memasukkan:

Black White
White Black

Keluaran:

2

Contoh 5

Memasukkan:

Foo Bar Foo
Foo Bar Bar

Keluaran:

1

Contoh 6

Memasukkan:

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

Keluaran:

1

Contoh 7

Memasukkan:

A B A C

Keluaran:

3

Contoh 8

Memasukkan:

A
B
C

Keluaran:

1

Contoh 9

Memasukkan:

X

Keluaran:

1

Sledgehammer 0.5.1 , 16 15 byte

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

Mengekompres ke dalam fungsi Bahasa Wolfram ini (yang terakhir &adalah implisit):

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

Cobalah online!

Transpose[StringSplit @ #1]: Pisahkan setiap string dalam daftar input, dan ambil kolom (identitas mata-mata)

RelationGraph[Inner[Equal, ##1, Or] &, ...]: Buat grafik di mana dua simpul berbagi tepi jika setidaknya satu posisi sama (jika mereka diklasifikasikan sebagai mata-mata yang sama oleh beberapa agen ramah)

Length[ConnectedComponents[...]]: Jumlah komponen yang terhubung adalah batas atas jumlah mata-mata yang memungkinkan.

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

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

Cobalah online!

Bagaimana?

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

Berkomentar

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 byte

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

Cobalah online!

Mengambil input sebagai daftar garis yang dipisahkan spasi (catatan kaki untuk itu).

Catatan: ḲŒQ)PStidak tidak bekerja.

Python 3 , 132 162 154 139 135 byte

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

Cobalah online!

Ini adalah implementasi yang sangat kompak dari algoritma pengidentifikasi grafik cluster.

1. Untuk setiap agen, kita membuat peta profil dan alias mereka, yang merupakan indeks terendah penampilan: [map(b.index,b)for b in map(str.split,a)]. Yaitu [0,1,2,1,2]mengidentifikasi tiga mata-mata, di mana profil pertama milik satu, yang kedua dan keempat yang lain dan yang ketiga dan kelima ke yang terakhir. Indeks grup juga merupakan indeks dari profil pertama dalam grup.

2. Dengan mentransposkan matriks ini ( [*zip(*m...)]), kami mendapatkan keanggotaan grup untuk setiap profil. Ini membentuk, grafik asiklik diarahkan, karena indeks grup adalah subset dari indeks profil, dan semua tepi menuju indeks yang lebih rendah atau sama. Profil yang sesuai dengan mata-mata yang sama sekarang membentuk sebuah cluster tanpa koneksi ke profil lain. Kami masih memiliki jalur duplikat, karena indeks profil ditautkan ke beberapa indeks grup.

3. Dengan loop berikut, kami meminimalkan grafik ke hutan datar, di mana semua profil dihubungkan langsung ke indeks terendah di pohon mereka, yaitu root: min(min(u)for u in r if min(w)in u)

4. Akhirnya, kembali jumlah akar di hutan, indeks yaitu terkait dengan diri mereka sendiri: return sum(i==...).

Arang , 49 43 byte

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

Cobalah online! Tautan adalah untuk mengucapkan versi kode. Mungkin dapat menyimpan beberapa byte dengan menggunakan format input yang rumit. Penjelasan:

≔⪪Ｓ θ

Masukkan daftar agen pertama.

ＷＳ«

Ulangi untuk agen yang tersisa.

≔⪪ι ι

Masukkan daftar mereka.

ＦＬι

Ulangi setiap indeks elemen.

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

Temukan elemen pertama dalam daftar agen ini dengan identitas yang sama dan perbarui daftar agen pertama untuk menunjukkan bahwa mereka adalah identitas yang sama.

ＩＬΦθ⁼κ⌕θι

Hitung jumlah identitas unik yang tersisa.

Jelly , 25 15 byte

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

Cobalah online!

Tautan monadik mengambil daftar klaim agen pemisah ruang dan mengembalikan batas atas terendah dari jumlah mata-mata yang berbeda.

Penjelasan

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

Terima kasih kepada @Arnauld dan @JonathanAllan untuk mengidentifikasi masalah dengan versi sebelumnya, dan @JonathanAllan lagi untuk menghemat byte! Jika spek input dilonggarkan untuk memungkinkan daftar daftar, ini akan menghemat satu byte.

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

Cobalah 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

Sekam , 12 byte

LωomΣknṁoηkw

Cobalah online!

Penjelasan

Idenya adalah untuk membuat daftar semua kelompok mata-mata yang dikenal sebagai orang yang sama, kemudian secara progresif menggabungkan kelompok-kelompok yang berpotongan sampai titik tetap tercapai. Outputnya adalah jumlah grup yang tersisa yang tidak dapat digabungkan.

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 byte

Terima kasih, rekursif

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

Cobalah online!

Ruby , 123 117 byte

Menggunakan ide yang mirip dengan solusi Python 3 movatica tetapi menghitung indeks mata-mata terendah untuk setiap "pohon" dengan cara yang sedikit berbeda (dengan melacak profil yang ditemukan sebelumnya, menemukan tumpang tindih jika ada, dan menggabungkannya)

-6 byte dari @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}

Cobalah online!

Penjelasan

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

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

Cobalah online!

8 byte thx ke wilkben .

Bersihkan , 137 byte

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

Cobalah online!

Mengaitkan string yang digunakan oleh agen dengan nomor baris yang muncul untuk mencegah kesetaraan di seluruh agen, lalu berulang kali memeriksa apakah ada frasa untuk posisi apa pun yang tumpang tindih dan menghitung jumlah set yang dihasilkan.

PHP , 271 byte

Ini tidak akan berfungsi jika salah satu identitas hanyalah angka ketika saya menyimpan "nomor mata-mata" dengan identitas. Saya tidak berpikir itu tidak akan sulit untuk memperbaikinya.

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

Cobalah online!

Penjelasan

Agak bingung sendiri menulis ini tetapi berfungsi untuk semua kasus uji!

$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

Cobalah online!