39
\$\begingroup\$

Your task is to translate a 103-smooth number into an English word, using the method described below.

How?

  1. Generate the list of prime factors (with repetition) of the input number.
  2. Sort the list:
    • If 2 is not one of the prime factors, sort the list in ascending order.
    • If 2 is one of the prime factors, remove it from the list and sort the remaining factors in descending order.
  3. Translate each factor into a letter, using the following table:

     3 = S   13 = L   29 = X   43 = O   61 = Z   79 = H  101 = K  
     5 = P   17 = Q   31 = N   47 = R   67 = T   83 = V  103 = Y  
     7 = M   19 = U   37 = C   53 = A   71 = E   89 = D  
    11 = F   23 = I   41 = W   59 = G   73 = J   97 = B  
    

Note: This table was built empirically to maximize the number of possible words. For the curious, here is a list of 2,187 words that can be encoded that way (may include rude language). It's definitely not guaranteed to be optimal, but it's good enough for this challenge.

Examples

Example 1: 579085261 (ascending order)

  1. The prime factors are [ 37, 47, 53, 61, 103 ].
  2. 2 is not a prime factor, so we keep the list sorted in ascending order.
  3. 37 = C, 47 = R, etc. The output is "CRAZY".

Example 2: 725582 (descending order)

  1. The prime factors are [ 2, 11, 13, 43, 59 ].
  2. 2 is a prime factor, so we remove it and sort the list in descending order, which gives:
    [ 59, 43, 13, 11 ].
  3. 59 = G, 43 = O, etc. The output is "GOLF".

Example 3: 10757494 (with a repeated factor)

  1. The prime factors are [ 2, 11, 71, 71, 97 ].
  2. 2 is a prime factor, so we remove it and sort the list in descending order, which gives:
    [ 97, 71, 71, 11 ].
  3. 97 = B, 71 = E, 11 = F. The output is "BEEF".

Clarifications and rules

  • The input number is guaranteed to be 103-smooth and divisible by 2 at most once.
  • By definition, a smooth-number is a positive integer.
  • Input and output can be handled in any reasonable format. The output can be in lowercase or uppercase. Trailing whitespace is acceptable. Leading whitespace is not.
  • If your program/function can't support large inputs, please specify it in your answer.
  • This is code golf, so the shortest answer in bytes wins.

Test cases

34874          --> ARM
483254         --> BAR
353722         --> EAR
494302         --> EGG
39061          --> FAT
6479           --> FUN
60421          --> ICE
54166          --> JAM
48911474       --> BETA
2510942        --> BOOM
2303854        --> DOOM
844261         --> FIRE
1606801        --> MAZE
1110085        --> PAGE
5212974        --> BALLS
67892046       --> BEANS
885396199      --> CREEK
67401037       --> FUNKY
27762173       --> QUICK
1238440506     --> ARROWS
33045832681    --> CRAGGY
1362714005     --> PIRATE
137302698      --> TROLLS
358310128062   --> BEGGARS
40255151586    --> DETAILS
164633248153   --> FIXATED
621172442227   --> UNRATED
2467812606     --> VACUUMS
86385078330    --> GROWNUPS
26607531423091 --> UNWORTHY
\$\endgroup\$
  • 9
    \$\begingroup\$ Ohhh crap... 05AB1E cache hit when using Ò on 579085261, feel like <s>Emigna</s> Adnan has already started. \$\endgroup\$ – Magic Octopus Urn Apr 27 '17 at 17:20
  • \$\begingroup\$ You could've allowed multiple factors of 2, then made it so that increasing the number of factors changes the index at which the reversal starts. \$\endgroup\$ – mbomb007 Apr 27 '17 at 18:16
  • \$\begingroup\$ @mbomb007 Yes, there are many possible variants. My initial idea was to encode any word by working on groups of letters. \$\endgroup\$ – Arnauld Apr 27 '17 at 18:47
  • 5
    \$\begingroup\$ The test cases on this challenge remind be of those "discover your X name" things on Facebook. Find the title of the movie you're in! Step one, choose your favorite prime number <=103... your result is PIRATE MAZE, or DOOM VACUUMS... \$\endgroup\$ – mbomb007 Apr 27 '17 at 19:21
  • 2
    \$\begingroup\$ @Qwerp-Derp It was first randomly shuffled and tested against a dictionary of ~106K words, up to 11 letters (the file is on my HD for a long time -- I think it was originally extracted from the TWL). Then I forced 'S' to be either first or last to maximize plural words and tried a couple of individual letter exchanges on a good combination (recursively). Finally, I lost patience and wrote the challenge. :-) Actually, before all of this, I tried to take Letter Counts by Position Within Word into account but it wasn't all that great. \$\endgroup\$ – Arnauld Apr 28 '17 at 8:25

