Diberikan daftar pekerjaan, yang harus dilakukan secara berurutan, dengan masing-masing mengambil slot untuk dilakukan, berapa lama waktu yang dibutuhkan untuk melakukan semuanya jika setelah melakukan pekerjaan, pekerjaan yang sama tidak dapat dilakukan untuk dua slot berikutnya (mendinginkan slot )? Namun, pekerjaan yang berbeda dapat ditugaskan dalam slot pendinginan ini.

Sebagai contoh,

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

Karena pekerjaan akan dialokasikan sebagai [9 10 _ 9 8].
1. Pertama, 9 membutuhkan dua titik pendinginan _ _. Jadi kita mulai dengan 9 _ _.
2. Pekerjaan berikutnya 10 berbeda dari pekerjaan sebelumnya 9, jadi kami dapat mengalokasikan salah satu dari _ _. Maka kita akan punya 9 10 _.
3. Ketiga, 9 tidak dapat dialokasikan sekarang, karena pekerjaan pertama 9 adalah pekerjaan yang sama dan perlu pendinginan waktu. 9 10 _ 9.
4. Terakhir, 8 tidak sama dengan dua pekerjaan sebelumnya lainnya, sehingga dapat dialokasikan setelah 9 dan karena ini adalah pekerjaan terakhir, tidak perlu pendinginan waktu. Daftar akhir adalah 9 10 _ 9 8dan output yang diharapkan adalah 5, yang merupakan jumlah tempat (atau jumlah slot)

Kasus uji:

[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])

Nilai input dapat berupa bilangan bulat apa saja (negatif, 0, positif). Panjang daftar pekerjaan adalah 0 <= panjang <= 1.000.000.
Output akan berupa integer, jumlah total slot, yang ditunjukkan dalam test case sebagai output. Daftar di dalam tanda kurung adalah bagaimana output akan dihasilkan.

Memenangkan kriteria
kode-golf

Jelly , 14 byte

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

Cobalah online!

05AB1E , 22 byte

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

Cobalah secara online atau verifikasi semua kasus uji .

Penjelasan:

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 byte

Selalu menyenangkan melihat masalah di mana Brachylog berkinerja terbaik

⊆Is₃ᶠ≠ᵐ∧Il

Penjelasan

⊆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

Cobalah online!

R , 123 byte

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

Cobalah online - satu program!

Cobalah online - beberapa contoh!

Program lengkap yang membaca daftar bilangan bulat yang dipisahkan koma sebagai input, dan mengeluarkan slot yang dibutuhkan. Saya yakin ini bisa lebih golf, dan menerapkan solusi berbasis regex ini dalam beberapa bahasa lain akan lebih efisien dalam byte.

Catatan pada TIO kedua saya membungkusnya dalam suatu fungsi untuk memungkinkan beberapa contoh ditampilkan. Fungsi ini juga menunjukkan daftar akhir, tetapi ini bukan output program utama saya jika dijalankan secara terpisah.

Permintaan TSQL, 158 byte

Masukkan data sebagai tabel.

Kueri bersifat rekursif jadi

OPTION (MAXRECURSION 0)

diperlukan, karena daftar angka dapat melebihi 100 walaupun hanya bisa menangani 32.767 rekursi - apakah pembatasan benar-benar diperlukan dalam tugas ini?

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) 

Cobalah online

R , 81 70 byte

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

Cobalah online!

Setelah beberapa upaya gagal, kode berubah agak jelek dan tidak terlalu pendek, tetapi setidaknya berfungsi sekarang ...

Pertama, kami mengevaluasi durasi berturut-turut dari pekerjaan yang sama. Misalnya untuk 3, 3, 4, 3ini memberi:

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

Setiap (len - 1) * 3 + 1langkah ini menghasilkan langkah-langkah (+ 1 ditangani secara terpisah).

Selanjutnya, kami memproses kejadian dengan pekerjaan yang sama 2 tempat terpisah, seperti:, x, y, xdengan menggunakan diff(s, lag=2). Vektor yang dihasilkan juga dipotong menjadi run berurutan ( r) berdasarkan rlefungsi. Sekarang, karena berbagai pergantian berselang kita perlu menambahkan ceiling(r$len/2)langkah untuk semua run dari nol. Misalnya:

x y x(panjang 1) dan x y x y(panjang 2) keduanya membutuhkan 1 langkah ekstra:x y _ x (y)

x y x y x(panjang 3) dan x y x y x y(panjang 4) keduanya membutuhkan 2 langkah ekstra:x y _ x y _ x (y)

Akhirnya, kita perlu mengimbangi kemunculan dari pergantian-pergantian ini di tengah jangka panjang dari pekerjaan yang sama:, x, x, x, x...karenanya 1-l%/%6alih-alih sederhana 1.

Python 2 , 67 byte

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

Cobalah online!

Menerapkan tantangan secara harfiah. Menggunakan salinan daftar itu sendiri sebagai "kosong", karena ini tidak dapat sama dengan angka berapa pun.

Arang , 27 23 byte

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

Cobalah online! Tautan adalah untuk mengucapkan versi kode. Penjelasan:

Ｆθ«

Lewati pekerjaan.

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

