23
7
This is a fewest-operations challenge where the objective is to sort a vector into ascending order using the fewest reversals. Your algorithm can only sort the vector using "sub-vector reversals"1, but it can use other operations for arithmetic operations, loops, checking if it's sorted etc. The number of sub-vector reversals your algorithm performs is its score.
1A "sub-vector reversal":
- Select a range of numbers in the vector, and reverse the elements in that range.
To give a simple example, if you start with the vector {4,3,2,1}
, then you can sort it in a lot of different ways:
- Reverse the entire vector. This is obviously the shortest approach as it only requires one reversal:
{4,3,2,1} -> {1,2,3,4}
- You can do a version of the bubble sort, which requires 6 reversals:
{4,3,2,1} -> {3,4,2,1} -> {3,2,4,1} -> {2,3,4,1} -> {2,3,1,4} -> {2,1,3,4} -> {1,2,3,4}
- You can start with the first 3 elements, then the three last, and finally the two first and the two last, which requires 4 swaps:
{4,3,2,1} -> {2,3,4,1} -> {2,1,4,3} -> {1,2,4,3} -> {1,2,3,4}
- ... and so on. There are an infinite amount of options available (you may repeat any operation if you like).
Rules and requirements:
Your code must finish in less than one minute for a list with 100 numbers. You may time this yourself, but please play fair2.
You must store the start and end indices of all swaps you perform, so that the solution might be verified. (I'll explain what this means below).
The code must be deterministic.
You can take the input on any format you want: Numeric vector, linked-list, array with length ... whatever you like.
You can do whatever you like on a copy of the vector. That includes attempting different reversals and check which is most efficient. Brute-forcing is perfectly fine, but stick to the time limit.
The score is the total number of flips for the 5 test vectors. Tie-breaker will the date stamp.
Example:
4 1 23 21 49 2 7 9 2 | Initial vector / list 4 1 2 9 7 2 49 21 23 | (2, 8) (flipped the elements between indices 2 and 8) 4 1 2 2 7 9 49 21 23 | (3, 5) 4 1 2 2 7 9 23 21 49 | (6, 8) 4 1 2 2 7 9 21 23 49 | (6, 7) 2 2 1 4 7 9 21 23 49 | (0, 3) 1 2 2 4 7 9 21 23 49 | (0, 2)
The score would be 6, since you performed 6 reversals. You must store (not print) the indices listed on the right side on a suitable format that can easily be printed/outputted for verification purposes.
Test vectors:
133, 319, 80, 70, 194, 333, 65, 21, 345, 142, 82, 491, 92, 167, 281, 386, 48, 101, 394, 130, 111, 139, 214, 337, 180, 24, 443, 35, 376, 13, 166, 59, 452, 429, 406, 256, 133, 435, 446, 304, 350, 364, 447, 471, 236, 177, 317, 342, 294, 146, 280, 32, 135, 399, 78, 251, 467, 305, 366, 309, 162, 473, 27, 67, 305, 497, 112, 399, 103, 178, 386, 343, 33, 134, 480, 147, 466, 244, 370, 140, 227, 292, 28, 357, 156, 367, 157, 60, 214, 280, 153, 445, 301, 108, 77, 404, 496, 3, 226, 37
468, 494, 294, 42, 19, 23, 201, 47, 165, 118, 414, 371, 163, 430, 295, 333, 147, 336, 403, 490, 370, 128, 261, 91, 173, 339, 40, 54, 331, 236, 255, 33, 237, 272, 193, 91, 232, 452, 79, 435, 160, 328, 47, 179, 162, 239, 315, 73, 160, 266, 83, 451, 317, 255, 491, 70, 18, 275, 339, 298, 117, 145, 17, 178, 232, 59, 109, 271, 301, 437, 63, 103, 130, 15, 265, 281, 365, 444, 180, 257, 99, 248, 378, 158, 210, 466, 404, 263, 29, 117, 417, 357, 44, 495, 303, 428, 146, 215, 164, 99
132, 167, 361, 145, 36, 56, 343, 330, 14, 412, 345, 263, 306, 462, 101, 453, 364, 389, 432, 32, 200, 76, 268, 291, 35, 13, 448, 188, 11, 235, 184, 439, 175, 159, 360, 46, 193, 440, 334, 128, 346, 192, 263, 466, 175, 407, 340, 393, 231, 472, 122, 254, 451, 485, 257, 67, 200, 135, 132, 421, 205, 398, 251, 286, 292, 488, 480, 56, 284, 484, 157, 264, 459, 6, 289, 311, 116, 138, 92, 21, 307, 172, 352, 199, 55, 38, 427, 214, 233, 404, 330, 105, 223, 495, 334, 169, 168, 444, 268, 248
367, 334, 296, 59, 18, 193, 118, 10, 276, 180, 242, 115, 233, 40, 225, 244, 147, 439, 297, 115, 354, 248, 89, 423, 47, 458, 64, 33, 463, 142, 5, 13, 89, 282, 186, 12, 70, 289, 385, 289, 274, 136, 39, 424, 174, 186, 489, 73, 296, 39, 445, 308, 451, 384, 451, 446, 282, 419, 479, 220, 35, 419, 161, 14, 42, 321, 202, 30, 32, 162, 444, 215, 218, 102, 140, 473, 500, 480, 402, 1, 1, 79, 50, 54, 111, 189, 147, 352, 61, 460, 196, 77, 315, 304, 385, 275, 65, 145, 434, 39
311, 202, 126, 494, 321, 330, 290, 28, 400, 84, 6, 160, 432, 308, 469, 459, 80, 48, 292, 229, 191, 240, 491, 231, 286, 413, 170, 486, 59, 54, 36, 334, 135, 39, 393, 201, 127, 95, 456, 497, 429, 139, 81, 293, 359, 477, 404, 129, 129, 297, 298, 495, 424, 446, 57, 296, 10, 269, 350, 337, 39, 386, 142, 327, 22, 352, 421, 32, 171, 452, 2, 484, 337, 359, 444, 246, 174, 23, 115, 102, 427, 439, 71, 478, 89, 225, 7, 118, 453, 350, 109, 277, 338, 474, 405, 380, 256, 228, 277, 3
I'm fairly certain that finding an optimal solution is NP-hard (since regular pancake sorting is).
2Yes, people with very fast computers might have a benefit, due to the time limit of one minute. After much discussion I've figured it's best if everyone does their own benchmarking, it's not a fastest code challenge.
1Somewhat related. – Stewie Griffin – 2017-04-14T20:35:34.170
1The optimal solution should at most be equivalent to insertion sort in the number of reversals, each reversal can place a single number. – fəˈnɛtɪk – 2017-04-14T22:54:32.317
3This is not pancake flipping (which can only flip from one location until the end). Selection sort is O(n) and uses n-1 swaps. There are worst cases in which n-1 swaps are necessary. Selection sort is asymptotically optimal. – orlp – 2017-04-15T19:08:51.087
>
Can I specialize the program to work with 100 numbers only? – user202729 – 2017-10-22T13:25:13.593
Sure. It should be simple to adapt it to work for 80 numbers too, and since it's not code golf you could make the list length dynamic, by expanding the code. You don't need to make it harder than it is. But you may not optimize it to perform better on the test cases than other lists with 100 numbers. – Stewie Griffin – 2017-10-22T14:53:11.547
1@orlp Can you prove that there are worst cases with
n-1
flips? I can only prove a lower bound of about 50. – user202729 – 2017-10-24T01:25:49.090@user202729 Not sure, such a long time ago :D – orlp – 2017-10-24T15:30:28.140