How to read multiple lines input in python

Question

I am new to Python and I was trying to workout an interviewstreet problem of Kingdom Connectivity. Although, I managed to solve the problem, I'm having trouble giving input of the given format, I've tried my solution on my system and the output is correct, but as soon as I compile there, there is no output.

Input is of the form:

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

Please, help me figure out how to solve this problem.

Currently, I'm taking input from raw_input() in a loop and splitting using a.split(' ').

Here is part of the question:

**Input Description:**

First line contains two integers N and M.

Then follow M lines ,each having two integers say x and y, 1<=x,y<=N , indicating there is a road from city x to city y.

**Output Description:**

Print the number of different paths from city 1 to city N modulo 1,000,000,000(10^9).If there are infinitely many different paths print "INFINITE PATHS"(quotes are for clarity).

**Sample Input:**

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

**Sample Output:**

2

**Sample Input:**

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

**Sample Output:**

INFINITE PATHS

Here is my solution

import sys
import numpy as np
c=0
x=raw_input()
y=x.split(' ')
l=(int(y[0]),int(y[1]))
e=[raw_input() for i in range(l[1])]
f=[e[i].split(' ') for i in range(l[1])]
a=[map(int,i) for i in f]
b=[[0 for i in a] for j in range(l[0])]
for i in range(l[0]+1):
    for j in range(l[0]+1):
        if [i,j] in a:
            b[i-1][j-1]=1
        elif a[i-1][0]>=a[i-1][1]:
            print "INFINITE PATHS"
            sys.exit(0)
for i in range(0,l[1]): 
    d=np.linalg.matrix_power(b,i+1)
    c+=d[0][l[1]-1]   
print c

Here is screenshot

Answer 1

I found your program difficult to understand. So, I rewrote it, and I think my version is a bit easier to understand.

import sys
import numpy as np


line = raw_input()
max_val, num_paths = (int(n) for n in line.split())


# a will be a list of tuples of int, taken from the input.
#
# Each tuple represents a path, so this is effectively a sparse representation
# of a square matrix of possible paths.
#
# Input city numbers are 1-based, but we will treat them as 0-based, so
# subtract 1 from each value before appending to array a.

a = []
for _ in xrange(num_paths):
    line = raw_input()

    # TRICKY: subtract 1 to convert from 1-based to 0-based city numbers
    tup = tuple(int(n)-1 for n in line.split())

    if len(tup) != 2:
        raise ValueError, "input should only have two values per line"
    for n in tup:
        if not 0 <= n < max_val:
            raise ValueError, "value must be in range [1, %d]" % max_val
        if tup[0] >= tup[1]:
            #raise ValueError, "INFINITE PATHS"
            print "INFINITE PATHS"
            sys.exit(0)
    a.append(tup)


# Expand the sparse matrix representation into an actual square matrix.
# It should have a 1 anywhere a path was indicated with a tuple in list a,
# and a 0 everywhere else.
b = [ [0 for _ in xrange(max_val)] for _ in xrange(max_val)]
for i, j in a:
    b[i][j] = 1


c = 0
for i in xrange(num_paths):
    d = np.linalg.matrix_power(b, i + 1)
    c += d[0][max_val - 1]
print c

My version does print 2 when given the example input.

Here are some things I figured out as I worked on this:

The first line gives us constants (N and M in the documentation, representing the max legal value and the number of paths respectively). You should save these values in variables with good names, rather than putting them in a list and referring to them by list index. I have used the names max_val and num_paths. You yourself made a mistake: you are supposed to find paths from city 1 to city N, so the check at the end should be d[0][max_val - 1]; you used l[1] which is num_paths rather than l[0].

b should be a square matrix. Your code was setting the width based on the length of a, but max_val and num_paths might not always be equal, so that's a dangerous way to do it.

It is strange to loop over every possible point in the square matrix and check to see whether it should be set as a 1 or not. It's also very inefficient, especially because the in test is O(n) where n is the length of the array a. Instead, build the empty square matrix, and then simply loop over the paths and set the 1 values per path.

Likewise, it is strange to validate the input values in the loop that initializes the square matrix; it's better to validate the input values as they are read in the input loop. And again it is dangerous, because num_paths might be unrelated to max_val. Also it's inefficient, because you were checking a[i-1][0] against a[i-1][1] once per column in b; that comparison doesn't use the value j at all. You were doing each check five times; it's enough to do each check once.

There is a Python idiom that I used, where you can use _ (a single underscore) as the name of a variable when you don't care about the value of that variable. When we are just doing something a certain number of times with a loop, and we won't be using the loop counter value for anything, I used a _ as the loop counter variable. This is not essential of course.

To answer your actual question: I don't see any possible way for your program not to produce output. I suspect that there might be an issue on the server that runs this test problem. Your program should always either print "INFINITE PATHS" or else some sort of integer value.

P.S. I don't actually understand how your program works; the problem description says you should provide a number of paths modulo 1e9, and I don't see anything to enforce that.