13 Answers 13

13
\$\begingroup\$

Jelly, 29 27 bytes

ÆEµØA“¡3ḅḲ+Ṿɼ¡ẏƙẊƘ’œ?xḊṚḢ}¡

Thanks to @JonathanAllan for golfing off 1 byte!

Try it online!

Background

“¡3ḅḲ+Ṿɼ¡ẏƙẊƘ’

is a numeric literal. The characters between the quotes are replaced with their 1-based indices in the Jelly code page, and the resulting array is interpreted as a base-250 number. This yields the integer c := 288824892868083015619552399.

How it works

ÆEµØA“¡3ḅḲ+Ṿɼ¡ẏƙẊƘ’œ?xḊṚḢ}¡  Main link. Argument: n

ÆE                           Yield the exponents of n's prime factorization, with.
                             zeroes. This yields an array A.
  µ                          Begin a new monadic chain with argument A.
   ØA                        Set the return value to “ABC...XYZ”.
     “¡3ḅḲ+Ṿɼ¡ẏƙẊƘ’œ?        Select the c-th permutation of the alphabet, yielding
                             s := “SPMFLQUIXNCWORAGZTEJHVDBKY”.
                      Ḋ      Dequeue; yield A without its first element, stripping
                             the exponent of 2.
                     x       Repeat the k-th letter of s r times, where r is the
                             exponent of the k-th odd prime number.
                          ¡  Combine the two links to the left into a quicklink:
                        Ḣ}     - Apply head to the right argument (A), yielding the
                                 exponent of 2. Since n is at most divisible by the
                                 first power of 2, this yields 1 for even numbers
                                 and 0 for odd ones. Call the link to the left that
                                 many times on the previous return value.
                       Ṛ       - Reverse the string to the left.
\$\endgroup\$
10
\$\begingroup\$

Jelly, 36 bytes

“¡3ḅḲ+Ṿɼ¡ẏƙẊƘ’œ?ØA1;;⁶
×107ÆE¢×UḢ¡t⁶

Try it online!

Explanation

Helper constant (produces “SPMFLQUIXNCWORAGZTEJHVDBKY ” with a 1 prepended)

“¡3ḅḲ+Ṿɼ¡ẏƙẊƘ’œ?ØA1;;⁶
“¡3ḅḲ+Ṿɼ¡ẏƙẊƘ’          288824892868083015619552399 (compressed representation)
              œ?ØA      th permutation of the alphabet
                  1;    prepend 1
                    ;⁶  append a space

Main program

×107ÆE¢×UḢ¡t⁶
×107           Multiply {the input} by 107
    ÆE         Convert to a list of frequencies for each factor
      ¢×       {Vectorized} multiply by the return value of 1£
        UḢ¡    Delete the first value, reverse the list that many times
           t⁶  Delete trailing/leading space

I have a feeling that my compression of the list easily beats the other Jelly answer, but that my algorithm for using it could be a lot more efficient. Maybe I'll try to combine them.

Jelly, 31 bytes, inspired by @Leakynun's answer

“¡3ḅḲ+Ṿɼ¡ẏƙẊƘ’œ?ØA⁷;
ÆfÆCị¢U⁸¡U

