Codegolf Rainbow: Bersenang-senang dengan Integer-Arrays

12

Pengantar:

masukkan deskripsi gambar di sini(Sumber: Wikipedia )
Ketika kita melihat pelangi ia akan selalu memiliki warna dari atas ke bawah:
Merah; jeruk; kuning; hijau; biru; nila; violet

Jika kita melihat masing-masing cincin, cincin merah tentu saja lebih besar dari cincin ungu.
Selain itu, juga dimungkinkan untuk memiliki dua atau bahkan tiga pelangi secara bersamaan.

Semua gabungan di atas akan digunakan dalam tantangan ini:

Tantangan:

Diberikan daftar bilangan bulat dengan ukuran persis 7, di mana setiap nilai menunjukkan partikel warna yang tersedia untuk membentuk pelangi (di mana indeks terbesar menunjukkan merah dan indeks terkecil ditunjukkan ungu), menampilkan jumlah pelangi yang dapat dibentuk.

Satu integer-pelangi harus memiliki setidaknya 3x violet, 4x indigo, 5x biru, 6x hijau, 7x kuning, 8x oranye, 9x merah. Pelangi kedua di atasnya bahkan akan lebih besar dari cincin merah pelangi pertama (termasuk satu ruang di antara mereka), sehingga diperlukan setidaknya 11x violet, 12x indigo, 13x biru, 14x hijau, 15x kuning, 16x oranye , 17x merah sebagai tambahan dari apa yang digunakan pelangi pertama. Pelangi ketiga akan mulai pada 19x violet lagi.

Contoh:

Input-list: [15,20,18,33,24,29,41]
Output:2

Mengapa? Kami memiliki 15x violet, dan kami membutuhkan setidaknya 3 + 11 = 14 untuk dua pelangi. Kami memiliki 20 nila dan kami membutuhkan setidaknya 4 + 12 = 16 untuk dua pelangi. Dll. Kami memiliki cukup warna untuk dua pelangi, tetapi tidak cukup untuk membentuk tiga pelangi, jadi hasilnya adalah 2.

Aturan tantangan:

  • Bilangan bulat dalam larik input dijamin non-negatif ( >= 0).
  • Input-list dijamin ukurannya persis 7.
  • Ketika tidak ada pelangi dapat terbentuk, kami menghasilkan 0.
  • Format input dan output fleksibel. Dapat berupa daftar atau array bilangan desimal, bisa diambil dari STDIN. Output dapat berupa pengembalian dari suatu fungsi dalam tipe output yang masuk akal, atau dicetak langsung ke STDOUT.

Jumlah minimum warna yang dibutuhkan untuk njumlah pelangi:

Amount of Rainbows    Minimum amount per color
0                     [0,0,0,0,0,0,0]
1                     [3,4,5,6,7,8,9]
2                     [14,16,18,20,22,24,26]
3                     [33,36,39,42,45,48,51]
4                     [60,64,68,72,76,80,84]
5                     [95,100,105,110,115,120,125]
etc...

Aturan umum:

  • Ini adalah , jadi jawaban tersingkat dalam byte menang.
    Jangan biarkan bahasa kode-golf mencegah Anda memposting jawaban dengan bahasa non-codegolf. Cobalah untuk memberikan jawaban sesingkat mungkin untuk bahasa pemrograman 'apa pun'.
  • Aturan standar berlaku untuk jawaban Anda, jadi Anda diperbolehkan menggunakan STDIN / STDOUT, fungsi / metode dengan parameter yang tepat dan tipe pengembalian, program penuh. Panggilanmu.
  • Celah default tidak diperbolehkan.
  • Jika memungkinkan, silakan tambahkan tautan dengan tes untuk kode Anda.
  • Juga, menambahkan penjelasan untuk jawaban Anda sangat dianjurkan.

Kasus uji:

Input:  [15,20,18,33,24,29,41]
Output: 2

Input:  [3,4,5,6,7,8,9]
Output: 1

Input:  [9,8,7,6,5,4,3]
Output: 0

Input:  [100,100,100,100,100,100,100]
Output: 4

Input:  [53,58,90,42,111,57,66]
Output: 3

Input:  [0,0,0,0,0,0,0]
Output: 0

Input:  [95,100,105,110,115,120,125]
Output: 5

