title: "Convenient palindrome" checker

text:
# Question
Title: "Convenient palindrome" checker
If you've ever tried to write palindromic code before, you'd know how much brackets tend to get in your way. `()()` is not a palindrome, even though it kinda looks like it should be, while `())(` and `()(` are both palindromic and both very dumb looking. Wouldn't it be convenient if it was the other way around?

A string is *conveniently palindromic* if it is equal to the string derived when its reverse has all its parentheses (`()`), brackets (`[]`), and braces (`{}`) flipped. No other characters are special and require flipping. (`<>` are sometimes paired but often not so they are left out.)

**Your task** is to write, in your language, a program (taking input on STDIN) or a function (taking a single string argument) which (a) gives a consistent true value\* when its argument is conveniently palindromic and a different, consistent false value otherwise, and (b) is *itself* conveniently palindromic.

For example, the following inputs are conveniently palindromic:

```
racecar
(a)(bb)(a)
void main(int argc, *char[] argv) {} (vgra []rahc* ,cgra tni)niam diov

```

And the following are not:

```
non-palindrome
A nut for a jar of tuna?
(old [style] parens) )snerap ]elyts[ dlo(
ingirumimusnocte)etconsumimurigni

```

You may not rely on any external state (specific filename, directory structure, other user input, web access, etc) except interpreter/compiler flags.

Also, you may not use "the comment trick" where you comment out or render unused some piece of code by taking advantage of your language's commenting facilities. For instance, all of the following are not allowed, because they contain non-functional parts that can be safely removed or destroyed (at the expense of losing conveniently-palindromic-ness):

```
{some code} // {edoc emos}
{some code} NB.BN {edoc emos}
"n\" ;{edoc emos} ;"; {some code}; "\n"

```

Obviously this might not cover every such case, but the spirit of the challenge here is not to use comments and unparsed\** code to achieve palindrominess, instead making use of the corrected parens and brackets. I'm looking at you, LISP, Brainfuck.

This is a , so the shortest code wins, but all lengths of code are welcome.

* By consistent true and false values, I mean that you can return one of a pair of values, such as `1` for true and `0` for false, or `False` for true and `"no"` for false, so long as these values are different from each other, and do not change from run to run of your program. Use whatever saves you characters.

\** Not to be confused with *unexecuted*: code that is valid and might do weird things but never called is fine.

# Answer
## J (60)

```
(|.-:'())([]][{}}{'&charsub) :: (busrahc&'}{{}][[])(()':-.|)

```

This is a function that takes an argument:

```
   (|.-:'())([]][{}}{'&charsub) :: (busrahc&'}{{}][[])(()':-.|) 'ingirumimusnocte)etconsumimurigni'
0
   (|.-:'())([]][{}}{'&charsub) :: (busrahc&'}{{}][[])(()':-.|) '(a)(bb)(a)'
1

```

Explanation:

* `f :: g` runs the function `f` over the input, and returns the result if it returns without error. If `f` fails, it runs `g` instead.
* The `f` here is `(|.-:'())([]][{}}{'&charsub)`, which does the actual work:

+ `|.`: reverse
    + `-:`: is equal to
    + `'())([]][{}}{'&charsub`: replacing each bracket with its opposing bracket
* The `g` function is `(busrahc&'}{{}][[])(()':-.|)`, which is nonsense but syntactically valid. `busrahc` is not defined, but that doesn't matter because it is only resolved when it is run (and it won't run).
> 13 votes

# Answer
# GolfScript, ~~107~~ 91

```
.4:ab-1:ba=;1
%ba%{...fi@@=
c43.=;)('"([{
}])"'~?~'"([{
}])"')(;=.34c
=@@if...}%ab%
1;=ab:1-ba:4.

```

Newlines are artistic. `fi`, `c43` and `c` are noops, but **the entire code is executed.**

Prints `-3-1-1` for convenient palindromes, `-4-1-1` otherwise. Try it online!

### Alternate version, 155 bytes

At the cost of 64 bytes, this can be improved upon:

```
0!*1{!}\;:);0:f;0:i;-1:ab;9:ba;
...=;1%ab%{....i@f@@fi@@=@.=@\)
+""'"([{}])"'~+?+~'"([{}])"'""+
(\@=.@=@@if@@f@i....}%ba%1;=...
;ab:9;ba:1-;i:0;f:0;(:;\{!}1*!0

```

As before, the entire code is executed and **every single byte affects the output.**

Prints `010` for convenient palindromes, `-100` otherwise. Try it online!

### Tests and examples

```
$ base64 > palindrome.gs -d <<< LjQ6YWItMTpiYT07MSViYSV7Li4uZmlAQD1jNDMuPTspKCciKFt7fV0pIid+P34nIihbe31dKSInKSg7PS4zNGM9QEBpZi4uLn0lYWIlMTs9YWI6MS1iYTo0Lg==
$ wc -c palindrome.gs
91 palindrome.gs
$ rev palindrome.gs | tr '([{}])' ')]}{[(' | diff - palindrome.gs
$ echo -n 'r(a[c{"e"}c]a)r' | golfscript palindrome.gs
-3-1-1
$ echo -n 'totallynotapalindrome' | golfscript palindrome.gs
-4-1-1
$
$ base64 > pal.gs -d <<< MCEqMXshfVw7Oik7MDpmOzA6aTstMTphYjs5OmJhOy4uLj07MSVhYiV7Li4uLmlAZkBAZmlAQD1ALj1AXCkrIiInIihbe31dKSInfis/K34nIihbe31dKSInIiIrKFxAPS5APUBAaWZAQGZAaS4uLi59JWJhJTE7PS4uLjthYjo5O2JhOjEtO2k6MDtmOjA7KDo7XHshfTEqITA=
$ wc -c pal.gs
155 pal.gs
$ rev pal.gs | tr '([{}])' ')]}{[(' | diff - pal.gs
$ echo -n 'r(a[c{"e"}c]a)r' | golfscript pal.gs
010
$ echo -n 'totallynotapalindrome' | golfscript pal.gs
-100
$ for i in {1..154}; do head -c $i pal.gs > tmp.gs; tail -c +$[i+2] pal.gs >> tmp.gs
> [ "$(echo -n 'r(a[c{"e"}c]a)r' | golfscript tmp.gs 2> /dev/null)" = "010" ] && echo $i
> done; rm tmp.gs
1
for i in {1..154}; do head -c $i pal.gs > tmp.gs; tail -c +$[i+2] pal.gs >> tmp.gs
>  [ "$(echo -n '42' | golfscript tmp.gs 2> /dev/null)" = "-100" ] && echo $i
> done | grep '^1$'; rm tmp.gs

```

### How it works

```
.             # Duplicate the input string.
4:ab-1:ba     # Save 4 in “ab” and -1 in “ba”.
=;            # Compare 4 to -1 and discard the result.
1%            # Save every element from the input string in a new string.
ab%           # Reverse the input string.
{             # For each character in the input string:
  ...         # Duplicate the character thrice.
  fi          # Variable “fi” is undefined; this does nothing.
  @@=         # Verify that the character is equal to itself; push 1.
  c43         # Variable “c43” is undefined; this does nothing.
  .=;         # Verify that 1 is equal to itself and discard the result.
  )(          # Increment and decrement the character.
  '"([{}])"'~ # Push that string and evaluate it. Result: '([{}])'
  ?           # Retrieve the character's position in '([{}])'. -1 means not found.
  ~           # Negate the position.. Examples: -1 -> 0    0 -> -1    2 -> -3
  '"([{}])"') # Push that string and pop its last element. Result: '"([{}])' 34
  (;          # Decrement 34 (the ASCII code of a double quote) and discard.
  =           # Retrieve the corresponding character.
  .34         # Duplicate the character and push 34.
  c           # Variable “c” is undefined; this does nothing.
  =           # If the character is a double quote, the index was -1.
  @@if        # In that case, replace the double quote with the original character.
  ...         # Duplicate the new character thrice.
}%            #
ab%           # Save every fourth element in a new string to discard dummy values.
1;            # Push 1 and discard.
=             # Push 1 if the modified string matches the original, 0 otherwise.
ab:1-         # Save 4 in “1” and subtract.
ba:4.         # Save -1 in “4” and duplicate.

```

