Вы сражаетесь с обширной сетью вражеских шпионов . Вы знаете, что у каждого шпиона есть хотя бы одна (иногда множественная) фальшивая личность, которую они любят использовать. Вам бы очень хотелось узнать, сколько шпионов вы имеете дело с.

К счастью, ваши агенты контрразведки выполняют свою работу и иногда могут выяснить, когда две поддельные личности фактически контролируются одним и тем же вражеским шпионом.

То есть:

• Ваши агенты не всегда знают, когда за двумя поддельными личностями стоит один и тот же шпион
• Если агент говорит вам, что две поддельные личности контролируются одним и тем же шпионом, вы уверены, что они правы.

Сообщения агента

Агенты отправляют вам загадочные сообщения, сообщающие, у каких личностей за спиной стоит один и тот же шпион. Пример:

У вас есть 2 агента и 5 поддельных личностей, чтобы иметь дело с.

Первый агент отправляет вам сообщение:

Red Red Blue Orange Orange

Это означает, что они думают, что есть 3 шпиона:

• первый (красный) контролирует тождества 1 и 2
• второй (синий) контролирует личность 3
• третий (оранжевый) контролирует личности 4 и 5

Второй агент отправляет вам сообщение:

cat dog dog bird fly

Это означает, что они думают, что есть 4 шпиона:

• первый (кот) контролирует личность 1
• второй (собака) контролирует личности 2 и 3
• третий (птица) контролирует личность 4
• четвертый (муха) контролирует личность 5

Компилируя информацию мы видим:

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

Это означает, что есть не более 2 шпионов .

Заметки

Идентификационные данные, принадлежащие одному и тому же шпиону, не обязательно должны быть последовательными, то есть сообщение вроде:

dog cat dog

действует.

Кроме того, одно и то же слово может использоваться двумя разными агентами - это ничего не значит, это просто совпадение, например:

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

Лед используется обоими агентами - Iceиспользуемый первым агентом не связан с двумя случаями Iceиспользования второго агента.

Вызов

Скомпилируйте информацию всех ваших агентов и выясните, сколько в действительности шпионов противника. (Точнее, получите самую низкую верхнюю границу, учитывая имеющуюся у вас ограниченную информацию.)

Самый короткий код в байтах побеждает.

Спецификация входа и выхода

Входные данные представляют собой список из n строк, которые представляют n сообщений от агентов. Каждая строка состоит из k разделенных пробелами токенов, одинаковых k для всех строк. Жетоны имеют буквенно-цифровую, произвольную длину. Дело имеет значение.

Вывод должен быть одним числом, представляющим количество различных шпионов, основанных на интеллекте ваших агентов.

Примеры

Пример 1

Входные данные:

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

Выход:

2

Пример 2

Входные данные:

Blossom Bubbles Buttercup
Ed Edd Eddy

Выход:

3

Пример 3

Входные данные:

Botswana Botswana Botswana
Left Middle Right

Выход:

1

Пример 4

Входные данные:

Black White
White Black

Выход:

2

Пример 5

Входные данные:

Foo Bar Foo
Foo Bar Bar

Выход:

1

Пример 6

Входные данные:

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

Выход:

1

Пример 7

Входные данные:

A B A C

Выход:

3

Пример 8

Входные данные:

A
B
C

Выход:

1

Пример 9

Входные данные:

X

Выход:

1

Кувалда 0.5.1 , 16 15 байт

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

Распаковывается в эту функцию языка Wolfram Language (финал &неявный):

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

Попробуйте онлайн!

