¿Es la palabra coprime?

18

Dada una palabra, trate cada letra como su número en el alfabeto inglés (se aconvierte en 1, se bconvierte en 2, se zconvierte en 26 y así sucesivamente), y verifique si todas ellas, incluidos los duplicados, son coprimos por pares .

La entrada es exactamente una palabra de letras minúsculas en inglés. El resultado es el hecho si la palabra es coprime: cualquier valor verdadero / falso, pero solo dos variantes de ellos. Las lagunas estándar están prohibidas.

Casos de prueba:

  • man: True
  • day: True(gracias a Ørjan Johansen)
  • led: False( l=12y d=4tener gcd=4)
  • mana: True(aunque aocurre varias veces, 1 y 1 son coprimos)
  • mom: False( gcd(13,13)=13))
  • of: False(Gracias a XNOR; sin embargo 15∤6, gcd(15,6)=3)
  • a: True(si no hay pares de letras, trate la palabra como coprime también)

Este es un , por lo que gana el código más corto en bytes.

bodqhrohro
fuente
1
¿Podemos dar salida 0si son coprime y 1si no?
dylnan
2
Caso de prueba sugerido que habría captado una respuesta defectuosa:day: True
Ørjan Johansen
1
También sugeriría of: Falsetener un ejemplo falso en el que ningún valor sea múltiplo de otro.
xnor
@dylnan no, es contr intuitivo. De todos modos, la respuesta de Dennis es mejor ;-)
bodqhrohro
@LuisMendo cualquier verdad / falsey, pero solo dos.
bodqhrohro

Respuestas:

8

Jalea , 10 bytes

ØaiⱮgþ`P$Ƒ

Pruébalo en línea!

Cómo funciona

ØaiⱮgþ`P$Ƒ  Main link. Argument: s (string)

