Apakah dua angka mengandung faktorial unik?

11

Pecah dua angka menjadi faktorial mereka; jika mereka berbagi, kembalikan nilai falsey. Jika tidak, kembalikan nilai yang sebenarnya. (terinspirasi oleh pertanyaan terakhir ini )

Dengan kata lain, tulis setiap nomor input sebagai jumlah faktorial (dari bilangan bulat positif) dengan cara serakah mungkin; mengembalikan nilai kebenaran jika tidak ada faktorial yang muncul di kedua representasi, nilai falsey sebaliknya.

Contoh

Diberikan 20 dan 49:

20 = 3! + 3! + 3! + 2!
49 = 4! + 4! + 1!

Tidak ada faktorial yang muncul di kedua representasi, jadi kembalikan nilai yang sebenarnya.

Diberikan 32 dan 132:

132 = 5! + 3! + 3!
 32 = 4! + 3! + 2!

3! muncul di kedua representasi, jadi kembalikan nilai falsey.

I / O

Input dan output dapat melalui sarana standar apa pun .

Input akan selalu berupa dua bilangan bulat tidak negatif; tidak ada batas atas pada bilangan bulat ini selain dari yang dibutuhkan bahasa Anda.

Output harus berupa nilai truey atau falsey . Nilai-nilai ini tidak harus konsisten untuk input yang berbeda, selama setiap output benar / salah.

Uji Kasus

Jika satu input adalah 0, jawabannya akan selalu benar. Kasus uji kebenaran lainnya:

{6, 3}, {4, 61}, {73, 2}, {12, 1}, {240, 2}, {5, 264}, {2, 91}, {673, 18},
 {3, 12}, {72, 10}, {121, 26}, {127, 746}

Jika kedua input bilangan bulat ganjil, atau jika kedua input bilangan bulat positif yang sama, maka output akan selalu salah. Kasus uji falsey lainnya:

{8, 5}, {7, 5}, {27, 47}, {53, 11}, {13, 123}, {75, 77}, {163, 160}, {148, 53},
 {225, 178}, {285, 169}, {39, 51}, {207, 334}, {153, 21}, {390, 128}, {506, 584},
 {626, 370}, {819, 354}

Ini kode-golf , byte paling sedikit menang!

code-golf arithmetic decision-problem integer factorial Greg Martin
sumber
"tulis setiap nomor input sebagai jumlah faktorial (dari bilangan bulat positif) dengan cara serakah mungkin" bukankah Anda maksudkan cara yang paling malas sebagai gantinya?
user41805
4
@KritixiLithos no. Dia merujuk pada kelas algoritma yang dikenal sebagai algoritma serakah, yang bekerja dengan memaksimalkan beberapa metrik setelah setiap langkah. Seperti dalam, selalu mengambil sebanyak yang mereka bisa.
John Dvorak

Jawaban:

9

Jelly , 7 byte

Æ!ṠḄ&/¬

Cobalah online!

Bagaimana itu bekerja

Æ!ṠḄ&/¬  Main link. Argument: (x, y) (pair of integers)

Æ!       Convert x and y to factorial base.
  Ṡ      Apply the sign function to each digit.
   Ḅ     Unbinary; convert each resulting Boolean array from base 2 to integer.
    &/   Reduce the resulting pair of integers by bitwise AND.
      ¬  Take the logical NOT of the result.
Dennis
sumber
Æ!tampaknya sangat berguna dalam skenario tertentu.
Magic Gurita Guci
Adakah yang bisa diperoleh dengan mencoba melipatgandakan daftar basis faktorial secara langsung, tanpa mengambil tanda?
Greg Martin
@GregMartin kurasa tidak. Susunan digit harus empuk atau terpotong dengan panjang yang sama, yang mungkin akan menelan biaya lebih banyak byte daripada menghemat.
Dennis
3

Python 3 , 93 91 byte

lambda a,b:k(a)&k(b)=={0}
k=lambda t,n=1,a=1:{t}&{0}or a*n>t and{a-1}|k(t-n)or k(t,n*a,a+1)

Cobalah online!

ovs
sumber
3

Python 2 , 47 byte

h=lambda a,b,d=2:a<1or a%d*(b%d)<h(a/d,b/d,d+1)

Cobalah online!

Tidak
sumber
Saya suka solusi ini. Bisakah Anda membubuhi keterangan dengan sedikit pemikiran?
Chas Brown
2

JavaScript (ES6), 71 byte

(a,b,g=(n,e=1,f=1)=>n>=f&&g(n,++e,f*e)+((n/f|0)%e&&1<<e))=>!(g(a)&g(b))

Bilangan bulat JavaScript terbatas pada presisi 53 bit, yang hanya cukup untuk 18!; ini berarti bahwa saya dapat menggunakan topeng 18 bit untuk melacak faktorial mana yang diperlukan.

Neil
sumber
2

PHP, 109 Bytes

for(;$a?:$a=$argv[++$i];$a-=$r[$i][]=$f,$i<2?:$t+=in_array($f,$r[1]))for($c=$f=1;($a/$f*=$c)>=++$c;);echo!$t;

Cobalah online!

Jörg Hülsermann
sumber
0

Mathematica, 73 byte

F[x_]:=First@IntegerPartitions[x,99,Range[99]!];!IntersectingQ[F@#,F@#2]&

formulir input

[x1, x2]

J42161217
sumber
Saya mendapatkan beberapa kesalahan saat menguji ini ...
Scott Milner
Cukup ketik di akhir [x1, x2]
J42161217
Ah. Saya memasukkan daftar, bukan dua bilangan bulat terpisah. Anda dapat bermain golf lebih jauh dengan ±x_:=First@IntegerPartitions[x,99,Range[99]!];!IntersectingQ[±#,±#2]&[4,61](69 byte). Dalam penyandian ISO 8859-1, ±adalah satu byte.
Scott Milner
0

C, 122 119 byte

G(q,i){return gamma(q+1)>i?gamma(q):G(q+1,i);}
Q(a,b,u,v){while(a&&b){a-=u=G(1,a);b-=v=G(1,b);if(a==b)exit();}exit(0);}

Qadalah fungsi utama. Itu harus dipanggil dengan tepat dua nilai integer positif. Ini keluar dengan kode keluar dari 0untuk truthy dan 1untuk falsy.

Meskipun ini sepertinya tidak bekerja pada TIO, ini bekerja pada sistem saya dengan Homebrew disediakan gcc 7.1.0.

Saya belum Cbermain golf cukup lama, jadi tips bermain golf sangat dihargai!

R. Kap
sumber