Keine Co-Prime-Nachbarn

33

Bei einer Liste positiver Ganzzahlen wird ausgegeben, ob jedes benachbarte Ganzzahlpaar einen Primfaktor gemeinsam hat. Mit anderen Worten, die Ausgabe ist genau dann wahr, wenn keine zwei benachbarten Ganzzahlen in der Liste Co-Primzahlen sind.

Mit anderen Worten: Geben Sie bei einer Liste positiver Ganzzahlen [a 1 a 2 … a n ] aus , ob

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

Die Liste enthält immer mindestens zwei Elemente (n ≥ 2).

Jedoch…

Diese Herausforderung hat auch eine : Die Codepunkte in Ihrer Antwort (in welcher Codepage auch immer) müssen die Bedingung erfüllen, auf die Ihr Programm prüft.

Zum Beispiel print 2ist ein gültiges Programm. Als eine Liste von Unicode-Codepunkten ist es [112 114 105 110 116 32 50] , das diese Bedingung erfüllt: 112 und 114 teilen sich einen Faktor von 2 ; und 114 und 105 teilen sich einen Faktor von 3 usw.

mainKann jedoch in einem gültigen Programm nicht vorkommen (sorry!), Da die Unicode-Codepunkte von mund a, nämlich 109 und 97 , Coprime sind. (Zum Glück muss Ihr Beitrag kein vollständiges Programm sein!)

Ihr Programm darf nicht den Codepunkt 0 enthalten.

Testfälle

Wahrheit:

[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

Falsch:

[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

Das ist : Der kürzeste Code in Bytes gewinnt.

Lynn
quelle
8
Für alle , diese Herausforderung in einer normalen Programmiersprache versucht, dies ist eine Liste von Zeichen , die prime Codepoints in ASCII haben: %)+/5;=CGIOSYaegkmq\DEL.
Cristian Lupascu
@Lynn Müssen Wahrheiten konsistent sein?
H.PWiz
1
@ H.PWiz Nö! -
Lynn
Eigentlich wollte ich, dass dies für einige normale (nicht-golf) langs machbar ist, und ich war hoffnungsvoll, als ich bemerkte, dass print 2das gültig ist, aber );=aePrime zu sein ist wirklich hart, das habe ich nicht in Betracht gezogen ... Ich frage mich, ob so etwas wie Haskell das kann konkurrieren?
Lynn
Diese Einschränkung ist einfacher als die Umkehrung dieser Frage . Angenommen, niemand verwendet 0x02 Byte. Diese Frage wird in Mathematica, Logo, Haskell, Python, Perl und TI-BASIC mit einer ungültigen Antwort beantwortet. Dieser hat bereits einen Haskell, ich denke, Mathematica ist unmöglich, aber Logo scheint sehr wahrscheinlich möglich zu sein, obwohl ich die Lösung noch nicht erstellt habe.
User202729

Antworten:

15

MATL , 14 Bytes

!TM1*Zdl2$Xdl-

Dies gibt einen nicht leeren Spaltenvektor von Zahlen ungleich Null als wahr oder einen Vektor mit mindestens einem Null-Eintrag als falsch aus.

Erläuterung

!     % 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
quelle
4
Herzlich Glückwunsch zu einer Antwort , die nicht zufrieden ist mit eingeschränkter Quelle Anforderung!
Erik der Outgolfer
13

Haskell , 103 100 Bytes

BEARBEITEN:

  • -3 Bytes: Mit einem d<-fzGuard werden die letzten beiden Zeilen zusammengeführt und gekürzt.

fist die Hauptfunktion, die eine Liste von ganzen Zahlen aufnimmt und a zurückgibt Bool.

Beachten Sie, dass die ersten beiden ԁs (nur) kyrillische (Komi) Unicode-Zeichen sind und vor dem ersten ein Tabulatorzeichen steht.

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

Probieren Sie es online! oder testen Sie es an sich.

