11
\$\begingroup\$

Inspired by Greg Martin's "Shiny cryptarithm" puzzle.

A cryptarithm is a game consisting of a mathematical equation among unknown numbers, whose digits are represented by letters of the alphabet. The goal is to identify the value of each letter. They are usually represented by an addition operation, such as SEND + MORE = MONEY. In this case, replacing O with 0, M with 1, Y with 2, E with 5, N with 6, D with 7, R with 8 and S with 9 yields 9567 + 1085 = 10652, a correct equation.

But what if they were represented by a square-root operation?

Input

Two strings, \$a\$ and \$b\$, composed exclusively by letters, representing the cryptarithm

$$\sqrt{c^a_1c^a_2c^a_3...c^a_{n-2}c^a_{n-1}c^a_{n}} = c^b_1c^b_2c^b_3...c^b_{m-2}c^b_{m-1}c^b_{m}$$

where \$c^x_y\$ is the character of input string \$x\$ at position \$y\$ (1-indexed), \$n\$ is the length of \$a\$ and \$m\$ is the length of \$b\$.

The operation between the digits is concatenation, not multiplication.

You can assume that always \$n \geq m\$.

For example, for input "abacus" and "tab", the following cryptarithm shall be solved:

$$\sqrt{ABACUS} = TAB$$

where the same letter always represents the same digit, numbers don't start with 0 and two different letters may represent the same digit.

Replacing A and U with 7, B and S with 6, C with 3 and T with 8 yields

$$\sqrt{767376} = 876$$

a valid (and the only) solution.

You can choose to accept either only uppercase letters or only lowercase letters as input (or both).

Output

The number on the right-hand side of any solution of the given cryptarithm. In the previous example, you must output \$876\$.

If the given cryptarithm has more than one solution, you can output either one indistinctly.

If the given cryptarithm has no solution, output a fixed and consistent value indicating that (such as an empty string).

Test samples

abacus, tab -> 876
illuminate, light -> 75978
abalienation, backup -> 758524 or 999700
balletic, scar -> 3636 or 6412 or 7696 or 7923
felicitation, zipper -> 759977
preestablish, chains -> 400000 or 500000 or 600000 or 603660 or 700000 or 800000 or 900000 or 903660
spathiphyllum, cyborg -> no solution
transiently, myth -> no solution
accelerometer, biotin -> no solution

The briefest code in bytes prevails.

\$\endgroup\$
5
  • 3
    \$\begingroup\$ I'd suggest making it more prominent that two different letters may represent the same digit, since it's not the way I usually see this things work, and it's written in an example paragraph which is easy to miss. \$\endgroup\$
    – xnor
    Commented Jan 28 at 18:46
  • \$\begingroup\$ @xnor I made it bold now, thanks for the input \$\endgroup\$
    – enzo
    Commented Jan 28 at 18:48
  • 1
    \$\begingroup\$ @JonathanAllan Yes, you can assume the input will always be len(a) >= len(b). Don't need to handle these cases. Will update the question to include that \$\endgroup\$
    – enzo
    Commented Jan 28 at 22:40
  • \$\begingroup\$ Is there any solution better than brute-force? \$\endgroup\$
    – qwr
    Commented Jan 30 at 18:35
  • 1
    \$\begingroup\$ @qwr I can think of different degrees of brute-forcing. For example, the maximum brute-force is generating all Bs, squaring them, and checking whether they could match A. However, you could also be a bit more clever there by generating the B one digit at a time, starting from the lowest digit, since the lowest digit of B*B is the lowest digit of the square of the lowest digit of B, so proceeding one digit at a time may rule out many combinations at once. \$\endgroup\$ Commented Jan 31 at 10:43

12 Answers 12

6
\$\begingroup\$

JavaScript (ES12), 93 bytes

