Die beste Basis ist 10… Lass es uns erreichen!

40

Eingang:

Eine positive ganze Zahl n, die aus Ziffern im Bereich von 0 bis 9 besteht .

Herausforderung:

Wenn d die höchste Ziffer in der ganzen Zahl ist, wird angenommen, dass die Basis der Zahl d + 1 ist . Wenn die Ganzzahl beispielsweise 1256 ist, nehmen Sie an, dass sie zur Basis 7 gehört , wenn sie 10110 ist, dann nehmen Sie an, dass sie zur Basis 2 (binär) gehört, und wenn sie 159 ist, dann ist sie dezimal.

Führen Sie nun die folgenden Schritte aus, bis Sie entweder 1: eine Ganzzahl zur Basis 10 oder 2: eine einstellige Ganzzahl erreichen.

  1. Konvertiere die ganze Zahl von base- (d + 1) zu base-10
  2. Finden Sie die Basis dieser neuen Ganzzahl (wieder base- (d + 1), wobei d die höchste Ziffer in der neuen Zahl ist)
  3. Fahren Sie mit Schritt 1 fort .

Beispiele:

Angenommen, die Eingabe ist n = 413574 . Die höchste Ziffer d = 7 , also ist dies die Basis 8 (oktal). Wandle dies in eine Dezimalzahl um und erhalte 137084 . Die höchste Ziffer d = 8 , das ist also die Basis 9 . Wandle dies in eine Dezimalzahl um und erhalte 83911 . Die höchste Ziffer ist 9 , das ist also eine Dezimalzahl, und wir hören auf. Die Ausgabe soll 83911 sein .

Angenommen, die Eingabe ist n = 13552 . Die höchste Ziffer ist d = 5 , dies ist also die Basis 6 . Wandle dies in eine Dezimalzahl um und erhalte 2156 . Die höchste Ziffer d = 6 , also ist dies die Basis 7 . Wandle dies in eine Dezimalzahl um und erhalte 776 . Die höchste Ziffer ist d = 7 , dies ist also die Basis 8 . Wandle dies in eine Dezimalzahl um und erhalte 510 . Die höchste Ziffer ist d = 5 , dies ist also die Basis 6 . Wandle dies in eine Dezimalzahl um und erhalte 186 . Die höchste Ziffer ist 8 , dies ist also die Basis 9 . Wandle dies in eine Dezimalzahl um und erhalte 159. Die höchste Ziffer ist 9 , das ist also eine Dezimalzahl und wir hören auf. Die Ausgabe soll 159 sein .

Angenommen, die Eingabe ist n = 17 . Dies gibt uns 15 , dann 11 , dann 3 , die wir ausgeben, da es eine einzelne Ziffer ist.


Testfälle:

5
5

17
3

999
999

87654321  (base-9 -> 42374116 in decimal -> base-7 -> 90419978 in decimal) 
9041998

41253  (5505 -> 1265 -> 488 -> 404 -> 104 -> 29)
29

Anmerkungen:

  • Standardregeln für E / A, Lücken usw. Sie können die Eingabe als Zeichenfolge verwenden
  • Erklärungen sind erwünscht
  • Sie können integrierte Base-Conversion-Befehle verwenden
    • Lösungen, die die in der Sprache integrierten Funktionen zur Basiskonvertierung (sofern vorhanden) nicht verwenden, sind willkommen, auch wenn sie viel länger dauern als die offensichtliche Vorgehensweise bei Verwendung integrierter Funktionen.

Anscheinend ist dies OEIS A091047 .

Stewie Griffin
quelle
2
Anscheinend liebe ich Matrizen , also dachte ich, ich mache stattdessen eine Base-Conversion- Challenge.
Stewie Griffin
34
"Die beste Basis ist 10" ... "10" steht in welcher Basis?
Olivier Grégoire
5
@ OlivierGrégoire Das ist das Schlaue ... Egal auf welcher Basis wir landen, es wird immer noch eine gültige Aussage sein!
Stewie Griffin
@StewieGriffin Aber wie liest du das? "10" hat in jeder Basis einen anderen Namen.
user11153
10
Nun, das hängt von der Basis ab ... oder wie Meghan sagen würde: "Es geht nur um diese Basis, 'Über diese Basis, keine Probleme" ;-)
Stewie Griffin

