Machen Sie die größten und kleinsten Zahlen

13

Inspiriert von diesem Beitrag über Rätsel. Die Spoiler für dieses Rätsel finden Sie weiter unten.

Wenn Sie drei positive Ganzzahlen als Eingabe haben (x, y, z), konstruieren Sie den Einschlussbereich [x, y], verknüpfen Sie diesen Bereich und entfernen Sie dann znicht unbedingt aufeinanderfolgende Ziffern, um die größtmöglichen und kleinsten positiven Ganzzahlen zu erhalten. Führende Nullen sind nicht zulässig (dh die Zahlen müssen mit beginnen [1-9]). Gib diese beiden Zahlen in beliebiger Reihenfolge aus.

Für das Beispiel aus der Rätselhafte Post, für die Eingabe (1, 100, 100)möglich , die größte Zahl ist 99999785960616263646566676869707172737475767778798081828384858687888990919293949596979899100,
und die kleinste Zahl ist 10000012340616263646566676869707172737475767778798081828384858687888990919293949596979899100, im
Anschluss an dem unten Logik von JAFE der Antwort gepostet dort:

  • Wir können die Länge der Zahl nicht beeinflussen (es gibt eine feste Anzahl von Stellen). Um den Wert zu maximieren, nehmen wir die maximale erste Stelle, dann die zweite Stelle usw.
  • Entfernen Sie die 84 ersten Nicht-Neunen (16 Stellen müssen noch entfernt werden): 999995051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
  • Die größte Zahl innerhalb der nächsten 17 Ziffern ist 7, daher kann die nächste Ziffer in der Antwort höchstens 7 sein (wir können nicht mehr als 16 Ziffern entfernen). Entfernen Sie also 15 Nicht-7-Zeichen ... (1 Ziffer muss noch entfernt werden):999997585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
  • Von hier aus kann die nächste Ziffer höchstens 8 sein, entfernen Sie also eine Nicht-8 aus der Mitte: 99999785960616263646566676869707172737475767778798081828384858687888990919293949596979899100
  • Ähnliche Logik, aber umgekehrt (dh wir wollen führende 1s anstelle von führenden 9s) für die kleinste Zahl.

Hier ist ein kleines Beispiel: (1, 10, 5).

Wir konstruieren den Bereich 12345678910und bestimmen, welche 5Ziffern wir entfernen können, wobei die größtmögliche Anzahl übrig bleibt. Dies bedeutet natürlich, dass wir die führende Ziffer maximieren möchten, da wir die Länge der Ausgabe nicht beeinflussen können. Wenn wir also entfernen 12345, bleibt uns nichts anderes übrig 678910, und das ist das größte, was wir machen können. Das kleinste zu machen ist ein bisschen schwieriger, da wir stattdessen Zahlen aus der Mitte herauszupfen können, um 123410das kleinstmögliche zu erhalten.

Denn (20, 25, 11)das Ergebnis ist eher langweilig, als 5und 1.

Schließlich, um Antworten auszuschließen, die führende Nullen versuchen, (9, 11, 3)gibt 91011das wiederum 91und 10als die größten und kleinsten.

I / O und Regeln

  • Wenn es einfacher / kürzer ist, können Sie zwei Programme / Funktionen codieren - eines für das größte und eines für das kleinste. In diesem Fall ist Ihre Punktzahl die Summe beider Teile.
  • Die Eingabe und Ausgabe kann durch jede bequeme Methode erfolgen .
  • Die Eingabe kann davon ausgegangen werden in Ihrer Sprache nativen Nummerntyp passen, jedoch weder die verkettete Nummer noch der Ausgang kann so tun , angenommen werden.
  • Es ist entweder ein vollständiges Programm oder eine Funktion zulässig. Bei einer Funktion können Sie die Ausgabe zurückgeben, anstatt sie zu drucken.
  • Standardlücken sind verboten.
  • Dies ist daher gelten alle üblichen Golfregeln, und der kürzeste Code (in Byte) gewinnt.
