Calculate walking points to reach target-CodePudding

Given a number (finish end point), then an array of scooters, where scooters represents the position of the ith scooter.
Each scooter can travel up to 10 points before the battery is fully discharged, and cannot go further. For example, if the scooter is at point 5, it can travel to points 5, 6, 7, ..., ., up to point 15 (inclusive), but not to point 16 or beyond.
Calculate walking steps to reach the target.

Example1:

finish=23, scooters[7, 4, 14] 
output -> solution(finish, scooters) = 4

Explanation1:

Starting from 0, the closest scooter is scooters[1] = 4 so it takes 4 points to walk there.
Then the scooter can go up to 10 points, 10 4=14.
There is a scooter at 14 points (scooters[2] = 14).
This way we can go straight to the end to complete 23.
So it's a total of 4 points of walking

Example2:

finish=27, scooters[15, 7, 3, 10]
output -> solution(finish, scooters) = 5

My Code:

finish=23
scooters = [7, 4, 14]

def solution(finish, scooters):
    sum = min(scooters)
    step = min(scooters)
    
    while sum < finish:
        step  = 10
        sum = sum   step
    
    return step

solution(finish, scooters)

How to include scooters[i] within the while loop to check for the next available scooter?

CodePudding user response：

Simplest way to achieve consistency without too much logic is first sort()ing your list. After that you can calculate any distance between two scooters that has over 10 steps and add it to the sum:

def solution(finish, scooters):
    scooters.append(finish)
    scooters.sort()
    steps = scooters[0]
    for i in range(1, len(scooters)):
        steps  = max(0, scooters[i] - scooters[i - 1] - 10)
        if finish in (scooters[i], scooters[i - 1]):
            break

    return steps

print(solution(27, [15, 7, 3, 10]))
# 5
print(solution(23, [7, 4, 14]))
# 4
print(solution(10, [15, 7, 3, 10]))
# 3
print(solution(2, [15, 3]))
# 2

CodePudding user response：

As a simple approach, you can just iterate over the scooters array, and increment steps based on the distance between the i-th scooter and the i 1-th scooter.

def solution(finish, scooters):
    i = 0
    n = len(scooters)
    scooters.sort()
    steps = min(scooters[0], finish)
    for i in range(0, n-1):
        if scooters[i]   10 >= finish:
            break
        elif scooters[i 1] > finish:
            steps  = max(0, finish-scooters[i]-10)
        else:
            steps  = max(0, scooters[i 1]-scooters[i]-10)
    if scooters[-1] < finish:
        steps  = max(0, finish - scooters[-1] - 10)
    return steps

print(solution(27, [15, 7, 3, 10]))
print(solution(23, [7,4,14]))

Time complexity: O(nlogn) where n is the length of scooters array.

CodePudding user response：

One way to solve this is by counting the number of steps which cannot be taken by scooter. You can do this by creating a list of all the steps that need to be made, populating it with 1s. Then set to 0 any step that can be taken by a scooter. The number of walking steps is then the sum of the list:

def solution(finish, scooters):
    steps = [1 for _ in range(finish 1)]
    zeros = [0 for _ in range(11)]
    for s in scooters:
        steps[s:s 11] = zeros
    return sum(steps)

solution(27, [15, 7, 3, 10])
# 5
solution(23, [7,4,14])
# 4