0
$\begingroup$

Let K players be among N towns in a circular position.

  • On each turn, only one player can move.
  • A player cannot move if he is the one who moved in the previous turn.
  • A player can only move clockwise to the next town, ex from town 0 to town 1, from town T to town T + 1, from town N - 1 to town 0.
  • Each town at any point can have 0, 1, or more players.

What is the minimum number of turns, so all the players end up in the same town (if that's possible)?

Any algorithm for solving this puzzle? It is a school assignment.

$\endgroup$
2
  • 3
    $\begingroup$ There isn't always a solution with two players. $\endgroup$
    – orlp
    Jun 9 at 9:59
  • $\begingroup$ @orlp I know, that's why I added (if that's possible) $\endgroup$ Jun 9 at 11:49
2
$\begingroup$

You can determine simply if there is no solution. Case $K=2$ with the players on different and non-adjacent cities (thanks orlp to point it).

Let's first assume a simpler problem where players may move several time in a row. Then you know the arrival point is necessarily one of the initial position of a player. Indeed, a city just before one with no player on it is reached $K$ turns before.

Let's call :

  • $D(i)$, the number of turns needed to meet all players on starting city $i$.
  • $S$ is the number of starting cities ($S \le K$ and $S \le N$).
  • $p_i$ is the clockwise position of starting city $i$.
  • $s_i$ is the number of players on starting city $i$.

First of all, you need to find all starting cities and the number of player on it. Depending on input format, It may be done in $O(K)$, $O(S)$ or $O(N)$. So the solution is the minimum of $D$. You may compute all $D(k)$ with the trivial sum in $O(S^2)$ :

$D(k) = \sum_{i=0}^{S-1} ((p_k-p_i) \mod{N}) s_i$.

But it is more efficient to do it by difference with the sum of the previous city, achieving $O(S)$:

$D(k+1) - D(k) = (K-s_{k+1}) \times((p_{k+1}-p_{k}) \mod{N}) - s_{k+1} \times (p_{k+1}-p_{k}) \mod{N})$

So now, to consider the "turn alternation" constraint, you have an additional computation to do, let's call it $A_k$, the number of turns needed to advance all players some more cities so they can meet respecting alternation. Let's also define $L(k)$, the longest distance a player may have to do to reach starting city $k$.

Note that $L(k) = p(k+1)-p(k) \mod{N}$.

all $A(k)$ are computed in $O(S)$ :

if $L(k) \le \frac{D(k)+1}{2}$ then $A(k) = 0$, basic alternation let you finish on starting city $k$.

else $A(k) = K \times ceil( \frac{L(k)-(\frac{D(k)+1}{2})}{K-2} )$, as you may alternate with the $K-1$ other players.

And the solution to your problem is $\min(D(k)+A(k))$ that you find in $O(S)$ = $O(min(N, K))$ with an adapted input format, else probably something like $O(max(N, K))$.

EDIT: exemple with :

  • $N=13, K=5$
  • $p=[0, 10, 11]$
  • $s=[1, 3, 1]$
  • $S=3$

$D(0) = 0\times1 + 3\times3 + 2\times1 = 11$

$D(10) = D(0) + 2\times10 - 3\times3 = 22$

$D(11) = D(10) + 4\times1 - 1\times12 = 14$

$L(0)= 3 \implies A(0) = 0$

$L(10) = 10 \implies A(10) = 0$

$L(11) = 11 \implies A(11) = K \times ceil(\frac{4.5}{K-2}) = 2\times K = 10$

It means you cannot chose city 11 as arrival but city 0 instead making players advancing 2 extra cities, which would take a total of 24 turns (as the player starting at 0 would have done a full cycle). Of course, the answer to the problem, is the first one going to city 0 without moving the player on it in 11 turns.

$\endgroup$
5
  • $\begingroup$ I don't get the point of alternating with the other K - 1 players, since a player cannot go counter clock wise and the again clock wise. Assume city_0 has 1 player, city_10 has 3 players and city_11 has 1 player. How would you determine the D(k) and A(k) for the city_11 or city_12 ?? $\endgroup$ Jun 9 at 17:25
  • $\begingroup$ @entropyfever I added your exemple as edit. Also sligthly corrected the $A(k)$ formula. The divisor is $K-2$ instead of $K-1$ (explaining why the 2 players case generally fails). The idea, is once all players but one have arrived, they have to all advance once to let the last one advance K-1 times, generating an offset on the arrival city. But relatively to the group, the last one only advanced $K-2$ times. You repeat this as long all players do not meet computing $A(k)$. $\endgroup$
    – Optidad
    Jun 9 at 20:45
  • $\begingroup$ @Optitad It seems ok with an exception which I will add (and please give me some feedback) before marking it as correct. Suppose city_0 with 1 player, city_1 empty, city_2 many players, city_3 empty. The solution should be city_2 (as target city) as it has many players, but it has to "give/led" only two of its players (not all of them) to go and pick up the lone player in city_0. The two players are needed to achieve alternation. So I don't think your algorithm takes this into account but it really helped me a lot to have a better understanding of the puzzle. Thanx ! $\endgroup$ Jun 10 at 17:49
  • $\begingroup$ Actually it is just a modification of L(K) <= ... to know if you can end up in starting city. You just take into account that if the initial L(k) is positive, then also check if the city can give 2 players to make a full rotation and go pick up everyone $\endgroup$ Jun 10 at 17:55
  • 1
    $\begingroup$ @entropyfever You are right, the $L$ to $D$ comparison had a little mistake, now it should be good. The +1 stands for the fact the furthest player may first move once then he cannot move more than the sum of all other player moves. $\endgroup$
    – Optidad
    Jun 11 at 8:34
0
$\begingroup$

Quite simple if time complexity O(K*N) is acceptable:

For each of the N towns, you calculate how long it takes for everyone to reach that town. First, you add everyone's distance to that town. That's one minimum requirement. Second, since nobody can do two turns in a row, find the person furthest away. If the person is X steps away, then they can't reach that town earlier than after 2X-1 moves. So you calculate max (sum of all distances, 2*largest distance - 1). You do that for each town and chose the smallest value.

You can get the time complexitiy a lot lower by counting how many players are in each town initially, calculating the numbers for the first time, and for each of the following towns calculate the numbers in constant time by using the numbers of the previous town. (For example if you know the sum of distances to town 3, then for town 4 you increase that sum by K since everyone goes one step further, then subtract N * number of players in town 4, because these don't move N steps but no steps at all. )

$\endgroup$
2
  • $\begingroup$ Can you be a little bit more thorough at "So you calculate max (sum of all distances, 2*largest distance - 1). You do that for each town and chose the smallest value.", what exactly is that and why is it needed ? Is it to check if the furthest player is alone, if it's possible to reach the goal town by the moves the intermediate players can do ? Can you please explain a little bit more ? $\endgroup$ Jun 9 at 11:55
  • $\begingroup$ Also your algorithm does not take into account if there is a solution. For example the configuration might be: town with 1 player, ...., town with 3 players, ...., goal town. How can you know if the player in the first town can reach the goal town if there are no moves left for the three players ? meaning that the 3 players reached the goal town earlier $\endgroup$ Jun 9 at 12:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.