Najlepsza baza to 10… Osiągnijmy to!

40

Wejście:

Dodatnia liczba całkowita n składająca się z cyfr z zakresu 0–9 .

Wyzwanie:

Jeśli d jest najwyższą cyfrą w liczbie całkowitej, załóż, że podstawą liczby jest d + 1 . Np. Jeśli liczba całkowita wynosi 1256 , to zakładasz, że jest ona w bazie-7 , jeśli jest to 10110, to założysz, że jest to podstawa-2 (binarna), a jeśli jest to 159, to jest dziesiętna.

Teraz wykonaj następujące czynności, aż albo: 1: osiągniesz liczbę całkowitą podstawową 10 , albo 2: osiągniesz jednocyfrową liczbę całkowitą.

  1. Przelicz liczbę całkowitą z base- (d + 1) na base-10
  2. Znajdź podstawę tej nowej liczby całkowitej (ponownie, base- (d + 1), gdzie d jest najwyższą cyfrą w nowym numerze)
  3. Przejdź do kroku 1 .

Przykłady:

Załóżmy, że dane wejściowe to n = 413574 . Najwyższa cyfra d = 7 , więc jest to podstawa-8 (ósemkowa). Konwertuj to na dziesiętne i otrzymaj 137084 . Najwyższa cyfra d = 8 , więc jest to podstawa-9 . Konwertuj to na dziesiętne i otrzymaj 83911 . Najwyższa cyfra to 9 , więc jest to liczba dziesiętna i przestajemy. Dane wyjściowe wynoszą 83911 .

Załóżmy, że dane wejściowe to n = 13552 . Najwyższą cyfrą jest d = 5 , więc jest to podstawa-6 . Przelicz to na dziesiętne i otrzymaj 2156 . Najwyższa cyfra d = 6 , więc jest to podstawa-7 . Przelicz to na dziesiętne i otrzymaj 776 . Najwyższą cyfrą jest d = 7 , więc jest to podstawa-8 . Przelicz to na dziesiętne i otrzymaj 510 . Najwyższą cyfrą jest d = 5, więc jest to podstawa-6 . Przelicz to na dziesiętne i uzyskaj 186 . Najwyższa cyfra to 8 , więc jest to podstawa-9 . Przelicz to na dziesiętne i otrzymaj 159. Najwyższa cyfra to 9 , więc jest to liczba dziesiętna i przestajemy. Dane wyjściowe wynoszą 159 .

Załóżmy, że dane wejściowe to n = 17 . To da nam 15 , następnie 11 , a następnie 3 , które wyprowadzimy, ponieważ jest to jedna cyfra.


Przypadki testowe:

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

Uwagi:

  • Standardowe zasady dotyczące We / Wy, luk itp. Dane wejściowe można traktować jako ciąg znaków
  • Wyjaśnienia są zachęcane
  • Możesz użyć wbudowanych poleceń konwersji bazy
    • Rozwiązania, które nie używają wbudowanych funkcji konwersji języka (jeśli istnieją) są mile widziane, nawet jeśli kończą znacznie dłużej niż oczywiste podejście przy użyciu funkcji wbudowanych.

Najwyraźniej jest to OEIS A091047 .

Stewie Griffin
źródło
2
Najwyraźniej uwielbiam matryce , więc pomyślałem, że zamiast tego wykonam wyzwanie konwersji bazy .
Stewie Griffin,
34
„Najlepsza baza to 10” ... W której bazie napisane jest „10”?
Olivier Grégoire,
5
@ OlivierGrégoire To sprytna rzecz ... Bez względu na to, z jakiej bazy się skończysz, nadal będzie to ważne stwierdzenie!
Stewie Griffin,
@StewieGriffin Ale jak to czytasz? „10” ma inną nazwę w każdej bazie.
user11153
10
Cóż, to zależy od bazy ... lub, jak powiedziałaby Meghan, „chodzi o tę bazę,„ O tę bazę, żadnych problemów ” ;-)
Stewie Griffin

Odpowiedzi:

20

Mathematica, 56 bajtów

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

Wypróbuj online! (Korzystanie z matematyki.)

