title: Appending String Lengths

text:
# Question
Title: Appending String Lengths
### Challenge:

Given a string `s` on the characters `a`-`z`, `A`-`Z`, `0`-`9`, append the length of `s` to itself, counting the additional character(s) in the length as part of the total length of `s`.

### Input:

Just a string of arbitrary length (can be empty).

### Output:

The same string, but with its length appended to the end. The characters that represent the length should also be counted as part of the length. In cases where there are multiple valid lengths to append, choose the smallest one possible (see test cases for examples).

### Test Cases:

```
INPUT     -> OUTPUT       // Comment
aaa       -> aaa4
          -> 1            // Empty string
aaaaaaaa  -> aaaaaaaa9    // aaaaaaaa10 would also normally be valid, but violates using the smallest number rule mentioned above
aaaaaaaaa -> aaaaaaaaa11
a1        -> a13          // Input can contain numbers at the end of the string, you do not have to handle the fact that it looks like 13 rather than 3.

Longer test case(s):

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa -> aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa101
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa -> aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa102

```

### Rules:

This is , so shortest code in bytes wins. Standard loopholes are forbidden. Submissions may be an entire program or a function, and you may either print the result to stdout or return it as a variable from a function.

# Answer
# Pyth - 7 bytes

```
+Qfql+Q

```

Try it online here.
> 4 votes

# Answer
## JavaScript (ES6), 32 bytes

```
f=(s,n=0)=>(s+n)[n]?f(s,n+1):s+n

```

### How it works

```
f = (s, n = 0) =>   // given a string 's' and starting with n = 0:
  (s + n)[n] ?      // if the Nth character of (s + n) exists:
    f(s, n + 1)     //   try again with n + 1
  :                 // else
    s + n           //   return s + n

```

Starting with `N=0`, we test the Nth character (0-based) of the string made of the concatenation of the original input string and the decimal representation of `N`. We increment `N` until this character doesn't exist anymore.

Example:

```
N =  0 : abcdefghi0
         ^
N =  1 : abcdefghi1
          ^
N =  2 : abcdefghi2
           ^
...
N =  8 : abcdefghi8
                 ^
N =  9 : abcdefghi9
                  ^
N = 10 : abcdefghi10
                   ^
N = 11 : abcdefghi11    -> success
                    ^

```

### Test cases

```
f=(s,n=0)=>(s+n)[n]?f(s,n+1):s+n

console.log(f("aaa"));       // -> aaa4
console.log(f(""));          // -> 1
console.log(f("aaaaaaaa"));  // -> aaaaaaaa9
console.log(f("aaaaaaaaa")); // -> aaaaaaaaa11
console.log(f("a1"));        // -> a13
```
> 19 votes

# Answer
# LaTeX, 108/171

```
\newcounter{c}\def\s#1#2]{\stepcounter{c}\def\t{#2}\ifx\empty\t\arabic{c}\else#1\s#2]\fi}\def\q[#1]{\s#10]}

```

`\q[] //1`
> 12 votes

# Answer
## JavaScript (ES6), 37 bytes

```
f=(s,t=s,u=s+t.length)=>t==u?t:f(s,u)
```

```
<input oninput=o.textContent=f(this.value)><pre id=o>
```
> 5 votes

# Answer
## Lua 5.2, 32 Bytes

```
a=arg[1]print(a..#a+#(''..#a+1))

```

Where the variable *a* is the input string.
> 5 votes

# Answer
# C, ~~67~~ ~~65~~ 61 bytes

```
x;f(*v){printf("%d",(int)log10(x=-~printf(v))*-~(x%10>8)+x);}

```

Wandbox
> 5 votes

# Answer
# Mathematica, 57 bytes

```
#<>ToString[(a=Length@#)+(i=IntegerLength)[a+i@a]~Max~1]&

```

Unnamed function taking an array of characters as input and returning a string. Uses the fact that if `a` is the length of the input, then the number to append to the input is `a` plus the number of digits in (`a` \+ the length of `a`), rather than just `a` plus the number of digits of `a`. Unfortunately it wouldn't give the right answer for the empty-string input without the `~Max~1` special case.
> 4 votes

# Answer
## Pyke, 8 bytes (old version)

```
.f+liq)+

```

Explanation:

```
.f    )  -  first where (i++)
  +      -    input + i
   l     -    len(^)
    iq   -   ^ == i
       + - input + ^

```

Try it here! (New version, 9 bytes)
> 3 votes

# Answer
# Python 2, ~~54~~ ~~48~~ 46 bytes

Simple solution. Recursion ended up being shorter.

```
f=lambda s,n=0:f(s,n+1)if(s+`n`)[n:]else s+`n`

```

**Try it online**
> 3 votes

# Answer
## Haskell, 46 bytes

```
f s=[l|i<-[0..],l<-[s++show i],length l==i]!!0

```

Usage example: `f "aaaaaaaa"` -\> `"aaaaaaaa9"`.

Simply try all numbers starting with 0 and take the first that fits.
> 3 votes

# Answer
# Brachylog, 13 bytes

```
l<L$@:?rc.lL,

```

Try it online!

### Explanation

Basically a description of the problem. It will try every value of `L` bigger than the length of the input until it finds one for which, when concatenated to the input, is the length of that concatenation.

```
l<L              length(Input) < L
  L$@            Convert L to a string
     :?rc.       The Output is the concatenation of the Input with L as string
         .lL,    The length of the Output is L itself

```
> 3 votes

# Answer
# Brainfuck, 258 bytes

```
,>+<----------[++++++++++>+[>+<-],----------]<[<]>[.>]>>>++++++++++<<[->+>-[>+>>]>[+[-<+>]>+>>]<<<<<<]>>[-]>>>++++++++++<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]>[-]>>[>++++++[-<++++++++>]<.<<+>+>[-]]<[<[->-<]++++++[->++++++++<]>.[-]]<<++++++[-<++++++++>]<.[-]<<[-<+>]

```

The input must be terminated by a linefeed (LF). Only works for inputs with a length lesser than 256 (including the LF).

Try it online!

## Explanation

```
# read first char and add one to cell #1
# the cell after the input will contain the length
,>+<
# subtract 10 to check for LF
----------
# while the input is not 10 (LF)
[
# restore the input to its original value
++++++++++
# add one to the length
>+
# cut and paste the length to the next cell, then read the input
[>+<-],
# subtract 10 to check for LF
----------
]
# for input abc, the tape here would be: a b c *0* 4
# rewind to the beginning of the input
<[<]>
# print the input string
[.>]>
# convert the length to ascii chars and output them
>>++++++++++<<[->+>-[>+>>]>[+[-<+>]>+>>]<<<<<<]>>[-]>>>++++++++++<[->-[>+>>]>[+[-
<+>]>+>>]<<<<<]>[-]>>[>++++++[-<++++++++>]<.<<+>+>[-]]<[<[->-<]++++++[->++++++++
<]>.[-]]<<++++++[-<++++++++>]<.[-]<<[-<+>]

```

*Note: I used code from this SO answer to convert the length to ascii output; I hope this is acceptable on PPCG. This is my first Codegolf submission, and my second BF program. Feedback is welcomed.*
> 3 votes

# Answer
# Perl 6,  ~~46~~  35 bytes

```
{$_~(.chars,*.chars+.chars...{$^a==$^b})[*-1]}

```

```
{$_~(.chars,*.chars+.chars...*)[2]}

```

Try it

## Expanded:

```
{   # bare block lambda with implicit parameter ｢$_｣

  $_  # the input

  ~   # concatenated with

  (  # sequence generator

    .chars,  # the number of chars in ｢$_｣ (seed the generator)

    *\      # Whatever lambda input (represents previous value)
    .chars  # number of chars in that
    +       # plus
    .chars  # the number of chars in ｢$_｣

    ...     # keep doing that until

    *       # indefinitely

  )[2] # get the value at index 2 of the sequence
}

```
> 3 votes

# Answer
## Python, 39 bytes

```
lambda a:eval('a+str(len('*3+'a))))))')

```

Longer form:

```
lambda a:a+str(len(a+str(len(a+str(len(a))))))

```

Iteratively in Python 2 (41 bytes):

```
x=a=input();exec"x=a+`len(x)`;"*3;print x

```

Starting with `x` as the input string `a`, applies the transformation `x -> a + str(len(x))` three times. I'm still not clear why three applications are needed to always reach the fixed point.
> 3 votes

# Answer
## Retina, 22 bytes

```
\G`
.
x
+r`\d*$
$._
x

```

Try it online!

Ah well, if it wasn't for digits appearing in the input, this would be merely 11 bytes:

```
+r`\d*$
$._

```
> 2 votes

# Answer
# Haskell, ~~61~~ 60 bytes

```
e=length
l%n|s<-show$l+1,n>e s=s|m<-n+1=(l+1)%m
c s=s++e s%2

```

Try it online!

Recursive solution. Usage:

```
Prelude> c "aaaaaaaaa"
"aaaaaaaaa11"

```
> 2 votes

# Answer
# Ruby, 62 58 56 bytes

```
s=gets.chomp;p s+"#{(s+"#{(s+"#{s.size}").size}").size}"

