Palindrome Basis Terendah

16

Diberi nomor n, tulis fungsi yang menemukan basis terkecil b ≥ 2sedemikian rupa sehingga nmerupakan palindrom di dasarnya b. Misalnya, input 28harus mengembalikan basis 3karena representasi terner 28 adalah 1001. Meskipun 93merupakan palindrom di kedua basis 2 dan basis 5, output harus 2sejak 2 <5.

Memasukkan

Bilangan bulat positif n < 2^31.

Keluaran

Kembalikan basis terkecil b ≥ 2sehingga brepresentasi dasar nadalah palindrom. Jangan menganggap angka nol di depan.

Sampel (input => keluaran):

11 => 10

32 => 7

59 => 4

111 => 6

Aturan

Kode terpendek menang.

ntomlin1996
sumber
1
Saya pikir basis harus dibatasi.
Snack
3
@Snack: Apa masalahnya dengan pangkalan yang lebih tinggi? Terlepas dari pilihan simbol, angka dasar 1000 akan berupa palindrom atau tidak.
Dennis
3
Anekdot yang menarik: n pada basis n-1 selalu 11 untuk n> = 2 dan dengan demikian palindrom selalu dimungkinkan.
Cruncher
1
@Cruncher: nbisa 1 dan 2 bukan palindrom basis 1. Namun, setiap positif nadalah n + 1palindrom dasar .
Dennis
1
@ Dennis Bagaimana 2 bukan palindrom basis 1? Ini 11. Atau II, atau 2 dari simbol apa pun yang Anda gunakan. Sebenarnya semua angka dasar 1 adalah palindrom. Dan saya katakan n> = 2, karena saya tidak tahu apa yang akan menjadi basis 0.
Cruncher

Jawaban:

4

CJam , 19 byte / GolfScript, 23 byte

q~:N;1{)_N\b_W%=!}g

atau

~:N;1{).N\base.-1%=!}do

Cobalah online:

Contohnya

$ cjam base.cjam <<< 11; echo
10
$ cjam base.cjam <<< 111; echo
6
$ golfscript base.gs <<< 11
10
$ golfscript base.gs <<< 111
6

Bagaimana itu bekerja

q~:N;   # Read the entire input, interpret it and save the result in “N”.
1       # Push 1 (“b”).
{       #
  )     # Increment “b”.
  _N\   # Duplicate “b”, push “N” and swap.
  b     # Push the array of digits of “N” in base “b”.
  _W%   # Duplicate the array and reverse it.
  =!    # Compare the arrays.
}g      # If they're not equal, repeat the loop.

Untuk GolfScript, q~is ~, _is ., bis base, Wis -1dan gis do.

Dennis
sumber
6

GolfScript, 20 karakter

~:x,2>{x\base.-1%=}?

Pendekatan yang berbeda dengan GolfScript selain Dennis '. Ini menghindari loop eksplisit mahal yang mendukung operator find . Coba online .

~:x        # interpret and save input to variable x
,2>        # make a candidate list 2 ... x-1 (note x-1 is the maximum possible base)
{          # {}? find the item on which the code block yields true
  x\       # push x under the item under investigation
  base     # perform a base conversion
  .-1%     # make a copy and reverse it
  =        # compare reversed copy and original array
}?         
Howard
sumber
1
Pintar! Namun, ini tidak berfungsi jika x = 1atau x = 2. Keduanya adalah single-digit, x + 1palindrom dasar , jadi x))harus memperbaikinya.
Dennis
4

Mathematica, 67 66 byte

g[n_]:=For[i=1,1>0,If[(d=n~IntegerDigits~++i)==Reverse@d,Break@i]]

Tidak bisa benar-benar bersaing dengan GolfScript di sini dalam hal ukuran kode, tetapi hasil untuk 2 32 pada dasarnya dikembalikan secara instan.

Martin Ender
sumber
Bagus. Fungsi ini tidak harus disebutkan namanya, bukan? Bisakah Anda menggunakan fungsi yang tidak disebutkan namanya?
numbermaniac
(Juga, apakah mungkin digunakan PalindromeQuntuk cek terbalik?)
numbermaniac
4

Japt , 12 9 byte

Kecuali saya telah melewatkan trik (sudah terlambat!), Ini harus bekerja untuk semua nomor hingga dan termasuk setidaknya 2**53-1.

Dalam pengujian saya (yang diakui terbatas dan sepenuhnya acak), saya mendapatkan hasil hingga basis (!) Sejauh ini. Tidak terlalu kumuh jika Anda mempertimbangkan JavaScript hanya mendukung secara native basis untuk .11601 310,515236

