Take the square root of a string

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 • Forcing an error state on these characters without a square root seems unnecessary, I'd recommend just undefined behavior. Jul 26 '17 at 4:21 • @ATaco I updated the challenge. Jul 26 '17 at 4:40 • What to do if the given string is the square of multiple strings? – tsh Jul 26 '17 at 6:26 • @tsh Return any, I'll update the challenge. Jul 26 '17 at 7:02 • @curiousdannii Actually it should be the range 0-94 (that's the printable range), that's a typo - sorry about that. Jul 26 '17 at 12:39 11 Answers 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.

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!']
• Welcome! Nice first post. You can remove the space between 32 and for. Jul 26 '17 at 15:46
• ...also, here is a link to an online interpreter test suite. Jul 26 '17 at 15:52

Python 2, 80 bytes

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

Try it online!

Throws IndexError if no root exists.

Japt, 16 15 bytes

c@H+LÇ²%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

Mathematica, 94 bytes

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

Jelly, 1817 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.
• 95Ḷ²%95+32iÐ€O+31Ọ is basically what my Japt answer does, though your solution is two bytes shorter... Jul 26 '17 at 18:26

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"]));

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!

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.

Perl 6, 53 bytes

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

Try it online!

Mathematica 82 Bytes

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

Using Solve's ability to do modular arithmetic.