Wie es funktioniert

  • fist die Hauptfunktion. Alles, was es tut, ist, sein Argument ԁin eine Singleton-Liste zu packen (weil der ASCII-Primärwert von )Klammern viel umständlicher zu verwenden ist als eckige Klammern) und damit aufzurufen zbund ein Dummy-Argument (die Haskell-Funktion hat idzufällig genau die richtigen Zeichen, die passen) Hier).
    • Dasselbe Zeichen neben beidem passt, =]ist mit normalem ASCII nicht möglich, daher wird das Argument mit dem 2-Byte-Unicode-Zeichen CYRILLIC SMALL LETTER KOMI DE (ԁ), dem Codepunktwert, benannt 3*7*61=U+0501, der zu all diesen und passt [.
      • Da der Codepunkt nicht gerade ist (die kleinste Option, bei der es sich um einen gültigen Bezeichner handelt und die auch drei Bytes verwendet), ist die Verwendung eines Tabulatorzeichens anstelle eines Leerzeichens erforderlich.
      • Eine sieben Bytes länger reine ASCII - Option ist das Argument zu benennen: f fz|bf<-fz=zb[bf]fz.
  • zbEs werden zwei Argumente verwendet, eine Singleton-Liste, deren Element die rekursive Liste der reellen Zahlen ist, und ein Dummy-Argument fz, das nur benötigt wird, um ein zvor den =s der Funktion zu erhalten .
    • Wenn die innere Liste wenigstens zwei Elemente hat, die Funktion zwird mit den ersten beiden (benannt genannt hund p), und wenn das zurückkehrt True, zbrekursiv auf den Schwanz p:lvon der Liste.
    • Wenn die innere Liste weniger als zwei Elemente enthält, wird zbzurückgegeben True. Da =dem Zeichen gefolgt werden muss z, ist die einfachste Möglichkeit, einen Aufruf der zFunktion zu verwenden, von der bekannt ist, dass sie zurückgibt True.
  • zNimmt zwei Argumente und berechnet rekursiv ihren größten gemeinsamen Divisor mithilfe der Subtraktion (jede andere relevante Ganzzahldivision oder gcd-Funktion ist nicht verfügbar) und gibt zurück, Truewenn sie größer als eins ist.
    • Die Rekursion endet mit dem ersten Argument 0, wobei das zweite Argument der gcd ist. In dieser Zeile wird auch das zweite Argument genannt z. Das Zeichen 1ist hier unangenehm und z^0wird verwendet, um die Nummer eins zu bekommen.
    • Ist das erste Argument fkleiner als das zweite fz, werden sie vertauscht und zrekursiv.
    • Andernfalls wird das kleinere Argument vom größeren abgezogen und dann zwiederholt (auch das Vertauschen der Argumente, obwohl dies nur zur Vermeidung von Klammern dient).
Ørjan Johansen
quelle
2
Ich wusste , dass es eine Nicht-Golf-Sprache geben musste, die es schaffen konnte!
Lynn
2
@Lynn Es hilft Haskell wirklich bei dieser Art von Herausforderung, dass es eine ziemlich ausdrucksstarke syntaktische Teilmenge mit nur einem Zeichen Token hat. Das ist ungefähr auf halbem Weg zu einer Golfsprache, denke ich.
Ørjan Johansen
Sind das wegen der Kyrillik wirklich 100 Bytes? Das Code Golf Graduation-UserScript gibt 102 UTF-8-Bytes an, aber ich weiß nicht, ob es korrekt ist / ob dies der richtige Weg ist, die Bytes hier zu zählen. Egal wie viele Bytes, es ist wirklich beeindruckend!
Mark S.
1
@MarkS. TIO meldet 100 Bytes (und 98 Zeichen). Ich vermute, Sie wurden von dem Tabulator-Zeichen erwischt, das SE als 3 Leerzeichen anzeigt (das dann als solches kopiert wird). Ich glaube, ich habe jemanden gesehen, der Pre-Tags verwendet, um dies zu vermeiden. Lassen Sie mich versuchen, das Problem zu beheben.
Ørjan Johansen
@MarkS. Getan. Obwohl ich vermute, dass das das Userscript nur noch mehr verwirren könnte.
Ørjan Johansen
10

05AB1E , 8 Bytes

Code

ü‚ÒüÃP≠P

Verwendet die 05AB1E- Codierung , die die folgende Liste von Codepunkten enthält:

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

Probieren Sie es online! oder Überprüfen Sie den Quellcode!

Erläuterung

Da der gcd-Operator ( ¿) einen Prim-Code-Punkt hat, musste ich nach anderen Möglichkeiten suchen, um die Koprimalität zu überprüfen:

ü‚          # 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
quelle
Welche Codepunkte enthält die Codepage von 05AB1E? Können Sie sie zur Antwort hinzufügen?
Mr. Xcoder
@ Mr.Xcoder hinzugefügt
Adnan
Irgendein Grund für Òvorbei f?
Magic Octopus Urn
10

Schale , 8 Bytes

Für Wahrheitseingaben wird eine positive Ganzzahl zurückgegeben, für Falsy wird 0 zurückgegeben

←▼`Ṡt(ż⌋

Probieren Sie es online! und an eigenen Codepunkten getestet

Verwendet die Codepage von Husk

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

Erläuterung

          -- 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.PWiz
quelle
Wie heißt die Notation, die Sie in der Erklärung verwenden ? Ich sehe es auch in den Dokumenten in der "Typ" -Spalte auf der Befehlsseite und kann mich nicht darum kümmern, also möchte ich es nachschlagen, damit ich es vielleicht lernen kann.
Jonathan Allan
@ JonathanAllan Das ist die Definition der Funktion in Haskells Syntax. Es übersetzt ungefähr Ṡ(f,g,x) = f(g(x),x)in gängigere Sprachen.
Zgarb
Quelle Link
H.PWiz
Wenn es jedoch umgedreht wird, wird es`Ṡ g f x = Ṡ f g x = f (g x) x
H.PWiz
1
@JonathanAllan Wenn Sie sich dem Chatroom von Husk anschließen , können wir versuchen, es dort besser zu erklären.
Zgarb
5

Japt , 8 7 Bytes

äj d¹¥Z

Online testen!

Code Punkte:

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

Erläuterung

 ä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
ETHproductions
quelle
5

Jelly , 11 9 Bytes

,Pnælð2\P

2 Bytes dank @ Jonathan Allan gespeichert .

Probieren Sie es online!

Jelly hat eine eigene Codepage und die Codepunkte der einzelnen Zeichen sind

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

Hiermit wird geprüft, ob es sich um Nicht-Coprime-Nummern handelt lcm(a, b) != a*b. Es könnte eine kürzere Lösung geben, da ich nur nach Zeichen mit geraden Codepunkten gefiltert habe.

Erläuterung

,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
Meilen
quelle
Genius! Das ist unglaublich: O
Mr. Xcoder
,ist auch so, dass Sie æln,P¥ð2\für zwei weniger tun können . Edit: Ich habe das Trailing fallen gelassen P, mach das weniger: p)
Jonathan Allan
Oh ja, tauschen Sie die Argumente sogar :)
Jonathan Allan
5