Antworten:

20

Mathematica, 56 Bytes

#//.x_/;(b=Max[d=IntegerDigits@x]+1)<11:>d~FromDigits~b&

Probieren Sie es online! (Verwenden von Mathematik.)

Ich dachte, ich würde nachsehen, wie die Sequenz aussieht:

Bildbeschreibung hier eingeben

Und hier ist eine grafische Darstellung der Anzahl der Schritte, die erforderlich sind, um das Ergebnis zu finden:

Bildbeschreibung hier eingeben

(Klicken Sie hier, um eine größere Version zu erhalten. In der Überarbeitungshistorie werden nur Darstellungen bis n = 1000 angezeigt .)

Sieht aus wie eine sehr interessante Mischung aus großräumiger Struktur und feinräumigem Chaos. Ich frage mich, was mit den größeren Lücken zwischen 30.000 und 60.000 los ist.

Martin Ender
quelle
4
@StewieGriffin sollte auf der linken Seite sein. Die kleinen Lücken sind da, weil die Zahlen, die zu einem Vielfachen einer 9Zehnerpotenz führen, a enthalten , sie sind also bereits in der Basis 10. Aber für 30k und 60k scheint es, dass Zahlen mit einer 8 oder sogar 7 (müssen) check) statt der 9 wird nach höchstens einem schritt immer die basis 10.
Martin Ender
@StewieGriffin Um genau zu sein, alle Zahlen im Bereich [28051, 28888] sind Basis 9 und werden in Zahlen der Form 19xxx übersetzt, wodurch sich diese Lücke so ziemlich verdoppelt.
CMASTER
Ah, verstanden ... :) Für die Aufzeichnung: Ich wusste, warum es Lücken auf der linken Seite von Zehnerpotenzen gab ... Es waren nur die doppelt so großen Lücken, die seltsam waren (warum 30/60 und nicht 20 / 40/50). Ich sehe jetzt allerdings, dass Zahlen im Bereich 28xxx -> 19xxx, aber 38xxx -> 26xxx, nicht 29xxx liegen.
Stewie Griffin
10

Java 8, 172 166 163 152 151 140 138 116 114 99 Bytes

s->{for(Integer b=0;b<10&s.length()>1;s=""+b.valueOf(s,b=s.chars().max().getAsInt()-47));return s;}

Nimmt die Eingabe als String.

-64 Bytes dank @ OlivierGrégoire . Und hier dachte ich, dass meine anfänglichen 172 nicht so schlimm waren ..;)

Probieren Sie es hier aus.

Erläuterung:

s->{                    // Method with String as parameter and return-type
  for(Integer b=0;b<10  //  Loop as long as the largest digit + 1 is not 10
      &s.length()>1;    //  and as long as `s` contains more than 1 digit
    s=""+               //   Replace `s` with the String representation of:
         b.valueOf(s,   //    `s` as a Base-`b` integer
          b=s.chars().max().getAsInt()-47)
                        //     where `b` is the largest digit in the String + 1
  );                    //  End of loop
  return s;             //  Return result-String
}                       // End of method
Kevin Cruijssen
quelle
1
Versprichst du, ruhig zu bleiben? : Ok p ... gehen wir: s->{for(Integer b=0;b<10&s.length()>1;)s=""+b.valueOf(s,b=s.chars().max().getAsInt()-47);return s;}. Außerdem habe ich die meisten meiner Kommentare gelöscht, da sie jetzt völlig irrelevant sind ( bist die Basis, Ihre a; und sist die Nummer, an der wir arbeiten).
Olivier Grégoire
1
Ich habe versucht, dies zu rekursivieren, um einige Bytes mit Integer b;return(b=s.chars().max().getAsInt()-47)>9|s.length()<2?s:c(""+b.valueOf(s,b));(88) zu entfernen , aber ich bin brandneu darin, Golf zu codieren. Das ist ein Schnipsel, oder? Gibt es eine Möglichkeit, dies als Methode zu deklarieren, ohne es hinzufügen zu müssen public String c(String s)?
Lord Farquaad
1
@LordFarquaad Sie brauchen das nicht public, aber ich befürchte, Sie müssen es tatsächlich String c(String s){}für rekursive Aufrufe verwenden, auch in Java 8. Wenn Sie ein Lambda mit java.util.function.Function<String, String> c=s->{Integer b;return(b=s.chars().max().getAsInt()-47)>9|s.length()<2?s:c‌.apply​(""+b.valueOf(s,b));}oder eine Schnittstelle interface N{String c(String s);}N n = s->{Integer b;return(b=s.chars().max().getAsInt()-47)>9|s.length()<2?s:n.c‌​(""+b.valueOf(s,b));};damit erstellen, wird im Initialisierer eine " Selbstreferenz " angezeigt Fehler "in beiden Fällen. Trotzdem sehr nette Herangehensweise!
Kevin Cruijssen
Ah, ich glaube, ich habe es dann ein paar Bytes entgolfet. Aber danke für die Hilfe! Ich werde das im Hinterkopf behalten.
Lord Farquaad
8

Pyth, 9 Bytes

ui`GhseS`

Testsuite

Erläuterung:

ui`GhseS`
ui`GhseS`GQ    Implicit variable introduction
u         Q    Repeatedly apply the following function until the value repeats,
               starting with Q, the input.
        `G     Convert the working value to a string.
      eS       Take its maximum.
     s         Convert to an integer.
    h          Add one.
 i`G           Convert the working value to that base
isaacg
quelle
Es ist ein bisschen seltsam, wie Sie ein Lambda mit zwei Variablen verwendeten, das schließlich eine Variable verwendete ... und dabei keine Fehler verursachte. Oh, die beiden Variablen sind Qund Q, ich verstehe.
Erik der Outgolfer
@EriktheOutgolfer Nicht genau. uOhne die dritte Eingabe wird sie bis zur Wiederholung angewendet, während bei einer dritten Eingabe eine feste Anzahl von Malen angewendet wird. uLambda hat Gund H, aber Sie müssen nicht verwenden H.
Isaacg
Eigentlich hätte das Ersetzen Gmit Hdas gleiche Ergebnis gehabt ... BTW implizite Variable ist G?
Erik der Outgolfer
@EriktheOutgolfer Die implizite Variable lautet Gyes. Hzählt bei jeder Iteration von 0 aufwärts, es ist also völlig anders. Ich bin mir nicht sicher, wovon du sprichst. Hier ist ein Beispielprogramm, das Ihnen zeigt, was los ist: pyth.herokuapp.com/…
isaacg
6

JavaScript (ES6), 63 57 54 53 Bytes

f=a=>a>9&(b=Math.max(...a+""))<9?f(parseInt(a,b+1)):a

8 Bytes gespart dank Shaggy und Dom Hastings

f=a=>a>9&(b=Math.max(...a+""))<9?f(parseInt(a,b+1)):a;

console.log(f("413574"))

Tom
quelle
Schlagen Sie mich zu. Ich denke, Sie könnten ein paar Bytes sparen +a>9||b<9und das Ternär umkehren.
Shaggy
1
@ Shaggy bearbeiten: Ich bin dumm
Tom
1
Sei nicht so hart zu dir, Tom! Du bist nicht dumm, aber definitiv nicht so schlau wie @Shaggy!
Stewie Griffin
1
Alternative für 55 Bytesf=n=>n>9&&(k=Math.max(...n+"")+1)<10?f(parseInt(n,k)):n
Dom Hastings
@DomHastings Danke für die Verbesserungen! :)
Tom
5

