Tentukan Basis mana Persamaan Diberikan Benar

22

Dengan 3 bilangan bulat, tentukan basis terendah yang mungkin untuk dua bilangan bulat pertama untuk dikalikan menjadi yang ketiga. Jika Anda memikirkan Jawaban atas Pertanyaan Utama Kehidupan, Alam Semesta, dan Segalanya, 6 * 9 == 42, benar di Basis 13.

Input dapat menyertakan angka apa pun yang digitnya menggunakan karakter 0-9, az, dan AZ, di mana asama dengan 10 di Basis 10, dan Z61 di Basis 10.

Input harus dimasukkan dengan cara apa pun yang Anda suka (kecuali untuk hard-coding), dan Anda dapat menulis fungsi individual atau keseluruhan program.

Basis maksimum yang harus dipertimbangkan adalah Basis 62, dan basis minimum adalah Basis 2.

Anda dapat mengasumsikan bahwa dua nilai pertama lebih kecil dari nilai ketiga. Anda juga dapat menyimpulkan bahwa basis minimum adalah satu lebih besar dari digit / karakter tertinggi dari input (misalnya, jika inputnya 3 1a 55, basis minimum adalah Base 11, karena amerupakan digit tertinggi).

Jika tidak ada basis seperti itu, kembalikan nilai sampah pilihan Anda.

Ini kode golf, jadi kode terpendek menang.

Uji Kasus

6 9 42     -->   13
a a 64     -->   16
aA bB 36jk -->   41
2 3 20     -->   <junk value>
10 10 100  -->   2
erdekhayser
sumber
Saya pikir STDIN mungkin akan lebih baik, dan keduanya akan baik-baik saja.
erdekhayser
@ MartinBüttner Jadi haruskah saya mengizinkan input dalam bentuk apa pun?
erdekhayser
1
Sebagai titik klarifikasi apa yang harus dilakukan jika banyak basis berlaku seperti contoh terakhir Anda (yang sekarang telah dihapus - itu 10 * 10 = 100) di mana juga berlaku di basis 10 dan memang basis lain yang Anda inginkan sebutkan ...
Chris
1
@Kay Jika saya mendefinisikan sistem posisi di pangkalan bsecara umum seperti a_0 b^0 + a_1 b^1 + a_2 b^2 + ...(di mana a_0digit paling signifikan) daripada basis 1 pasti masuk akal. Selain itu, kesimpulan OP juga akan mencakup basis 1 dalam pencarian jika digit hadiah terbesar adalah 0.
Martin Ender
2
Tentang pangkalan 1, unary adalah sistem angka. en.m.wikipedia.org/wiki/Unary_numeral_system
erdekhayser

Jawaban:

3

CJam, 52 51 48 byte

