How to read multiple lines in python

I'm new to Python and I was trying to get my head around the Kingdom Connectivity interviewing issue. Although I was able to solve the problem, I had problems providing input of the given format, I tried my solution on my system and the result is correct, but as soon as I compile it, there is no output.

The entrance looks like:

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


Please help me figure out how to solve this problem.

I am currently taking input from raw_input()

in a loop and breaking it up with 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:**


**Sample Input:**

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

**Sample Output:**



Here is my solution

import sys
import numpy as np
y=x.split(' ')
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:
        elif a[i-1][0]>=a[i-1][1]:
            print "INFINITE PATHS"
for i in range(0,l[1]): 
print c


Here is a screenshot enter image description here


source to share

3 answers

I realized that your program is difficult to understand. So I rewrote it and I think my version is a little self-explanatory.

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"

# 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 prints 2

as I enter the example.

Here are some things I figured out when I was working on this:

The first line gives us constants ( N

and M

in the documentation, representing the maximum legal value and the number of paths, respectively). These values ​​should be stored in well-named variables, not put in a list and referenced by the index of the list. I have used names max_val

and num_paths

. You yourself made a mistake: you must find the paths from city 1 to city N, so there should be a check at the end d[0][max_val - 1]

; you used l[1]

which num_paths

, not l[0]



should be a square matrix. Your code was setting the width depending on the length a

, but max_val

they num_paths

may not always be equal, so this is a dangerous way to do it.

It's weird to iterate over every possible point of a square matrix and check if it should be set to 1 or not. It's also very inefficient, especially since the test in

is O (n), where n is the length of the array a

. Instead, create an empty square matrix and then just loop through the paths and set the values ​​to 1 for each path.

Likewise, it is weird to check input values ​​in a loop that initializes a square matrix; it is better to check the input values ​​as they are read in the input loop. Again, this is dangerous because it num_paths

may not be related to max_val

. Also, it is inefficient, because you checked a[i-1][0]

on a[i-1][1]

once a column in b

; this comparison uses no value at all j

. You have made each check five times; it is sufficient to perform each check once.

There is a Python idiom I have used where you can use _

(one underscore) as a variable name when you don't care about the value of that variable. When we just do something a certain number of times with a loop, and we will not use the value of the loop counter for something, I used it _

as a loop counter variable. Of course, this is not necessary.

To answer your real question: I see no way for your program to produce no output. I suspect there may be an issue on the server that triggers this test issue. Your program should always either print "INFINITE PATHS" or some integer value.

PS I don't understand how your program works; the problem description says that you must specify multiple paths mod 1e9, and I see nothing to provide this.



You can read the specified input like this:

line = raw_input()
n, m = map(int, line.split())

for _ in range(m):
  line = raw_input()
  x, y = map(int, line.split())
  print x, y




if you have an input to an input.txt file in the same folder as the script:

with open("input.txt") as f:
    l = [int(i) for i in f.readline().split(" ")]
    a = []
    for line in f.readlines():
        a.append([int(i) for i in line.strip().split(" ")])
print(l, a)


if the input is passed as a command line argument:

import sys
input_string = sys.argv[1]
print(input_string) # test if this prints the input




All Articles