Øa          Yield "abc...xyz".
  iⱮ        Find the 1-based index of each c of s in "abc...xyz".
        $Ƒ  Call the monadic chain to the left.
            Yield 1 if the result is equal to the argument, 0 if not.
    gþ`       Take the GCDs of all pairs of indices, yielding a matrix.
       P      Take the columnwise product.
            For coprimes, the column corresponding to each index will contain the
            index itself (GCD with itself) and several 1's (GCD with other indices),
            so the product is equal to the index.
Dennis
fuente
7

Haskell , 48 bytes

((==).product<*>foldr1 lcm).map((-96+).fromEnum)

Pruébalo en línea!

Muy sencillo: convierte la cadena en una lista de números y luego comprueba si el producto es igual al LCM.

Delfad0r
fuente
6

Pyth , 9 bytes

{Ism{PhxG

Banco de pruebas

Explicación:
{Ism{PhxG   | Full code
{Ism{PhxGdQ | With implicit variables filled
------------+------------------------------------------
   m      Q | For each char d in the input:
    {P      |  list the unique prime factors of
      hx d  |  the 1-based index of d in
        G   |  the lowercase alphabet
  s         | Group all prime factors into one list
{I          | Output whether the list has no duplicates

¿Pyth acaba de superar a Jelly?

hakr14
fuente
6

Python 2 - 122 118 bytes

-4 bytes gracias a @JonathanAllan

Esto es sinceramente terrible, pero he pasado demasiado tiempo para no publicar esto.

from fractions import*
def f(n):r=reduce;n=[ord(i)-96for i in n];return r(lambda x,y:x*y/gcd(x,y),n)==r(int.__mul__,n)

Pruébalo en línea

Don mil
fuente
44
96 for~> 96for; lambda x,y:x*y~> int.__mul__.
Jonathan Frech
5

05AB1E , 11 bytes

Ç96-2.Æ€¿PΘ

Pruébalo en línea!

Explicación

Ç96-         # convert to character codes and subtract 96
    2.Æ      # get all combinations of size 2
       €¿    # gcd of each pair
         P   # product of gcds
          Θ  # is true
Emigna
fuente
¿Es la final Θrealmente necesaria?
Sr. Xcoder
@ Mr.Xcoder: No, supongo que no. Simplemente asumí que necesitábamos usar 2 valores distintos, pero ahora que lo veo, no hay nada en el desafío al respecto. Truthy / Falsy debería estar bien entonces.
Emigna
@Emigna Agregué una aclaración para eso: debería haber solo dos variantes de valores de salida.
bodqhrohro
@bodqhrohro: OK. Regresé a la versión anterior para cumplir con este nuevo requisito.
Emigna
5

Brachylog , 11 bytes

ạ{-₉₆ḋd}ᵐc≠

Pruébalo en línea!

Explicación

ạ{-₉₆ḋd}ᵐc≠
ạ              Split the input into its character codes
 {     }ᵐ      For each one
  -₉₆          Subtract 96 (a -> 1, b -> 2 etc.)
     ḋd        And find the unique (d) prime factors (ḋ)
         c     Combine them into one list
          ≠    And assert they are all different
PunPun1000
fuente
4

Python 2 , 77 68 64 bytes

lambda a:all(sum(ord(v)%96%i<1for v in a)<2for i in range(2,26))

Pruébalo en línea!

Básicamente, (algún par en la entrada no es co-prime) si y solo si (hay un número i> 1 que divide más de una de las entradas).

Chas Brown
fuente
Parece que teníamos la misma idea pero me ganaste unos minutos :) ¿No puedes guardar esos 2 bytes usando ally <2sin embargo?
Vincent
4

Python 3 , 61 59 bytes

Usando bytes de python como argumento:

lambda s:all(sum(c%96%x<1for c in s)<2for x in range(2,24))

El último divisor para verificar es 23, el primo más grande por debajo de 26.

Pruébalo en línea!

Gracias a @Dennis por guardar dos bytes.

Vincent
fuente
3
c%96%x<1for c in sahorra 2 bytes.
Dennis
4

Perl 6 , 34 32 bytes

-2 bytes gracias a nwellnhof

{[lcm](@_)==[*] @_}o{.ords X-96}

Pruébalo en línea!

Un bloque de código anónimo que toma una cadena y devuelve Verdadero o Falso. Si el mínimo común múltiplo de las letras es igual al producto de las letras, entonces no comparten divisores comunes.

Explicación:

                     {.ords X-96}  # Convert the letters to a list of numbers
 {                 }o              # Pass result to the next codeblock
  [lcm](@_)           # The list reduced by the lcm
           ==         # Is equal to?
             [*] @_   # The list reduced by multiplication
Jo King
fuente
Si no me equivoco, ¿ funciona esto ? (21 bytes)
Conor O'Brien
@ ConorO'Brien No, acabas de mapear aa 0lol
Jo King el
@JoKing oh, ok lol
Conor O'Brien
Esa estrategia fue con errores, caso de prueba: day.
Ørjan Johansen
1
32 bytes
nwellnhof el
3

J, 36 bytes

[:(1 =[:*/-.@=@i.@##&,+./~)_96+a.&i.

Sin golf

[: (1 = [: */ -.@=@i.@# #&, +./~) _96 + a.&i.

Explicación

[: (                            ) _96 + a.&i.  NB. apply fn in parens to result of right
                                  _96 + a.&i.  NB. index within J's ascii alphabet, minus 96.
                                               NB. gives index within english alphabet
   (1 =                         )              NB. does 1 equal...
   (    [: */                   )              NB. the product of...
   (                    #&,     )              NB. Flatten the left and right args, and then copy
   (                        +./~)              NB. right arg = a table of cross product GCDs
   (          -.@=@i.@#         )              NB. the complement of the identity matrix.
                                               NB. this removes the diagonal.

Pruébalo en línea!

Jonás
fuente
[:(1=[:*/+./~#&,~#\~:/#\)_96+a.&i.por 34 bytes Tuviste un espacio en `1 = ':)
Galen Ivanov
1
Gracias @GalenIvanov
Jonah
3

Jalea , 11 bytes

ŒcO_96g/€ỊẠ

Pruébalo en línea!

  • Gracias a Dennis por tomar nota de mis booleanos.

ŒcO_96g/€ỊẠ
Œc           All pairs of characters without replacement
  O          Code point of each character
   _96       Subtract 96. a->1, b->2, etc.
        €    For each pair:
      g/       Get the greatest common denominator
         Ị   abs(z)<=1? If they are all 1 then this will give a list of 1s
          Ạ  "All". Gives 1 if they are coprime, 0 if not.
dylnan
fuente
2
ỊẠvoltea los booleanos.
Dennis
3

MATL , 10 bytes

96-YF&fdA&

Salidas 1para coprime, de lo 0contrario.

Pruébalo en línea! O verificar todos los casos de prueba .

Explicación

Considere la entrada 'man'por ejemplo.

96-  % Implicit input: string. Subtract 96 from (the codepoint of) each element
     % STACK: [13 1 14] 