TI-BASIC, 38 Bytes

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

TI-BASIC ist wie hier aufgeführt in Ein-Byte- oder Zwei-Byte-Token unterteilt .

Die schwierigsten Teile dieser Lösung waren:

  1. Das Komma-Token ist eine Primzahl (43) und zwingt mich, es mit einem Vielfachen von 43 zu umgeben (in diesem Fall das V-Token, das 86 ist).

  2. Der gcd (Token ist eine große Primzahl (47881), was bedeutet, dass er überhaupt nicht verwendet werden kann.

Die Token für dieses Programm werden ausgegeben an:

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

Erläuterung

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
quelle
3

Pyth , 15 Bytes

&F.bPiFNP.TtBQQ

Probieren Sie es hier aus oder testen Sie die Test Suite.

Dies ist eine Zusammenarbeit zwischen Erik the Outgolfer und Mr. Xcoder . Gibt einen inkonsistenten Wert (nicht leere Liste) für truthy und die leere Liste für falsy zurück.


ASCII-Werte

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

Welche teilen die folgenden Faktoren:

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

Erläuterung

&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)

Ohne die wäre dies eine 7 5-Byte-Version gewesen, die dieselbe Aufgabe erfüllt (-2 dank FryAmTheEggman ):

-1iVt

Erläuterung

-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
quelle
Warum brauchst du aus Neugier das Qs am Ende?
ETHproductions
@ETHproductions Da .bes variable Aritäten gibt und implizite Eingaben verwendet, wird die niedrigste (1) ausgewählt, anstatt die beabsichtigte (2).
Erik der Outgolfer