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
in a loop and breaking it up with
Here is part of the question:
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. 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). Input:** 5 5 1 2 2 4 2 3 3 4 4 5 Output:** 2 Input:** 5 5 1 2 4 2 2 3 3 4 4 5 Output:** INFINITE PATHS
Here is my solution
import sys import numpy as np c=0 x=raw_input() y=x.split(' ') l=(int(y),int(y)) e=[raw_input() for i in range(l)] f=[e[i].split(' ') for i in range(l)] a=[map(int,i) for i in f] b=[[0 for i in a] for j in range(l)] for i in range(l+1): for j in range(l+1): if [i,j] in a: b[i-1][j-1]=1 elif a[i-1]>=a[i-1]: print "INFINITE PATHS" sys.exit(0) for i in range(0,l): d=np.linalg.matrix_power(b,i+1) c+=d[l-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 >= tup: #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[max_val - 1] print c
My version prints
as I enter the example.
Here are some things I figured out when I was working on this:
The first line gives us constants (
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
. 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[max_val - 1]
; you used
should be a square matrix. Your code was setting the width depending on the length
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
is O (n), where n is the length of the array
. 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
may not be related to
. Also, it is inefficient, because you checked
once a column in
; this comparison uses no value at all
. 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 print(input_string) # test if this prints the input ...
source to share