Étant donné une liste de travaux, qui doivent être effectués dans l'ordre, chacun prenant un emplacement à faire, combien de temps cela prendra-t-il pour les exécuter tous si après avoir effectué un travail, le même travail ne peut pas être effectué pour les deux emplacements suivants (refroidissement des emplacements )? Cependant, un travail différent peut être affecté dans ces emplacements de refroidissement.

Par exemple,

[9,10,9,8] => output: 5

Parce que les emplois seront attribués en tant que [9 10 _ 9 8].
1. Tout d'abord, 9 a besoin de deux points de refroidissement _ _. Nous commençons donc par 9 _ _.
2. Le travail suivant 10 est différent du travail précédent 9, nous pouvons donc allouer l'un des _ _. Ensuite, nous aurons 9 10 _.
3. Troisièmement, 9 ne peut pas être alloué maintenant, car le premier travail 9 est le même travail et nécessite un temps de refroidissement. 9 10 _ 9.
4. Enfin, 8 n'est pas le même que les deux autres travaux précédents, il peut donc être alloué juste après 9 et puisqu'il s'agit du dernier travail, il n'a pas besoin de temps de refroidissement. La liste finale est 9 10 _ 9 8et la sortie attendue est 5, qui est le nombre de spots (ou nombre de slots)

Cas de test:

[1,2,3,4,5,6,7,8,9,10] => output : 10 ([1 2 3 4 5 6 7 8 9 10])
[1,1,1] => output: 7 ([1 _ _ 1 _ _ 1])
[3,4,4,3] => output: 6 ([3 4 _ _ 4 3])
[3,4,5,3] => output: 4 ([3 4 5 3])
[3,4,3,4] => output : 5 ([3 4 _ 3 4])
[3,3,4,4] => output : 8 ([3 _ _ 3 4 _ _ 4])
[3,3,4,3] => output : 7 ([3 _ _ 3 4 _ 3])
[3,2,1,3,-4] => output : 5 ([3 2 1 3 -4])
[] => output : 0 ([])
[-1,-1] => output : 4 ([-1 _ _ -1])

La valeur d'entrée peut être n'importe quel entier (négatif, 0, positif). La longueur de la liste des tâches est 0 <= longueur <= 1 000 000.
La sortie sera un entier, le nombre total d'emplacements, qui est indiqué dans le cas de test comme sortie. La liste entre parenthèses indique comment la sortie serait générée.

Code de critère gagnant
-golf

Gelée , 14 octets

ṫ-i⁹⁶ẋ⁸;;µƒ⁶L’

Essayez-le en ligne!

05AB1E , 22 octets

v¯R¬yQiõˆ}2£yåiˆ}yˆ}¯g

Essayez-le en ligne ou vérifiez tous les cas de test .

Explication:

v           # Loop over the integers `y` of the (implicit) input-list:
 ¯R         #  Push the global_array, and reverse it
   ¬        #  Get the first item (without popping the reversed global_array itself)
    yQi  }  #  If it's equal to the integer `y`:
       õˆ   #   Add an empty string to the global_array
   2£       #  Then only leave the first 2 items of the reversed global_array
     yåi }  #  If the integer `y` is in these first 2 items:
        ˆ   #   Add the (implicit) input-list to the global_array
 yˆ         #  And push the integer `y` itself to the global_array
}¯g         # After the loop: push the global array, and then pop and push its length
            # (which is output implicitly as result)

Brachylog , 10 octets

C'est toujours agréable de voir le problème où Brachylog est le plus performant

⊆Is₃ᶠ≠ᵐ∧Il

Explication

⊆I           # Find the minimal ordered superset of the input (and store in I) where:
   s₃ᶠ       #     each substring of length 3
      ≠ᵐ     #     has only distinct numbers
        ∧Il  # and output the length of that superset

Essayez-le en ligne!

R , 123 octets

