Optimize sorting, using "Sub-vector reversals"
Java, genetic-ish algorithm, 80+81+79+78+80=398 (previously 418)
After trying a bunch of different ideas and mostly failing, I settled on this algorithm: start with the input array, try all possible reversals and keep a certain number of results with the smallest number of runs, then do the same for those results, until we get a sorted array.
By "runs" I mean maximal subarrays that appear exactly or reversed in the sorted array. Basically they are maximal sorted subarrays, but in case of repeated elements, the number of elements in the middle should match. E.g. if the sorted array is 2, 2, 3, 3, 4, 4 then 4, 3, 3, 2 is a run but 2, 2, 3, 4 is not (and neither is 2, 3, 2).
In this version I optimized the algorithm to reverse only at run boundaries and only if a reversed run can be joined with a newly-adjacent run. Also, the runs are adjusted and joined at each step, to avoid recalculating them from the modified array. This allowed me to increase the "population size" from 30 to about 3000, and to run multiple simulations at various sizes.
import java.io.*;
import java.util.*;
public class SubReversal {
static int n;
static int[] a;
static int[] srt;
static List<int[]> rev;
static Map<Integer, Integer> idx;
static Map<Integer, Integer> count;
static final int NB = 2000;
static State[] best = new State[NB + 1];
static int ns;
static class Run {
int start;
int end;
int dir;
int nstart = 1;
int nend = 1;
Run(final int start) {
this.start = start;
}
Run(final Run r) {
start = r.start;
end = r.end;
dir = r.dir;
nstart = r.nstart;
nend = r.nend;
}
Run copy() {
return new Run(this);
}
Run reverse() {
int t = start;
start = end;
end = t;
t = nstart;
nstart = nend;
nend = t;
dir = -dir;
return this;
}
boolean canJoin(final Run r) {
if (dir * r.dir == -1) {
return false;
}
final int t = idx.get(a[r.start]) - idx.get(a[end]);
if (Math.abs(t) > 1) {
return false;
}
if (t != 0 && dir + r.dir != 0 && t != dir && t != r.dir) {
return false;
}
if (t == 0) {
if (dir * r.dir == 0) {
return true;
}
return nend + r.nstart == count.get(a[end]);
}
return (dir == 0 || nend == count.get(a[end])) && (r.dir == 0 || r.nstart == count.get(a[r.start]));
}
Run join(final Run r) {
if (a[start] == a[r.start]) {
nstart += r.nstart;
}
if (a[end] == a[r.end]) {
nend += r.nend;
}
else {
nend = r.nend;
}
end = r.end;
if (dir == 0) {
dir = r.dir;
}
if (dir == 0 && a[start] != a[end]) {
dir = idx.get(a[end]) - idx.get(a[start]);
}
return this;
}
@Override
public String toString() {
return start + "(" + nstart + ") - " + end + '(' + nend + "): " + dir;
}
}
static class State implements Comparable<State> {
int[] b;
int[] rv;
State p;
List<Run> runs;
public State(final int[] b, final int[] rv, final State p, final List<Run> runs) {
this.b = Arrays.copyOf(b, b.length);
this.rv = rv;
this.p = p;
this.runs = runs;
}
@Override
public int compareTo(final State o) {
return runs.size() - o.runs.size();
}
@Override
public String toString() {
return Arrays.toString(b) + " - " + Arrays.toString(rv) + " - " + runs.size();
}
int getCount() {
return p == null ? 0 : p.getCount() + 1;
}
}
static void reverse(int x, int y) {
while (x < y) {
int t = a[x];
a[x] = a[y];
a[y] = t;
x++;
y--;
}
}
static List<Run> runs() {
final List<Run> l = new ArrayList<>();
Run run = new Run(0);
for (int i = 1; i < n; ++i) {
final int t = idx.get(a[i]) - idx.get(a[i - 1]);
if (Math.abs(t) > 1) {
run.end = i - 1;
l.add(run);
run = new Run(i);
}
else if (t == 0) {
run.nend++;
if (run.dir == 0) {
run.nstart++;
}
}
else {
if (run.dir == 0) {
run.dir = t;
}
else if (run.dir != t || run.nend != count.get(a[i - 1])) {
run.end = i - 1;
l.add(run);
run = new Run(i);
}
run.nend = 1;
}
}
run.end = n - 1;
l.add(run);
return l;
}
static void show() {
if (!Arrays.equals(a, srt)) {
System.out.println("bug!");
System.out.println(Arrays.toString(a));
throw new RuntimeException();
}
System.out.println("Sorted: " + Arrays.toString(a));
System.out.println(rev.size() + " reversal(s):");
for (int[] x : rev) {
System.out.println(Arrays.toString(x));
}
}
static void sort() {
State bestest = null;
final int[] a1 = Arrays.copyOf(a, n);
final int[] sizes = {10, 20, 30, 50, 100, 200, 300, 500, 1000, 2000};
for (int nb : sizes) {
System.arraycopy(a1, 0, a, 0, n);
ns = 1;
best[0] = new State(a, null, null, runs());
while (best[0].runs.size() > 1) {
final State[] s = Arrays.copyOf(best, ns);
ns = 0;
for (State x : s) {
System.arraycopy(x.b, 0, a, 0, n);
final int m = x.runs.size();
for (int i = 0; i < m; ++i) {
for (int j = i; j < m; ++j) {
boolean b = false;
if (i > 0) {
final Run r = x.runs.get(j);
r.reverse();
b = x.runs.get(i - 1).canJoin(r);
r.reverse();
}
if (!b && j < m - 1) {
final Run r = x.runs.get(i);
r.reverse();
b = r.canJoin(x.runs.get(j + 1));
r.reverse();
}
if (!b) {
continue;
}
final List<Run> l = new ArrayList<>(x.runs);
final int rstart = l.get(i).start;
final int rend = l.get(j).end;
final int t = rstart + rend;
reverse(rstart, rend);
for (int k = i; k <= j; ++k) {
final Run r = x.runs.get(i + j - k).copy().reverse();
r.start = t - r.start;
r.end = t - r.end;
l.set(k, r);
}
if (j < m - 1 && l.get(j).canJoin(l.get(j + 1))) {
l.get(j).join(l.get(j + 1));
l.remove(j + 1);
}
if (i > 0 && l.get(i - 1).canJoin(l.get(i))) {
l.set(i - 1, l.get(i - 1).copy().join(l.get(i)));
l.remove(i);
}
if (ns < nb || l.size() < best[ns - 1].runs.size()) {
best[ns++] = new State(a, new int[]{rstart, rend}, x, l);
Arrays.sort(best, 0, ns);
if (ns > nb) {
ns = nb;
}
}
reverse(rstart, rend);
}
}
}
if (ns == 0) {
for (State x : s) {
System.arraycopy(x.b, 0, a, 0, n);
final List<Run> l = new ArrayList<>(x.runs);
final int rstart = l.get(0).start;
final int rend = l.get(0).end;
final int t = rstart + rend;
reverse(rstart, rend);
final Run r = x.runs.get(0).copy().reverse();
r.start = t - r.start;
r.end = t - r.end;
l.set(0, r);
best[ns++] = new State(a, new int[]{rstart, rend}, x, l);
reverse(rstart, rend);
}
Arrays.sort(best, 0, ns);
}
}
State r = null;
for (int i = 0; i < ns; ++i) {
if (Arrays.equals(best[i].b, srt)) {
r = best[i];
break;
}
}
if (r == null) {
final State x = best[0];
System.arraycopy(x.b, 0, a, 0, n);
reverse(0, n - 1);
r = new State(a, new int[]{0, n - 1}, x, runs());
}
if (!Arrays.equals(r.b, srt)) {
throw new RuntimeException("bug");
}
if (bestest == null || r.getCount() < bestest.getCount()) {
bestest = r;
}
}
while (bestest.p != null) {
rev.add(bestest.rv);
bestest = bestest.p;
}
Collections.reverse(rev);
a = a1;
for (int[] x : rev) {
reverse(x[0], x[1]);
}
if (!Arrays.equals(a, srt)) {
throw new RuntimeException("bug");
}
}
static void init(final String s) {
final String[] b = s.split(s.contains(",") ? "," : " ");
n = b.length;
a = new int[n];
count = new HashMap<>();
for (int i = 0; i < n; ++i) {
a[i] = Integer.parseInt(b[i].trim());
final Integer x = count.get(a[i]);
count.put(a[i], x == null ? 1 : x + 1);
}
srt = Arrays.copyOf(a, n);
Arrays.sort(srt);
idx = new HashMap<>();
int j = 0;
for (int i = 0; i < n; ++i) {
if (i == 0 || srt[i] != srt[i - 1]) {
idx.put(srt[i], j++);
}
}
rev = new ArrayList<>();
}
static void test5() {
final String[] t = {"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"};
int r = 0;
for (String s : t) {
init(s);
sort();
System.out.println(rev.size());
r += rev.size();
}
System.out.println("total: " + r);
}
public static void main(final String... args) throws IOException {
System.out.print("Input: ");
final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
final String s = br.readLine();
final long t = System.currentTimeMillis();
if (s.isEmpty()) {
System.out.println("Running tests");
test5();
}
else {
init(s);
sort();
show();
}
System.out.println("Time: " + (System.currentTimeMillis() - t + 500) / 1000 + " sec");
}
}
Input is a list of numbers separated by comma and/or space (from stdin). If the input is empty, the program runs the 5 tests. Each one takes about 40 sec here.
One move brute-force then selection sort (also naive solution), 90 + 89 + 88 + 87 + 89 = 443 moves
let doReverse = (a, l, r) => {
a.splice(l, r - l, ...a.slice(l, r).reverse());
};
let selectSubVectorReverseSort = a => {
let log = [];
for (let i = 0, l = a.length; i < l; i++) {
let j, p = i;
for (j = i; j < l; j++) {
if (a[j] < a[p]) p = j;
}
if (p === i) continue;
log.push([i, p + 1]);
doReverse(a, i, p + 1);
}
return log;
};
let a = JSON.parse(`[${readline()}]`);
let copiedArray = a => a.map(x => x);
let minLog = selectSubVectorReverseSort(copiedArray(a));
for (let i = 0, l = a.length; i < l; i++) {
for (let j = i + 1; j < l; j++) {
let b = copiedArray(a);
doReverse(b, i, j + 1);
let log = [[i, j + 1], ...selectSubVectorReverseSort(b)];
if (log.length < minLog.length) minLog = log;
}
}
print(minLog.length);
for every possible first move, try it, and then, do a selection sort.
Yes, this is another naive solution.
I'm not sure this should be an edit or another post, but it seems the solution is too simple, so editing is chosen.
Selection Sort (Naive Solution), 92 + 93 + 95 + 93 + 96 = 469 moves
let log = [];
let doReverse = (a, l, r) => {
log.push([l, r]);
a.splice(l, r - l, ...a.slice(l, r).reverse());
}
let a = JSON.parse(`[${readline()}]`);
for (let i = 0, l = a.length; i < l; i++) {
let j, p = i;
for (j = i; j < l; j++) {
if (a[j] < a[p]) p = j;
}
if (p === i) continue;
doReverse(a, i, p + 1);
}
print(log.length)
A naive solution use selection sort.
There MUST be some better solutions, but post this since I did not find a better one (without brute-force search).
(Above code is JavaScript Shell)