Myślałem, że sprawdzę, jak wygląda sekwencja:

wprowadź opis zdjęcia tutaj

A oto wykres liczby kroków, które należy wykonać, aby znaleźć wynik:

wprowadź opis zdjęcia tutaj

(Kliknij, aby wyświetlić większe wersje. Zobacz historię zmian dla wykresów tylko do n = 1000 ).

Wygląda na bardzo interesującą mieszankę wielkoskalowej struktury i drobnego chaosu. Zastanawiam się, co słychać przy szerszych lukach między 30 000 a 60 000.

Martin Ender
źródło
4
@StewieGriffin powinien znajdować się po lewej stronie. Istnieją małe luki, ponieważ liczby prowadzące do wielokrotności potęgi 10 zawierają a 9, więc są już w bazie 10. Ale dla 30k i 60k wydaje się, że liczby z 8 lub nawet 7 (musiałyby check) zamiast tego 9 zawsze staje się bazą 10 po co najwyżej jednym kroku.
Martin Ender
@StewieGriffin Mówiąc ściślej, wszystkie liczby w zakresie [28051, 28888] są podstawą 9 i przekładają się na liczby w postaci 19xxx, co znacznie podwaja tę lukę.
cmaster
Ach, rozumiem ... :) Dla przypomnienia: wiedziałem, dlaczego po lewej stronie mocy 10-tych były luki ... Tylko dziwne były podwójne szczeliny (dlaczego 30/60, a nie 20 / 40/50). Widzę teraz, że liczby w zakresie 28xxx -> 19xxx, ale 38xxx -> 26xxx, a nie 29xxx.
Stewie Griffin
10

Java 8, 172 166 163 152 151 140 138 116 114 99 bajtów

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

Pobiera dane wejściowe jako String.

-64 bajty dzięki @ OlivierGrégoire . I tutaj myślałem, że mój początkowy 172 nie był taki zły ...;)

Wypróbuj tutaj.

Wyjaśnienie:

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
źródło
1
Obiecujesz zachować spokój? : p Ok ... chodźmy: s->{for(Integer b=0;b<10&s.length()>1;)s=""+b.valueOf(s,b=s.chars().max().getAsInt()-47);return s;}. Usunąłem także większość moich komentarzy, ponieważ są one całkowicie nieistotne ( bjest to podstawa, twoja ai sliczba, nad którą pracujemy).
Olivier Grégoire
1
Próbowałem rekursywnie to, aby zgolić kilka bajtów za pomocą: Integer b;return(b=s.chars().max().getAsInt()-47)>9|s.length()<2?s:c(""+b.valueOf(s,b));(88), ale jestem zupełnie nowy w kodowaniu golfa. To jest fragment, prawda? Czy istnieje sposób zadeklarowania tego jako metody bez potrzeby dodawania public String c(String s)?
Lord Farquaad
1
@ LordFarquaad Nie potrzebujesz tego public, ale obawiam się, że rzeczywiście będziesz musiał go używać String c(String s){}do wywołań rekurencyjnych, nawet w Javie 8. Kiedy utworzysz lambda za pomocą 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));}lub interfejsu używającego 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));};go, podasz inicjator błąd ”w obu przypadkach. Ale jednak bardzo miłe podejście!
Kevin Cruijssen
Ach, przypuszczam, że wtedy odkopałem go kilka bajtów. Ale dzięki za pomoc! Będę pamiętać o tym, by iść naprzód.
Lord Farquaad
8

Pyth, 9 bajtów

ui`GhseS`

Zestaw testowy

Wyjaśnienie:

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
źródło
To trochę dziwne, jak użyłeś lambda z dwiema zmiennymi, który ostatecznie wykorzystał jedną zmienną ... i nie wyrzucił błędów. Och, dwie zmienne są Qi Q, rozumiem.
Erik the Outgolfer,
@EriktheOutgolfer Niezupełnie. ubez trzeciego wejścia stosuje się do powtórzenia, podczas gdy przy trzecim wejściu stosuje się określoną liczbę razy. ulambda ma Gi H, ale nie musisz jej używać H.
isaacg
W rzeczywistości zastąpienie Ggo Hmiałoby ten sam wynik ... zmienna domyślna btw jest G?
Erik the Outgolfer,
@EriktheOutgolfer Domyślną zmienną jest Gtak. Hzlicza od 0 przy każdej iteracji, więc jest zupełnie inna. Nie jestem do końca pewien, o czym mówisz. Oto przykładowy program pokazujący, co się dzieje: pyth.herokuapp.com/…
isaacg
6