Try it online! (slightly modified to run a lot faster)

Is inconsistent in whether it prints a trailing newline (but PPCG normally allows answers either with or without a trailing newline, so I guess this works too?). Is very slow (O(n) where n is the input, and those numbers aren't exactly small…)

Explanation

Helper constant (produces “¶SPMFLQUIXNCWORAGZTEJHVDBKY”, where is newline)

“¡3ḅḲ+Ṿɼ¡ẏƙẊƘ’œ?ØA⁷;
“¡3ḅḲ+Ṿɼ¡ẏƙẊƘ’          288824892868083015619552399 (compressed representation)
              œ?ØA      th permutation of the alphabet
                  ⁷;    prepend newline

Main program

ÆfÆCị¢U⁸¡U
Æf          Produce list of prime factors (repeating repeated factors)
  ÆC        Map the nth prime to n
    ị¢      Index into the output of 1£
      U     Reverse
        ¡   a number of times
       ⁸    equal to the input
         U  Reverse again
\$\endgroup\$
  • \$\begingroup\$ That's a very nice way to store a permutation of the alphabet... \$\endgroup\$ – Leaky Nun Apr 27 '17 at 17:46
  • \$\begingroup\$ Ah you have used my permutation atom too :D \$\endgroup\$ – Jonathan Allan Apr 27 '17 at 17:50
9
\$\begingroup\$

05AB1E, 39 38 bytes

ÒW<iR¨}26LØR•6Ê2"£´õþÕàçŸôëÂÛ*™•36BS:J

Uses the CP-1252 encoding. Try it online!

\$\endgroup\$
  • 8
    \$\begingroup\$ I knew it was one of you hahaha. scrapes halfway finished answer into the garbage \$\endgroup\$ – Magic Octopus Urn Apr 27 '17 at 17:22
  • 6
    \$\begingroup\$ @carusocomputing the cache hits can bring up some time pressure haha \$\endgroup\$ – Adnan Apr 27 '17 at 17:25
  • \$\begingroup\$ Ø was the part of this that beat mine by 20 bytes anyway :P. \$\endgroup\$ – Magic Octopus Urn Apr 27 '17 at 17:36
  • \$\begingroup\$ I think you can do Ò26ÝØR•1Sî?¾±=&ÔìÍècS¦ÁÜ7d•36BS:Já¹GR for 37. \$\endgroup\$ – Emigna Apr 27 '17 at 19:06
  • 2
    \$\begingroup\$ It's not very efficient no ;) \$\endgroup\$ – Emigna Apr 27 '17 at 21:12
8
\$\begingroup\$

Python 2, 220 217 bytes

n=input()
i=1
L=[]
exec'i+=1;c=0\nwhile n%i<1:c+=1;n/=i\nif c:L+=[i]*c\n'*n
T='SPMFLQUIXNCWORAGZTEJHVDBKY'
print''.join(T[[p for p in range(3,104)if all(p%k for k in range(2,p))].index(q)]for q in[L,L[:0:-1]][L[0]<3])

Try it online - only runs the smallest test case without running out of memory

Ungolfed:

This version doesn't use exec, so you can actually test all of the test cases without running out of memory.

n=input()
i=1
L=[]
while~-n:
 i+=1;c=0
 while n%i<1:c+=1;n/=i
 if c:L+=[i]*c
if L[0]<3:L=L[:0:-1]
T='SPMFLQUIXNCWORAGZTEJHVDBKY'
print''.join(T[[p for p in range(3,104)if all(p%k for k in range(2,p))].index(q)]for q in L)

Try it online

\$\endgroup\$
8
\$\begingroup\$

Ruby, 139 138 134 125 120 115+7 = 146 145 141 132 127 122 bytes

Uses the -rprime flag for +7 bytes.

-1 byte from @daniero. -4 bytes by remembering that I can just do a regular divisibility check instead of checking the prime division for the existence of 2.

