38
\$\begingroup\$

You are fighting an extensive network of enemy spies. You know that each spy has at least one (sometimes multiple) fake identities they like to use. You'd really like to know how many spies you're actually dealing with.

Luckily, your counter-intelligence agents are doing their job and can sometimes figure out when two fake identities are actually controlled by the same enemy spy.

That is to say:

  • Your agents don't always know when two fake identies have the same spy behind them, however
  • If an agent tells you two fake identities are controlled by the same spy, you trust they are right.

Agent messages

Agents send you cryptic messages telling you which identities have the same spy behind them. An example:

You have 2 agents and 5 fake identities to deal with.

The first agent sends you a message:

Red Red Blue Orange Orange

This means they think there are 3 spies:

  • the first one (Red) controls identities 1 and 2
  • the second one (Blue) controls identity 3
  • the third one (Orange) controls identities 4 and 5

The second agent sends you a message:

cat dog dog bird fly

This means they think there are 4 spies:

  • the first one (cat) controls identity 1
  • the second one (dog) controls identities 2 and 3
  • the third one (bird) controls identity 4
  • the fourth one (fly) controls identity 5

Compiling the intel we see:

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

This means there are at most 2 spies.

Notes

Identities owned by the same spy do not have to be consecutive, i.e. a message like:

dog cat dog

is valid.

Also, the same word might be used by two different agents - that does not mean anything, it's just a coincidence, e.g.:

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

Ice is used by both agents - the Ice used by the first agent is unrelated to the two occurences of Ice used by the second agent.

Challenge

Compile all your agents' intel and figure out how many enemy spies there really are. (To be more precise, get the lowest upper bound, given the limited information you have.)

The shortest code in bytes wins.

Input and Output spec

The input is a list of n lines, which represent n messages from agents. Each line consists of k space-separated tokens, same k for all lines. Tokens are alphanumeric, arbitrary length. Case matters.

The output should be a single number, representing the number of distinct spies, based on your agents' intel.

Examples

Example 1

Input:

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

Output:

2

Example 2

Input:

Blossom Bubbles Buttercup
Ed Edd Eddy

Output:

3

Example 3

Input:

Botswana Botswana Botswana
Left Middle Right

Output:

1

Example 4

Input:

Black White
White Black

Output:

2

Example 5

Input:

Foo Bar Foo
Foo Bar Bar

Output:

1

Example 6

Input:

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

Output:

1

Example 7

Input:

A B A C

Output:

3

Example 8

Input:

A
B
C

Output:

1

Example 9

Input:

X

Output:

1
\$\endgroup\$
  • \$\begingroup\$ May we take each line as an array of words? \$\endgroup\$ – Arnauld Jul 13 at 12:56
  • 8
    \$\begingroup\$ @HenryHenrinson The only thing making the input strict does is add a short blurb at the start of the code to change the input format. It doesn't really add anything to the challenge itself \$\endgroup\$ – fəˈnɛtɪk Jul 13 at 14:42
  • 6
    \$\begingroup\$ Sounds to me like that will give more opportunities to golf the code :) \$\endgroup\$ – Henry Henrinson Jul 13 at 15:50
  • 17
    \$\begingroup\$ Strict I/O formats are really discouraged since they detract from the core of the challenge. For example, enforcing that the input is in form of lines of space-separated words isn't necessary, since one can also represent each line as a list of words (what Arnauld said), and the only thing this rule adds to the challenge is the necessity to split the lines, something that's not necessarily a part of the challenge. \$\endgroup\$ – Erik the Outgolfer Jul 13 at 22:35
  • 2
    \$\begingroup\$ This title sounds like your average Team Fortress 2 game! \$\endgroup\$ – Tvde1 Jul 16 at 15:43

13 Answers 13

10
\$\begingroup\$

Sledgehammer 0.5.1, 16 15 bytes

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

Decompresses into this Wolfram Language function (the final & is implicit):

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

Try it online!

