"Researcher Hatim is right or wrong" challenge

Question

I wrote a program to solve a problem, I am not so good in python so want help to find areas where this program can be improved or simplified and readable too:-

I got this problem in a code challenge

Problem

Professor Hatim is researching the sexual behavior of a rare species of lizard. He assumes that they feature two different genders and that they only interact with lizard of the opposite gender. Each lizard has a integer printed on their back.

Given the details of lizard interactions, decide whether the experiment supports his assumption of two genders with no homosexual bugs, or if it contains some bug interactions that falsify it. Or simply, you have to print "Suspicious lizard found!" (without quotes), if an interaction of two lizards of same gender is found in the list of interactions, otherwise print "No suspicious lizard found!" (without quotes).

Input format

• The first line contains an integer T, denoting the number of test cases.

• The first line of each test case contains two integers N and M, where N denotes the number of lizards and M denotes the number of interactions.

• Next M lines of each test case contains, two space separated integers, say x and y , denoting the interaction between lizard no. x and lizard no. y.

Note: Integers on the back of lizards are numbered from 1 to N.

Output format

For each test case ,print a line, saying either “No suspicious lizard found!” if the experiment is consistent with his assumption about the lizard sexual behavior, or “Suspicious lizard found!” if Professor Hatims’s assumption is definitely wrong.

Constraints

• 1 ≤ T ≤ 5
• 2 ≤ N ≤ 2000
• 1 ≤ M ≤ 105

Sample Input

2
3 3
1 2
2 3
1 3
4 2
1 2
3 4

Sample Output

Suspicious lizards found!
No suspicious lizards found!

Time Limit: 1 sec(s) for each input file.
Memory Limit: 256 MB Source
Limit: 1024 KB
Marking Scheme: Marks are awarded if any testcase passes.
Allowed languages: PYTHON

CODE

from sys import argv

class Test:

    def __init__(self, file):
        self.file = file

    def run_test_case(self):
        n, m = self.file.readline().split()
        n = int(n)
        m = int(m)
        first_gender = []
        second_gender = []

        for i in range(m):
            x, y = 0, 0
            x, y = self.file.readline().split()
            if first_gender == [] and second_gender == []:
                first_gender[ len(first_gender) : ] = x
                second_gender[ len(second_gender) : ] = y
            elif (x in first_gender and y in first_gender) or (x in second_gender and y in second_gender):
                print 'Suspicious lizard found!'
                return
            elif (x in first_gender and y not in  second_gender):
                second_gender[ len(second_gender) : ] = y
            elif (x in second_gender and y not in first_gender):
                first_gender[ len(first_gender) : ] = y
            elif (y in first_gender and x not in second_gender):
                second_gender[ len(second_gender) : ] = x
            elif (y in second_gender and x not in first_gender):
                first_gender[ len(first_gender) : ] = x
        print 'No suspicious lizard found!'



def start(filename):
    file = open(filename, 'r')
    num_test_cases = int(file.readline())
    for i in range(num_test_cases):
        test_instance = Test(file)
        test_instance.run_test_case()

if __name__ == '__main__':
    (script, filename) = argv
    start(filename)

Answer 1

You don't need a class

I highly recommend the Stop Writing Classes presentation. The typical situation it describes : a class with two methods, an init and a run is exactly what you've done.

Changing this already makes your code much simpler.

def run_test_case(file_):
    n, m = file_.readline().split()
    n = int(n)
    m = int(m)
    first_gender = []
    second_gender = []

    for i in range(m):
        x, y = 0, 0
        x, y = file_.readline().split()
        if first_gender == [] and second_gender == []:
            first_gender[ len(first_gender) : ] = x
            second_gender[ len(second_gender) : ] = y
        elif (x in first_gender and y in first_gender) or (x in second_gender and y in second_gender):
            print 'Suspicious lizard found!'
            return
        elif (x in first_gender and y not in  second_gender):
            second_gender[ len(second_gender) : ] = y
        elif (x in second_gender and y not in first_gender):
            first_gender[ len(first_gender) : ] = y
        elif (y in first_gender and x not in second_gender):
            second_gender[ len(second_gender) : ] = x
        elif (y in second_gender and x not in first_gender):
            first_gender[ len(first_gender) : ] = x
    print 'No suspicious lizard found!'



def start(filename):
    file_ = open(filename, 'r')
    num_test_cases = int(file_.readline())
    for i in range(num_test_cases):
        run_test_case(file_)

Close your file

You open a file but never close it. You should but it's quite normal to forget it. A nice solution not to forget it is to use the with statement.

def start(filename):
    with open(filename, 'r') as file_:
        num_test_cases = int(file_.readline())
        for i in range(num_test_cases):
            run_test_case(file_)

Separation of concerns

