Beta

Detecting Factions in Friend-Foe Networks

24AlexandraBaier
Description
Loading description...
Graph Theory
Algorithms
Data Structures
View
AllIssues2QuestionsSuggestionsShow Resolved
  • Please sign in or sign up to leave a comment.
  • Voile Avatar

    This kata currently does not explicitly rule out networks with any cycle that contains odd number of -1s, such as

     0 -1 -1
-1  0 -1
-1 -1  0

    These networks are unsolvable for obvious reasons, and existing solutions all return their own results when this happens.

  • Voile Avatar
     
    /workspace/default/tests.py:28: DeprecationWarning: Sampling from a set deprecated
since Python 3.9 and will be removed in a subsequent version.
  neighbors = random.sample(connected.difference({current_node}), min_edges)
  • Minecraftian14 Avatar

    🤯Nicely made - but I am lost somewhere! Well - in short, my code "works" for the visible tests and not for the random ones - of course 😝 Given a matrix as:

     1 -1  1  1
 0  0  0 -1
 0  0  0 -1
 1 -1 -1  0

    If I understood the rules correctly, the 1 placed third in first row represents that the person indexed 0 and the person indexed 2 know each other in a friendly manner. Because index 0 is always LOL, index 3 should also be LOL.

    However - the result is Dota...

    Where am I wrong??

    • Minecraftian14 Avatar

      The complete test data

       1 -1  1  1 -1 -1  1  1 -1 -1 -1  1  1  1  1  1  1  1  1 
 0  0  0 -1 -1  1 -1  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0 -1  0  0  0  0  0 -1  0  0  1  0  0  0  0  0  0 
 1 -1 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0 -1  0  0  0  0  0  0  1  0  0  0  0  0  0  0 -1  0  0 
 0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1 
 0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0 
 1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  1  0  0  0  0  0  0  0  0  0  0 -1  0  0  0 
 0  0 -1  0  0  0  0  0  0  0  1 -1  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0 
 0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 1  0  0  0  0  0  0  0  0  0  0  0  0  0 -1  0  0  0  0 
 0  0  0  0  0  0  0  0  0  0  0  0  0 -1  0  0  0  0  0 
 0  0  0  0  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0 
 0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0

      The expectation ' ' My answer

      League of Legends      League of Legends
Dota 2                        Dota 2
Dota 2                        League of Legends
League of Legends      League of Legends
League of Legends      Dota 2
Dota 2                        Dota 2
League of Legends      League of Legends
League of Legends      League of Legends
League of Legends      Dota 2
League of Legends      Dota 2
League of Legends      Dota 2
Dota 2                        League of Legends
Dota 2                        League of Legends
League of Legends      League of Legends
Dota 2                        League of Legends
Dota 2                        League of Legends
Dota 2                        League of Legends
League of Legends      League of Legends
Dota 2                        League of Legends
    • B1ts Avatar

      Maybe you're misinterpreting the logs, IDK. The result for the first 4x4 matrix should be ['League of Legends', 'Dota 2', 'League of Legends', 'League of Legends'] (according to my solution).

  • Blind4Basics Avatar

    Very enjoyable and thurough about the tests. Very well built kata.

    We want more like that! ;)