18
\$\begingroup\$

Given a word, treat every letter as its number in English alphabet (so a becomes 1, b becomes 2, z becomes 26 and so on), and check if all of them, including duplicates, are pairwise coprime.

The input is exactly one word of lowercase English letters. The output is the fact if the word is coprime: any truthy/falsey values, but only two variants of them. Standard loopholes are forbidden.

Test cases:

  • man: True
  • day: True (thanks to Ørjan Johansen)
  • led: False (l=12 and d=4 have gcd=4)
  • mana: True (though a occurs multiple times, 1 and 1 are coprimes)
  • mom: False (gcd(13,13)=13))
  • of: False (thanks to xnor; though 15∤6, gcd(15,6)=3)
  • a: True (if no pairs of letters, treat the word as coprime too)

This is a , so the shortest code in bytes wins!

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Can we output 0 if they are coprime and 1 if not? \$\endgroup\$
    – dylnan
    Sep 27, 2018 at 1:08
  • 2
    \$\begingroup\$ Suggested test case that would have caught a buggy answer: day: True \$\endgroup\$ Sep 27, 2018 at 6:00
  • 1
    \$\begingroup\$ I'd also suggest of: False to have a false example where no value is a multiple of another. \$\endgroup\$
    – xnor
    Sep 27, 2018 at 6:04
  • \$\begingroup\$ @dylnan no, it's contr-intuitive. Anyway, Dennis'es answer is better ;-) \$\endgroup\$
    – bodqhrohro
    Sep 27, 2018 at 9:37
  • \$\begingroup\$ @LuisMendo any truthy/falsey, but only two. \$\endgroup\$
    – bodqhrohro
    Sep 27, 2018 at 9:51

29 Answers 29

13
\$\begingroup\$

Wolfram Language (Mathematica), 36 bytes

CoprimeQ@@LetterNumber@Characters@#&

Try it online!


Wolfram Language (Mathematica), 33 bytes

  • Thanks to Misha Lavrov for this three bytes shorter version.
