algorithm to calculate speeds to move in order to arrive in x turns

given a distance, turns calculate the number of turns to be on each speed - 1 2 4, and 8. to complete the distance on the last turn.

you start on speed 1, and in each turn you can accelerate to the next speed or do nothing (1 -> 2, 2 -> 4, 4 -> 8), once you accelerate you can't slow back down.

each turn you are moving speed steps (distance -= speed).

also, it's ok to go more than distance steps but only if it happens on the last turn.

for example: distance = 25, turns = 10 -> speed 1: 1 turn, speed 2: 5 turns, speed 4: 4 turns, the total distance is 1 * 1 + 2 * 5 + 4 * 4 = 27 steps, but we got to 25 steps on the last turn which is what we need.

I need help writing a function that will calculate that.

def calc_speeds(distance: int, arrive_in_x_turns: int) -> dict[int, int]:

so far i've used this turns_till_arrival = ((turns_till_arrival - (speed // 2)) // speed) + (speed // 2) + 1 formula, in a for loop, for each speed and if turns_till_arrival is equal to turns I will accelerate until I get to speed without spending extra turns in other speeds (only the 1 necessary turn, because I can only accelerate once per turn) but then there are a lot of times that it doesn't work because in order for it to work I must spend more than 1 turn at other speeds but I can't figure out a way to calculate that.

This is a fairly exhaustive approach, but it does provide the correct answer to the problem above about how to cover your distance in a specified number of steps.

For my method, I first created the output dictionary in the form of {1: distance, 2: 0, 4: 0, 8: 0}, where, for each key-value pair, the key represents your speed and the value represents the total number of turns spent at that speed. This dictionary above represents the way to cover your distance in the maximum number of turns possible, since each turn you are just running at speed=1.

The important realization here is that if you subtract two turns from output[1] and add a turn to output[2], you are covering the same distance as before, but you have lost a turn. Therefore, you can make a loop that stops when the number of turns in your output equals arrive_in_x_turns, and during each iteration, you lose a turn by doing the subprocess I have described above. This also works for the other speeds (i.e. subtracting two turns from output[2] and adding a turn into output[4] maintains the distance you want to travel while losing a turn).

Here is my implementation below. When running your example of calc_speeds(distance=25, arrive_in_x_turns=10), my output is {1: 1, 2: 6, 4: 3, 8: 0}. The number of turns are correct (1 + 6 + 3 = 10), as is the distance covered (1*1 + 2*6 + 4*3 + 8*0 = 1 + 12 + 12 + 0 = 25).

def calc_speeds(distance: int, arrive_in_x_turns: int) -> dict[int, int]:
    output = {1: distance, 2: 0, 4: 0, 8: 0}

    # Loop until the total number of turns is equal to the number of turns requested
    while (sum(output.values()) > arrive_in_x_turns):
        # Subtract two turns off of '1' and add a turn to '2' until not possible
        # This method ensures that during each iteration, number of turns decreases
        # by one while the distance traveled remains the same
        if output[1] // 2 > 0:
            output[1] -= 2
            output[2] += 1
        # Do a similar method for the ones above
        elif output[2] // 2 > 0:
            output[2] -= 2
            output[4] += 1
        elif output[4] // 2 > 0:
            output[4] -= 2
            output[8] += 1
    
    return output

Again, this is an exhaustive solution that will have a long runtime with harder examples, but hopefully this will help get you started on finding a more optimal way to solve it!

EDIT:

This answer above can be optimized! Instead of subtracting two turns from a current speed and adding one turn to the next, we can instead find the minimum between half the number of turns of the current speed and the remaining number of turns that need to be gotten rid of. Here's a newer version.

def calc_speeds(distance: int, arrive_in_x_turns: int) -> dict[int, int]:
    output = {1: distance, 2: 0, 4: 0, 8: 0}

    # Loop until the total number of turns is equal to the number of turns requested
    while sum(output.values()) > arrive_in_x_turns:
        if output[1] // 2 > 0:
            # Calculate turns to subtract from current speed as the minimum between half the 
            # current turns under this speed and the number of turns remaining
            turns_to_subtract = min(output[1] // 2, sum(output.values()) - arrive_in_x_turns)
            # Use similar logic to the previous version of this algorithm
            output[1] -= turns_to_subtract * 2
            output[2] += turns_to_subtract
        elif output[2] // 2 > 0:
            turns_to_subtract = min(output[2] // 2, sum(output.values()) - arrive_in_x_turns)
            output[2] -= turns_to_subtract * 2
            output[4] += turns_to_subtract
        elif output[4] // 2 > 0:
            turns_to_subtract = min(output[4] // 2, sum(output.values()) - arrive_in_x_turns)
            output[4] -= turns_to_subtract * 2
            output[8] += turns_to_subtract
    
    return output