@ìX êê}a2

Cobalah

  • Terima kasih kepada ETH karena menunjukkan sesuatu yang baru bagi saya yang menghemat 3 byte dan meningkatkan efisiensi secara signifikan.

Penjelasan

Input bilangan bulat implisit U.

@     }a2

Dimulai dengan 2, kembalikan angka pertama yang mengembalikan true ketika melewati fungsi berikut, dengan Xmenjadi angka saat ini

ìX

Konversi Uke array Xangka dasar .

êê

Uji apakah array itu adalah palindrom.

Shaggy
sumber
1) Ya. Salahkan bir untuk itu! : D 2) Bagus; tidak pernah tahu N.ì(n)bisa menangani pangkalan yang lebih besar dari 36. Terima kasih untuk itu.
Shaggy
Ya, alfabet dasar-36 tidak masalah N.ì(n)karena kami menggunakan bilangan bulat mentah ;-)
ETHproduksi
2

Python 2 (83)

def f(n,b=2):
 l=[];m=n
 while m:l+=[m%b];m//=b
 return l==l[::-1]and b or f(n,b+1)

Saya tidak yakin apa format input / output pertanyaan yang diinginkan. Saya menulis sebuah fungsi. Kode menggunakan input opsional buntuk melacak basis saat ini sedang diuji. The whileloop mengkonversi nomor tersebut ke daftar digit dalam basis b.

Baris terakhir mengembalikan bif lis a palindrome, dan secara rekursif mencoba berikutnya b. Trik index-by-Boolean tidak berfungsi di sini karena akan menyebabkan kedua opsi dievaluasi terlepas dari Boolean, dan rekursi tidak akan pernah keluar dari posisi semula.

Tidak
sumber
1
Jadi ini tidak akan bekerja dengan basis tinggi sewenang-wenang kan? Jika basis terendah yang dimiliki palindrome adalah 10.000 maka Anda akan mendapatkan stack overflow?
Cruncher
@Cruncher Tergantung dari implementasi Python. Ini akan meluap ketika dijalankan dengan CPython, tetapi tidak dengan Stackless Python , yang melakukan optimasi panggilan ekor dan tidak memiliki batas rekursi (meskipun saya belum benar-benar mengujinya).
xnor
2

JavaScript, 88 byte

f=function(n){for(a=b='+1';a^a.split('').reverse().join('');a=n.toString(++b));return+b}

Tidak Terkumpul:

f = function(n) {
    for(a = b = '+1'; // This is not palindrome, but equals 1 so we have at least one iteration
        a ^ a.split('').reverse().join(''); // test a is palindrome
        a = n.toString(++b));
    return+b
}
core1024
sumber
1

Javascript, 105 byte

function f(n){for(var b=2,c,d;d=[];++b){for(c=n;c;c=c/b^0)d.push(c%b);if(d.join()==d.reverse())return b}}

JSFiddle: http://jsfiddle.net/wR4Wf/1/

Perhatikan bahwa implementasi ini juga berfungsi dengan benar untuk basis besar. Misalnya, f(10014)mengembalikan 1668 (10014 adalah 66 di basis 1668).

GOTO 0
sumber
Ini bagus. Anda bahkan s/var b=2,c,d/b=d=2/dapat memperoleh 6 byte lebih banyak;)
core1024
1

Bash + coreutils, 100 byte

for((b=1;b++<=$1;)){
p=`dc<<<${b}o$1p`
c=tac
((b<17))&&c=rev
[ "$p" = "`$c<<<$p`" ]&&echo $b&&exit
}

Menggunakan dcuntuk melakukan pemformatan dasar. Yang sulit adalah dcformatnya berbeda untuk n> 16.

Testcases:

$ ./lowestbasepalindrome.sh 11
10
$ ./lowestbasepalindrome.sh 32
7
$ ./lowestbasepalindrome.sh 59
4
$ ./lowestbasepalindrome.sh 111
6
$ 
digital Trauma
sumber
1

J - 28 char

#.inv~(-.@-:|.@)(1+]^:)^:_&2

Dijelaskan:

  • #.inv~ - Bentangkan argumen kiri ke pangkalan di argumen kanan.

  • (-.@-:|.@) - Kembalikan 0 jika ekspansi palindromik, dan 1 sebaliknya.

  • (1+]^:) - Tambahkan argumen yang benar satu per satu jika kami mengembalikan 1, jika tidak lakukan tindakan.

  • ^:_ - Ulangi kenaikan di atas sampai tidak ada tindakan.

  • &2 - Siapkan argumen yang tepat sebagai 2, menjadikan ini fungsi dari satu argumen.

