21
\$\begingroup\$

Given a positive integer, determine if it can be represented as a concatenation of two square numbers. Concatenated numbers may not begin with 0 (except for 0). Any leading zeros in input should be ignored.

Examples

11 -> true // because 1 and 1 are squares  
90 -> true // because 9 and 0 are squares  
1001 -> true // because 100 and 1 are squares  
144100 -> true // because 144 and 100 are squares  
151296561 -> true // because 15129 and 6561 are squares  
164 -> true // because 1 and 64 are squares (also 16 and 4)  
101 -> false // can't be 1+01 as a number may not begin with 0  
016 -> false // leading 0 is ignored and 16 doesn't count
9 -> false // need two squares  
914 -> false // need two squares (there are three)

Task

Given a positive integer return a value indicating if it is a concatenation of two squares.

This is code-golf the goal is to minimize the size of the source code as measured in bytes.

\$\endgroup\$
3
  • 3
    \$\begingroup\$ Welcome to the site. It is generally recommended to use the sandbox to get help on questions before posting. \$\endgroup\$
    – Wheat Wizard
    Feb 10 at 13:54
  • \$\begingroup\$ Related \$\endgroup\$
    – Fatalize
    Feb 10 at 16:37
  • 4
    \$\begingroup\$ Suggested test cases: 361, 3614, 36144 (all true) \$\endgroup\$
    – Nitrodon
    Feb 10 at 21:48

21 Answers 21

9
\$\begingroup\$

Brachylog, 7 bytes

~cĊ~^₂ᵐ

Try it online!

Explanation

~cĊ       Deconcatenate into a couple of 2 elements Ċ
  Ċ~^₂ᵐ   Each element of Ċ must be the square of a number
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Basically the same answer as for "Sum of two squares", with ~c instead of ~+. \$\endgroup\$
    – Fatalize
    Feb 10 at 16:39
  • 1
    \$\begingroup\$ As soon as I saw the question I thought "Brachylog would be perfect for this" :) \$\endgroup\$
    – Sundar R
    Feb 10 at 18:14
8
\$\begingroup\$

R, 42 bytes

function(x)x%in%outer(y<-(0:x)^2,y,paste0)

Try it online!

Same horribly-inefficient approach as my Husk answer.

R's %in% function to search for an element in a vector conveniently appears to cast its arguments to the same type (here the numeric input x and the character vector of pasted-together squares), which was a nice surprise to me.

Note: After reading Fatalize's comment, I realise that this answer is also very close to pajonk's answer to the "Sum of two squares" challenge. Note though that that answer wasn't the shortest in R, so a small change to the challenge does seem to favour a completely different approach, which is also nice.

\$\endgroup\$
7
\$\begingroup\$

Python 3.6 (with IO), 73 bytes

n=input();l=range(int(n));print(n in[f"{i*i}{j*j}"for i in l for j in l])

You could also use,

n=input();l=range(int(n));print({n}&{f"{i*i}{j*j}"for i in l for j in l})

But unfortunately it doesnt output booleon values rather it outputs, {n} for True and set() for False

Try on Online

slightly longer answer (By 2 bytes)

n=int(input());print(str(n)in[f"{(k//n)**2}{(k%n)**2}"for k in range(n*n)])

and without a loop

n=int(input());m=k=0;exec('m+=f"{(k//n)**2}{(k%n)**2}"==str(n);k+=1;'*n**2);print(m>0)
\$\endgroup\$
2
  • 3
    \$\begingroup\$ Welcome to Code Golf, and nice first answer! It'd be nice if you added a TIO link so others could test your code. \$\endgroup\$
    – emanresu A
    Feb 12 at 8:09
  • \$\begingroup\$ @emanresuA Thanks for pointing that out. I think 've added it correctly. :) \$\endgroup\$ Feb 12 at 16:08
5
\$\begingroup\$

Julia, 130 122 98 91 bytes

!x=√parse(Int,x)%1
f(a,s="$a",l=length(s))=0∈1:~-l.|>i->s[l-i]<'1'||!s[i+1:end]+!s[1:i]

Try it online!

Thanks to Sunda R we can save 8 bytes!

Thanks to MarcMush we can save 32 39 bytes!