AdmBorkBork
quelle
eine Ziffernliste als Ausgabe zulässig?
Rod
Ein Testfall, der ein falsches Minimum ergeben würde, wenn man die mit führenden Nullen auswertet, kann sich lohnen - ich denke, 9, 11, 3würde es tun.
Jonathan Allan
@Rod Ja, eine Liste mit Ziffern ist für die Ausgabe ausreichend.
AdmBorkBork
@ Rod Ich weiß nicht, wovon du sprichst, ich habe oben deutlich "output" eingegeben. ;-)
AdmBorkBork
@ JonathanAllan Guter Anruf. Hinzugefügt.
AdmBorkBork

Antworten:

5

Haskell , 162 Bytes

l=length
((m,f)%n)s|n>=l s=[]|n>0,(p,c:r)<-span(/=m(f$take(n+1)s))s=c:((m,id)%(n-l p)$r)|1>0=s
(x#y)z=[p%z$show=<<[x..y]|p<-[(maximum,id),(minimum,filter(>'0'))]]

Probieren Sie es online!

Verwendet den von jafe beschriebenen Algorithmus. Es könnte kürzer sein, eine weniger effiziente Methode zu verwenden, aber das Schreiben hat mehr Spaß gemacht :)

Die %Operation benötigt 4 Argumente (eigentlich 3, aber was auch immer): mDiese Funktion wählt das "optimale" Element aus einer Liste aus (entweder maximumoder minimumje nachdem, was wir wollen). fdas ist eine "Filter" -Funktion; ndie Anzahl der Stellen, die noch zu löschen sind; und sdie Zeichenfolge. Zuerst prüfen wir, ob n der Anzahl der in der Zeichenfolge verbleibenden Ziffern entspricht (ich habe es >=aus Sicherheitsgründen verwendet) und lassen den Rest fallen, sfalls dies der Fall ist . Andernfalls prüfen wir, ob wir noch Ziffern ( n>0) löschen müssen, und zerlegen dann spanunsere Zeichenfolge in drei Teile: pdie zu löschenden Ziffern, cdie optimal erreichbare Ziffer undrdie verbleibende Zeichenfolge. Wir tun dies, indem wir ein Prädikat übergeben, das die Gleichheit mit unserer optimalen Ziffer vergleicht. Um diese Ziffer zu finden, nehmen wir die ersten n+1Ziffern der Zeichenkette, filtern sie und übergeben sie dann an unsere "Auswahl" -Funktion. Jetzt geben wir einfach unsere optimale Ziffer und wiederholen sie, indem wir die Länge von p(die Anzahl der gesunkenen Ziffern) von subtrahieren n. Beachten Sie, dass wir unsere Filterfunktion nicht an den rekursiven Aufruf übergeben, sondern durch ersetzen id. Dies liegt daran, dass der Filter nur dazu dient, die Auswahl von führenden Nullen zu vermeiden, minimumwenn dies nur für die erste Iteration relevant ist. Danach brauchen wir keinen Filter mehr.

%ist wirklich nur eine Hilfsfunktion für #die unsere „echte“ Funktion ist, nehmen x, yund z. Wir verwenden ein Listenverständnis, um Wiederholungen zu vermeiden. Wir iterieren über unsere Funktionstupel und übergeben sie %zusammen mit zund der verketteten Zeichenfolge. Diese Zeichenfolge wird mit dem Magic-Monad-Operator erstellt (=<<), der in diesem Zusammenhang wie folgt funktioniert concatMap.

user1472751
quelle
3

Gelee , 17 Bytes

r/VDœcL_¥¥ḷ/ƇVṢ.ị

Probieren Sie es online!

Berechnet alle Möglichkeiten und behält dann die größten und kleinsten bei.

Linkes Argument: x,yum den Bereich zu konstruieren. Richtiges Argument: zZu entfernende Ziffern.

