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

Forcing an error state on these characters without a square root seems unnecessary, I'd recommend just undefined behavior. — ATaco
– ATaco, Commented Jul 26, 2017 at 4:21
What to do if the given string is the square of multiple strings? — tsh
– tsh, Commented Jul 26, 2017 at 6:26
@curiousdannii Actually it should be the range 0-94 (that's the printable range), that's a typo - sorry about that. — ბიმო
– ბიმო, Commented Jul 26, 2017 at 12:39

Anders Kaseorg · Accepted Answer · 2017-07-26 05:39:37Z

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.

jferard · Accepted Answer · 2017-07-26 18:02:12Z

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. — Jonathan Allan
– Jonathan Allan, Commented Jul 26, 2017 at 15:46
...also, here is a link to an online interpreter test suite. — Jonathan Allan
– Jonathan Allan, Commented Jul 26, 2017 at 15:52

Chas Brown · Accepted Answer · 2017-07-26 07:10:57Z

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.

ETHproductions · Accepted Answer · 2017-07-26 20:35:46Z

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

ZaMoC · Accepted Answer · 2017-07-26 07:18:07Z

Mathematica, 94 bytes

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

Try it online!

PurkkaKoodari · Accepted Answer · 2017-07-26 12:15:10Z

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.

95Ḷ²%95+32iÐ€O+31Ọ is basically what my Japt answer does, though your solution is two bytes shorter... — ETHproductions
– ETHproductions, Commented Jul 26, 2017 at 18:26

Community · Accepted Answer · 2020-06-17 09:04:33Z

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

Community · Accepted Answer · 2020-06-17 09:04:33Z

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!

Kelly Lowder · Accepted Answer · 2017-07-26 20:39:45Z

Mathematica 82 Bytes

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

Using Solve's ability to do modular arithmetic.

Jordan · Accepted Answer · 2022-10-27 02:20:51Z

2

Ruby, 65 bytes

->s{s.chars.map{|c|((0..94).find{_1**2%95+32==c.ord}+32).chr}*""}

Attempt This Online!

answered Oct 27, 2022 at 2:20

Jordan

11.9k1 gold badge36 silver badges56 bronze badges

Add a comment |

LegionMammal978 · Accepted Answer · 2017-07-26 11:22:55Z

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.

Sean · Accepted Answer · 2017-07-26 18:38:19Z

1

Perl 6, 53 bytes

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

Try it online!

answered Jul 26, 2017 at 18:38

Sean

8,16612 silver badges16 bronze badges

Add a comment |

bigyihsuan · Accepted Answer · 2022-10-27 14:44:53Z

Go, 120 bytes

func f(s[]rune)[]rune{ for i:=range s{for k:=0;k<95;k++{r:=rune(k*k%95+32) if r==s[i]{s[i]=rune(k+32) break}}} return s}

Attempt This Online!

Shaggy · Accepted Answer · 2022-10-27 15:05:16Z

1

JavaScript, 56 bytes

s=>Buffer(s).map(x=>(g=y=>y*y%95+32-x?g(++y):y+32)``)+``

Try it online!

edited Oct 27, 2022 at 15:05

answered Oct 27, 2022 at 14:57

Shaggy

45k4 gold badges39 silver badges95 bronze badges

Add a comment |

chunes · Accepted Answer · 2022-10-27 16:33:16Z

1

Factor, 59 55 bytes

[ [ 32 - 95 iota [ sq 95 mod = ] with find 32 + ] map ]

Try it online!

edited Oct 27, 2022 at 16:33

answered Oct 27, 2022 at 3:47

chunes

27.8k3 gold badges32 silver badges55 bronze badges

Add a comment |

Baby_Boy · Accepted Answer · 2022-10-27 15:26:23Z

Pip, 33 bytes

FiA*a YyAE((SQ,h)%95+32@?i)+32 Cy

Try It Online!

Pip, 37 bytes

FiA*a-32 YyAE((SQ_%95=i)FI,h)@0+32 Cy

Try It Online!

Stack Exchange Network

Take the square root of a string

Motivation

How does it work?

Rules

Test cases

16 Answers 16

sh + coreutils, 58 bytes

Python 3, 57 56 bytes

Python 2, 80 bytes

Japt, 16 15 bytes

Explanation

Mathematica, 94 bytes

Jelly, 18 17 16 bytes

Explanation

JavaScript, 82 bytes

Test snippet

05AB1E, 17 bytes

Explanation

Mathematica 82 Bytes

Ruby, 65 bytes

Mathematica, 60 bytes

Perl 6, 53 bytes

Go, 120 bytes

JavaScript, 56 bytes

Factor, 59 55 bytes

Pip, 33 bytes

Pip, 37 bytes

Linked

Hot Network Questions

Take the square root of a string

Motivation

How does it work?

Rules

Test cases

16 Answers 16

sh + coreutils, 58 bytes

Python 3, 57 56 bytes

Python 2, 80 bytes

Japt, 16 15 bytes

Explanation

Mathematica, 94 bytes

Jelly, 18 17 16 bytes

Explanation

JavaScript, 82 bytes

Test snippet

05AB1E, 17 bytes

Explanation

Mathematica 82 Bytes

Ruby, 65 bytes

Mathematica, 60 bytes

Perl 6, 53 bytes

Go, 120 bytes

JavaScript, 56 bytes

Factor, 59 55 bytes

Pip, 33 bytes

Pip, 37 bytes

Linked

Related

Hot Network Questions