Assume the Earth is flat and that it extends infinitely in all directions. Now assume we have one infinitely long train railway and
n trains in that railway. All trains have different speeds and all trains are going in the same direction. When a faster train reaches a slower train, the two trains connect (becoming a single train) and the new train keeps going at the speed with which the slower train was going.
E.g., if we have two trains, one going at speed 1 and another at speed 9, the lines below "simulate" what would happen on the railway:
9 1 9 1 11 11 11
whereas if the trains start in a different order, we'd have
1 9 1 9 1 9 1 9 etc...
With that being said, given a train/position/speed configuration there comes a time when no more connections will be made and the number of trains on the railway stays constant.
Given the number
n of trains in the railway, your task is to compute the total number of trains there will be on the railway, after all the connections have been made, summing over all
n! possible arrangements of the
A possible algorithm would be:
- Start counter at 0
- Go over all possible permutations of the train speeds
- Simulate all the connections for this permutation
- Add the total number of remaining trains to the counter
- Return the counter
Note that you can assume the train speeds are whatever
n distinct numbers that you see fit, what really matters is the relationships between train speeds, not the magnitudes of the differences in speeds.
You must take
n, a positive integer, as input.
An integer representing the total number of trains that there will be on the railway, summed over all possible permutations of the trains.
1 -> 1 2 -> 3 3 -> 11 4 -> 50 5 -> 274 6 -> 1764 7 -> 13068 8 -> 109584 9 -> 1026576 10 -> 10628640 11 -> 120543840 12 -> 1486442880 13 -> 19802759040 14 -> 283465647360 15 -> 4339163001600 16 -> 70734282393600 17 -> 1223405590579200 18 -> 22376988058521600 19 -> 431565146817638400 20 -> 8752948036761600000
This is code-golf so shortest submission in bytes, wins! If you liked this challenge, consider upvoting it! If you dislike this challenge, please give me your feedback. Happy golfing!