r sequence problem - max number of changes in a given sequence

Question

Can somebody help me understand a CS problem.

The problem is the New York Time Rollercoaster problem.

I have a queue:

queue <- seq(from = 1, to = 5)
 1 2 3 4 5

A person can bribe another person who is ahead of them in the queue but by only a maximum of 2 times. Thus a queue sequence might look like:

Ride: 1, 2, 3, 4, 5  # Original queue
Ride: 1, 2, 3, 5, 4  # 5 bribes number 4
Ride: 1, 2, 5, 3, 4  # 5 bribes number 3 and thus runs out of bribes and cannot move further (it does not state in the problem if 3 can "re-bribe" 5 so I assume they cannot).
Ride: 2, 1, 5, 3, 4  # 2 bribes number 1

So given the input c(1, 2, 3, 4, 5) what are the minimum number of swaps it would take to get to the final output which would be c(2, 1, 5, 3, 4).

Python code from here:

def minimumBribes(q):
    moves = 0
    for pos, val in enumerate(q):
        if (val-1) - pos > 2:
            return "Too chaotic"
        for j in xrange(max(0,val-2), pos):
            if q[j] > val:
                moves+=1
    return moves

I am trying to re-create this in R and understand the solution.

Answer 1

Here's a way I think -

minimumBribes <- function(final_q) {
  change <- final_q - seq_along(final_q)
  if(any(change > 2)) return("Too chaotic!")
  sum(change[change > 0])
}

minimumBribes(q = c(2, 1, 5, 3, 4))
[1] 3

Explanation -

initial_q <- 1:5
final_q <- c(2, 1, 5, 3, 4)

# calculate change in position; +ve is gain and -ve is loss
change <- final_q - initial_q

[1]  1 -1  2 -1 -1
# it is clear that if some gained x posn combined then other(s) lost x posn combined
# i.e. sum of posn gains and losses will always be 0

# therefore, to get min total swaps, simply add either gains or losses
# which in a way implies the most direct path from initial_q to final_q
sum(change[change > 0])

[1] 3