Tidak ada tetangga tetangga

33

Diberikan daftar bilangan bulat positif, output apakah setiap pasangan bilangan bulat yang berdekatan di dalamnya berbagi faktor prima. Dengan kata lain, keluaran truthy jika dan hanya jika ada dua bilangan bulat tetangga di daftar adalah co-prime.

Dalam istilah lain: diberi daftar bilangan bulat positif [a 1 a 2 ... a n ] , hasilkan apakah

       gcd (a 1 , a 2 )> 1 && gcd (a 2 , a 3 )> 1 && ... && gcd (a n − 1 , a n )> 1.

Daftar akan selalu mengandung setidaknya dua elemen (n ≥ 2).

Namun…

Tantangan ini juga : codepoints dalam jawaban Anda (codepage apa pun itu berada) harus memenuhi kondisi program Anda memeriksa.

Misalnya, print 2adalah program yang valid. Sebagai daftar titik kode Unicode [112 114 105 110 116 32 50] , yang memenuhi kondisi ini: 112 dan 114 berbagi faktor 2 ; dan 114 dan 105 berbagi faktor 3 , dll.

Namun, tidakmain dapat muncul dalam program yang valid (maaf!), Karena titik kode Unicode dan , yaitu 109 dan 97 , adalah coprime. (Syukurlah, kiriman Anda tidak harus berupa program lengkap!)ma

Program Anda tidak diizinkan mengandung codepoint 0.

Uji kasus

Benar:

[6 21] -> 1
[502 230 524 618 996] -> 1
[314 112 938 792 309] -> 1
[666 642 658 642 849 675 910 328 320] -> 1
[922 614 530 660 438 854 861 357 477] -> 1

Falsy:

[6 7] -> 0
[629 474 502 133 138] -> 0
[420 679 719 475 624] -> 0
[515 850 726 324 764 555 752 888 467] -> 0
[946 423 427 507 899 812 786 576 844] -> 0

Ini adalah : kode terpendek dalam byte menang.

Lynn
sumber
8
Untuk siapa pun yang mencoba tantangan ini dalam bahasa pemrograman yang normal, ini adalah daftar karakter yang memiliki codepoints utama dalam ASCII: %)+/5;=CGIOSYaegkmq\DEL.
Cristian Lupascu
@ Lynn Do Truthys harus konsisten?
H.PWiz
1
@ H.PWiz Tidak! -
Lynn
Saya sebenarnya bermaksud ini bisa dilakukan untuk beberapa permainan normal (non-golf), dan saya merasa penuh harapan ketika saya menyadari bahwa print 2itu valid, tetapi );=aemenjadi yang utama sangat sulit, saya tidak mempertimbangkan itu ... Saya ingin tahu apakah sesuatu seperti Haskell dapat bersaing?
Lynn
Pembatasan ini lebih mudah daripada kebalikan dari pertanyaan ini , anggap tidak ada yang menggunakan 0x02 byte. Pertanyaan itu mendapatkan jawaban valid nongolf dalam Mathematica, Logo, Haskell, Python, Perl, TI-BASIC. Yang ini sudah punya Haskell, saya pikir Mathematica tidak mungkin, tetapi Logo kelihatannya sangat mungkin, walaupun saya belum selesai membuat solusi.
user202729

Jawaban:

15

MATL , 14 byte

!TM1*Zdl2$Xdl-

Ini menghasilkan vektor kolom non-kosong dari angka bukan nol sebagai kebenaran, atau vektor yang mengandung setidaknya nol entri sebagai kepalsuan.

Penjelasan

!     % Implicit input. Transpose
TM    % Push input to latest function again
1*    % Multiply by 1 (does nothing, but matches factors)
Zd    % Compute gcd with broadcast: matrix of gcd of all pairs
l     % Push 1
2$    % The next function will use 2 inputs
Xd    % Extract diagonal 1 (i.e. that below the main diagonal) from the matrix
l-    % Subtract 1 from each entry. Implicitly display
Luis Mendo
sumber
4
Selamat atas jawaban yang tidak memuaskan dibatasi-sumber kebutuhan!
Erik the Outgolfer
13

Haskell , 103 100 byte

EDIT:

  • -3 byte: Digunakan d<-fzpenjaga untuk menggabungkan dan mempersingkat dua baris terakhir.

fadalah fungsi utama, yang mengambil daftar bilangan bulat dan mengembalikan a Bool.

Perhatikan bahwa dua yang pertama ԁ(hanya) adalah karakter Unicrill Cyrillic (Komi), dan ada karakter tab sebelum yang pertama.