\$\endgroup\$
11
  • 1
    \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$ Feb 13 at 21:35
  • 1
    \$\begingroup\$ f(a,s="$a",l=length(s))=0 in[startswith(last(s,l-i),r"0.+")+(parse(Int,last(s,l-i))^.5+parse(Int,s[1:i])^.5)%1 for i=1:l-1] for -6 bytes. \$\endgroup\$
    – Sundar R
    Feb 14 at 10:10
  • 1
    \$\begingroup\$ f(a,s="$a",l=length(s))=0 in[occursin(r"^0.+",last(s,l-i))+(parse(Int,last(s,l-i))^.5+parse(Int,s[1:i])^.5)%1 for i=1:l-1] to lose 1 more byte. \$\endgroup\$
    – Sundar R
    Feb 14 at 10:15
  • 1
    \$\begingroup\$ By the way, my last code above seems to be 1.0 compatible: Try it online! (also, my wc counting locally somehow messed up, my first change is -7 bytes actually) \$\endgroup\$
    – Sundar R
    Feb 14 at 10:29
  • 1
    \$\begingroup\$ Glad to hear that! About TIO, the code works now because I replaced the startswith call with an occursin call (to reduce 1 byte). startswith takes regular expressions only from Julia 1.2, that's why it wasn't working previously. \$\endgroup\$
    – Sundar R
    Feb 14 at 10:39
4
\$\begingroup\$

Husk, 12 bytes

€s¹Σ´Ṫ+mos□ŀ

Try it online!

Outputs nonzero for 'concats of two squares', zero for numbers that aren't.

Builds a list of 'concat of two squares' numbers, and then checks if the input is present. So not very efficient for large inputs...

€s¹Σ´Ṫ+
       mos    # get strings of 
          □ŀ  # all squares up to input,
    ´Ṫ        # combine all combinations
      +       # by concatenation,
   Σ          # flatten the list-of-lists
€s¹           # and look for the input as a string
\$\endgroup\$
4
\$\begingroup\$

JavaScript (Node.js), 56 53 bytes

2 byte from tsh

x=>(g=_=>x--&&x*x+'|'+g(),x+g).match(`^(${g()}){2}_`)

Try it online!

RegEx with many choices

\$\endgroup\$
1
  • \$\begingroup\$ (g=y=>x&&x*x+'|'+g(x--))() \$\endgroup\$
    – tsh
    Feb 11 at 5:26
3
\$\begingroup\$

Burlesque, 29 bytes

Jsuf{?sXXsm}0_+)up2CB)++jup~[

Try it online!

J   # Duplicate
su  # Substrings of
f{  # Filter for
 ?s # Sqrt
 XX # [floor, ceil]
 sm # Same (i.e. is int)
}   # -- Is square
0_+ # Append 0 to list
)up # Unparse each to str
2CB # Combinations of pairs
)++ # Mapped Concat 
j   # Reorder stack
up  # Unparse input
~[  # Is in list
\$\endgroup\$
3
\$\begingroup\$

C (gcc), 127 125 bytes

i;r;q(n){for(r=i=n;i;--i)r=r&&i*i-n;i=!r;}t;h;m;f(n){for(t=h=0,m=1;n>9;n/=10,m*=10)n%10|m<2?h+=n%10*m,t|=q(n/10)*q(h):0;n=t;}

Try it online!

Saved 2 bytes thanks to ceilingcat!!!

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

Haskell, 54 51 bytes

f n|l<-show.(^2)<$>[0..n]=elem(show n)$(++)<$>l<*>l

Try it online!

  • Thanks to @ovs for saving 3 Bytes.

So much inefficient approach:
l is all numbers up to input squared and to string.
We search trough the powerset of l if there is a pair that form the input

\$\endgroup\$
2
  • \$\begingroup\$ 51 with <$> and <*>. \$\endgroup\$
    – ovs
    Feb 11 at 9:22
  • \$\begingroup\$ @ovs thanks! I was just trying something similar but messed with any(==show n) ending at the same byte count, using elem was very clever \$\endgroup\$
    – AZTECCO
    Feb 11 at 9:48
3
\$\begingroup\$

Python 2, 68 bytes

Inefficient and somewhat boring approach.

lambda n:`n`in('%d'*2%(a*a,b*b)for a in range(1,n)for b in range(n))

Try it online!


Python 2, 77 bytes

Much more efficient and interesting.

f=lambda n,m=0,d=1:n and((m*10<d!=10)==n**.5%1+m**.5%1)|f(n/10,m+n%10*d,d*10)

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ For me is less boring the inefficient one :-p \$\endgroup\$
    – AZTECCO
    Feb 11 at 11:32
3
\$\begingroup\$

Perl 5 -ap, 69 64 bytes

$_=grep{1<grep/^0$|^[^0]/&sqrt!~/\./,unpack$_."A*","@F"+0}A1..A9

Try it online!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Nice one! You can save 5 bytes too utilising @F: Try it online! \$\endgroup\$ Feb 11 at 18:48
  • \$\begingroup\$ @DomHastings - thanks, fixed now. I tried "@F" but without +0. My original answer was: Try it online! \$\endgroup\$
    – Kjetil S
    Feb 12 at 10:44
3
\$\begingroup\$

Perl 5 -nE, 78 61 bytes

say int=~/^((.+)(?(?{$+eq(0|$+)&(0|sqrt$+)**2==$+})|^))(?1)$/

Try it online!

A whopping -17 bytes thanks to @kjs.

Explanation:

say int                      # convert input to number to remove leading 0s
        =~                   # and match it against the regex
           /^(               # match from the beginning of input
           (.+)              # match 1 or more digits
           (?                # evaluate a condition here
             (?{             # the condition is the result of this code
               $+            # the digits matched so far are in $+
               eq            # string equality check
               (0|$+)        # int($+) - golfy way of writing it
                             # if they're equal, no leading 0s here     
               & 
               (0|sqrt$+)    # again, golfy form of int(sqrt($+))
               **2==$+}      # square that and compare to original number
               )             # if no leading zeroes and number is a square
                             # do nothing and move on 
             |               # else
             ^               # add an impossible pattern here so regex match fails
             )
             )               
             (?1)            # now do the same match again, for the second square
             $               # and that should be the end of input
             /x;

The trick is in exploiting regex "backtracking" mechanism. Any time the part of the string we're looking at doesn't match the conditions we want, we make the match fail deliberately so that the regex engine chooses a different subset of the input string for the /(.+)/, and automatically tries the match again.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Yes, cool method, but 17 bytes can be shaved off to get 61 bytes. And perhaps even less?: Try it online! \$\endgroup\$
    – Kjetil S
    Feb 11 at 18:34
  • \$\begingroup\$ @kjs Thanks a lot! It has been forever since I wrote Perl - normal or golfed - and had to refer to the Perl golfing tips even for the (0|$n) trick. Now it looks like proper golfed code! \$\endgroup\$
    – Sundar R
    Feb 14 at 9:59
  • \$\begingroup\$ (I just chose Perl because I knew I could reliably stretch its regex engine to extremes and it would happily bend to it.) \$\endgroup\$
    – Sundar R
    Feb 14 at 10:00
  • \$\begingroup\$ Save a byte by negating the condition: (?{$+ne(0|$+)|(0|sqrt$+)**2!=$+})^). \$\endgroup\$
    – Neil
    Feb 19 at 14:33
