Click here to Skip to main content
15,867,568 members
Please Sign up or sign in to vote.
4.20/5 (2 votes)
See more:
Note: In Chris' absence[^] I've stepped up to post this week's challenge. Enjoy!

Consider a randomized list of the integers 1 to N. You want to sort it using only the following actions:

Swap the first and last list elements. (S)
Pop off the first element and append it to the end of the list. (P)

Using S and P you can swap any adjacent elements by calling P until the two elements in question are the first and last items in the list, then calling S to swap them, then calling P again until they are in the original indices (now swapped).

Create a method that takes in a permutation of the numbers from 1 to N (N > 1). It can be given as a list or string or whatever is convenient. It should output a sequence of S's and P's that would sort the permutation when applied from left to right. This sequence does not have to be optimally short, but shorter it is the better.

You may not hard code your program to suit any data.

What I have tried:

Example

If the input was [2, 1, 3] the output might be SP because

S applied to [2, 1, 3] makes it [3, 1, 2],
and P applied to [3, 1, 2] makes it [1, 2, 3], which is sorted.

Test data
1. Length 3
[2, 1, 3]
2. Length 7
[2, 7, 5, 3, 4, 6, 1]
3. Length 41
[7, 12, 17, 2, 14, 15, 33, 20, 37, 18, 9, 25, 41, 26, 39, 29, 16, 5, 23, 24, 35, 38, 32, 6, 11, 21, 27, 8, 40, 3, 10, 36, 13, 30, 31, 28, 1, 4, 19, 22, 34]
4. Length 52
[19, 49, 34, 26, 38, 3, 14, 37, 21, 39, 46, 29, 18, 6, 15, 25, 28, 47, 22, 41, 32, 51, 50, 5, 45, 4, 30, 44, 10, 43, 20, 17, 13, 36, 48, 27, 35, 24, 8, 12, 40, 2, 1, 16, 7, 31, 23, 33, 42, 52, 9, 11]
5. Length 65
[12, 53, 4, 5, 17, 32, 58, 54, 18, 43, 21, 26, 51, 45, 9, 2, 35, 28, 40, 61, 57, 27, 62, 39, 24, 59, 36, 25, 20, 33, 63, 56, 64, 47, 38, 7, 13, 34, 16, 30, 49, 22, 37, 3, 48, 11, 52, 1, 29, 42, 50, 23, 6, 8, 60, 65, 46, 10, 41, 31, 44, 15, 14, 19, 55]
6. Length 69
[58, 15, 63, 18, 24, 59, 26, 37, 44, 67, 14, 52, 2, 31, 68, 54, 32, 17, 55, 50, 42, 56, 65, 29, 13, 41, 7, 45, 53, 35, 21, 39, 61, 23, 49, 12, 60, 46, 27, 57, 28, 40, 10, 69, 1, 6, 19, 62, 8, 30, 64, 34, 3, 43, 38, 20, 25, 33, 66, 47, 4, 36, 16, 11, 5, 22, 51, 48, 9]
7. Length 75
[14, 69, 1, 43, 32, 42, 59, 37, 70, 63, 57, 60, 56, 73, 67, 6, 11, 36, 31, 22, 40, 7, 21, 35, 50, 64, 28, 41, 18, 17, 75, 54, 51, 19, 68, 33, 45, 61, 66, 52, 49, 65, 4, 72, 23, 34, 9, 15, 38, 16, 3, 71, 29, 30, 48, 53, 10, 8, 13, 47, 20, 55, 74, 27, 25, 62, 46, 24, 44, 39, 2, 26, 58, 12, 5]
8. Length 80
[3, 65, 44, 14, 19, 6, 11, 29, 79, 35, 42, 16, 68, 7, 62, 30, 38, 46, 15, 9, 75, 5, 52, 32, 22, 70, 64, 13, 21, 47, 10, 4, 55, 40, 45, 56, 77, 27, 23, 72, 17, 71, 53, 20, 18, 25, 73, 59, 36, 34, 37, 57, 1, 69, 24, 58, 33, 76, 2, 12, 49, 61, 78, 67, 66, 63, 50, 80, 28, 48, 26, 51, 41, 60, 31, 54, 39, 8, 74, 43]
9. Length 103
[40, 62, 53, 6, 32, 85, 8, 83, 33, 29, 87, 93, 22, 37, 80, 12, 74, 69, 64, 9, 18, 98, 17, 45, 60, 38, 10, 103, 19, 5, 54, 15, 90, 100, 79, 91, 46, 82, 43, 31, 51, 96, 30, 70, 76, 16, 55, 77, 11, 65, 58, 75, 61, 3, 28, 24, 101, 20, 41, 72, 86, 56, 35, 50, 78, 27, 67, 95, 44, 68, 48, 26, 39, 97, 21, 49, 102, 73, 63, 7, 71, 52, 1, 88, 34, 42, 14, 47, 36, 99, 4, 13, 94, 89, 59, 92, 57, 25, 23, 66, 81, 2, 84]
10. Length 108
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108]
11. Length 109
[48, 89, 25, 64, 8, 69, 81, 98, 107, 61, 106, 63, 59, 50, 83, 24, 86, 68, 100, 104, 56, 88, 46, 62, 94, 4, 47, 33, 19, 1, 77, 102, 9, 30, 44, 26, 16, 80, 67, 75, 70, 96, 108, 45, 79, 51, 12, 38, 73, 37, 65, 31, 60, 22, 28, 3, 43, 71, 105, 91, 93, 101, 13, 97, 29, 72, 82, 87, 27, 5, 17, 10, 34, 84, 53, 15, 78, 41, 85, 6, 14, 57, 76, 7, 23, 99, 32, 95, 49, 2, 21, 109, 74, 39, 11, 103, 18, 90, 35, 40, 58, 20, 55, 52, 36, 54, 42, 92, 66]
12. Length 151
[61, 7, 8, 79, 78, 4, 48, 13, 14, 117, 12, 96, 130, 118, 63, 110, 72, 57, 86, 126, 62, 10, 29, 102, 99, 28, 56, 135, 11, 151, 141, 97, 45, 109, 38, 150, 40, 149, 52, 140, 106, 80, 66, 134, 125, 137, 31, 85, 68, 94, 36, 26, 95, 92, 49, 25, 120, 148, 33, 73, 41, 100, 58, 127, 60, 122, 133, 9, 19, 81, 59, 55, 103, 146, 42, 21, 128, 75, 101, 82, 50, 142, 131, 76, 20, 69, 139, 83, 16, 64, 17, 124, 90, 138, 37, 1, 34, 43, 129, 77, 23, 35, 144, 121, 113, 115, 114, 67, 98, 70, 145, 104, 71, 5, 119, 6, 18, 88, 116, 111, 132, 39, 89, 24, 15, 107, 27, 65, 30, 47, 143, 93, 53, 108, 2, 74, 123, 44, 51, 54, 87, 147, 84, 3, 112, 46, 32, 91, 136, 22, 105]
13. Length 173
[93, 14, 141, 125, 64, 30, 24, 85, 44, 68, 91, 22, 103, 155, 117, 114, 123, 51, 131, 72, 67, 61, 5, 41, 10, 20, 129, 86, 154, 108, 161, 2, 82, 153, 96, 50, 136, 121, 128, 126, 120, 111, 89, 113, 104, 84, 18, 109, 42, 83, 162, 124, 173, 116, 12, 54, 52, 39, 122, 49, 46, 1, 130, 71, 152, 73, 56, 34, 149, 75, 133, 8, 74, 45, 88, 23, 7, 60, 115, 134, 53, 119, 106, 81, 112, 31, 35, 172, 159, 38, 59, 69, 142, 146, 110, 170, 160, 166, 43, 58, 4, 107, 78, 156, 47, 33, 145, 63, 163, 27, 70, 77, 36, 16, 100, 26, 19, 151, 57, 32, 15, 13, 40, 169, 98, 132, 135, 62, 66, 90, 102, 171, 99, 148, 80, 144, 147, 168, 94, 143, 17, 3, 140, 97, 11, 65, 55, 92, 95, 127, 167, 150, 87, 118, 28, 137, 9, 29, 105, 157, 25, 165, 158, 21, 164, 101, 79, 76, 6, 138, 48, 37, 139]
14. Length 177
[68, 117, 61, 159, 110, 148, 3, 20, 169, 145, 136, 1, 120, 109, 21, 58, 52, 97, 65, 168, 34, 134, 111, 176, 13, 156, 172, 53, 55, 124, 177, 88, 92, 23, 72, 26, 104, 121, 133, 73, 39, 140, 25, 71, 119, 158, 146, 128, 18, 94, 113, 45, 60, 96, 30, 5, 116, 153, 90, 115, 67, 80, 112, 154, 9, 17, 10, 33, 81, 38, 95, 118, 35, 160, 151, 150, 76, 77, 14, 147, 173, 135, 162, 114, 27, 100, 167, 74, 69, 165, 108, 79, 91, 48, 105, 125, 129, 75, 93, 11, 12, 64, 24, 170, 142, 98, 44, 37, 43, 78, 16, 28, 166, 155, 138, 164, 122, 163, 107, 130, 86, 56, 2, 161, 63, 126, 131, 144, 82, 106, 103, 32, 132, 54, 41, 171, 70, 85, 19, 143, 137, 87, 84, 66, 99, 102, 15, 49, 123, 175, 89, 51, 141, 62, 50, 36, 152, 47, 42, 8, 7, 46, 29, 22, 149, 139, 4, 40, 83, 6, 59, 57, 174, 31, 127, 101, 157]
15. Length 192
[82, 130, 189, 21, 169, 147, 160, 66, 133, 153, 143, 116, 49, 13, 63, 61, 94, 164, 35, 112, 141, 62, 87, 171, 19, 3, 93, 83, 149, 64, 34, 170, 129, 182, 101, 77, 14, 91, 145, 23, 32, 92, 187, 54, 184, 120, 109, 159, 27, 44, 60, 103, 134, 52, 122, 33, 78, 88, 108, 45, 15, 79, 137, 80, 161, 69, 6, 139, 110, 67, 43, 190, 152, 59, 173, 125, 168, 37, 151, 132, 1, 178, 20, 114, 119, 144, 25, 146, 42, 136, 162, 123, 31, 107, 131, 127, 51, 105, 2, 65, 28, 102, 76, 24, 135, 174, 9, 111, 98, 39, 74, 142, 70, 121, 154, 38, 113, 75, 40, 86, 100, 106, 181, 117, 95, 85, 138, 41, 167, 172, 4, 186, 17, 16, 104, 71, 81, 73, 57, 8, 140, 118, 158, 12, 148, 53, 29, 185, 18, 150, 22, 188, 72, 128, 84, 96, 47, 192, 126, 56, 163, 50, 157, 165, 97, 166, 180, 7, 46, 30, 191, 124, 5, 48, 175, 68, 36, 89, 177, 11, 176, 183, 99, 90, 55, 26, 10, 58, 115, 155, 179, 156]
16. Length 201
[23, 8, 58, 24, 19, 87, 98, 187, 17, 130, 116, 141, 129, 166, 29, 191, 81, 105, 137, 171, 39, 67, 46, 150, 102, 26, 163, 183, 170, 72, 160, 43, 9, 197, 189, 173, 196, 68, 100, 16, 93, 175, 74, 28, 133, 122, 27, 79, 107, 162, 62, 192, 108, 104, 97, 12, 60, 155, 161, 82, 167, 158, 149, 30, 124, 22, 168, 115, 134, 94, 34, 184, 127, 121, 177, 112, 142, 95, 164, 41, 59, 55, 143, 85, 176, 3, 156, 148, 153, 42, 180, 145, 78, 147, 119, 109, 139, 178, 61, 181, 136, 157, 91, 84, 47, 71, 70, 118, 18, 63, 80, 56, 123, 194, 117, 195, 152, 66, 48, 11, 99, 201, 128, 151, 138, 64, 21, 131, 159, 103, 75, 49, 169, 113, 53, 114, 69, 54, 165, 38, 101, 76, 200, 199, 140, 125, 193, 88, 32, 51, 126, 14, 13, 77, 52, 50, 198, 172, 5, 92, 96, 15, 106, 182, 31, 83, 120, 57, 135, 65, 7, 154, 20, 25, 45, 1, 6, 73, 40, 174, 132, 10, 111, 186, 190, 4, 36, 188, 185, 146, 44, 110, 179, 2, 90, 86, 35, 37, 33, 89, 144]
17. Length 201
[97, 146, 168, 5, 56, 147, 189, 92, 154, 13, 185, 109, 45, 126, 17, 10, 53, 98, 88, 41, 163, 99, 157, 35, 125, 34, 173, 171, 138, 104, 149, 172, 60, 183, 36, 65, 32, 180, 87, 167, 59, 84, 188, 11, 69, 57, 174, 61, 66, 7, 8, 111, 91, 58, 128, 94, 141, 139, 31, 78, 156, 70, 16, 162, 26, 33, 106, 175, 103, 21, 164, 110, 159, 80, 200, 82, 123, 144, 44, 148, 4, 55, 179, 184, 186, 124, 63, 107, 54, 112, 137, 165, 121, 25, 132, 196, 90, 89, 71, 160, 95, 117, 197, 37, 108, 39, 115, 12, 52, 119, 120, 79, 29, 49, 93, 22, 122, 161, 76, 38, 72, 169, 85, 178, 77, 105, 190, 100, 9, 86, 177, 194, 2, 136, 114, 51, 68, 19, 47, 195, 113, 193, 67, 96, 182, 170, 50, 83, 143, 166, 3, 192, 24, 127, 140, 176, 134, 158, 116, 199, 1, 135, 118, 145, 14, 15, 155, 48, 42, 73, 46, 102, 191, 28, 201, 181, 75, 133, 153, 6, 131, 130, 81, 20, 198, 64, 142, 150, 27, 101, 18, 30, 40, 23, 129, 43, 62, 187, 152, 151, 74]
18. Length 205
[161, 197, 177, 118, 94, 112, 13, 190, 200, 166, 127, 80, 115, 204, 186, 60, 50, 97, 175, 32, 26, 65, 16, 4, 55, 120, 143, 187, 121, 29, 18, 82, 17, 21, 144, 20, 88, 195, 99, 67, 203, 23, 176, 126, 137, 77, 70, 30, 103, 182, 113, 119, 36, 47, 90, 98, 54, 3, 49, 105, 57, 135, 153, 142, 174, 155, 158, 11, 157, 22, 171, 110, 28, 196, 129, 163, 79, 63, 38, 145, 140, 2, 128, 180, 106, 59, 25, 184, 81, 164, 95, 39, 68, 78, 178, 156, 72, 51, 202, 66, 48, 101, 71, 108, 130, 5, 107, 147, 199, 12, 27, 150, 167, 91, 64, 170, 191, 151, 149, 168, 34, 125, 188, 181, 139, 58, 75, 189, 124, 152, 183, 7, 111, 89, 84, 52, 141, 83, 69, 62, 73, 43, 123, 14, 179, 162, 114, 138, 117, 159, 74, 85, 10, 96, 86, 31, 132, 1, 104, 109, 45, 165, 148, 172, 154, 92, 173, 40, 19, 56, 37, 205, 44, 193, 122, 185, 93, 133, 53, 9, 169, 6, 61, 136, 46, 76, 33, 15, 116, 198, 160, 194, 131, 41, 42, 35, 146, 134, 192, 8, 87, 201, 100, 24, 102]
19. Length 211
[200, 36, 204, 198, 190, 161, 57, 108, 180, 203, 135, 48, 134, 47, 158, 10, 41, 11, 23, 127, 167, 121, 109, 211, 201, 1, 42, 40, 86, 104, 147, 139, 145, 101, 144, 166, 176, 92, 118, 54, 182, 30, 58, 123, 124, 67, 125, 154, 187, 168, 103, 17, 72, 98, 12, 184, 59, 87, 174, 93, 45, 116, 73, 69, 74, 80, 56, 14, 34, 85, 38, 185, 165, 110, 164, 151, 43, 192, 62, 4, 140, 170, 197, 111, 173, 141, 65, 77, 70, 136, 206, 83, 100, 148, 25, 183, 209, 189, 150, 33, 46, 16, 64, 114, 71, 102, 91, 39, 177, 196, 169, 128, 129, 44, 75, 188, 146, 26, 84, 138, 162, 194, 105, 37, 35, 88, 156, 130, 193, 19, 179, 82, 106, 181, 153, 28, 53, 21, 195, 66, 159, 115, 113, 112, 191, 172, 63, 143, 178, 94, 160, 186, 31, 29, 90, 68, 205, 155, 119, 117, 157, 107, 60, 79, 171, 149, 6, 24, 27, 50, 51, 126, 15, 133, 2, 131, 7, 49, 207, 163, 18, 120, 199, 61, 52, 32, 208, 20, 210, 13, 78, 55, 137, 202, 152, 8, 81, 76, 9, 97, 22, 99, 132, 95, 122, 89, 175, 5, 3, 96, 142]
20. Length 226
[204, 79, 88, 98, 197, 32, 40, 117, 153, 167, 29, 74, 170, 115, 127, 210, 22, 109, 65, 47, 41, 132, 110, 158, 192, 99, 96, 224, 190, 143, 33, 225, 195, 19, 70, 73, 54, 161, 75, 179, 181, 207, 26, 221, 66, 130, 152, 131, 30, 35, 155, 69, 68, 38, 129, 95, 116, 214, 7, 186, 62, 27, 212, 125, 216, 86, 148, 164, 141, 4, 140, 222, 16, 46, 12, 215, 78, 219, 211, 134, 118, 171, 121, 52, 123, 56, 220, 15, 25, 100, 137, 163, 51, 91, 10, 83, 55, 187, 182, 201, 149, 160, 8, 14, 218, 77, 3, 184, 114, 43, 122, 135, 142, 104, 120, 198, 45, 108, 85, 189, 151, 175, 136, 165, 226, 97, 124, 200, 60, 172, 20, 67, 1, 174, 87, 102, 119, 188, 223, 199, 103, 89, 49, 213, 57, 9, 101, 112, 36, 176, 194, 92, 145, 180, 168, 111, 94, 178, 39, 166, 193, 17, 2, 154, 58, 156, 217, 13, 80, 202, 206, 169, 107, 177, 144, 205, 139, 93, 34, 64, 106, 150, 146, 126, 185, 208, 63, 203, 105, 18, 191, 53, 183, 209, 6, 23, 84, 5, 61, 59, 162, 128, 37, 50, 28, 159, 173, 196, 24, 31, 72, 138, 82, 48, 133, 147, 42, 113, 81, 90, 71, 21, 11, 157, 76, 44]
21. Length 227
[197, 52, 91, 42, 29, 113, 82, 68, 147, 225, 80, 167, 117, 142, 140, 216, 65, 195, 97, 61, 133, 209, 214, 58, 152, 71, 56, 182, 201, 163, 227, 186, 63, 171, 207, 102, 161, 136, 224, 146, 92, 175, 45, 217, 6, 99, 20, 119, 210, 93, 77, 211, 21, 70, 90, 96, 115, 100, 183, 173, 69, 98, 172, 75, 111, 203, 19, 129, 35, 155, 74, 37, 23, 51, 192, 212, 33, 64, 59, 194, 112, 135, 1, 184, 5, 166, 185, 84, 199, 138, 144, 86, 128, 26, 190, 73, 179, 27, 118, 223, 46, 95, 159, 153, 226, 25, 180, 132, 189, 60, 32, 208, 123, 89, 87, 22, 181, 143, 47, 18, 198, 219, 156, 148, 193, 122, 110, 28, 106, 39, 30, 103, 4, 176, 114, 3, 131, 107, 204, 218, 141, 169, 16, 206, 36, 188, 174, 54, 94, 50, 205, 104, 170, 160, 72, 165, 78, 24, 222, 8, 108, 81, 76, 15, 13, 126, 79, 7, 105, 125, 162, 83, 41, 145, 139, 66, 127, 38, 12, 187, 130, 221, 48, 164, 191, 157, 88, 168, 196, 10, 9, 53, 124, 150, 31, 116, 49, 34, 200, 134, 220, 121, 2, 62, 149, 158, 101, 17, 202, 11, 109, 85, 55, 67, 120, 43, 154, 44, 215, 177, 178, 40, 57, 14, 213, 151, 137]
22. Length 230
[69, 204, 215, 61, 97, 149, 9, 11, 137, 71, 37, 219, 92, 115, 156, 159, 200, 222, 3, 89, 172, 177, 203, 45, 54, 82, 147, 176, 168, 6, 26, 81, 25, 132, 212, 70, 228, 122, 225, 141, 100, 12, 124, 30, 146, 73, 19, 49, 52, 62, 217, 166, 191, 102, 163, 50, 181, 7, 134, 58, 76, 199, 179, 169, 197, 108, 174, 22, 186, 171, 114, 103, 173, 68, 65, 4, 13, 117, 64, 10, 126, 77, 206, 133, 121, 60, 40, 38, 59, 178, 224, 211, 187, 80, 220, 140, 8, 34, 130, 41, 95, 105, 227, 66, 210, 180, 192, 106, 209, 107, 157, 188, 170, 101, 131, 87, 14, 165, 78, 182, 136, 193, 190, 20, 67, 125, 36, 5, 145, 218, 99, 138, 154, 16, 29, 152, 194, 53, 148, 93, 202, 229, 198, 109, 43, 214, 150, 51, 128, 216, 1, 83, 196, 135, 74, 119, 75, 42, 142, 72, 226, 185, 116, 162, 63, 2, 112, 33, 184, 158, 15, 213, 144, 223, 98, 57, 160, 143, 90, 44, 205, 35, 21, 48, 151, 85, 123, 32, 47, 39, 189, 161, 56, 207, 84, 94, 230, 46, 164, 113, 175, 18, 195, 110, 127, 96, 129, 88, 17, 153, 104, 91, 86, 31, 118, 111, 120, 201, 28, 221, 23, 139, 24, 27, 167, 208, 183, 155, 79, 55]
23. Length 238
[202, 18, 122, 135, 11, 57, 103, 35, 86, 2, 84, 232, 208, 186, 54, 77, 145, 101, 105, 137, 210, 234, 207, 93, 55, 63, 230, 66, 160, 10, 223, 36, 34, 216, 104, 174, 121, 25, 166, 75, 167, 176, 61, 32, 118, 89, 68, 5, 14, 27, 204, 99, 149, 88, 91, 222, 37, 144, 108, 78, 128, 131, 190, 17, 65, 168, 225, 165, 41, 49, 38, 72, 43, 147, 158, 74, 130, 7, 82, 64, 97, 69, 100, 22, 152, 85, 48, 33, 218, 47, 228, 113, 40, 185, 219, 112, 180, 120, 4, 213, 179, 194, 51, 96, 221, 44, 238, 31, 117, 114, 229, 81, 164, 193, 236, 26, 59, 30, 151, 12, 115, 170, 24, 70, 227, 159, 133, 52, 134, 203, 15, 197, 155, 83, 50, 111, 195, 139, 109, 127, 188, 87, 62, 157, 226, 142, 98, 76, 211, 138, 58, 140, 198, 220, 16, 46, 183, 107, 106, 29, 163, 173, 209, 217, 215, 1, 177, 233, 199, 110, 172, 23, 212, 79, 94, 102, 39, 20, 178, 150, 175, 119, 8, 13, 42, 156, 201, 73, 200, 124, 53, 161, 92, 123, 224, 143, 196, 28, 9, 6, 80, 56, 148, 125, 214, 60, 171, 153, 231, 181, 205, 19, 95, 206, 154, 132, 169, 116, 3, 126, 187, 162, 191, 67, 136, 45, 192, 189, 235, 129, 21, 141, 237, 184, 90, 146, 182, 71]
24. Length 241
[2, 33, 49, 83, 207, 204, 13, 57, 115, 86, 102, 219, 232, 44, 177, 197, 171, 227, 191, 10, 25, 162, 62, 11, 76, 214, 163, 201, 130, 91, 233, 194, 112, 179, 66, 139, 183, 116, 196, 193, 150, 211, 30, 144, 209, 97, 174, 3, 68, 38, 120, 165, 56, 64, 87, 15, 79, 131, 206, 96, 188, 7, 99, 195, 129, 8, 186, 78, 212, 125, 161, 230, 225, 239, 47, 107, 53, 218, 164, 106, 198, 215, 181, 226, 6, 175, 167, 236, 67, 80, 210, 128, 155, 40, 63, 74, 113, 89, 18, 190, 124, 221, 59, 149, 103, 42, 156, 157, 200, 168, 34, 77, 65, 146, 5, 187, 222, 231, 140, 141, 172, 234, 100, 94, 132, 237, 24, 216, 152, 22, 51, 69, 35, 43, 105, 23, 61, 1, 72, 135, 104, 9, 12, 21, 46, 192, 159, 205, 158, 109, 28, 98, 50, 122, 111, 71, 166, 229, 37, 114, 173, 134, 136, 81, 121, 185, 118, 223, 20, 14, 108, 82, 178, 54, 26, 153, 36, 39, 117, 147, 95, 90, 16, 17, 170, 119, 199, 19, 84, 213, 88, 93, 151, 4, 101, 142, 110, 184, 55, 138, 75, 133, 148, 145, 45, 70, 217, 143, 224, 241, 31, 240, 182, 52, 238, 126, 85, 154, 137, 160, 27, 180, 60, 29, 32, 169, 235, 123, 176, 48, 220, 203, 228, 127, 41, 58, 73, 92, 189, 202, 208]
25. Length 241
[105, 160, 132, 32, 10, 117, 76, 2, 190, 108, 178, 51, 71, 237, 232, 47, 14, 124, 100, 31, 169, 196, 8, 184, 21, 151, 223, 86, 42, 127, 55, 58, 229, 4, 219, 46, 238, 179, 24, 194, 203, 122, 66, 15, 81, 146, 172, 106, 129, 135, 216, 120, 92, 231, 144, 195, 181, 162, 69, 45, 137, 136, 9, 30, 5, 188, 91, 49, 147, 233, 198, 17, 241, 163, 36, 18, 183, 59, 16, 29, 116, 182, 41, 48, 23, 39, 154, 210, 68, 167, 95, 213, 79, 225, 37, 157, 109, 143, 78, 142, 173, 155, 200, 110, 20, 73, 141, 168, 156, 126, 150, 201, 114, 1, 230, 211, 217, 131, 140, 204, 209, 149, 103, 199, 165, 175, 35, 107, 74, 63, 193, 239, 218, 234, 197, 224, 174, 121, 60, 88, 22, 171, 133, 207, 152, 34, 43, 228, 125, 115, 101, 7, 12, 220, 82, 153, 134, 52, 130, 70, 72, 44, 177, 89, 65, 98, 94, 53, 208, 227, 161, 3, 123, 236, 221, 87, 102, 50, 90, 180, 185, 186, 67, 77, 26, 212, 27, 222, 6, 145, 11, 13, 84, 25, 164, 64, 85, 139, 214, 189, 61, 96, 191, 128, 93, 138, 148, 19, 119, 202, 75, 176, 159, 56, 104, 206, 40, 187, 215, 62, 166, 240, 112, 226, 170, 83, 97, 57, 99, 38, 28, 113, 205, 158, 235, 111, 54, 192, 118, 80, 33]
26. Length 244
[89, 13, 154, 161, 235, 225, 92, 188, 215, 194, 54, 58, 128, 21, 165, 85, 144, 205, 142, 77, 109, 24, 83, 69, 72, 7, 224, 240, 191, 204, 183, 203, 68, 70, 63, 95, 206, 170, 153, 180, 45, 178, 35, 27, 190, 132, 222, 41, 40, 156, 97, 20, 217, 177, 167, 65, 23, 136, 216, 234, 38, 201, 236, 164, 82, 241, 10, 141, 148, 229, 5, 125, 113, 159, 193, 187, 130, 179, 52, 108, 86, 196, 174, 123, 56, 116, 227, 30, 239, 98, 186, 67, 135, 118, 163, 43, 32, 50, 231, 226, 232, 172, 200, 99, 6, 143, 39, 93, 107, 34, 129, 157, 100, 127, 15, 84, 81, 73, 121, 220, 44, 8, 57, 105, 91, 171, 162, 211, 244, 104, 112, 238, 212, 133, 71, 192, 145, 160, 87, 181, 60, 184, 119, 4, 55, 96, 53, 12, 213, 124, 94, 22, 42, 3, 48, 131, 117, 140, 138, 228, 219, 155, 59, 29, 202, 169, 114, 101, 47, 233, 176, 139, 207, 33, 79, 16, 51, 66, 75, 90, 198, 168, 166, 31, 151, 49, 208, 150, 111, 14, 25, 197, 17, 76, 80, 78, 9, 173, 26, 137, 19, 120, 199, 106, 152, 88, 147, 36, 158, 28, 243, 221, 110, 74, 175, 237, 61, 2, 62, 214, 189, 134, 195, 218, 18, 102, 46, 103, 11, 122, 146, 185, 182, 209, 1, 149, 115, 64, 37, 126, 230, 223, 242, 210]
27. Length 246
[28, 186, 214, 18, 220, 73, 20, 88, 234, 187, 27, 102, 22, 129, 10, 228, 196, 56, 47, 2, 16, 67, 124, 137, 177, 179, 223, 147, 188, 23, 103, 109, 149, 60, 229, 99, 222, 90, 49, 80, 158, 93, 171, 71, 175, 143, 19, 212, 40, 226, 219, 120, 146, 66, 167, 232, 94, 174, 237, 9, 173, 70, 122, 241, 58, 82, 191, 211, 180, 104, 53, 36, 83, 37, 131, 25, 162, 32, 210, 144, 145, 69, 135, 63, 154, 165, 46, 57, 50, 74, 128, 140, 112, 118, 125, 231, 221, 233, 95, 200, 153, 6, 166, 98, 208, 91, 89, 141, 4, 26, 134, 86, 8, 30, 157, 156, 224, 201, 243, 7, 161, 1, 84, 115, 44, 230, 78, 79, 5, 17, 194, 148, 152, 121, 193, 107, 240, 181, 29, 43, 65, 164, 45, 110, 64, 195, 216, 127, 59, 197, 178, 151, 139, 85, 75, 11, 204, 184, 77, 54, 51, 205, 108, 142, 130, 138, 238, 87, 38, 101, 96, 31, 215, 244, 242, 172, 213, 136, 97, 35, 39, 76, 42, 245, 123, 227, 24, 168, 33, 159, 217, 239, 55, 176, 68, 207, 106, 132, 15, 116, 61, 198, 62, 182, 225, 202, 105, 150, 183, 81, 170, 13, 41, 199, 3, 185, 235, 14, 155, 21, 126, 119, 169, 72, 12, 236, 48, 209, 190, 113, 218, 100, 52, 111, 189, 92, 192, 114, 117, 160, 133, 203, 163, 34, 206, 246]
28. Length 250
[119, 57, 59, 181, 212, 120, 236, 121, 99, 247, 138, 187, 175, 108, 107, 197, 123, 101, 141, 77, 201, 3, 52, 60, 56, 240, 157, 39, 42, 199, 23, 18, 136, 74, 137, 143, 229, 170, 20, 160, 206, 219, 191, 185, 46, 223, 150, 190, 116, 96, 198, 221, 220, 159, 238, 48, 176, 113, 168, 33, 44, 142, 67, 244, 13, 218, 122, 246, 214, 234, 237, 27, 165, 24, 153, 90, 84, 154, 235, 196, 80, 111, 102, 231, 228, 135, 16, 148, 26, 45, 10, 71, 156, 224, 183, 232, 72, 94, 132, 54, 58, 248, 144, 213, 139, 129, 245, 115, 25, 164, 87, 19, 193, 81, 32, 78, 91, 167, 171, 40, 92, 226, 109, 69, 86, 38, 61, 5, 14, 118, 145, 103, 53, 93, 172, 178, 225, 68, 163, 210, 179, 192, 208, 169, 17, 12, 50, 233, 6, 55, 243, 158, 88, 188, 242, 36, 173, 126, 155, 184, 216, 149, 47, 76, 200, 1, 112, 28, 161, 174, 41, 73, 222, 66, 37, 63, 64, 124, 89, 205, 9, 186, 202, 70, 203, 127, 105, 250, 182, 79, 43, 133, 8, 241, 114, 128, 51, 83, 98, 49, 209, 7, 95, 151, 162, 189, 180, 75, 195, 62, 207, 21, 104, 30, 117, 110, 140, 29, 227, 249, 82, 152, 11, 34, 85, 106, 217, 211, 2, 35, 215, 4, 230, 134, 31, 194, 97, 22, 125, 130, 100, 239, 131, 166, 65, 15, 146, 177, 204, 147]
29. Length 253
[46, 245, 174, 180, 85, 29, 141, 70, 252, 119, 214, 225, 86, 91, 41, 67, 219, 118, 127, 243, 2, 71, 157, 114, 55, 92, 5, 200, 199, 139, 191, 235, 153, 102, 206, 171, 117, 58, 223, 249, 11, 211, 202, 175, 156, 133, 57, 163, 47, 65, 213, 247, 189, 111, 177, 49, 124, 154, 164, 145, 80, 15, 232, 142, 39, 69, 201, 185, 229, 215, 170, 42, 3, 248, 169, 136, 149, 218, 237, 90, 135, 7, 242, 246, 23, 186, 31, 4, 167, 207, 173, 132, 195, 196, 78, 212, 22, 35, 194, 54, 184, 183, 222, 230, 88, 43, 144, 151, 34, 97, 6, 109, 37, 147, 72, 158, 134, 33, 51, 238, 165, 162, 9, 63, 166, 113, 137, 198, 50, 121, 106, 224, 19, 104, 95, 129, 193, 79, 192, 122, 30, 12, 234, 168, 76, 103, 73, 66, 188, 178, 172, 176, 250, 182, 110, 231, 155, 26, 197, 10, 152, 98, 131, 25, 36, 81, 138, 150, 227, 24, 112, 120, 204, 75, 8, 179, 94, 17, 140, 32, 77, 61, 233, 38, 205, 93, 99, 27, 208, 56, 216, 48, 241, 20, 130, 240, 115, 83, 60, 108, 28, 13, 89, 128, 160, 82, 40, 126, 16, 253, 21, 251, 228, 59, 159, 64, 203, 236, 52, 18, 181, 105, 107, 239, 220, 44, 74, 125, 209, 84, 226, 217, 210, 190, 101, 100, 68, 116, 161, 148, 244, 221, 96, 45, 123, 187, 62, 87, 53, 1, 146, 143, 14]
30. Length 256
[159, 248, 75, 43, 111, 38, 4, 17, 155, 87, 81, 208, 53, 230, 65, 11, 108, 228, 146, 212, 137, 225, 144, 189, 86, 105, 84, 128, 97, 50, 223, 15, 83, 169, 217, 47, 88, 236, 114, 181, 115, 177, 102, 250, 246, 104, 80, 45, 240, 14, 196, 52, 247, 41, 198, 32, 182, 206, 226, 101, 70, 94, 113, 49, 254, 59, 42, 154, 77, 253, 112, 215, 99, 25, 134, 92, 95, 150, 64, 178, 118, 79, 130, 63, 129, 131, 57, 218, 85, 204, 3, 163, 158, 186, 10, 199, 24, 125, 251, 51, 74, 160, 207, 120, 233, 30, 19, 9, 56, 167, 58, 117, 164, 54, 220, 229, 234, 203, 211, 103, 205, 69, 39, 5, 31, 191, 106, 180, 116, 245, 21, 222, 91, 235, 8, 2, 214, 29, 238, 176, 135, 61, 227, 202, 122, 252, 231, 89, 187, 37, 149, 96, 190, 172, 73, 18, 71, 1, 179, 46, 156, 201, 165, 256, 151, 27, 242, 188, 126, 124, 244, 100, 107, 143, 170, 72, 255, 40, 67, 192, 185, 219, 20, 157, 98, 237, 136, 168, 141, 224, 232, 44, 139, 132, 22, 60, 109, 90, 175, 171, 62, 23, 161, 12, 76, 210, 68, 184, 93, 243, 48, 209, 174, 200, 121, 123, 36, 173, 140, 133, 145, 6, 110, 152, 142, 241, 55, 138, 147, 193, 213, 127, 7, 34, 66, 153, 26, 13, 162, 183, 239, 78, 249, 221, 28, 194, 16, 35, 33, 82, 195, 148, 216, 119, 166, 197]