Expects "string_b,string_a" and returns an integer (0 if there's no solution).

s=>eval("for(n=10**s.search`,`;n&&(q=n+[,n*n])!=s.replace(o=/\\w/g,(c,i)=>o[c]||=q[i]);)--n")

Attempt This Online!

Commented

This is a version without eval() for readability.

s => {                  // s = "string_b,string_a"
  for(                  // loop:
    n =                 //   n = counter, initialized to 10 ** L,
      10 **             //       where L = length of string_b (i.e.
      s.search`,`;      //       the 0-indexed position of the comma)
    n &&                //   stop if n = 0 (no solution)
    (q = n + [, n * n]) //   define the string q as the concatenation
    !=                  //   of n and n², separated by a comma
    s.replace(o =       //   o = object to store letter replacements
      /\w/g,            //   for each letter ...
      (c, i) =>         //   ... c at index i in s:
        o[c] ||= q[i]   //     replace c with o[c], which is set to
                        //     q[i] if still undefined
    );                  //   end of replace()
                        //   stop if the result is identical to q
  )                     //
    --n;                //   decrement n at each iteration
                        // end of for()
  return n              // return the final value of the counter
}                       //
\$\endgroup\$
6
  • \$\begingroup\$ Fail \$\endgroup\$
    – l4m2
    Commented Jan 29 at 5:36
  • \$\begingroup\$ Still fail \$\endgroup\$
    – l4m2
    Commented Jan 29 at 8:03
  • \$\begingroup\$ Fail all cases where answer exist \$\endgroup\$
    – l4m2
    Commented Jan 29 at 8:13
  • \$\begingroup\$ Though I don't get why this returns 0 \$\endgroup\$
    – l4m2
    Commented Jan 29 at 8:18
  • \$\begingroup\$ Get it, you're in an eval so \ is parsed there \$\endgroup\$
    – l4m2
    Commented Jan 29 at 8:26
4
\$\begingroup\$

Jelly,  27  26 bytes

Faster version (also 26)

ẈḢ⁵*Ṗ²ĖDṁ"ƑƇF⁹ịEƇƑʋƇFĠ$ḌḢ€

A monadic Link that accepts a list of two lists of characters [b, a] and yields a list of all solutions.

Try it online!

How?

ẈḢ⁵*Ṗ²ĖDṁ"ƑƇF⁹ịEƇƑʋƇFĠ$ḌḢ€ - Link: [b, a]
ẈḢ⁵*                       - lengths, head, 10^ -> 10^(length(b))
    Ṗ                      - pop -> [1,2,...,10^(length(b))-1]
     ²                     - square these -> [1,4,9,26,...]
      Ė                    - enumerate -> [[1,1],[2,4],[3,9],[4,16],...]
       D                   - convert to decimal digits
        ṁ"ƑƇ               - keep if invariant under zipped mould-like
                              (i.e. those shaped like the input strings)
                   Ƈ       - keep those for which:
                  ʋ        -   last four links as a dyad...
                               ... with right argument:
                      $    -     last two links as a dyad - f([b,a]):
                    F      -       flatten
                     Ġ     -       group indices by their values
            F              -     flatten {the potential pair of digit lists}
             ⁹             -     right argument -> the grouped indices
              ị            -     {grouped indices} index into {flattened potential}
               EƇƑ         -     is invariant under keep if all equal
                           -  (i.e. those with equal digits at equal characters)
                       Ḍ   - convert from decimal digits
                        Ḣ€ - head of each

Original version

-1 thanks to emanresu A (don't deduplicate the characters - slowing it even more :p - and then only yield a single solution to avoid repeats.)

F,Ɱe€r9Œpɗ¥ZḢ$yⱮ€⁸Ḍ²⁼¥/ƇḢ€

A monadic Link that accepts a list of two lists of characters [b, a] and yields a solution if any exist, or zero if not.

Try it online! (Too inefficient for the given test cases!)

How?

F,Ɱe€r9Œpɗ¥ZḢ$yⱮ€⁸Ḍ²⁼¥/ƇḢ€ - Link: P = [b, a]
F                          - flatten P -> all characters
             $             - last two links as a monad - f(P):
           Z               -   transpose
            Ḣ              -   head -> first characters of each of b & a
          ¥                - last two links as a dyad - f(alphabet, firsts):
         ɗ                 -   last three links as a dyad - f(alphabet, firsts):
   e€                      -     for each: exists in? -> 1 if a first, 0 otherwise
     r9                    -     inclusive range with 9 (vectorises)
                                  -> list of valid digits for each of our alphabet
       Œp                  -     Cartesian product -> list of possible digit values
  Ɱ                        -   map across D in that:
 ,                         -     {our alphabet} pair with {D}
                                -> assignment map
                €          - for each:
               Ɱ ⁸         -   map across {[b, a]} with:
              y            -     translate
                  Ḍ        - convert from decimal (vectorises)
                       Ƈ   - filter keep those for which:
                      /    -   reduce by:
                     ¥     -     last two links as a dyad:
                   ²       -       square {the translated b}
                    ⁼      -       equals {the translated a}?
                        Ḣ  - head (0 if empty)
                         Ḣ - head (0 if 0)
\$\endgroup\$
2
  • \$\begingroup\$ You can remove the Q for 26, at the cost of only outputting one solution and a huge performance detriment. \$\endgroup\$
    – emanresu A
    Commented Jan 28 at 22:41
  • \$\begingroup\$ Nice spot @emanresuA. I can't help but think there is a shorter way, but the leading zeros do seem to play havoc. \$\endgroup\$ Commented Jan 28 at 23:06
4
\$\begingroup\$

05AB1E, 26 25 bytes

9ÝIS©gãε®s:}ʒ€нPĀ}.Δ`tQ}н

Input pair in reversed order. Will output - when there is no solution.

Way too slow to even output the example test case, but works in theory..
-1 byte and even slower by removing the uniquify..

Try it online (with a very small test case).

Explanation:

9Ý       # Push list [0,1,2,3,4,5,6,7,8,9]
  I      # Push the input-pair
   S     # Convert the pair of strings to a flattened list of characters
    ©    # Store this in variable `®` (without popping)
     g   # Pop and push its length
      ã  # Cartesian product of the [0,9]-ranged list and this length
ε        # Map over each list of digits:
 ®       #  Push the input-characters of variable `®`
  s      #  Swap so the list of digits is at the top
   :     #  Replace all characters with these digits in the (implicit) input-strings
}ʒ       # After the map: Filter it by:
  €н     #  Get the first digit of both integer-strings
    P    #  Take the product of that
     Ā   #  Check that this is NOT 0
         # (so neither integer-string has leading 0s)
 }.Δ     # After the filter: find the first that's truthy for
         # (or -1 if none are):
    `    #  Pop the pair, and push both values to the stack
     t   #  Take the square-root of the second/largest one
      Q  #  Check if this square-root is equal to the first/shortest converted input
   }н    # After the find first: only leave the first item (or the "-" of the -1)
         # (which is output implicitly as result)