Your run_test_case functions does way too much : file reading to get input, getting solution for the problem, printing out the answer. It would be much nicer to have this splitted into individual functions. Among other things, it would make your code easier to test. Code-challenge are very good candidates for unit tests because the algorithm involved is usually pretty tricky, the input and ouput are usually pretty clear, no side-effect is expected and you are provided some simple tests with the problem.

Rewriting this gives :

def find_suspicious_lizard(interactions):
    first_gender = []
    second_gender = []
    for x, y in interactions:
        if first_gender == [] and second_gender == []:
            first_gender[ len(first_gender) : ] = x
            second_gender[ len(second_gender) : ] = y
        elif (x in first_gender and y in first_gender) or (x in second_gender and y in second_gender):
            return True
        elif (x in first_gender and y not in  second_gender):
            second_gender[ len(second_gender) : ] = y
        elif (x in second_gender and y not in first_gender):
            first_gender[ len(first_gender) : ] = y
        elif (y in first_gender and x not in second_gender):
            second_gender[ len(second_gender) : ] = x
        elif (y in second_gender and x not in first_gender):
            first_gender[ len(first_gender) : ] = x
    return False



def run_test_from_file(filename):
    with open(filename, 'r') as file_:
        num_test_cases = int(file_.readline())
        for i in range(num_test_cases):
            n, m = file_.readline().split()
            n = int(n)
            m = int(m)
            interactions = []
            for i in range(m):
                x, y = file_.readline().split()
                interactions.append((x, y))
            print('Suspicious lizard found!' if find_suspicious_lizard(interactions) else 'No suspicious lizard found!')

if __name__ == '__main__':
    (script, filename) = argv
    run_test_from_file(filename)
    assert find_suspicious_lizard([('1', '2'), ('2', '3'), ('1', '3')])
    assert not find_suspicious_lizard([('1', '2'), ('3', '4')])

With the test I've added, I can now tweak the algorithm and maybe see quickly if I break something.

Do things the easy way

second_gender[ len(second_gender) : ] = y seems like a complicated way to add an element to an array/list. If only there was an append method on Lists. Oh great, it is actually the first method documented.

def find_suspicious_lizard(interactions):
    first_gender = []
    second_gender = []
    for x, y in interactions:
        if first_gender == [] and second_gender == []:
            first_gender.append(x)
            second_gender.append(y)
        elif (x in first_gender and y in first_gender) or (x in second_gender and y in second_gender):
            return True
        elif (x in first_gender and y not in  second_gender):
            second_gender.append(y)
        elif (x in second_gender and y not in first_gender):
            first_gender.append(y)
        elif (y in first_gender and x not in second_gender):
            second_gender.append(y)
        elif (y in second_gender and x not in first_gender):
            first_gender.append(x)
    return False

Performance

You call foo in bar many times with the same values. It could be worth storing the result:

        x_in_first = x in first_gender
        y_in_first = y in first_gender
        x_in_second = x in second_gender
        y_in_second = y in second_gender
        if x_in_first and y_in_first:
            return True
        elif x_in_second and y_in_second:
            return True
        elif x_in_first and not y_in_second:
            second_gender.append(y)
        elif x_in_second and not y_in_first:
            first_gender.append(y)
        elif y_in_first and not x_in_second:
            second_gender.append(y)
        elif y_in_second and not x_in_first:
            first_gender.append(x)

It also helped me to think about the logic you've written and helped me to find... a bug!!

Bug

Adding a simple test case (I knew it would be worth it) shows that there is something wrong in your code.

assert not find_suspicious_lizard([('1', '2'), ('3', '4'), ('3', '5'), ('4', '5')])  # should return true because of triplet 3-4-5.

Answer 2

@Josay has found that your code doesn't work. I'd like to point out the bad coding practice that led to the possibility of the bug: your elif chain has no catch-all else case. If you had written

else:
    assert False

… you would have triggered the assertion failure with the sample input, and discovered that there is a possibility that your first_gender or second_gender list is non-empty, yet neither of the lizards on the current line has been previously mentioned.

The exercise is equivalent to the problem of determining whether a graph is 2-colorable (i.e., bipartite).

Answer 3

The start function opens a file for reading but doesn't close it. It's a bad practice to forget to close resources when you no longer need them.

For this reason it's recommended to use a contract manager, which automatically closes a file handle when leaving the scope, like this:

with open(filename) as file:
    num_test_cases = int(file.readline())
    for _ in range(num_test_cases):
        test_instance = Test(file)
        test_instance.run_test_case()

I also dropped the 'r' parameter, as that's the default anyway, and renamed the unused loop variable i to _, which is a common convention in such situations.

---

The first line here is pointless, and should be removed:

        x, y = 0, 0
        x, y = self.file.readline().split()

---

Empty lists are falsy in Python, so instead of this:

        if first_gender == [] and second_gender == []:
            # ...

The recommended writing style is this:

      if not first_gender and not second_gender:
            # ...