`-`=nchar;x=scan(,'');while(x!=(y=gsub("([^,]+),(([^,]*,){0,1})\\1(,|$)","\\1,\\2,\\1\\4",x)))x=y;-gsub("[^,]","",y)+(-y>1)

Essayez-le en ligne - programme unique!

Essayez-le en ligne - plusieurs exemples!

Un programme complet qui lit une liste d'entiers séparés par des virgules comme entrée et génère les emplacements nécessaires. Je suis sûr que cela pourrait être joué un peu plus, et la mise en œuvre de cette solution basée sur regex dans d'autres langues serait plus efficace en octets.

Remarque sur le deuxième TIO, je l'ai enveloppé dans une fonction pour permettre l'affichage de plusieurs exemples. Cette fonction affiche également la liste finale, mais celle-ci n'est pas affichée dans le programme principal si elle est exécutée isolément.

Requête TSQL, 158 octets

Saisissez les données sous forme de tableau.

La requête est récursive donc

OPTION (MAXRECURSION 0)

est nécessaire, car la liste des nombres peut dépasser 100 bien qu'elle ne puisse gérer que 32 767 récursions - la limitation est-elle vraiment nécessaire dans cette tâche?

DECLARE @ table(a int, r int identity(1,1))
INSERT @ VALUES(3),(3),(4),(4);

WITH k as(SELECT null b,null c,1p
UNION ALL
SELECT iif(a in(b,c),null,a),b,p+iif(a in(b,c),0,1)FROM @,k
WHERE p=r)SELECT sum(1)-1FROM k
OPTION(MAXRECURSION 0) 

Essayez-le en ligne

R , 81 70 octets

sum(l<-rle(s<-scan())$l*3-3,1-l%/%6,((r=rle(diff(s,2)))$l+1)%/%2*!r$v)

Essayez-le en ligne!

Après plusieurs tentatives infructueuses, le code est devenu plutôt laid et pas si court, mais au moins il fonctionne maintenant ...

Tout d'abord, nous évaluons la durée des exécutions consécutives du même travail. Par exemple, 3, 3, 4, 3cela donne:

Run Length Encoding
  lengths: int [1:3] 2 1 1
  values : num [1:3] 3 4 3

Chacune de ces exécutions produit des (len - 1) * 3 + 1étapes ( + 1est gérée séparément).

Ensuite, nous traitons les occurrences du même travail à 2 endroits d'intervalle, comme:, x, y, xen utilisant diff(s, lag=2). Le vecteur résultant est également divisé en séquences consécutives ( r) par rlefonction. Maintenant, en raison de diverses alternances entrelacées, nous devons ajouter des ceiling(r$len/2)étapes pour toutes les séries de zéros. Par exemple:

x y x(longueur 1) et x y x y(longueur 2) nécessitent tous deux 1 pas supplémentaire:x y _ x (y)

x y x y x(longueur 3) et x y x y x y(longueur 4) nécessitent toutes deux 2 étapes supplémentaires:x y _ x y _ x (y)

Enfin, nous devons compenser les occurrences de ces alternances au milieu d'un long terme du même travail x, x, x, x...:, donc 1-l%/%6au lieu de simplement 1.

Python 2 , 67 octets

r=[]
for x in input():
 while x in r[-2:]:r+=r,
 r+=x,
print len(r)

Essayez-le en ligne!

Met en œuvre le défi assez littéralement. Utilise des copies de la liste elle-même en tant que "blancs", car ceux-ci ne peuvent être égaux à aucun nombre.

Fusain , 27 23 octets

Ｆθ«Ｗ№✂υ±²¦¦¦ι⊞υω⊞υι»ＩＬυ

Essayez-le en ligne! Le lien est vers la version détaillée du code. Explication:

Ｆθ«

Boucle sur les travaux.

Ｗ№✂υ±²¦¦¦ι⊞υω

Ajoutez des points de refroidissement tandis que le travail est l'un des deux derniers dans le résultat.

⊞υι»