3
\$\begingroup\$

Julia 1.0, 47 44 37 bytes

~n="$(n^2)"
!a="$a"∈.~(r=0:a)'.*.~r

Try it online!

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

Retina 0.8.2, 55 bytes

^0+

\B
$'¶$`;
A`;0.
\d+
$*
m`(^1|11\1)+;(1(?(2)1\2))*$

Try it online! Link includes faster test cases (a ^ after the m` would speed it up enough to be able to check 151296561 on TIO). Outputs the count of square concatenations, so for example 144100 can be split up as 144 and 100 or alternatively as 1 and 44100, so the output would be 2 in that case. Explanation:

^0+

Delete leading zeros.

\B
$'¶$`;

Try splitting between every pair of digits.

A`;0.

Delete numbers with leading zeros.

\d+
$*

Convert to unary.

m`(^1|11\1)+;(1(?(2)1\2))*$

Match two square numbers. (1(?(2)1\2))* is a generalised match for a square number; (^1|11\1)+ is a simplified special case for a non-zero square to be matched at the start (of a line).

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

Julia 1.0, 38 47 bytes

~a=string.(a.^2);!a=any(~(0:a)'.*~(0:a).=="$a")

Try it online!

Based on MarcMush’s answer (tnx for pointing out the error when squaring)

\$\endgroup\$
0
1
\$\begingroup\$

Python 3.8 (pre-release), 92 bytes

f=lambda n,x=1:x<len(n)and all(e[0]!='0'and int(e)**.5%1==0for e in[n[:x],n[x:]])or f(n,x+1)

Try it online!

-28 for @ophact's tip

\$\endgroup\$
4
  • 2
    \$\begingroup\$ Combine the two alls together and remove space between in and [ \$\endgroup\$
    – ophact
    Feb 11 at 6:31
  • \$\begingroup\$ @ophact thanks! haven't golfed for a while so I missed it \$\endgroup\$
    – Wasif
    Feb 11 at 7:42
  • \$\begingroup\$ 91 \$\endgroup\$
    – l4m2
    Feb 11 at 8:28
  • \$\begingroup\$ Why infloop for 90? \$\endgroup\$
    – l4m2
    Feb 11 at 8:30
1
\$\begingroup\$

05AB1E, 8 bytes

ÝāsânJIå

Based on my 05AB1E answer for the Sum of two squares challenge.

Try it online or verify (almost) all test cases (151296561 is omitted since it'll timeout).

Explanation:

Ý         # Push a list in the range [0, (implicit) input]
 ā        # Push a list in the range [1,length] (without popping the list)
  s       # Swap so the [0,input] list is at the top
   â      # Cartesian product: create all possible pairs using these two lists
    n     # Square each inner integer
     J    # Join each pair together
      Iå  # Check if the input is in this list
          # (after which the result is output implicitly)

We can't just use the range \$[0,input]\$ twice, since it would create a false positive with for example "09" and input 9. We also can't just use the range \$[1,input]\$ twice, since it would fail with for example input 90. Hence the use of the range \$[1,input+1]\$ with \$[0,input]\$ for the creation of pairs with the cartesian product instead.

\$\endgroup\$
1
+50
\$\begingroup\$

Vyxal, 37 bytes

Probably can be golfed a lot, but this is too long for me. So basically for every i in input n, it checks if both n[:i] and n[i:] are squares.
I think the time complexity is \$O(2*\mathrm{len}(n)) \$

Lʁƛ?fnȯṅ:h⌊[⌊|3]∆²→?fẎṅ:h⌊[⌊|3]∆²←∧;a

Explanation:

Lʁƛ?fnȯṅ:h⌊[⌊|3]∆²→?fẎṅ:h⌊[⌊|3]∆²←∧;a
Lʁ                                     Exclusive 0 range of length(n)                                    
  ƛ                                    Map through range
   ?f                                  Push stringified n
     nȯṅ                               Slice from loop index to end
        :h⌊[⌊|3]                        Duplicate slice, if int(head) = 0, push 3 (non-square) else int(slice)
               ∆²→                     Set var to "is a perfect square?"
                  ?f                   Push stringified n
                    Ẏṅ                 Slice from 0 to loop index
                      h⌊[⌊|3]           Duplicate slice, if int(head) = 0, push 3 (non-square) else int(slice)
                            ∆²         Is it a perfect square?
                              ←        Get var
                               ∧       Are both are squares?
                                ;a     End map, check if any element is true.

Try it Online!

\$\endgroup\$
1
\$\begingroup\$

MATL, 33 bytes

Vf3L)"GV@:&),tUV=A3MtX^kU=*w]*?T.

Try it out

Outputs 1 for truthy, nothing for falsey.

V           % take in number (ignoring initial 0s) and convert to string
f           % get list of its indices (starting from 1)
3L)         % remove the last index
"           % for 1 to end-1
  GV        % get input as string again, say S
  @         % get the current loop index i
  :         % form range 1:i
  &)        % split S[1:i] and S[i+1:end]
  ,         % for each split part
    t       % duplicate it
    U       % convert to numeric
    V       % and back to string - this gets rid of initial 0s
    =A      % condition 1: did that give the same string back? 
    3M      % get the numeric form N of the current part again
    tX^kU   % floor(sqrt(N))^2
    =       % condition 2: did that get the number back
            %   i.e. is it a square number
    *       % AND those conditions
    w       % swap the other part in to be checked
  ]         % end
  *?        % if both parts satisfied the conditions
    T       % save True to output
    .       % break
            % (implicit) end
            % (implicit) end
            % (implicit) convert to string and display