```
0!*           # Pop and push the input string.
1{!}\;:);     # Make “)” an alias for “!”.
0:f;0:i;      # Variables.
-1:ab;9:ba;   # Moar variables.
...=;         # Duplicate the input string.
1%ab%         # Reverse the copy.
{             # For each character in the input string:
  ....        # Duplicate the character four times.
  i@          # Push 0 and rotate a string copy on top of it.
  f@@fi@@     # Push 0 and rotate 0 on top of it.
  =@          # Push 1 and rotate a string copy on top of it.
  .=@         # Push 1 and rotate 1 on top of it.
  \)+         # Negate a 1 and add. Result: 1
  ""          # Push that string.
  '"([{}])"'  # Push that string.
   ~+         # Evaluate the second string and concatenate. Result: '([{}])'
   ?          # Retrieve the characters position in '([{}])'. -1 means not found.
   +~         # Add 1 to the position and negate. Ex.: -1 -> -1 | 0 -> -2 | 1 -> -3
  '"([{}])"'  # Push that string.
  ""          # Push that string.
  +           # Concatenate. Result: '"([{}])"'
  (\          # Pop the first double quote and swap it with the rest of the string.
  @=.         # Retrieve the corresponding character and duplicate it.
  @=          # If the character is a double quote, the index was -1.
  @@if        # In that case, replace the double quote with the original character.
  @@          # Rotate the modified character to the bottom.
  f@i....     # Push dummy values.
  }%          #
  ba%         # Save every ninth element in a new string to discard dummy values.
  1;          # Push 1 and discard.
  =           # Push 1 if the modified string matches the original, 0 otherwise.
  ...;        # Duplicate thrice and discard the last copy.
  ab:9;ba:1-; # Variables.
  i:0;f:0;    # Moar variables.
  (:;\        # Negate, override “;” and swap.
  {!}1*!0     # Negate twice and push 0.

```
> 36 votes

# Answer
## Ruby, 110

```
(z=gets;r=z.tr *["([{}])",")]}{[("];p *z==r.reverse;1)||(1;esrever.r==z* p;[")]}{[(","([{}])"]* rt.z=r;steg=z)

```

Prints `true` if the input is a convenient palindrome and `false` if it isn't. Note that this solution assumes that the input isn't terminated by a newline, so test it with `echo -n`:

```
echo -n '(a)(bb)(a)' | ruby convpal.rb
true

echo -n '(a)(bb()a(' | ruby convpal.rb
false

# note that for this to work, the file must not contain a newline
# to remove a trailing newline, pipe it through tr -d $'\n'
cat convpal.rb | ruby convpal.rb
true

```

This is a somewhat straightforward port of my answer to Palindromic Palindrome Checker (and not really golfed so far). The main trick used is that the first parenthesised expression always returns `1`, so the second half of the boolean expression is never evaluated (but it is parsed).

The only difficulty in adapting this was figuring out how to add the call to `z.tr` so that its "convenient reverse" would also be syntactically valid - but I could simply use the same trick I already used puts: `*`, which in the first half is parsed as splat operator (use array contents as function parameters) and as array multiplication (or repitition) operator in the second half.

## Ruby, 157 ~~297~~, all code executed

```
w=tsoh=gets p
o=rt=esrever=Gem
q=tsoh.tr *["([{}])",")]}{[("]
q==esrever.host=w=tsoh.reverse==q
[")]}{[(","([{}])"]* rt.host=q
meG=reverse=tr=o
p steg=host=w

```

This (slightly longer) version executes *all* code, and all but two lines affect the output, which is printed in the last line - but all lines are parsed and executed without any errors. This version interprets any trailing newline as part of the input, so use either `echo -n` to test it, or prepend your input with a newline. It prints `true` if the input is a convenient palindrome, and `false` otherwise.

### Explanation

```
# Read the input by calling gets(nil), which is achieved by passing the return
# value of a call to Kernel#p (which returns nil if no argument is supplied) to
# gets.
w=tsoh=gets p
# Assign the global Gem module to three variables.
# The variable names are the reversed names of methods we have to call later.
# This doesn't necessarily have to be the Gem module, any global module/variable
# (or class that allows object creation through a call to the module itself,
# e.g. Hash or GC) with a writable property would do, but Gem#host was
# the shortest one I could find. This is necessary because Ruby doesn't
# allow setting previously undefined properties through the dot syntax.
o=rt=esrever=Gem
# Replace the parentheses with the corresponding flipped one.
# sserts is the reverse of the property name we're going to use later.
q=tsoh.tr *["([{}])",")]}{[("]
# Do the convinient palindrome check and assign its result to a few variables
# and Gem's host property.
q==esrever.host=w=tsoh.reverse==q
# Here, the * is parsed as array join operator.
[")]}{[(","([{}])"]* rt.host=q
# Nothing special here.
meG=reverse=tr=o
# Print the result of the palindrome check, which was stored in w.
p steg=host=w

```
> 13 votes

# Answer
# GolfScript, 61 chars

OK, here's a baseline solution in GolfScript. I'm sure it could be further improved:

```
{.-1%{"([{}])".2$?~@[.]@+=}%=}~{=%{=+@[.]@~?$2."([{}])"}%1-.}

```

As usual for GolfScript, this program reads its input from stdin. It outputs:

```
1{=%{=+@[.]@~?$2."([{}])"}%1-.}

```

if the input is a convenient palindrome, as defined in the challenge above, and:

```
0{=%{=+@[.]@~?$2."([{}])"}%1-.}

```

if it is not.

**Explanation:** This program relies heavily on the ruling that *unexecuted* code is OK, as long as it gets parsed. It consists of two code blocks, delimited by curly braces (`{ }`), which are mirror images of each other.

The first code block is executed by the `~` following it, and checks if the input is a convenient palindrome, outputting `1` if it is and `0` if it isn't. The second code block is *not* executed, and so simply remains on the stack until the program ends and everything on the stack gets automatically stringified and printed by the GolfScript interpreter.

It should be noted that the GolfScript interpreter does *very* few syntax checks at parse time (or ever, for that matter); a GolfScript code block literal can contain almost anything, even if it might crash when executed. Still, a few syntax errors, such as unterminated string literals, do raise an error even in unexecuted code, so I believe this solution (barely) falls within the rules.

**Ps.** Looking at the actual executed code, it contains a few conveniently palindromic elements like `@[.]@`, the string literal `"([{}])"`, and even the loop `%{ ... }%`. This offers the tantalizing suggestion that an "intrinsically palindromic" GolfScript solution, where the full palindromic program would be executed and functional, might actually be possible. As I haven't managed to produce one myself yet, I hereby offer a **+100 rep bounty** to the first person who manages to come up with one!
> 10 votes

# Answer
# JavaScript (ES6), 245 bytes

I wanted a JS answer that could be run in the browser, so here it is.

```
eurt=>eurt==(("",eurt))["split"||"nioj"]("")["map"||"esrever"](x=>({'{':'}','}':'{','[':']',']':'[','(':')',')':'('})[x]||x||[x]({')':'(','(':')',']':'[','[':']','}':'{','{':'}'})>=x)["reverse"||"pam"]("")["join"||"tilps"]((true,""))==true>=true

```

Removing all code that is never actually run, we get this:

```
eurt=>eurt==(("",eurt))["split"||"nioj"]("")["map"||"esrever"](x=>({'{':'}','}':'{','[':']',']':'[','(':')',')':'('})[x]||x||[x]({')':'(','(':')',']':'[','[':']','}':'{','{':'}'})>=x)["reverse"||"pam"]("")["join"||"tilps"]((true,""))==true>=true
eurt=>eurt==(("",eurt))["split"        ]("")["map"           ](x=>({'{':'}','}':'{','[':']',']':'[','(':')',')':'('})[x]||x                                                           )["reverse"       ]("")["join"         ]((true,""))==true>=true

```

Which can be simplified to this:

```
eurt=>eurt==eurt.split("").map(x=>({'{':'}','}':'{','[':']',']':'[','(':')',')':'('})[x]||x).reverse("").join("")

```
> 4 votes

# Answer
# Javascript (ES6) 288

Runs in the Spidermonkey command line shell. Reads a single line from STDIN and outputs `true` or `false` depending on if the input is a convenient palindrome.