-9 bytes from @mbomb007's Python solution reminding me of a shorter way to retrieve the matching letter.

-5 bytes because trailing whitespace is now allowed.

-5 bytes from discovering Enumerable#find_index

->n{x=Prime.prime_division n;x.reverse!if n%2<1;x.map{|i,c|" SPMFLQUIXNCWORAGZTEJHVDBKY"[Prime.find_index i]*c}*''}

Try it online! (all test cases)

Explanation

->n{                                   # Anonymous procedure with one argument n
    x=Prime.prime_division n;          # Get prime factorization of n, sorted
                                       # p0^e0 * p1^e1 ... -> [[p0,e0],[p1,e1],...]
    x.reverse!if n%2<1;                # Reverse if divisible by 2
    x.map{|i,c|                        # For each prime/exponent pair:
        " SPMFLQUIXNCWORAGZTEJHVDBKY"[ # Get corresponding character by obtaining:
            Prime.find_index i]        # Determine index of the current prime
                               *c      # Repeat the letter by the supplied exponent
                                 }*''} # Join all letter sequences together
\$\endgroup\$
  • \$\begingroup\$ Nice one. You can remove the space between zip and " \$\endgroup\$ – daniero Apr 27 '17 at 18:42
7
\$\begingroup\$

Bash + GNU utilities + bsd-games package, 170

Seems pretty non-optimal, but it works:

p='printf %03d\n'
a=(`factor $1`)
x=$[a[1]<3]
$p `primes 3 104`|paste - <(fold -1<<<SPMFLQUIXNCWORAGZTEJHVDBKY)|join -o1.2 - <($p ${a[@]:x+1})|(((x))&&tac||cat)|tr -d \\n

Try it online.

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

Jelly, 33 bytes

ÆfÆCUṖ$¹e@?1’ị“¡3ḅḲ+Ṿɼ¡ẏƙẊƘ’œ?ØA¤

Try it online!

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

Japt, 51 50 bytes

49 bytes of code, +1 for the -P flag.

%2?Uk :Uk Åw)£`yspmflquixncÙgz’jhvdbk`g#ho fj bX

Try it online!

This could be way shorter if only Japt had a couple more features...

Explanation

`yspmflquixncÙgz’jhvdbk` is just the same string everyone else is using compressed as much as Japt can compress it (3 bytes shorter than the original!). Japt's only built-in compression tool at the moment replaces common pairs of lowercase letter with a single-byte char.

So let's examine the actual code:

%2?Uk :Uk Å  w)
%2?Uk :Uk s1 w)
%2?             // If the input mod 2 is non-zero,
   Uk           //   take the prime factors of the input (U).
      :Uk       // Otherwise, take the prime factors of the input,
          s1 w  //   slice off the first one (2), and reverse.

Then £ is used to replace each item X in the result like this:

"string"g#h o fj bX
"string"g104o fj bX

         104o         // Create the range [0...104).
              fj      // Filter to only items Z where Z.j() is truthy (Z is prime).
                      // This results in the list of prime numbers from 2 to 103.
                 bX   // Take the index of X in this list.
"string"g             // Get the char in the compressed string at that index.
                      // For `y`, the index is 26, but since the string is only 26 chars
                      // long, Japt wraps around and grabs the first char in the string.

The result is an array of characters at this point, so the -P flag joins it into a single string, and the result is implicitly sent to output.

\$\endgroup\$
5
\$\begingroup\$

Jelly, 40 bytes

Æfḟ2ÆCṚ⁸Ḃ¤¡Ṛị“YSPMFLQUIXNCWORAGZTEJHVDBK

Try it online!

Verify all testcases at once! (slightly modified)

\$\endgroup\$
5
\$\begingroup\$

Pyth, 54 47 bytes

7 bytes thanks to isaacg

s__W%Q2@L."AZ❤O❤❤❤❤❤❤Q❤9❤❤×❤❤"xL_MP#r_3_103-PQ2

( represents an unprintable character)

Pyth doesn't have many prime built-ins...