r/VDœcL_¥¥ḷ/ƇVṢ.ị
r/                 Inclusive range from x to y
  V                Concatenate the digits together
   D               Get the resulting digits
         ¥         Dyad:
        ¥            Dyad:
      L                Length of the list of digits in the concatenated number.
       _               Subtract the number of digits to be removed.
    œc               Combinations without replacement. (remove z digits)
            Ƈ      Keep lists of digits that:
          ḷ/       have a positive first element (no leading zeros).
             V     Combine digits into integers. (vectorizes to ldepth 1)
              Ṣ    Sort the numbers
               .ị  Indexes at value 0.5 which yields the first and last elements.
dylnan
quelle
2

Python 2 , 143 Bytes

import itertools
s,e,r=input()
l=''.join(map(str,range(s,e+1)))
L=[i for i in itertools.combinations(l,len(l)-r)if'0'<i[0]]
print min(L),max(L)

Probieren Sie es online!

Dies funktioniert, indem alle Kombinationen der Zielgröße berechnet werden (die Elementreihenfolge bleibt erhalten) und die kleinsten / größten Zahlen daraus erhalten werden

Stange
quelle
Oh ... ich denke das funktioniert lol. Ich habe mich sehr bemüht, ein Programm zu entwickeln, das es tatsächlich deterministisch berechnet.
Don Thousand
@RushabhMehta Brute Force-Berechnungen sind immer noch deterministisch, nur langsamer.
Dylnan
2

Kohle , 56 Bytes oder 21 + 46 35 = 67 56 Bytes

≔⪫…·NNωθFN≔⌈EθΦθ⁻λνθθ

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Erläuterung:

≔⪫…·NNωθ

Geben Sie xund ein y, erstellen Sie einen Inklusivbereich und fügen Sie die Zahlen zu einer Zeichenfolge zusammen.

FN

Schleife einmal für jede zu entfernende Ziffer.

≔⌈EθΦθ⁻λνθ

Erstellen Sie eine Liste von Zeichenfolgen, indem Sie jedes mögliche Zeichen aus der aktuellen Zeichenfolge entfernen und das Maximum verwenden.

θ

Drucken Sie das Ergebnis.

≔⪫…·NNωθF⊕N⊞υωΦθ∧⁼ι⌊Φ✂θκLυ¹∨κIλ⊞Oυω

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Erläuterung:

≔⪫…·NNωθ

Geben Sie xund ein y, erstellen Sie einen Inklusivbereich und fügen Sie die Zahlen zu einer Zeichenfolge zusammen.

F⊕N⊞υω

Geben Sie es ein zund erhöhen Sie es. Ich erstelle dann eine Liste dieser Länge: Ich muss in der Lage sein, zinnerhalb des folgenden Filters zu inkrementieren , aber nur Befehle dürfen Variablen inkrementieren; Es gibt eine Lücke, PushOperatordie die Länge der Liste erhöht.

 θ                      String of digits
Φ                       Filter over characters
         κ              Current index
          Lυ            Length of list i.e. current `z` value
            ¹           Literal 1
       ✂θ               Slice string of digits
      Φ                 Filter over characters
              κ         Outer index
               Iλ       Cast inner character to number
             ∨          Logical OR
     ⌊                  Minimum
   ⁼ι                   Equals the outer character
  ∧              ⊞Oυω   And also push to list i.e. increment `z`
                        Implicitly print

Filtern Sie nach den Zeichen, die gesucht werden sollen, indem Sie sicherstellen, dass der aufteilbare Bereich keine niedrigeren Zeichen enthält. Die Region beginnt mit den ersten z+1Zeichen (da das erste Zeichen zbei Bedarf entfernt werden kann) und erhöht den Endpunkt für jedes Zeichen, das beibehalten wird. Es wird darauf geachtet, für das erste Zeichen keine Null zu wählen.

