1

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()
Improve this question
5
  • How can you launch 4 days if you have 50 of fuel and consumed (10+40) = everything after 2 days? or is it refueling? what happens if there is not enough fuel? does it launch anyway and get lost? Commented Jan 1, 2022 at 15:28
  • 1
    Is that this? If so, why keep that (and its needed details) secret? Commented Jan 1, 2022 at 15:29
  • @KellyBundy, I had no intention of hiding it but yes it is that Commented Jan 1, 2022 at 15:34
  • @mozway It's not explained very well. Fuel is only used on the first and last day. You get to choose which day to launch and return, to optimize the fuel use. Commented Jan 1, 2022 at 15:36
  • @mozway, sorry I didn't clear it up but you don't count the days in between so it would only be 10 (day 1) + 30 (day 4) Commented Jan 1, 2022 at 15:37

2 Answers 2

Reset to default
3

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)
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

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.

Improve this answer

2 Comments

I have done that, however the main issue is the amount of times my program has to loop through this part: 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
as when the program is dealing with large number of inputs it will take a long time to loop through the list

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.