JavaScript (ES6), 63 57 54 53 bajtów

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

Zaoszczędź 8 bajtów dzięki Shaggy i Dom Hastings

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

console.log(f("413574"))

Tomek
źródło
Pokonaj mnie do tego. Myślę, że można zaoszczędzić kilka bajtów +a>9||b<9i odwrócić trójskładnik.
Shaggy
1
@Shaggy edit: I'm głupi
Tom
1
Nie bądź dla siebie zbyt surowy Tom! Nie jesteś głupi ,,, ale zdecydowanie nie jesteś tak mądry jak @Shaggy!
Stewie Griffin
1
Alternatywa dla 55 bajtówf=n=>n>9&&(k=Math.max(...n+"")+1)<10?f(parseInt(n,k)):n
Dom Hastings
@DomHastings Dzięki za ulepszenia! :)
Tom
5

Python 3 , 91 78 76 75 73 bajtów

@Emigna straciła 5 bajtów. @FelipeNardiBatista zapisał 1 bajt. @ RomanGräf zapisał 2 bajty

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

Wypróbuj online!


Wyjaśnienie

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
Pan Xcoder
źródło
5

05AB1E , 10 5 bajtów

5 bajtów zaoszczędzonych dzięki Magic Octopus Urn

F§Z>ö

Ponieważ przy dużych nakładach szybkość ta rośnie bardzo szybko, zostawiam tutaj starszą, znacznie szybszą wersję do testowania. Algorytm jest taki sam, różni się tylko liczba iteracji.