Input:  [39525,41278,39333,44444,39502,39599,39699]
Output: 98
Kevin Cruijssen
sumber
Kasus 0,0,0,0,0,0,0tepi :( (tidak cocok dengan logika 1-celah)
Jonathan Allan

Jawaban:

8

Pyth , 14 byte

thS.ef<b*+tkyy

Suite uji!

Bagaimana?

Algortihm

Pertama, mari kita turunkan rumus yang mendasari jawaban ini. Mari kita sebut fungsi yang memberikan jumlah yang diperlukan dari partikel warna , di mana adalah jumlah lapisan dan adalah indeks warna, berbasis 0. Pertama, kita perhatikan bahwa untuk layer (di mana adalah 1-diindeks, dalam hal ini), kita membutuhkan partikel warna . Dengan mengingat hal ini, kami menjumlahkan hasil dari setiap untuk setiap layer :n i n th n L ( n , i ) = i + 3 + 8 ( n - 1 ) L ( k , i ) kC(n,i)ninthnL(n,i)=i+3+8(n1)L(k,i)k

C ( n , i ) = ( i + 3 ) n

C(n,i)=(i+3)1st layer+(i+3+8)2nd layer++[i+3+8(n1)]nth layer
C ( n , i ) = ( i + 3 ) n + 8 ( n - 1 ) n
C(n,i)=(i+3)n+8(0+1++n1)
C(n,i)=n(i+3+4n-4)
C(n,i)=(i+3)n+8(n1)n2=(i+3)n+4n(n1)
C(n,i)=n(i+3+4n4)C(n,i)=n(4n+i1)

Oleh karena itu, kita sekarang tahu bahwa jumlah maksimum lapisan yang mungkin, sebut saja , harus memenuhi ketimpangan , di mana adalah elemen dari daftar input.C ( k , i ) I i I i i thkC(k,i)IiIiith

Penerapan

Ini mengimplementasikan fungsi , dan iterates ( ) di atas daftar input, dengan menjadi indeks (berbasis 0) dan menjadi elemen. Untuk setiap nilai, pencarian program pertama yang positif bilangan bulat yang (negasi logis dari , kondisi kita menyimpulkan sebelumnya), kemudian menemukan hasil minimum dan menurunkannya. Dengan cara ini, bukan mencari integer tertinggi yang tidak memenuhi kondisi, kita mencari terendah yang tidak dan kurangi satu dari itu untuk menebus offset dari 1.k b T b < C ( T , i ) C ( T , i ) bC.ekbTb<C(T,i)C(T,i)b

Tuan Xcoder
sumber
3

Python 2 , 64 61 byte

lambda l:min(((16*v+i*i)**.5-i)//8for i,v in enumerate(l,-1))

Cobalah online!


Setiap warna pelangi digunakan (3+i)+n*8untuk layer ndan warna i(0 = ungu, dll.)

Oleh karena itu total untuk x lapisan adalah: (3*i)*x + 8*x*(x+1).

Kami hanya menyelesaikan untuk n, dan mengambil nilai minimum.


Diselamatkan:

  • -3 byte, terima kasih atas ovs
TFeld
sumber
2
Ah, sekarang saya mendapat tanggapan itu ...
Jonathan Frech
1
61 byte
ovs
@ovs, Terima kasih :)
TFeld
3

05AB1E , 18 17 16 byte

Terima kasih -1 byte ke Magic Octopus Mm

[ND4*6Ý<+*¹›1å#N

Cobalah online!

Jumlah warna yang dibutuhkan untuk n pelangi adalah n (4n + [-1, 0, 1, 2, 3, 4, 5]) .

Okx
sumber
[ND4*6Ý<+*¹›1å#Nbekerja tetapi saya tidak tahu mengapa. -1 byte.
Magic Gurita Guci
@MagicOctopusUrn Terima kasih! Itu hanya menggunakan indeks loop bukan variabel counter.
Okx
Sepertinya aneh aku tidak perlu melakukan N>itu-- karena kamu pernah melakukannya ¾>sebelumnya.
Magic Octopus Mm
@MagicOctopusUrn Perintah untuk meningkatkan variabel penghitung tidak mendorong variabel penghitung.
Okx
2

JavaScript (ES6), 49 byte

f=(a,n)=>a.some((v,k)=>v<4*n*n-~-k*n)?~n:f(a,~-n)

Cobalah online!

Bagaimana?

P(n,k)nk

P(n,k)=n(4n+(k1))=4n2+(k1)n

nvkP(n,k)

Tetapi untuk tujuan bermain golf, kita mulai dengan n === undefineddan menggunakan nilai negatif nsesudahnya. Iterasi pertama selalu berhasil karena sisi kanan ketidaksetaraan dievaluasi NaN. Oleh karena itu, tes bermakna pertama adalah yang kedua dengan n == -1.

Arnauld
sumber
1

Jelly , 18 byte

Ṁµ×4+-r5¤×)⁸<Ẹ€¬TṪ

Cobalah online!

Gunakan penjelasan dalam jawaban OkAB's 05AB1E.

Erik the Outgolfer
sumber
1

Excel VBA, 78 byte

Fungsi anonim yang mengambil input dari kisaran [A1:G1]dan keluaran ke jendela langsung VBE.

[A2:G999]="=A1-(COLUMN()+8*ROW()-14)":[H:H]="=-(MIN(A1:G1)<0)":?998+[Sum(H:H)]
Taylor Scott
sumber
1

Arang , 21 byte

I⌊EA÷⁻X⁺X⊖κ²×¹⁶ι·⁵⊖κ⁸

Cobalah online! Tautan adalah untuk mengucapkan versi kode. Penjelasan: Langsung menghitung jumlah pelangi yang mungkin dengan setiap warna dengan formula yang saya peroleh sendiri-sendiri tetapi ternyata sama dengan formula @ TField.

   A                   Input array
  E                     Map over values
          κ             Current index
         ⊖              Decrement
        X  ²            Square
               ι        Current index
            ×¹⁶         Multiply by 16
       ⁺                Add
      X         ·⁵      Square root
                   κ    Current index
                  ⊖     Decrement
     ⁻                  Subtract
    ÷               ⁸   Integer divide by 8
 ⌊                      Take the maximum
I                       Cast to string
                        Implicitly print
Neil
sumber
1

Jelly , 14 byte

Ini sulit!

Ṃ+9s8Ṗ‘+\>Ż§ỊS

Tautan monadik yang menerima daftar tujuh bilangan bulat yang menghasilkan bilangan bulat, jumlah pelangi yang mungkin.

Cobalah online! Atau lihat test-suite .

Bagaimana?

Sayangnya setiap metode naif tampaknya mengambil 16 byte, salah satu metode tersebut adalah Ṃɓ_J×¥H÷‘H<¬Ȧð€S, namun ternyata metode yang digunakan di sini jauh lebih efisien dan juga lebih pendek!

Metode ini membangun lebih dari cukup tumpukan pelangi saat jumlah partikel, termasuk pita ultra-violet , dan menambahkan 1 untuk setiap tumpukan yang mungkin.

Tes untuk itu menjadi mungkin adalah untuk memeriksa bahwa hanya ada satu band TIDAK mungkin mengingat kita membutuhkan beberapa partikel band ultra-violet tetapi diberikan nol.

Ṃ+9s8Ṗ‘+\>Ż§ỊS - Link list of integers    e.g. [0,0,0,0,0,0,0]        or [17,20,18,33,24,29,41]
Ṃ              - minimum                       0                         17
 +9            - add nine                      9                         26
   s8          - split into eights             [[1,2,3,4,5,6,7,8],[9]]   [[1,2,3,4,5,6,7,8],[9,10,11,12,13,14,15,16],[17,18,19,20,21,22,23,24],[25,26]]
     Ṗ         - discard the rightmost         [[1,2,3,4,5,6,7,8]]       [[1,2,3,4,5,6,7,8],[9,10,11,12,13,14,15,16],[17,18,19,20,21,22,23,24]]
      ‘        - increment (vectorises)        [[2,3,4,5,6,7,8,9]]       [[2,3,4,5,6,7,8,9],[10,11,12,13,14,15,16,17],[18,19,20,21,22,23,24,25]]
               -   (single rainbow counts, including ultra-violet bands, ready to stack)
       +\      - cumulative addition           [[2,3,4,5,6,7,8,9]]       [[2,3,4,5,6,7,8,9],[12,14,16,18,20,22,24,26],[30,33,36,39,42,45,48,51]]
               -   (stacked rainbow counts, including ultra-violet bands)
          Ż    - zero concatenate              [0,0,0,0,0,0,0,0]         [0,17,20,18,33,24,29,41]
               -   (we got given zero ultra-violet band particles!)
         >     - greater than? (vectorises)    [[1,1,1,1,1,1,1,1]]       [[1,0,0,0,0,0,0,0],[1,0,0,0,0,0,0,0],[1,1,1,1,1,1,1,1]]
               -   (always a leading 1 - never enough particles for the ultra-violet band)
           §   - sum each                      [8]                       [1,1,8]
               -   (how many bands we failed to build for each sacked rainbow?)
            Ị  - insignificant? (abs(X)<=1?)   [0]                       [1,1,0]
               -   (1 if we only failed to build an ultra-violet band for each sacked rainbow, 0 otherwise)
             S - sum                           0                         2
               -   (the number of rainbows we can stack, given we don't see ultra-violet!)
Jonathan Allan
sumber
Saya merasa Anda, itu pasti terlalu sulit bagi saya untuk memeras algoritma Okx dalam 18 byte ...
Erik the Outgolfer
Juga, ide cerdas dengan §ỊS!
Erik the Outgolfer
1

05AB1E , 14 byte

žv*āÍn+tā-Ì8÷ß

Cobalah online!

n

Algoritma Pyth ⟶ Algoritma 05AB1E

Ada banyak metode yang bisa dicoba untuk menyelesaikan tantangan ini di 05AB1E, jadi saya mencoba beberapa dari mereka dan ini ternyata yang terpendek. Mengadaptasi formula yang disebutkan di atas dari jawaban Pyth saya, mengingat bahwa 05AB1E menggunakan pengindeksan 1, kita dapat membangun fungsi kita sebagai berikut:

C(n,i)=n(i+2)+4n(n1)

Ii

4n2+n(i2)Ii=0

Perhatikan bahwa kesetaraan ini tidak tepat (tapi saya saat ini tidak tahu cara untuk menyatakan ini secara lebih formal) dan bahwa solusi untuk persamaan ini akan menghasilkan angka floating-point, tapi kami memperbaikinya dengan menggunakan pembagian lantai daripada pembagian yang tepat kemudian. Bagaimanapun, untuk melanjutkan argumen kami, sebagian besar dari Anda mungkin sangat akrab dengan solusi dari persamaan seperti itu , jadi di sini kita memilikinya:

n1,2=2i±(i2)2+16Ii8

Ii(i2)2+16Iii22ii+2=42ii22i2+i=4n

n=2+(i2)2+16Iii8

Persisnya hubungan yang diterapkan oleh jawaban ini.

Tuan Xcoder
sumber
1

C ++, 127 125 byte

Dicukur 2 byte berkat Kevin Cruijssen.

#include<cmath>
int f(int x[7]){size_t o=-1;for(int c=0,q;c<7;c++,o=o>q?q:o)q=(std::sqrt(--c*c-c+16*x[++c])-c+1)/8;return o;}

Cobalah online!

Fungsi mengambil array C-style dari tujuh int dan mengembalikan sebuah int.

c0c6n(n1)yc(n)=(c+3)+8(n1)nYc(n)=k=1nyc(k)=n(c+3)+8n(n1)2xcYc(n)xcn:

n(c1)+(c1)2+16xc8

xc

Penjelasan:

#include <cmath> // for sqrt

int f (int x[7])
{
     // Note that o is unsigned so it will initially compare greater than any int
     size_t o = -1;
     // Iterate over the array
     for (int c = 0; c < 7; c++)
     {
         // calculate the bound
         int q = c - 1;
         q = (std::sqrt (q * q + 16 * x[c]) - q) / 8;

         // if it is less than previously found - store it
         o = o > q ? q : o;
     }
     return o;
 }
Max Yekhlakov
sumber
Halo, selamat datang di PPCG! Aku tidak tahu C ++ terlalu baik, tapi aku cukup yakin Anda dapat golf bagian ini: for(int c=0;c<7;c++){int q=c-1;q=(std::sqrt(q*q+16*x[c])-q)/8;o=o>q?q:o;}untuk ini: for(int c=0,q;c<7;c++,o=o>q?q:o)q=(std::sqrt(--c*c-c+16*x[++c]))/8;. Juga, bisakah Anda memberikan tautan TIO dengan kode uji?
Kevin Cruijssen
@KevinCruijssen Terima kasih!
Max Yekhlakov