Sort a List With Swaps and Pops

Question

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

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

This is always possible because any list can be sorted with enough swaps of adjacent elements. 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).

Yet, in terms of the number of S and P operations, this method is unlikely to be optimal for most lists.

Challenge

Write a program or function 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 (see Scoring).

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.

Verifier

This stack snippet can be used to verify that a sequence really sorts the list. The list should have square brackets and be comma separated. The SP sequence is just a string of S's and P's.

<style>*{font-family:monospace}</style><script>function swap(list) {var tmp = list[0];list[0] = list[list.length - 1];list[list.length - 1] = tmp;}function pop(list) {list.push(list.shift())}function check() {var result = 'Sorted sucessfully.';var details = '';try {var list = eval(document.getElementById('list').value);var seq = document.getElementById('seq').value;details += 'Sequence: ' + seq + '<br>Steps:<br>' + list + ' <-- original';for(var i = 0; i < seq.length; i++) {if (seq.charAt(i) == 'S')swap(list);else if (seq.charAt(i) == 'P')pop(list);details += ' (' + i + ')<br>' + list;}details += ' <-- final (' + i + ')';for(var i = 1; i < list.length; i++) {if (list[i-1] > list[i]) {result = 'Sorting failed!';break;}}} catch(e) {result = 'Error: ' + e;}document.getElementById('result').innerHTML = result;document.getElementById('details').innerHTML = details;}</script><p>List<br><input id='list'type='text'size='60'value='[2, 1, 3]'></p><p>SP Sequence<br><textarea id='seq'rows='1'cols='60'>SP</textarea><br></p><button type='button'onclick='check()'>Check</button><p id='result'></p><p id='details'></p>

Scoring

Your algorithm must produce correct, but possibly sub-optimal, SP sequences for N = 2 to 256. For any permutation in this range it must run in less than 5 minutes on a decent modern computer.

Your score is the total number of S and P operations your algorithm needs to sort all 30 of the lists provided below. The lowest score wins.

You may not hardcode your program to suit this data. If it seems necessary I may add more test data to determine the winner.

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]

Answer 1

Python 3 (with PyPy) - score: 607771

Edit: I think the bug is fixed, but I'm still not convinced this works until I prove it does

def d(a, b, N):
    a, b = a%N, b%N

    if a >= b:
        return a-b
    else:
        return a+(N-b)

def gt(a, b, N):
    if a == N and b == 1:
        return False
    if a == 1 and b == N:
        return True
    return a > b

def solve(numbers):
    N = len(numbers)
    best_move = None
    target = sorted(numbers)

    if N == 2:
      return "" if numbers == [1,2] else "P"

    for b in range(N):
        nums = numbers[:]
        moves = []
        head_ptr = 0 # Which element should be at the start of the list if we actually moved stuff
        reference = target[b:]+target[:b]
        ref_d = {t:i for i,t in enumerate(reference)}

        while True:
            for pops in range(N):
                ptr = (head_ptr + pops) % N

                # Magic
                d1 = d(ref_d[nums[ptr-1]],ptr-1,N)+d(ptr,ref_d[nums[ptr]],N)
                d2 = d(ref_d[nums[ptr]],ptr,N)+d(ptr-1,ref_d[nums[ptr-1]],N)

                if d1 > d2 or (d1 == d2 and gt(nums[ptr-1], nums[ptr], N)):
                    moves.append("P"*pops + "S")
                    head_ptr = (head_ptr + pops) % N
                    nums[ptr-1],nums[ptr] = nums[ptr],nums[ptr-1]
                    break

            else:
                if nums[nums.index(1):]+nums[:nums.index(1)] != target:
                    print("This algorithm is seriously broken.\n")
                moves.append("P"*((N+nums.index(1)-head_ptr)%N))
                break

        moves = "".join(moves)

        if not best_move or len(moves) < len(best_move):
            best_move = moves

    return best_move

Usage

solve([3, 4, 2, 1, 5])

Explanation

The program just performs bubble sort swaps, using the observation that:
S: n 1 2 3 ... n-1 0 PS: 0 2 3 ... n-1 n 1 PPS: 1 3 ... n-1 n 0 2 PPPS: 2 ... n-1 n 0 1 3 ...

In other words, i pushes followed by a swap means that element i gets swapped with element i-1, indices wrapping. However, we need to keep track of the fact that the list gets shifted in doing so.