\$\endgroup\$
3
\$\begingroup\$

Vyxal, 26 bytes

∑Lkd↔ƛ?:∑nvĿ;'⌊=A$⌊÷²=∧;ht

Try it Online! Returns 0 for no solution.

Here's a slightly more performant version.

     ↔                      # Combinations with replacement of
   kd                       # Digits 0 to 9
  L                         # With length of
∑                           # both inputs
      ƛ      ;              # For each
           vĿ               # Transliterate each of
       ?                    # Both inputs
        :∑                  # Replacing each character in the input
          n                 # With the corresponding digits in that combination
              '         ;   # Filter by
                =A          # All remaining the same under
               ⌊            # Conversion to int (i.e. not starting with 0)
                       ∧    # And
                     ²      # Square of
                  $⌊÷       # Second item
                      =     # Equals
                  $⌊÷       # First item
                         ht # Find the first solution and get the second item
\$\endgroup\$
3
\$\begingroup\$

Charcoal, 50 bytes

IΦ…Xχ⊖LηXχLη∧⁼L×ιιLθ⬤⁺ηθ¬⁻⌕A⁺ηθλ⌕A⁺IιI×ιι§⁺IιI×ιιμ

Try it online! Link is to verbose version of code. Explanation:

IΦ…Xχ⊖LηXχLη

Filter from the range 1000..9999 (appropriate number of digits for the second input), where...

∧⁼L×ιιLθ

... the number of digits in the square equals the number of letters in the first input, and...

⬤⁺ηθ

... for each letter in the two inputs, ...

¬⁻⌕A⁺ηθλ⌕A⁺IιI×ιι§⁺IιI×ιιμ

the corresponding digit in the integer or its square appear in at least all of the places where the letter appears in the two inputs.

\$\endgroup\$
3
\$\begingroup\$

Ruby, 88 bytes

