CODEWITHSUNDEEP
pythonlistalgorithm
The Voyager
The Voyager

Reputation: 90

More efficient solution to search a python list

Question: there is a rocket ship which launches of any day from day 0 to day N and has F amount of fuel and is collecting samples but can only collect 1 sample each day and each day the fuel consumption is different for example day1: 12 ,day2: 32 ,day3: 5 etc. The program must output the most amount of days the rocket can be in space without running out of fuel.

I have succeeded in writing a correct solution however it is too slow, is there any data structure or another method of writing this program which would allow the program to run faster

example

code:

#!/usr/bin/env python
import sys
sys.setrecursionlimit(1000000000)



# N is the number of available days.
N = None

# F is the amount of fuel available.
F = None

# C contains the fuel needed to open a portal on each day.
C = [None for x in range(100005)]

answer = None

# Open the input and output files.
input_file = open("spacein.txt", "r")
output_file = open("spaceout.txt", "w")

# Read the value of N and F.
input_line = input_file.readline().strip()
N, F = map(int, input_line.split())

# Read the cost to open a portal on each day.
for i in range(0, N):
    C[i] = int(input_file.readline().strip())



fuel = []
for i in range(0, N):
    fuel.append(C[i])

print(fuel)
final = []

for i in range(0, len(fuel)-2):
    for j in range(i+1, len(fuel)):
        if fuel[i] + fuel[j] < F or fuel[i] + fuel[j] == F:
            final.append(fuel.index(fuel[j])-fuel.index(fuel[i]))
            print(fuel.index(fuel[i]), fuel.index(fuel[j]))
        else:
            pass
if len(fuel) > 2:
    answer = (max(final)+1)
else:
    answer = -1

# Write the answer to the output file.
output_file.write("%d\n" % (answer))

# Finally, close the input/output files.
input_file.close()
output_file.close()

Upvotes: 1

Views: 105

Answers (2)

Jovan Topolac
Jovan Topolac

Reputation: 64

I think you can make your program faster by simply changing the line:

C = [None for x in range(100005)]

to:

C = []

And then, in your loop, change:

C[i] = int(input_file.readline().strip())

to:

C.append(int(input_file.readline().strip()))

Since that way you won't loop 100005 times just to put a None value into the C array. Also, I don't see why you need the C array at all, since you only use it to fill the fuel array? I would just read the portal costs for each day directly into the fuel array so you reduce redundancies, that way you will have one less N loop in your code.

Upvotes: 0

Kelly Bundy
Kelly Bundy

Reputation: 27650

The second sample input has a more insightful daily consumptions list:

F = 14
C = [12, 8, 2, 16, 4, 6, 10]

Note that you definitely wouldn't start on the day with consumption 16 even if F were larger, as the earlier days cost less and give more. Only 12, 8 and 2 are viable start days due to this reason.

So go through the days and keep decreasing consumption entries along with their original indexes (i.e., their dates). And for each day as possible end day, binary search that list. For example for the day with consumption 4 as end day, you can afford 14-4=10 for a start day. Binary search 10 in [12, 8, 2] to find the 8.

Accepted code (I negated the consumption values because bisect wants an increasing list):

from bisect import bisect_left

with open('spacein.txt') as f:
    _, F, *C = map(int, f.read().split())

S = []
I = []
best = -1
for i, c in enumerate(C):
    j = bisect_left(S, c - F)
    if j < len(S):
        best = max(best, i - I[j] + 1)
    if not S or c < -S[-1]:
        S.append(-c)
        I.append(i)

with open('spaceout.txt', 'w') as f:
    print(best, file=f)

Upvotes: 3

Related Questions