Codegolf Rainbow: Spaß mit Integer-Arrays

12

Einführung:

Bildbeschreibung hier eingeben(Quelle: Wikipedia )
Wenn wir einen Regenbogen betrachten, hat er immer die Farben von oben nach unten:
Rot; Orange; Gelb; Grün; Blau; Indigo; violett

Wenn wir uns diese einzelnen Ringe ansehen, ist der rote Ring natürlich größer als der violette Ring.
Darüber hinaus ist es auch möglich, zwei oder sogar drei Regenbogen gleichzeitig zu haben.

All dies oben kombiniert wird in dieser Herausforderung verwendet:

Herausforderung:

Ausgehend von einer Liste von Ganzzahlen der exakten Größe 7, wobei jeder Wert die Farbpartikel angibt, die zur Bildung von Regenbögen zur Verfügung stehen (wobei der größte Index Rot und der kleinste Index Violett angibt), geben Sie die Anzahl der Regenbögen aus, die gebildet werden können.

Ein einzelner Ganzzahl-Regenbogen muss mindestens 3x Violett, 4x Indigo, 5x Blau, 6x Grün, 7x Gelb, 8x Orange, 9x Rot haben. Ein zweiter Regenbogen darüber ist sogar größer als der rote Ring des ersten Regenbogens (einschließlich eines Zwischenraums zwischen ihnen), sodass mindestens 11x Violett, 12x Indigo, 13x Blau, 14x Grün, 15x Gelb, 16x Orange benötigt werden , 17x rot zusätzlich zu dem, was der erste Regenbogen benutzt. Der dritte Regenbogen startet wieder bei 19x Violett.

Beispiel:

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

Warum? Wir haben 15x Violett und wir brauchen mindestens 3 + 11 = 14 für zwei Regenbogen. Wir haben 20 Indigos und wir brauchen mindestens 4 + 12 = 16 für zwei Regenbogen. Wir haben genug Farben für zwei Regenbögen, aber nicht genug, um drei Regenbögen zu formen. Die Ausgabe ist also 2.

Herausforderungsregeln:

  • Die Ganzzahlen im Input-Array sind garantiert nicht negativ ( >= 0).
  • Die Eingabeliste hat garantiert die Größe 7 genau.
  • Wenn sich keine Regenbogen bilden können, geben wir aus 0.
  • Das Eingabe- und Ausgabeformat ist flexibel. Kann eine Liste oder ein Array von Dezimalzahlen sein, kann aus STDIN entnommen werden. Die Ausgabe kann eine Rückgabe einer Funktion in einem beliebigen sinnvollen Ausgabetyp sein oder direkt an STDOUT gesendet werden.

Mindestanzahl der Farben für die nAnzahl der Regenbogen:

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

Allgemeine Regeln:

  • Das ist , also gewinnt die kürzeste Antwort in Bytes.
    Lassen Sie sich von Code-Golf-Sprachen nicht davon abhalten, Antworten mit Nicht-Codegolf-Sprachen zu veröffentlichen. Versuchen Sie, für jede Programmiersprache eine möglichst kurze Antwort zu finden.
  • Für Ihre Antwort gelten Standardregeln. Daher dürfen Sie STDIN / STDOUT, Funktionen / Methoden mit den richtigen Parametern und vollständige Programme vom Rückgabetyp verwenden. Ihr Anruf.
  • Standardlücken sind verboten.
  • Fügen Sie nach Möglichkeit einen Link mit einem Test für Ihren Code hinzu.
  • Es wird außerdem dringend empfohlen, eine Erklärung für Ihre Antwort hinzuzufügen.

Testfälle:

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
quelle
Der 0,0,0,0,0,0,0Rand-Fall aber :( (es passt nicht mit der 1-Gap-Logik)
Jonathan Allan

Antworten:

8

Pyth , 14 Bytes

thS.ef<b*+tkyy

Testsuite!

Wie?

Algortihm

Lassen Sie uns zunächst die Formel ableiten, auf der diese Antwort basiert. Nennen wir die Funktion, die die erforderliche Menge an Farbpartikeln ergibt , wobei n die Anzahl der Schichten und i der Index der Farbe ist, basierend auf 0. Zunächst stellen wir fest, dass wir nur für die n- te Schicht ( in diesem Fall ist n 1-indiziert) L ( n , i ) = i + 3 + 8 ( n - 1 ) Farbpartikel benötigen . Vor diesem Hintergrund fassen wir die Ergebnisse der einzelnen Schritte zusammenC(n,i)ninthnL(n,i)=i+3+8(n1) für jede Schicht k :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)

