No hay vecinos co-prime

33

Dada una lista de enteros positivos, muestra si cada par de enteros adyacentes comparte un factor primo. En otras palabras, dar salida a la verdad si y solo si no hay dos enteros vecinos en la lista que sean primos.

En otros términos: dada una lista de enteros positivos [a 1 a 2 ... a n ] , muestra si

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

La lista siempre contendrá al menos dos elementos (n ≥ 2).

Sin embargo…

Este desafío también es : los puntos de código en su respuesta (cualquiera que sea la página de código en la que se encuentre) deben satisfacer la condición que su programa verifica.

Por ejemplo, print 2es un programa válido. Como una lista de puntos de código Unicode, es [112 114 105 110 116 32 50] , que satisface esta condición: 112 y 114 comparten un factor de 2 ; y 114 y 105 comparten un factor de 3 , etc.

Sin embargo, nomain puede ocurrir en un programa válido (¡lo siento!), Ya que los puntos de código Unicode y , a saber, 109 y 97 , son coprimos. (¡Afortunadamente, su envío no necesita ser un programa completo!)ma

Su programa no puede contener el punto de código 0.

Casos de prueba

Verdad:

[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

Esto es : gana el código más corto en bytes.

Lynn
fuente
8
Para cualquier persona que intente este reto en un lenguaje de programación normal, esta es una lista de caracteres que tienen puntos de código de primera en ASCII: %)+/5;=CGIOSYaegkmq\DEL.
Cristian Lupascu
@ Lynn ¿Los Truthys tienen que ser consistentes?
H.PWiz
1
@ H.PWiz ¡No! -
Lynn
En realidad, tenía la intención de que esto fuera factible para algunos idiomas normales (que no sean de golf), y me sentí esperanzado cuando me di cuenta de que print 2era válido, pero );=aeser excelente es realmente difícil, no lo consideré ... Me pregunto si algo como Haskell puede ¿competir?
Lynn
Esta restricción es más fácil que el reverso de esta pregunta , suponga que nadie usa el byte 0x02. Esa pregunta obtiene una respuesta nongolf válida en Mathematica, Logo, Haskell, Python, Perl, TI-BASIC. Este ya tiene un Haskell, creo que Mathematica es imposible, pero es muy probable que Logo sea posible, aunque todavía no he terminado de construir la solución.
user202729

Respuestas:

15

MATL , 14 bytes

!TM1*Zdl2$Xdl-

Esto genera un vector de columna no vacío de números distintos de cero como verdadero, o un vector que contiene al menos una entrada cero como falso.

Explicación

!     % 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
fuente
44
Felicitaciones por una respuesta que no satisfacen el código restringido el requisito!
Erik the Outgolfer
13

Haskell , 103 100 bytes

EDITAR:

  • -3 bytes: se utilizó una d<-fzprotección para fusionar y acortar las dos últimas líneas.

fes la función principal, que toma una lista de enteros y devuelve a Bool.

Tenga en cuenta que los primeros dos ԁs (solo) son caracteres cirílicos (Komi) Unicode, y hay un carácter de tabulación antes del primero.

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

Pruébalo en línea! o probarlo en sí mismo.

