14
$\begingroup$

On the three paths of a station are A, B, and C types of train cars as shown in the figure.

enter image description here

A locomotive driver (L) can attach from 1 to 9 train cars to a locomotive at any time, move them to the right path, and then return them to any left path.

For example, if the locomotive picks up 2 train cars from track no. 3 to track no. 1, then after such an action, the distribution of train cars along the tracks will be as follows:

  1. А C B А C
  2. B C А
  3. B

We code these actions by one line as: 2 3 1

Question 1.

It is necessary to develop an algorithm for the driver's actions to sort train cars. On each path, the train cars the same type should be (it doesn’t matter which path).

Question 2. It is necessary to show that your solution is the shortest.

Source: vos.olimpiada.ru/ (in Russian).

$\endgroup$
  • 2
    $\begingroup$ old but good question :) $\endgroup$ – Oray Jun 6 at 8:19
  • 3
    $\begingroup$ They are probably not trains, but train cars. $\endgroup$ – trolley813 Jun 6 at 11:49
  • 1
    $\begingroup$ Cool problem! I would be interested to solve a larger case of this. Reminds me of towers of Hanoi. $\endgroup$ – Dmitry Kamenetsky Jun 6 at 12:38
  • 1
    $\begingroup$ @AlwaysConfused If the tracks were ♥ / ♦ / ♣ instead of 1 / 2 / 3, then "♦3♥" (231) would mean "move 3 carriages from track ♦ to track ♥". The first and last numbers are which track, and the middle number is how many carriages. $\endgroup$ – Chronocidal Jun 8 at 16:08
  • 2
    $\begingroup$ @Chronocidal, I think the first number in the notation is the number of carriages. Not the second one. So 231 means move 2 cars from track 3 to track 1. $\endgroup$ – justhalf Jun 10 at 3:41
19
$\begingroup$

Here is an optimal solution:

7 moves:
213, 121, 431, 113, 223, 132, 212

Or in full:

 acb
 bca
 bac
 
 a
 bca
 baccb
 
 aa
 bc
 baccb
 
 aaaccb
 bc
 b
 
 aaacc
 bc
 bb
 
 aaacc
 
 bbbc
 
 aaacc
 c
 bbb
 
 aaa
 ccc
 bbb

Proof of optimality:

There are 6 pairs of adjacent carriages of mismatched types. Each move can break up at most one such adjacent pair by moving away the right carriage to another track. The left-most carriages of the tracks are not all different types - there are two Bs - so at least one of the left-most carriages will have to move as well. Therefore at least 7 moves are necessary. This solution uses 7 moves, so cannot be made shorter.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Could you please explain how many 7 moves solutions can be? $\endgroup$ – Nick Jun 6 at 6:28
  • 2
    $\begingroup$ @Nick: There are a lot of them. I did a computer search, and it says there are 562, of which 179 end as aaa/bbb/ccc and 383 as aaa/ccc/bbb. $\endgroup$ – Jaap Scherphuis Jun 7 at 16:06
3
$\begingroup$

I reached to a 9-step (8 moves) solution it is as follows:

GIF animated version

RailGIF

Still-image version:

1. 1 2. 2 3. 3 4. 4 5. 5 6. 6 7. 7 8. 8 9. 9

(although I could not understand the 123 notation; sorry about it)

| improve this answer | |
$\endgroup$

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.