Ajoutez le travail en cours au résultat.

ＩＬυ

Imprimez le nombre de taches.

R , 74 68 octets

length(Reduce(function(x,y)c(y,rep("",match(y,x[2:1],0)),x),scan()))

Essayez-le en ligne!

Construit le tableau de travail (en sens inverse), puis prend la longueur. Un peu plus court que la réponse de Kirill L. , donc parfois, l'approche naïve est plutôt bonne. EDIT: encore plus court! J'ai également emprunté le modèle de test de Kirill.

-6 octets remplaçant max(0,which(y==x[2:1])) par match(y,x,0) .

Perl 6 , 98 octets

{($!=$,|$_ Z$_ Z .[1..*+1])>>.repeated.squish(:with({$+^=[*] $! ne$^a ne$^b,$b==($!=$a)})).sum+$_}

Essayez-le en ligne!

Blergh, il doit y avoir une meilleure façon de le faire. Je ne suis pas sûr à 100% que cela soit tout à fait correct, bien qu'il passe tous les cas extrêmes auxquels je pourrais penser.

Fondamentalement, cela commence par regrouper tous les triplets de la liste d'entrée, avec un remplissage de chaque côté. Par exemple, [1,2,1,2]devient (Any,1,2), (1,2,1), (2,1,2), (1,2,Nil). Nous obtenons les repeatedéléments dans chaque triplet, devenant (), (1), (2), ().

Il s'agit alors d' squishéléments consécutifs qui ne sont pas la même liste, mais qui sont de la même taille (pour ne pas écraser quelque chose comme [1,1,1]), et le premier élément n'est pas égal à l'élément précédent (car nous ne pouvons pas fusionner les heures [1,1,2,2]), et enfin l'élément précédent n'a pas non plus été écrasé ( [1,2,1,2,1,2]). Donc, (1), (2)dans l'exemple ci-dessus, ils seraient écrasés ensemble.

Enfin, nous obtenons sumtoutes les longueurs de cette liste, qui représentent nos heures insérées, et ajoutons la longueur de la liste d'origine.

Par exemple:

(1,1,1) => (Any,1,1),(1,1,1),(1,1,Nil) => (1),(1,1),(1) => (no squishes) => 4+3 = 7
(1,2,1,2,1,2) => (Any,1,2), (1,2,1), (2,1,2), (1,2,1), (2,1,2), (1,2,Nil) => (),(1),(2),(1),(2),() => squish (1),(2) and (1),(2) => 2+6 = 8

JavaScript (ES6), 57 octets

f=([x,...a],p,q)=>1/x?1+f(x!=p&x!=q?a:[x,...a,x=f],x,p):0

Essayez-le en ligne!

Commenté

f = (             // f is a recursive function taking:
  [x,             //   x   = next job
      ...a],      //   a[] = array of remaining jobs
  p,              //   p   = previous job, initially undefined
  q               //   q   = penultimate job, initially undefined
) =>              //
  1 / x ?         // if x is defined and numeric:
    1 +           //   add 1 to the grand total
    f(            //   and do a recursive call to f:
      x != p &    //     if x is different from the previous job
      x != q ?    //     and different from the penultimate job:
        a         //       just pass the remaining jobs
      :           //     else:
        [ x,      //       pass x, which can't be assigned yet
          ...a,   //       pass the remaining jobs
          x = f   //       set x to a non-numeric value
        ],        //
      x,          //     previous job = x
      p           //     penultimate job = previous job
    )             //   end of recursive call
  :               // else:
    0             //   stop recursion

C (gcc) , 69 octets

f(j,l)int*j;{j=l>1?(*j-*++j?j[-1]==j[l>2]?j++,l--,3:1:3)+f(j,l-1):l;}

Essayez-le en ligne!

Récursivité simple.