Points awarded for the least number of Ps & Ss.
Posted
Updated 27-Jul-17 8:48am
v3
Comments
PIEBALDconsult 24-Mar-17 9:37am    
I see no point in using Pops; Swaps should be enough for anybody.
Given [ 2 , 1 , 3 ], define new (sub) list [ 2 , 1 ], Swap, done.
Patrice T 31-Mar-17 5:12am    
Hi Graeme,
Interesting challenge, because it is open.
Unfortunately, I will not submit a solution, not enough time to work on it (job take too much time this week).
Graeme_Grant 31-Mar-17 5:17am    
Yeah, I thought so...

I would submit a solution but as I am the one asking, I can't. Maybe Chris will extend it for another week.

I have some other interesting ones ... might forward them to Chris to use at a later time...
Patrice T 14-Apr-17 22:19pm    
Hi Greame,
I posted my solution, so if no one else is working on the challenge, I think you can post your solution.
Patrice T 25-Jul-17 18:25pm    
Hi,
Nice to see you back online.
I am still curious to see your approach to this challenge. :)

This is basically a bubble sort implementation: looping through the sequence, swapping items if they are not in order.
C#
class Sorter {
    private readonly int[] data;
    private readonly List<char> sortSequence = new List<char>();

    public Sorter(int[] data) {
        this.data = data;
    }