Hexdump:

0000000: 73 5f 5f 57 25 51 32 40 4c 2e 22 41 5a 03 4f f3 s__W%Q2@L."AZ.O.
0000010: 14 af 15 ed f5 51 90 39 d5 18 d7 20 a8 22 78 4c .....Q.9... ."xL
0000020: 5f 4d 50 23 72 5f 33 5f 31 30 33 2d 50 51 32    _MP#r_3_103-PQ2

Try it online!

\$\endgroup\$
  • \$\begingroup\$ pyth.herokuapp.com/… \$\endgroup\$ – isaacg Apr 27 '17 at 17:35
  • \$\begingroup\$ @isaacg I tried it, and I don't know why it produces strange result for the last one. \$\endgroup\$ – Leaky Nun Apr 27 '17 at 17:36
  • \$\begingroup\$ I don't know what you mean: pyth.herokuapp.com/… \$\endgroup\$ – isaacg Apr 27 '17 at 17:39
  • \$\begingroup\$ @isaacg That's very weird. \$\endgroup\$ – Leaky Nun Apr 27 '17 at 17:39
5
\$\begingroup\$

J, 59 bytes

'SPMFLQUIXNCWORAGZTEJHVDBKY'{~(p:>:i.26)i.[:|.@}.^:(2={.)q:

Try it online!

Quite simple...

'SPMFLQUIXNCWORAGZTEJHVDBKY'{~(p:>:i.26)i.[:|.@}.^:(2={.)q:
                              (p:>:i.26)                      first 26 primes after 2
                                        i.                    for which the indices is
                                                         q:   prime factors
                                            |.@}.             remove first and reverse
                                                 ^:           if
                                                   (2={.)     the first entry is 2
                            {~                                reverse index
'..........................'                                  hardcoded string
\$\endgroup\$
3
\$\begingroup\$

PHP, 173 Bytes

for($i=2;1<$n=&$argn;$n%$i?++$i:$r[]=$i.!$n/=$i)for($t=$i;$i>2&!$w[$i]&&$i%--$t;$t>2?:$w[$i]=SPMFLQUIXNCWORAGZTEJHVDBKY[$p++]);$r[0]>2?:rsort($r);foreach($r as$s)echo$w[$s];

Online Version

Expanded

for($i=2;1<$n=&$argn; # loop till input is 1
$n%$i?++$i:$r[]=$i.!$n/=$i) #after loop add value to result if input is divisible and divide input
  for($t=$i;$i>2&!$w[$i]&&$i%--$t; # loop if number is gt 2 and not in letter array till number is divisible 
  $t>2?:$w[$i]=SPMFLQUIXNCWORAGZTEJHVDBKY[$p++]) # if is prime add to letter array
  ; # make nothing in the loop
$r[0]>2?:rsort($r); # reverse result array if 2 is in result array
foreach($r as$s) # loop result array
  echo$w[$s]; # Output 

PHP, 178 Bytes

for($z=2;$p<26;$t>1?:$w[$z]=SPMFLQUIXNCWORAGZTEJHVDBKY[$p++])for($t=++$z;$z%--$t;);for($i=2;1<$n=&$argn;)$n%$i?++$i:$r[]=$i.!$n/=$i;$r[0]>2?:rsort($r);foreach($r as$s)echo$w[$s];

Online Version

Expanded

for($z=2;$p<26;
$t>1?:$w[$z]=SPMFLQUIXNCWORAGZTEJHVDBKY[$p++]) # after loop if is prime add to letter array
  for($t=++$z;$z%--$t;); 
for($i=2;1<$n=&$argn;)  # loop till input is 1
  $n%$i?++$i:$r[]=$i.!$n/=$i; #add value to result if input is divisible and divide input
$r[0]>2?:rsort($r); # reverse result array if 2 is in result array
foreach($r as$s) # loop result array
  echo$w[$s]; # Output 
\$\endgroup\$
1
\$\begingroup\$

Python, 1420 bytes

lambda x:(lambda a,b,e,k,l,m,q,p:len.__name__[:a].join(dict(zip((lambda n:(lambda n,f,g:f(n,e,[],f,g))(n,lambda n,i,r,f,g:g(n,i+b,r,f,g)if i<n else r,lambda n,i,r,f,g:f(n,i,[r,r+[i]][all(i%x!=a for x in[e]+r)],f,g)))(l*e*(k*l+b)),(lambda n,o,t:(lambda n,f,g:f(n, len.__name__[:a],f,g))(n,lambda n,s,f,g:g(n,s,f,g)if n>o else s,lambda n,s,f,g:f(n//t,s+chr(n%t),f,g)))((((((k<<e)-b)<<m)+m)<<((k<<q)+(k<<b)))+(((((k<<e)-b)<<e)+b)<<((k<<q)-(b<<b)))+((((((b<<k)+b))<<l)+b)<<((((k<<e)-b)<<l)+(b<<b)))+(((((k<<e)-b)<<l)-k)<<((m<<m)+p))-(((p<<m)-b)<<((m<<m)-(b<<b)))+(((m<<k)+b)<<((((m<<e)-b)<<k)-(b<<b)))+(((((k<<e)-b)<<l)-m)<<((((b<<l)+b)<<k)+k))-(((((b<<l)-b)<<l)-p)<<((b<<p)+(b<<b)))-(((p<<k)-b)<<((((b<<l)-b)<<k)+k))-(((k<<q)-b)<<((p<<l)))+(((m<<m)+m)<<((((k<<e)+b)<<k)-b))-(((k<<m)+b)<<((k<<m)-b))-(((m<<m)+k)<<((((k<<e)-b)<<k)-(b<<b)))+(((((k<<e)+b)<<e)+b)<<((m<<l)-(b<<e)))-(((((k<<e)+b)<<e)+b)<<((((b<<l)+b)<<e)-b))+((((((b<<k)+b))<<k)+b)<<((p<<k)))+(((((k<<e)-b)<<k)-k)<<((k<<l)))+(((m<<l)+b)<<((m<<k)))+(((m<<e)-b)<<((b<<m)+(b<<b)))+((((((b<<k)+b))<<e)-b)<<((k<<k)+b))+(((m<<k)-b)<<((b<<l)+b))-((((k<<e)-b))<<((k<<e)))+(((m<<e)+b)<<e)-b,b,b<<l*e)))[i]for i in(lambda x: [x.remove(e), x[::-b]][b] if e in x else x)((lambda x:(lambda x,g,h:g(x,b,[],g,h))(x,lambda x,n,r,g,h:h(x,n+b,r,g,h)if x>b else r,lambda x,n,r,g,h:h(x//n,n,r+[n],g,h)if x%n==a else g(x,n,r,g,h)))(x))))(*[x for x in range(True<<len(len.__name__))])

This could definitely by shorted some, but it's my attempt at solving it with no numbers or string literals. I realize this is a code-golf problem and this isn't exactly short but wanted to share anyway, not sure if this breaks any rules or not.

Was a lot of fun to make, I used the algorithm on this blog post to reduce the ASCII numerical representation of "SPMFLQUIXNCWORAGZTEJHVDBKY" in to the bit-shift expression I use. I also generally took a lot of inspiration from this blog, I wanted to try it out myself and this seemed like a good challenge to do it with.

Here is a slightly more readable version, with some more sensible variable names too

\$\endgroup\$
  • \$\begingroup\$ There's at least one space that can be removed. \$\endgroup\$ – mbomb007 Apr 28 '17 at 19:22
  • 2
    \$\begingroup\$ Welcome to Programming Puzzles & Code Golf! This is a code golf competition, so your objective should be to make your code as short as possible. Our help center states that all solutions to challenges should [...] be a serious contender for the winning criteria in use. [...] An entry to a code golf contest needs to be golfed \$\endgroup\$ – Dennis Apr 28 '17 at 20:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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