f	ԁ=zb[ԁ]id
zb[h:p:l]fz=z h p&&zb[p:l]fz
zb l fz=z 0 2
z 0z=z>z^0
z f fz|f<fz=z fz f|d<-fz=z d$f-d

Cobalah online! atau mengujinya sendiri.

Bagaimana itu bekerja

  • fadalah fungsi utama. Yang dilakukannya hanyalah membungkus argumennya ԁdalam daftar tunggal (karena nilai ASCII utama )membuat kurung lebih canggung daripada kurung kotak) dan memanggilnya zbdengan argumen dummy (fungsi Haskell idkebetulan memiliki karakter yang tepat untuk menyesuaikannya. sini).
    • Mendapatkan karakter yang sama agar sesuai selain keduanya =]tidak mungkin dengan ASCII biasa, sehingga argumen tersebut dinamai dengan karakter Unicode 2-byte CYRILLIC SMALL LETTER KOMI DE (ԁ), nilai codepoint 3*7*61=U+0501, yang cocok dengan semua itu dan [.
      • Karena codepoint tidak genap (opsi terkecil yang merupakan pengidentifikasi hukum dan juga bahkan menggunakan tiga byte), ini diperlukan menggunakan karakter tab alih-alih spasi sebelum itu.
      • Sebuah pilihan ASCII tujuh byte lagi polos adalah untuk mengubah nama argumen: f fz|bf<-fz=zb[bf]fz.
  • zbmengambil dua argumen, daftar tunggal yang elemennya adalah daftar nyata dari angka yang berulang, dan argumen bodoh fzhanya perlu untuk mendapatkan zsebelum fungsi itu =.
    • Ketika daftar dalam memiliki setidaknya dua elemen, fungsinya zdipanggil dengan dua elemen pertama (bernama hdan p), dan jika itu kembali True, zbberulang pada ekor p:ldaftar.
    • Jika daftar dalam memiliki kurang dari dua elemen, zbkembali True. Karena =perlu diikuti oleh karakter z, cara paling sederhana untuk melakukan ini adalah dengan menggunakan panggilan zfungsi yang dikenal kembali True.
  • zmengambil dua argumen dan menghitung pembagi umum terbesar mereka secara rekursif menggunakan pengurangan (setiap divisi integer atau fungsi gcd lain yang relevan tidak tersedia), mengembalikan Truejika lebih besar dari satu.
    • Rekursi berakhir ketika argumen pertama adalah 0, dengan argumen kedua adalah gcd. Pada baris ini argumen kedua juga disebutkan z. Karakternya 1canggung di sini sehingga z^0digunakan untuk mendapatkan yang nomor satu.
    • Kalau tidak, jika argumen pertama flebih kecil dari yang kedua fz, mereka bertukar dan zberulang.
    • Jika tidak, argumen yang lebih kecil dikurangkan dari yang lebih besar, kemudian zberulang (juga bertukar argumen, meskipun itu hanya untuk menghindari tanda kurung.)
Ørjan Johansen
sumber
2
Saya tahu harus ada bahasa non-golf yang bisa berhasil!
Lynn
2
@ Lynn Ini benar-benar membantu Haskell dalam tantangan semacam ini yang memiliki subset sintaksis yang cukup ekspresif hanya dengan token karakter tunggal. Itu kira-kira setengah dari bahasa golf, saya kira.
Ørjan Johansen
Karena Cyrillic, apakah ini benar-benar 100 byte? The Kode Golf Wisuda userscript melaporkan 102 UTF-8 byte, tapi saya tidak tahu apakah itu / akurat itulah cara yang tepat untuk menghitung byte sini. Tidak peduli berapa banyak byte, ini benar-benar mengesankan!
Mark S.
1
@Tanda. TIO melaporkan 100 byte (dan 98 karakter). Saya menduga Anda tertangkap oleh karakter tab, yang ditampilkan SE sebagai 3 spasi (yang kemudian akan disalin seperti itu). Saya pikir saya telah melihat seseorang menggunakan tag pra untuk menghindarinya, izinkan saya mencoba memperbaikinya.
Ørjan Johansen
@Tanda. Selesai Meskipun saya curiga itu mungkin hanya membingungkan userscript itu.
Ørjan Johansen
10

05AB1E , 8 byte

Kode

ü‚ÒüÃP≠P

Menggunakan penyandian 05AB1E , yang memberi kami daftar poin kode berikut:

hex: [0xFC, 0x82, 0xD2, 0xFC, 0xC3, 0x50, 0x16, 0x50]
dec: [252,  130,  210,  252,  195,  80,   22,   80]

Cobalah online! atau Verifikasikan kode sumber!

Penjelasan

Karena operator gcd ( ¿) memiliki titik kode utama saya harus mencari cara lain untuk memeriksa coprimality:

ü‚          # Get an array of adjacent pairs of the input
  Ò         # Factorize both elements of each pair in the array
   üà       # For each pair, get the intersection of both prime factorization lists
     P      # Product of each intersection (this leaves 1 when there is no intersection)
      ≠     # Check for each element whether it does not equal 1
       P    # Product of the booleans
Adnan
sumber
Poin kode apa yang ada di halaman kode 05AB1E ini? Bisakah Anda menambahkannya ke dalam jawabannya?
Tn. Xcoder
@ Mr.Xcoder menambahkan
Adnan
Ada alasan untuk Òlebih f?
Magic Octopus Mm
10

Sekam , 8 byte

Untuk input yang sebenarnya mengembalikan bilangan bulat positif, untuk Falsy mengembalikan 0

←▼`Ṡt(ż⌋

Cobalah online! dan Diuji pada codepoint sendiri

Gunakan codepage Husk

Source -- [ ←  , ▼  , `  , Ṡ  , t  , (  , ż  , ⌋  ]
Hex    -- [0x06,0xbd,0x60,0xd0,0x74,0x28,0xeb,0x8d]
Dec    -- [6   ,189 ,96  ,208 ,116 ,40  ,235 ,141]

Penjelasan

          -- implicit input, e.g                                  [63,36,18,3]
  `       -- flip the args of the next function
   Ṡ      -- some combinator (Ṡ f g x = f (g x) x)
    t     -- tail                                                 [36,18,3]
      ż   -- zipWith (note, keeps trailing elems of longer list)  [(63,36),(36,18),(18,3),(3)]
       ⌋  -- gcd                                                  [9,9,3,3]
     (    -- used just to match restricted source criteria
 ▼        -- minimum of the list                                    3
←         -- minus 1                                                2
H.Piz
sumber
Untuk apa notasi yang Anda gunakan dalam penjelasan itu ? Saya melihatnya di dokumen juga di kolom "ketik" pada halaman perintah dan tidak bisa memahaminya, jadi ingin mencarinya sehingga saya bisa mempelajarinya.
Jonathan Allan
@ JonathanAllan Itulah definisi fungsi dalam sintaksis Haskell. Ini diterjemahkan secara kasar ke Ṡ(f,g,x) = f(g(x),x)dalam bahasa yang lebih umum.
Zgarb
link sumber
H.PWiz
Meskipun, ketika dibalik, itu menjadi`Ṡ g f x = Ṡ f g x = f (g x) x
H.PWiz
1
@JonathanAllan Jika Anda bergabung dengan ruang obrolan Husk , kami dapat mencoba menjelaskannya dengan lebih baik di sana.
Zgarb
5

Japt , 8 7 byte

äj d¹¥Z

Uji secara online!

Poin kode:

Char    ä   j       d   ¹   ¥   Z
Hex    e4  6a  20  64  b9  a5  5a
Dec   228 106  32 100 185 165  90

Penjelasan

 äj d¹ ¥ Z
Uäj d) ==Z
             Implicit: U = input array, Z = 0