    public string Sort() {
        while (!IsSorted())
            if(IsInSequence(LastItem, FirstItem))
                Pop(); // if the two elements are sorted move on
            else
                Swap(); // swap them if they are not in order

        return new string(sortSequence.ToArray());
    }

    private bool IsInSequence(int x, int y) {
        return x < y                         // must be a rising sequence
            || (x == data.Length && y == 1); // except for last/first item boundary
    }

    private void Swap() {
        var tmp = FirstItem;
        FirstItem = LastItem;
        LastItem = tmp;
        sortSequence.Add('S');
    }

    private void Pop() {
        var first = FirstItem;
        Array.Copy(data, 1, data, 0, data.Length - 1);
        LastItem = first;
        sortSequence.Add('P');
    }

    private bool IsSorted() {
        for (int i = 1; i < data.Length; i++)
            if (data[i - 1] > data[i])
                return false;

        return true;
    }

    private int FirstItem  {
        get { return data[0]; }
        set { data[0] = value; }
    }

    private int LastItem {
        get { return data[data.Length - 1]; }
        set { data[data.Length - 1] = value; }
    }
}

And here are my results (input length vs. output length):
input output
    3     2
    7    19
   41  1642
   52  3336
   65  4913
   69  4966
   75  6780
   80  6246
  103 12142
  108     0
  109 13986
  151 24976
  173 34061
  177 38171
  192 42372
  201 48316
  201 47674
  205 49845
  211 51551
  226 58859
  227 56824
  230 59450
  238 64227
  241 66250
  241 66287
  244 71345
  246 73426
  250 72260
  253 68629
  256 77677