->a,b{(1..10**b.size).find{|x|!(a+b).chars.zip("#{x*x}#{x}".chars).uniq.uniq!(&:first)}}

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Perl 5 -MList::Util=uniq -nF, 111 84 bytes

$"=$,;map{$_=eval"'@F'=~y/@l/${_}0/r";/,/;$'**2-$`||/\b0/||say$'}0..9x(@l=uniq/\w/g)

Try it online!

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

Python3, 258 bytes

def l(v,r):
 for i in range(10**(len(r)-1),10**len(r)):
  if(L:=len(K:=str(i*i)))==len(v):
   d={}
   for a,b in zip(v,K):d[a]={*d.get(a,[]),b}
   if all(len(d[j])==1 for j in d)and all(d.get(a,{b})=={b}for a,b in zip(r,str(i))):return i
  if L>len(v):return

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ The 10**(len(r)-1), in the range is redundant in terms of golf. (This can probably all be golfed a lot more.) \$\endgroup\$ Commented Jan 28 at 20:15
2
\$\begingroup\$

Pyth, 25 bytes

eefqF^VTS2mm.vXksQ`dQ^Tls

Try it online!

Takes input as a list of two strings [a, b] and returns an integer. Returns 0 if there is no solution.

Explanation

                              # implicitly assign Q = eval(input())
eefqF^VTS2mm.vXksQ`dQ^TlsQ    # implicitly add Q
                     ^TlsQ    # 10 ^ len(sum(Q))
          m                   # map lambda d over the range of this integer
           m        Q         #   map lambda k over Q
              XksQ`d          #     translate k from sum(Q) to str(d) with modular indexing
            .v                #     pyth eval (this has the useful property that if there is a leading 0 this will return 0 since that counts as its own token)
  f                           # filter over lambda T
     ^VTS2                    #   vecotrized exponentiation of T and (1, 2)
   qF                         #   both elements are equal
ee                            # take the last value (this will be 0 iff there are no other solutions)

Obligatory slightly faster version for 27 bytes

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

Python 3, 206 203 184 bytes

Extremely slow, but works..

-19 bytes thanks to @enzo

def f(a,b):
 C=[*{*(a+b)}];l=len(C)
 for i in range(10**l-1):
  D=dict(zip(C,f"{i:0{l}}"))
  x,y=[''.join(D[c]for c in d)for d in(a,b)]
  if(x[0]>"0"<y[0])*(int(x)==int(y)**2):return y

Try it online!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Great answer! You could subtract 8 bytes by removing the last return statement (since it's implicit when the function ends), 9 bytes by creating x and y from a list comprehension (x,y=[''.join(D[c]for c in x)for x in(a,b)]), 1 byte by declaring C and l on the same line (C=...;l=...) and another 1 byte by replacing and with * (explanation). \$\endgroup\$
    – enzo
    Commented Jan 31 at 12:29
  • 1
    \$\begingroup\$ Thanx... how did I miss the the last two optimizations I knew but somehow missed... the list comprehension is a nice catch, I tried some other stuff to get rid of the redundant code, but couldn't come up with that trick :) \$\endgroup\$
    – movatica
    Commented Jan 31 at 21:18
2
\$\begingroup\$

Python 3, 151 bytes

lambda a,b:[j for i,j,k in[[int(''.join((len(a+b)*str(f))[(a+b).find(h)]for h in g))for g in(a,b,b[0])]for f in range(10**len(a+b))]if(k>0)*j*j==i][-1]

Try it online!

Port of my pyth answer. Takes input as two strings a, b and returns an integer. Returns 0 if there is no solution.

Fairly surprised at how short this is with all the nested list comprehensions

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

R, 281 bytes

Here is a very slow version in R. Exceeds 60 seconds but could be tested in RStudio.

Edit:

works online with a minimal example ("aba","ta").

\(a,b){'?'=\(x)strsplit(x,"")[[1]];w=unique(c(?a,?b));m=length(w);for(j in 10^(m-1):(10^m-1)){n=?sprintf("%d",j);'*'=\(g,h){substr(g,h,h)<-n[which(w==(?g)[k])];g};for(k in 1:nchar(d<-a))d=d*k;for(k in 1:nchar(e<-b))e=e*k;'+'=as.numeric;if((+e)^2==+d){cat(e,"\n");T=F}};if(T)cat(0)}

Attempt This Online!

\$\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.