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:**
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 a screenshot
source to share
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"
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 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]
.
b
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.
source to share
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
...
source to share