Code golf the best permutation

CJam (60 bytes + 120 = 180 score)

{_5/4*8e!961=7_)er<:A\,^e!{A\+}%{2ew::-:z1&!},{_$.-:z1b}$0=}

Online test suite with integrated scoring

Extension up to n=24

Dissection

{
  _5/4*        e# Work out how much of the hard-coded prefix to use
  8e!961=7_)er e# Prefix [0 2 4 1 3 5 8 6]
               e# I identified this by brute forcing up to n=10 and looking for patterns
               e# I then used the identified prefix [0 2 4 1] to brute-force further
  <:A          e# Take the desired prefix of the hard-coded array, and store a copy in A
  \,^e!        e# Generate all permutations of the values in [0 .. n-1] which aren't in A
  {A\+}%       e# Prepend A to each of them
  {            e# Filter...
    2ew::-     e#   Take each difference of two consecutive elements
    :z         e#   Find their absolute values
    1&         e#   Test whether 1 is among those absolute values
    !          e#   Reject if it is
  },
  {            e# Sort by...
    _$.-       e#   Take pairwise differences of permutation with the identity
    :z         e#   Absolute values
    1b         e#   Add them (by interpreting in base 1)
  }$
  0=           e# Take the first
}

Jelly, 36 34 33 32 31 30 bytes, result: 120

Thanks to Dennis for -1 byte! (implicitly by fixing a Jelly bug, although the feature postdates the challenge)

ðRḟISị“Ƥ¿‘Ʋœ?$;@µ2x5~4¦ṁ_4$Ä’

New feature: accumulated sum (Ä).

Try it online!

Use 1-indexing.

Takes linear time, too.

---

This C++ program generates the lexicographically smallest permutation, assuming that |i - p_i| ≤ width (where width is a hardcoded constant) for all 0 ≤ i < n, with time complexity about O(width² × 2^2×width × n) (which is just O(n) for fixed width): Try it online!

---

How?

1. Write a C++ program attempting to solve the problem optimally.

2. Observe the pattern. We note that the sequence of all elements except 4 last ones is a prefix of

   0 2 4 1 3 5 7 9 6 8 10 12 14 11 13 15 17 19 16 18 20 22 24 21 23 25 ...
   

3. Computes the sequence's incremental difference.

   2 2 -3 2 2 2 2 -3 2 2 2 2 -3 2 2 2 2 -3 2 2 2 2 -3 2 2
   

   Note the period 5.

4. The Jelly implementation:

   • n-4 first elements are taken from the sequence above. O(n).

   • For 4 last elements, just brute force all 24 possibilities. O(1).

     (note: I no longer brute force all 24 possibilities from the 32-bytes version)

Haskell, 146+89 score+bytes

f i|k<-mod i 4=scanl(+)1$take(i-2-k)(cycle[2,-3,2,3])++[[2],[2,2],[5,-3,2],[5,-3,2,2]]!!k

Repeats pattern [1,3,0,2], last mod i 4 elements are hand tuned.

Previous algorithm (132+116):

f i=last$filter(\a->all(`elem`a)[0..i-1]).(!!(i-1)).iterate((\l->map((:l).(+head l))[-3,2,-2,3])=<<)$pure<$>[i-3..i]

Bruteforces the correct number of jumps of length ±2 or ±3. Selects the last one that has the correct numbers in it, seems to work just fine and is a lot cheaper than implementing the score. Tio just runs out time before the last score, which is 18.

Try it online!