I know these are not optimal. I have another implementation which searches for best solution but this of course doesn't finish in reasonable time for anything bigger than 7 items.
 
Share this answer
 
Comments
PIEBALDconsult 24-Mar-17 18:48pm    
"which searches for best solution"
Yeah, my thought was that the cost of the analysis required to find the optimal solution outweighs the cost of a brute-force solution.
https://xkcd.com/1445/
Tomas Takac 25-Mar-17 8:36am    
I like that :)
UPDATED: Fixed a couple bugs including a weighting bug that could cause infinitely swapping the same position. Handles the first two example inputs as shown below but still runs into a stack overflow for larger data sets. I checked and it isn't stuck looping on a single swap, the algorithm just doesn't seem "smart" enough to solve the large set before recursion causes a stack overflow. Working on improving the algorithm now.

I gotta say, this is probably my favorite challenge so far. When you really dive into the problem it gets quite complex to optimize.

This is my first try at an optimal solution. Works well for small array numbers, runs into stack overflows at higher array numbers. Currently working to fix that but dunno if it'll be in time since I started so late. The idea is simple:
1) Create an ISort implementation for your data type.
2) Register this implementation with SortRegistry.
3) Call SPSorter.Solve(arrayToSort).

This will call SPOptimizer which weights the swaps based on how positively they affect the resulting array compared to the final result. This continues until a solution is found. The program has a default LSD Radix Sort for integers.
C#
static void Main(string[] args)
{
    SPSorter sorter = new SPSorter();
    int[][] testValues = new int[][] {
        new int[] { 2, 1, 3 },
        new int[] { 2, 7, 5, 3, 4, 6, 1 },
        new int[] { 7, 12, 17, 2, 14, 15, 33, 20, 37, 18, 9, 25, 41, 26, 39, 29, 16, 5, 23, 24, 35, 38, 32, 6, 11, 21, 27, 8, 40, 3, 10, 36, 13, 30, 31, 28, 1, 4, 19, 22, 34 }
        };
    Console.WriteLine(sorter.Solve(testValues[0])); //PS
    Console.WriteLine("-----");
    Console.WriteLine(sorter.Solve(testValues[1])); //PSPPPPPPSPPPSPS
    Console.WriteLine("-----");
    Console.WriteLine(sorter.Solve(testValues[2])); //Overflow
    Console.ReadKey();
}