```

Tested in `irb`.

There's probably a better way to do this, but this was the first thing I came up with. Any help in golfing would be appreciated.

**edit:** I realized my use of parentheses was excessive.
> 2 votes

# Answer
# 05AB1E, 11 bytes

```
[¹¾JDg¾Q#¼\

```

Pretty straightforward bruteforce:

```
            Implicit i = 0
[           while true
 ¹¾J        Concatenate input and i -> str
    Dg¾Q#   Break if length(str) == i
         ¼\ Else, i += 1

```

Try it online!
> 2 votes

# Answer
# PHP, 42 bytes

```
while(++$n<strlen($a=$argv[1].$n));echo$a;

```

Run with `-r`. Test at OnlinePHPfunctions.
> 2 votes

# Answer
## bash, 47 bytes

```
 for((n=-1;${#s} != $n;));{ s=$1$[++n];};echo $s

```

Save this as a script, and pass the input string as an argument.

It's a brute force implementation: try each number in turn until you find one which works.
> 2 votes

# Answer
# \>\<\> (Fish) 35 bytes

```
i:1+?!v:o
ln;v9l<  >
*9+>:&)?!^1l&a

```

Takes input onto the stack, checks the length against values 9,99,999... and if the length is larger than add 1 to the stack length.
> 2 votes

# Answer
# Ruby, ~~43~~ 36 bytes

Anonymous function, abusing the `$.` global.

```
->s{$.+=1while(t=s+"#$.").size>$.;t}

```

Call it like this:

```
f = ->s{$.+=1while(t=s+"#$.").size>$.;t}
f[""]          # => "1"
f["a"]         # => "a2"
f["aaaaaaa"]   # => "aaaaaaa8"
f["aaaaaaaa"]  # => "aaaaaaaa9"
f["aaaaaaaaa"] # => "aaaaaaaaa11"

```
> 2 votes

# Answer
# Vyxal, 6 bytes

```
LJL+LJ

```

Try it Online!

Append the length of the string, take the length of that, then append the new length to the original. This does work with digit overflows (9, 99, etc...).
> 2 votes

# Answer
# Pip, 8 bytes

```
L3Ya.#yy

```

Try It Online!

### Explanation

Inspired by Pacmanboss256's Vyxal solution.

```
          ;; y is empty string; a is first command-line argument (implicit)
L3        ;; Loop 3 times:
   a.     ;;  Concatenate a with
     #y   ;;  Length of y
  Y       ;;  Assign the result to y
       y  ;; After the loop, output y

```

Some worked examples:

```
Input a        ""    "aaa"    "aaaaaaaaa"
Original y     ""    ""       ""
After loop 1   "0"   "aaa0"   "aaaaaaaaa0"
After loop 2   "1"   "aaa4"   "aaaaaaaaa10"
After loop 3   "1"   "aaa4"   "aaaaaaaaa11"

```
> 2 votes

# Answer
# K (ngn/k), 31 bytes

```
{$[9>t:#x;x,$1+t;x,$#x,($1+t)]}

```

Try it online!

*+22 bytes thanks to Dominic van Essen for pointing out a not-working test case (that should have worked)*
> 2 votes

# Answer
# MATL, 11 bytes

```
`G@Vhtn@>]&

```

Try it online! Or verify all test cases.

```
`      % Do...while
  G    %   Push input
  @    %   Push iteration index (1-based)
  V    %   Convert number to string
  h    %   Concatenate horizontally
  t    %   Duplicate
  n    %   Get length of concatenated string
  @    %   Push iteration index
  >    %   True if length of concatenated string exceeds iteration index
]      % End. Run next iteration if top of stack is true; else exit loop
&      % Specifiy that next function (implicit display) takes only one input
       % Implicitly display top of the stack. This is the concatenated string
       % that had a length equal to the iteration index

```
> 1 votes

# Answer
# C#, 77 bytes

```
n=>{int a=n.Length;int c=(a+1).ToString().Length-1;return(n+(n.Length+1+c));}

```
> 1 votes

# Answer
# Ruby, 51 bytes (program)

# Ruby, 49 bytes (function)

Program (last newline is not necessary and thus unscored):

```
x=gets.strip
i=0
i+=1 until(y=x+i.to_s).size==i
p y

```

Function (last newline is scored):

```
def f x
i=0
i+=1 until(y=x+i.to_s).size==i
y
end

```
> 1 votes

# Answer
## R, 49 bytes

```
cat(a<-scan(,""),(t<-nchar(a))+nchar(t+1),sep='')

```

Pretty straightforward solution.
> 1 votes

# Answer
# Factor, 55 bytes

It's a walk in the park! I came up with this in my head as soon as I read the question.

```
[ dup length dup log10 ⌈ + >integer 10 >base append ]

```
> 1 votes

# Answer
**Clojure, 72 bytes**

```
(defn f([s](f s 1))([s n](if(=(count(str s n))n)(str s n)(f s(inc n)))))

```
> 1 votes

# Answer
# Wolfram, 56

```
#<>ToString@Nest[l+IntegerLength@#&,l=StringLength@#,2]&

```

Given `l = StringLength[x]` it appends `l + IntegerLength[l + IntegerLength[l]]` to `x`.
> 1 votes

# Answer
# Labyrinth, 48 45 41 bytes

```
)"   10/{:@!
.,;: _ { _ ;
   })"}) 10-9!@

```

Try it online!

Saved 4 bytes thanked to @Martin Ender
> 1 votes

# Answer
# ForceLang, 83 bytes

```
set s io.readln()
label 1
set n 1+n
set t s+n
if t.len=n
 io.write t
 exit()
goto 1

```
> 1 votes

# Answer
## awk, 37 bytes

```
{FS="";r=$0;$0=r NF;$0=r NF;$0=r NF}1

```

That will work in any awk that splits lines into characters when FS is NULL e.g. GNU awk and most others. WIth other awks you'd have to use the `length()` function instead of `NF` to calculate the number of characters in the record, e.g. `awk '{r=$0;$0=r length;$0=r length;$0=r length}1' file`.

Breakdown:

```
FS=""    # split the record at every character so NF is a count of characters in the record
r=$0     # save the original record
$0=r NF  # append the original length to the original record and cause awk to recalculate NF
$0=r NF  # append the new length to the original record and cause awk to recalculate NF again
$0=r NF  # append the final length to the original record for output
1        # a true condition invoking awks default action of printing the current record

```

Example:

```
$ awk '{FS="";r=$0;$0=r NF;$0=r NF;$0=r NF}1' file
aaa4
1
aaaaaaaa9
aaaaaaaaa11
a13
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa101
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa102

```
> 1 votes

# Answer
# Jelly, 12 bytes

Many thanks to Dennis for his help in writing this answer. Golfing suggestions welcome. Try it online!

```
D;³L=
LÇ1#;@

```

**Explanation**

```
LÇ1#;@  Main link. Argument: s
          Runs the helper link until a suitable x is found.
L       Yields the length of s.
 Ç1#    Calls the helper link until one match is found.
    ;@  Appends the matching x to s.

D;³L=  Helper link. Argument: x
         Appends x to s and checks if its length is equal to x.
D      Convert x from integer to decimal.
 ;³    Append to our original string.
   L=  Check if the length of this new string is equal to x.

```
> 1 votes

# Answer
# Perl, 31 bytes

Just going through all the numbers until one fits:

```
perl -lpe '1while++$n<length$_.$n;$_.=$n'

```
> 1 votes

# Answer
# Factor, 47 bytes

```
[ dup length dup log10 ⌈ + 1 /i >dec append ]

```

Attempt This Online!

small improvement to the previous answer.

`>dec` is polyfilled since it is a newer addition.
> 1 votes

# Answer
# Ly, ~~26~~ 14 bytes

```
iysp&ol`Syl+u;

```

Try it online!

This turned out to be trickier than I expected... Since strings of length 9, 99, etc... need an extra digit when the length it appended.

So the code computes the number of digits in the length of a string composed of the original string plus the length of that string. Then that length is added to the length of the original string to get the final length, which is appended to the original.

```
iysp&ol`Syl+u; -
i              - read in the input string
 ysp           - get the length, stash it, delete from stack
    &o         - print the string
      l`       - load the string length and increment
        Sy     - split to digit, count them
          l+   - load the string length and add to digit count
            u; - print as number and exit (to avoid printing stack)

```

# jq, 40 bytes

```
.+"\(length+(length+1|tostring|length))"

```

Try it online!

It's the same algorithm, just in `jq` for comparison. I couldn't find a shorter way to do it in `jq` even though using "length" three times seems like it should be golf-able...
> 1 votes

# Answer
# Thunno 2, 4 bytes

```
3{l+

```

Try it online!

#### Explanation

```
3{l+  # Implicit input
3{    # Repeat three times:
  l   #  Take the length of the top
      #  of stack (initially input)
   +  #  And append this to the input
      # (Three times is enough to handle
      #  digit overflows like 9, 99, etc.)
      # Implicit output

```
> 1 votes

# Answer
# C, 75 bytes

Yes, there's another C answer but this (the same method as my Factor answer) is shorter:

```
i,z;f(char*s){i=strlen(s);z=1+log10(i);sprintf(realloc(s,i+z)+i,"%d",i+z);}

```

Ungolfed:

```
i, z;

g (char* s){
  i = strlen(s);
  z = 1 + log10(i);
  s = realloc(s, i + z);
  sprintf(s + i, "%d", i + z);
}

```

`ceil(log10(n)` is the number of digits in base 10 `n`, but `1+` is shorter than `ceil()`.

Then, resize the string so we don't get a segfault, and format the number after the string part.
> 0 votes

# Answer
**Under review**

**Powershell V2.0, 64 bytes**

```
$s=$args[0]
$s+[string]($s.length+([string]($s.length)).length)

```

**Example**

```
PS C:\Users\***\Downloads\golf> .\str-length.ps1 'This is my strin3333333333333333333333333333333333333333333333333333
33333333333333333333333333333333333333333g'
This is my strin333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333g113

```
> 0 votes

# Answer
# Scala, 75 bytes

```
def a(b:String,c:Int=0):String=if((b+c).length>c)a(b,c+1)else b+c

```
> 0 votes

# Answer
## awk, 27 bytes

```
$0=$0length($0length($0NF))

```

Test it:

```
$ awk -F '' '$0=$0length($0length($0NF))' file
7aaaaaa8
8aaaaaaa9
9aaaaaaaa11
97aaaaa10aaaaaaaa10aaaaaaaa10aaaaaaaa10aaaaaaaa10aaaaaaaa10aaaaaaaa10aaaaaaaa10aaaaaaaa10aaaaaaaa99
98aaaaaa10aaaaaaaa10aaaaaaaa10aaaaaaaa10aaaaaaaa10aaaaaaaa10aaaaaaaa10aaaaaaaa10aaaaaaaa10aaaaaaaa101

```
> 0 votes

# Answer
# C# / CS Script ~~99~~ ~~87~~ 79 bytes

Saved a few bytes switching to a lambda. And a few more moving the try/catch out of the for loop.

```
F=a=>{int i=0,l;try{for(;;)l=(a+(a+a.Length).Length)[++i];}catch{}return a+i;};

```

Try it here

Expanded:

```
F => a
{
    // 'i' is for traversing the string
    // 'l' is just a placeholder
    int i = 0, l;

    // wrap the loop in a try/catch
    try
    {
        // loop forever
        for (;;)
            // assign to 'l' the char at position ++i
            // throws an IndexOutOfRangeException when it falls off the end
            l = (a + (a + a.Length).Length)[++i];
    }
    // empty catch block
    catch {}

    // returns a string concat of the input a and index i
    return a + i;
}

```
> 0 votes

# Answer
# Java 7, 67 bytes

```
String y(String y){int i=0;for(;(y+i).length()!=i;i++);return y+i;}

```

Try it online!
> 0 votes

# Answer
# 05AB1E, 4 bytes

```
3Fg«

```

Try it online or verify all test cases.

**Explanation:**

```
3F    # Loop 3 times:
  g   #  Pop the current string, and push its length
      #  (which will use the implicit input-string in the first iteration)
   «  #  Append this length to the (implicit) input-string
      # (after which the result is output implicitly)

```
> 0 votes

# Answer
# JavaScript, 29 bytes

```
s=>(g=x=>s+x.length)(g(g(s)))

```

Try it online!
> 0 votes

---
Tags: code-golf, string
---


title: Calculate max depth of JSON data

text:
# Question
Title: Calculate max depth of JSON data
## Challenge

Given some JSON data, calculate the maximum depth reached. (Both arrays and dictionaries increase the depth)

## Input/Output

The program is expected to read a JSON string from stdin and as soon as the program receives a \n start calculating the max depth, printing it to stdout and terminating the program when done.

If invalid JSON is provided, the output is undefined (the program can return anything).

## Test cases

`[]` -\> 1

`[1, 2, 3, 4, 5]` -\> 1

`[ [ 123], []]` -\> 2

`[{"a": []}, ["abc"]]` -\> 3

`{"a": 321}` -\> 1

`{"a": []}` -\> 2

`"hello"` -\> 0

`["abc[]bca"]` -\> 1

### Evaluating machine/platform

Platform: aarch64 Linux (arch Linux arm, cpu: apple M1)

### Results

| Contestant | Language | Result |
| --- | --- | --- |
| AnttiP | C | 43 ± 11 ms |
| Philx0 | C | 67 ± 7 ms |
| 138 Aspen | rust | 112 ± 7 ms |
| Arnauld | node.js | 276 ± 18 ms |
| tsh | node.js | 370 ± 16 ms |
| noodle man | node.js | 567 ± 143 ms |

### edit

Edit: changed challenge to not require outputting 0 in the case of invalid JSON

# Answer
# C, based on Philx0's answer

I tried to remove a few branches. Instead of storing state in a variable I store it... in the state. Namely, there are two loops depending on if we are parsing a string or not. The rest of the comparisons should be branchless when compiled with -O3.

Edit: Slightly improved version. It's possible to also remove most checks for "\n" by keeping track of whether the current depth is positive, tough I'm not sure how much it would improve performance.

```
#include <unistd.h>
#include <stdio.h>

#define BUFSIZE 4096
#define unlikely(x) __builtin_expect((x),0)

int main(void) {
    int depth = 0;
    int maxdepth = 0;

    char buf[BUFSIZE];

    ssize_t cnt;
    ssize_t i;
    ssize_t skip = 0;

    int str = 0;

    while ((cnt = read(0,buf,BUFSIZE))) {
        i = skip;
        if (!str) {
            for (; i < cnt; i++) {
                if (buf[i] == '"') goto instring;
                if (unlikely(buf[i] == '\n')) goto print;
                if (depth > maxdepth) maxdepth = depth;
                depth+= buf[i] == '{' || buf[i] == '[';
                depth-= buf[i] == '}' || buf[i] == ']';
                outstring:;
            }
            str = 0;
        } else {
            for (; i < cnt; i++) {
                if (buf[i] == '"') goto outstring;
                if (unlikely(buf[i] == '\\')) i+=1;
                instring:;
            }
            str = 1;
        }
        skip = i - cnt;
    }

    print:

    printf("%d\n", maxdepth);
    return 0;
}

```
> 7 votes

# Answer
# Rust

use `serde_json` crate. I don't know how fast it is.

upd 2023-06-19 \\$\quad \\$ In light of the comment of @lights0123, you can use `cargo build --release` instead of `cargo build`. It would likely be significantly faster in release mode.

### `src/main.rs`

```
use std::io::{self, Read, BufRead};
use serde_json::Value;
use std::process;

fn main() -> io::Result<()> {
    let stdin = io::stdin();
    for line in stdin.lock().lines() {
        let line = line?;
        let json_value: Value = serde_json::from_str(&line).unwrap_or(Value::Null);
        println!("{}", search(&json_value));
    }
    process::exit(0);
}

fn search(node: &Value) -> u32 {
    match node {
        Value::Object(map) => {
            let max_depth = map.values().map(|v| search(v)).max();
            match max_depth {
                Some(max) => 1 + max,
                None => 1,
            }
        },
        Value::Array(arr) => {
            let max_depth = arr.iter().map(|v| search(v)).max();
            match max_depth {
                Some(max) => 1 + max,
                None => 1,
            }
        },
        _ => 0,
    }
}

```

### `Cargo.toml`

```
[package]
name = "rust_hello"
version = "0.1.0"
edition = "2021"

# See more keys and their definitions at https:doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]
serde_json = "1.0"

```

### Build and running

```
# win10 environment

$ cargo build --release
$ target\release\rust_hello.exe
[{"a": []}, ["abc"]]
3
hello
0
{"a": []}
2
{"a": 321}
1
[ [ 123],   []]
2
[1, 2, 3, 4, 5]
1
[]
1
[[]
0

```
> 6 votes

# Answer
## A rewrite of noodle man’s solution in C

<pre><code>#include <stdio.h>

#define BUFSIZE 1024

int main(void) {
    int str = 0;
    int escape = 0; //backslash

    int depth = 0;
    int maxdepth = 0;

    char buf[BUFSIZE];

    while (fgets(buf, BUFSIZE, stdin)) {
        for (size_t i = 0; buf[i]; i++) {
            if (buf[i] == '\n') goto print;

            if (escape) {
                escape = 0;
                continue;
            }

            if (buf[i] == '\\') {
                escape = 1;
            } else if (buf[i] == '\"') {
                str = !str;
            } else if (!str) {
                if (buf[i] == '{' || buf[i] == '[') {
                    depth++;
                    if (depth > maxdepth) maxdepth = depth;
                } else if (buf[i] == '}' || buf[i] == ']') depth--;
            }
        }
    }

    print:;

    printf("%d\n", maxdepth);
}```
</code></pre>
> 5 votes

# Answer
# JavaScript (Node.js)

I honestly have no idea how fast it is.

*EDIT: Since the challenge is no longer asking for JSON validation, using `JSON.parse()` may now seem a bit overkill. But this built-in is apparently reasonably well optimized and still faster than a simpler 100% JS parser.*

```
const readline = require('readline');

// set up the readline interface
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
  terminal: false
});

// the following callback is invoked when a line is read
rl.on('line', str => {
  let json;

  try {
    // attempt to parse the line as JSON
    json = JSON.parse(str);
  }
  catch(e) {
    // if it fails, force the result to null
    json = null;
  }

  // recursive function computing the max. depth
  function search(node) {
    // look for anything whose typeof is 'object' but is not null
    if(typeof node == 'object' && node !== null) {
      // for an array, use the node itself
      // for a genuine object, use the list of its values
      let list = Array.isArray(node) ? node : Object.values(node);
      // return 1 right away if the list is empty
      // otherwise, do a recursive call for each element in the list
      // and return the highest result + 1
      return list.length ? 1 + Math.max(...list.map(search)) : 1;
    }
    // return 0 for non-iterable elements
    return 0;
  }

  // initial call to search
  console.log(search(json));

  // we're supposed to process only one line, so force exit
  process.exit();
});

```

Try it online!
> 4 votes

# Answer
# JavaScript (Node.js), 621 bytes

```
require("readline").createInterface({ input: process.stdin, output: process.stdout, terminal: false }).on("line", file => {
  let inString = false;
  let prevBackslash = false;
  let depth = 0;
  let maxDepth = 0;
  for (const char of file) {
    if (prevBackslash) {
      prevBackslash = false;
      continue;
    }
    if (char === "\\") prevBackslash = true;
    if (char === '"' && !prevBackslash) inString = !inString
    if (inString) continue;

    if ("{[".includes(char)) {
      if (++depth > maxDepth) maxDepth++;
    }
    if ("]}".includes(char)) depth--;
  }
  console.log(maxDepth);
  process.exit();
});

```

Attempt This Online!

This should be faster since it doesn't check if the JSON is valid, which is no longer required. If checking the JSON was valid was required, a solution like this manually verifying validity while checking the depth might still be faster, but I don't feel like writing a JSON parser.

All this does is loop over each character of the input, ignoring strings, incrementing a depth counter whenever it encounters a `{` or `[`, decrementing the counter when it encounters a `}` or `]`, and keeping track of the maximum depth.
> 3 votes

# Answer
# JavaScript (Node.js)

```
const isArray = Array.isArray, objectValues = Object.values, max = Math.max;
require("readline").createInterface({ input: process.stdin, output: process.stdout, terminal: false }).on("line", str => {
  const depth = JSON.parse(str, (key, value) => {
    if (value === null || typeof value !== 'object') return 0;
    const arr = isArray(value) ? value : objectValues(value);
    const depth = -~max(...arr);
    return depth;
  });
  console.log(depth);
  process.exit();
});

```

Try it online!

The readline part is based on other answers.

Just in case if you are interesting, it can be golfed into 70 bytes, however, this question is not tagged as code-golf.

```
s=>JSON.parse(s,(_,v)=>Object(v)===v&&-~Math.max(...Object.values(v)))

```

Try it online!
> 2 votes

# Answer
# Retina 0.8.2, 35 bytes

```
"(\\?.)*?"

T`[]`{}
[^{}]

+`}{

..

```

Try it online! Link includes test suite. Probably not going to win any awards for speed. Explanation:

```
"(\\?.)*?"

```

Delete all string literals.

```
T`[]`{}

```

Change square brackets into braces.

```
[^{}]

```

Delete everything other than braces.

```
+`}{

```

Merge adjacent containers at the same depth.

```
..

```

Count the maximum depth.
> 1 votes

# Answer
# GNU AWK, ~11ms

```
BEGIN {
	FPAT = "(\"([^\"])*\")+|."
	m = 0
}

{
	printf "%s -> ", $0
	gsub(/'\\'\"[^'\\\"']*'\\'\"/, "", $0)
	gsub(/\\"/, "\"\"", $0)
	for (i = 1; i <= NF; i++) {
		if ($i == "[" || $i == "{") {
			a++
			m = (a > m ? a : m)
		} else if ($i == "]" || $i == "}") {
			a--
		}
	}
	print m
	m = 0
}

Result:
123 -> 0
[] -> 1
[1, 2, 3, 4, 5] -> 1
[ [ 123],   []] -> 2
[{"a": []}, ["abc"]] -> 3
{"a": 321} -> 1
{"a": []} -> 2
"hello" -> 0
["abc[]bca"] -> 1
["\",[],\""] -> 1
["",[],""] -> 2
["\"",[],""] -> 2
["\"",[],"\""] -> 2
"[\\" -> 0

```

Try it online!
> 1 votes

# Answer
# Go, 715 bytes

```
package main

import (
	"bufio"
	"fmt"
	"os"
)

func calcDepth(data string) int {
	depth, maxDepth := 0, 0
	inString := false
	escaped := false
	for _, r := range data {
		switch r {
		case '\\':
			escaped = !escaped
		case '"':
			if !escaped {
				inString = !inString
			}
			escaped = false
		case '{', '[':
			if !inString {
				depth++
				if depth > maxDepth {
					maxDepth = depth
				}
			}
			escaped = false
		case '}', ']':
			if !inString && depth > 0 {
				depth--
			}
			escaped = false
		default:
			escaped = false
		}
	}
	return maxDepth
}

func main() {
	var data string

	scanner := bufio.NewScanner(os.Stdin)

	if scanner.Scan() {
		data = scanner.Text()
	}

	fmt.Println(calcDepth(data))
}

```

Try it online!
> 1 votes

# Answer
# Racket

```
#lang typed/racket/base

(require typed/json)

#|

Calculate the maximum depth of a JSON object read from input

Algorithm:

1. Read user input and parse JSON.
2. If input has no data, return 0.
2. Begin `max-depth` with the parsed JSON data and depth of 0.
   a. If the JSON input is a list, loop over each element of the list and pass
      the element as an input for `max-depth` and increment the depth. Repeat step 2.
   b. If the JSON input is a hash table, use each values of the table as the input list
      for step 2.a.
   c. If the JSON input is a number, string, boolean, or null, return the depth.
3. Print the maximum depth.

|#

(: max-depth (-> JSExpr Real Real))
(define (max-depth input depth)
  (let ([depth+1 (+ depth 1)])
    (cond [(list? input)
           (apply max
                  (cons depth+1
                        (map (λ ([elem : JSExpr]) : Real
                               (max-depth elem depth+1))
                             input)))]
          [(hash? input)
           (apply max
                  (cons depth+1
                        (hash-map input
                                  (λ ([_ : Symbol] [value : JSExpr]) : Real
                                    (max-depth value depth+1)))))]
          [else depth])))

(: main (-> (U JSExpr EOF) Real))
(define (main input)
  (cond [(equal? eof input) 0]
        [else (max-depth input 0)]))

(displayln (main (read-json)))

#| Tests [Remove line to run after input, if all pass, nothing will display.]

(require (only-in typed/rackunit check-equal?))
(check-equal? (main (string->jsexpr "[]")) 1)
(check-equal? (main (string->jsexpr "[1, 2, 3, 4, 5]")) 1)
(check-equal? (main (string->jsexpr "[ [ 123],   []]")) 2)
(check-equal? (main (string->jsexpr "[{\"a\": []}, [\"abc\"]]")) 3)
(check-equal? (main (string->jsexpr "{\"a\": 321}")) 1)
(check-equal? (main (string->jsexpr "{\"a\": []}")) 2)
(check-equal? (main (string->jsexpr "\"hello\"")) 0)
(check-equal? (main (string->jsexpr "[\"abc[]bca\"]")) 1)

Tests [Remove line to run after input, if all pass, nothing will display.] |#

```

## Compilation

Once Racket is installed one your system, simply run:

```
raco exe /path/to/this_file.rkt

```

Best compiled without the tests.

## Explanation

Racket provides a nice built-in package called `json` that parses JSON expressions (`JSExpr`). All lists in the JSON expression are parsed into Racket Lists and all dictionaries are parsed into Hash Tables where the keys are Symbols and the values are other `JSExpr`s. The reason I am using Typed Racket is that it is potentially faster than the dynamically typed language.

## Conclusion

This is my submission for the challenge, I am not that great at optimizing code, so I don't expect peak performance in its runs. I did do a sample test on my machine with a 64kB minified JSON file which ran (according to `time`) at about 700ms. As a note though, my CPU is Intel 2 Duo E8500 and 2GB RAM, so I think it should be faster on other machines :)

Have an amazing weekend!
> 0 votes

---
Tags: fastest-code, json
---


title: Count sums of two squares

text:
# Question
Title: Count sums of two squares
Given a non-negative number `n`, output the number of ways to express `n` as the sum of two squares of integers `n == a^2 + b^2` (OEIS A004018). Note that `a` and `b` can be positive, negative, or zero, and their order matters. Fewest bytes wins.

For example, `n=25` gives `12` because `25` can be expressed as

```
(5)^2  + (0)^2
(4)^2  + (3)^2
(3)^2  + (4)^2
(0)^2  + (5)^2
(-3)^2 + (4)^2
(-4)^2 + (3)^2
(-5)^2 + (0)^2
(-4)^2 + (-3)^2
(-3)^2 + (-4)^2
(0)^2  + (-5)^2
(3)^2  + (-4)^2
(4)^2  + (-3)^2

```

Here are the values up to `n=25`. Be careful that your code works for `n=0`.

```
0 1
1 4
2 4
3 0
4 4
5 8
6 0
7 0
8 4
9 4
10 8
11 0
12 0
13 8
14 0
15 0
16 4
17 8
18 4
19 0
20 8
21 0
22 0
23 0
24 0
25 12

```

Here are the values up to `n=100` as a list.

```
[1, 4, 4, 0, 4, 8, 0, 0, 4, 4, 8, 0, 0, 8, 0, 0, 4, 8, 4, 0, 8, 0, 0, 0, 0, 12, 8, 0, 0, 8, 0, 0, 4, 0, 8, 0, 4, 8, 0, 0, 8, 8, 0, 0, 0, 8, 0, 0, 0, 4, 12, 0, 8, 8, 0, 0, 0, 0, 8, 0, 0, 8, 0, 0, 4, 16, 0, 0, 8, 0, 0, 0, 4, 8, 8, 0, 0, 0, 0, 0, 8, 4, 8, 0, 0, 16, 0, 0, 0, 8, 8, 0, 0, 0, 0, 0, 0, 8, 4, 0, 12]

```

Fun facts: The sequence contains terms that are arbitrarily high, and the limit of its running average is π.

**Leaderboard:**

```
    var QUESTION_ID=64812,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/64812/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

```
    body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
    <script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
```

# Answer
## Python (59 57 56 bytes)

```
lambda n:0**n+sum((-(n%(x-~x)<1))**x*4for x in range(n))

```

Online demo

As with my CJam answer, this uses Möbius inversion and runs in pseudoquasilinear time.

Thanks to Sp3000 for 2 bytes' savings, and feersum for 1.
> 20 votes

# Answer
# Python 2, 44 bytes

```
f=lambda n,x=1:+(x>n)or(n%x<1)-f(n,x+2)/4<<2

```

This is almost the same as xsot's solution (which is based on Peter Taylor's solution), but saves 8 bytes by simplifying the way signs are handled.

Note that for a full program, we can save 2 bytes in the function without incurring a cost outside the function:

```
f=lambda n,x=1:x>n or(n%x<1)-f(n,x+2)/4<<2
print+f(input())

```

Two additional bytes for a full program this way:

```
n=input()
f=lambda x:x>n or(n%x<1)-f(x+2)/4<<2
print+f(1)

```

For `n > 0` there is a very legible 40-byte solution:

```
f=lambda n,x=1:n/x and(n%x<1)*4-f(n,x+2)

```
> 16 votes

# Answer
# Mathematica, 13 bytes

If built-ins are allowed, this is how to do it in Mathematica.

```
2~SquaresR~#&

```

---

For 0 \< = n \<= 100

```
2~SquaresR~# & /@ Range[0, 100]

```

> {1, 4, 4, 0, 4, 8, 0, 0, 4, 4, 8, 0, 0, 8, 0, 0, 4, 8, 4, 0, 8, 0, 0, 0, 0, 12, 8, 0, 0, 8, 0, 0, 4, 0, 8, 0, 4, 8, 0, 0, 8, 8, 0, 0, 0, 8, 0, 0, 0, 4, 12, 0, 8, 8, 0, 0, 0, 0, 8, 0, 0, 8, 0, 0, 4, 16, 0, 0, 8, 0, 0, 0, 4, 8, 8, 0, 0, 0, 0, 0, 8, 4, 8, 0, 0, 16, 0, 0, 0, 8, 8, 0, 0, 0, 0, 0, 0, 8, 4, 0, 12}
> 15 votes

# Answer
## J, 16 bytes

```
+/@,@:=+&*:/~@i:

```

This is a monadic verb (in other words, a unary function). Try it online or see it pass all test cases.

## Explanation

```
+/@,@:=+&*:/~@i:  Denote input by n
              i:  The array of integers from -n to n
           /~@    Take outer product wrt the following function:
       +           the sum of
        &*:        squares of both inputs
                  This results in a 2D array of a^2+b^2 for all a, b between -n and n
      =           Replace by 1 those entries that are equal to n, and others by 0
   ,@:            Flatten the binary matrix
+/@               Take its sum

```
> 12 votes

# Answer
# Pyth, 13 bytes

```
/sM^^R2}_QQ2Q

```

Test suite

```
/sM^^R2}_QQ2Q
                 Q = eval(input())
       }_QQ      Inclusive range from -Q to Q (all possible a and b)
    ^R2          Map to their squares
   ^       2     Form all pairs
 sM              Sum pairs
/           Q    Count occurances of Q

```
> 12 votes

# Answer
# Python 2, ~~69~~ ~~55~~ ~~53~~ 52 bytes

```
f=lambda n,x=1:+(x>n)or(2-x%4)*(n%x<1)+f(n,x+2)/4<<2

```

This is a recursive function based off Peter Taylor's excellent solution.
> 11 votes

# Answer
# Julia, 40 bytes

```
n->n>0?4sum(i->(n-i^2)^.5%1==0,1:n^.5):1

```

Ungolfed:

```
function f(n)
  if n==0
    return 1           # Handle special case of n=0
  else
    m=0                # Start the counter at zero
    for i=1:sqrt(n)    # Loop over the values (i) whose squares are
                       # less than n (except zero)
      k=sqrt(n-i^2)    # Find k such that n=k^2+i^2
      if k==floor(k)   # if k is an integer, we've found a pair
        m+=4           # Add one for each of k^2+i^2, (-k)^2+(-i)^2, and the other two
      end
    end
    return m           # Return the resulting count
  end
end

```

Note that the loop doesn't include `i==0`, because when `n` is a square, it's already included by `i=sqrt(n)`, and there are only four, not eight, for that form (`0^2+k^2, 0^2+(-k)^2, k^2+0^2, (-k)^2+0^2`).
> 8 votes

# Answer
# CJam, ~~25~~ 23 bytes

```
Zri:R#Ym*{Rf-Yf#:+R=},,

```

This is a theoretical solution that requires **O(9n)** time and memory for input **n**.

At the cost of one extra byte – for a total of **24 bytes** – we can reduce the complexity to **O(n2)**:

```
ri:R)Y*Ym*{Rf-Yf#:+R=},,

```

Try it online!

### How it works

Either

```
Z                  Push 3.
 ri:R              Read an integer from STDIN and save it in R.
     #             Compute 3**R.

```

or

```
ri:R               Read an integer from STDIN and save it in R.
    )Y*            Add 1 and multiply by 2.

```

Then

```
Ym*                Take the second Cartesian power, i.e., compute all pairs.
   {          },   Filter the pairs:
    Rf-              Subtract R from each.
       Yf#           Square the differences.
          :+         Add the squares.
            R=       Compare with R.
                   If = pushed 1, keep the pair.
                ,  Count the kept pairs.

```
> 7 votes

# Answer
## CJam (25 24 22 21 bytes)

```
{:X!X{X\2*)%!4*\-}/z}

```

Online demo

This runs in pseudoquasilinear time\* and uses the statement from the OEIS that

> Moebius transform is period 4 sequence \[ 4, 0, -4, 0, ...\]. - Michael Somos, Sep 17 2007

The input `0` is obviously a special case (Möbius tranforms and annihilators don't go well together), but ended up only costing one char.

* Pseudo- because it's quasilinear in the value of the input, not the size of the input; quasi because it does `Theta(n)` operations on integers of size on the order of `n`; a `b`-bit mod operation should take `b lg b` time, so overall this takes `Theta(n lg n lg lg n)` time.
> 7 votes

# Answer
# Japt, ~~42~~ ~~37~~ 33 bytes

**Japt** is a shortened version of **Ja**vaScri**pt**. Interpreter

```
V=Un oU+1;Vr@X+(Vf_p2 +Y*Y¥U)l ,0

```

### How it works

```
           // Implicit: U = input number
V=Un oU+1  // Set variable V to range(-U, U+1). Ends up like [-U,-U+1,...,U-1,U]
Vr@    ,0  // Reduce each item Y in V with this function, starting at 0:
X+(     l  //  Return the previous value X + the length of:
Vf_p2      //   V filtered by items Z where Z*Z
+Y*Y==U)   //    + Y*Y equals U.
           // This ends up as the combined length of all fitting pairs of squares.
           // Implicit: return last expression

```

Perhaps there's a better technique; suggestions are welcome.
> 6 votes

# Answer
## Haskell, 42 bytes

```
f n|q<-[-n..n]=sum[1|a<-q,b<-q,a*a+b*b==n]

```

Usage exapmle:

```
*Main> map f [0..25]
[1,4,4,0,4,8,0,0,4,4,8,0,0,8,0,0,4,8,4,0,8,0,0,0,0,12]
*Main>

```
> 6 votes

# Answer
## Python 3, ~~68~~ ~~61~~ 60 bytes

```
lambda n:0**n+4*sum(i**.5%1+(n-i)**.5%1==0for i in range(n))

```

Using two nested list comprehensions is too expensive. Instead, this checks if both coordinates on the circle of radius sqrt(n) are integers.

*Peter Taylor has beaten this with a Moebius-inversion based approach.*
> 6 votes

# Answer
# Julia, ~~89~~ ~~79~~ 63 bytes

```
g(x)=cos(π*x^.5)^2÷1
a(n)=(n==0)+4sum([g(i)g(n-i)for i=1:n])

```

This is a named function `a` which accepts an integer and returns a float. It calls a helper function `g`.

Ungolfed:

```
function g(x::Integer)
    floor(cos(π*sqrt(x))^2)
end

function a(n::Integer)
    (n == 0) + 4*sum([g(i)*g(n-i) for i=1:n])
end

```

The approach here uses a simplification of Wesley Ivan Hurt's formula listed on OEIS. The simplification was found by Glen O, the very same person who shaved 26 bytes off of this answer!
> 5 votes

# Answer
# Octave, 28 bytes

```
@(n)nnz((a=(-n:n).^2)'+a==n)

```
> 5 votes

# Answer
# Pyth, ~~16~~ 15 bytes

```
lfqQs^R2T^}_QQ2

```

Try it online in the Pyth Compiler.

### How it works

```
lfqQs^R2T^}_QQ2

          }_QQ   Compute the inclusive range from -Q to Q (input).
         ^    2  Take the second Cartesian power, i.e., compute all pairs.
 f               Filter; for each T in the list of pairs:
     ^R2T          Compute the squares of T's elements.
    s              Add the squares.
  qQ               Compare the sum with Q.
                 If q returned True, keep T.
l                Count the kept pairs.

```
> 4 votes

# Answer
## TI-BASIC, 23 bytes

```
sum(seq(Σ(X²+Y²=Ans,X,-Ans,Ans),Y,-Ans,Ans

```

Pretty straightforward. `Σ(` is summation.

Strangely, `sum(seq(sum(seq(` throws an `ERR:ILLEGAL NEST`, and so does `Σ(Σ(`, but `sum(seq(Σ(` is fine. I chose to put the `Σ(` on the inside to save a close-paren.
> 4 votes

# Answer
# JavaScript (ES6), ~~66~~ 60 bytes

```
n=>eval("for(r=0,a=~n;a++<n;)for(b=~n;b++<n;)r+=a*a+b*b==n")

```

6 bytes saved thanks to @edc65!

## Explanation

```
n=>eval(`              // use eval to allow for loops in an unparenthesised arrow function
  for(r=0,             // r = number of pairs
    a=~n;a++<n;        // a = first number to square
  )
      for(b=~n;b++<n;) // b = second number to square
        r+=a*a+b*b==n  // add one to the result if a^2 + b^2 == n
                       // implicit: return r
`)

```

## Test

```
n = <input type="number" oninput='result.innerHTML=(

n=>eval("for(r=0,a=~n;a++<n;)for(b=~n;b++<n;)r+=a*a+b*b==n")

)(+this.value)' /><pre id="result"></pre>
```
> 4 votes

# Answer
# Python 3, ~~93~~ ~~62~~ 69 bytes

Itertools wasn't working so I used two ranges again, but moved the range out to save bytes.

**Edit:** Previous code didn't actually work, since I defined range over n before I defined n.

```
lambda n:sum(i*i+j*j==n for i in range(-n,n+1)for j in range(-n,n+1))

```
> 4 votes

# Answer
## APL, ~~23~~ ~~20~~ 19 bytes

```
{+/⍵=∊∘.+⍨×⍨0,,⍨⍳⍵}

```

Explanation:

```
{+/⍵=∊∘.+⍨×⍨0,,⍨⍳⍵}        Monadic function:
                 ⍳⍵          1 2 3 ... ⍵
               ,⍨            Duplicate
             0,              Concatenate to 0
          ×⍨                 Square everything
      ∘.+⍨                   Make an addition table
     ∊                       Flatten
   ⍵=                        1s where equal to the input
 +/                          Sum up the 1s

```

Other than the fact that APL doesn't have J's `i:` (numbers from -n to n) function, this works pretty much like the J answer.

We can't use a train because getting the `-\⍳2×⍵` to not parse as `(-\) ⍳ (2×⍵)` would cost three bytes; similarly with other pair of atops. All those parentheses make the regular function shorter.

Try it here. The output of `1` means all values match.
> 2 votes

# Answer
# PARI/GP, ~~34~~ 28 bytes

Using generating functions:

Saved 6 bytes thanks to Mitch Schwartz.

```
n->sum(i=-n,n,x^i^2)^2\x^n%x

```

---

Using built-ins, 33 bytes (saved 1 byte thanks to Mitch Schwartz.):

```
n->if(n,2*qfrep(matid(2),n)[n],1)

```

> qfrep(q,B,{flag=0}): vector of (half) the number of vectors of norms from 1 to B for the integral and definite quadratic form q. If flag is 1, count vectors of even norm from 1 to 2B.

---
> 2 votes

# Answer
# Matlab 41 bytes

Even smaller as the previous answers

```
@(n)nnz(~mod(sqrt(n-(1:n^.5).^2),1))*4+~n

```

Essentially Agawa001's answer with power and sqrt replaced
> 2 votes

# Answer
# Candy, ~~17~~ 14 bytes

Input pushed onto stack initially

~~`~TbAT1C(sWs+Aeh)Z`~~

`~T0C(sWs+Aeh)Z`

```
peekA    # copy arg from stack to register A
range2   # create double sided range on stack, -A, 1-A, ... A-1, A
digit0   # prefix argument to 'cart',
cart     # cartesian product of current stack(0), and other stack(0)
while    # while stack not empty
  sqr    # pop and square and push
  swap   # swap two stack elements
  sqr    # pop and square and push
  add    # pop and pop and add and push
  pushA  # push original argument
  equal  # equality test 0/1
  popAddZ  # Z := Z + pop
endwhile
pushZ    # push Z onto stack, will be output to stdout on termination

```
> 2 votes

# Answer
# CJam, 28

```
qi_mF{3a>},{~)\4%2-&}%4+:*1?

```

Not really short, but efficient. E.g. the result for 15625 is instantly 28. Uses the factorization-based formula from OEIS.
Try it online

**Explanation:**

```
qi       read input and convert to integer
_        make a copy (will be used to handle the 0 case at the end)
mF       factorize into [prime exponent] pairs
{…},     filter the array of pairs
  3a>    with the condition that the pair is greater than [3]
          which means the prime factor must be ⩾3
{…}%     transform each pair as follows:
  ~      dump the prime factor and exponent onto the stack
  )      increment the exponent
  \      swap with the prime
  4%     get the remainder mod 4 (it will be 1 or 3)
  2-     subtract 2 (resulting in -1 or 1)
  &      bitwise AND with the incremented exponent (see below)
4+       append a 4 to the array
:*       multiply all
1?       if the input was 0, use 1, else use the above result

```

Some details about the calculation:

* if the prime is 1 mod 4, the code calculates `(exponent + 1) & -1`, which is `exponent + 1`
* if the prime is 3 mod 4, the code calculates `(exponent + 1) & 1`, which is 0 if the exponent is odd, and 1 if even

All these values multiplied together and multiplied by 4 are exactly the OEIS formula.
> 2 votes

# Answer
# Python 2, 68 bytes

```
def x(n):r=range(-n,n+1);print sum(a*a+b*b==n for a in r for b in r)

```

Defines a function called `x()` that takes a number n.

Try it online. http://ideone.com/aRoxGF
> 2 votes

# Answer
# Pyth, ~~41~~ ~~35~~ ~~33~~ ~~30~~ 27 bytes

Try it online.

**Edit:** Thanks to isaacg, I got `m` and `*F` to work! YES!

```
?Q*F+4m.&tt%ed4hhdr-PQ2 8 1
                                (implicit) Q = input()
?Q                              If Q != 0
      m                           Map to d (exponent, prime) from ...
                  r-PQ2 8         run-length-encoded(PQ with 2's removed)
       .&                           Bitwise and
           %ed4                       d[-1] % 4
         tt                           -2
                hd                  with d[0]
               h                      +1
    +4                            Append 4 to the resulting array
  *F                              Then multiply it all together
                          1     Else 1

```

**Edit:** Put the bitwise and back in for more byte savings! Also I removed all the "Formerly" stuff. It was starting to get cluttered.

Thanks to aditsu and his CJam solution, and to maltysen and his tips (One day I will get `m*Fd` to work. One day...)

```
J4Vr-PQ2 8=J*J.&tt%eN4hhN;?QJ1
                                (implicit) Q=input()
J4                              J=4
    -PQ2                        Remove all 2's from the prime factorization of Q
   r     8                      run-length encode (exponent, prime factor)
  V                      ;      For N in range( the above ):
          =J*J                      J = J * ...
                tt%eN4                N[-1] mod 4 -2
                      hhN             (exponent + 1)
              .&                    bitwise and
                          ?QJ1  if Q != 0 print(J) else print(1)

```

Note that,

* if the prime is 1 mod 4, we get `-1 & (exponent + 1)`, which is `exponent + 1`
* but if the prime is 3 mod 4, we get `1 & (exponent + 1)`, which is `0` if the exponent is odd, and `1` if even

Multiply it all together (times 4 at the beginning) and we get the number of sums of two squares that add up to our input.
> 2 votes

# Answer
# Python, 57 bytes

Nice challenge. Unfortunately I'm not getting it shorter than this at the moment.

```
lambda n:0**n+sum(2-d%4for d in range(1,n+1)if d%2>n%d)*4

```
> 2 votes

# Answer
## Matlab, 72 bytes

```
n=input('');m=fix(sqrt(n));m=(-m:m).^2;disp(nnz(bsxfun(@plus,m,m')==n))

```
> 1 votes

# Answer
# Matlab, ~~63~~ 50 bytes

```
@(y)nnz(~mod(sqrt(y-power((1:sqrt(y)),2)),1))*4+~y

```

---

* This does beat the other same-entitled code, thus I put it :D.
* The program finds the positive integer solutions then multiply by 4 to encompass negative ones.
* It can perform all 25 first test cases

```
for i=1:25 ans(i)
end

   1

   4

   4

   0

   4

   8

   0

   0

   4

   4

   8

   0

   0

   8

   0

   0

   4

   8

   4

   0

   8

   0

   0

   0

   0

   12

```
> 1 votes

# Answer
## Python, ~~133~~ 129 bytes

```
from itertools import*
n=input()
l=[];s=0
for i in range(-n,n+1):l.append(i**2)
for j in product(l,l):
 if sum(j)==n:s+=1
print s

```

This demonstrates the use of itertools cartesian product. Try it online
> 1 votes

# Answer
# JavaScript, 89 bytes

```
n=prompt()
p=Math.pow
for (x=c=(+n?0:1);x<=n;x++)if(x&&p(n-p(x,2),.5)%1===0)c+=4
alert(c)

```

I know this isn't the shortest JavaScript answer even if I were to remove the i/o lines, but I do think it is the best performing JS answer giving me the result for a million within a few seconds (ten million took about a minute).
> 1 votes

# Answer
# PHP, 80 Bytes

```
for($m=-$a=1+$argv[1];++$m<$a;)for($n=-$a;$n++<$a;)$c+=$a-1==$m**2+$n**2;echo$c;

```
> 1 votes

# Answer
# PHP, 70 bytes, not competing

```
for($x=-1;$x++<=$n=$argv[1];)$s+=(-($n%($x-~$x)<1))**$x*4;echo$n?$s:1;

```

algorithm stolen from one of the Python answers ... I forgot which one; wanted to at least partially understand what´s happening before I posted.
> 1 votes

# Answer
# ASP, 53 + 4 = 57 bytes

```
#show N:N=#count{o(A,B):k=A**2+B**2,A=-k..k,B=-k..k}.

```

Answer Set Programming is a logical language, similar to prolog. I use here the Potassco implementation, *clingo*.

Input is taken from parameters (`-ck=` is 4 bytes long). Call example:

```
clingo -ck=25

```

Output sample:

```
12

```

You can try it in your browser ; unfortunately, this method doesn't handle call flags, so you need to add the line `#const k=25` in order to make it work.
> 1 votes

# Answer
# Add++, 31 bytes

```
D,f,@,.5^1+iR2€Ω^d0BFB]d‽+A€=¦+

```

Try it online!

## How it works

This defines a function, \\$f\\$, that takes the input, \\$x\\$, as an argument and returns the correct output. We start by yielding \\$y := \lfloor\sqrt{x}+1\rfloor\\$. We then push the range \\$a := \[1, 4, ..., y^2\]\\$, the list of square numbers up to the smallest square number larger than \\$x\\$. We then duplicate this array and push \\$0\\$ to the stack. At this point, the stack looks like this, for an input of \\$25\\$:

```
[[1 4 9 16 25 36] [1 4 9 16 25 36] 0]

```

We then collect these values into a single list, which yields the list of \\$n^2\\$ for each \\$n \in \[-y, y\]\\$. We then duplicate this list and operate the *table* operator over the addition command. The *table* operator takes a dyad, \\$g(p, q)\\$, and two arrays, \\$A\\$ and \\$B\\$. It then takes the Cartesian Product of \\$A\\$ and \\$B\\$ and iterates \\$g(a, b)\\$ over each pair \\$(a, b)\\$ where \\$a \in A\\$ and \\$b \in B\\$.

In this code, this yields the array \\$\big\[a^2+b^2 \\: | \\: a, b \in \[-y, y\]\big\]\\$. We then compare each element of this list with the input, yielding a boolean array. Finally, we count the number of \\$1\\$s in this array by taking its sum, and returning that total.

Most of the code should be understandable when paired with the explanation. A few of the overlooked commands:

* `Ω` : The *reverse* operator. Takes a dyad and reverses the order of the arguments
* : The *table* operator, as described above.
* `¦` : The *fold* operator. Takes an array and a dyad and reduces by the dyad. `¦+` is an alias for sum.
> 1 votes

# Answer
# MathGolf, 9 bytes

```
╤■mæ²Σk=Σ

```

Try it online.

**Explanation:**

```
╤         # Take the (implicit) input-integer, and push a list in the range [-input, input]
 ■        # Take the cartesian product of this, creating a list of all possible pairs
  mæ      # Map these pairs to, using the following four commands:
    ²     #  Take the square of both values in the pair
     Σ    #  Sum those
      k=  #  And check whether it's equal to the input-integer (1 if truthy; 0 if falsey)
  Σ       # After the map, sum the list
          # (after which the entire stack joined together is output implicitly)

```
> 1 votes

# Answer
# 05AB1E, 7 bytes

```
(ŸãnOQO

```

Try it online or verify the test cases in the range \\$\[0,100\]\\$.

**Explanation:**

```
(        # Get the negative of the (implicit) input-integer
 Ÿ       # Push a list in the range [(implicit) input-integer, -input]
  ã      # Get the cartesian product of this list, creating all possible pairs
   n     # Square each value in each pair
    O    # Sum each inner pair
     Q   # Check for each sum whether it's equal to the (implicit) input-integer
         # (1 if truthy; 0 if falsey)
      O  # And sum those
         # (after which the result is output implicitly)

```
> 1 votes

# Answer
# Japt `-x`, 11 bytes

```
õUn)ï £¶Xx²

```

Try it
> 1 votes

# Answer
# Jelly, 7 bytes

```
rNp`²§ċ

```

Try it online!

## How it works

```
rNp`²§ċ - Main link. Takes n on the left
 N      - Yield -n
r       - Take the range [-n, -n+1, ..., -1, 0, 1, ..., n-1, n]
   `    - Use this list for both arguments for:
  p     -   Cartesian product
    ²   - Square each number
     §  - Take the sums of each pair
      ċ - Count the number of times n appears

```
> 1 votes

# Answer
# Perl 5, 52 bytes

56 bytes:

```
$n=pop;for$a(@a=-$n..$n){map$i+=$_*$_+$a*$a==$n,@a}say$i

```

If output can be in base 1, then 52 bytes:

```
$n=pop;for$a(@a=-$n..$n){print$_*$_+$a*$a==$n for@a}

```
> 0 votes

# Answer
## Python, ~~76~~ 74 bytes

I'm sure this can be golfed more, but I need to get back to work.

```
lambda n:sum([1for a in range(-n,n+1)for b in range(-n,n+1)if a*a+b*b==n])

```

Try it online

Thanks to @mathmandan for taking off 2 bytes.
> 0 votes

# Answer
# Ruby, ~~66~~ ~~58~~ ~~56~~ 54 bytes

```
->n{r=-n..n;r.map{|x|r.count{|y|n==x*x+y*y}}.reduce:+}

```

Thanks to sherlock9.

**56 bytes**

```
->n{r=-n..n;r.map{|x|r.count{|y|n==x**2+y**2}}.reduce:+}

```

**58 bytes**

```
->n{c=0;r=(-n..n);r.map{|x|c+=r.count{|y|n==x**2+y**2}};c}

```

**66 bytes**

```
->n{c=0;(-n..n).each{|x|c+=n.downto(-n).count{|y|n==x**2+y**2}};c}

```

**Ungolfed:**

```
-> n {
  r = -n..n
  r.map { |x|
    r.count { |y|
      n == x*x + y*y
    }
  }.reduce:+
}

```

**Usage:**

```
->n{r=-n..n;r.map{|x|r.count{|y|n==x*x+y*y}}.reduce:+}[25]
=> 12

```
> 0 votes

# Answer
## C, 224 219 182 175 158 bytes

Non-golfed version (with descriptive variables):

```
#include <math.h>

main (argc, argv)
    char **argv;
{

    int n, count, max, i, j;
    n = atoi (argv[1]);
    count = 0;
    max = sqrt ((float) n);

    for (i = -max; i <= max; i++)
        for (j = -max; j <= max; j++)
            if (i * i + j * j == n)
                count++;

    printf ("%d", count);
}

```

Golfed version (with short variables):

```
#include<math.h>
main(c,v)char**v;{int n,o,x,i,j;n=atoi(v[1]);o=0;x=sqrt((float)n);for(i=-x;i<=x;i++)for(j=-x;j<=x;j++)if(i*i+j*j==n)o++;printf("%d",o);}

```

**Update** Sorry about the multiple edits, I'm learning how to abuse K&R-style C ;)
> 0 votes

# Answer
## C++, 175 bytes

```
#include<iostream> using namespace std; int main() {int i,j,k=0,n; cin>>n; for(i=1;i<n;++i) for(j=1;j<n;++j) if(i*i+j*j==n) ++k; for(i=1;i<=n;++i) if(i*i==n) ++k; cout<<4*k;}

```

Ungolfed

```
#include<iostream>
using namespace std;
int main()
{
int i,j,k=0,n;
cin>>n;
for(i=1;i<n;++i)
 for(j=1;j<n;++j)
  if(i*i+j*j==n)
   ++k;
for(i=1;i<=n;++i)
 if(i*i==n)
  ++k;
cout<<4*k;
}

```
> 0 votes

# Answer
# Swift 2.0, ~~110~~ ~~108~~ 107 bytes

```
var n=Int(readLine()!)!,c=0;for(var i = -n;i<=n;i++){for(var j = -n;j<=n;j++){if i*i+j*j==n{c++}}};print(c)

```

First attempt
> 0 votes

# Answer
# Axiom 115 bytes

```
g(n)==(v:INT:=truncate(sqrt(n)::Float);c:=0;for i in -v..v repeat for j in -v..v repeat if i^2+j^2=n then c:=c+1;c)

```

ungolfed

```
gg(n:NNI):NNI==
   v:NNI:=truncate(sqrt(n)::Float)
   c:NNI:=0
   for i in -v..v repeat
      for j in -v..v repeat
          if i^2+j^2=n then c:=c+1
   c

```

results

```
(5) -> [i,g(i)]  for i in 0..25
   Compiling function g with type NonNegativeInteger -> NonNegativeInteger
   (5)
   [[0,1], [1,4], [2,4], [3,0], [4,4], [5,8], [6,0], [7,0], [8,4], [9,4],
    [10,8], [11,0], [12,0], [13,8], [14,0], [15,0], [16,4], [17,8], [18,4],
    [19,0], [20,8], [21,0], [22,0], [23,0], [24,0], [25,12]]
                                      Type: Tuple List NonNegativeInteger

```

dobious results

```
(13) -> g(10018)
   (13)  8
                                                    Type: PositiveInteger
(14) -> g(10019)
   (14)  0
                                                 Type: NonNegativeInteger
(15) -> g(10020)
   (15)  0

```
> 0 votes

# Answer
# C++, 81 bytes

```
#define F(x) for(int x=~n;x++<n;)
void f(int n,int&r){r=0;F(a)F(b)r+=a*a+b*b==n;}

```

Returns via reference parameter. Simply two ranges over `[-n,n]`, so it works for `n=0`.
> 0 votes

# Answer
# Husk, 8 bytes

```
#¹´×+m□ṡ

```

Try it online! or Verify first 25 values

# Husk, 8 bytes

```
#¹mṁ□π2ṡ

```

Try it online!
> 0 votes

# Answer
# Thunno 2 `S`, 7 bytes

```
ṄIDṖ²ʂ=

```

Try it online!

#### Explanation

```
ṄIDṖ²ʂ=  # Implicit input
ṄI       # Push [-input..input]
  DṖ     # Cartesian product
    ²ʂ   # Square and sum
      =  # Equals input?
         # Sum the list
         # Implicit output

```
> 0 votes

---
Tags: code-golf, math, combinatorics, number-theory
---


title: Find the sum of primes

text:
# Question
Title: Find the sum of primes
Given a number x, find the sum of all primes up to that number.

The input will always be a positive number, bigger than 2. An upper limit isn't defined, so data types can be ignored. Use whichever you want.

* This is a , so the shortest code in bytes wins.

Example for 5:

`2 + 3 + 5 = 10`

Test cases:

| Input | Output |
| --- | --- |
| 2 | 2 |
| 3 | 5 |
| 17 | 58 |

The input doesn't have to be parsed, so assume you get the "correct" data-type. (`int` in Java, for example)

# Answer
# Thunno 2 `S`, 2 bytes

```
æP

```

Try it online!

#### Explanation

```
    # Implicit input
æ   # Filter [1..input] by:
 P  #  Prime check
    # Sum the list
    # Implicit output

```
> 0 votes

---
Tags: code-golf, math
---


title: 1/N probability

text:
# Question
Title: 1/N probability
Because there are not enough simple challenges:

Create an optionally unnamed program or function that, given (by any means) an integer 1 ≤ N ≤ 10000, outputs your language's True value with a pseudo-random probability of 1/N, False otherwise.

**Please note that the requirement for naming has been removed. Feel free to edit answers and scores accordingly.**

Some languages use 1 (or -1) and 0 for True and False, that is fine too.

**Example:**

Example input tests:

```
4 -> True
4 -> False
4 -> False
4 -> False
4 -> False
4 -> True
4 -> False
4 -> False

```

I.e. given 4; it returns True with a 25% chance and False with a 75% chance.

# Answer
> 27 votes
# MediaWiki templates with ParserFunctions, 48 bytes

```
{{#ifexpr:1>{{#time:U}} mod {{{n}}}|true|false}}

```

# Answer
> 15 votes
# Pyth, 3 bytes

```
!OQ

```

Try it online

Simple inversion of random choice from 0 to input

Amusingly in Pyth it is not possible to make a function that does this without `$` because Pyth functions are automatically memoized.

# Answer
> 12 votes
## CJam, 5 bytes

Gotta be quick with these ones...

```
rimr!

```

Test it here.

### Explanation

```
ri e# Read input and convert to integer N.
mr e# Get a uniformly random value in [0 1 ... N-1].
!  e# Logical NOT, turns 0 into 1 and everything else into 0.

```

# Answer
> 12 votes
## TI-BASIC, 4 bytes using one byte tokens

```
not(int(Ansrand

```

Determines if the integer part of the input times a random number in \[0,1) is zero. `Ansrand<1` also works.

# Answer
> 11 votes
## MATL, 5 bytes

Three different versions of this one, all length 5.

```
iYr1=

```

which takes an input (`i`), generates a random integer between 1 and that number (`Yr`), and sees if it it is equal to 1 (`1=`). Alternatively,

```
li/r>

```

make a 1 (`l`, a workaround because there is a bug with doing `1i` at the moment), take an input (`i`), divide to get 1/N (`/`), make a random number between 0 and 1 (`r`), and see if the random number is smaller than 1/N. Or,

```
ir*1<

```

take and input (`i`), and multiply by a random number between 0 and 1 (`r*`), and see if the result is smaller than 1 (`1<`).

In Matlab, not MATL, you can do this anonymous function

```
@(n)n*rand<1

```

for 12 bytes, which is used by doing `ans(5)`, for example.

# Answer
> 10 votes
# Julia, ~~17~~ ~~16~~ 15 bytes

```
n->2>rand(1:n)

```

This is a function that generates a random integer between 1 and `n` and tests whether it's less than 2. There will be a 1/n chance of this happening, and thus a 1/n chance of returning `true`.

Saved 1 byte thanks to Thomas Kwa!

# Answer
> 10 votes
# JavaScript ES6, 15 bytes

-5 bytes thanks to Downgoat.

```
x=>1>new Date%x

```

Based off (uses) of this answer's technique.

# Answer
> 9 votes
# Microscript II, 3 bytes

```
NR!

```

Reads an integer `n`, generates a random integer between `0` and `n-1` (inclusive), then applies a boolean negation to that value.

# Answer
> 8 votes
# Candy, 2 bytes

```
Hn

```

*H* stands for *Heisen-double*

*n* stands for *not*

The 'n' is passed with the -i flag as numeric input. Values left on the stack are printed on exit.

"Long" form:

```
rand   # number between 0 and pop()
not    # cast to int, invert non-zero to zero, and zero to one

```

# Answer
> 7 votes
# R, ~~30~~ 22 bytes

### code

```
cat(runif(1)<1/scan())          #new
f=function(N)cat(runif(1)<1/N)  #old

```

It generates a number from a uniform distribution (0 to 1) and should evaluate to true 1/n of the times.

# Answer
> 7 votes
## Seriously, 3 bytes

```
,JY

```

`0` is falsey and `1` is truthy. Try it online

Explanation:

```
,JY
,    get input
 J   push a random integer in range(0, input) ([0, ..., input-1])
  Y  logical not: push 0 if truthy else 1

```

# Answer
> 6 votes
# APL, ~~6~~ 3 bytes

```
+=?

```

This is a function train that takes an integer and returns 1 or 0 (APL's true/false). We generate a random integer from 1 to the input using `?`, then check whether the input is equal to that integer. That results in a 1/input chance of true.

Saved 3 bytes thanks to Thomas Kwa!

# Answer
> 6 votes
# Japt, 6 bytes

```
1>U*Mr

```

Try it online!

`Mr` is equivalent to JS's `Math.random`. The rest is pretty obvious. I could probably add a number function that generates a random float between 0 and the number. When this happens, two bytes will be saved:

```
1>Ur    // Doesn't currently work

```

Alternate version:

```
1>Ð %U

```

`Ð` is equivalent to `new Date(`, and the Date object, when asked to convert to a number, becomes the current timestamp in milliseconds. Thus, this is entirely random, unless it is run multiple times per ms.

# Answer
> 6 votes
# PlatyPar, 3 bytes

```
#?!

```

`#?` gets a random number `[0,n)` where `n` is input. `!` returns `true` if the number before it is `0`, else it returns `false`.

Using more recent features that were implemented (but unfortunately for me not committed) before this question was asked I can get it down to 2 with `~!` Try it online!

# Answer
> 6 votes
# Marbelous, 21 bytes

```
}0    # takes one input n
--    # decrements n
??    # random value from range 0..n (inclusive)
=0?0  # push right if not equal to 0, fall through otherwise | convert to zero
++    # increment | no-op
{0//  # output | push left

```

I've taken `0` to be falsey and `1` to be truthy, though there is no real reason for that seeing as Marbelous doesn't really have an if. More Marbelousy would be output to `{0` for true and `{>` for false. This would look like this:

```
}0
--
??
=0{>
{0

```

But I'm not sure that's valid.

# Answer
> 5 votes
# Java, 43 bytes

```
boolean b(int a){return a*Math.random()<1;}

```

# Answer
> 5 votes
# C, 24 bytes

```
f(n){return!(rand()%n);}

```

# Answer
> 5 votes
# \>\<\>, 27 + 3 for -v = 30 bytes

Here is a not-uniform-at-all solution where I mod N the sum of 15876 random picks of 0 or 1 :

```
0"~":*>:?vr%0=n;
1-$1+$^-1x

```

N must be input on the stack with -v flag, output is 0 for falsey and 1 for truthy.

A much smarter and uniform solution that work for 1/2^N instead :

```
4{:?!v1-}:">"$2p:"x"$3p:"^"$4p1+:">"$3p1+!
   ^1<
0n;
1n;>

```

For an input 3 you've got 1/8 chances of getting 1 and 7/8 of getting 0.

Explanation :

I append as much `x` as needed on the 4th line and surround them with directions so there is only two ways out of the `x`: either the falsey output or the next `x`. If all `x` go in the right direction, the last one will route to the truthy output.

For example for N=5, the final codespace is the following :

```
4{:?!v1-}:">"$2p:"x"$3p:"^"$4p1+:">"$3p1+!
   ^1<
0n; > > > > >
1n;>x>x>x>x>x>
    ^ ^ ^ ^ ^

```

# Answer
> 4 votes
## Mathematica, ~~18~~ 16 bytes

```
#RandomReal[]<1&

```

Basic solution. The unnamed `Function` creates a random number in \[0, 1), multiplies it by its argument, and checks if it is still less than 1.

# Answer
> 4 votes
# Python, 42 bytes

```
import random
lambda n:1>random.random()*n

```

*Edit*: Removed the `time.time()` answer because of the distribution.

# Answer
> 4 votes
## TeaScript, 3 bytes

```
!N×

```

Try it here.

### Explanation

```
 N  maps to Math.rand which is a utility function that returns an integer
    between `arg1` and `arg2` or `0` and `arg1` if only one argument is
    provided.
  × is expanded to `(x)`, where `x` is initialised with the value provided
    in the input boxes; × represents byte '\xd7'
!   negate the result, 0 results in true, anything else false

```

# Answer
> 4 votes
# Fuzzy Octo Guacamole, 10 bytes

```
^-!_[0]1.|

```

Explanation:

```
^-!_[0]1.|

^          # Get input.
 -         # Decrement, so we can append <ToS> zeros and a 1 to the stack.
  !        # Set loop counter.
   _       # Pop, since we are done with the input.
    [      # Start loop
     0     # Push 0
      ]    # End for loop. We have pushed input-1 0s to the stack.
       1   # Push a single 1 to the stack.
        .  # Switch stacks
         | # Pick a random item from the inactive stack, which has n-1 falsy items and 1 truthy item, so the truthy probability is 1/n.
           # (implicit output)

```

# Answer
> 3 votes
# Ruby, 14

Function

```
->n{rand(n)<1}

```

Program is slightly longer

```
p rand(gets.to_i)<1

```

# Answer
> 3 votes
# Perl 6,  ~~10~~  8 bytes

~~```
!(^*).pick
#  ^- The * is the argument

```
This code creates a Range from 0 up-to but excluding the input `*`. It then `pick`s one at random and the `!` returns True when it receives a `0`.
~~
```
1>*.rand
# ^- The * is the argument

```

This takes the input `*` and multiplies it by a random Num from `0..^1` then returns True if it was smaller than `1`.

```
# store it in a lexical code variable for ease of use
my &code = 1>*.rand;

die "never dies here" unless code 1;

for ^8 { say code 4 }

```

```
False
True
False
False
False
True
False
False

```

# Answer
> 3 votes
## C#, ~~56~~ 45 bytes

Thanks to, pinkfloydx33 it's 45 now.

```
bool b(int n){return new Random().Next(n)<1;}

```

### Old 56 bytes

Generates random positive integer bigger or equal to 0 and smaller than `n` and checks if it's smaller than `1` and return comparison result.

```
bool a(int n){Random r=new Random();return r.Next(n)<1;}

```

# Answer
> 3 votes
# PHP, 22 bytes

```
<?=2>rand(1,$argv[1]);

```

Reads `n` from command line, like:

```
$ php probability.php 4

```

Outputs  (`false` is cast to an empty string in PHP) or `1` (in case of `true`).

# Answer
> 3 votes
# Prolog (SWI), 24 bytes

**Code:**

```
p(N):-X is 1/N,maybe(X).

```

**maybe(+P)** is a function which succeeds with probability **P** and fails with probability **1-P**

**Example:**

```
p(4).
false

p(4).
false

p(4).
true

```

# Answer
> 3 votes
## PowerShell, 25 Bytes

```
!(Random -ma($args[0]--))

```

The `Get-Random` function when given a `-Ma`ximum parameter `n` returns a value from the range `[0,n)`. We leverage that by subtracting 1 from our input `$args[0]`, so we're properly zero-indexed, and get a random value. Precisely `1/n`th of the time, this value will be `0`, so when we Boolean-not it with `!` it will return `True`. The other times will return `False`.

# Answer
> 3 votes
# Scratch, 63 bytes

Try it online!
Picture:
Scratchblocks code:

```
when gf clicked
ask[]and wait
say<(pick random(1)to(answer))=[1

```

# Answer
> 3 votes
## J, 3 bytes

```
0=?

```

This is a monadic fork that takes an argument on the right. Similarly to APL, ? generates a random integer; however, J arrays are zero-based. So we compare to 0 instead of to the input.

# Answer
> 3 votes
## Minkolang 0.14, 7 bytes

```
1nH1=N.

```

Try it here.

### Explanation

```
1          Pushes 1
 n         Takes number from input
  H        Pops b,a and pushes a random integer between a and b, inclusive
   1=      1 if equal to 1, 0 otherwise
     N.    Output as number and stop.

```

# Answer
> 2 votes
## Perl, ~~18~~ 12 bytes

```
$_=1>rand$_

```

That is 11 bytes + 1 for the `-p` commandline argument.
Save in a file (any name, say, `16.pl`) and run as: `echo 4 | perl -p 16.pl`.
It will print an empty line for false, and 1 for true.

As a function: **18 bytes**

```
sub f{1>rand$_[0]}

```

# Answer
> 2 votes
# , 3 chars / 6 bytes

```
!⁇ï

```

`Try it here (Firefox only).`

The punctuation is strong with this one.

# Answer
> 2 votes
# Racket, 21 bytes

```
(λ(x)(=(random x)0))

```

# Answer
> 2 votes
# Reng v.3.3, noncompeting, 6 bytes

```
iu0en~

```

`i` takes input, `u` pushes a random integer in `[0,i)`, `0e` checks if the value is `e`qual to `0`, `n` outputs that value, and `~` terminates the program.

Try it here!

# Answer
> 2 votes
# Befunge-93, ~~99~~ ~~98~~ ~~96~~ ~~95~~ ~~92~~ ~~90~~ 84 bytes

```
<vp90:g80<p80 &
v?v>v>9g1-:0`|
0^1-:0v\g80:$<
>v<10^ +*2p90<
@>\^`$`  >!.
 v  _^>  |

```

Try it online!

This deserves a separate spot from my other answer, as I did this from scratch.

This generates an integer (**x**) in the range **\[0,2^n)** using random binary digits, then redoes the program if **x\>=n** (Actually by checking **!(n\>x)**, because befunge). Then, it tests if **x=0**, outputting the result.

Any ways to knock off bytes are wanted!

# Answer
> 1 votes
# Perl 5, 10 bytes

A subroutine:

```
{1>rand@_}

```

It takes input as a list of `1`s of the appropriate length.

Hat-tip.

# Answer
> 1 votes
## \>\<\>, 44 + 3 = 47 bytes

```
&v<
0x1v
?^0\l&:&-
1=?\2*+l
?!v\:&:&(
n;~>0=

```

Try it online, or watch it at the fish playground!

Input is taken on the stack, with the `-v` flag (hence the +3 bytes). Unlike the other \>\<\> answer, this has a theoretically correct distribution, not just an approximately correct one (assuming the pseudo-random stuff behind the scenes is uniform).

Randomness is tricky in \>\<\>: the only non-deterministic instruction is `x`, which sets the fish's direction randomly from four choices.

If you want a uniform random number from 1 to *N* but you only have a (fair) *m*-sided die, where *m* \> *N*, you can do it by rolling the die, checking if the result is in the right range, and re-rolling if it isn't until you get a number between 1 and *N*. There's a probability of exactly 0 that you'll keep rolling the die forever without end, and the result you get (if the process terminates) is uniformly distributed. Also, if 1 \< *m* \< *N*, you can simulate an *m**k*-sided die by rolling it *k* times, and you can make *m**k* larger than *N* by picking *k* large enough. Thus you can simulate any rational probability using any die with more than 1 side (if you don't mind a vanishingly small chance of rolling the die forever).

This program rolls a 2*N*-sided die, by getting *N* random 1s or 0s and reading them in binary. The number 2*N* is always bigger than *N* for *N* ≥ 1, although it's usually a LOT bigger, so for large *N* you'll be waiting a while. TIO handles up to about *N* = 16.

# Answer
> 1 votes
# Befunge-93, ~~185~~ ~~171~~ ~~169~~ ~~142~~ ~~125~~ ~~124~~ ~~121~~ ~~118~~ ~~116~~ ~~113~~ 124 bytes

```
 &v>:00pv _v>v>\v
 > ^<  v?v:$1-+ :
@g:    1^2-1^   _$v>g`| @.0_1.
.$1    >v<1-\2*v+1<   >00g-^
 ^-     >\^>^>^>:00^  >
^#_#^

```

Try it online!

This uses the exact same strategy as this \>\<\> answer (generate an integer in the range `[1,2^n]` by generating `n` random binary digits then converting it, then try again if the resulting integer is outside of the range `[1,n]`), but with two modifications:

* Separate case for `n=1`
* The binary digits are at first generated with `1`s and `2`s, since Befunge pops `0` off of the stack when empty. After the digits are generated, they are decremented to their normal binary and converted to an integer in place.

This is surprisingly fast!

Anything that will reduce the bytecount are welcome, considering I'm not a good befunge-golfer (especially when it comes to `g` and `p`)

I apparently am horrible at reading directions, as I originally only outputted a random integer in the range `[1,n]` \>\_\<.

# Answer
> 1 votes
# Jelly, 2 bytes

```
XỊ

```

Try it online! (contains a footer that runs the program 100 times and reports the results)

I had to triple-check to make sure that Jelly wasn't here yet; it's a popular language, after all. But it turns out it wasn't.

`X` picks a random element from a list. Because it's at the start of the program but requires an input, it'll implicitly take the first command line argument as input. Most commands, when they expect a number but are given a list, convert the number into a range from 1 to that number; thus, for example, an input of 4 will pick a random element from \[1, 2, 3, 4\]. (Actually, Jelly has a special case to optimise this internally by not constructing the list.) Note that for an input of *n*, this means that there's a 1 in *n* chance of picking 1 as our element.

Once we have our element, we run  on it. That's a test for a small value, i.e. no higher than 1 or smaller than -1. The only element that we can produce that matches this condition is 1, so we get an output of true (expressed as `1` in Jelly) with 1/n probability, and false (expressed as `0` in Jelly) the rest of the time. The output then gets printed implicitly.

(This submission also works as a function rather than a full program, exactly the same way; the implicit input is then taken from the function argument, and the implicit output used as the function's return value.)

# Answer
> 1 votes
# SmileBASIC, 15 bytes

```
INPUT N?!RND(N)

```

`RND(n)` generates a random number from `0` to `n-1`, so there's a `1/n` chance that it will be `0`. Then it just uses `!` (logical not) to convert this to a `1/n` chance of generating `1` (true), and prints the result.

# Answer
> 1 votes
## Keg, 6 bytes

```
¿~$%2<

```

Takes random number & input, modulos them and checks whether the result is less than 2.

# Answer
> 0 votes
# MY, 5 bytes

```
ω0x=←

```

Try it online!

## How it works:

Generates a random integer in the range `[0,n)`, then tests for equality with `0`.

# Answer
> 0 votes
# GolfScript, 8 bytes

```
~rand 0=

```

Try it online!

# Answer
> 0 votes
# J, 6 bytes

```
?&0:<%

```

## explanation

A J fork:

```
      ?&0:                <               %
NB. uniform float    is less than?    1 / input

```

Try it online!

# Answer
> 0 votes
# x86, 10 bytes

Apparently there's a fairly new instruction called `rdrand` which makes this program pretty trivial.

Input in `ecx`, output in `ZF`. I consider one of x86's flags as a valid return value, which is arguably more useful than `setz` and returning in `eax`. It would've been very convenient if `div` set `ZF`.

```
5:  0f c7 f0                rdrand %eax
8:  31 d2                   xor    %edx,%edx
a:  f7 f1                   div    %ecx
c:  85 d2                   test   %edx,%edx
e:  c3                      ret

```

# Answer
> 0 votes
# Gol\>\<\>, 7 bytes

```
ISx*1(h

```

Try it online!

### How it works

```
ISx*1(h

I        Take input as number
 Sx      Generate random number in [0,1)
   *     Multiply the two
    1(   Is it less than 1?
      h  Print the result as number and halt

```

# Answer
> 0 votes
# Thunno 2 `!`, 2 bytes

Try it online!

#### Explanation

```
    # Implicit input
L   # Push [0..input)
 ɼ  # Take a random item
    # Logical NOT
    # (Check for != 0)
    # Implicit output

```

# Answer
> 0 votes
# 05AB1E, 2 bytes

Only `1` is truthy in 05AB1E, everything else is falsey, which is used to our advantage here.

Try it online or try it online an infinite amount of times with additional 05AB1E-truthify (`==1`) check.

**Explanation:**

```
L   # Push a list in the range [1, (implicit) input]
 Ω  # Pop and push a random integer from this list
    # (which is output implicitly as result)

```

---
Tags: code-golf, random, probability-theory
---