Algorithm for Helicopter Escape Solution

Question

I recently managed to solve an algorithmic problem by enumerating all possible conditions. However, I believe that through some mathematical artifice, it would be possible to solve the problem more simply.

The problem can be seen here: https://neps.academy/problem/5

A fugitive, a helicopter and a police officer are in different positions on a circular track, exactly as shown in the figure next to them, with sixteen positions numbered from 0 to 15 in anti-clockwise direction. The helicopter and the policeman are always stopped. The objective of the fugitive is to get to the helicopter without passing the policeman first, of course. He may decide to run clockwise, or counterclockwise. In this problem, given the positions of the helicopter, the policeman and the fugitive, and the direction in which the fugitive decides to run, his program must tell whether or not he will be able to escape! In the picture, if the fugitive decides to run clockwise, he manages to flee; if he decides to run anti-clockwise, he will be arrested before arriving in the helicopter!

Entree

The input consists of a line with four integers: H, P, F and D, representing, respectively, the positions of the helicopter, the police officer and the fugitive, and the direction in which the fugitive runs, 1 for time and 1 for counterclockwise.

Exit

Your program must print a line containing the character "S" if the fugitive manages to escape, or "N" otherwise

Restrictions

The integers H, P and F are distinct and are between 0 and 15 inclusive

The intention of this post is to discuss some easier way to solve the problem in question... Please do not need to share resolution code. Answering the question with the mentioned solution (enumerate all conditions) is also not worth :P

PS.: If this post is not suitable for the forum, I apologize and if necessary, I can remove it.

Answer 1

Just analyze mathematically (equate) and see which one is nearest.

Let’s say the fugitive has to walk p positions to reach the police and h positions to reach the helicopter. So:

• P = F + D*p
• H = F + D*h

As we know the positions of each one, we can calculate how many positions these values represent:

• p = (P - F)/D
• h = (H - F)/D

The number representing the least amount of positions will indicate who is closest in that direction and therefore the fugitive will flee if h < p.

Given the example, F = 7, H = 4, P = 14 and D = -1, thus:

• p = (14 - 7)/(-1) = -7
• h = (4 - 7)/(-1) = 3

The expected output is S, indicating that h should be smaller, but p is smaller. This is because the equation results in the smallest number of positions the fugitive must walk to get to the other point. Being negative means that it would contradict the premise of the direction given as input. That is, the fugitive would have to walk 7 positions in the direction that was defined by D. Therefore, we cannot consider a negative value; always a positive one. To calculate the complement of the negative value obtained, just add 16, which is the total number of positions.

Thus, p, which was calculated as -7, becomes 9. Comparing p = 9 and h = 3, we obtain that in this configuration the helicopter will be closer and therefore the fugitive will successfully flee.

---

In a matter of code (Python), would be:

def fuga(H, P, F, D):
    h = (H - F)/D
    p = (P - F)/D

    h += 16 if h < 0 else 0
    p += 16 if p < 0 else 0

    return 'S' if h < p else 'N'

If the originally calculated value is negative (for both values), 16 shall be added. If h is less than p, the escape will be successful.

The number of operations that this solution performs does not depend on the input values, thus configuring a complexity solution O(1).

testes = [
    (4, 14, 7, -1, 'S'),
    (4, 14, 7, 1, 'N'),
    (15, 9, 8, -1, 'S'),
    (0, 14, 15, -1, 'N')
]

for teste in testes:
    H, P, F, D, resultado = teste
    assert resultado == fuga(H, P, F, D), f'O teste {teste} falhou'

^{See working on Repl.it}