C#
public class SPSorter
{
    public SortRegistry Registry { get; private set; }

    public SPSorter()
    {
        Registry = new SortRegistry();
        Registry.Register(new RadixSort());
    }
    public SPSorter(SortRegistry registry)
    {
        Registry = registry;
    }

    public string Solve<T>(IEnumerable<T> items)
    {
        T[] sortedItems = items.ToArray();
        int[] sortedIndices = Registry.Sort<T>().Execute(sortedItems);
        return SPOptimizer.Optimize(sortedIndices);
    }

    private class SPOptimizer
    {
        public static string Optimize(int[] sortedIndices) =>
            Analyze(CalculateShiftOffsets(sortedIndices));

        private static SPList<int> CalculateShiftOffsets(int[] sortedIndices)
        {
            int arrayLength = sortedIndices.Length;
            int[] shiftOffsets = new int[arrayLength];
            int rawShift = 0;
            for (int i = 0; i < arrayLength; i++)
            {
                if (sortedIndices[i] >= i)
                    rawShift = sortedIndices[i] - i;
                else
                    rawShift = arrayLength + sortedIndices[i] - i;
                shiftOffsets[(i + rawShift) % arrayLength] = (arrayLength - rawShift) % arrayLength;
            }
            return new SPList<int>(shiftOffsets);
        }