YF   % Exponents of prime factoriation. Each number produces a row in the result
     % STACK: [0 0 0 0 0 1;
               0 0 0 0 0 0;
               1 0 0 1 0 0]
&f   % Two-output find: pushes row and column indices of nonzeros
     % STACK: [3; 3; 1], [1; 4; 6]
d    % Consecutive differences
     % STACK: [3; 3; 1], [3; 2]
A    % All: gives true if the array doesn't contain zeros
     % STACK: [3; 3; 1], 1
&    % Alternative in/out specification: the next function, which is implicit
     % display, will only take 1 input. So only the top of the stack is shown
Luis Mendo
fuente
3

Algoritmo de Markov, tal como lo interpreta eMain ( 474 484 463 bytes, 76 78 76 reglas)

a->
d->b
f->bc
h->b
i->c
j->be
l->bc
n->bg
o->ce
p->b
q->q
r->bc
t->be
u->cg
v->bk
x->bc
y->e
z->bm
cb->bc
eb->be
gb->bg
kb->bk
mb->bm
qb->bq
sb->bs
wb->bw
ec->ce
gc->cg
kc->ck
mc->cm
qc->cq
sc->cs
wc->cw
ge->eg
ke->ek
me->em
qe->eq
se->es
we->ew
kg->gk
mg->gm
qg->gq
sg->gs
wg->gw
mk->km
qk->kq
sk->ks
wk->kw
qm->mq
sm->ms
wm->mw
sq->qs
wq->qw
ws->sw
bb->F
cc->F
ee->F
gg->F
kk->F
mm->F
qq->F
ss->F
ww->F
b->
c->
e->
g->
k->
m->
q->
s->
w->
FF->F
TF->F
!->.
->!T

Las primeras 17 reglas factorizan las "letras compuestas" en sus factores de "letras primas", ignorando la multiplicidad. (Por ejemplo, se tconvierte en be20 factores como producto de una potencia de 2 y una potencia de 5).

Las siguientes 36 reglas (como cb->bc) ordenan los factores primos resultantes.

Las siguientes 9 reglas (como bb->F) reemplazan un factor primo repetido por F, luego 9 reglas más (comob-> ) eliminan las letras individuales restantes.

En este punto, tenemos una cadena vacía, o una cadena de uno o más Fs, y la última regla ->!Tagrega un !Tal principio. Luego las reglas FF->Fy TF->Fsimplificar el resultado a cualquiera !To !F. En este punto, !->.se aplica la regla, que nos dice que nos deshagamos !y nos detengamos: regresar Tpor una palabra coprime, y de lo Fcontrario.

(Gracias a bodqhrohro por señalar un error en la versión anterior que causó que este código dé una cadena vacía en la entrada a).

Misha Lavrov
fuente
1
No da Tni Fen caso de aprueba.
bodqhrohro
@bodqhrohro Gracias por la captura! (Al final, mi recuento de bytes disminuyó, porque me di cuenta de que estaba contando cada línea nueva como dos bytes).
Misha Lavrov
2

Python 3 , 90 89 bytes

-1 byte por numbermaniac

f=lambda q,*s:s==()or all(math.gcd(ord(q)-96,ord(w)-96)<2for w in s)and f(*s)
import math

Pruébalo en línea!

Usar como f(*'man').

Bubbler
fuente
2

Retina 0.8.2 , 45 bytes