```
((print)((eval)('r=readline()')==([0]['map']['call'](r,x=>({'{':'}','}':'{','[':']',']':'[','(':')',')':'('})[x]||x)['reverse']()['join']('')))&&((('')['nioj']()['esrever'](x||[x]({')':'(','(':')',']':'[','[':']','}':'{','{':'}'})>=x,r)['llac']['pam'][0])==('()enildaer=r')(lave))(tnirp))

```

This code is syntactically valid, but everything after `&&` is not executed, as the `print` function returns a falsey value.

You can run this code in Firefox's console by running this shim first to emulate the `readline` and `print` functions. Edit the input inside `readline` as needed:

```
readline = function(){
    return "void main(int argc, *char[] argv) {} (vgra []rahc* ,cgra tni)niam diov";
}, print = console.log.bind(console);

```

And here's a quick example of the output:
> 3 votes

# Answer
# 05AB1E, 35 bytes

```
"{[()]}"DRr‡`rJ¹Q,Q¹Jr`‡rRD"{[()]}"

```

Try it online!

Explanation:

```
                     # Implicit input
 "{[()]}"            # Push "{[()]}" onto the stack
         DR          # Pushes a reversed copy onto the stack
           r         # Reverse the order of the stack
            ‡        # Transliterate
             `       # Flatten array on stack
              r      # Reverse order of stack
               J     # Join stack
                ¹Q   # Check equality with first input
                  ,  # Print
                     # Everything after is still syntactically correct, but just does not print anything.

```
> 2 votes

# Answer
# CJam, 38 bytes

```
Q~"=re%W_@%W_q"`{[()]}`"q_W%@_W%er="~Q

```

Prints `"=re%W_@%W_q"1` if the input is conveniently palindromic and `"=re%W_@%W_q"0` otherwise.

Try it online in the CJam interpreter.

### How it works

```
Q~                                     e# Evaluate an empty string.
  "=re%W_@%W_q"                        e# Push that string.
               `                       e# Inspect. Pushes "\"=re%W_@%W_q\"".
                {[()]}                 e# Push that block.
                      `                e# Inspect. Pushes "{[()]}".
                       "           "~  e# Push and evaluate.
                        q              e# Read from STDIN.
                         _W%           e# Push a reversed copy.
                            @          e# Rotate "{[()]}" on top of the stack.
                             _W%       e# Push a reversed copy.
                                er     e# Perform transliteration.
                                  =    e# Compare to the input string.
                                     Q e# Push an empty string.

```

After executing the program, CJam automatically prints all three items on the stack: the inspected string, the Boolean from the string comparison and the empty string.
> 1 votes

# Answer
# Perl, 83 + 2 = 85 bytes

Run with `-nl`

```
say$_~~reverse y-"({[]})"-")}][{("-r;exit;tixe;r-")}][{("-"({[]})"-y esrever~~_$yas

```

The code exits after printing the truthiness of the input. Everything after the semicolon is interpreted (and would crash when the script reaches that point were it not for the `exit` it encounters), but not executed. If I left `exit;tixe;` out of the code, it would still print the result correctly before it crashed.
> 0 votes

---
Tags: code-golf, restricted-source, palindrome, balanced-string, decision-problem
---


title: Pi Calculation Code Golf

text:
# Question
Title: Pi Calculation Code Golf
## **The Challenge**

You must calculate pi in the shortest length you can. Any language is welcome to join and you can use any formula to calculate pi. It must be able to calculate pi to at least 5 decimal places. Shortest, would be measured in characters. Competition lasts for 48 hours. Begin.

---

**Note**: This similar question states that PI must be calculated using the series 4 * (1 – 1/3 + 1/5 – 1/7 + …). This question does **not** have this restriction, and in fact a lot of answers here (including the most likely to win) would be invalid in that other question. So, this is not a duplicate.

# Answer
## Python3, 7

Runs in the interactive shell

```
355/113

```

Output: `3.1415929203539825`, correct to 6 decimal places

And finally I have a solution that beats APL!

Oh, and in case you are wondering, this ratio is called the 密率 (literally "precise ratio"), and is proposed by the Chinese mathematician Zu Chongzhi (429-500 AD). A related wikipedia article can be found here. Zu also gave the ratio 22/7 as the "rough ratio", and he is known to be the first mathematician to propose that 3.1415926 \<= pi \<=3.1415927
> 58 votes

# Answer
# PHP — ~~132~~ ~~127~~ ~~125~~ 124 bytes

Basic Monte-Carlo simulation. Every 10M iterations, it prints the current status:

```
for($i=1,$j=$k=0;;$i++){$x=mt_rand(0,1e7)/1e7;$y=mt_rand(0,1e7)/1e7;$j+=$x*$x+$y*$y<=1;$k++;if(!($i%1e7))echo 4*$j/$k."\n";}

```

Thanks to cloudfeet and zamnuts for suggestions!

Sample output:

```
$ php pi.php
3.1410564
3.1414008
3.1413388
3.1412641
3.14132568
3.1413496666667
3.1414522857143
3.1414817
3.1415271111111
3.14155092
...
3.1415901754386
3.1415890482759
3.1415925423731

