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.
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.
Identities owned by the same spy do not have to be consecutive, i.e. a message like:
dog cat dog
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.
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.
Angel Devil Angel Joker Thief Thief Ra Ra Ras Pu Ti N say sea c c see cee
Blossom Bubbles Buttercup Ed Edd Eddy
Botswana Botswana Botswana Left Middle Right
Black White White Black
Foo Bar Foo Foo Bar Bar
A B C D A A C D A B C C A B B D
A B A C
A B C