63,{_ea{i32b~\([G-35-9]=-_Xe>:X;}f%fbW%~*=\X>*}#

Uji di sini. Penguji online tidak mendukung input melalui ARGV. Alternatif terdekat adalah dengan memasukkan input seperti 6 9 42ke STDIN dan gunakan:

lS/:E;
63,{_E{i32b~\([G-35-9]=-_Xe>:X;}f%fbW%~*=\X>*}#

Ini mencetak -1jika tidak ada basis yang valid hingga 62 dapat ditemukan.

Terima kasih banyak kepada Peter untuk kode penguraian digit!

Saya memperbaiki banyak masalah yang menambahkan 14 byte ke hitungan. Penjelasan berikut masih untuk pengiriman asli saya, dan saya akan memperbaruinya besok.

63,{_ea{i32b~\([G-35-9]=-_Xe>:X;}f%fbW%~*=\X>*}#
63,                                              "Push the array [0 1 .. 62].";
   {                                          }# "Find the first index for which the block returns
                                                  a truthy value.";
    _                                            "Duplicate the current base.";
     ea                                          "Read ARGV into an array of strings.";
       {                        }f%              "Apply this block to each character.";
        i32b                                     "Convert to code point, and then to base-32. The
                                                  most significant digit now identifies the 'type'
                                                  of digit.";
            ~\(                                  "Unwrap the array. Swap the digits. Decrement.";
               [G-35-9]                          "Push array [16 -35 -9] of digit offsets.";
                       =-                        "Select the relevant offset and subtract it from 
                                                  the least significant digit.";
                         _                       "Duplicate the current digit D.";
                          Xe>:X;                 "X := max(X,D). X is predefined as 1.";
                                   fb            "Convert all numbers to the current base.";
                                     W%          "Reverse the list of numbers.";
                                       ~         "Unwrap the array.";
                                        *=       "Multiply factors. Check equality with product.";
                                          \      "Swap result with current base.";
                                           X>    "Ensure base is greater than X.";
                                             *   "Multiply boolean results.";

Indeks dicetak secara otomatis di akhir program.

Martin Ender
sumber
Dalam GS digit dapat diuraikan sebagai 32base~\[-16.35 9]=+. Saya tahu CJam memiliki konversi basis yang lebih pendek.
Peter Taylor
7

APL (Dyalog Unicode) , 30 byte SBCS

⊢{3e=×/2e←⍵⊥⍺:⍵⋄⍺∇⍵+1}1+⌈/∘,

Cobalah online!

Terima kasih kepada Adám atas bantuannya.

Penjelasan:

⊢{3e=×/2e←⍵⊥⍺:⍵⋄⍺∇⍵+1}1+⌈/∘,  
                               left argument ⍺: the vector (do nothing)
                        1+⌈/∘,  right argument ⍵: our starting base.
                             ,              start by flattening the matrix of arguments                               ⌈/                reduce by max (find the highest number)
                                           compose both of these together
                        1+                  increment by one
 {         ⍵⊥⍺         }        convert inputs to the current base
 {       e            }        store the converted values in 3
 {      2             }        take the first 2 values
 {    ×/               }        multiply them together (reduce-multiply)
 {  e=                 }        compare with e (the converted inputs)
 {3                   }        only keep the result of the comparison with the 3rd element (expected result)
 {             :⍵      }        if truthy, return the current base.
 {                    }        otherwise...
 {                ⍺∇⍵+1}        ...recurse with the base incremented

Kami menggunakan fungsi pembantu In,, untuk menerima input ke format yang lebih enak. Kalau tidak, input akan menerima matriks 3 kolom.

'3 9 42' akan memberi, misalnya (baca top-down kemudian kiri-ke-kanan):

0 0 4
3 9 2

Dan untuk 'aA bB 36jk'(sama di sini. aAdalah 10, badalah 11, Aadalah 36, dll)

 0  0  3
 0  0  6
10 11 19
36 37 20
Yang Mulia
sumber
2

Python 2 - 197 213

Sungguh monster ... (dibandingkan dengan CJam)

from string import*
I=raw_input()
x,y,z=I.split()
B=lambda s,b:sum(b**i*(digits+lowercase+uppercase).find(s[-i-1])for i in range(len(s)))
print([b for b in range(B(max(I),10)+1,62)if B(x,b)*B(y,b)==B(z,b)]+[0])[0]

Sayangnya intkonversi basis hanya dapat menangani basis hingga 36. Jadi saya perlu mengimplementasikannya sendiri. (Lihat solusi luar biasa ini .)

Falko
sumber
Apakah ini memastikan untuk tidak mengembalikan basis kurang dari atau sama dengan digit terbesar?
Martin Ender
@ MartinBüttner: Saya tidak yakin. Setidaknya tidak secara eksplisit. Apakah Anda memiliki test case di mana ini merupakan masalah? (Sebenarnya, membuat test case harus diurus oleh OP ...)
Falko
Coba 2 * 3 = 20 yang memiliki basis 3 dalam kasus kesalahan. 3 bukan digit dalam sistem angka terner.
kay
2

CJam, 53 byte

lA,s'{,97>+'[,65>+f#_$W=1e>)63,>_@Wa/W%f{fb~*=}1#\0+=

Mengambil tiga input dari STDIN suka

6 9 42

Mencetak 0jika produk di pangkalan apa pun tidak dimungkinkan

Akan mencoba untuk golf lebih jauh.

Coba di sini

Pengoptimal
sumber
1

JavaScript (E6) 129 139

Secara rekursif coba semua pangkalan dari 2 hingga 62, menghasilkan -1 jika tidak ada nilai ok.
Fungsi parseInt JavaScript berfungsi dengan basis hingga 36, ​​sehingga sedikit bantuan diperlukan untuk basis yang lebih besar.
Hati-hati, parameter x, y, z adalah string, bukan angka.
Ini lebih sulit daripada yang terlihat. Terima kasih kepada Martin karena telah menunjukkan bug dasar di versi pertama.

F=(x,y,z,b=2,N=n=>[for(d of(t=0,n))t=(v=parseInt(d,36)+(d>'@'&d<'a')*26)<b?t*b+v:NaN]&&t)=>b<63?N(x)*N(y)!=N(z)?F(x,y,z,b+1):b:-1

Kurang golf

F=(x,y,z,b=2,
   D=d=>parseInt(d,36)+(d>'@'&d<'a')*26, // parse a single digit
   N=n=>[for(d of(t=0,n))t=(v=D(d))<b?t*b+v:NaN]&&t // parse a string
)=>b<63?N(x)*N(y)!=N(z)?F(x,y,z,b+1):b:-1

Uji di konsol FireFox / FireBug.
Tes ini mencoba 1000 angka dengan basis yang berbeda (hingga 36, ​​bukan 62). Perlu dicatat bahwa pangkalan yang ditemukan bisa benar tetapi kurang dari pangkalan yang menghasilkan kasus uji.

for(i=0;i<1000;i++)
{
   x=Math.random()*100|0,y=Math.random()*100|0,z=x*y,b=Math.random()*35+2|0
   bx=x.toString(b),by=y.toString(b),bz=z.toString(b),
   nb=F(bx,by,bz)
   nx=parseInt(bx,nb),ny=parseInt(by,nb),nz=parseInt(bz,nb)
   // if (nx*ny != nz) // uncomment to se output for errors only
     console.log(x,y,z,'base '+b,bx,by,bz, 'found base '+nb,nx,ny,nz,nx*ny)
}
edc65
sumber
@ MartinBüttner parameternya adalah string (karena nilai yang mungkin adalah sesuatu seperti aBB 36jk ...). Klarifikasi dalam jawabannya.
edc65
Oh benar, itu masuk akal.
Martin Ender
1

Arang , 28 byte

I⌊Φ…⊕⍘⌈⁺⁺θηζ⁶²¦⁶³⁼×⍘θι⍘ηι⍘ζι

Cobalah online! Tautan adalah untuk mengucapkan versi kode. Output Nonejika tidak ada basis yang valid dapat ditemukan. Penjelasan:

         θ                      First input
        ⁺                       Concatenated with
          η                     Second input
       ⁺                        Concatenated with
           ζ                    Third input
      ⌈                         Maximum character (by ordinal)
     ⍘                          Converted from base
            ⁶²                  Literal 62
    ⊕                           Incremented
   …                            Range up to
               ⁶³               Literal 63
  Φ                             Filtered by
                    θ           First input
                   ⍘            Converted from base
                     ι          Current value
                  ×             Multiplied by
                       η        Second input
                      ⍘         Converted from base
                        ι       Current value
                 ⁼              Equals
                          ζ     Third input
                         ⍘      Converted from base
                           ι    Current value
 ⌊                              Minimum
I                               Cast to string
                                Implicitly print
Neil
sumber
Apakah mungkin untuk memiliki program TIO yang menggunakan kode aktual yang Anda posting?
mbomb007
@ mbomb007 Anda dapat mencobanya online! tapi AST Generator tampaknya berpikir adalah Anyuntuk beberapa alasan ...
Neil
0

Erlang (eskrip) - 200

main(X)->m(2,X).
m(63,_)->0;m(C,X)->try[F,G,I]=[c(0,C,Y)||Y<-X],I=F*G,io:fwrite("~p",[C])catch _:_->m(C+1,X)end.
c(A,B,[H|T])->D=H-if$A>H->$0;$a>H->29;0<1->87end,if D<B->c(A*B+D,B,T)end;c(A,_,_)->A.

Tambahkan dua baris baru terkemuka yang harus ada.

Dapat dibaca:

#!/usr/bin/env escript

main(Args) -> test(2, Args).

test(63, _) -> 0;
test(Base, Args) ->
    try
        [Factor1, Factor2, Product] = [convert(0, Base, Arg) || Arg <- Args],
        Product = Factor1 * Factor2,
        io:fwrite("~p", [Base])
    catch _:_ ->
        test(Base + 1, Args)
    end.

convert(Accumulator, Base, [Head|Tail]) ->
    Digit = Head - if Head < $A -> $0;
                      Head < $a -> $A - 10 - 26;
                      true      -> $a - 10
                   end,
    if Digit < Base ->
        convert(Accumulator * Base + Digit, Base, Tail)
    end;
convert(Accumulator, _, _) -> Accumulator.

Doa:

$ escript x.erl 6 9 42
13
$ escript -i x.erl a a 64
16
$ escript -i x.erl aA bB 36jk
41
$ escript -i x.erl 2 3 20
(no output)
$ escript -i x.erl 10 10 100
2
kay
sumber
Apakah ini memastikan untuk tidak mengembalikan basis kurang dari atau sama dengan digit terbesar?
Martin Ender
Ya, if Digit < Base -> … endbagian itu yang mengurusnya. Jika ifblok tidak memiliki cabang yang benar, maka pengecualian dilemparkan, yang tertangkap try … catch _:_ -> … end.
kay
0

Haskell 216 char (177?)

Mencoba bermain golf ini sebanyak mungkin. Jika impor dihitung, maka ini adalah kode terpendek saya (216)

import Data.Char
import Data.List
m=maximum
j[]=0;j(x:_)=x
f=reverse.map(\x->ord x-48)
g[]_=0;g(m:n)x=m+x*g n x
main=do
l<-getLine
let k@[x,y,z]=words l
print$j[n|n<-[2..62],g(f x)n*g(f y)n==g(f z)n,n>(m.map(m.f)$k)]

Namun, jika impor tidak dihitung, maka ini adalah versi terbaik saya (177):

import Data.Char
import Data.List
import Control.Applicative
m=maximum
j[]=0;j(x:_)=x
f=reverse.map(\x->ord x-48)
g[]_=0;g(m:n)x=m+x*g n x
main=words<$>getLine>>= \k@[x,y,z]->print$j[n|n<-[2..62],g(f x)n*g(f y)n==g(f z)n,n>(m.map(m.f)$k)]

Ini memperlakukan setiap angka sebagai P polinomial (x) di mana x adalah basis, dengan syarat bahwa tidak ada koefisien lebih besar dari x; Saya kemudian mengevaluasi polinomial atas setiap basis yang mungkin, berhenti ketika saya mencapai satu yang memenuhi persamaan P (x) * Q (x) = R (x). Aturan 'base lebih besar dari digit terbesar' diberlakukan dengan penjaga terakhir dalam pertandingan pola, yaitu n>(m.map(m.f)$k). Saya tahu bahwa tantangan golf yang berbeda dan pembuat tantangan yang berbeda memiliki kebijakan yang berbeda tentang impor vis-a-vis scoring, jadi ambil yang kedua dengan sebutir garam.

archaephyrryx
sumber
Solusinya masing-masing 216 dan 177 byte / karakter. Tapi solusi kedua tidak valid, karena impor yang dihitung kecuali OP secara eksplisit ditentukan lain, yang tidak terjadi di sini sejauh yang saya tahu.
nyuszika7h
0

Prolog - 195 byte

Ide dasarnya sama dengan jawaban Erlang saya:

:-use_module(library(main)).
main(A):-between(2,62,B),maplist(x(B),A,[F,G,P]),0is F*G-P,write(B).
c(I,B,Q,O):-Q=[H|T]->(H<65->D=48;H<97->D=29;D=87),H-D<B,c(I*B+H-D,B,T,O);O=I.
c(B)-->name,c(0,B).

Dapat dibaca:

:- use_module(library(main)).

main(Args) :-
    between(2, 62, Base),
    maplist(convert(Base), Args, [Factor1, Factor2, Product]),
    0 is Factor1 * Factor2 - Product,
    write(Base).

convert(Accumulator, Base, List, Output) :-
    List = [Head|Tail] ->
        (   Head < 65 -> Offset = 48;
            Head < 97 -> Offset = 29;
                         Offset = 87),
        Head - Offset < Base,
        convert(Accumulator * Base + Head - Offset, Base, Tail, Output);
    Output = Accumulator.

convert(Base, Input, Output) :-
    name(Input, List),
    convert(0, Base, List, Output).

Doa:

$ swipl -qg main x.pl 6 9 42
13
$ swipl -qg main x.pl aA bB 36jk
41
$ swipl -qg main x.pl 2 3 20
ERROR: Unknown message: goal_failed(main([2,3,20]))
kay
sumber