Transpose[StringSplit @ #1]: Разделить каждую строку в списке ввода и взять столбцы (шпионские идентификаторы)

RelationGraph[Inner[Equal, ##1, Or] &, ...]: Построить график, где две вершины разделяют ребро, если хотя бы одна позиция равна (если они классифицированы как один и тот же шпион каким-то дружественным агентом)

Length[ConnectedComponents[...]]: Количество подключенных компонентов является верхней границей возможного количества шпионов.

JavaScript (Node.js) ,  155 150 142  141 байт

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

Попробуйте онлайн!

Как?

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

комментарии

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

Желе , 19 байт

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

Попробуйте онлайн!

Вводит в виде списка разделенных пробелами строк (это объясняется нижним колонтитулом).

Примечание: ḲŒQ)PSэто не работает.

Python 3 , 132 162 154 139 135 байтов

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

Попробуйте онлайн!

Это очень компактная реализация алгоритма графа, идентифицирующего кластеры.

1. Для каждого агента, мы создаем карту профилей и их псевдоним, который является самым низким показателем появления: [map(b.index,b)for b in map(str.split,a)]. Т.е.[0,1,2,1,2] определяются три шпиона, где первый профиль принадлежит одному, второй и четвертый - другому, а третий и пятый - последнему. Индекс группы также является индексом первого профиля в группе.

2. Транспонируя эту матрицу ( [*zip(*m...)]), мы получаем членство в группе для каждого профиля. Это формирует направленный, ациклический граф, потому что индексы группы являются подмножеством индексов профиля, и все ребра идут к более низким или равным индексам. Профили, соответствующие одному и тому же шпиону, теперь образуют кластер без подключений к другим профилям. У нас все еще есть повторяющиеся пути, потому что индексы профиля связаны с индексами нескольких групп.

3. С помощью следующих циклов мы минимизируем граф до плоского леса, где все профили связаны непосредственно с самым низким индексом в их дереве, то есть с корнем: min(min(u)for u in r if min(w)in u)

4. И, наконец, возвращает количество корней в лесу, то есть показатели , связанные с собой: return sum(i==...).

Древесный уголь , 49 43 байта

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

Попробуйте онлайн! Ссылка на подробную версию кода. Возможно, можно сэкономить пару байтов, используя громоздкий формат ввода. Объяснение:

≔⪪Ｓ θ

Введите список первого агента.

ＷＳ«

Повторите для остальных агентов.

≔⪪ι ι

Введите их список.

ＦＬι

Цикл по каждому элементу индекса.

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

Найдите первый элемент в списке этого агента с той же идентификационной информацией и обновите список первого агента, чтобы показать, что они имеют одинаковую идентификационную информацию.

ＩＬΦθ⁼κ⌕θι

Подсчитайте количество оставшихся уникальных идентификаторов.

Желе , 25 15 байт

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

Попробуйте онлайн!

Монадическая ссылка, принимающая список разделенных пробелами утверждений агента и возвращающая нижнюю верхнюю границу числа различных шпионов.

объяснение

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

Спасибо @Arnauld и @JonathanAllan за выявление проблем с предыдущими версиями и еще раз @JonathanAllan за сохранение байта! Если входная спецификация была ослаблена, чтобы разрешить список списков, это спасло бы один байт.

JavaScript (Node.js) , 120 байт

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

Попробуйте онлайн!

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

Шелуха , 12 байт

LωomΣknṁoηkw

Попробуйте онлайн!

объяснение

Идея состоит в том, чтобы создать список всех групп шпионов, которые, как известно, являются одним и тем же человеком, затем постепенно объединять пересекающиеся группы, пока не будет достигнута фиксированная точка. Выходными данными является количество оставшихся групп, которые не могут быть объединены.

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 байта

Спасибо рекурсивный

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

Попробуйте онлайн!

Рубин , 123 117 байт

Использует идею, аналогичную решению Python 3 от Movatica, но вычисляет самый низкий индекс шпиона для каждого «дерева» немного по-другому (отслеживая ранее обнаруженные профили, находя перекрытия, если оно существует, и комбинируя их)

-6 байт из @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}

Попробуйте онлайн!

объяснение

->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 байт

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

Попробуйте онлайн!

8 байтов, спасибо Вилкбену .

Чисто , 137 байт

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

Попробуйте онлайн!

Связывает строки, используемые агентами, с номером строки, в котором они появляются, чтобы предотвратить равенство между агентами, затем повторно проверяет, перекрываются ли какие-либо фразы для какой-либо позиции, и подсчитывает количество результирующих наборов.

PHP , 271 байт

Это не сработает, если какие-либо идентификаторы являются просто числами, так как я храню «номер шпиона» вместе с идентификаторами. Я не думаю, что это будет трудно исправить, хотя.

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

Попробуйте онлайн!

объяснение

Вроде как я запутался в написании этого, но это работает для всех тестов

$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

Попробуйте онлайн!