To do better than just the usual bubble sort, we try to apply a heuristic in order to make sure we don't do too many useless swaps, enforcing that any swap moves both elements closer to their respective goals (I haven't formally proved it's correct, but it seems to work so far). We then take the best solution out of many configurations (CPython takes a while, but PyPy gets this job done relatively quickly).

Scoring

Output on Pastebin.

---

Previous naive bubble sort ver. (score: 1126232)

This one definitely works.

def cyclic_sorted(nums):
    for i in range(len(nums)):
        if nums[i:] + nums[:i] == sorted(nums):
            return i
    return False

def solve(nums):
    N = len(nums)

    def gt(a, b):
        if a == 1 and b == N:
            return True
        if a == N and b == 1:
            return False
        return a > b

    moves = []
    head_ptr = 0 # Which element should be at the start of the list if we actually moved stuff

    while nums != sorted(nums):
        pops = 0
        ptr_offset = 0

        while pops < N:
            ptr = (head_ptr + pops) % N

            if (not moves or pops > 0) and gt(nums[ptr-1], nums[ptr]):
                moves.append("P"*pops + "S")
                head_ptr = (head_ptr + pops) % N

                nums[ptr-1],nums[ptr] = nums[ptr],nums[ptr-1]
                break

            pops += 1

        else:
            moves.append("P"*cyclic_sorted(nums[head_ptr:]+nums[:head_ptr]))
            break

    return "".join(moves)

Answer 2

Javascript ES6 - 607,771

function popsort( iData ) {
    var sSP, iLen,
        sSP_Opt = popsortimpl( iData.slice( 0 ), 0 ),
        iOptLen = sSP_Opt.length;

    for( var n = iData.length, i = 2; i <= n; i++ )
        if( (iLen = (sSP = popsortimpl( iData.slice( 0 ), i - 1 )).length) < iOptLen ) {
            iOptLen = iLen;
            sSP_Opt = sSP;
        }

    return sSP_Opt;
}

function popsortimpl( iData, iPivIdx ) {
    function issorted()
        { return iData.every( (_,i_) => _ == i_+1 ); }

    function swap() {
        var i_ = iData[0];

        iData[0] = iData[n-1];
        iData[n-1] = i_;

        sSP.push( 'S' );
    }

    function pop() {
        iData.push( iData.shift() );
        if( --iPivIdx < 0 )
            iPivIdx += n;

        sSP.push( 'P' );
    }

    function dist2home( iIdx_, i_ ) {
        var iHome_ = (iPivIdx + i_) %n,
            iDist1_ = iIdx_ - iHome_,
            iDist2_ = iHome_ - iIdx_;

        if( iDist1_ < 0 )
            iDist1_ += n;
        if( iDist2_ < 0 )
            iDist2_ += n;

        return Math.min( iDist1_, iDist2_*Math.max( 1, n/50 ) );
    }

    var n = iData.length,
        sSP = [];

    while( !issorted() ) {
        var iDistP = Math.max( dist2home( 0, iData[0] ), dist2home( n - 1, iData[n - 1] ) ),
            iDistS = Math.max( dist2home( n - 1, iData[0] ), dist2home( 0, iData[n - 1] ) );

        if( iDistS < iDistP )
            swap();
        else pop();
    }
    return sSP.join('');
}

Implements a "closest-end" bubble sort that bubbles elements up or down depending on the shortest route (bubble up or bubble down) to a reference position.

I don't believe the routine is optimal, but it should be reasonably close to it. As a bonus, it runs the full set of test vectors in milliseconds.

Updated to iterate over the pivot point to improve competitiveness. I also introduced heuristics to compensate for the fact that elements have a lower mobility moving "up" the list than moving "down" (a phenomenon analogous to the difference in electron and hole mobility in a semiconductor). There are major differences between this implementation and Sp3000's, hence the fact that both score exactly 607,771 is spooky. Halloween spooky.

The routine now takes about 20 seconds to run.

Sample Output

popsort( [2, 7, 5, 3, 4, 6, 1] )

yields

PSPPSPSPPPS

Answer 3

OCaml, score: 1136707 1136599

Edit: I messed up! I had read S would swap adjacent elements and missed that the first and last elements get swapped. This implementation builds on this as is obvious from the eval implementation. Edit²: I fixed it up by using the observation that you can write what I thought was S P as P S. I also switched to the better-scoring version with some optimizations to make it less slow.