Transpose[StringSplit @ #1]: Split each string in the input list, and take the columns (spy identities)

RelationGraph[Inner[Equal, ##1, Or] &, ...]: Construct the graph where two vertices share an edge if at least one position is equal (if they are classified as the same spy by some friendly agent)

Length[ConnectedComponents[...]]: The number of connected components is the upper bound on the possible number of spies.

\$\endgroup\$
9
\$\begingroup\$

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

Try it online!

How?

For each column \$x\$, we build a bitmask \$m\$ of linked columns (including the \$x\$th column). We eventually return the number of distinct bitmasks.

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

Commented

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
\$\endgroup\$
  • \$\begingroup\$ So... in practice, this would have a 32 or 64 identity limit? \$\endgroup\$ – Vilx- Jul 15 at 22:14
  • \$\begingroup\$ @Vilx- I think he could switch to BigInt, although that would cost bytes of course. \$\endgroup\$ – Neil Jul 16 at 19:24
6
\$\begingroup\$

Jelly, 19 bytes

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

Try it online!

Takes input as a list of space-separated lines (the footer accounts for that).

Note: ḲŒQ)PS does not work.

\$\endgroup\$
6
\$\begingroup\$

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

Try it online!

This is a very compact implementation of a graph algorithm identifying clusters.

  1. For each agent, we create a map of profiles and their alias, which is the lowest index of appearance: [map(b.index,b)for b in map(str.split,a)]. I.e. [0,1,2,1,2] identifies three spies, where the first profile belongs to one, the second and fourth to another one and the third and fifth to the last one. The group index is also the index of the first profile in the group.

  2. By transposing this matrix ([*zip(*m...)]), we get a group membership for each profile. This forms a directed, acyclic graph, because the group indices are a subset of the profile indices, and all edges go towards lower or equal indices. Profiles corresponding to the same spy now form a cluster with no connections to the other profiles. We still have duplicate paths though, because profile indices are linked to multiple groups indices.

  3. With the following loops, we minimize the the graph to a flat forest, where all profiles are linked directly to the lowest index in their tree, i.e. the root: min(min(u)for u in r if min(w)in u)

  4. Finally, return the number of roots in the forest, i.e. indices linked to themselves: return sum(i==...).

\$\endgroup\$
  • \$\begingroup\$ is the indentation necessary? it has been ages since I used python, but I seem to remember that you can make oneliners. \$\endgroup\$ – Mark Gardner Jul 14 at 14:24
  • \$\begingroup\$ You can, but not if you use nested for loops. TIO for yourself ;) \$\endgroup\$ – movatica Jul 14 at 14:38
5
\$\begingroup\$

Charcoal, 49 43 bytes

≔⪪S θWS«≔⪪ι ιFLιUMθ⎇⁼λ§θκ§θ⌕ι§ικλ»ILΦθ⁼κ⌕θι

Try it online! Link is to verbose version of code. Could possibly save a couple of bytes by using a cumbersome input format. Explanation:

≔⪪S θ

Input the first agent's list.

WS«

Repeat for the remaining agents.

≔⪪ι ι

Input their list.

FLι

Loop over each element index.

UMθ⎇⁼λ§θκ§θ⌕ι§ικλ»

Find the first element in this agent's list with the same identity and update the first agent's list to show that they are the same identity.

ILΦθ⁼κ⌕θι

Count the number of unique identities remaining.

\$\endgroup\$
5
\$\begingroup\$

Jelly, 25 15 bytes

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

Try it online!

A monadic link taking a list of space-separates agent claims and returning the lowest upper bound of the number of distinct spies.

Explanation

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

Thanks to @Arnauld and @JonathanAllan for identifying issues with previous versions, and to @JonathanAllan again for saving a byte! If the input spec were relaxed to allow a list of lists, this would save one byte.

\$\endgroup\$
  • \$\begingroup\$ I think the sort may actually be unnecessary, since the indices in the groups from Ġ are sorted and the flattened, de-duplicated filter result, fƇFQ, would always, after repeated application, end up with these in sorted order (e.g. 'a a b b c', 'a b a b c will not find an eventual [3,4,1,2], even though it would appear along the way). So ḲĠ)ẎfƇFQɗⱮQ$ÐLL might be good for 15? \$\endgroup\$ – Jonathan Allan Jul 14 at 19:14
  • \$\begingroup\$ @JonathanAllan good spot. I’ve had a bit of a play (and think about how it works) and think you’re right. \$\endgroup\$ – Nick Kennedy Jul 14 at 19:26
4
\$\begingroup\$

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

Try it 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
\$\endgroup\$
3
\$\begingroup\$

Husk, 12 bytes

LωomΣknṁoηkw

Try it online!

Explanation

The idea is to create a list of all groups of spies that are known to be the same person, then progressively merge intersecting groups until a fixed point is reached. The output is the number of remaining groups that couldn't be merged.

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
\$\endgroup\$
3
\$\begingroup\$

Python 3, 191 182 bytes

Thank you recursive

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

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Ruby, 123 117 bytes

Uses a similar idea to movatica's Python 3 solution but calculates the lowest spy index for each "tree" in a slightly different way (by keeping track of previous encountered profiles, finding an overlap if it exists, and combining them)

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

Try it online!

Explanation

->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
\$\endgroup\$
  • \$\begingroup\$ Instead of popping and zipping, you can just transpose. \$\endgroup\$ – G B Jul 17 at 14:40
  • \$\begingroup\$ 113 bytes \$\endgroup\$ – G B Jul 17 at 14:46
  • \$\begingroup\$ @GB thanks for the heads up; I've been using pop-zip or shift-zip to transpose arrays forever! Also, your trick of using s.split.map{|i|s.index i} is nice, but it can create edge cases depending on the length of the inputs. This input should return 3, not 2. \$\endgroup\$ – Value Ink Jul 17 at 16:40
2
\$\begingroup\$

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

Try it online!

8 bytes thx to wilkben.

\$\endgroup\$
  • \$\begingroup\$ Since g is only used once, couldn't you define it inline? I kinda forget if that's possible in Python but I seem to remember it is. \$\endgroup\$ – Stephen Jul 15 at 18:16
  • \$\begingroup\$ 221 Bytes \$\endgroup\$ – wilkben Jul 17 at 17:52
1
\$\begingroup\$

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

Try it online!

Associates the strings used by the agents with the line-number the appear in to prevent equality across agents, then repeatedly checks if any phrases for any position overlap and counts the number of resulting sets.

\$\endgroup\$
0
\$\begingroup\$

PHP, 271 bytes

This won't work if any of the identities are just numbers as I store the "spy number" in with the identities. I don't think it wouldn't be hard to fix that though.

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

Try it online!

Explanation

Sort of confused myself writing this but it works for all the test cases!

$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

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.