Daher wissen wir jetzt, dass die maximale Anzahl möglicher Schichten, nennen wir es , die Ungleichung C ( k , i ) I i erfüllen muss , wobei I i das i- te Element der Eingabeliste ist.kC(k,i)IiIiith

Implementierung

Dies implementiert die Funktion und iteriert ( ) über die Eingabeliste, wobei k der Index (0-basiert) und b das Element ist. Für jeden Wert sucht das Programm die erste positive ganze Zahl T, für die b < C ( T , i ) ist (die logische Negation von C ( T , i ) b , die Bedingung, die wir zuvor hergeleitet haben), und findet dann das minimale Ergebnis und die minimalen Dekremente es. Auf diese Weise, statt für die höchste ganze Zahl von sucht , die tut eine Bedingung erfüllen, die wir für die niedrigsten suchen , die nicht der Fall istC.ekbTb<C(T,i)C(T,i)b und subtrahiere eins davon, um den Versatz von 1 auszugleichen.

Mr. Xcoder
quelle
3

Python 2 , 64 61 Bytes

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

Probieren Sie es online!


Jede Farbe des Regenbogens wird (3+i)+n*8für Ebene nund Farbe verwendet i(0 = Violett usw.)

Die Summe x Schichten ist daher: (3*i)*x + 8*x*(x+1).

Wir lösen einfach nach n und nehmen den Minimalwert.


Gerettet:

  • -3 Bytes dank ovs
TFeld
quelle
2
Ah, jetzt bekomme ich diese Antwort ...
Jonathan Frech
1
61 Bytes
Ovs
@ovs, Danke :)
TFeld
3

05AB1E , 18 17 16 Bytes

-1 Byte dank Magic Octopus Urn

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

Probieren Sie es online!

Die für n Regenbogen benötigte Farbmenge beträgt n (4n + [-1, 0, 1, 2, 3, 4, 5]) .

