Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It only takes a minute to sign up.
Sign up to join this community
A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself.
Calculate the number of perfect squares below a number \$n\$ where \$n\$ will be taken as an input
Examples:
There are 9 perfect squares below 100: 1, 4, 9, 16, 25, 36, 49, 64, 81
Constraints: \$0<n<10^6\$
Since this is a golfing challenge, the entry with least amount of bytes will win.
Best of Luck!
,>>>>>>+[-<<<<<+[>+>+>+<<<-]>[-<+>]>[>[>+<<<+>>-]>[<+>-]<<-]>[-]<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[>+<<[>>[-]>+<<<-]>>>[<<<+>>>-]<[>>+<<-]<<->-]<[-]>>>>]<<<<<-.
Finally, a challenge simple enough that I could attempt some brainfuckery.
Credits to https://esolangs.org/wiki/Brainfuck_algorithms for the squaring algorithm and the comparison algorithm ideas, Fatih Erikli's brainfuck visualizer, and to El Brainfuck for quick runs.
(Also to user202729 for noticing an unnecessary space in the code and for a link with a bash I/O wrapper.)
Calculates \$ i^2 \$ for each \$ i \$ starting from 1, and checks if \$ i^2 < n \$. Returns the last \$ i \$ for which that's true.
Input and output are usually ASCII characters representing numbers. For eg., in the TIO link, input Now links to a version that takes and returns numeric I/O directly. Assumes a wrapping implementation (for the comparison algorithm).d (ASCII 100) returns character tab \t (ASCII 9).
, n input
> i = 0
> isqr/temp0
> icopy1/ncopy/temp1
> icopy2/temp2
> temp3
> exitflag (is isqr lt n)
+[- while exitflag not 0
<<<<<
+ increment i
[>+>+>+<<<-] make 3 copies of i (destructively)
>[-<+>] use one of them (temp0) to restore i
Squaring by multiplying icopy1 with icopy2:
>[ while icopy1 not 0
>[>+<<<+>>-] copy icopy2 to temp3 and add it to isqr
>[<+>-] restore icopy2 from temp3
<<- decrement icopy1
]
>[-] reset temp2 (icopy2) to 0
Comparing n and isqr:
<<<<[>>>+>+<<<<-] copy n to ncopy and temp2
>>>>[<<<<+>>>>-] restore n from temp2
<[ while ncopy
>+ increment temp2 as flag
<<[>>[-]>+<<<-] if isqr gt 0 reset temp2 (destroys isqr & copies to temp3)
>>>[<<<+>>>-] restore isqr from temp3
<[>>+<<-] set exitflag to 1 if temp2 was not reset
<<->- decrement isqr & decrement ncopy
]
<[-] reset isqr (would have been set to negative of n minus isqr)
>>>> check the flag and exit if isqr gt n
]
<<<<<-. decrement i by 1 and output
!
Use byte-value input/output. Can only process numbers up to maximum cell value. Requires a tape that has at least 3 cells to the left and 2 cells to the right of the initial memory pointer.
+>>,[<[<<]<[[<+>>+<-]++<[>+<-]<<+>]>>>->-]<<<<<-.
(with nice Bash wrapper that converts decimal input/output to byte input/output)
Based on the identity \$1 + 3 + 5 + \dots + (2n-1) = n^2\$ (so it subtracts 1, then 3, then 5, then 7, ... from the input \$n\$ until it is \$\le 0\$, then count number of subtraction)
Explanation:
# Mem layout: {r t A a c x}. Ptr initially at {a}.
# {t} == 0. r == result. a == 1, then increase to 3, 5, ...
# {c} counts from {a} to 0.
# {x} is the input, gradually decremented.
+ # a=1
>>, # read x
[ # while x:
< # goto c
[<<]< # if c, goto {t}, else goto {a}
[ # if not c:
[<+>>+<-] # A=c=a; a=0
++<[>+<-] # a=2+A; A=0
<<+> # r+=1
]
# now mem pointer is at {t} regardless of initial
# value of {c}, and c!=0
>>>- # c-=1
>- # x-=1
]
<<<<<-. # print r-1
Compilable Python code works the same way -- explanation in reverse.
’ƽ
Simply takes the floor of the square root of \$n-1\$. Assumes \$0\$ should be counted and assumes that we ought to find the number of perfect squares strictly lower than \$n\$. (This is just an illustration of why such trivial challenges are discouraged)
f=n=>--n&&!(n**.5%1)+f(n). Now, n=>--n**.5|0 should work for 12 bytes.
\$\endgroup\$
0 (wrongly) shouldn't be counted. Work away with that 12 byte version, was too rushed to figure out the Maths! ;)
\$\endgroup\$
{({}[()]<(({})){(<{}({}[({})({}[()])])>)}{}({}({})({}())[()])>)}{}{}({}[()])
Uses a simple counting method. It has 3 counters, the number, the slice and the result. We decrement the number until it reaches zero, each time we do we also decrement the slice if it is non-zero. If the slice is zero we increment the result and set the slice to one less than twice the result.
This computes the square root via the sum of consecutive odds.
Also based on the identity \$1 + 3 + 5 + \dots + (2n-1) = n^2\$ . Thanks to H.PWiz for saving some bytes.
dip f 1
f
+ 1 > - A f F
F
> - i r
+ 1 1 >
i
i I
I
>
>
r
>
> - A
A
+ >
+
-
- dip
1
dip + _
_
+
dot
>
dab
Fortunately there are no scroll bar in the code...
_ Returns an empty list.
1 Append 1.
- Assume x<y, given (x, y) return (0, y-x).
> - A Get the first element of a list (return 0 for empty list).
r Reverse a list of 2 elements.
i Incremential: Given (x, y) return (x, y) if x<y else (y, y).
f Main function.
Writing Dodos code is similar to Haskell that all functions are (effectively) pure.
Bonus Haskell code (ungolfed) which this solution bases on.
Using the same approach as others
qX^k
Try it at MATL Online
Explanation
Implicitly grab input
q Subtract 1
X^ Compute the square root
k Round down
Implicitly display the result
I1-0.5^_P
This is just an implementation of the formula \$\left\lfloor{\sqrt{n-1}}\right\rfloor\$:
I - Push the user input onto the stack
1 - Push 1 onto the stack
- - Pop two numbers a and b off the stack and push the result of a-b
0.5 - Push 0.5 onto the stack
^ - Pop two numbers a and b off the stack and push the result of a^b
_ - Pop the number on the top of stack, floor it and push the result
P - Print the item on the top of the stack
n->(int)Math.sqrt(n-1)
Lambda using the formula \$\left\lfloor{\sqrt{n-1}}\right\rfloor\$. Trivial implementation. Try it online here.
f(n){n=sqrt(n-1);}
Trivial implementation of the formula \$\left\lfloor{\sqrt{n-1}}\right\rfloor\$. Try it online here.
modulo 1or built-ins likeis_squareare irrelevant here, for example). Thus, I hammer-reopened the challenge. \$\endgroup\$