[©Z>öD®Q#§

Wypróbuj online!

Wyjaśnienie

[             # 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
źródło
Nie możesz po prostu użyć тFZ>ö§? Widzisz, jak liczba iteracji ( jak widać tutaj ) wydaje się plateau? Jeśli chcesz uzyskać techniczne, tempo, w którym iteracje rosną, jest prawdopodobnie logarytmiczne ... Więc możesz po prostu użyć czegoś takiego: DFZ>ö§i stwierdzić, że nie będzie działać na dużą skalę n. LUB może nawet: T.n>FZ>ö§bezpośrednio obliczyć liczbę iteracji jako log_10(n).
Magic Octopus Urn
@MagicOctopusUrn: Tak, teraz, kiedy o tym wspominasz, ponieważ sekwencja zdecydowanie wydaje się wolniejsza niż liniowa, F§Z>öpowinna załatwić sprawę.
Emigna
Myślę, że możesz usunąć §.
Erik the Outgolfer,
@EriktheOutgolfer: Niestety nie. Jeśli usuniemy §, Zweźmie najwyższą liczbę na stosie zamiast najwyższej cyfry na górze stosu.
Emigna
@Emigna Huh?
Erik the Outgolfer,
3

APL (Dyalog) , 20 16 bajtów

Bierze i zwraca ciąg znaków

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

()⍣≡ Zastosuj następującą funkcję, aż dwa kolejne terminy będą identyczne:

⍎¨ wykonaj każdy znak (zamienia ciąg znaków na listę liczb)

() Zastosuj do tego następującą milczącą funkcję:

  ⌈/ znajdź maksimum argumentu

  1+ Dodaj jeden

  ⊢⊥⍨ oceń argument w tej bazie

   format (stringify, w ramach przygotowań do kolejnego zastosowania funkcji zewnętrznej)

Wypróbuj online!

Adám
źródło
3

Rubinowy , 60 56 bajtów

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

Wypróbuj online!

Wartość tuszu
źródło
3

Mathematica, 52 bajty

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

Czysta funkcja przyjmująca nieujemną liczbę całkowitą jako dane wejściowe i zwracająca nieujemną liczbę całkowitą. Wykorzystuje tę samą podstawową mechanikę, FromDigits[s=IntegerDigits@#,Max@s+1]co odpowiedź Jenny_mathy , ale wykorzystuje się FixedPointdo wykonania iteracji.

Greg Martin
źródło
3

Perl 6 , 49 bajtów

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

Sprawdź to

Rozszerzony:

{
  (

    $_,                 # 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
źródło
2

Pip , 17 bajtów

Wa>9>YMXaaFB:1+ya

Pobiera dane wejściowe jako argument wiersza polecenia. Wypróbuj online!

Wyjaśnienie

To była zabawa - musiałem wyciągnąć operatory porównania łańcuchów.

Chcemy zapętlać, dopóki liczba nie będzie jednocyfrowa LUB zawiera 9. Równoważnie, chcemy zapętlać, gdy liczba jest wielocyfrowa ORAZ nie zawiera 9. Równoważnie, zapętlać, gdy liczba jest większa niż 9 ORAZ maksymalna cyfra to mniej niż 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
źródło
2

Python 2 , 60 59 56 53 bajtów

Zaoszczędzono 4 bajty dzięki Felipe Nardi Batista
Zaoszczędzono 3 bajty dzięki ovs

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

Wypróbuj online!

Za pomocą rekurencyjnej lambda, porównując wynik konwersji podstawowej z poprzednią iteracją.

Emigna
źródło
dlaczego nie użyć, x==y and x or ...jak xnigdy nie będzie 0(baza 1). a nawet(x==y)*x or ...
Felipe Nardi Batista
@FelipeNardiBatista: Dzięki! Próbowałem, x and x==y or ...co nie zadziałało, ale nie jestem zbyt biegły w tych sztuczkach, więc nie zdawałem sobie sprawy, że mogę to odwrócić :)
Emigna
@ovs: Masz rację. Dzięki!
Emigna
@FelipeNardiBatista „Wejście: dodatnia liczba całkowita n składająca się z cyfr z zakresu 0–9.” 0 jest nadal prawidłowym wejściem, a teraz kod je odrzuca.
Maszt
@Mast: Na szczęście dla nas 0 nie jest dodatnią liczbą całkowitą, więc nie będzie podawana jako dane wejściowe.
Emigna
2

C #, 257 244 243 244 233 222 bajtów

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

C # zawsze zajmuje dużo bajtów, ale jest to po prostu śmieszne. Żadna z wbudowanych funkcji nie jest w stanie obsłużyć arbitralnej bazy, więc musiałem sam obliczyć konwersję. Nie golfowany:

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
źródło
1

Mathematica, 92 bajty

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
źródło
1

JavaScript (ES6) z funkcją strzałki 0, 74 bajty

function f(a){a>9&&b=Math.max(...a)<9&&f(parseInt(a,b+1));alert(a)}f('11')
użytkownik71507
źródło
3
Witamy w PPCG! :) To prawdopodobnie bardzo miła odpowiedź, ale nie potrafię tego wyjaśnić bez wyjaśnienia. Ja (i prawdopodobnie inni) nigdy nie oceniam odpowiedzi, które nie zawierają wyjaśnień.
Stewie Griffin
1
Dlaczego dzwonisz f('11')po funkcji? Chyba że brakuje mi czegoś, co wygląda tylko na wykorzystanie, a nie jest częścią zgłoszenia. Jeśli tak, wyjmij go z sekcji kodu i umieść w wyjaśnieniu (po dodaniu) i zaktualizuj liczbę bajtów do 67.
PunPun1000
1

K4 , 19 bajtów

Rozwiązanie:

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

Przykłady:

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    

Wyjaśnienie:

Użyj /:wbudowanego do konwersji bazy.

{(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
źródło
1

Kotlin , 97 bajtów

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

Upiększony

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

Test

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
źródło
0

C, 159 157 bajtów

#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
źródło
0

Scala , 119 bajtów

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

Wypróbuj online!

Scala , 119 bajtów

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

Wypróbuj online!

Obie metody działają w ten sam sposób, ale w pierwszej wstawiam x.length-1zmienną, aw drugiej nie.

V. Courtois
źródło