        private static string Analyze(SPList<int> shiftOffsets)
        {
            StringBuilder solution = new StringBuilder();
            int listCount = shiftOffsets.Count;
            int minimumShiftConstant = shiftOffsets.Count * 2;
            int swapLocation = 0;
            //Weight and compare swaps in the shift list
            for (int i = 0; i < listCount; i++)
            {
                int currentOffset = shiftOffsets.Data;
                shiftOffsets.Pop();
                int nextOffset = shiftOffsets.Data;
                int shiftConstant = (listCount - (nextOffset + 1)) + ((currentOffset == 0)?listCount:currentOffset) - 1;
                if (shiftConstant < minimumShiftConstant)
                {
                    minimumShiftConstant = shiftConstant;
                    swapLocation = (i + 1) % listCount;
                }
            }
            //Shift to the chosen swap
            for (int i = 0; i < swapLocation; i++)
            {
                shiftOffsets.Pop();
                solution.Append('P');
            }
            //Swap and update shift offsets
            if (++shiftOffsets.Data >= listCount)
                shiftOffsets.Data = 0;
            shiftOffsets.Swap();               
            if (--shiftOffsets.Data < 0)
                shiftOffsets.Data = listCount - 1;
            solution.Append('S');

            //Check if offsets are satisfied
            bool complete = true;
            for (int i = 0; i < listCount; i++)
            {
                if (shiftOffsets.Data != 0)
                    complete = false;
                shiftOffsets.Pop();
            }
            if (!complete)
                solution.Append(Analyze(shiftOffsets));
            return solution.ToString();
        }
    }
}

public class SortRegistry
{
    private readonly Dictionary<Type, object> _registeredSorts = new Dictionary<Type, object>();

    public IIndexSort<T> Sort<T>() =>
        _registeredSorts[typeof(T)] as IIndexSort<T>;

    public void Register<T>(IIndexSort<T> typeSort) =>
        _registeredSorts[typeof(T)] = typeSort;
}

public interface IIndexSort<T>
{
    int[] Execute(T[] list);
}

public class RadixSort : IIndexSort<int>
{
    private int bits = sizeof(int) * 8;
    public int BitGroupingCount { get; set; } = 8;

    public int[] Execute(int[] list)
    {
        List<KeyValuePair<int, int>> indexValuePairs = new List<KeyValuePair<int, int>>(list.Length);
        for (int i = 0; i < list.Length; i++)
            indexValuePairs.Add(new KeyValuePair<int, int>(i, list[i]));
        int groups = (int)Math.Ceiling((double)bits / BitGroupingCount);
        int groupMask = (1 << BitGroupingCount) - 1;
        int[] itemCount = new int[1 << BitGroupingCount];
        int[] itemOrder = new int[1 << BitGroupingCount];
        KeyValuePair<int, int>[] tempList = new KeyValuePair<int, int>[list.Length];

        for (int i = 0, groupOffset = 0; i < groups; i++, groupOffset += BitGroupingCount)
        {
            for (int j = 0; j < itemCount.Length; j++)
                itemCount[j] = 0;
            for (int j = 0; j < list.Length; j++)
            {
                int groupValue = (list[j] >> groupOffset) & groupMask;
                itemCount[groupValue]++;
            }
            itemOrder[0] = 0;
            for (int j = 1; j < itemCount.Length; j++)
                itemOrder[j] = itemOrder[j - 1] + itemCount[j - 1];                
            for (int j = 0; j < list.Length; j++)
            {
                int groupValue = (list[j] >> groupOffset) & groupMask;
                int orderValue = itemOrder[groupValue]++;
                tempList[orderValue] = indexValuePairs[j];
            }
            indexValuePairs = new List<KeyValuePair<int, int>>(tempList);
        }
        int[] results = new int[indexValuePairs.Count];
        for (int i = 0; i < indexValuePairs.Count; i++)
            results[i] = indexValuePairs[i].Key;
        return results;
    }
}

public class SPList<T> : IEnumerable<T>
{
    private class Node
    {
        public Node NextNode { get; set; } = null;
        public Node PreviousNode { get; set; } = null;
        public T Data { get; set; }
    }

    private Node head = new Node();
    public int Count { get; private set; } = 0;
    public T Data
    {
        get { return head.Data; }
        set { if (value != null) head.Data = value; }
    }

    public SPList(IEnumerable<T> list)
    {
        Node originalHead = head;
        Node newNode;
        foreach (T item in list)
        {
            newNode = new Node();
            newNode.Data = item;
            newNode.PreviousNode = head;
            head.NextNode = newNode;
            head = newNode;
            Count++;
        }
        head.NextNode = originalHead.NextNode;
        originalHead.NextNode.PreviousNode = head;
        head = head.NextNode;
    }

    public void Pop() =>
        head = head.NextNode;
    public void UnPop() =>
        head = head.PreviousNode;
    public void Swap()
    {
        //Change surrounding Node references to head and tail
        head.NextNode.PreviousNode = head.PreviousNode;
        head.PreviousNode.PreviousNode.NextNode = head;

        //Change head and tail next Node references
        head.PreviousNode.NextNode = head.NextNode;
        head.NextNode = head.PreviousNode;

        //Change head and tail previous Node references
        head.PreviousNode = head.PreviousNode.PreviousNode;
        head.NextNode.PreviousNode = head;

        //Change head
        Pop();
    }

    public List<T> ToList()
    {
        List<T> returnList = new List<T>();
        foreach (T data in this)
            returnList.Add(data);
        return returnList;
    }

    public SPList<T> Copy() =>
        new SPList<T>(this);

    public IEnumerator<T> GetEnumerator()
    {
        for (int i = 0; i < Count; i++)
        {
            yield return head.Data;
            Pop();
        }
    }
    IEnumerator IEnumerable.GetEnumerator() => 
        GetEnumerator();
}
 
Share this answer
 
v7
Comments
Graeme_Grant 31-Mar-17 5:19am    
I thought it was an interesting problem... Was expecting a few more devs to offer solutions.

Enjoyed looking at your solution.

Maybe email Chris directly and see if he is willing to extend it.
Jon McKee 31-Mar-17 5:35am    
Will do! I doubt any of the solutions will be "ground-breaking" (O(n) is about the best you can ask for) but it could still lead to some very interesting solutions!
Patrice T 31-Mar-17 11:54am    
How does it perform with data from question ?
Jon McKee 31-Mar-17 15:26pm    
Besides the stack overflows? Hehe. I figured out the area that's causing the overflow but was too tired to figure out what was wrong so I went to bed. Will be fixing it up today :thumbsup:
I think I got my solution (finally):
I used again my beloved Clipper language (FoxPro alike).

- First I use the list of numbers like a circular buffer: data don't move, pointers are.
- Then I build a helper array with final position in sorted array, so I don't make assumption on data: continuous values, holes in values, repeats.
VB
dest= array(size)
for scan= 1 to size
    dest[scan]= 1
    for scanp=1 to scan-1
        if lst[scan]<lst[scanp]
            dest[scanp]++
        else
            dest[scan]++
        endif
    next
