Défi

Étant donné un entier n ≥ 4 , émettez une permutation des nombres entiers [0, n-1] avec la propriété qu'aucun deux nombres entiers consécutifs ne sont côte à côte. La valeur d'une permutation piest la somme de abs(pi[i] - i)pour tous les indices i.

Exemples

• (1, 3, 0, 2) a de la valeur 6
• (0, 2, 4, 1, 3) a de la valeur 6
• (0, 2, 4, 1, 3, 5) a de la valeur 6
• (0, 2, 4, 1, 5, 3, 6) a de la valeur 8

Score de votre réponse

Le score de votre réponse est la somme des valeurs de vos permutations pour n = 4 .. 14plus le nombre d'octets que prend votre code. Plus le score est bas, mieux c'est. Votre code doit fournir une sortie valide pour toutes ces valeurs de n.

Vous devez pouvoir exécuter votre soumission jusqu'à son terme sur votre machine.

En cas d'égalité, l'heure du dernier montage qui a abouti au score correspondant sera décisive.

N'est-ce pas la même question que celle-ci ?

Les réponses à la question liée ne seront pas compétitives pour cette question car elles ne font aucun effort pour optimiser la valeur d'une permutation. Par exemple pour n=10, la permutation [1, 3, 5, 7, 9, 0, 2, 4, 6, 8]donnée par la plupart des réponses donne une valeur de 30. Vous pouvez faire bien mieux que ça.

Pour la partie permutation de la question, la valeur optimale globale est au maximum 120. (Merci à @Laikoni.) Alors que la réponse de Dennis à la question précédente obtient 222 . (Merci à @ user202729.)

Gelée , 36 34 33 32 31 30 octets, résultat: 120

Merci à Dennis pour -1 octet! (implicitement en corrigeant un bug Jelly, bien que la fonctionnalité soit postérieure au défi)

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

Nouvelle fonctionnalité: somme cumulée ( Ä).

Essayez-le en ligne!

Utilisez l'indexation 1.

Prend aussi du temps linéaire.

Ce programme C ++ génère la permutation lexicographiquement la plus petite, en supposant que | i - p _i | ≤ largeur (où largeur est une constante codée en dur) pour tout 0 ≤ i <n , avec une complexité temporelle d'environ O (largeur ² × 2 ^{2 × largeur} × n) (qui est juste O (n) pour une largeur fixe ): Essayez-le en ligne !

Comment?

1. Écrivez un programme C ++ essayant de résoudre le problème de manière optimale.

2. Observez le motif. On note que la séquence de tous les éléments sauf les 4 derniers est un préfixe de

   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. Calcule la différence incrémentielle de la séquence.

   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
   

   Notez la période 5.

4. L'implémentation de Jelly:

   • n-4 premiers éléments sont tirés de la séquence ci-dessus. O (n) .

   • Pour les 4 derniers éléments, forcez simplement les 24 possibilités . O (1) .

     (note: je ne force plus brutalement les 24 possibilités de la version 32 octets)

CJam (60 octets + 120 = score 180)

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

Suite de tests en ligne avec notation intégrée

Extension jusqu'à 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
}

Haskell , 146 + 89 score + octets

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

Répète le motif [1,3,0,2], les derniers mod i 4éléments sont réglés à la main.

Algorithme précédent (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]

Renforce le nombre correct de sauts de longueur ± 2 ou ± 3. Sélectionne le dernier qui contient les bons chiffres, semble fonctionner très bien et est beaucoup moins cher que la mise en œuvre du score. Tio vient de manquer de temps avant le dernier score, qui est de 18.

Essayez-le en ligne!

Japt, 120 + 20 = 140

(Copier une de mes solutions de l'autre défi m'aurait valu 227)

o á k_äa d¥1ÃñxÈaYÃg

Essayez-le ou utilisez cette version pour vérifier les scores. Les deux versions peuvent commencer à vous craquer vers 9 heures.

Explication

o                        :Range [0,input)
  á                      :All permutations
    k_      Ã            :Remove sub-arrays that return true
      äa                 :  Get the consecutive absolute differnces
         d¥1             :  Do any equal 1?
               È  Ã      :Pass the integers in each remaining sub-array through a function
                aY       :  Get the absolute difference with the integer's index
              x          :Reduce by addition
             ñ           :Sort the main array by those values
                   ñ     :Return the first sub-array

Rubis , 120 points + 112106 91 82 octets

->n{(0...n).map{|a|a+(a+2)%5-([[],[],[0,4,3],[-1,4,4,4],[1,1,6,1]][n%5][a-n]||2)}}

Essayez-le en ligne!

La séquence est essentiellement (a-2)+(a+2)%5.

Si n mod 5 n'est pas 0 ou 1, les 3 ou 4 derniers éléments sont différents.

C'est encore à moitié codé en dur, trouve toujours la meilleure solution, peut-être pourrait-on jouer un peu plus au golf, mais je n'ai plus d'idées.

JavaScript (Node.js) , 148 score + 109 73 octets

n=>[...Array(n)].map(_=>l=!m|l>n%5+2&&l>m+2?[+m,m=l+2][0]:l+2,m=n>4,l=~m)

Essayez-le en ligne! Explication: lgarde la trace du dernier nombre généré et mgarde la trace du numéro suivant de la parité opposée à l; une fois ldépassé m+2les variables sont échangées. Un ajustement est effectué au début de la séquence afin que les séquences dont les longueurs ne sont pas des multiples de 5 ne manquent aucun nombre, et un autre ajustement est effectué pour n=4.