f(j,l)int*j;{               //Jobs, (array) Length
    j=l>1                   //if l > 1, do a recursion:
        ? (*j-*++j          // check if first and second elements are equal (j++)
            ? j[-1]==       //  1st!=2nd; check if first and third are equal
                j[l>2]      //  (first and second if l==2, but we already know 1st!=2nd)
                ? j++,l--,3 //   1st==3rd (j++,l--) return 3+f(j+2,l-2)
                : 1         //   1st!=3rd (or l==2) return 1+f(j+1,l-1)
            : 3             //  1st==2nd            return 3+f(j+1,l-1)
          )+f(j,l-1)        // j and l were modified as needed
        : l;                // nothing more needed  return l
}

Perl 6 , 48 octets

{$!=0;.map:{{$_=($!=$!+1 max$_)+3}((%){$_})};$!}

Essayez-le en ligne!

45 octets si la liste comporte au moins deux éléments:

+*.reduce:{$^b,|(*xx 3-(|$^a,*,$b...$b)),|$a}

Essayez-le en ligne!

Smalltalk, 125 octets

c:=0.n:=q size.1to:n-2do:[:i|(j:=q at:i)=(k:=q at:i+1)ifTrue:[c:=c+2].j=(m:=q at:i+2)ifTrue:[c:=c+1]].k=m ifTrue:[c:=c+1].c+n

Explication

c : accumulator of proximity penalty
q : input array.
n := q length
i : iteration index from 1 to: n-2 (arrays are 1-based in Smalltalk).
j := memory for element i, saves some few bytes when reused
k := similar to j but for i+1.
m := similar to k but for i+2.

Perl 5 -pl , 42 40 octets