\$\endgroup\$
1
\$\begingroup\$

Vyxal, 10 bytes

›₌ɾʁẊ²vṅ⌊c

Try it Online!

An 05AB1E port.

Explained

›₌ɾʁẊ²vṅ⌊c
›          # Increment the input
 ₌ɾʁ       # The range [1, input + 1] and the range [0, input + 1)
    Ẋ      # Cartesian product of those ranges
     ²     # Square each number in each pair
      vṅ⌊  # Integer version of each pair concatenated into a single string
         c # Does that contain the original input? 
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 20 bytes

⊙…¹Iθ⊙…⁰Iθ⁼θ⪫X⟦ιλ⟧²ω

Try it online! Link is to verbose version of code. Takes input as a string and outputs a Charcoal boolean, i.e. - for a concatenation of two squares, nothing if not. Explanation:

 …                      Range from
  ¹                     Literal integer `1`
    θ                   To input
   I                    Cast to integer
⊙                       Does any satisfy
      …                 Range from
       ⁰                Literal integer `0`
         θ              To input
        I               Cast to integer
     ⊙                  Does any satisfy
           θ            Input as a string
          ⁼             Equals
              ⟦ιλ⟧      List of loop variables
             X          Vectorised to power
                  ²     Literal integer 2
            ⪫      ω    Joined
\$\endgroup\$

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.