```
> 50 votes

# Answer
## J 6

```
{:*._1

```

Explanation: `*.` gives length and angle of a complex number. The angle of -1 is pi. `{:` takes the tail of the list \[length, angle\]

Just for the slowly-converging-series-fettishists, for 21 bytes, a Leibniz series:

```
      +/(4*_1&^%>:@+:)i.1e6
 3.14159

```
> 32 votes

# Answer
## Perl, 42 bytes

```
map{$a+=(-1)**$_/(2*$_+1)}0..9x6;print$a*4

```

It's calculates π using the Leibniz formula:

999999 is used as largest *n* to get the precision of five decimal digits.

Result: `**3.14159**165358977`
> 25 votes

# Answer
# TECHNICALLY I'M CALCULATING, 9

```
0+3.14159

```

# TECHNICALLY I'M STILL CALCULATING, 10

```
PI-acos(1)

```

# I'M CALCULATING SO HARD, 8

```
acos(-1)

```

# I ACCIDENTALLY PI, 12

```
"3.14"+"159"

```

And technically, this answer stinks.
> 20 votes

# Answer
## Piet, many codels

Not my answer, but this is the best solution I've seen to this problem:

My understanding is that it adds up the pixels in the circle and divides by the radius, and then once again. That is:

```
A = πr²  # solve for π
π = A/r²
π = (A/r)/r

```

A better approach in my mind is a program that generates this image at an arbitrary size and then runs it through a Piet interpreter.

Source: http://www.dangermouse.net/esoteric/piet/samples.html
> 19 votes

# Answer
# APL - 6

```
2×¯1○1

```

Outputs `3.141592654`. It computes twice the arcsine of 1.

A 13-char solution would be:

```
--/4÷1-2×⍳1e6

```

This outputs `3.141591654` for me, which fits the requested precision.
It uses the simple `+ 4/1 - 4/3 + 4/5 - 4/7 ...` series to calculate though.
> 14 votes

# Answer
# J - 5 bytes

```
|^._1

```

This means `|log(-1)|`.
> 14 votes

# Answer
# Octave, 31

```
quad(inline("sqrt(4-x^2)"),0,2)

```

Calculates the area of one quarter of a circle with radius 2, through numerical integration.

```
octave:1> quad(inline("sqrt(4-x^2)"),0,2)
ans =     3.14159265358979

```
> 12 votes

# Answer
# Mathematica 6

```
180N@°
-->3.14159

```
> 11 votes

# Answer
# Python, 88

Solution :

```
l=q=d=0;t,s,n,r=3.,3,1,24
while s!=l:l,n,q,d,r=s,n+q,q+8,d+r,r+32;t=(t*n)/d;s+=t
print s

```

Sample output in Python shell :

```
>>> print s
3.14159265359

```

Manages to avoid any imports. Can easily be swapped to use the arbitrary precision Decimal library; just replace `3.` with `Decimal('3')`, set the precision before and after, then unary plus the result to convert precision.

And unlike a whole lot of the answers here, actually *computes* π instead of relying on built-in constants or math fakery, i.e. `math.acos(-1)`, `math.radians(180)`, etc.
> 11 votes

# Answer
### x86 assembly language (5 characters)

```
fldpi

```

Whether this loads a constant from ROM or actually calculates the answer depends on the processor though (but on at least some, it actually does a calculation, not just loading the number from ROM). To put things in perspective, it's listed as taking 40 clock cycles on a 387, which is rather more than seems to make sense if it were just loading the value from ROM.

If you really want to ensure a calculation you could do something like:

```
fld1
fld1
fpatan
fimul f

f dd 4

```

\[for 27 characters\]
> 9 votes

# Answer
# bc -l, 37 bytes

```
for(p=n=2;n<7^7;n+=2)p*=n*n/(n*n-1);p

```

I don't see any other answers using the Wallis product, so since its named after my namesake (my *History of Mathematics* lecturer got a big kick out of that), I couldn't resist.

Turns out its a fairly nice algorithm from the golfing perspective, but its rate of convergence is abysmal - approaching 1 million iterations just to get 5 decimal places:

```
$ time bc -l<<<'for(p=n=2;n<7^7;n+=2)p*=n*n/(n*n-1);p'
3.14159074622629555058

real    0m3.145s
user    0m1.548s
sys 0m0.000s
$

```

---

# bc -l, 15 bytes

Alternatively, we can use Newton-Raphson to solve `sin(x)=0`, with a starting approximation of 3. Because this converges in so few iterations, we simply hard-code 2 iterations, which gives 10 decimal places:

```
x=3+s(3);x+s(x)

```

The iterative formula according to Newton-Raphson is:

```
x[n+1] = x[n] - ( sin(x[n]) / sin'(x[n]) )

```

`sin'` === `cos` and `cos(pi)` === `-1`, so we simply approximate the `cos` term to get:

```
x[n+1] = x[n] + sin(x[n])

```

Output:

```
$ bc -l<<<'x=3+s(3);x+s(x)'
3.14159265357219555873
$

```
> 8 votes

# Answer
## Perl - 35 bytes

```
$\=$\/(2*$_-1)*$_+2for-46..-1;print

```

Produces full floating point precision. A derivation of the formula used can be seen elsewhere.

Sample usage:

```
$ perl pi.pl
3.14159265358979

```

---

**Arbitrary Precision Version**

```
use bignum a,99;$\=$\/(2*$_-1)*$_+2for-329..-1;print

```

Extend as needed. The length of the iteration (e.g. `-329..-1`) should be adjusted to be approximately *log2(10)**3.322* times the number of digits.

```
3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211707

```

Or, using `bigint` instead:

```
use bigint;$\=$\/(2*$_-1)*$_+2e99for-329..-1;print

```

This runs noticably faster, but doesn't include a decimal point.

```
3141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067

```
> 6 votes

# Answer
# Javascript, 43 36

```
x=0;for(i=1;i<1e6;i++){x+=1/i/i};Math.sqrt(6*x)

```

`x` becomes `zeta(2)=pi^2/6` so `sqrt(6*x)=pi`. (47 characters)

After using the distributive property and deleting the curly brackets from the `for` loop you get:

```
x=0;for(i=1;i<1e6;i++)x+=6/i/i;Math.sqrt(x)

```

(43 characters)

It returns:

```
3.14159169865946

```

Edit:

I found an even shorter way using the Wallis product:

```
x=i=2;for(;i<1e6;i+=2)x*=i*i/(i*i-1)

```

(36 characters)

It returns:

```
3.141591082792245

```
> 6 votes

# Answer
# python - ~~47~~ 45

pi is actually being calculated without trig functions or constants.

```
a=4
for i in range(9**6):a-=(-1)**i*4/(2*i+3)

```

result:

```
>>> a
3.1415907719167966

```
> 6 votes

# Answer
# C, 99

Directly computes area / r^2 of a circle.

```
double p(n,x,y,r){r=10000;for(n=x=0;x<r;++x)for(y=1;y<r;++y)n+=x*x+y*y<=r*r;return(double)n*4/r/r;}

```

This function will calculate pi by counting the number of pixels in a circle of radius `r` then dividing by `r*r` (actually it just calculates one quadrant). With `r` as 10000, it is accurate to 5 decimal places (3.1415904800). The parameters to the function are ignored, I just declared them there to save space.
> 6 votes

# Answer
## Python, Riemann zeta (~~58~~ 41 char)

```
(6*sum(n**-2for n in range(1,9**9)))**0.5

```

Or spare two characters, but use scipy

```
import scipy.special as s
(6*s.zeta(2,1))**0.5

```

**Edit**: Saved 16 (!) characters thanks to amcgregor
> 6 votes

# Answer
## TI CAS, 35

```
lim(x*(1/(tan((180-360/x)/2))),x,∞)

```
> 5 votes

# Answer
## Javascript: 99 characters

Using the formula given by Simon Plouffe in 1996, this works with 6 digits of precision after the decimal point:

```
function f(k){return k<2?1:f(k-1)*k}for(y=-3,n=1;n<91;n++)y+=n*(2<<(n-1))*f(n)*f(n)/f(2*n);alert(y)

```

This longer variant (130 characters) has a better precision, 15 digits after the decimal point:

```
function e(x){return x<1?1:2*e(x-1)}function f(k){return k<2?1:f(k-1)*k}for(y=-3,n=1;n<91;n++)y+=n*e(n)*f(n)*f(n)/f(2*n);alert(y)

```

I made this based in my two answers to this question.
> 5 votes

# Answer
### Ruby, ~~54~~ ~~50~~ 49

```
p (0..9**6).map{|e|(-1.0)**e/(2*e+1)*4}.reduce :+

```

Online Version for testing.

Another version without creating an array (50 chars):

```
x=0;(0..9**6).each{|e|x+=(-1.0)**e/(2*e+1)*4}; p x

```

Online Version for testing.
> 5 votes

# Answer
## Game Maker Language, 34

Assumes all uninitialized variables as 0. This is default in some versions of Game Maker.

```
for(i=1;i<1e8;i++)x+=6/i/i;sqrt(x)

```

Result:

```
3.14159169865946

```
> 5 votes

# Answer
**C# 192**

```
class P{static void Main(){var s=(new System.Net.WebClient()).DownloadString("http://www.ctan.org/pkg/tex");System.Console.WriteLine(s.Substring(s.IndexOf("Version")+21).Split(' ')[0]);}}

```

Outputs:

```
3.14159265

```

No math involved. Just looks up the current version of TeX and does some primitive parsing of the resulting html. Eventually it will become π according to Wikipedia.
> 5 votes

# Answer
## Python 3 Monte Carlo (103 char)

```
from random import random as r
sum(1 for x,y in ((r(),r()) for i in range(2**99)) if x**2+y**2<1)/2**97

```
> 5 votes

# Answer
**Java - ~~83~~ 55**

Shorter version thanks to Navin.

```
class P{static{System.out.print(Math.toRadians(180));}}

```

Old version:

```
class P{public static void main(String[]a){System.out.print(Math.toRadians(180));}}

```
> 4 votes

# Answer
## **R**: 33 characters

```
sqrt(8*sum(1/seq(1,1000001,2)^2))
[1] 3.141592

```

Hopefully this follows the rules.
> 4 votes

# Answer
# Ruby, 12

```
p 1.570796*2

```

I *am* technically "calculating" ~~pi~~ an approximation of pi.
> 3 votes

# Answer
# Ruby, 82

```
q=1.0
i=0
(0.0..72).step(8){|k|i+=1/q*(4/(k+1)-2/(k+4)-1/(k+5)-1/(k+6))
q*=16}
p i

```

Uses some formula I don't really understand and just copied down. :P

Output: `3.1415926535897913`
> 3 votes

# Answer
## JavaScript - 19 bytes

```
Math.pow(29809,1/9)

```

Calculates the *9*th root of *29809*.

```
3.1415914903890925

```
> 3 votes

# Answer
**53 characters of Javascript:**

`x=3;d=1;while(d>1e-8){d=Math.sin(x);x+=d;};alert(x);`

With an arbitrary numeric precision implementation of sin (e.g. taylor expansion), this will give an arbitrarily exact result with good convergence and a roughly estimated precision while keeping the code very simple.
> 3 votes

# Answer
## R

A few years back I was taking a math course and the instructor asked the class how we might compute pi from scratch. A guy at the back of the class suggested drawing a circle of diameter 1 and then laying a piece of string around it.

I couldn't figure out how to do that in R. I decided the second most primitive approach would be to approximate the circle with a regular polygons. A 4096-gon gets us 5 digits. The polygons are approximated with a simple binary search using only the midpoint and distance formulae (i.e. no trigonometric functions are used).

```
a <- c(0,1); b <- c(0,0); c <-c(1,0)
eps <- 0.000000001
mid  <- function(a,b) { c(mean(c(a[1],b[1])), mean(c(a[2],b[2])))}
dist <- function(a,b) { sqrt((a[1]-b[1])^2 + (a[2]-b[2])^2)}
for (i in 1:10)
{
    ab1 <- mid(a,b)
    ab2 <- mid(b, ab1)
    bc1 <- mid(b,c)
    bc2 <- mid(b, bc1)
    repeat
    {
        newab <- mid(ab1,ab2)
        newbc <- mid(bc1, bc2)
        corner <- dist(newab,newbc)
        side   <- dist(a,b) - 2*dist(newab,b)
        dif <- side - corner
        if (abs(dif) < eps)
        {
            a <- c(0,newab[2]+dist(newab,newbc))
            b <- newab
            c <- newbc
            break
        }
        if (dif > 0){ab2 <- newab;bc2 <- newbc}
        if (dif < 0){ab1 <- newab;bc1 <- newbc}
    }
}
print((2^(i+2))*dist(newab,newbc))

```
> 3 votes

# Answer
# Python, 37 chars

Using zeta(10) for fast convergence:

```
    sum(93555./i**10 for i in[1,2,3])**.1
    3.1415923154068

```

Using the same serie to get 15 correct digits:

```
    sum(93555./i**10 for i in range(1,40))**.1
    3.141592653589793

```
> 3 votes

# Answer
# bc -l, 6

```
4*a(1)

```

This requires the -l option to `bc`. Do I need to declare extra points for that?

Using -l calculates to 20 decimal places:

```
$ bc -l<<<"4*a(1)"
3.14159265358979323844
$

```
> 2 votes

# Answer
# TI CAS , 4

Assuming you're in radians mode,

```
180°

```

If you really insist, to put it into radians mode:

```
Radians:180°

```

(suggested by AJMansfield)

(similar to the Mathematica answer)
> 2 votes

# Answer
***AppleScript*****, 8 characters**

Solution :

```
3+.14159

```

Result :

```
3.14159

```
> 2 votes

# Answer
# Python - 68 characters

Quite a long solution.

```
_=lambda x,y=1:x^y and y*2-1+y**2/_(x,y+1)or x*2.0+1
print 4/_(99)

```
> 2 votes

# Answer
# Groovy, 77

```
def x=0;for(k in 0..99){x+=Math.pow(-1/3,k)/(2*k+1)};println x*Math.sqrt(12)

```

This uses the Madhava-Leibniz series, which converges more quickly than the plain Leibniz series:

Output:

3.141592653616969
> 2 votes

# Answer
***AppleScript*****, 4 characters !**

Solution :

```
pi+0

```

Displayed result :

```
3.14159265359

```
> 1 votes

# Answer
## Windows Calculator - cheat: 1, less cheating: 5

`p` (not my final answer, but I just had to include this for lulz)

or

~~`F₁` `1` `i` `t` `*` `4`~~
`F₄` `1` `F₉` `i` `o`

(F₄ sets mode to radians, F₉ negates the buffer)

If it must be a pasteable/savable string, and mode is already set to radians and the buffer is 0.0: `io*2=`
> 1 votes

# Answer
# TI BASIC, 24

```
Disp fnInt(√(4-X²),X,0,2

```

returns:

```
3.141593074
Done

```

This does not use any trig function, instead it uses numerical integration of the function of half a circle with radius 2. That circle has area 4pi, so half that circle has area 2pi, but i integrate from 0 to 2 wich is half of that, so a quarter of the circle, area pi.
> 1 votes

# Answer
## Groovy: 25

```
print Math.log(10691/462)

```

Output is 3.141592653932079

de Jerphanion approximation
> 1 votes

# Answer
# APL : 2 chars

```
    ○1
3.141592653589793

```

Reference for monadic circle: http://www.microapl.co.uk/apl\_help/ch\_020\_020\_230.htm
> 1 votes

# Answer
# JavaScript 50 (30 decimal places, including alert call...)

```
alert((m=Math).log(pow(640320,3)+744)/pow(163,.5))
....5....0....5....0....5....0....5....0....5....0

```

Based on the entry under *Miscellaneous Approximations* section in wikipedia: http://en.wikipedia.org/wiki/Approximations\_of\_%CF%80

Or for less accurate...

# JavaScript 40 (10 decimal places, including alert call)

```
alert(Math.pow(1e100/11222.11122,1/193))
....5....0....5....0....5....0....5....0

```

Output:

```
3.1415926536438223
...........^ Accuracy finishes after this digit!)

```

Or for even less accurate...

# JavaScript 28 (8 decimal places, including alert call!)

```
alert(Math.pow(2143/22,.25))
....5....0....5....0....5..8

```

Output:

```
3.1415926525826463
.........^ Accuracy finishes after this digit!)

```
> 1 votes

# Answer
# Julia

Hiperarmonic series:

```
julia> s=0;sqrt(6*([s+=1/i^2 for i=1:8^6][end]))
3.1415890108270967

```

Zeta function:

```
julia> sqrt(zeta(2)*6)
3.141592653589793

```

Bailey-Borwein-Plouffe formula:

```
julia> s=0;[s+=(-1)^k/4^k*(2/(4k+1)+2/(4k+2)+1/(4k+3)) for k=0:7]
8-element Array{Any,1}:
 3.33333
 3.11429
 3.14636
 3.14068
 3.14178
 3.14155
 3.1416
 3.14159

```

Ramanujan formula (fastest convergence):

```
julia> !n=factorial(n);s=0;([s+=!4n*(1103+26390n)/(!n*396^n)^4 for n=0][end]*(sqrt(8)/9801))^-1
3.1415927300133055

```
> 1 votes

# Answer
## Javascript 44

I am new to golfing, so this is my best shot:

```
p=0;for(i=1;i<1e7;i+=4)p+=8/i/(i+2);alert(p)

```
> 1 votes

# Answer
# Smalltalk, 9

```
1arcSin*2

```

will do
> 0 votes

# Answer
## Python : 8 bytes

```
acos(-1)

```

do i have to include imports??
> 0 votes

# Answer
# q \[7 chars\]

```
acos -1

```

### Example

```
acos -1
3.141593

355%113       // [7 Chars]
3.141593

2*asin 1      // [8 Chars]
3.141593

```
> 0 votes

# Answer
## Ruby, 35

Using Euler's formula. No reliance on trigonometric functions that might store π somewhere (though CMath might use Math::PI internally...).

```
require('cmath');CMath.log(-1).imag

```

Returns

```
3.141592653589793

```
> 0 votes

# Answer
## Java: 89

```
class j{public static void main(String[]a){System.out.print(4-Math.pow(105./166,1./3));}}

```

unGolfed:

```
class j {
    public static void main(String a[]){
        //E. Pegg approximation
        System.out.print(4-Math.pow(105./166,1./3));
    }
}

```
> 0 votes

# Answer
**Python, 27**

```
import math
math.atan(1)*4

```
> 0 votes

# Answer
This was originally a comment to this answer, but since the full program is shorter than the other C solution (which is only a function), I might as well post it as an answer:

# C, 64

```
double x,i;main(){for(;i++<1e8;)x+=6/i/i;printf("%f",sqrt(x));}

```

output:

```
3.141593

```
> 0 votes

# Answer
# C

```
main(){printf("%f",22/7.0);}

```
> 0 votes

# Answer
### bc -l, 9 chars

```
2*a(2^99)

```

Even with bc(1)'s default `scale` this is correct up to as many digits as I memorised. Raise the potence (and the `scale`) to get more precisions.
> 0 votes

# Answer
## PHP, 281

*Not going to win, but more of a challenge for myself.*

Calculates PI to the nth precision (determined by the value of `$d`, currently 5). This is a PHP implementation of the Gauss–Legendre algorithm. I discovered after the fact this was almost exactly done by someone 7 years ago... \*smh\* ...posting anyway.

Golfed:

```
$d=5;$r=$d+4;$n=floor(log($r)/log(2));bcscale($r);$a=1;$b=bcdiv(1,bcsqrt(2));$t=.25;$p=1;while($n--){$x=bcdiv(bcadd($a,$b),2);$y=bcsqrt(bcmul($a,$b));$t=bcsub($t,bcmul($p,bcsub(bcpow($x,2),bcpow($y,2))));$p=bcmul(2,$p);$a=$x;$b=$y;}echo bcdiv(bcpow(bcadd($a,$b),2),bcmul(4,$t),$d);

```

`$d = 5` outputs `3.14159`

`$d = 19` outputs `3.1415926535897932384`

`$d = 41` outputs `3.14159265358979323846264338327950288419716`

etc...

---

*Community Help:* I would like to set the scale/precision more appropriately on each iteration (rather than fixed at 4: `$r=$d+4`), but I can't seem to find a way to reliably determine the error precision, i.e. the rate of convergence isn't constant.
> 0 votes

# Answer
# Windows Calculator, 1 click

Inspired by This Answer
> 0 votes

# Answer
# Java 8, 155

```
class P{public static void main(String[] s){System.out.print(4*java.util.stream.IntStream.range(0,999999).mapToDouble(x->Math.pow(-1,x)/(2*x+1)).sum());}}

```

Uses the same approach as @HeikoOberdiek's Perl solution i.e., the Leibniz formula.

Here's the same program in a longer form, formatted for easier reading:

```
import static java.lang.Math.pow;
import static java.util.stream.IntStream.range;

public class Pie {
    public static void main(String[] args) {
        System.out.println(4 * range(0, 999_999).mapToDouble(x -> pow(-1, x) / (2*x + 1)).sum());
    }
}

```

Output:

`3.1415936535907933`
> 0 votes

# Answer
# JavaScript, 94 characters

```
+function p(n){return~n?(4/(8*n+1)-1/(4*n+2)-1/(8*n+5)-1/(8*n+6))/Math.pow(16,n)+p(n-1):0}(9)

```
> 0 votes

# Answer
## R, Monte Carlo 68

Old square inscribed in circle method.

```
z=n=0;repeat{z=z+ifelse(sum(runif(2)^2)<1,1,0);n=n+1;write(4*z/n,1)}

```

Check if x^2 + y^2 \<= r^2, if yes z += z, else n += n. Pi ~= 4z/n as iteration -\> inf.
> 0 votes

# Answer
## C++ 26

```
main(){cout<<6*asin(0.5);}

```
> 0 votes

# Answer
# Python 3.x - 123

Sadly this has very little precision... giving only 1-2 decimal places correct.

Anyway this is a fun method of calculating pi.

```
import random
R = lambda: random.uniform(-1,1)
print(sum(1 for _ in range(10**6) if abs(R() + R()*1j) < 1)*4/10**6)

```
> 0 votes

# Answer
# Ruby 8

```
-0.0.arg

```

Output takes 2 more chars:

```
p -0.0.arg  # => 3.141592653589793

```
> 0 votes

# Answer
# Python 3, 91 (with display), 82 (just calculation)

This knows that Pi is 3, then it uses the Nilakantha method to calculate Pi accurately to 6 decimal places.

```
p,n,s=3,2,1
while s<99:
 n,s,z=n+2,s+1,4/(n*(n+1)*(n+2))
 if s%2<1:p+=z
 else:p-=z
print(p)

```

It starts with the humorous `3,2,1`, but also with the rather distasteful `p,n,s`...

### Output

`3.141592 395970107`
The space is to separate the correct output from the incorrect.
> 0 votes

# Answer
# Java, 55

```
class P{static{System.out.print(Math.toRadians(180));}}

```

Hooray for static blocks ^\_^
> -1 votes

# Answer
***bc*****, 8 characters**

Solution :

```
3+.14159

```

Usage :

```
$ bc <<< "3+.14159"
3.14159
$

```
> -1 votes

# Answer
## Python, 27 chars

```
print "%.5f"%(355.0/113.0)

```
> -1 votes

# Answer
Matlab or Octave

```
0+pi

```

So short stackexchange won't let me post it without this. The output:

```
octave:5> 0+pi
ans =  3.14159265358979

```
> -2 votes

---
Tags: code-golf, pi, approximation
---


# Question
Title: The Government has a Limited Supply of Walls
**Introduction**

Knowledgeable code golfers prepared us for the doomsday flood. Areas at risk were evacuated, and the population moved to high ground.

We underestimated the flood (or perhaps there was a bug in @user12345's code). Some high-ground areas are rapidly approaching sea level. Walls must be erected in order to ensure the survival of the now densely populated encampments. Sadly, the government has a limited supply of walls.

**Problem**

Our doomsday scenario is described by two numbers on a single line, `n` and `m`. Following that line are `n` lines with `m` values per line, separated only by a single space. Each value will be one of four characters.

* `x` Impassable. Water cannot flow here. Walls cannot be erected here.
* `-` Unstable. Water can flow through this here. Walls cannot be erected here.
* `.` Stable. Water can flow through here. Walls can be erected here.
* `o` Encampment. Water can flow through here. If it does, everyone dies. Walls cannot be built here.

Water will flow from all edges of the map, unless the edge is impassable or a wall is constructed on the tile. Write a program that can output the minimum number of walls required to protect an encampment.

**Example Input**

```
 6 7
 x . . x x x x
 x . . x - - x
 x . x x - - x
 x . o o o - .
 x . o o o - .
 x x x x x x x

```

**Example Output**

```
3

```

**Assumptions**

* Water only flows orthogonally
* Encampments only exist as one orthonagonally contiguous block per scenario
* A solution will always exist (although it may require copious amounts of walls)
* Encampments cannot be located on an edge, as the scenario would then have no solution
* 2 \< `n` \< 16
* 2 \< `m` \< 16
* Input may be provided from stdin, read from "city.txt", or accepted as a single argument

Shortest code wins!

# Answer
> 10 votes
# Mathematica, ~~257~~ 253 chars

```
d="city.txt"~Import~"Table";g=EdgeAdd[#,∞<->Tr@#&/@Position[VertexDegree@#,2|3]]&@GridGraph@d[[1,{2,1}]];{o,x,s}=Tr/@Position[Join@@d[[2;;]],#]&/@{"o","x","."};Catch@Do[If[Min[GraphDistance[VertexDelete[g,x⋃w],∞,#]&/@o]==∞,Throw@Length@w],{w,Subsets@s}]

```

Input is read from `"city.txt"`.

### Explanation:

Mathematica has many functions to deal with graphs.

First, I read the data from `"city.txt"`.

```
d="city.txt"~Import~"Table";

```

Then I construct a grid graph with 'm'\*'n' vertices (`GridGraph@d[[1,{2,1}]]`), and add to it a "vertex at infinity" which is connected to every vertex on the "edges" of the graph. This vertex is where the water flow from.

```
g=EdgeAdd[#,∞<->Tr@#&/@Position[VertexDegree@#,2|3]]&@GridGraph@d[[1,{2,1}]];

```

And `o`, `x` and `s` denote the positions of "o", "x" and "." respectively.

```
{o,x,s}=Tr/@Position[Join@@d[[2;;]],#]&/@{"o","x","."};

```

Then for any subset `w` of `s` (the subsets are sorted by length), I delete the vertices in `x` and `w` from `g` (`VertexDelete[g,x⋃w]`), and find the length of the shortest path from the "vertex at infinity" to the encampment `o`. If the length is infinity, then the encampment will be safe. So the length of the first such `w` is the minimum number of walls required to protect an encampment.

```
Catch@Do[If[Min[GraphDistance[VertexDelete[g,x⋃w],∞,#]&/@o]==∞,Throw@Length@w],{w,Subsets@s}]

```

# Answer
> 4 votes
# Python, ~~553~~ ~~525~~ ~~512~~ ~~449~~ ~~414~~ ~~404~~ ~~387~~ 368 characters (+4? for invocation)

I had way too much fun golfing this. It's 82 bytes bigger if you try to compress it! Now that's a measure of compactness and lack of repetition.

```
R=range;import itertools as I
f=map(str.split,open('city.txt'))[1:]
S=[]
def D(q):
 q=set(q)
 def C(*a):
    r,c=a
    try:p=(f[r][c],'x')[a in q]
    except:p='x'
    q.add(a)
    if'.'==p:S[:0]=[a]
    return p<'/'and C(r+1,c)|C(r-1,c)|C(r,c+1)|C(r,c-1)or'o'==p
 if sum(C(j,0)|C(j,-1)|C(0,j)|C(-1,j)for j in R(16))<1:print n;B
D(S);Z=S[:]
for n in R(len(Z)):map(D,I.combinations(Z,n))

```

Indentation levels are space, tab.

**Usage**:

Reads from `city.txt`:

```
6 7
x . . x x x x
x . . x - - x
x . x x - - x
x . o o o - .
x . o o o - .
x x x x x x x

```

Invoke as follows:

```
$ python floodfill_golf.py 2>X
3

```

The `2>X` is to hide stderr since program exits by raising an exception. If this is considered unfair feel free to add 4 characters for the invocation.

**Explanation**:

Simple brute force. `C` does a flood-fill and returns true if it hit an encampment. No extra padding since it took too much space to set the padding up properly. `D`, given a set of walls to fill in, calls `C` from every point on the edge such that `C` accounts for those walls, and prints length and exits if none of them reached the encampment. The list of walls is also used to keep track of the flood-fill, so no copying of the board is required! Trickily, `C` also appends any empty spots it finds to a list, `S`, so the function `D` is *also* used to first construct the list of empty spots. For this reason, I use `sum` instead of `any`, to ensure all the `.`s are collected on the first run-through.

I invoke `D` once, then copy the list of empty spots into `Z` since `S` will keep being appended to (inefficient, but cheaper on character count). Then I use `itertools.combinations` to select each combo of empty spots, from 0 spots up. I run each combo through `D` and it prints the length of the first one that works, raising an exception to exit the program. If no answer is found then nothing is printed.

Note that currently, the program doesn't work if no walls are needed. It'd be +3 characters to take care of this case; not sure if it's necessary.

Also note that this is an `O(2^n)` algorithm, where `n` is the number of empty spots. So, for a 15x15 completely empty board with one encampment in the middle, this will take `2^(15*15-1)` = `2.6959947e+67` iterations to complete, which is going to be a very long time indeed!

# Answer
> 4 votes
## C, ~~827 799~~ 522

**Golfed:**

```
#define N for(
#define F(W,X,Y,Z) N i= W;i X Y;i Z)
#define C(A,B,C) if(c[A][B]==C)
#define S(W,X,Y,Z,A,B) p=1;F(W,X,Y,Z)C(A,B,120)p=0;if(p){F(W,X,Y,Z){C(A,B,46){c[A][B]='x';z++;Q();break;}}}else{F(W,X,Y,Z){C(A,B,120)break;else c[A][B]='o';}}
p,m,z,w,h,o,i,u,l,x,y;char c[16][16];Q(){N u=0;u<h;u++)N l=0;l<w;l++)if(c[u][l]=='o'){x=u;y=l;S(x,>,m,--,i,y)S(y,>,m,--,x,i)S(y,<,w,++,x,i)S(x,<,h,++,i,y)}}main(int a, char **v){h=atoi(v[1]);w=atoi(v[2]);N m=-1;o<h;o++)N i=0;i<w;i++)scanf("%c",&c[o][i]);Q();printf("%d",z);}

```

Input is given with the height and with as command line arguments, and then the grid is read as a single string on stdin like so: `./a.out 6 7 < input` where input is in this form (left to right, top to bottom):

> x..xxxxx..x--xx.xx--xx.ooo-.x.ooo-.xxxxxxx

**"Readable":**

```
#define F(W,X,Y,Z) for(i= W;i X Y;i Z)
#define C(A,B,C) if(c[A][B]==C)
#define S(W,X,Y,Z,A,B) p=1;F(W,X,Y,Z)C(A,B,120)p=0;if(p){F(W,X,Y,Z){C(A,B,46){c[A][B]='x';z++;Q();break;}}}else{F(W,X,Y,Z){C(A,B,120)break;else c[A][B]='o';}}

/*Example of an expanded "S" macro:
p=1;
for(i=x;i>m;i--) if(c[i][y]==120) p=0;
if(p)
{
    for(i=x;i>m;i--)
    {
        if(c[i][y]==46)
        {
            c[i][y]='x';
            z++;
            Q();
            break;
        }
    }
}
else
{
    for(i= x;i > m;i --)
    {
        if(c[i][y]==120) break;
        else c[i][y]='o';
    }
}
*/

p,m,z,w,h,o,i,u,l,x,y;
char c[16][16];
Q(){
    for(u=0;u<h;u++)
        for(l=0;l<w;l++)
            if(c[u][l]=='o')
            {
        x=u;y=l;
        S(x,>,m,--,i,y)
        S(y,>,m,--,x,i)
        S(y,<,w,++,x,i)
        S(x,<,h,++,i,y)
            }
}

main(int a, char **v)
{
    h=atoi(v[1]);
    w=atoi(v[2]);
    for(m=-1;o<h;o++)
        for(i=0;i<w;i++)
            scanf("%c",&c[o][i]);
    P();
    Q();
    printf("%d\n",z);
    P();
}

//Omitted in golfed version, prints the map.
P()
{
    for(o=0;o<h;o++)
    {
        for (i=0;i<w;i++) printf("%c",c[o][i]);
        printf("\n");
    }
}

```

Nowhere near as short as the solution by @Claudiu, but it runs blazingly fast. Instead of flood filling from the edges, it finds the encampment and works outward from the 'o' tokens.

* If it encounters any unstable ground next to the encampment, it expands the encampment onto it.
* If any encampment on the grid doesn't have at least one wall in each direction, it moves in that direction until it can build a wall.
* After each new wall section is placed, it recurses to find the next wall section to place.

Sample wall placements:

```
x..xxxx                           x..xxxx
x..x--x                           x..xoox
x.xx--x                           x3xxoox
x.ooo-.  <-- results in this -->  xooooo1
x.ooo-.                           xooooo2
xxxxxxx                           xxxxxxx

```

# Answer
> 1 votes
## Groovy : 841 805 754

```
i=new File("city.txt").getText()
x=i[2] as int
y=i[0] as int
m=i[4..i.length()-1].replaceAll('\n','').toList()
print r(m,0)
def r(m,n){if(f(m))return n;c=2e9;g(m).each{p=r(it,n+1);if(p<c)c=p;};return c;}
def f(m){u=[];u.addAll(m);for(i in 0..(x*y)){for(l in 0..m.size()-1){n(l,u);s(l,u);e(l,u);w(l,u);}};m.count('o')==u.count('o')}
def n(i,m){q=i-x;if((((q>=0)&(m[q]=='!'))|(q<0))&m[i]!='x'&m[i]!='W'){m[i]='!'}}
def s(i,m){q=i+x;if((((q>=0)&(m[q]=='!'))|(q<0))&m[i]!='x'&m[i]!='W'){m[i]='!'}}
def e(i,m){q=i+1;if((((q%x!=0)&(m[q]=='!'))|(q%x==0))&m[i]!='x'&m[i]!='W'){m[i]='!'}}
def w(i,m){q=i-1;if((((i%x!=0)&(m[q]=='!'))|(i%x==0))&m[i]!='x'&m[i]!='W'){m[i]='!'}}
def g(m){v=[];m.eachWithIndex{t,i->if(t=='.'){n=[];n.addAll(m);n[i]='W';v<<n}};return v}

```

Ungolfed:

```
def i = new File("city.txt").getText()
x=i[2].toInteger()
y=i[0].toInteger()
def m=i[4..i.length()-1].replaceAll('\n','').toList()
println r(m, 0)

def r(m, n){
    if(f(m)) return n
    def c = Integer.MAX_VALUE

    getAllMoves(m).each{ it ->
        def r = r(it, n+1)
        if(r < c) c = r
    }
    return c;
}

def f(m){
    def t = []
    t.addAll(m)
    for(i in 0..(x*y)){
        for(l in 0..m.size()-1){
            n(l,t);s(l,t);e(l,t);w(l,t);
        }
    }
    m.count('o')==t.count('o')
}

def n(i,m){
    def t = i-x;
    if( ( ( (t >= 0) && (m[t]=='!') ) || (t < 0)) && m[i]!='x' && m[i]!='W'){
        m[i]='!'
    }
}

def s(i,m){
    def t = i+x;
    if( ( ( (t >= 0) && (m[t]=='!') ) || (t < 0)) && m[i]!='x' && m[i]!='W'){
        m[i]='!'
    }
}

def e(i,m){
    def t = i+1;
    if( ( ( (t%x!=0) && (m[t]=='!') ) || (t%x==0)) && m[i]!='x' && m[i]!='W'){
        m[i]='!'
    }
}

def w(i,m){
    def t = i-1;
    if( ( ( (i%x!=0) && (m[t]=='!') ) || (i%x==0)) && m[i]!='x' && m[i]!='W'){
        m[i]='!'
    }
}

def getAllMoves(m){
    def moves = []
    m.eachWithIndex { t, i ->
        if(t=='.'){
            def newList = []
            newList.addAll(m)
            newList[i]='W'
            moves << newList
        }
    }
    return moves
}

```

Much more golfing to come...

Returns 2E9 if no solution.

# Answer
> 1 votes
# Dyalog APL, 91 bytes

`⊃∊{1∊a[⍸×{(×d)∧s 3∨/3∨⌿⍵}⍣≡4=d←0@⍵⊢a]:⍬⋄≢⍵}¨c[⍋≢¨c←(,⍳2⊣¨b)/¨⊂b←⍸2=a←(s←(4,4,⍨⍉)⍣2)'xo.'⍳⎕]`

assumes `⎕IO=0`, uses features from v16.0 (`@` and ), running time is exponential in the number of `.`-s

is evaluated input, must be a matrix of characters

`'xo.'⍳` replace `x` with 0, `o` with 1, `.` with 2, and all others with 3

`s←(4,4,⍨⍉)⍣2` a function that surrounds a matrix with 4s

`a←` assign the numeric matrix surrounded with 4s to a variable `a`

`b←⍸2=` `b` is the list of coord pairs where the 2s (i.e. the `.`-s) are

`(,⍳2⊣¨b)/¨⊂b` generate all combinations of elements of `b`

`c[⍋≢¨c←...]` sort them by size

`{... :⍬⋄≢⍵}¨` for each combination, check something and return either its length or an empty list

`⊃∊` the first non-empty result

`d←0@⍵⊢a` `d` is `a` with some elements replaced with 0

`4=` create boolean matrix - where are the 4s? i.e. the border we added

`{...}⍣≡` keep on applying the function in `{}` until the result stabilizes

`3∨/3∨⌿⍵` "boolean or" each element with its neighbours

`s` the result will be smaller, so let's re-create the border

`(×d)∧` apply the non-zero elements of `d` (the non-walls) as a boolean mask

`a[⍸× ...]` what in `a` corresponds to the 1s in our boolean matrix?

`1∊` are there any 1s, i.e. `o`, encampments?

---
Tags: code-golf
---


title: Solve the Diophantine Pell equation

text:
# Question
Title: Solve the Diophantine Pell equation
Given a natural number c as input, our task is finding the fastest way to calculate one -atleast- availabe integer solution (a,b) of pell equation **c=a²-b²**.

Rules

Built-in functions and loopholes arent given any interest.

The program deals with integers (signed), the input is not supposed to abuse this range.

Output can be formatted in any form.

Your submission is scored by sum of milliseconds elapsed with these inputs:

```
6 17 489 1270453 5609331 92 3343 74721 3920.

```

Lowest time wins.

# Answer
> 5 votes
**nasm x64 i7 - 2 - 5 milliseconds**

```
    extern  printf
    section .bss

    section .data
        fmt:           db "%i - %i", 10, 0
        NumberToTestF  dq 5609331.0 ; put the number to test in floating
        NumberToTestI  dq 0         ; format, ie not 489, but 489.0
        Counter        dq 0
        OutsideLoop    dq 0
        Divide1        dq 2
        Divide2        dq 1.7
    section .text

    global main
    main:
        push    rbp
        mov rbp, rsp
        sub rsp, 32

        ; convert from float to int for faster cmp
        fld qword [NumberToTestF]
        movq xmm0, qword [NumberToTestF]
        cvttsd2si rax, xmm0
        mov [NumberToTestI], rax

        ; Make 1st counter convert result to int
        fdiv qword [Divide2]
        fstp qword [OutsideLoop]
        movq xmm1, [OutsideLoop]
        cvttsd2si rax, xmm1
        mov [OutsideLoop], rax

        ; make counter
        mov r8, [Divide1]
        xor rdx, rdx
        mov rax, [NumberToTestI]
        idiv r8
        mov [Counter], rax

        ; initialize locals
        mov dword [rbp - 8], eax
        mov dword [rbp - 20], edi
        mov qword [rbp - 32], rsi
        jmp .l00p

     .t0p:
        mov eax, [Counter]
        mov dword [rbp - 4], eax
        jmp .b0tt0m
     .inn3r:

        ; square & subtract each
        ; number
        mov eax, dword [rbp - 8]
        mov edx, eax
        imul edx, dword [rbp - 8]
        mov eax, dword [rbp - 4]
        imul eax, dword [rbp - 4]
        mov ecx, edx
        sub ecx, eax
        mov eax, ecx

        ; final comparison
        ; if cmp == true print value
        ; & exit, if not keep looping
        cmp eax, [NumberToTestI]
        jnz .k33p0n
        mov eax, fmt
        mov edx, dword [rbp - 4]
        mov ecx, dword [rbp - 8]
        mov esi, ecx
        mov rdi, rax
        mov eax, 0
        call printf
        jmp .d0n3
    .k33p0n:
        add dword [rbp - 4], 1
    .b0tt0m:
        mov eax, [OutsideLoop]
        cmp dword [rbp-4], eax
        jle .inn3r
        add dword [rbp - 8], 1
    .l00p:
        mov eax, [OutsideLoop]
        cmp dword [rbp-8], eax
        jle .t0p
    .d0n3:
        mov eax,0
        leave
        ret

Compile/link:
     nasm -f elf64 -o Break.o Break.asm
     gcc -o Break Break.o

```

# Answer
> 1 votes
# Python, 130.0 Miliseconds

```
k=False
c = q
for i in range (int(c/2),int(c/1.7)):
    if k:
        break
    for x in range (int(c/2),int(c/1.7)):
        if i**2-x**2 == c:
            print i,x
            k=True
            break

```

# Answer
> 1 votes
# Axiom, 0.02 sec

```
v(c)==
  local m
  if c rem 2=0 then
        m:INT:=c/2
        if m rem 2~=0 then return [0,0]
        else return reverse sort  [(c/4)-1,(c/4)+1]
  reverse sort [1+(c-1)/2, (c-1)/2]

f()==for i in [6,17,489,1270453,92,3343,74721,3920] repeat output[i, v(i)]

(4) -> f()
   [6,[0,0]]
   [17,[8,9]]
   [489,[244,245]]
   [1270453,[635226,635227]]
   [92,[22,24]]
   [3343,[1671,1672]]
   [74721,[37360,37361]]
   [3920,[979,981]]
                                                               Type: Void
                                               Time: 0.02 (EV) = 0.02 sec

```

When integer equation b^2-a^2=c is not soluble in N+{0} return \[0,0\] one has to note there is no loop few remender and division so it is O(1)

```
-> v(6),v(17),v(489),v(1270453),v(92),v(3343),v(74721),v(3920)
 Compiling function v with type PositiveInteger -> List Fraction
    Integer

 [[0,0], [9,8], [245,244], [635227,635226], [24,22], [1672,1671],
  [37361,37360], [981,979]]

```

add some test

```
(13) -> r:=[6,17,489,1270453,92,3343,74721,3920,613352373758390083167447227749,5
82316870718762711394729885483949672964468220019,97658628223769028234818028188353
8549090329]

    (13)
   [6, 17, 489, 1270453, 92, 3343, 74721, 3920, 613352373758390083167447227749,
    582316870718762711394729885483949672964468220019,
    976586282237690282348180281883538549090329]
                                                   Type: List PositiveInteger
(14) -> a:=[v(i)  for i in r]

   (14)
   [[0,0], [9,8], [245,244], [635227,635226], [24,22], [1672,1671],
    [37361,37360], [981,979],
    [306676186879195041583723613875,306676186879195041583723613874],

     [291158435359381355697364942741974836482234110010,
      291158435359381355697364942741974836482234110009]
     ,

     [488293141118845141174090140941769274545165,
      488293141118845141174090140941769274545164]
     ]
                                         Type: List List Fraction Integer
(15) -> [a.i.1^2-a.i.2^2-r.i  for i in 1..#a]

   (15)  [- 6,0,0,0,0,0,0,0,0,0,0]
                                                  Type: List Fraction Integer

```

---
Tags: fastest-code
---