;
{`\w
#$&
}T`l`_l
M`;(##+)\1*;(#*;)*\1+;
^0

Pruébalo en línea! Explicación:


;

Inserte separadores entre cada letra y al principio y al final.

{`\w
#$&

Anteponer una #a cada letra.

}T`l`_l

Mueva cada letra 1 nuevamente en el alfabeto, eliminando el as. Luego repita las operaciones anteriores hasta que se hayan eliminado todas las letras. Esto convierte cada letra a su índice alfabético basado en 1 en unario.

M`;(##+)\1*;(#*;)*\1+;

Pruebe si dos valores comparten un factor común mayor que 1. (Esto puede encontrar más de un par de letras con un factor común, por ejemplo, en la palabra yearling).

^0

Compruebe que no se encontraron factores comunes.

Neil
fuente
2

Biblioteca R + pracma, 75 bytes

function(w){s=utf8ToInt(w)-96;all(apply(outer(s,s,pracma::gcd),1,prod)==s)}

Estoy usando la gcdfunción en la pracmabiblioteca en lo que sé, R no tiene una función incorporada para eso. Estoy usando el enfoque de comparar el producto de los gcds con los números mismos.

65 bytes (crédito: @ J.Doe)

function(w)prod(outer(s<-utf8ToInt(w)-96,s,pracma::gcd))==prod(s)

jld
fuente
1

Japt , 14 bytes

;à2 e_®nR+CÃrj

Pruébalo en línea!

Toma la entrada como una matriz de caracteres.

Cómo funciona

;à2 e_m_nR+C} rj
;                 Use alternative predefined variables (in this case, C = "a-z")
 à2               Get all pairs
    e_            Does all pairs satisfy that...
      m_            when the character pair is mapped over...
        nR+C}         conversion from "a-z" to [1..26]
              rj    then the two numbers are coprime?
Bubbler
fuente
1

Java 10, 86 bytes

a->{var r=1>0;for(int i=1,s=0;++i<24;r&=s<2,s=0)for(var c:a)s+=c%96%i<1?1:0;return r;}

Puerto de la respuesta Python 3 de @Vincent .

Pruébalo en línea.

Explicación:

a->{                 // Method with character-array parameter and boolean return-type
  var r=1>0;         //  Result-boolean, starting at true
  for(int s=0,       //  Sum integer, starting at 0
      i=1;++i<24     //  Loop `i` in the range (1, 24)
      ;              //    After every iteration:
       r&=s<2,       //     If the sum is >= 2: change the result to false
       s=0)          //     And reset the sum to 0
     for(var c:a)    //   Inner loop over the input-characters
       s+=c%96%i<1?  //    If the current character modulo-96 is divisible by `i`
           1         //     Increase the sum by 1
          :          //    Else
           0;        //     Leave the sum the same
  return r;}         //  Return the result-boolean
Kevin Cruijssen
fuente
0

q, 121 111 bytes

{$[1=count x;1b;1b=distinct{r:{l:{$[0~y;:x;.z.s[y;x mod y]]}[y;]'[x];2>count l where l<>1}[x;]'[x]}[1+.Q.a?x]]}
Thaufeki
fuente
0

Stax , 16 bytes

è'B╕i4à!ùà╫æor4Z

Ejecutar y depurarlo

Explicación

2S{M{$e96-mm{E:!m|A     #Full program, unpacked, implicit input
2S                      #Generate all combinations of size 2
  {       m             #Map for each element
   M                    #Split into size of 1 element
    {       m           #Map for each element
     $e                 #Convert to number
       96-              #Subtract 96
           {    m       #Map for each element
            E:!         #Explode array onto stack, are they coprime
                 |A     #Are all elements of array truthy

Salidas 1 para Verdadero, 0 Para falso.

Probablemente haya una mejor manera de hacer la conversión a parte numérica, pero funciona.

Multi
fuente
Stax autor aquí. ¡Gracias por probar Stax! Aquí hay un programa que usa su algoritmo que tiene paquetes de 10 bytes. 2SOF{96-F:!* Avísame si quieres saber más al respecto. ¡El primero es gratis!
recursivo el
@recursive ¡Gracias por hacer Stax! Es mi idioma de golf preferido en este momento. Puedo ver cómo funciona su respuesta y tendré que seguir trabajando para mejorar mis respuestas en el futuro.
Multi
0

APL (NARS), 16 caracteres, 32 bytes

{(×/p)=∧/p←⎕a⍳⍵}

Este método de uso utilizó otro que LCM () = × /, es rápido pero se desborda si la matriz de entrada es lo suficientemente larga; Otras soluciones alternativas un poco más lentas:

{1=×/y∨y÷⍨×/y←⎕a⍳⍵} 
{1=≢,⍵:1⋄1=×/{(2⌷⍵)∨1⌷⍵}¨{x←97-⍨⎕AV⍳⍵⋄(,x∘.,x)∼⍦x,¨x}⍵}

esto debajo parece 10 veces más rápido (o +) que las funciones anteriores

∇r←h m;i;j;k;v
   r←i←1⋄k←≢v←97-⍨⎕AV⍳m
A: →F×⍳i>k⋄j←i+1⋄→C
B:   →E×⍳1≠(j⌷v)∨i⌷v⋄j←j+1
C:   →B×⍳j≤k
D: i←i+1⋄→A
E: r←0
F:
∇

Prefiero esto último porque es más fácil, más rápido, confiable (porque hay menos posibilidades de desbordamiento), más fácil de escribir y cómo debe ser (incluso si tiene algunos bytes más ...)

RosLuP
fuente