Uä           For each pair of items in the array:
  j            Return whether the two items are coprime.
    d)       Return true if any items are truthy, false otherwise.
       ==Z   Return whether this is equal to 0 (false -> true, true -> false).
             Implicit: output result of last expression
Produksi ETH
sumber
5

Jelly , 11 9 byte

,Pnælð2\P

Disimpan 2 byte berkat @ Jonathan Allan .

Cobalah online!

Jelly memiliki halaman kode sendiri dan codepoint masing-masing karakter

Chr Hex Dec
,   2c   44
P   50   80
n   6e  110
æ   16   22
l   6c  108
ð   18   24
2   32   50
\   5c   92
P   50   80

Ini menguji untuk nomor non-coprime dengan memeriksa jika lcm(a, b) != a*b. Mungkin ada solusi yang lebih pendek karena saya hanya memfilter untuk karakter dengan codepoint bahkan.

Penjelasan

,Pnælð2\P  Input: array A
      2\   For each overlapping sublist of size 2
     ð       Reduce it using this dyad
,              Pair
 P             Product
  n            Not equals, 1 if true else 0
   æl          LCM
        P  Product
mil
sumber
Jenius! Ini luar biasa: O
Tn. Xcoder
,demikianlah yang dapat Anda lakukan æln,P¥ð2\untuk dua lebih sedikit. Sunting: Saya menghilangkan jejaknya P, membuatnya kurang: p)
Jonathan Allan
Oh ya, bertukar argumen bahkan :)
Jonathan Allan
5

