Take the square root of a string

Question

Motivation

In this challenge your task was to multiply two strings, this naturally introduces a way to take the square root of a string.

How does it work?

Given a string (for example pub) the first thing you need to do, is to determine the ASCII code for each character:

"pub" -> [112, 117, 98]

Next you map these codes to the range [0..94] by subtracting 32 of each value:

[112, 117, 98] -> [80, 85, 66]

Now you need to find for each value its root modulo 95 (eg. 40*40 % 95 = 80, you could also pick 55):

[80, 85, 66] -> [40, 35, 16]

And finally you'll map it back to the range [32..126] and convert it back to a string:

[40, 35, 16] -> [72, 67, 48] -> "HC0"

Indeed "HC0" ⊗ "HC0" = "pub" as you can verify with a solution from the other challenge here.

---

The ones familiar with modular arithmetic probably noticed that the square root modulo 95 does not always exist, for example there's no root for 2. In such a case the square root of a string is not defined and your program/function may crash, loop indefinetly etc.

For your convenience, here's the list of chars that have a square root (the first one is a space):

 !$%&)+03489:>CDGLMQVW]`bjlpqu

Rules

• You will write a program/function that takes a string (or list of chars) as an argument and returns any square root if it exists
• You may assume that the input always has a square root
• The input may consist of an empty string
• The input will be in the printable range ([32..126])
• The output is either printed to the console or you return a string if the square root exists
• In case the square root doesn't exist, the behavior of your program/function is left undefined
• If you choose to print the root to the console trailing newlines or whitespaces are fine

Test cases

Note that these are not necessarily the only solutions:

''              -> ''
'pub'           -> 'HC0'
'pull!'         -> 'HC33!'
'M>>M'          -> '>MM>'
'49'            -> '4%'
'64'            -> undefined
'Hello, World!' -> undefined

Answer 1

sh + coreutils, 58 bytes

tr '$%&)+0389:>CDGLMQVW]`bjpqu' 1u.#:BFO%+M/L2Aa,795d0@H=C

Try it online!

The modular square root is typically not unique; we have 2 or 4 choices for each character except . We don’t need to translate , !, 4, l since each is already a square root of itself. For the remaining characters, we choose images that don’t need to be escaped for the shell or tr.

Answer 2

Python 3, 57 56 bytes

lambda s:s.translate({k*k%95+32:k+32for k in range(95)})

translate uses a mapping from "Unicode ordinals to Unicode ordinals". Thus, we don't need chr/ord conversions. Note: it doesn't crash when the char has no root.

Saved 1 byte thanks to @jonathan-allan

The value of the mapping is the greatest root in range 0..94 of the key. To have the least root (as in the examples), use:

lambda s:s.translate({k*k%95+32:k+32for k in range(95,0,-1)})

(61 bytes)

>>> [s.translate({k*k%95+32:k+32for k in range(95,0,-1)}) for s in ['','pub','pull!','M>>M','49','64','Hello, World!']]
['', 'HC0', 'HC33!', '>MM>', '4%', '64', 'He33o,\x7f9or3d!']

Answer 3

Python 2, 80 bytes

lambda s:''.join([chr(i+32)for i in range(95)if i*i%95==ord(c)-32][0]for c in s)

Try it online!

Throws IndexError if no root exists.

Answer 4

Japt, 16 15 bytes

c@H+LDz%95+HÃbX

Try it online!

Saved a byte by looking at the 05AB1E answer (using L = 100 instead of 95). Now Japt is the shortest, a quite rare occurance :-D

Explanation

 c@ H+LÇ   ²  %95+HÃ bX
UcX{H+LoZ{Zp2 %95+H} bX}   Ungolfed
                           Implicit: U = input string, H = 32, L = 100
UcX{                   }   Map each charcode X in the input to the following:
      Lo                     Create the array [0, 1, ..., 98, 99]
        Z{         }         and map each item Z to
          Zp2                  Z ** 2
              %95              mod 95
                 +H            plus 32.
                     bX      Find the first index of X in this array. This gives the
                             smallest square root (mod 95) of (X - 32).
    H+                       Add 32 to map this back into the printable range.
                           Implicit: output result of last expression

Answer 5

Jelly, 18 17 16 bytes

95Ḷ²%95+32żØṖFyO

Try it online! (comes with test-suite footer)

Saved 2 bytes by doing a complete rewrite. Also the first time I've found use for }.

Explanation

The code first calculates all square characters, and then maps them to their respective square roots.

95Ḷ²%95+32żØṖFyO    Main link. Argument: S (string)
95                    Take 95.
  Ḷ                   Get the array [0, 1, ..., 94].
   ²                  Square each to get [0, 1, ..., 8836].
    %95               Get each square modulo 95 to get [0, 1, ..., 1].
       +32            Add 32 to get [32, 33, ..., 33].
           ØṖ         Get the list of printables [" ", "!", ..., "~"].
          ż           Interleave with printables to get [[32, " "], ..., [33, "~"]].
             F        Flatten the mapping to [32, " ", ..., 33, "~"].
               O      Get the code point of each character in input.
              y       Map the code points to the correct output characters using the map.

Answer 6

Mathematica, 94 bytes

(R[x_]:=Min@Select[Range@45,Mod[#^2,95]==x&];FromCharacterCode[R/@(ToCharacterCode@#-32)+32])&

Try it online!

Answer 7

JavaScript, 82 bytes

Collaborated with @ETHproductions

s=>s.map(x=>(g=z=>z*z%95==x.charCodeAt(0)-32?String.fromCharCode(z+32):g(z+1))(0))

Input and output are in the form of a char array.

Test snippet

var f=s=>s.map(x=>(g=z=>z*z%95==x.charCodeAt(0)-32?String.fromCharCode(z+32):g(z+1))(0))

console.log(f([...""]));
console.log(f([..."pub"]));
console.log(f([..."pull!"]));
console.log(f([..."M>>M"]));
console.log(f([..."49"]));

Answer 8

05AB1E, 17 bytes

vтLn95%žQykk33+ç?

The algorithm is very similar to the Jelly and Japt answer (Had something else before but that only got me to 19 bytes)

Explanation

vтLn95%žQykk33+ç?
v                 # For each character of the input...
 тL                # Push [1..100]
   n               # Square every element of the list
    95%            # And take it modulo 95
       žQyk        # Push the index of the current character in the printable ascii range
           k       # Push the index of that in the list created earlier
            33+    # Add 33 to the result
               ç   # And convert it back to a character
                ?  # Print the character

Try it online!

Answer 9

Mathematica, 60 bytes

FromCharacterCode[PowerMod[ToCharacterCode@#-32,1/2,95]+32]&

Anonymous function. Takes a string as input and returns a string as output. Errors on invalid input.

Answer 10

Perl 6, 53 bytes

{[~] .comb.map({32+first *²%95==.ord-32,^95})».chr}

Try it online!

Answer 11

Mathematica 82 Bytes

FromCharacterCode[Solve[x^2==#,Modulus->95][[1,1,2]]+32&/@(ToCharacterCode@#-32)]&

Using Solve's ability to do modular arithmetic.