Der schnellere Algorithmus ist 30 Byte, wenn er zur Berechnung der größtmöglichen Anzahl verwendet wird:

≔⪫…·NNωθF⊕N⊞υωΦθ∧⁼ι⌈✂θκLυ¹⊞Oυω

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Bearbeiten: Ich habe seitdem in der Lage, die beiden oben genannten zu einer zweiten 56-Byte-Lösung zu kombinieren, die beide Ergebnisse generiert:

≔⪫…·NNωθF⊕N⊞υω≔⮌υη⟦Φθ∧⁼ι⌈✂θκLυ¹⊞OυωΦθ∧⁼ι⌊Φ✂θκLη¹∨κIλ⊞Oηω

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Erläuterung:

≔⪫…·NNωθ

Generieren Sie die Anfangszeichenfolge.

F⊕N⊞υω

Stellen Sie z+1die Länge der Liste dar.

≔⮌υη

Kehren Sie die Liste um, klonen Sie sie und speichern Sie das Ergebnis.

Drucken Sie die beiden Ergebnisse in separaten Zeilen. (Eine andere Möglichkeit besteht darin, die Ergebnisse mit einem wörtlichen \rZeichen zu trennen .)

Φθ∧⁼ι⌈✂θκLυ¹⊞Oυω

Generieren Sie die größtmögliche Anzahl.

Φθ∧⁼ι⌊Φ✂θκLη¹∨κIλ⊞Oηω

Generieren Sie mithilfe der geklonten Liste die kleinstmögliche Anzahl, um den Überblick zu behalten z.

Neil
quelle
1

Jelly ,  19  18 Bytes

rDẎœcL_⁵Ɗ$ị@Ƈ1ḌṢ.ị

Probieren Sie es online!

Sehr ineffizient, definitiv kein Punkt für das Gehen 1, 100, 100als(19292)=305812874887035355118559193163641366325011573739619723360

Jonathan Allan
quelle
1

05AB1E , 16 Bytes

ŸSDg³-.Æʒ¬Ā}{Ć`‚

Probieren Sie es online!

Vollständiges Programm, Eingaben in dieser Reihenfolge lesen: y, x, z . Gibt eine Liste mit zwei Zeichenlisten aus.

Erläuterung

ŸSDg³-.Æʒ¬Ā}{Ć`‚    Full program. Inputs: y, x, z.
Ÿ                   Inclusive binary range from x to y. Push [x ... y].
 S                  Dump the digits separately in a list.
  Dg                Duplicate, and use the second copy to get its length.
    ³-              Subtract z from the length.
      .Æ            Retrieve all combinations of length - z elements from the digits.
        ʒ  }        Keep only those that...
         ¬Ā         Don't start with a 0 (head, then Python-style boolean).
            {       Sort the remaining elements.
             Ć      Enclose. Pushes list + list[0] (appends its tail to itself)
              `     Dump all elements separately on the stack.
               ,    Pair, to get the last two, min and max (after enclosing)
Mr. Xcoder
quelle
Oh, Ć`‚ist ziemlich schlau, nette Antwort!
Kevin Cruijssen
0

Matlab, 95 Bytes

function[m]=f(s,e,c),a=sprintf('%d',s:e);x=str2num(combnk(a,length(a)-c));m=[min(x),max(x)];end

Probieren Sie es online!

Gibt eine 1x2 Matrix mit min und max zurück.

Wie es funktioniert

% Full code
function[m]=f(s,e,c),a=sprintf('%d',s:e);x=str2num(combnk(a,length(a)-c));m=[min(x),max(x)];end

% The function
function[m]=f(s,e,c),                                                                       end

                     % Creates the range in a single string
                     a=sprintf('%d',s:e);

                                                   % Gets all the combinations
                                                   combnk(a,length(a)-c)

                                         % Converts the string combinations to integers
                                         x=str2num(                     );

                                                                          % Finds min and max
                                                                          m=[min(x),max(x)];
DimChtz
quelle