TI-BASIC, 38 byte

Input L1:ΔList(cumSum(L1:augment(Ans+V,V+{0:2>sum(AnsL1=lcm(Ans+V,V+L1

TI-BASIC adalah tokenized menjadi token satu atau dua byte, seperti yang tercantum di sini .

Bagian tersulit dari solusi ini adalah:

  1. Tanda koma adalah bilangan prima (43), memaksa saya untuk mengelilinginya dengan kelipatan 43 (dalam hal ini token V, yaitu 86).

  2. Gcd (token adalah bilangan prima besar (47881), yang berarti tidak bisa digunakan sama sekali.

Token untuk program ini adalah:

token     hex     dec
Input     0xDC    220
L1        0x5D00  23808
:         0x3E    62
ΔList(    0xBB2C  47916
cumSum(   0xBB29  47913
L1        0x5D00  23808
:         0x3E    62
augment(  0x14    20
Ans       0x72    114
+         0x70    112
V         0x56    86
,         0x2B    43
V         0x56    86
+         0x70    112
{         0x08    8
0         0x30    48
:         0x3E    62
2         0x32    50
>         0x6C    106
sum(      0xB6    182
Ans       0x72    114
L1        0x5D00  23808
=         0x6A    106
lcm(      0xBB08  47880
Ans       0x72    114
+         0x70    112
V         0x56    86
,         0x2B    43
V         0x56    86
+         0x70    112
L1        0x5D00  23808

Penjelasan

Input L1:                   Prompt the user to input L1.

ΔList(cumSum(L1:            Take the differences of the prefix sum of L1,
                            which in effect removes the first element (result in Ans).

augment(Ans+V,V+{0:         Append a 0 to the end of Ans.
                            V defaults to 0, so adding it is a no-op.
                            Ans now holds L1 shifted to the left by one element,
                            with a 0 shifted in.

      AnsL1=lcm(Ans+V,V+L1  Take the least common multiple of each corresponding element
                            of Ans and L1, and check if each is equal to their product.
                            This returns a list of booleans, each 1 corresponding to
                            a co-prime pair. The last element (having been paired with 0)
                            will always be 1.

2>sum(                      Returns 1 if there is at most one 1 in the list, else 0.
                            Since the last element is always 1, this means
                            we return 1 only if there are no co-prime pairs.
calc84maniac
sumber
3

Pyth , 15 byte

&F.bPiFNP.TtBQQ

Cobalah di sini atau Lihat Test Suite.

Ini adalah upaya kolaborasi antara Erik the Outgolfer dan Mr. Xcoder . Mengembalikan nilai yang tidak konsisten (daftar tidak kosong) untuk kebenaran, dan daftar kosong untuk falsy.


Nilai-nilai ASCII

[38, 70, 46, 98, 80, 105, 70, 78, 80, 46, 84, 116, 66, 81, 81]

Yang memiliki faktor-faktor berikut:

[2, 2, 2, 2, 5, 35, 2, 2, 2, 2, 4, 2, 3, 81]

Penjelasan

&F.bPiFNP.TtBQQ
           tBQ   Return [Q, Q[1:]] (Q = eval first line of input)
         .T      Transpose ^ without cropping absences
        P        Remove last element of ^
  .b          Q  Map in parallel on ^ (N) and Q (Y, ignored)
     iFN           GCD of N
    P              Prime factors of ^ (P(1) = [])
&F               Left fold (reduce) the result of the map with Logical AND (short-circuiting)

Tanpa persyaratan , ini akan menjadi versi 7 5-byte yang menyelesaikan tugas yang sama (-2 terima kasih kepada FryAmTheEggman ):

-1iVt

Penjelasan

-1iVtQQ  Implicit QQ at the end
    tQ   Return Q[1:]
  iV  Q  Vectorized GCD on ^ and Q
-1       Remove every element of ^ from [1] (implicit singleton)
Erik the Outgolfer
sumber
Karena penasaran, mengapa Anda membutuhkan huruf Qs pada akhirnya?
ETHproduk
@ ETHproductions Karena .bmemiliki variabel arities, dan menggunakan input implisit berarti akan memilih yang terendah (1) alih-alih yang dimaksudkan (2).
Erik the Outgolfer