Tambahkan titik pendinginan saat pekerjaan adalah salah satu dari dua yang terakhir di hasilnya.

⊞υι»

Tambahkan pekerjaan saat ini ke hasilnya.

ＩＬυ

Cetak jumlah tempat.

R , 74 68 byte

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

Cobalah online!

Bangun susunan kerja (terbalik), lalu ambil panjangnya. Hanya sedikit lebih pendek dari jawaban Kirill L. , jadi terkadang, pendekatan naifnya cukup bagus. Sunting: lebih pendek lagi! Saya juga meminjam template uji Kirill.

-6 byte diganti max(0,which(y==x[2:1])) dengan match(y,x,0) .

Perl 6 , 98 byte

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

Cobalah online!

Blergh, pasti ada cara yang lebih baik untuk melakukan ini. Saya tidak 100% yakin ini sepenuhnya benar, meskipun melewati semua kasus tepi yang dapat saya pikirkan.

Pada dasarnya, ini dimulai dengan mengelompokkan semua kembar tiga dari daftar input, dengan bantalan di kedua sisi. Misalnya, [1,2,1,2]menjadi (Any,1,2), (1,2,1), (2,1,2), (1,2,Nil). Kami mendapatkan repeatedelemen di setiap triplet, menjadi (), (1), (2), ().

Kemudian squishelemen berurutan yang bukan daftar yang sama, tetapi memiliki ukuran yang sama (untuk tidak squish seperti [1,1,1]), dan elemen pertama tidak sama dengan elemen sebelumnya (karena kita tidak dapat menggabungkan jam di [1,1,2,2]), dan akhirnya elemen sebelumnya juga belum di-squished ( [1,2,1,2,1,2]). Jadi (1), (2)dalam contoh di atas akan diperas bersama.

Akhirnya, kami mendapatkan sumsemua panjang dari daftar ini, yang mewakili jam yang dimasukkan, dan menambahkan panjang dari daftar asli.

Sebagai contoh:

(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 byte

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

Cobalah online!

Berkomentar

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 byte

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;}

Cobalah online!

Rekursi langsung.

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 byte

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

Cobalah online!

45 byte jika daftar memiliki setidaknya dua elemen:

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

Cobalah online!

Smalltalk, 125 byte

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

Penjelasan

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 byte

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

Cobalah online!

Batch, 184 byte

@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

Input melalui argumen baris perintah dan output melalui kode keluar. Penjelasan:

@set l=-
@set p=-

Lacak dua pekerjaan terakhir.

@set n=0

Inisialisasi penghitungan.

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

Proses setiap pekerjaan.

@exit/b%n%

Keluarkan hitungan akhir.

:c

Untuk setiap pekerjaan:

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

Jika kami memproses pekerjaan baru-baru ini, tambahkan jumlah titik pendinginan yang tepat. Selain itu, bersihkan pekerjaan terakhir sehingga pekerjaan berikutnya hanya memicu pendinginan jika sama dengan pekerjaan ini.

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

Perbarui dua pekerjaan terakhir dan alokasikan satu tempat untuk pekerjaan ini.

Swift, 114 byte

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)")}

Cobalah online!

Python 3 , 79 75 byte

-3 byte terima kasih kepada mypetlion
-1 byte terima kasih kepada 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)

Cobalah online!

Java (JDK) , 110 byte

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;}

Cobalah online!

Kode komentar yang tidak disatukan:

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;
}

Jelly , 20 byte

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

Cobalah online!

Meskipun ini agak mirip dengan jawaban pendek @ EriktheOutgolfer , saya menulisnya tanpa melihatnya. Bagaimanapun dia lebih baik!

Penjelasan

Tautan dyadic helper, mengambil daftar saat ini sebagai item kiri dan item berikutnya sebagai kanan

ṫ-            | 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

Tautan monadik utama, mengambil daftar bilangan bulat sebagai input

⁶             | 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 byte

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

Cobalah online!

JavaScript (Node.js) , 52 byte

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

Cobalah online!

APL (Dyalog Classic) , 22 byte

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

Cobalah online!

JavaScript (V8), 101 byte

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}

Cobalah online!

Kode yang dibongkar terlihat sebagai berikut:

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;
}

Upaya kode-golf pertama saya, mungkin dapat dioptimalkan banyak dengan mengecilkan array dan meneruskannya secara rekursif.

Zsh , 66 60 byte

-6 byte dari implisit "$@"

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

Cobalah online! Saya sangat merekomendasikan set -xuntuk menambahkan ke awal sehingga Anda dapat mengikuti.

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

aselalu berisi dua pekerjaan terakhir, jadi jika pencarian menemukan pekerjaan yang cocok a[2], kami bertambah tiga (karena slot pekerjaan akan menjadi[... 3 _ _ 3 ...] ).

Jika atidak disetel, pencarian akan gagal dan ekspansi aritmatika akan mengembalikan kesalahan, tetapi itu hanya terjadi pada pekerjaan pertama dan tidak fatal.

Kita dapat menyimpan satu byte lagi jika kita menggunakan $[x+=i+1]sebaliknya, dan tidak ada perintah pada sistem pengguna yang seluruhnya terdiri dari digit.

K (ngn / k) , 27 byte

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

Cobalah online!