Język J ma bardzo głupią składnię do określania stałych . Chcę skupić się w szczególności na jednej fajnej funkcji: umiejętności pisania w dowolnych podstawach.

Jeśli piszesz XbYdla Xdowolnej liczby i Ydowolnego ciągu alfanumerycznego, to J będzie interpretował Yjako Xliczbę podstawową , gdzie 0poprzez 9mają swoje zwykłe znaczenie i oznaczają aprzez z10 do 35.

A kiedy mówię Xdowolną liczbę, mam na myśli dowolną liczbę. Na potrzeby tego pytania ograniczę się Xdo bycia liczbą całkowitą dodatnią, ale w J możesz użyć wszystkiego: liczb ujemnych, ułamków, liczb zespolonych, cokolwiek.

Dziwne jest to, że możesz używać liczb od 0 do 35 jako cyfr bez względu na bazę, ponieważ twoja kolekcja użytecznych symboli składa się tylko z 0-9 i az.

Problem

Chcę, aby program pomógł mi przy użyciu tej metody magicznych liczb golfowych, takich jak 2 933,774,030,998 . Cóż, okej, może nie aż tak duże, nie będę się nudzić. Więc...

Twoim zadaniem jest napisanie programu lub funkcji, która przyjmuje (zwykle dużą) liczbę dziesiętną Nod 1 do 4 294 967 295 (= 2 ³² -1) jako dane wejściowe i zwraca / zwraca najkrótszą reprezentację postaci XbY, gdzie Xdodatnia liczba całkowita, Yto ciąg składający się z znaków alfanumerycznych (0-9 i az, bez rozróżniania wielkości liter) i Yzinterpretowany w Xrówności podstawowej N.

Jeśli długość każdej reprezentacji XbYreprezentacji jest większa lub równa liczbie cyfr N, wówczas Nwypisuje. We wszystkich innych powiązaniach możesz wyprowadzać dowolny niepusty podzbiór najkrótszych reprezentacji.

To jest golf golfowy, więc krótszy jest lepszy.

Przypadki testowe

      Input | Acceptable outputs (case-insensitive)
------------+-------------------------------------------------------
          5 | 5
            |
   10000000 | 79bkmom  82bibhi  85bgo75  99bauua  577buld
            | 620bq9k  999baka
            |
   10000030 | 85bgo7z
            |
   10000031 | 10000031
            |
   12345678 | 76bs9va  79bp3cw  82bmw54  86bjzky  641buui
            |
   34307000 | 99bzzzz
            |
   34307001 | 34307001
            |
 1557626714 | 84bvo07e  87brgzpt  99bglush  420blaze
            |
 1892332260 | 35bzzzzzz  36bvan8x0  37brapre5  38bnxkbfe  40bij7rqk
            | 41bgdrm7f  42bek5su0  45bablf30  49b6ycriz  56b3onmfs
            | 57b38f9gx  62b244244  69b1expkf  71b13xbj3
            |
 2147483647 | 36bzik0zj  38br3y91l  39bnvabca  42bgi5of1  48b8kq3qv
 (= 2^31-1) | 53b578t6k  63b2akka1  1022b2cof  1023b2661  10922bio7
            | 16382b8wv  16383b8g7  32764b2gv  32765b2ch  32766b287
            | 32767b241
            |
 2147483648 | 512bg000  8192bw00
            |
 4294967295 | 45bnchvmu  60b5vo6sf  71b2r1708  84b12mxf3  112brx8iv
 (= 2^32-1) | 126bh5aa3  254b18owf  255b14640  1023b4cc3  13107bpa0
            | 16383bgwf  21844b9of  21845b960  32765b4oz  32766b4gf
            | 32767b483  65530b1cz  65531b1ao  65532b18f  65533b168
            | 65534b143  65535b120

Jeśli nie masz pewności, czy reprezentacja jest równa jakiejś liczbie, możesz użyć dowolnego interpretera języka J, takiego jak ten w Try It Online . Wystarczy wpisać, stdout 0":87brgzpta J wypluje z powrotem 1557626714. Zauważ, że J akceptuje tylko małe litery, nawet jeśli w tym problemie nie jest rozróżniana wielkość liter.

Jakaś pomocna teoria

• Dla wszystkich Nmniejszych niż 10 000 000 reprezentacja dziesiętna jest tak krótka jak każda inna, a zatem jest jedynym akceptowalnym wynikiem. Aby cokolwiek zapisać, musisz być co najmniej o cztery cyfry krótszy w nowej bazie, a nawet więcej, jeśli baza jest większa niż 99.
• Wystarczy sprawdzić podstawy do sufitu pierwiastka kwadratowego N. W przypadku każdej większej bazy B , Nbędą miały najwyżej dwie cyfry w bazie B , więc pierwszy raz otrzymasz coś z poprawną pierwszą cyfrą w okolicach B ≈ N/ 35. Ale przy tym rozmiarze zawsze będziesz co najmniej tak duży jak reprezentacja dziesiętna, więc nie ma sensu próbować. Mając to na uwadze, ceil (sqrt (największa liczba, o którą poproszę cię o rozwiązanie tego problemu)) = 65536.
• Jeśli masz jakąkolwiek reprezentację w bazie mniejszej niż 36, wówczas podstawowa reprezentacja 36 będzie co najmniej tak krótka. Nie musisz się więc martwić przypadkowymi krótkimi rozwiązaniami w bazach mniejszych niż 36. Na przykład reprezentacja 1 35bzzzzzz892 332 260 używa nietypowej cyfry dla tej bazy, ale 36bvan8x0ma tę samą długość.