Cómo funciona

  • fEs la función principal. Todo lo que hace es envolver su argumento ԁen una lista única (porque el valor ASCII principal de los )paréntesis es mucho más difícil de usar que los corchetes) y llamar zbcon eso y un argumento ficticio (la función Haskell idtiene los caracteres correctos para encajar aquí).
    • Hacer que el mismo carácter se ajuste además de ambos =]es imposible con ASCII simple, por lo que el argumento se nombra con el carácter Unicode de 2 bytes CYRILLIC SMALL LETTER KOMI DE (ԁ), el valor de punto de código 3*7*61=U+0501, que se ajusta a todos esos y[ .
      • Dado que el punto de código no es par (la opción más pequeña que es un identificador legal y que incluso usa tres bytes), esto requiere el uso de un carácter de tabulación en lugar de un espacio antes.
      • Una opción ASCII siete bytes más sencillo es cambiar el nombre del argumento: f fz|bf<-fz=zb[bf]fz.
  • zbtoma dos argumentos, una lista singleton cuyo elemento es la lista real de números en los que se recurre, y un argumento ficticio fzsolo necesario para obtener un zantes de la función =s.
    • Cuando la lista interna tiene al menos dos elementos, la función zse llama con los dos primeros (con nombre hy p), y si eso regresa True, vuelve a zbaparecer en la cola p:lde la lista.
    • Si la lista interna tiene menos de dos elementos, zbregresa True. Como =debe ser seguido por el carácter z, la forma más sencilla de hacerlo es utilizar una llamada de la zfunción que se sabe que devuelve True.
  • ztoma dos argumentos y calcula recursivamente su máximo divisor común usando la resta (cualquier otra división entera relevante o función gcd no está disponible), regresando Truesi es mayor que uno.
    • La recursión termina cuando el primer argumento es 0, con el segundo argumento siendo el mcd. En esta línea también se nombra el segundo argumento z. El personaje 1es incómodo aquí, por lo que z^0se usa para obtener el número uno.
    • De lo contrario, si el primer argumento fes más pequeño que el segundo fz, se intercambian y zvuelven a aparecer.
    • De lo contrario, el argumento más pequeño se resta del más grande, luego se zrepite (también intercambiando los argumentos, aunque eso es solo para evitar paréntesis).
Ørjan Johansen
fuente
2
¡ Sabía que tenía que haber un lenguaje que no fuera de golf que pudiera lograrlo!
Lynn
2
@ Lynn Realmente ayuda a Haskell en este tipo de desafío que tiene un subconjunto sintáctico bastante expresivo con solo tokens de un solo carácter. Supongo que está a medio camino de un idioma de golf.
Ørjan Johansen
Debido al cirílico, ¿son realmente 100 bytes? El script de usuario de Code Golf Graduation informa 102 bytes UTF-8, pero no sé si es correcto / esa es la forma correcta de contar los bytes aquí. No importa cuántos bytes, ¡es realmente impresionante!
Mark S.
1
@Marcas. TIO informa 100 bytes (y 98 caracteres). Sospecho que te atrapó el carácter de tabulación, que SE muestra como 3 espacios (que luego se copia como tal). Creo que he visto a alguien usar etiquetas previas para evitar eso, déjame intentar solucionarlo.
Ørjan Johansen
@Marcas. Hecho. Aunque sospecho que eso podría confundir aún más ese script de usuario.
Ørjan Johansen
10

05AB1E , 8 bytes

Código

ü‚ÒüÃP≠P

Utiliza la codificación 05AB1E , que nos da la siguiente lista de puntos de código:

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

Pruébalo en línea! o Verifique el código fuente!

Explicación

Como el operador gcd ( ¿) tiene un punto de código principal, tuve que buscar otras formas de verificar la coprimidad:

ü‚          # 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
fuente
¿Qué puntos de código tiene esto en la página de códigos de 05AB1E? ¿Puedes agregarlos a la respuesta?
Sr. Xcoder
@ Mr.Xcoder agregado
Adnan
¿Alguna razón para Òterminar f?
Urna mágica de pulpo
10

Casco , 8 bytes

Para las entradas de Truthy devuelve un entero positivo, para Falsy devuelve 0

←▼`Ṡt(ż⌋

Pruébalo en línea! y probado en sus propios puntos de código

Utiliza la página de códigos de Husk

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

Explicación

          -- 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
fuente
¿Para qué se llama la notación que usas en la explicación ? Lo veo en los documentos también en la columna "tipo" en la página de comandos y no puedo entenderlo, así que quiero buscarlo para poder aprenderlo.
Jonathan Allan
@ JonathanAllan Esa es la definición de la función en la sintaxis de Haskell. Se traduce aproximadamente a Ṡ(f,g,x) = f(g(x),x)en los idiomas más convencionales.
Zgarb
enlace fuente
H.PWiz
Aunque, cuando se voltea, se convierte en`Ṡ g f x = Ṡ f g x = f (g x) x
H.PWiz
1
@JonathanAllan Si te unes a la sala de chat de Husk , podemos intentar explicarlo mejor allí.
Zgarb
5

Japt , 8 7 bytes

äj d¹¥Z

¡Pruébelo en línea!

Puntos de código:

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

Explicación

 ä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
ETHproducciones
fuente
5

Jalea , 11 9 bytes

,Pnælð2\P

Guardado 2 bytes gracias a @ Jonathan Allan .

Pruébalo en línea!

Jelly tiene su propia página de códigos y los puntos de código de cada personaje son

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

Esto comprueba los números no primos marcando si lcm(a, b) != a*b. Puede haber una solución más corta ya que acabo de filtrar los caracteres con incluso puntos de código.

Explicación

,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
millas
fuente
¡Genio! Esto es increíble: O
Sr. Xcoder
,es incluso así que puedes hacer æln,P¥ð2\por dos menos. Editar: se me cayó el final P, que sea menos: p)
Jonathan Allan
Oh sí, intercambie los argumentos incluso :)
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 se tokeniza en tokens de uno o dos bytes, como se enumera aquí .

Las partes más difíciles de esta solución fueron:

  1. El token de coma es un número primo (43), lo que me obliga a rodearlo con múltiplos de 43 (en este caso, el token V, que es 86).

  2. El gcd (token es un número primo grande (47881), lo que significa que no se puede usar en absoluto.

Los tokens para este programa salen a:

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

Explicación

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

Pyth , 15 bytes

&F.bPiFNP.TtBQQ

Pruébalo aquí o echa un vistazo a Test Suite.

Este es un esfuerzo de colaboración entre Erik the Outgolfer y el Sr. Xcoder . Devuelve un valor inconsistente (lista no vacía) para verdadero, y la lista vacía para falso.


Valores ASCII

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

Que comparten los siguientes factores:

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

Explicación

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

Sin el requisito de , esta habría sido una versión de 7 5 bytes que realiza la misma tarea (-2 gracias a FryAmTheEggman ):

-1iVt

Explicación

-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
fuente
Por curiosidad, ¿por qué necesitas el Qs al final?
ETHproductions
@ETHproductions Debido a que .btiene aridades variables, y el uso de entrada implícita significa que elegirá el más bajo (1) en lugar de lo previsto (2).
Erik the Outgolfer