Contoh:

   #.inv~(-.@-:|.@)(1+]^:)^:_&2 (28)
3
   #.inv~(-.@-:|.@)(1+]^:)^:_&2 every 93 11 32 59 111  NB. perform on every item
2 10 7 4 6
   #.inv~(-.@-:|.@)(1+]^:)^:_&2 every 1234 2345 3456 4567 5678 6789
22 16 11 21 31 92
algoritme hiu
sumber
2+1 i.~[#.inv"*(-:|.@)~2+i.selama 27 byte. (Tidak ingin mempostingnya secara terpisah. Saya hanya akan meninggalkannya di sini.)
randomra
@randomra Saya akan menghitungnya 29 karena kereta perlu parens untuk digunakan sebaris; saya menyimpan karakter dengan memiliki konjungsi di tingkat atas.
algorithmshark
Saya pikir pendirian mayoritas pada penilaian adalah penghitungan kurang-paren dengan fungsi yang tidak disebutkan namanya meskipun selalu ada argumen tentang ini. Bagaimanapun, saya akan meninggalkannya di sini dan semua orang dapat memilih bagaimana skornya. :)
randomra
1

R, 122 95 byte

function(n)(2:n)[sapply(2:n,function(x){r={};while(n){r=c(n%%x,r);n=n%/%x};all(r==rev(r))})][1]

Solusi berusia tiga tahun pada 122 byte:

f=function(n)(2:n)[sapply(sapply(2:n,function(x){r=NULL;while(n){r=c(n%%x,r);n=n%/%x};r}),function(x)all(x==rev(x)))][1]

Dengan beberapa penjelasan:

f=function(n)(2:n)[sapply(
                    sapply(2:n,function(x){ #Return the decomposition of n in bases 2 to n
                                 r=NULL
                                 while(n){
                                     r=c(n%%x,r)
                                     n=n%/%x}
                                     r
                                     }
                           ),
                    function(x)all(x==rev(x))) #Check if palindrome
                   ][1] #Return the first (i. e. smallest) for which it is
plannapus
sumber
1

Sekam , 11 9 byte

ḟoS=↔`B⁰2

Terima kasih @Zgarb untuk -2!

Cobalah online!

Penjelasan

ḟ(      )2  -- find least number ≥ 2 that satisfies:
     `B⁰    --   convert input to base (` flips arguments)
  S=↔       --   is palindrome (x == ↔x)
ბიმო
sumber
0

Catatan: Pyth lebih baru dari pertanyaan ini, jadi jawaban ini tidak memenuhi syarat untuk menang.

Pyth, 10 byte

fq_jQTjQT2

Coba di sini.

isaacg
sumber
0

Scala, 83 byte

def s(n:Int)=(for(b<-2 to n;x=Integer.toString(n,b);if(x==x.reverse))yield(b)).min
Dave Swartz
sumber
0

Perl 5 , 84 + 1 (-p) = 85 byte

$\=1;{++$\;my@r;$n=$_;do{push@r,$n%$\}while$n=int$n/$\;@t=@r;map$_-pop@t&&redo,@r}}{

Cobalah online!

Xcali
sumber
0

JavaScript 72 byte

F=(n,b=2)=>eval(`for(t=n,a=c="";t;t=t/b|0)a=t%b+a,c+=t%b`)^a?F(n,b+1):b

console.log(F(11) == 10)

console.log(F(32) == 7)

console.log(F(59) == 4)

console.log(F(111) == 6)

DanielIndie
sumber
0

Mathematica 42 byte

Variasi entri Martin Ender. Memanfaatkan IntegerReverse(tersedia dalam versi 10.3) yang dibagikan IntegerDigits.

(i=2;While[#~IntegerReverse~i !=#,i++];i)&
DavidC
sumber
0

Java 8, 103 byte

n->{int b=1,l;for(String s;!(s=n.toString(n,++b)).equals(new StringBuffer(s).reverse()+""););return b;}

Penjelasan:

Coba di sini.

n->{                          // Method with integer as both parameter and return-type
  int b=1,                    //  Base-integer, starting at 1
      l;                      //  Length temp integer
  for(String s;               //  Temp String
      !(s=n.toString(n,++b))  //   Set the String to `n` in base `b+1`
                              //   (by first increase `b` by 1 using `++b`)
       .equals(new StringBuffer(s).reverse()+"");
                              //   And continue looping as long as it's not a palindrome
  );                          //  End of loop
  return b;                   //  Return the resulting base integer
}                             // End of method
Kevin Cruijssen
sumber