Runtime is 1.33 18 1.01 seconds on my system using the interpreter compiled binary.

type sp = S | P

let string_of_sp = function
  | S -> "S"
  | P -> "P"

let rec eval (e : sp list) (xs : int list) : int list =
  match e, xs with
  | [], xs -> xs
  | P :: S :: e, x1 :: x2 :: xs -> eval e (x1 :: xs @ [x2])
  | P :: e, x :: xs -> eval e (xs @ [x])
  | _ -> assert false

let generate_sp_sequence xs : sp list =
  let sorted = List.sort compare xs in
  let rec generate_sp_sequence ((xs, ys) : int list * int list) acc : sp list =
    if sorted = ys @ List.rev xs
    then acc
    else 
      match ys with
      | v1 :: v2 :: ys' ->
         if v1 > v2
         then generate_sp_sequence (v2 :: xs, v1 :: ys') (S :: P :: acc)
         else generate_sp_sequence (v1 :: xs, v2 :: ys') (P :: acc)
      | [x] ->
         let ys = List.rev (x :: xs) in
         generate_sp_sequence ([], ys) (P :: acc)
      | [] ->
         assert false
  in List.rev @@ generate_sp_sequence ([], xs) []


(** Uncomment to run tests **)
(*
let test =
  QCheck.(mk_test
            ~n:1000
            ~name:"generate_sp_sequence sorting test"
            ~pp:PP.(list int)
            Arbitrary.(list ~start:2 ~stop:256 small_int)
            (fun xs ->
             Prop.assume (List.length xs >= 2);
             eval (generate_sp_sequence ([], xs))
                  xs
             = List.sort compare xs))

let _ = QCheck.run test
 *)

let score_test = ... (* not included for brevity *)

let score =
  List.map (fun xs -> generate_sp_sequence ([], xs)) score_test
  |> List.map List.length
  |> List.fold_left (+) 0

let _ =
  print_string "The score is: ";
  print_int score;
  print_newline ()

generate_sp_sequence simply runs bubblesort and outputs the steps in terms of S and P. It may generate unnecessary steps.

Answer 4

C, score: 607771

It turns out my solution is very similar to Sp3000's Python solution (which explains the identical score). I've never used Python so I can't say for sure, but I think the concept is exactly the same:

For each number r in 0..n-1, set a goal of a sorted array rotated r times from the initial position (i.e. containing P pops with r = P mod n), and find a series of moves resulting in this configuration. Record the shortest sequence of moves for any r.
Perform swaps only when the swap brings closer whichever element is further from its goal position (looking in either direction), or when the swap moves both elements closer if both are equally far away.

Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Returns true if the array is sorted starting at position 'offset' */
int is_sorted(int *array, int n, int offset)
{
    int i;
    for (i = 0; i < n && array[(offset+i)%n] == i+1; i++);
    return i == n;
}

/* Find moves that would sort the array, assuming the first element will
   be at position (offset + n/2) % n */
int get_moves(int *array, int n, int offset, int stop_after, char *moves)
{
    int tmp, posA = n-1, posB = 0, counter = 0;
    /* Repeat until sorted or reaching the maximum number of moves (previous
       best, or the worst case upper bound if no previous solution) */
    for (; counter < stop_after && !is_sorted(array, n, posB); posA = (posA+1)%n, posB = (posB+1)%n, moves[counter++] = 'P')
    {
        /* Perform a swap if it would move whichever element is further away
           closer to its target */
        if ((array[posA] - posA + offset + n) % n >
            (array[posB] - posB + offset + n) % n)
        {
            tmp = array[posA];
            array[posA] = array[posB];
            array[posB] = tmp;
            moves[counter++] = 'S';
            if (is_sorted(array, n, posB))
            {
                break;
            }
        }
    }
    return counter;
}

int *parse_input(int _argc, char **_argv)
{
    int i;
    int *array = NULL;
    if (_argc > 1)
    {
        array = malloc((_argc-1) * sizeof(int));
        _argv[1]++; /* remove initial square bracket */
        for (i = 1; i < _argc; i++)
        {
            array[i-1] = atoi(_argv[i]);
        }
    }
    return array;
}

int main(int _argc, char **_argv)
{
    int *orig_array = parse_input(_argc, _argv);
    if (orig_array != NULL)
    {
        int n = _argc - 1;
        /* Safe worst case upper bound representing n^2 "SP" moves */
        int worst_move_count = 2*n*n;

        int i, move_count, offset;
        int best_offset, best_move_count = worst_move_count;

        char *best_moves = malloc(worst_move_count + 1);
        char *moves = malloc(worst_move_count + 1);
        int *array = malloc(n * sizeof(int));

        memset(best_moves, 0, worst_move_count + 1);
        /* Try all offsets from 0 to n-1; i.e. find solutions for:
           1, 2, 3, ..., n-2, n-1, n
           2, 3, 4, ..., n-1, n,   1
           3, 4, 5, ..., n,   1,   2
           ...
           n, 1, 2, ..., n-3, n-2, n-1
        */
        for (offset = 0; offset < n; offset++)
        {
            memset(moves, 0, worst_move_count + 1);
            memcpy(array, orig_array, n*sizeof(int));
            move_count = get_moves(array, n, offset, best_move_count, moves);
            if (move_count < best_move_count)
            {
                strcpy(best_moves, moves);
                best_move_count = move_count;
                best_offset = offset;
            }
        }
        printf("%s\n", best_moves);

        free(best_moves);
        free(moves);
        free(array);
        free(orig_array);
    }
    return 0;
}

Usage

$ gcc -Ofast -o popswap popswap.c
$ ./popswap [2, 7, 5, 3, 4, 6, 1]
PSPPSPSPPPS
$ ./popswap [2, 7, 5, 3, 4, 6, 1]|tr -d '\n'|wc -c
11

Scoring

Script:

#!/bin/sh
grep ^\\[ input.txt|while read line; do
    len=`echo $line|wc -w`;
    score=`./popswap $line|tr -d '\n'|wc -c`;
    echo "    $len $score";
done

Results:

$ ./scoring.sh |cut -d' ' -f 6|paste -sd+|bc
607771
$ time ./scoring.sh > /dev/null

real    0m1.926s
user    0m1.879s
sys     0m0.122s
$ ./scoring.sh
3 2
7 11
41 893
52 1546
65 2543
69 2686
75 3391
80 3728
103 6483
108 0
109 7103
151 14371
173 18663
177 19728
192 22824
201 24828
201 24752
205 25573
211 27509
226 32221
227 31928
230 33630
238 34603
241 36676
241 36505
244 37759
246 38106
250 38264
253 40040
256 41405

Answer 5

C++11, score: 1122052

Very naive implementation that doesn't take in account holes in the input sequence but takes in account the minimal value in the sequence.

Argument list is just the sequence of numbers, without commas and brackets (eg: "./a.out 2 7 5")

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

int* input  = 0;
int s_count = 0;
int p_count = 0;
int len;
int last;

void do_swap()
{
  int a = input[0];
  input[0] = input[last];
  input[last] = a;
  s_count++;
  cerr << "S";
}

void do_pop()
{
  int a = input[0];
  memmove(&input[0], &input[1], sizeof(int) * last);
  input[last] = a;
  p_count++;
  cerr << "P";
}

bool is_sorted()
{
  int i = 0;
  while (input[i] < input[i+1]) { if (++i == last) return true; }
  return false;
}

int main(int argc, char** args)
{
  int min_val = 256;

  len = argc - 1;
  last = len - 1;
  if (len <= 1)
    return 1;

  input = new int[len];
  for (int i = 2; i <= argc; i++)
  {
    int j = stoi(args[i-1]);
    input[i-2] = j;
    min_val = min(min_val, j);
  }

  while (!is_sorted())
  {
    if ((input[0]) == min_val)
      do_pop();
    else if (input[0] < input[last])
      do_swap();
    else if (input[0] > input[last])
      do_pop();
  }

  cerr << endl;
  cout << len << " " << (s_count + p_count) << endl;
  delete [] input;
  return 0;
}

Scoring

3 2
7 19
41 1642
52 3236
65 4787
69 4966
75 6644
80 6090
103 12142
108 0
109 13774
151 24976
173 34061
177 37835
192 41994
201 48316
201 47276
205 49439
211 51551
226 58859
227 56824
230 58994
238 64227
241 65774
241 66287
244 71345
246 73426
250 71766
253 68629
256 77171