next

- Then I choose 1 value in array and use it as a pivot and all other values are moving around.
- In order to get best result, I test every possible pivot

The whole problem is about making the pointers arithmetic right.

Source code:
VB
*   CCCP Code Challenge Code Project
*    Sort list with swaps and Rotates
procedure cccp8()
	set printer to cccp8.log
	set color to w/n
	clear
	set printer on
	? "      Size", "           ", "          S", "         P", "     Total", "     seconds"
	set printer off
	tot_nb_s= 0
	tot_nb_p= 0

	SR_Sort({2, 1, 3})
	SR_Sort({2, 7, 5, 3, 4, 6, 1})
	SR_Sort({7, 12, 17, 2, 14, 15, 33, 20, 37, 18, 9, 25, 41, 26, 39, 29, 16, 5, 23, 24, 35, 38, 32, 6, 11, 21, 27, 8, 40, 3, 10, 36, 13, 30, 31, 28, 1, 4, 19, 22, 34})
	/* removed other datasets */
	set printer on
	? 0, 0, tot_nb_s, tot_nb_p, tot_nb_s+ tot_nb_p
	set printer off
	set printer to
	return

procedure SR_Sort (lst)
	ltmp= aclone(lst)
	seq=""
	mx= SR_SortC1 (ltmp, 1)
	aadd(mx,seq)
	for fx=2 to len(lst)
		ltmp= aclone(lst)
		seq=""
		tmp= SR_SortC1 (ltmp, fx)
		if tmp[5]>0 .and. tmp[5] < mx[5]
			mx= tmp
			aadd(mx,seq)
		endif
	next

	set color to w/n
	set printer on
	? mx[1], mx[2], mx[3], mx[4], mx[5], mx[6]
	set console off
	?? "  ", RLE(mx[7])
	set console on
	set printer off
	tot_nb_s += mx[3]
	tot_nb_p += mx[4]
	return

function SR_SortC1 (lst, fx)
	t_db= seconds()
	*	Init
	size= len(lst)
	nb_s= 0
	nb_p= 0
	pntr= size

	*	calc final position
	dest= array(size)
	for scan= 1 to size
		dest[scan]= 1
		for scanp=1 to scan-1
			if lst[scan]<lst[scanp]
				dest[scanp]++
			else
				dest[scan]++
			endif
		next
	next
	
	fix_d= fx
	fix_f= fx
	fix_l= 1
	heat= size-1
	do while heat > 0 .and. dest[(fix_d+ size- 2)% size +1]%size+1 = dest[fix_d]
		fix_d = (fix_d+ size- 2)% size +1
		fix_l++
		heat--
	enddo
	do while heat > 0 .and. dest[fix_f]%size+1 = dest[fix_f%size+1]
		fix_f= fix_f% size+ 1
		fix_l++
		heat--
	enddo

	*	Sort Swap Rot
	if fx>1 .and. fix_d<>fx
		heat=-1
	else
		do while heat > 0
			nxt= pntr%size+1
			rst= (size-(fix_f- fix_d+size)%size)/2

			do case
			case (nxt-fix_d+size)%size < fix_l
				*	*	sorted pivot range
				do while pntr != fix_f
					rotat(lst)
				enddo
				nxt= pntr%size+1
			case (dest[pntr]-dest[fix_d]+size)%size < (dest[nxt]-dest[fix_d]+size)%size
				*	already ordered
			case (fix_d-nxt+size)%size < rst .and. (dest[nxt]-dest[fix_f]+size)%size < rst
				*	The quick for jump over the lazy dog.
				*	Moves intersting values over the pivot
				do while nxt != fix_f
					rotat(lst)
					swapC(lst)
					nxt= pntr%size+1
				enddo
				fix_d = (fix_d+ size- 2)% size +1
				fix_f = (fix_f+ size- 2)% size +1
			otherwise
				swapC(lst)
			endcase

			do while heat > 0 .and. dest[(fix_d+ size- 2)% size +1]%size+1 = dest[fix_d]
				fix_d = (fix_d+ size- 2)% size +1
				fix_l++
				heat--
			enddo
			do while heat > 0 .and. dest[fix_f]%size+1 = dest[fix_f%size+1]
				fix_f= fix_f% size+ 1
				fix_l++
				heat--
			enddo
			if heat > 0
				rotat(lst)
			endif
		enddo

		*	Rotation finale
		do while lst[pntr] < lst[pntr%size+1]
			rotat()
		enddo
		
		heat=1
		for scan= 1 to size-1
			if dest[scan]<dest[scan+1]
				heat ++
			endif
		next
		if dest[size]<dest[1]
			heat ++
		endif
	endif
	t_fn= seconds()
	return {size, heat, nb_s, nb_p, nb_s+ nb_p, t_fn-t_db}

procedure swapC(lst,pos)
	*	swap
	nxt= pntr% size+ 1

	tmp= lst[pntr]
	lst[pntr]= lst[nxt]
	lst[nxt]= tmp

	tmp= dest[pntr]
	dest[pntr]= dest[nxt]
	dest[nxt]= tmp

	nb_s++
	seq += "S"
	return

procedure rotat()
	pntr= pntr% size+ 1
	seq += "R"
	nb_p++
	return

function RLE(st)
	rep=""
	scan=1
	do while scan<= len(st)
		if st[scan]="S"
			rep+= "S"
			scan++
		else
			rpt= 1
			do while scan+rpt<= len(st) .and. st[scan+rpt]="R"
				rpt++
			enddo
			if rpt>2
				rep+= str(rpt,,,.T.)+"R"
				scan+= rpt
			else
				rep+= "R"
				scan++
			endif
		endif
	enddo
	return rep


- First version sorting code:
VB
do case
case (nxt-fix_d+size)%size < fix_l
    *   sorted pivot range
    do while pntr != fix_f
        rotat(lst)
    enddo
    nxt= pntr%size+1
case (dest[pntr]-dest[fix_d]+size)%size < (dest[nxt]-dest[fix_d]+size)%size
    *   already ordered
otherwise
    swapC(lst)
endcase

- First version result:
 Size      Swaps    Rotates      Total
    3          1          1          2
    7          4          7         11    RSRRSRS3RS
   41        339       1002       1341
   52        559       1683       2242
   65        840       2894       3734
   69        939       3086       4025
   75       1210       3607       4817
   80       1533       4297       5830
  103       2471       8013      10484
  108          0          0          0
  109       2870       8742      11612
  151       5200      17928      23128
  173       6534      24153      30687
  177       7529      25225      32754
  192       9128      28512      37640
  201       8894      30321      39215
  201       9188      30706      39894
  205       9906      33120      43026
  211      10146      33665      43811
  226      11707      40712      52419
  227      12796      40664      53460
  230      12178      42334      54512
  238      13056      46223      59279
  241      13947      47465      61412
  241      13614      46258      59872
  244      13968      49137      63105
  246      14339      47365      61704
  250      13941      51463      65404
  253      15587      51119      66706
  256      15631      52136      67767
Total      228055     771838     999893


- Second version sorting code:
VB
do case
case (nxt-fix_d+size)%size < fix_l
    *   sorted pivot range
    do while pntr != fix_f
        rotat(lst)
    enddo
    nxt= pntr%size+1
case (dest[pntr]-dest[fix_d]+size)%size < (dest[nxt]-dest[fix_d]+size)%size
    *   already ordered
case (fix_d-nxt+size)%size < rst .and. (dest[nxt]-dest[fix_f]+size)%size < rst
    *   The quick for jump over the lazy dog.
    *   Moves intersting values over the pivot
    do while nxt != fix_f
        rotat(lst)
        swapC(lst)
        nxt= pntr%size+1
    enddo
    fix_d = (fix_d+ size- 2)% size +1
    fix_f = (fix_f+ size- 2)% size +1
otherwise
    swapC(lst)
endcase

- Second version result:
 Size          S          P      Total
    3          1          2          3
    7          8         13         21
   41        327        801       1128
   52        576       1274       1850
   65        972       1983       2955
   69        929       2035       2964
   75       1222       2805       4027
   80       1274       2948       4222
  103       2245       5664       7909
  108          0          0          0
  109       2550       6153       8703
  151       5060      12861      17921
  173       6850      15963      22813
  177       6721      17632      24353
  192       8251      19719      27970
  201       8300      22685      30985
  201       8228      22504      30732
  205       8604      23742      32346
  211       9928      24425      34353
  226      10558      29269      39827
  227      10954      30734      41688
  230      12049      29365      41414
  238      11240      33305      44545
  241      12029      34980      47009
  241      12284      33438      45722
  244      13220      33725      46945
  246      13036      35086      48122
  250      12840      35810      48650
  253      13801      35492      49293
  256      13986      37625      51611