JavaScript (ES6), 103 101 bajtów

Pobiera dane wejściowe jako ciąg.

n=>[...Array(7e4)].reduce(p=>p[(r=++b+(g=x=>x?g(x/b|0)+(x%b).toString(36):'b')(n)).length]?r:p,n,b=2)

Przypadki testowe

Uwaga: liczba iteracji w funkcji fragmentu kodu jest ograniczona do 600, dzięki czemu przypadki testowe kończą się szybciej. (W przeciwnym razie zajęłoby to kilka sekund.)

let f =

n=>[...Array(6e2)].reduce(p=>p[(r=++b+(g=x=>x?g(x/b|0)+(x%b).toString(36):'b')(n)).length]?r:p,n,b=2)

console.log(f("5"))
console.log(f("10000000"))
console.log(f("10000030"))
console.log(f("10000031"))
console.log(f("12345678"))
console.log(f("34307000"))
console.log(f("34307001"))
console.log(f("1557626714"))
console.log(f("1892332260"))
console.log(f("2147483647"))
console.log(f("2147483648"))
console.log(f("4294967295"))

Rubin , 118 bajtów

Było to powiązane z innym pytaniem i zauważyłem, że nie ma tu wielu odpowiedzi, więc postanowiłem spróbować.

Przejdź przez wszystkie bazy aż do danych wejściowych włącznie, aby skonstruować wszystkie prawidłowe konstrukcje liczb J. Pomija jednak 1-8, ponieważ nie ma szans, że będą one krótsze niż reprezentacja base-10. Jest to dość naiwne rozwiązanie, biorąc pod uwagę wszystkie kwestie, ponieważ wywołuje funkcję digitswbudowaną, aby uzyskać cyfry, ale ponieważ zaczyna się ona od najmniej znaczącej cyfry, najpierw musimy reverseją uzyskać, aby uzyskać rzeczywistą liczbę, aby można ją było poprawić.

Jest wolny Tak bardzo bardzo wolno. Na przykład limit czasu TIO dla 34307000. My mogliśmy pójść z pierwiastka kwadratowego lub nawet wybór Arnauld z dnia 7e4aby zaoszczędzić czas, ale to koszty dodatkowe bajty, więc po co się męczyć?

->n{([n.to_s]+(9..n).map{|b|d=n.digits b;"#{b}b"+d.reverse.map{|i|i.to_s 36}*''if d.all?{|i|i<36}}-[p]).min_by &:size}

Wypróbuj online!

Wypróbuj online w / sqrt, aby wszystko skończyło się na czas

05AB1E , 37 bajtów

[¼35ݾãvtîEyNβQižhA«yèJ'bìNìDgIg@i\}q

10000000ã$\geq4$

Bez końcowej instrukcji if DgIg@i\}nadal można ją przetestować pod kątem niższych wartości, aby sprawdzić, czy faktycznie działa: Wypróbuj online.

Zobaczę, czy mogę później (prawdopodobnie znacznie dłużej, ale) bardziej wydajne rozwiązanie.

Wyjaśnienie:

[              # Start an infinite loop:
 ¼             #  Increase the counter variable by 1 (0 by default)
 35Ý           #  Push a list in the range [0, 35]
 ¾ã            #  Take the cartesian product of this list with itself,
               #  with chunks-sizes equal to the counter variable
 v             #  Loop `y` over each of these lists:
  t            #   Take the square-root of the (implicit) input-integer
   î           #   Ceil it
  E            #   Loop `N` in the range [1, ceil(square(input))]:
   yNβ         #    Convert list `y` to base-`N`
   Qi          #    If it's equal to the (implicit) input-integer:
     žh        #     Push string "0123456789"
       A«      #     Append the lowercase alphabet
     yè        #     Index each value in list `y` into this string
     J         #     Join the characters to a single string
     'bì      '#     Prepend a "b"
        Nì     #     Prepend the number `N`
     D         #     Duplicate it
      g        #     And pop and push the length of this string
       Ig      #     Also push the length of the input
         @i }  #     If the length of the string is >= the input-length:
           \   #      Discard the duplicated string
     q         #     Stop the program
               #     (after which the result is output implicitly;
               #      or if the string was discarded and the stack is empty, it will
               #      implicitly output the implicit input as result instead)