Okx
quelle
[ND4*6Ý<+*¹›1å#Nfunktioniert, aber ich weiß nicht warum. -1 Byte obwohl.
Magic Octopus Urn
@MagicOctopusUrn Danke! Das verwendet nur den Schleifenindex anstelle der Zählervariable.
Okx
Scheint komisch, dass ich es nicht tun N>muss, weil du es ¾>vorher getan hast .
Magic Octopus Urn
@MagicOctopusUrn Mit dem Befehl zum Erhöhen der Zählervariable wird die Zählervariable nicht verschoben.
Okx
2

JavaScript (ES6), 49 Byte

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

Probieren Sie es online!

Wie?

P(n,k)nk ten Farbe beträgt:

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

nvkP(n,k)

Zum Golfen beginnen wir jedoch mit n === undefinednegativen Werten von ndanach und verwenden diese . Die erste Iteration ist immer erfolgreich, da die rechte Seite der Ungleichung zu bewertet wird NaN. Daher ist der erste aussagekräftige Test der zweite mit n == -1.

Arnauld
quelle
1

Excel VBA, 78 Bytes

Anonyme Funktion, die Eingaben aus dem Bereich von [A1:G1]und Ausgaben in das VBE-Direktfenster übernimmt .

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

Holzkohle , 21 Bytes

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

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Erklärung: Berechnet direkt die Anzahl der Regenbögen, die mit jeder Farbe möglich sind, mit einer Formel, die ich unabhängig abgeleitet habe, die jedoch mit der @ TField-Formel übereinstimmt.

   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
quelle
1

Gelee , 14 Bytes

Das war schwer!

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

Ein monadischer Link, der eine Liste mit sieben ganzen Zahlen akzeptiert, die eine ganze Zahl ergibt, die Anzahl der möglichen Regenbogen.

Probieren Sie es online! Oder sehen Sie sich die Testsuite an .

Wie?

Leider scheint jede naive Methode 16 Bytes zu benötigen, eine solche Methode ist Ṃɓ_J×¥H÷‘H<¬Ȧð€Sjedoch, wie sich herausstellt, die hier verwendete Methode ist sowohl effizienter als auch kürzer!

Diese Methode baut mehr als genug Regenbogenstapel auf, da die Partikelanzahl, einschließlich der ultravioletten Bänder , hoch ist, und addiert 1 für jeden Stapel, der möglich ist.

Der Test für die Möglichkeit besteht darin, zu überprüfen, dass es nur eine einzige Bande gibt, die NICHT möglich ist, vorausgesetzt, wir benötigen einige ultraviolette Bandenpartikel, die jedoch mit Null versehen wurden.

Ṃ+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
quelle
Ich fühle dich, es war definitiv zu schwer für mich, Okx 'Algorithmus in 18 Bytes zu quetschen ...
Erik the Outgolfer
Auch kluge Idee mit dem §ỊS!
Erik der Outgolfer
1

05AB1E , 14 Bytes

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

Probieren Sie es online!

Eine geschlossene Lösung, die keine zusätzliche Schleife anstelle der Karte erfordert. Dies funktioniert, indem die Formel meiner Pyth-Antwort an die Indizierungskonvention von 05AB1E angepasst und dann aufgelöst wirdn, was dem Algorithmus von TFeld entspricht .

Pyth-Algorithmus ⟶ 05AB1E Algorithmus

Es gibt viele Methoden, mit denen man diese Herausforderung in 05AB1E lösen kann. Deshalb habe ich ein paar ausprobiert, und dies stellte sich als die kürzeste heraus. Wenn wir die oben genannte Formel aus meiner Pyth-Antwort übernehmen und berücksichtigen, dass 05AB1E die 1-Indizierung verwendet, können wir unsere Funktion wie folgt aufbauen:

C(n,ich)=n(ich+2)+4n(n-1)

Gleichsetzen mit dem Element der Eingabe (ich) am Index ich und wenn wir es in standardmäßiger (quadratischer) Polynomnotation schreiben, haben wir:

4n2+n(ich-2)-ichich=0

Beachten Sie, dass diese Gleichheit nicht genau ist (aber ich kenne derzeit keine Möglichkeit, dies formeller zu formulieren) und dass die Lösungen für diese Gleichung Gleitkommazahlen ergeben. Wir beheben dies jedoch, indem wir eine Bodenteilung anstelle einer präzisen Unterteilung verwenden später. Wie auch immer, mit unserem Argumente weiterhin auf, die meisten von Ihnen sind wahrscheinlich sehr vertraut mit den Lösungen von solchen Gleichung , also hier haben wir es:

n1,2=2-ich±(ich-2)2+16ichich8

Wie ichich ist immer positiv, (ich-2)2+16ichichich-2, also die "-"case macht nicht viel sinn, denn das wäre auch nicht 2-ich-ich+2=4-2ich, das ist negativ für ich2 oder 2-ich-2+ich=4, was konstant ist. Daraus können wir schließenn wird gegeben durch:

n=2+(ich-2)2+16ichich-ich8

Welches ist genau die Beziehung, die diese Antwort implementiert.

Mr. Xcoder
quelle
1

C ++, 127 125 Bytes

Kevin Cruijssen hat 2 Bytes gespart.

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

Probieren Sie es online!

Die Funktion verwendet ein Array im C-Stil mit sieben Zoll und gibt ein int zurück.

Der Algorithmus ist ziemlich unkompliziert (und wurde bereits einige Male beschrieben, daher folgt hier eine weitere Beschreibung, hauptsächlich für mein eigenes Sehvergnügen). Lassenc sei der Farbindex (0c6), so dass sich die erforderliche Anzahl von Partikeln bildet n-th (n1) Regenbogenteil dieser Farbe ist yc(n)=(c+3)+8(n-1)und die Gesamtmenge der zu bildenden Teilchen n Regenbogenteile der Farbe sind dann Y.c(n)=k=1nyc(k)=n(c+3)+8n(n-1)2. Jetzt haben wir ein UngleichungssystemxcY.c(n) (wo xc ist die Elemente des Eingabe-Arrays), die uns eine Reihe von Obergrenzen auf gibt n:

n-(c-1)+(c-1)2+16xc8
.

Was übrig bleibt, wird einfach durchlaufen xc und finde das Minimum.

Erläuterung:

#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
quelle
Hallo, willkommen bei PPCG! Ich weiß nicht , C ++ zu gut, aber ich bin ziemlich sicher , können Sie Golf dieses Teil: 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;}dazu: for(int c=0,q;c<7;c++,o=o>q?q:o)q=(std::sqrt(--c*c-c+16*x[++c]))/8;. Könnten Sie vielleicht auch einen TIO-Link mit Testcode bereitstellen ?
Kevin Cruijssen
@ KevinCruijssen Vielen Dank!
Max Yekhlakov