CoprimeQ@@(ToCharacterCode@#-96)&

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ CoprimeQ@@(ToCharacterCode@#-96)& is three bytes shorter. \$\endgroup\$ Sep 27, 2018 at 2:22
8
\$\begingroup\$

Jelly, 10 bytes

ØaiⱮgþ`P$Ƒ

Try it online!

How it works

Ø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.
\$\endgroup\$
7
\$\begingroup\$

Haskell, 48 bytes

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

Try it online!

Very straightforward: converts the string to a list of numbers and then checks whether the product is equal to the LCM.

\$\endgroup\$
6
\$\begingroup\$

Pyth, 9 bytes

{Ism{PhxG

Test suite

Explanation:
{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

did Pyth just outgolf Jelly?

\$\endgroup\$
6
\$\begingroup\$

Python 2 - 122 118 bytes

-4 bytes thanks to @JonathanAllan

This is honestly terrible, but I've spent way too long to not post this.

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)

Try it Online

\$\endgroup\$
1
  • 4
    \$\begingroup\$ 96 for ~> 96for; lambda x,y:x*y ~> int.__mul__. \$\endgroup\$ Sep 27, 2018 at 3:14
5
\$\begingroup\$

05AB1E, 11 bytes

Ç96-2.Æ€¿PΘ

Try it online!

Explanation

Ç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
\$\endgroup\$
4
  • \$\begingroup\$ Is the final Θ really necessary? \$\endgroup\$
    – Mr. Xcoder
    Sep 27, 2018 at 6:32
  • \$\begingroup\$ @Mr.Xcoder: No I suppose not. I just assumed we needed to use 2 distict values, but now that I look there is nothing in the challenge about it. Truthy/Falsy should be okay then. \$\endgroup\$
    – Emigna
    Sep 27, 2018 at 6:53
  • \$\begingroup\$ @Emigna I added a clarification for that: there should be only two variants of output values. \$\endgroup\$
    – bodqhrohro
    Sep 27, 2018 at 11:46
  • \$\begingroup\$ @bodqhrohro: OK. I rolled back to the previous version to conform to this new requirement. \$\endgroup\$
    – Emigna
    Sep 27, 2018 at 11:55
5
\$\begingroup\$

Brachylog, 11 bytes

ạ{-₉₆ḋd}ᵐc≠

Try it online!

Explanation

ạ{-₉₆ḋ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
\$\endgroup\$
4
\$\begingroup\$

Python 2, 77 68 64 bytes

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

Try it online!

Basically, (some pair in the input is not co-prime) if and only if (there is a number i > 1 which divides more than one of the inputs).

\$\endgroup\$
1
  • \$\begingroup\$ Looks like we had the same idea but you beat me by a few minutes :) Can't you save those 2 bytes by using all and <2 though? \$\endgroup\$
    – Vincent
    Sep 27, 2018 at 5:00
4
\$\begingroup\$

Python 3, 61 59 bytes

Using python bytes as argument:

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

The last divisor to check is 23, the largest prime below 26.

Try it online!

Thanks to @Dennis for saving two bytes.

\$\endgroup\$
1
  • 3
    \$\begingroup\$ c%96%x<1for c in s saves 2 bytes. \$\endgroup\$
    – Dennis
    Sep 27, 2018 at 5:21
4
\$\begingroup\$

JavaScript (Node.js), 60 bytes

f=(s,v=23)=>n=v<2||f(s,v-1)&&Buffer(s).every(c=>c%32%v||n--)

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ 62 bytes by going recursive and using every(c=>c%32%v||n--,n=1). \$\endgroup\$
    – Arnauld
    Sep 27, 2018 at 8:25
  • \$\begingroup\$ @Arnauld Thanks. And I golfed 2 more bytes from it. \$\endgroup\$
    – tsh
    Sep 27, 2018 at 9:14
  • \$\begingroup\$ 59 \$\endgroup\$
    – l4m2
    Jan 27, 2023 at 11:04
4
\$\begingroup\$

Perl 6, 34 32 bytes

-2 bytes thanks to nwellnhof

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

Try it online!

An anonymous codeblock that takes a string and returns True or False. If the lowest common multiple of the letters is equal to the product of the letters than they share no common divisors.

Explanation:

                     {.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
\$\endgroup\$
6
  • \$\begingroup\$ If I'm not mistaken, does this work? (21 bytes) \$\endgroup\$ Sep 27, 2018 at 2:32
  • \$\begingroup\$ @ConorO'Brien No, you've just mapped a to 0 lol \$\endgroup\$
    – Jo King
    Sep 27, 2018 at 3:19
  • \$\begingroup\$ @JoKing oh, ok lol \$\endgroup\$ Sep 27, 2018 at 3:48
  • \$\begingroup\$ That strategy was buggy, test case: day. \$\endgroup\$ Sep 27, 2018 at 6:01
  • 1
    \$\begingroup\$ 32 bytes \$\endgroup\$
    – nwellnhof
    Sep 27, 2018 at 10:08
3
\$\begingroup\$

J, 36 bytes

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

Ungolfed

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

Explanation

[: (                            ) _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.

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ [:(1=[:*/+./~#&,~#\~:/#\)_96+a.&i. for 34 bytes You had a space in `1 =' :) \$\endgroup\$ Sep 27, 2018 at 6:43
  • 1
    \$\begingroup\$ Thanks @GalenIvanov \$\endgroup\$
    – Jonah
    Sep 27, 2018 at 15:40
3
\$\begingroup\$

Jelly, 11 bytes

ŒcO_96g/€ỊẠ

Try it online!

  • Thanks to Dennis for NOTing my booleans

Œ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.
\$\endgroup\$
1
  • 2
    \$\begingroup\$ ỊẠ flips the Booleans. \$\endgroup\$
    – Dennis
    Sep 27, 2018 at 5:07
3
\$\begingroup\$

MATL, 10 bytes

96-YF&fdA&

Outputs 1 for coprime, 0 otherwise.

Try it online! Or verify all test cases.

Explanation

Consider input 'man' for example.

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
\$\endgroup\$
3
\$\begingroup\$

Markov algorithm, as interpreted by eMain (474 484 463 bytes, 76 78 76 rules)

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

The first 17 rules factor the "composite letters" into their "prime letter" factors, ignoring multiplicity. (E.g., t becomes be because 20 factors as a product of a power of 2 and a power of 5.)

The next 36 rules (such as cb->bc) sort the resulting prime factors.

The next 9 rules (such as bb->F) replace a repeated prime factor by F, then 9 more rules (such as b->) get rid of the remaining single letters.

At this point, we either have an empty string, or a string of one or more Fs, and the last rule ->!T adds a !T at the beginning. Then the rules FF->F and TF->F simplify the result to either !T or !F. At this point, the !->. rule applies, telling us to get rid of ! and halt: returning T for a coprime word, and F otherwise.

(Thanks to bodqhrohro for pointing out a bug in the earlier version that caused this code to give an empty string on input a.)

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Gives neither T nor F on a testcase. \$\endgroup\$
    – bodqhrohro
    Sep 29, 2018 at 13:09
  • \$\begingroup\$ @bodqhrohro Thanks for the catch! (In the end, my byte count went down, because I realized I was counting every newline as two bytes.) \$\endgroup\$ Sep 29, 2018 at 17:28
2
\$\begingroup\$

Python 3, 90 89 bytes

-1 byte by 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

Try it online!

Use as f(*'man').

\$\endgroup\$
0
2
\$\begingroup\$

Retina 0.8.2, 45 bytes


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

Try it online! Explanation:


;

Insert separators between each letter and at the start and end.

{`\w
#$&

Prepend a # to each letter.

}T`l`_l

Move each letter 1 back in the alphabet, deleting the as. Then repeat the above operations until all the letters have been deleted. This converts each letter to its 1-based alphabet index in unary.

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

Test whether any two values share a common factor greater than 1. (This can find more than one pair of letters with a common factor, e.g. in the word yearling.)

^0

Check that no common factors were found.

\$\endgroup\$
2
\$\begingroup\$

R + pracma library, 75 bytes

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

I'm using the gcd function in the pracma library as to my knowledge R does not have a built-in for that. I'm using the approach of comparing the product of the gcds to the numbers themselves.

65 bytes (credit: @J.Doe)

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

\$\endgroup\$
0
1
\$\begingroup\$

Japt, 14 bytes

;à2 e_®nR+CÃrj

Try it online!

Takes input as an array of characters.

How it works

;à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?
\$\endgroup\$
1
\$\begingroup\$

Ruby, 56 bytes

->s{s.bytes.combination(2).all?{|a,b|2>(a-96).gcd(a-b)}}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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;}

Port of @Vincent's Python 3 answer.

Try it online.

Explanation:

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
\$\endgroup\$
1
\$\begingroup\$

Japt, 13 bytes

Takes input as a character array.

®c uHÃà2 e_rj

Try it or verify all test cases

\$\endgroup\$
0
1
\$\begingroup\$

Pyt, 23 18 bytes

ą1Ĩ6²-⁺ϼƑ⁻ž⁺ĐỤŁ⇹Ł=

Try it online!

ą                     implicit input (string); convert to array of characters
 1Ĩ6²-⁺               use bug in arbitrary-base radix interpretation code to
                      convert lowercase letters to integers
       ϼ              get unique prime factors for each number
        Ƒ             flatten array
         ⁻ž⁺          remove all 1s
            ĐỤŁ⇹Ł=    is the resulting list the same length as the list of its
                      unique elements?; implicit print

Original Approach (23 bytes)

ą1Ĩ6²-⁺ĐĐɐǤƑ⁻⇹ŁřĐɐ≠Ƒ*↑¬

Try it online!

ą                              implicit input (string); convert to array of characters
 1Ĩ6²-⁺                        abuses bug in arbitrary-base radix interpretation code to
                               convert lowercase letters to integers
       Đ                       duplicate top of stack
        ĐɐǤ                    get all GCD pairs
           Ƒ⁻                  flatten array, and decrement each element
             ⇹                 swap top two items on stack
              ŁřĐɐ≠Ƒ           creates matrix of all 1s except for the main diagonal,
                               which contains only 0s; then flattens that array
                    *↑¬        multiplies element-wise the two arrays, gets the max, and
                               logically negates that value

Outputs "True" if coprime, "False" if not

\$\endgroup\$
1
\$\begingroup\$

Vyxal, 9 bytes

øA2ḋvġΠċ¬

Try it Online (with test cases)

øA        # convert letters to index in alphabet
  2ḋ      # get all combinations of length 2
    vġ    # get the gcd of each
      Π   # get the product of this list
       ċ  # inequality to 1 
        ¬ # logical not

Probably golfable.

\$\endgroup\$
0
\$\begingroup\$

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]]}
\$\endgroup\$
0
\$\begingroup\$

JavaScript (Node.js), 87 82 bytes

a=>!/\b(11+)\1* (1+ )*\1+\b/.exec(Buffer(a).map(x=>w+=" ".padEnd(x-95,1),w="")&&w)

Try it online!

Original approach (87B)

a=>!(b=Buffer(a)).some((x,i)=>b.some((y,j)=>i-j&&(g=(p,q)=>q?g(q,p%q):p)(x-96,y-96)>1))

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Stax, 16 bytes

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

Run and debug it

Explanation

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

Outputs 1 for True, 0 For false.

There is probably a better way to do the converting to number part, but it works.

\$\endgroup\$
2
  • \$\begingroup\$ Stax author here. Thanks for giving stax a try! Here's a program using your algorithm that packs to 10 bytes. 2SOF{96-F:!* Let me know if you want to know more about it. First one is free! \$\endgroup\$
    – recursive
    Oct 1, 2018 at 17:49
  • \$\begingroup\$ @recursive Thank you for making Stax! It's my golfing language of choice at the moment. I can see how your answer works and I'll have to keep working to improve my answers in the future. \$\endgroup\$
    – Multi
    Oct 1, 2018 at 19:24
0
\$\begingroup\$

APL(NARS), 16 chars, 32 bytes

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

This use method other used that LCM()=×/, it is fast but overflow if input array is enough long; other alternative solutions a little slower:

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

this below it seems 10 times faster(or+) than just above functions

∇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:
∇

i prefer this last because it is easier, faster, trusted (becaise less overflow possiblity), easier to write, and how it has to be (even if it has some bytes more...)

\$\endgroup\$
0
\$\begingroup\$

Thunno, \$ 13 \log_{256}(96) \approx \$ 10.70 bytes

O96-2zQ.AgP1=

Attempt This Online!

Port of Emigna's 05AB1E answer.

Explanation

O96-2zQ.AgP1=  # Implicit input
O              # Ordinal of each character in the input
 96-           # Subtract 96 from each
    2zQ        # Combinations of length 2
       .Ag     # GCD of each pair
          P    # Product of this list
           1=  # Equals 1?
               # Implicit output
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.