Python 3 , 91 78 76 75 73 Bytes

@Emigna 5 Bytes rasiert. @FelipeNardiBatista 1 Byte gespeichert. @ RomanGräf 2 Bytes gespart

i=input()
while'9'>max(i)and~-len(i):i=str(int(i,int(max(i))+1))
print(i)

Probieren Sie es online!


Erläuterung

i=input()                                  - takes input and assigns it to a variable i
while '9'>max(i)and~-len(i):               - repeatedly checks if the number is still base-9 or lower and has a length greater than 1
    i=str(...)                             - assigns i to the string representation of ...
          int(i,int(max(i))+1)             - converts the current number to the real base 10 and loops back again
print(i)                                   - prints the mutated i
Mr. Xcoder
quelle
5

05AB1E , 10 5 Bytes

5 Bytes gespart dank Magic Octopus Urn

F§Z>ö

Da dies bei großen Eingaben sehr schnell langsam wird, lasse ich die alte, viel schnellere Version hier zum Testen. Der Algorithmus ist derselbe, nur die Anzahl der Iterationen unterscheidet sich.

[©Z>öD®Q#§

Probieren Sie es online!

Erläuterung

[             # start a loop
 ©            # store a copy of the current value in the register
  Z>          # get the maximum (digit) and increment
    ö         # convert the current value to base-10 from this base
     D        # duplicate
      ®Q#     # break loop if the new value is the same as the stored value
         §    # convert to string (to prevent Z from taking the maximum int on the stack)
Emigna
quelle
Kannst du nicht auch einfach benutzen тFZ>ö§? Sehen Sie, wie die Anzahl der Iterationen ( wie hier zu sehen ) zu Plateau scheint? Wenn Sie technische erhalten möchten, ist die Geschwindigkeit , die Iterationen steigen wahrscheinlich logarithmisch ... So einfach so etwas wie verwenden: DFZ>ö§Staat und es wird nicht für große laufen n. ODER vielleicht sogar: T.n>FZ>ö§um die Anzahl der Iterationen direkt zu berechnen als log_10(n).
Magic Octopus Urn
@MagicOctopusUrn: Ja, jetzt, da Sie es erwähnen, da die Sequenz definitiv langsamer als linear zu F§Z>ösein scheint, sollten Sie den Trick machen.
Emigna
Ich denke, Sie können das entfernen §.
Erik der Outgolfer
@EriktheOutgolfer: Leider nein. Wenn wir das entfernen §, Zwird die höchste Zahl auf dem Stapel anstelle der höchsten Ziffer in der Zahl oben auf dem Stapel genommen.
Emigna
@Emigna Huh?
Erik der Outgolfer
3

APL (Dyalog) , 20 bis 16 Bytes

Nimmt und gibt einen String zurück

((⍕⊢⊥⍨1+⌈/)⍎¨)⍣≡

(... )⍣≡ gilt die folgende Funktion , bis zwei aufeinander folgenden Begriffe sind identisch:

⍎¨ führe jedes Zeichen aus (verwandelt die Zeichenkette in eine Liste von Zahlen)

() Wenden darauf folgende implizite Funktion an:

  ⌈/ finde das Maximum des Arguments

  1+ füge eins hinzu

  ⊢⊥⍨ bewerte das Argument in dieser Basis

   Format (stringify, in Vorbereitung auf eine andere Anwendung der äußeren Funktion)

Probieren Sie es online!

Adam
quelle
3

Ruby , 60 56 Bytes

->n{n=(s=n.to_s).to_i(s.bytes.max-47)while/9/!~s&&n>9;n}

Probieren Sie es online!

Wert Tinte
quelle
3

Mathematica, 52 Bytes

FromDigits[s=IntegerDigits@#,Max@s+1]&~FixedPoint~#&

Reine Funktion, die eine nichtnegative Ganzzahl als Eingabe verwendet und eine nichtnegative Ganzzahl zurückgibt. Verwendet die gleiche KernmechanikFromDigits[s=IntegerDigits@#,Max@s+1] wie Jenny_mathys Antwort , nutzt sie jedoch aus FixedPoint, um die Iteration durchzuführen .

Greg Martin
quelle
3

Perl 6 , 49 Bytes

{($_,{.Str.parse-base(1+.comb.max)}...*==*).tail}

Probier es aus

Erweitert:

{
  (

    $_,                 # seed the sequence with the input

    {
      .Str
      .parse-base(      # parse in base:
        1 + .comb.max   # largest digit + 1
      )
    }

    ...                 # keep generating values until

    * == *              # two of them match (should only be in base 10)

  ).tail                # get the last value from the sequence
}
Brad Gilbert b2gills
quelle
2

Pip , 17 Bytes

Wa>9>YMXaaFB:1+ya

Übernimmt Eingaben als Befehlszeilenargument. Probieren Sie es online!

Erläuterung

Das hat Spaß gemacht - ich musste die Verkettungsvergleichsoperatoren herausziehen.

Wir wollen eine Schleife machen, bis die Zahl eine einzelne Ziffer ist ODER eine 9 enthält. Entsprechend wollen wir eine Schleife machen, während die Zahl mehrere Ziffern hat UND keine 9 enthält. Entsprechend wollen wir eine Schleife machen, während die Zahl größer als 9 ist UND die maximale Ziffer ist weniger als 9: a>9>MXa.

Wa>9>YMXaaFB:1+ya
                   a is 1st cmdline arg (implicit)
     YMXa          Yank a's maximum digit into the y variable
Wa>9>              While a is greater than 9 and 9 is greater than a's max digit:
         aFB:1+y    Convert a from base 1+y to decimal and assign back to a
                a  At the end of the program, print a
DLosc
quelle
2

Python 2 , 60 59 56 53 Bytes

4 Byte dank Felipe Nardi Batista
gespeichert 3 Byte dank ovs gespeichert

f=lambda x,y=0:x*(x==y)or f(`int(x,int(max(x))+1)`,x)

Probieren Sie es online!

Verwenden Sie ein rekursives Lambda und vergleichen Sie das Ergebnis der Basiskonvertierung mit der vorherigen Iteration.

Emigna
quelle
Warum nicht so verwenden, x==y and x or ...wie xes niemals sein wird 0(Basis 1)? oder sogar(x==y)*x or ...
Felipe Nardi Batista
@FelipeNardiBatista: Danke! Ich habe versucht, x and x==y or ...was nicht
geklappt hat
@ovs: Richtig. Vielen Dank!
Emigna
@FelipeNardiBatista "Eingabe: Eine positive ganze Zahl n, die aus Ziffern im Bereich von 0 bis 9 besteht." 0 ist immer noch eine gültige Eingabe, und der Code weist sie jetzt zurück.
Mast
@Mast: Zum Glück ist 0 keine positive Ganzzahl und wird daher nicht als Eingabe angegeben.
Emigna
2

C #, 257 244 243 244 233 222 Bytes

using System.Linq;z=m=>{int b=int.Parse(m.OrderBy(s=>int.Parse(s+"")).Last()+""),n=0,p=0;if(b<9&m.Length>1){for(int i=m.Length-1;i>=0;i--)n+=int.Parse(m[i]+"")*(int)System.Math.Pow(b+1,p++);return z(n+"");}else return m;};

Nun, C # braucht immer eine Menge Bytes, aber das ist einfach lächerlich. Keines der eingebauten Systeme kann mit einer beliebigen Basis umgehen, daher musste ich die Umrechnung selbst berechnen. Ungolfed:

using System.Linq;
z = m => {
int b = int.Parse(m.OrderBy(s => int.Parse(s + "")).Last()+""), n = 0, p = 0; //Get the max digit in the string
if (b < 9 & m.Length > 1) //if conditions not satisfied, process and recurse
{
    for (int i = m.Length - 1; i >= 0; i--)
        n += int.Parse(m[i] + "") * (int)System.Math.Pow(b+1, p++); //convert each base-b+1 representation to base-10
    return z(n + ""); //recurse
}
else return m; };
Ceshion
quelle
1

Mathematica, 92 Bytes

f[x_]:=FromDigits[s=IntegerDigits@x,d=Max@s+1];(z=f@#;While[d!=10&&Length@s>1,h=f@z;z=h];z)&
J42161217
quelle
1

Javascript (ES6) mit 0 Pfeilfunktion, 74 Bytes

function f(a){a>9&&b=Math.max(...a)<9&&f(parseInt(a,b+1));alert(a)}f('11')
user71507
quelle
3
Willkommen bei PPCG! :) Dies ist wahrscheinlich eine sehr schöne Antwort, aber ich kann es nicht ohne Erklärung sagen. Ich (und wahrscheinlich auch andere) habe niemals Antworten positiv bewertet, die keine Erklärungen enthalten.
Stewie Griffin
1
Warum rufst du f('11')nach der Funktion an? Es sei denn, ich vermisse etwas, das nur als Verwendung erscheint und nicht Teil der Einreichung ist. Wenn ja, sollten Sie es aus dem Codeabschnitt
entfernen
1

K4 , 19 Bytes

Lösung:

{(1+|/x)/:x:10\:x}/

Beispiele:

q)\
  {(1+|/x)/:x:10\:x}/413574
83911
  {(1+|/x)/:x:10\:x}/13552
159
  {(1+|/x)/:x:10\:x}/17
3
  {(1+|/x)/:x:10\:x}/41253
29    

Erläuterung:

Verwenden Sie die /:integrierte Funktion, um die Basis zu konvertieren.

{(1+|/x)/:x:10\:x}/ / the solution
{                }/ / converge lambda, repeat until same result returned
            10\:x   / convert input x to base 10 (.:'$x would do the same)
          x:        / store in variable x
 (     )/:          / convert to base given by the result of the brackets
    |/x             / max (|) over (/) input, ie return largest
  1+                / add 1 to this
Streetster
quelle
1

Kotlin , 97 Bytes

fun String.f():String=if(length==1||contains("9"))this else "${toInt(map{it-'0'}.max()!!+1)}".f()

Verschönert

fun String.f(): String = if (length == 1 || contains("9")) this else "${toInt(map { it - '0' }.max()!! + 1)}".f()

Prüfung

fun String.f():String=if(length==1||contains("9"))this else "${toInt(map{it-'0'}.max()!!+1)}".f()
val tests = listOf(
        5 to 5,
        17 to 3,
        999 to 999,
        87654321 to 9041998,
        41253 to 29
)

fun main(args: Array<String>) {
    tests.forEach { (input, output) ->
        val answer = input.toString().f()
        if (answer != output.toString()) {
            throw AssertionError()
        }
    }
}

TIO

TryItOnline

jrtapsell
quelle
0

C, 159 157 Bytes

#include <stdlib.h>
char b[99];i=0;m=-1;c(n){do{m=-1;sprintf(b,"%d",n);i=0;while(b[i]){m=max(b[i]-48,m);i++;}n=strtol(b,0,++m);}while(b[1]&&m<10);return n;}
Govind Parmar
quelle
0

Scala , 119 Bytes

if(x.max==57|x.length==1)x else{val l=x.length-1
f((0 to l).map(k=>(((x(k)-48)*math.pow(x.max-47,l-k))) toInt).sum+"")}

Probieren Sie es online!

Scala , 119 Bytes

if(x.max==57|x.length==1)x else f((0 to x.length-1).map(k=>(((x(k)-48)*math.pow(x.max-47,x.length-1-k))) toInt).sum+"")

Probieren Sie es online!

Beide Methoden funktionieren auf die gleiche Weise, aber in der ersten habe ich x.length-1eine Variable eingegeben und in der zweiten nicht.

V. Courtois
quelle