Total     208043     552038     760081

I knew there was a good shave to do on first version. There is still some fine tuning possible.
[Update 20140710]
- Third version sorting code: a simple tweak improved the solution of 25000 moves.
VB
do case
case (nxt-fix_d+size)%size < fix_l
    *   sorted pivot range
    do while pntr != fix_f
        rotat(lst)
    enddo
    nxt= pntr%size+1
case (dest[pntr]-dest[fix_d]+size)%size < (dest[nxt]-dest[fix_d]+size)%size
    *   already ordered
case (fix_d-nxt+size)%size + (dest[nxt]-dest[fix_f]+size)%size < rst
    *   The quick for jump over the lazy dog.
    *   Moves intersting values over the pivot
    do while nxt != fix_f
        rotat(lst)
        swapC(lst)
        nxt= pntr%size+1
    enddo
    fix_d = (fix_d+ size- 2)% size +1
    fix_f = (fix_f+ size- 2)% size +1
otherwise
    swapC(lst)
endcase

- Third version result:
 Size          S          P      Total
    3          1          1          2
    7          4          7         11
   41        249        808       1057
   52        501       1277       1778
   65        694       2132       2826
   69        891       2170       3061
   75       1138       2712       3850
   80       1223       3267       4490
  103       1913       5566       7479
  108          0          0          0
  109       2154       5935       8089
  151       4532      12721      17253
  173       5760      16136      21896
  177       6043      17811      23854
  192       6608      20708      27316
  201       8280      22200      30480
  201       7746      22276      30022
  205       8422      22664      31086
  211       8426      25033      33459
  226       9482      29323      38805
  227       9650      29888      39538
  230      10468      30360      40828
  238      10705      31880      42585
  241      10487      31610      42097
  241      11392      33375      44767
  244      11778      34161      45939
  246      11636      34200      45836
  250      11548      35876      47424
  253      12497      35736      48233
  256      13152      37089      50241
Total     187380     546922     734302

[Update 20170411]
- Fourth version sorting code: looks like the range defined by rst have big effect on efficiency.
VB
rst= (size-(fix_f- fix_d+size)%size)*2/3-1

- Fourth version result:
 Size          S          P      Total
    3          1          1          2
    7          4          7         11
   41        301        676        977
   52        482       1226       1708
   65        742       1994       2736
   69        901       1967       2868
   75       1020       2567       3587
   80       1169       2947       4116
  103       2009       5146       7155
  108          0          0          0
  109       2084       5610       7694
  151       4454      11592      16046
  173       5724      14568      20292
  177       5997      15871      21868
  192       7039      18195      25234
  201       8178      19600      27778
  201       7646      20060      27706
  205       7868      20866      28734
  211       8314      21875      30189
  226       9583      25736      35319
  227      10144      25966      36110
  230      10430      27498      37928
  238      10938      28561      39499
  241      11111      28697      39808
  241      11538      29703      41241
  244      11871      30516      42387
  246      11567      31199      42766
  250      12022      31536      43558
  253      12199      31434      43633
  256      12820      33499      46319
Total     188156     489113     677269
 
Share this answer
 
v9
Comments
Maciej Los 9-Apr-17 14:20pm    
I see the result of your job, but where is a code?
Patrice T 9-Apr-17 14:31pm    
Last sentence is "Still have a couple optimization to test before publishing my solution"
Code is coming after I tested the optimizations.
Maciej Los 9-Apr-17 15:31pm    
OK. We're waiting :)
Patrice T 14-Apr-17 22:17pm    
Completed my solution :)
Maciej Los 15-Apr-17 14:50pm    
Looks good to me ;)
C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SwapAndPop
{
    internal static class Program
    {
        private static void Main()
        {
            var lists = new List<int[]>
            {
                new int[] { 2, 1, 3 },
                new int[] { 2, 7, 5, 3, 4, 6, 1 },
                // trimmed
            };

            int tlMoves = 0, tlSwap = 0, tlPop = 0;

            Console.WriteLine("SIZE      SWAP       POP     TOTAL");

            for (int i = 0; i < lists.Count; i++)
            {
                var listCount = lists[i].Length;
                var moves = Solve(lists[i]);
                var movesCount = moves.Length;
                var types = moves.GroupBy((x) => x).ToDictionary(x => x.Key, x => x);
                var countSwap = types.Keys.Contains('S') ? types['S'].Count() : 0;
                var countPop = types.Keys.Contains('P') ? types['P'].Count() : 0;

                tlMoves += movesCount;
                tlSwap += countSwap;
                tlPop += countPop;

                Console.WriteLine($"{listCount,4:N0}{countSwap,10:N0}{countPop,10:N0}{movesCount,10:N0}");
            }

            Console.WriteLine($"Total: {tlSwap,7:N0}{tlPop,10:N0}{tlMoves,10:N0}");
            Console.WriteLine("\n  --Press any key to exit --");
            Console.ReadKey();
        }

        private static string Solve(int[] list)
        {
            var count = list.Length;
            var optimalMoves = Solve(list, 0);
            var optimalCount = optimalMoves.Length;

            for (int i = 1; i < count; i++)
            {
                var moves = Solve(list, i - 1);
                var moveCount = moves.Length;
                if (moveCount < optimalCount)
                {
                    optimalCount = moveCount;
                    optimalMoves = moves;
                }
            }
            return optimalMoves;
        }

        private static string Solve(int[] list, int PivotIdx)
        {
            var count = list.Length;
            var work = new int[count];
            Array.Copy(list, work, count);

            var moves = new StringBuilder();

            void swap()
            {
                int tmp = work[0];
                work[0] = work[count - 1];
                work[count - 1] = tmp;
                moves.Append("S");
            }

            void pop()
            {
                int temp = work[0];
                Array.Copy(work, 1, work, 0, count - 1);
                work[count - 1] = temp;
                if (--PivotIdx < 0) PivotIdx += count;
                moves.Append("P");
            }

            float dist2Home(int ndx, int i)
            {
                var home = (PivotIdx + i) % count;
                var dist1 = ndx - home;
                var dist2 = home - ndx;
                if (dist1 < 0) dist1 += count;
                if (dist2 < 0) dist2 += count;
                return Math.Min(dist1, dist2 * Math.Max(1F, count / 50F));
            }

            while (!work.IsSolved())
            {
                var distP = Math.Max(dist2Home(0, work[0]), dist2Home(count - 1, work[count - 1]));
                var distS = Math.Max(dist2Home(count - 1, work[0]), dist2Home(0, work[count - 1]));

                if (distS < distP)
                    swap();
                else
                    pop();

            }
            return moves.ToString();
        }

        private static bool IsSolved(this int[] list)
        {
            int count = list.Length - 1;
            if (count < 1) return true;
            int item = list[0], i = 1;
            while (i <= count && item <= (item = list[i])) i++;
            return i > count;
        }
    }
}

Output:
SIZE      SWAP       POP     TOTAL
   3         1         1         2
   7         4         7        11
  41       257       636       893
  52       433     1,113     1,546
  65       686     1,857     2,543
  69       719     1,967     2,686
  75       886     2,505     3,391
  80     1,017     2,711     3,728
 103     1,631     4,852     6,483
 108         0         0         0
 109     1,816     5,287     7,103
 151     3,758    10,613    14,371
 173     4,936    13,727    18,663
 177     5,085    14,643    19,728
 192     6,200    16,624    22,824
 201     6,628    18,200    24,828
 201     6,492    18,260    24,752
 205     6,750    18,823    25,573
 211     7,096    20,413    27,509
 226     8,609    23,612    32,221
 227     8,448    23,480    31,928
 230     8,631    24,999    33,630
 238     9,426    25,177    34,603
 241     9,683    26,993    36,676
 241     9,682    26,823    36,505
 244     9,671    28,088    37,759
 246     9,786    28,320    38,106
 250    10,228    28,036    38,264
 253    10,341    29,699    40,040
 256    10,715    30,690    41,405
Total: 159,615   448,156   607,771

  --Press any key to exit --
 
Share this answer
 
Comments
Patrice T 27-Jul-17 15:08pm    
From the output, it is damn efficient.
Graeme_Grant 27-Jul-17 20:56pm    
;)

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900