$a{$_}=~s/.*/$\=$&if++$\<$&;$\+3/e}{$_=0

Essayez-le en ligne!

Lot, 184 octets

@echo off
@set l=-
@set p=-
@set n=0
@for %%j in (%*)do @call:c %%j
@exit/b%n%
:c
@if %1==%l% (set l=-&set/an+=2)else if %1==%p% set l=-&set/an+=1
@set p=%l%&set l=%1&set/an+=1

L'entrée se fait via des arguments de ligne de commande et la sortie se fait via un code de sortie. Explication:

@set l=-
@set p=-

Suivez les deux derniers travaux.

@set n=0

Initialisez le décompte.

@for %%j in (%*)do @call:c %%j

Traitez chaque tâche.

@exit/b%n%

Afficher le décompte final.

:c

Pour chaque travail:

@if %1==%l% (set l=-&set/an+=2)else if %1==%p% set l=-&set/an+=1

Si nous avons traité le travail récemment, ajoutez un nombre approprié de points de refroidissement. En outre, effacez le dernier travail afin que le travail suivant ne déclenche le refroidissement que s'il est identique à ce travail.

@set p=%l%&set l=%1&set/an+=1

Mettez à jour les deux derniers travaux et attribuez une place à ce travail.

Swift, 114 octets

func t(a:[Int]){
var s=1
for i in 1...a.count-1{s = a[i-1]==a[i] ? s+3:i>1&&a[i-2]==a[i] ? s+2:s+1}
print("\(s)")}

Essayez-le en ligne!

Python 3 , 79 75 octets

-3 octets grâce à mypetlion
-1 octet grâce à Sara J

f=lambda a,b=[]:a and f(*[a[1:],a,a[:1]+b,[b]+b][a[0]in b[:2]::2])or len(b)

Essayez-le en ligne!

Java (JDK) , 110 octets

j->{int p,q;for(p=q=j.length;p-->1;q+=j[p]==j[p-1]?2:(p>1&&j[p]==j[p-2]&(p<3||j[p-1]!=j[p-3]))?1:0);return q;}

Essayez-le en ligne!

Code commenté non golfé:

j -> {
    int p, q = j.length; // Run all jobs
    for (p = q; p-- > 1;) { // reverse iterate
        q += j[p] == j[p - 1] ? 2 : // add 2 if prev same
        (p > 1 && j[p] == j[p - 2] & // 1 if 2prev same
        (p < 3 || j[p - 1] != j[p - 3]) // except already done
        ) ? 1 : 0; // otherwise 0
    }
    return q;
}

Gelée , 20 octets

ṫ-i⁹⁶x;
⁶;ç³Ṫ¤¥¥³¿L’

Essayez-le en ligne!

Bien que cela soit assez similaire à la réponse courte de @ EriktheOutgolfer , je l'ai écrite sans voir la sienne. En tout cas c'est mieux!

Explication

Lien dyadique d'aide, prend la liste actuelle comme élément de gauche et l'élément suivant comme droit

ṫ-            | take the last two items in the list
  i⁹          | find the index of the new item
    ⁶x        | that many space characters
      ;       | prepend to new item

Lien monadique principal, prend la liste des entiers en entrée

⁶             | start with a single space
 ;            | append...
  ç³Ṫ¤¥       | the helper link called with the current list
              | as left item and the next input item as right
       ¥³¿    | loop the last two as a dyad until the input is empty
          L   | take the length
           ’  | subtract one for the original space

Python 2 , 75 octets

lambda a:len(reduce(lambda b,c:b+[c]*-~((c in b[-2:])+(c in b[-1:])),a,[]))

Essayez-le en ligne!

JavaScript (Node.js) , 52 octets

(a,i=0,h={})=>a.map(n=>h[n]=3+(i=h[n]>++i?h[n]:i))|i

Essayez-le en ligne!

APL (Dyalog Classic) , 22 octets

≢∊(⊢,⍨⊣,# #↓⍨⍳⍨)/⍵,⊂⍬⍬

Essayez-le en ligne!

JavaScript (V8), 101 octets

f=a=>for(var c=0,i=0;i<a.length;i++,c++)a[i-1]==a[i]?c+=2:a[i-2]==a[i]&&(c++,a[i-1]=void 0)
return c}

Essayez-le en ligne!

Le code décompressé se présente comme suit:

function f(a)
{
    var c = 0;
    for (var i = 0; i < a.length; i++, c++)
    {
        if (a[i - 1] == a[i])
            c+=2;
        else if (a[i - 2] == a[i])
            c++,a[i-1]=undefined;
    }

    return c;
}

Ma toute première tentative de golf de code, peut probablement être beaucoup optimisée en réduisant le tableau et en le passant récursivement.

Zsh , 66 60 octets

-6 octets implicites "$@"

for j
{((i=$a[(I)$j]))&&a=
a=("$a[-1]" $j)
((x+=i+1))}
<<<$x

Essayez-le en ligne! Je recommande fortement d'ajouter set -xau début afin que vous puissiez suivre.

for j                   # Implicit "$@"
{                       # Use '{' '}' instead of 'do' 'done'
    (( i=$a[(I)$j] )) \ # (see below)
        && a=           # if the previous returned true, empty a
    a=( "$a[-1]" $j )   # set the array to its last element and the new job
    (( x += i + 1 ))    # add number of slots we advanced
}
<<<$x                   # echo back our total

((i=$a[(I)$j]))
    $a[     ]           # Array lookup
       (I)$j            # Get highest index matched by $j, or 0 if not found
  i=                    # Set to i
((           ))         # If i was set nonzero, return true

acontient toujours les deux derniers travaux, donc si la recherche trouve un travail correspondant dans a[2], nous incrémentons de trois (puisque les emplacements de travail seront[... 3 _ _ 3 ...] ).

Si a n'est pas défini, la recherche échouera et l'expansion arithmétique renverra une erreur, mais cela ne se produit que lors du premier travail et n'est pas fatal.

Nous pouvons enregistrer un octet de plus si nous utilisons à la $[x+=i+1]place, et il n'y a pas de commandes sur le système des utilisateurs entièrement composées de chiffres.

K (ngn / k) , 27 octets

{#2_``{y,#[0|2-x?y;`],x}/x}

Essayez-le en ligne!