# Question
Title: How do I find the factorial of a positive number?
The challenge:

> Write a program or a function that inputs a positive number and returns its factorial.

Note: This is a question. Please do not take the question and/or answers seriously. More information here. Every question is also a question, so the highest voted answer wins.

# Answer
This is a very simple numerical computing problem that we can solve with Stirling's approximation:

As you can see, that formula features a square root, which we will also need a way to approximate. We will choose the so-called "Babylonian method" for that because it is arguably the simplest one:

Note that computing the square root this way is a good example of recursion.

Putting it all together in a Python program gives us the following solution to your problem:

```
def sqrt(x, n): # not the same n as below
    return .5 * (sqrt(x, n - 1) + x / sqrt(x, n - 1)) if n > 0 else x

n = float(raw_input())
print (n / 2.718) ** n * sqrt(2 * 3.141 * n, 10)

```

With a simple modification the above program can output a neat table of factorials:

```
1! =    0.92215
2! =    1.91922
3! =    5.83747
4! =   23.51371
5! =  118.06923
6! =  710.45304
7! = 4983.54173
8! = 39931.74015
9! = 359838.58817

```

This method should be sufficiently accurate for most applications.
> 46 votes

# Answer
## C#

Sorry, but I hate recursive function.

```
public string Factorial(uint n) {
    return n + "!";
}

```
> 44 votes

# Answer
Java

```
public int factorial ( int n ) {
switch(n){
case 0: return 1;
case 1: return 1;
case 2: return 2;
case 3: return 6;
case 4: return 24;
case 5: return 120;
case 6: return 720;
case 7: return 5040;
case 8: return 40320;
case 9: return 362880;
case 10: return 3628800;
case 11: return 39916800;
case 12: return 479001600;
default : throw new IllegalArgumentException();
}
}

```
> 36 votes

# Answer
# Python

Of course the best way how to solve any problem is to use regular expressions:

```
import re

# adapted from http://stackoverflow.com/q/15175142/1333025
def multiple_replace(dict, text):
  # Create a regular expression  from the dictionary keys
  regex = re.compile("(%s)" % "|".join(map(re.escape, dict.keys())))
  # Repeat while any replacements are made.
  count = -1
  while count != 0:
    # For each match, look-up corresponding value in dictionary.
    (text, count) = regex.subn(lambda mo: dict[mo.string[mo.start():mo.end()]], text)
  return text

fdict = {
    'A': '@',
    'B': 'AA',
    'C': 'BBB',
    'D': 'CCCC',
    'E': 'DDDDD',
    'F': 'EEEEEE',
    'G': 'FFFFFFF',
    'H': 'GGGGGGGG',
    'I': 'HHHHHHHHH',
    'J': 'IIIIIIIIII',
    'K': 'JJJJJJJJJJJ',
    'L': 'KKKKKKKKKKKK',
    'M': 'LLLLLLLLLLLLL',
    'N': 'MMMMMMMMMMMMMM',
    'O': 'NNNNNNNNNNNNNNN',
    'P': 'OOOOOOOOOOOOOOOO',
    'Q': 'PPPPPPPPPPPPPPPPP',
    'R': 'QQQQQQQQQQQQQQQQQQ',
    'S': 'RRRRRRRRRRRRRRRRRRR',
    'T': 'SSSSSSSSSSSSSSSSSSSS',
    'U': 'TTTTTTTTTTTTTTTTTTTTT',
    'V': 'UUUUUUUUUUUUUUUUUUUUUU',
    'W': 'VVVVVVVVVVVVVVVVVVVVVVV',
    'X': 'WWWWWWWWWWWWWWWWWWWWWWWW',
    'Y': 'XXXXXXXXXXXXXXXXXXXXXXXXX',
    'Z': 'YYYYYYYYYYYYYYYYYYYYYYYYYY'}

def fact(n):
    return len(multiple_replace(fdict, chr(64 + n)))

if __name__ == "__main__":
    print fact(7)

```
> 21 votes

# Answer
Haskell

Short code is efficient code, so try this.

```
fac = length . permutations . flip take [1..]

```

Why it's trolling:

I'd laugh at any coder who wrote this... The inefficiency is beautiful. Also probably incomprehensible to any Haskell programmer who actually can't write a factorial function.

Edit: I posted this a while ago now, but I thought I'd clarify for future people and people who can't read Haskell.

The code here takes the list of the numbers 1 to n, creates the list of all permutations of that list, and returns the length of that list. On my machine it takes about 20 minutes for 13!. And then it ought to take four hours for 14! and then two and a half days for 15!. Except that at some point in there you run out of memory.

Edit 2: Actually you probably won't run out of memory due to this being Haskell (see the comment below). You might be able to force it to evaluate the list and hold it in memory somehow, but I don't know enough about optimizing (and unoptimizing) Haskell to know exactly how to do that.
> 15 votes

# Answer
## C#

Since this is a math problem, it makes sense to use an application specifically designed to solve math problems to do this calculation...

### Step 1:

Install MATLAB. A trial will work, I think, but this super-complicated problem is likely important enough to merit purchasing the full version of the application.

### Step 2:

Include the MATLAB COM component in your application.

### Step 3:

```
public string Factorial(uint n) {
    MLApp.MLApp matlab = new MLApp.MLApp();
    return matlab.Execute(String.Format("factorial({0})", n);
}

```
> 10 votes

# Answer
## C#

Factorials are a higher level math operation that can be difficult to digest all in one go. The best solution in programming problems like this, is to break down one large task into smaller tasks.

Now, n! is defined as 1\*2\*...\*n, so, in essence repeated multiplication, and multiplication is nothing but repeated addition. So, with that in mind, the following solves this problem:

```
long Factorial(int n)
{
    if(n==0)
    {
        return 1;
    }

    Stack<long> s = new Stack<long>();
    for(var i=1;i<=n;i++)
    {
        s.Push(i);
    }
    var items = new List<long>();
    var n2 = s.Pop();
    while(s.Count >0)
    {
        var n3 = s.Pop();
        items.AddRange(FactorialPart(n2,n3));
        n2 = items.Sum();
    }
    return items.Sum()/(n-1);
}

IEnumerable<long> FactorialPart(long n1, long n2)
{
    for(var i=0;i<n2;i++){
        yield return n1;
    }
}

```
> 9 votes

# Answer
```
#include <math.h>

int factorial(int n)
{
    const double g = 7;
    static const double p[] = { 0.99999999999980993, 676.5203681218851,
                                -1259.1392167224028, 771.32342877765313,
                                -176.61502916214059, 12.507343278686905,
                                -0.13857109526572012, 9.9843695780195716e-6,
                                1.5056327351493116e-7 };
    double z = n - 1 + 1;
    double x = p[0];
    int i;
    for ( i = 1; i < sizeof(p)/sizeof(p[0]); ++i )
        x += p[i] / (z + i);
    return sqrt(2 * M_PI) * pow(z + g + 0.5, z + 0.5)  * exp(-z -g -0.5) * x + 0.5;
}

```

Trolls:

* A 100% correct way of computing factorial that completely misses the point of either doing it iteratively or recursively.
* You have no idea why it works and could not generalize it to do anything else.
* More costly than just computing it with integer math.
* The most obvious "suboptimal" code (`z = n - 1 + 1`) is actually self-documenting if you know what's going on.
* For extra trolling I should compute `p[]` using a recursive calculation of the series coefficients!

(It's the Lanczos approximation of the gamma function)
> 9 votes

# Answer
We all know from college that the most efficient way to calculate a multiplication is through the use of logarithms. After all, why else would people use logarithm tables for hundreds of years?

So from the identity `a*b=e^(log(a)+log(b))` we form the following Python code:

```
from math import log,exp

def fac_you(x):
    return round(exp(sum(map(log,range(1,x+1)))))

for i in range(1,99):
    print i,":",fac_you(i)

```

It creates a list of numbers from `1` to `x`, (the `+1` is needed because Python sucks) calculates the logarithm of each, sums the numbers, raises the e to the power of the sum and finally rounds the value to the nearest integer (because Python sucks). Python has a built-in function for calculating factorials, but it only works for integers, so it can't produce big numbers (because Python sucks). This is why the function above is needed.

Btw, a general tip for students is that if something doesn't work as expected, it's probably because the language sucks.
> 9 votes

# Answer
Unfortunately, Javascript lacks a built-in way to compute the factorial. But, you can use its meaning in combinatorics to determine the value nevertheless:

The factorial of a number n is the number of permutations of an list of that size.

So, we can generate every list of n-digit number, check if it is a permutation, and if so, increment a counter:

```
window.factorial = function($nb_number) {
  $nb_trials = 1
  for($i = 0; $i < $nb_number; $i++) $nb_trials *= $nb_number
  $nb_successes = 0
  __trying__:
  for($nb_trial = 0; $nb_trial < $nb_trials; $nb_trial++){
    $a_trial_split = new Array
    $nb_tmp = $nb_trial
    for ($nb_digit = 0; $nb_digit < $nb_number; $nb_digit++){
      $a_trial_split[$nb_digit] = $nb_tmp - $nb_number * Math.floor($nb_tmp / $nb_number)
      $nb_tmp = Math.floor($nb_tmp / $nb_number)
    }
    for($i = 0; $i < $nb_number; $i++)
      for($j = 0; $j < $nb_number; $j++)
        if($i != $j)
          if($a_trial_split[$i] == $a_trial_split[$j])
            continue __trying__
    $nb_successes += 1
  }
  return $nb_successes
}

alert("input a number")
document.open()
document.write("<input type = text onblur = alert(factorial(parseInt(this.value))))>")
document.close()

```

---

---

Trolls:

* Types hungarian notation, snake\_case *and* unneccessary sigils. How evil is that?
* Invented my own convention for jump labels, incompatible with the current use of this convention.
* Every possible variable is accidentally global.
* The solution is not `O(n)`, not `O(n!)`, but `O(n^n)`. This alone would have sufficed to qualify here.
* Incrementing a number and then converting as base-n is a bad way to generate a list of sequences. Even if we did want duplicates. Mysteriously breaking for n \> 13 is not the only reason.
* Of course we could have used `number.toString(base)`, but that doesn't work for bases above 36. Yes, I know 36! is a *lot*, but still...
* Did I mention Javascript had the modulus operator? Or `Math.pow`? No? Oh well.
* Refusing to use `++` outside of for-loops makes it even more mysterious. Also, `==` is bad.
* Deeply nested braceless looping constructs. Also, nested conditionals instead of AND. Also, the outer condition could have been avoided by ending the inner loop at `$i`.
* The functions `new Array`, `document.write` (with friends) and `alert` (instead of a prompt or an input label) form a complete trifecta of function choice sins. Why is the input added dynamically after all?
* Inline event handlers. Oh, and deep piping is hell to debug.
* Unquoted attributes are fun, and the spaces around `=` make them even harder to read.
* Did I already mention I hate semicolons?
> 8 votes

# Answer
**Ruby and WolframAlpha**

This solution uses the WolframAlpha REST API to calculate the factorial, with RestClient to fetch the solution and Nokogiri to parse it. It doesn't reinvent any wheels and uses well tested and popular technologies to get the result in the most modern way possible.

```
require 'rest-client'
require 'nokogiri'

n = gets.chomp.to_i
response = Nokogiri::XML(RestClient.get("http://api.wolframalpha.com/v2/query?input=#{n}!&format=moutput&appid=YOUR_APP_KEY"))
puts response.xpath("//*/moutput/text()").text

```
> 8 votes

# Answer
# Javascript

Javascript is a functional programming language, this means you have to use functions for everything because its faster.

```
function fac(n){
    var r = 1,
        a = Array.apply(null, Array(n)).map(Number.call, Number).map(function(n){r = r * (n + 1);});
    return r;
}

```
> 7 votes

# Answer
# Using Bogo-Sort in Java

```
public class Factorial {
    public static void main(String[] args) {
        //take the factorial of the integers from 0 to 7:
        for(int i = 0; i < 8; i++) {
            System.out.println(i + ": " + accurate_factorial(i));
        }
    }

    //takes the average over many tries
    public static long accurate_factorial(int n) {
        double sum = 0;
        for(int i = 0; i < 10000; i++) {
            sum += factorial(n);
        }
        return Math.round(sum / 10000);
    }

    public static long factorial(int n) {
        //n! = number of ways to sort n
        //bogo-sort has O(n!) time, a good approximation for n!
        //for best results, average over several passes

        //create the list {1, 2, ..., n}
        int[] list = new int[n];
        for(int i = 0; i < n; i++)
            list[i] = i;

        //mess up list once before we begin
        randomize(list);

        long guesses = 1;

        while(!isSorted(list)) {
            randomize(list);
            guesses++;
        }

        return guesses;
    }

    public static void randomize(int[] list) {
        for(int i = 0; i < list.length; i++) {
            int j = (int) (Math.random() * list.length);

            //super-efficient way of swapping 2 elements without temp variables
            if(i != j) {
                list[i] ^= list[j];
                list[j] ^= list[i];
                list[i] ^= list[j];
            }
        }
    }

    public static boolean isSorted(int[] list) {
        for(int i = 1; i < list.length; i++) {
            if(list[i - 1] > list[i])
                return false;
        }
        return true;
    }
}

```

This actually works, just very slowly, and it isn't accurate for higher numbers.
> 5 votes

# Answer
**PERL**

Factorial can be a hard problem. A map/reduce like technique -- just like Google uses -- can split up the math by forking off a bunch of processes and collecting the results. This will make good use of all those cores or cpus in your system on a cold winter's night.

Save as f.perl and chmod 755 to make sure you can run it. You do have the Pathologically Eclectic Rubbish Lister installed, don't you?

```
#!/usr/bin/perl -w
use strict;
use bigint;
die "usage: f.perl N (outputs N!)" unless ($ARGV[0] > 1);
print STDOUT &main::rangeProduct(1,$ARGV[0])."\n";
sub main::rangeProduct {
    my($l, $h) = @_;
    return $l    if ($l==$h);
    return $l*$h if ($l==($h-1));
    # arghhh - multiplying more than 2 numbers at a time is too much work
    # find the midpoint and split the work up :-)
    my $m = int(($h+$l)/2);
    my $pid = open(my $KID, "-|");
      if ($pid){ # parent
        my $X = &main::rangeProduct($l,$m);
        my $Y = <$KID>;
        chomp($Y);
        close($KID);
        die "kid failed" unless defined $Y;
        return $X*$Y;
      } else {
        # kid
        print STDOUT &main::rangeProduct($m+1,$h)."\n";
        exit(0);
    }
}

```

Trolls:

* forks O(log2(N)) processes
* doesn't check how many CPUs or cores you have
* Hides lots of bigint/text conversions that occur in every process
* A for loop is often faster than this code
> 4 votes

# Answer
## Python

Just an O(n!\*n^2) algorithm to find the factorial. Base case handled. No overflows.

```
def divide(n,i):
    res=0
    while n>=i:
         res+=1
         n=n-i
    return res

def isdivisible(n,numbers):
    for i in numbers:
         if n%i!=0:
             return 0
         n=divide(n,i)
    return 1

def factorial(n):
    res = 1
    if n==0: return 1 #Handling the base case
    while not isdivisible(res,range(1,n+1)):
         res+=1
    return res

```
> 4 votes

# Answer
Well, there is an easy solution in Golfscript. You could use a Golfscript interpreter and run this code:

```
.!+,1\{)}%{*}/

```

Easy huh :) Good luck!
> 3 votes

# Answer
### Mathematica

```
factorial[n_] := Length[Permutations[Table[k, {k, 1, n}]]]

```

It doesn't seem work for numbers larger than 11, and factorial\[11\] froze up my computer.
> 3 votes

# Answer
# Ruby

```
f=->(n) { return 1 if n.zero?; t=0; t+=1 until t/n == f[n-1]; t }

```

The slowest one-liner I can imagine. It takes 2 minutes on an i7 processor to calculate `6!`.
> 3 votes

# Answer
# Python

Below is a Python version of the solution, which is not limited to the 32 bit (or 64 bit on a very recent system) limit for integer numbers in Python. To get around this limitation, we shall use a string as input and output for the `factorial` routine and internally split the string in it's digits to be able to perform the multiplication.

So here is the code: the `getDigits` function splits a string representing a number in to its digits, so "1234" becomes `[ 4, 3, 2, 1 ]` (the reverse order just makes the `increase` and `multiply` functions simpler). The `increase` function takes such a list and increases it by one. As the name suggests, the `multiply` function multiplies, e.g. `multiply([2, 1], [3])` returns `[ 6, 3 ]` because 12 times 3 is 36. This works in the same way as you would multiply something with pen and paper.

Then finally, the `factorial` function uses these helper functions to calculate the actual factorial, for example `factorial("9")` gives `"362880"` as its output.

```
import copy

def getDigits(n):
    digits = []
    for c in n:
        digits.append(ord(c) - ord('0'))

    digits.reverse()
    return digits

def increase(d):
    d[0] += 1
    i = 0
    while d[i] >= 10:
        if i == len(d)-1:
            d.append(0)

        d[i] -= 10
        d[i+1] += 1
        i += 1

def multiply(a, b):
    subs = [ ]
    s0 = [ ]
    for bi in b:

        s = copy.copy(s0)
        carry = 0
        for ai in a:
            m = ai * bi + carry
            s.append(m%10)
            carry = m//10

        if carry != 0:
            s.append(carry)

        subs.append(s)
        s0.append(0)

    done = False
    res = [ ]
    termsum = 0
    pos = 0
    while not done:
        found = False
        for s in subs:
            if pos < len(s):
                found = True
                termsum += s[pos]

        if not found:
            if termsum != 0:
                res.append(termsum%10)
                termsum = termsum//10
            done = True
        else:
            res.append(termsum%10)
            termsum = termsum//10
            pos += 1

    while termsum != 0:
        res.append(termsum%10)
        termsum = termsum//10

    return res

def factorial(x):
    if x.strip() == "0" or x.strip() == "1":
        return "1"

    factorial = [ 1 ]
    done = False
    number = [ 1 ]
    stopNumber = getDigits(x)
    while not done:
        if number == stopNumber:
            done = True

        factorial = multiply(factorial, number)
        increase(number)

    factorial.reverse()

    result = ""
    for c in factorial:
        result += chr(c + ord('0'))

    return result

print factorial("9")

```

### Notes

In python an integer doesn't have a limit, so if you'd like to do this manually you can just do

```
fac = 1
for i in range(2,n+1):
    fac *= i

```

There's also the very convenient `math.factorial(n)` function.

This solution is obviously far more complex than it needs to be, but it does work and in fact it illustrates how you can calculate the factorial in case you are limited by 32 or 64 bits. So while nobody will believe this is the solution you've come up with for this simple (at least in Python) problem, you can actually learn something.
> 2 votes

# Answer
The correct approach for these difficult math problems is a DSL. So I'll model this in terms of a simple language

```
data DSL b a = Var x (b -> a)
             | Mult DSL DSL (b -> a)
             | Plus DSL DSL (b -> a)
             | Const Integer (b -> a)

```

To write our DSL nicely, it's helpful to view it as a free monad generated by the algebraic functor

```
F X = X + F (DSL b (F X)) -- Informally define + to be the disjoint sum of two sets

```

We could write this in Haskell as

```
Free b a = Pure a
         | Free (DSL b (Free b a))

```

I will leave it to the reader to derive the trivial implementation of

```
join   :: Free b (Free b a) -> Free b a
return :: a -> Free b a
liftF  :: DSL b a -> Free b a

```

Now we can descibe an operation to model a factorial in this DSL

```
factorial :: Integer -> Free Integer Integer
factorial 0 = liftF $ Const 1 id
factorial n = do
  fact' <- factorial (n - 1)
  liftF $ Mult fact' n id

```

Now that we've modeled this, we just need to provide an actual interpretation function for our free monad.

```
denote :: Free Integer Integer -> Integer
denote (Pure a) = a
denote (Free (Const 0 rest)) = denote $ rest 0
...

```

And I'll leave the rest of the denotation to the reader.

To improve readability, it's sometimes helpful to present a concrete AST of the form

```
data AST = ConstE Integer
         | PlusE AST AST
         | MultE AST AST

```

and then right a trivial reflection

```
reify :: Free b Integer -> AST

```

and then it's straightforward to recursively evaluate the AST.
> 2 votes

# Answer
## Python

The most reasonable solution is clearly to check through all numbers until you find the one which is the factorial of the given number.

```
print('Enter the number')
n=int(input())
x=1
while True:
    x+=1
    tempx=int(str(x))
    d=True
    for i in range(1, n+1):
        if tempx/i!=round(tempx/i):
            d=False
        else:
            tempx/=i
    if d:
        print(x)
        break

```
> 2 votes

# Answer
Just go to Google and type in your factorial:

```
5!

```

http://lmgtfy.com/?q=5!
> 2 votes

# Answer
# A most elegant recursive solution in C

Every one knows the most elegant solutions to factorials are recursive.

Factorial:

```
0! = 1
1! = 1
n! = n * (n - 1)!

```

But multiplication can also be defined recursively as successive additions.

Multiplication:

```
n * 0 = 0
n * 1 = n
n * m = n + n * (m - 1)

```

And so can addition as successive incrementations.

Addition:

```
n + 0 = n
n + 1 = (n + 1)
n + m = (n + 1) + (m - 1)

```

In `C`, we can use `++x` and `--x` to handle the primitives `(x + 1)` and `(x - 1)` respectively, so we have everything defined.

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

// For more elegance, use T for the type
typedef unsigned long T;

// For even more elegance, functions are small enough to fit on one line

// Addition
T A(T n, T m) { return (m > 0)? A(++n, --m) : n; }

// Multiplication
T M(T n, T m) { return (m > 1)? A(n, M(n, --m)): (m? n: 0); }

// Factorial
T F(T n) { T m = n; return (m > 1)? M(n, F(--m)): 1; }

int main(int argc, char **argv)
{
    if (argc != 2)
        return 1;

    printf("%lu\n", F(atol(argv[1])));

    return 0;
}

```

Let's try it out:

```
$ ./factorial 0
1
$ ./factorial 1
1
$ ./factorial 2
2
$ ./factorial 3
6
$ ./factorial 4
24
$ ./factorial 5
120
$ ./factorial 6
720
$ ./factorial 7
5040
$ ./factorial 8
40320

```

Perfect, although 8! took a long time for some reason. Oh well, the most elegant solutions aren't always the fastest. Let's continue:

```
$ ./factorial 9

```

Hmm, I'll let you know when it gets back...
> 2 votes

# Answer
# Python

As @Matt\_Sieker's answer indicated, factorials can be broken up into addition- why, breaking up tasks is the essence of programming. But, we can break that down into addition by 1!

```
def complicatedfactorial(n):
    def addby1(num):
        return num + 1
    def addnumbers(a,b):
        copy = b
        cp2 = a
        while b != 0:
            cp2 = addby1(cp2)
            b -= 1
    def multiply(a,b):
        copy = b
        cp2 = a
        while b != 0:
            cp2 = addnumbers(cp2,cp2)
    if n == 0:
        return 1
    else:
        return multiply(complicatedfactorial(n-1),n)

```

I think this code *guarantees* an SO Error, because

1. Recursion- warms it up
2. Each layer generates calls to multiply
3. which generates calls to addnumbers
4. which generates calls to addby1!

Too much functions,right?
> 2 votes

# Answer
## bash

Factorials are easily determined with well known command line tools from bash.

```
read -p "Enter number: " $n
seq 1 $n | xargs echo | tr ' ' '*' | bc

```

As @Aaron Davies mentioned in the comments, this looks much tidier and we all want a nice and tidy program, don't we?

```
read -p "Enter number: " $n
seq 1 $n | paste -sd\* | bc

```
> 1 votes

# Answer
## TI-Basic 84

```
:yumtcInputdrtb@gmail And:cReturnbunchojunk@Yahoo A!op:sEnd:theemailaddressIS Crazy ANSWER LOL

```

It really works :)
> 1 votes

# Answer
# Javascript

Obviously the job of a programmer is to do as little work as possible, and to use as many libraries as possible. Therefore, we want to import jQuery *and* math.js. Now, the task is simple as this:

```
$.alert=function(message){
    alert(message);
}$.factorial=function(number){
    alert(math.eval(number+"!"));
    return math.eval(number+"!");
}
$.factorial(10);

```
> 1 votes

# Answer
## Python

With just a slight modification of the standard recursive factorial implementation, it becomes intolerably slow for n \> 10.

```
def factorial(n):
    if n in (0, 1):
        return 1
    else:
        result = 0
        for i in range(n):
            result += factorial(n - 1)
        return result

```
> 1 votes

# Answer
# Bash

```
#! /bin/bash

function fact {
    if [[ ${1} -le 1 ]]; then
        return 1
    fi;

    fact $((${1} - 1))
    START=$(date +%s)
    for i in $(seq 1 $?); do sleep ${1}; done
    END=$(date +%s)
    RESULT=$(($END - $START))
    return $RESULT
}

fact ${1}
echo $?

```
> 1 votes

# Answer
Let's try to do it by **the Monte Carlo Method**. We all know that the probability of two random ***n***-permutations being equal is exactly ***1/n!***. Therefore we can just check how many tests are needed (let's call this number ***b***) until we get ***c*** hits. Then, ***n! ~ b/c***.

## Sage, should work in Python, too

```
def RandomPermutation(n) :
    t = range(0,n)
    for i in xrange(n-1,0,-1):
        x = t[i]
        r = randint(0,i)
        t[i] = t[r]
        t[r] = x
    return t

def MonteCarloFactorial(n,c) :
    a = 0
    b = 0
    t = RandomPermutation(n)
    while a < c :
        t2 = list(t)
        t = RandomPermutation(n)
        if t == t2 :
            a += 1
        b += 1
    return round(b/c)

MonteCarloFactorial(5,1000)
# returns an estimate of 5!

```
> 1 votes

# Answer
**Haskell**

```
c :: Integer -> (Integer -> Integer) -> Integer -> Integer
c 0 f x = x
c 1 f x = f x
c n f x = f (c (n-1) f x)

factorial 0 = 1
factorial n = (foldl1 (.) $ map c [1..n]) (+1) 0

```
> 1 votes

# Answer
# C

```
#include<stdio.h>
int main()
{
    int t;
    int a[200]; //array will have the capacity to store 200 digits.
    int n,i,j,temp,m,x;

    scanf("%d",&t);
    while(t--)
    {
       scanf("%d",&n);
       a[0]=1;  //initializes array with only 1 digit, the digit 1.
       m=1;    // initializes digit counter

       temp = 0; //Initializes carry variable to 0.
       for(i=1;i<=n;i++)
       {
            for(j=0;j<m;j++)
            {
               x = a[j]*i+temp; //x contains the digit by digit product
               a[j]=x%10; //Contains the digit to store in position j
               temp = x/10; //Contains the carry value that will be stored on later indexes
            }
             while(temp>0) //while loop that will store the carry value on array.
             {
               a[m]=temp%10;
               temp = temp/10;
               m++; // increments digit counter
             }
      }
              for(i=m-1;i>=0;i--) //printing answer
              printf("%d",a[i]);
              printf("\n");
    }
    return 0;
}

```
> 0 votes

# Answer
# Powershell

```
# This line will make sure there aren't any errors in your script.
# You should use this at the start of every script.
$ErrorActionPreference = 'SilentlyContinue'

<#
The next line looks really tricky, but it's actually pretty simple.
    $n= tells the computer we want to give it a number.
    read-host takes that number from us.
    $m= tells the computer we're going to do maths on that number.
    1e3* tells the computer we expect the result to be no longer than 3 digits.
        If the result might be longer than 3 digits you'll need to increase this by changing the 3 to however many digits there might be. Otherwise the answer will be wrong.
    ..1 tells the computer we want accuracy down to the ones digit.
    |%{ starts a maths statement.
#>

($m=1e3*($n=read-host))..1|%{

<#
    This line is a little simpler.
        ($x=1) starts a maths counter at 1. This is needed because computers normally start counting at zero.
        ..$_ brings in the accuracy setting we used earlier.
        |%{ starts a nested maths statement.
#>

    ($x=1)..$_|%{

        # The next bit is really entry-level stuff. You should probably re-read a few chapters if you don't get it.
        # $x gets our starting counter we made.
        # *= tells the computer we want a factorial.
        # $_ pulls in the user input we got earlier.

        $x*=$_

    # This ends the nested maths statement.
    }

    # This next line outputs the maths result in the advanced "X2" format.
    # Trust me, your professor will be very impressed by this.

    "{0:X2}"-f$x

# This ends the rest of the script.
}

```

---

**Trolls**

The above is a fully commented script seeking to appear well-documented and thoroughly explained. However, not a single bit of the documentation is true. Particular items of interest are noted below.

* Setting `$ErrorActionPreference` to `'SilentlyContinue'` doesn't prevent any errors - it just makes sure they're not displayed. This will also make troubleshooting the script more difficult. Also, the recommendation to use this in all other scripts may make troubleshooting of future scripts more difficult.
* Changing the 3 to any other number doesn't change the accuracy of the output. It just affects how long the script might run, and how much additional garbage output there might be.
* There is no "advanced X2 format". The given line changes the output to hexadecimal, with a minimum of 2 digits.

The requested factorial *is* given in the output. However, the output also includes all other factorials from `1!` to `($n*1000)!`. Oh, and they're all in hex. Ah, and limited to the maximum value available in a signed 32-bit integer. And since the script *starts* with `($n*1000)!`, it's going to take awhile to run before it outputs *any* numbers (the majority of the factorials will silently error since they're too large and we set `$ErrorActionPreference` to `'SilentlyContinue'`) let alone the *right* number.

The right answer actually is in there, but someone who doesn't know what they're doing - and especially someone who actually believes the comments - could have a hard time finding it. The simplest way to really do it is:

```
($x=1)..(read-host)|%{$x*=$_};$x

```

Granted, that's still limited to the space in a signed 32-bit integer. (The default integer type in PowerShell) But it's a legitimate start.
> 0 votes

# Answer
It is well known in combinatorics that

```
n! (def)= nPr(n,n)

```

That is, factorial is the number of n-long strings that can be made from n distinct values without repetition.

Here's the faster application of that:

## C99

```
int find_permutations( int n, char* s )
{
    /* find the NUL byte which terminates every string */
    char* p = s;
    while (*(p++));

    int permutations_found = 1;
    if (p > s + n) {
        for( char *f = s; *f; ++f )
            for( char *g = s; g < f; ++g )
                permutations_found *= -(s - p - n) * (*f - *g) / (p - s);
        return! !permutations_found;
    }

    *p = p[-1];
    p[-1] = '0';
    do { permutations_found += find_permutations(n, s); } while (++((-1)[p]) != '0' + n);
    p[-1] = 0;

    return-- permutations_found;
}

int factorial( int n )
{
    char s[n+3];
    s[1] = 0;
    return find_permutations(n, s+1);
}

```

The slower version would of course generate permutations using rand() and count the unique ones.
> 0 votes

# Answer
So, clearly we have an interesting math problem here... I would say that the best that we can do is to write a C# program to generate a latex snippet that we can put into a latex document.

```
class LatexFactorial
{
    public static string getLatexFactorial(int n)
    {
        string latex = n + "! = ";

        for (int i = n; i > 0; i--)
        {
            latex += i + " \\cdot ";
        }

        //Don't forget 0!
        latex += "1";

        return latex;
    }

}

```

Naturally, the user needs to identify n, but we don't want to make it too easy for the user... we'll use something like this...

```
 static void Main(string[] args)
    {
        string line = Console.ReadLine();

        Console.WriteLine();
        Console.WriteLine();

        Console.WriteLine(LatexFactorial.getLatexFactorial(int.Parse(line)));

        Console.Read();

    }

```
> 0 votes

# Answer
# R

You could use `factorial` but to save some of the precious computing time, just add one to your argument and use the `gamma` distribution:

```
gamma(5) # return factorial of 4

```

Unfortunately, the problem with this approach is that it will return `Inf` for numbers greater than 170.

```
> gamma(171)
[1] 7.257416e+306
> gamma(172)
[1] Inf
Warning message:
value out of range in 'gammafn'

```
> 0 votes

# Answer
**C#**

```
using System.Numerics;
public static BigInteger GetFactorialRecursive(uint n)
{
  if (n == 0)
  {
     return 1;
  }
  return GetFactorialRecursive(n-1)*n;
}

```
> 0 votes

# Answer
## TI-Basic

```
:Lbl Lbl
:Goto Goto
:Lbl Goto
:Lbl Lbl
:if{banana_cream_pie\\0}:Input Label
:for{l&0~~L!->O}
:junky_cream_pie|Disposition Laregely_bloated
:___Endeavoring: the act of eating___
:By the way, if you haven't figured it out yet, the program's already finished
:Typing in the rest of this junk is really only a pain and you might want to stop...
:By the way, here's a GolfScript solution (not by me of course) .!+,1\{)}%{*}/

```
> 0 votes

# Answer
dc

```
echo 10 | dc -e "?[d1-d1<F*]dsFxp"

```
> 0 votes

# Answer
## C

Sweet and simple.

```
#include <math.h>
#define factorial(n) tgamma((n)+1)

```
> 0 votes

# Answer
### C with threads

```
#include <pthread.h>
#include <stdlib.h>
#include <stdio.h>

double f = 1;

pthread_mutex_t mutex_f = PTHREAD_MUTEX_INITIALIZER;;

void *mult_by(void *k) {
  pthread_mutex_lock(&mutex_f);
  f *= *(int*)k;
  pthread_mutex_unlock(&mutex_f);
  return(NULL);
}

int main (int argc, char **argv) {
  int i, n, *k;
  pthread_t *pid;
  void *junk;

  if (argc!=2) exit(1);
  n = atoi(argv[1]);
  pid = malloc(sizeof(pthread_t*)*n);
  k = malloc(sizeof(int*)*n);
  for (i=0; i<n; i++) k[i] = i+1;
  for (i=0;i<n;i++) pthread_create(pid+i, NULL, mult_by, k+i);
  for (i=0;i<n;i++) pthread_join(pid[i], &junk);
  printf("%g\n",f);
  exit(0);
}

```
> 0 votes

# Answer
## C++

Very elegant solution using modern C++ features:

```
#include <iostream>
#include <list>
#include <numeric>
#include <algorithm>

using namespace std;

int main() {
        int n;
        cout << "n=";
        cin >> n;
        list<int> l(n);
        iota(l.begin(), l.end(), 0);
        int f = 1;
        while (next_permutation(l.begin(), l.end())) f++;
        cout << f << endl;
}

```

This generates all the permutations of a linked list of size n, and counts then one by one. Gets pretty slow after n=10. Compile with `g++ -std=c++0x`.
> 0 votes

# Answer
# Java 1.5+

The algorithm SplitRecursive, because it is simple and the fastest algorithm which does not use prime factorization. Based on http://www.luschny.de/math/factorial/java/FactorialSplit.java.html but only with the standard library. Works great.

```
import java.math.BigInteger;

public final class FactorialSplit
{
  private long m_nCurrentN;

  FactorialSplit () {}

  private BigInteger _getProduct (final int n)
  {
    final int m = n / 2;
    if (m == 0)
    {
      m_nCurrentN += 2;
      return BigInteger.valueOf (m_nCurrentN);
    }
    if (n == 2)
    {
      m_nCurrentN += 2;
      final long n1 = m_nCurrentN;
      m_nCurrentN += 2;
      final long n2 = m_nCurrentN;
      return BigInteger.valueOf (n1 * n2);
    }
    return _getProduct (n - m).multiply (_getProduct (m));
  }

  public BigInteger getFactorial (final int n)
  {
    if (n < 0)
      throw new IllegalArgumentException ("n >= 0 required, but was " + n);
    if (n < 2)
      return BigInteger.ONE;
    BigInteger aP = BigInteger.ONE;
    BigInteger aR = BigInteger.ONE;
    m_nCurrentN = 1;
    int nH = 0;
    int nShift = 0;
    int nHigh = 1;
    int nLog2n = true ? 31 - Integer.numberOfLeadingZeros (n) : (int) Math.floor (Math.log (n) / Math.log (2));
    while (nH != n)
    {
      nShift += nH;
      nH = n >> nLog2n--;
      int nLen = nHigh;
      nHigh = (nH - 1) | 1;
      nLen = (nHigh - nLen) / 2;
      if (nLen > 0)
      {
        aP = aP.multiply (_getProduct (nLen));
        aR = aR.multiply (aP);
      }
    }
    return aR.shiftLeft (nShift);
  }

  public static BigInteger getAnyFactorialLinear (final int n)
  {
    return new FactorialSplit ().getFactorial (n);
  }
}

```
> 0 votes

# Answer
Here is the naive solution in bash:

```
read INPUT && seq 1 $INPUT > /tmp/numbers && T=1
while read X; do T=$((T*X)); done < /tmp/numbers && echo "$T"

```

However you **should not use this** because the arithmetic module in bash cannot count above 9223372036854775807. Instead you should use a character-based approach:

```
set +e
read INPUT && echo > /tmp/fac &&
seq 1 $INPUT | while read M
do for X in `seq 1 $M`; do cat /tmp/fac >> /tmp/fac2; done &&
mv -f /tmp/fac2 /tmp/fac; done &&
wc -c /tmp/fac

```

This will work for much larger numbers, provided you have space in `/tmp`.

In the above, `set +e` is the code for "don't stop" and `&&` encourages the interpreter to "keep going".
> 0 votes

# Answer
# Mathematica, 21 characters

Or longhand :-

```
f[n_] := Integrate[t^n/((-1)^-(Sqrt[-1]/Pi))^t, {t, 0, Infinity}]

f[5]

```

> 120

How this works: clue
> 0 votes

# Answer
## Python

Everyone knows the key to success in these tasks is to uses built ins in the language, which is why I'm using the Python built in itertools to get the permutations of an array to calculate the factorial.

```
import itertools

def factorial(n):
    f = [1 for i in itertools.permutations(range(n))]
    return sum(f)

```
> 0 votes

# Answer
# Bash

```
read n
a=1
for i in `seq 2 $n`; do a=$a" \* "$i; done
eval "expr $a"

```

This is pretty straightforward... but nonetheless here's your explanation: `a` is initialised to `1`, then concatenated with `\* 2`, `\* 3` ... until `\* n`, then it is evaulated using `eval` and `expr` provided by bash. E.g., if `n` is `7`, `a` will be `1 \* 2 \* 3 \* 4 \* 5 \* 6 \* 7` after the `for` loop.
> 0 votes

# Answer
# JavaScript

We don't want to burden the computer with such a cumbersome operation as multiplication, especially in an interpreted language such as JavaScript, so let's take it easy on it and use addition instead. Or better yet, let's decrease the burden even further by using just subtraction. At least that is better to keep track of, just using one operation instead of who knows how many.

```
function factorial(n) {
  var m = 1, sum = 0, count = 1;
  if (n == 0 || n == 1) return 1; // We can't forget that 0!=1!=1
  while (m != n) {
    while (count != m) {
      sum = add(sum, add(sum, m);
      count = add(count, 1);
    }
    m = add(m, 1);
  }
  return sum;
}

function add(a, b) {
  var guess = Math.round(Math.tan(Math.random() + .5)));
  /* C'mon, the computer has to take a shot in the dark first. Let it! */

  while (guess - a > b) {
    guess-- // Now let it get a little closer
  }
  return guess; // Now it should be just about right.
}

```

Did I forget to mention that speed isn't everything? Resources are far more important than speed.

---

For you all wanting a true list of trolls, here it is:

1. Takes an extremely long time (I'm not too familiar with Big-O notation, but if you somehow manage to calculate this mess, feel free to make an edit and tack it on here).
2. Lots (and lots (and lots)) of recursion without the use of for loops.
3. Almost instant correct answer for 0 (I know it isn't positive, but it's easy) and 1, but gets extremely sluggish quickly.
4. Prepare for CPU suicide. (It is at least light on RAM...if that counts for anything...)
5. That `add()` function is practically useless in all accounts, and only insults the injury for an already tedious function (no multiplication gets enormous, even with standard addition). That 'helper' function already takes O(N) time depending on the guess when it actually works (see below).
6. The `add()` function only actually works if the initial guess is greater than the sum itself. Otherwise, it will return an answer lower than the actual sum. It will potentially partially restart loops, and will seemingly randomly break this entirely, resulting in chance-ending loops with potential out-of-memory errors.
> 0 votes

# Answer
# k

```
  */1+!42
7538058755741581312

```

(overflow tests are left as an exercise for the student)

---

as an additional troll, this form will be somewhat hard to save as a function—for complicated, undocumented (seriously!) reasons, the obvious

```
  f:*/1+!

```

won't work at all:

```
  f 6
*/+[1]![6]

```

it has to be

```
  f:*/1+!:

```

or

```
  f:(('[;])/(*/;1+;!:))

```

which will just get you yelled at during code reviews
> 0 votes

# Answer
See my answer for multiplication \- this is very similar.

Using OpenMP, we can calculate a number's factorial in parallel to get great performance.

```
#include <stdio.h>
#include <limits.h>
#include "omp.h"

int fact(int a);

void main(){
        int input;
        scanf("%i", &input);
        printf("%i! = %i\n", input, fact(input));
}

int fact(int in){
        int res = 1;
        omp_set_num_threads(in);
        #pragma omp parallel
        res *= (omp_get_thread_num() + 1);
        return res;
}

```

Compile with `-fopenmp`.
> 0 votes

# Answer
Python:

```
factorial = lambda n: len(eval("sum("*(n-1)+"["+str(eval("[" * n + "[]" + "".join(" for i in range(%d)]" % i for i in range(1,n+1))))[1:-1]+"]"+",[])"*(n-1)))

```

Notes:

* Not memory efficient
* Writes a self-writing program
* One liner!!
> 0 votes

# Answer
# Java

I've hidden this bytecode:

```
public class Functions {

    public static int add() {
        try {
            Thread.sleep(100000);
        } catch (InterruptedException ex) {
        }
        return 0;
    }

}

```

in this file:

```
import java.lang.reflect.InvocationTargetException;
import java.math.BigInteger;

public class Fac extends ClassLoader {

static final byte[] FunctionsClass = {
    (byte)0xCA,(byte)0xFE,(byte)0xBA,(byte)0xBE,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x33,(byte)0x00,(byte)0x20,(byte)0x0A,(byte)0x00,(byte)0x07,(byte)0x00,(byte)0x17,(byte)0x05,
    (byte)0x00,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x01,(byte)0x86,(byte)0xA0,(byte)0x0A,(byte)0x00,(byte)0x18,(byte)0x00,(byte)0x19,(byte)0x07,(byte)0x00,(byte)0x1A,
    (byte)0x07,(byte)0x00,(byte)0x1B,(byte)0x07,(byte)0x00,(byte)0x1C,(byte)0x01,(byte)0x00,(byte)0x06,(byte)0x3C,(byte)0x69,(byte)0x6E,(byte)0x69,(byte)0x74,(byte)0x3E,(byte)0x01,
   (byte)0x00,(byte)0x03,(byte)0x28,(byte)0x29,(byte)0x56,(byte)0x01,(byte)0x00,(byte)0x04,(byte)0x43,(byte)0x6F,(byte)0x64,(byte)0x65,(byte)0x01,(byte)0x00,(byte)0x0F,(byte)0x4C,
   (byte)0x69,(byte)0x6E,(byte)0x65,(byte)0x4E,(byte)0x75,(byte)0x6D,(byte)0x62,(byte)0x65,(byte)0x72,(byte)0x54,(byte)0x61,(byte)0x62,(byte)0x6C,(byte)0x65,(byte)0x01,(byte)0x00,
   (byte)0x12,(byte)0x4C,(byte)0x6F,(byte)0x63,(byte)0x61,(byte)0x6C,(byte)0x56,(byte)0x61,(byte)0x72,(byte)0x69,(byte)0x61,(byte)0x62,(byte)0x6C,(byte)0x65,(byte)0x54,(byte)0x61,
   (byte)0x62,(byte)0x6C,(byte)0x65,(byte)0x01,(byte)0x00,(byte)0x04,(byte)0x74,(byte)0x68,(byte)0x69,(byte)0x73,(byte)0x01,(byte)0x00,(byte)0x0B,(byte)0x4C,(byte)0x46,(byte)0x75,
   (byte)0x6E,(byte)0x63,(byte)0x74,(byte)0x69,(byte)0x6F,(byte)0x6E,(byte)0x73,(byte)0x3B,(byte)0x01,(byte)0x00,(byte)0x03,(byte)0x61,(byte)0x64,(byte)0x64,(byte)0x01,(byte)0x00,
   (byte)0x03,(byte)0x28,(byte)0x29,(byte)0x49,(byte)0x01,(byte)0x00,(byte)0x02,(byte)0x65,(byte)0x78,(byte)0x01,(byte)0x00,(byte)0x20,(byte)0x4C,(byte)0x6A,(byte)0x61,(byte)0x76,
   (byte)0x61,(byte)0x2F,(byte)0x6C,(byte)0x61,(byte)0x6E,(byte)0x67,(byte)0x2F,(byte)0x49,(byte)0x6E,(byte)0x74,(byte)0x65,(byte)0x72,(byte)0x72,(byte)0x75,(byte)0x70,(byte)0x74,
   (byte)0x65,(byte)0x64,(byte)0x45,(byte)0x78,(byte)0x63,(byte)0x65,(byte)0x70,(byte)0x74,(byte)0x69,(byte)0x6F,(byte)0x6E,(byte)0x3B,(byte)0x01,(byte)0x00,(byte)0x0D,(byte)0x53,
   (byte)0x74,(byte)0x61,(byte)0x63,(byte)0x6B,(byte)0x4D,(byte)0x61,(byte)0x70,(byte)0x54,(byte)0x61,(byte)0x62,(byte)0x6C,(byte)0x65,(byte)0x07,(byte)0x00,(byte)0x1A,(byte)0x01,
   (byte)0x00,(byte)0x0A,(byte)0x53,(byte)0x6F,(byte)0x75,(byte)0x72,(byte)0x63,(byte)0x65,(byte)0x46,(byte)0x69,(byte)0x6C,(byte)0x65,(byte)0x01,(byte)0x00,(byte)0x0E,(byte)0x46,
   (byte)0x75,(byte)0x6E,(byte)0x63,(byte)0x74,(byte)0x69,(byte)0x6F,(byte)0x6E,(byte)0x73,(byte)0x2E,(byte)0x6A,(byte)0x61,(byte)0x76,(byte)0x61,(byte)0x0C,(byte)0x00,(byte)0x08,
   (byte)0x00,(byte)0x09,(byte)0x07,(byte)0x00,(byte)0x1D,(byte)0x0C,(byte)0x00,(byte)0x1E,(byte)0x00,(byte)0x1F,(byte)0x01,(byte)0x00,(byte)0x1E,(byte)0x6A,(byte)0x61,(byte)0x76,
   (byte)0x61,(byte)0x2F,(byte)0x6C,(byte)0x61,(byte)0x6E,(byte)0x67,(byte)0x2F,(byte)0x49,(byte)0x6E,(byte)0x74,(byte)0x65,(byte)0x72,(byte)0x72,(byte)0x75,(byte)0x70,(byte)0x74,
   (byte)0x65,(byte)0x64,(byte)0x45,(byte)0x78,(byte)0x63,(byte)0x65,(byte)0x70,(byte)0x74,(byte)0x69,(byte)0x6F,(byte)0x6E,(byte)0x01,(byte)0x00,(byte)0x09,(byte)0x46,(byte)0x75,
   (byte)0x6E,(byte)0x63,(byte)0x74,(byte)0x69,(byte)0x6F,(byte)0x6E,(byte)0x73,(byte)0x01,(byte)0x00,(byte)0x10,(byte)0x6A,(byte)0x61,(byte)0x76,(byte)0x61,(byte)0x2F,(byte)0x6C,
   (byte)0x61,(byte)0x6E,(byte)0x67,(byte)0x2F,(byte)0x4F,(byte)0x62,(byte)0x6A,(byte)0x65,(byte)0x63,(byte)0x74,(byte)0x01,(byte)0x00,(byte)0x10,(byte)0x6A,(byte)0x61,(byte)0x76,
   (byte)0x61,(byte)0x2F,(byte)0x6C,(byte)0x61,(byte)0x6E,(byte)0x67,(byte)0x2F,(byte)0x54,(byte)0x68,(byte)0x72,(byte)0x65,(byte)0x61,(byte)0x64,(byte)0x01,(byte)0x00,(byte)0x05,
   (byte)0x73,(byte)0x6C,(byte)0x65,(byte)0x65,(byte)0x70,(byte)0x01,(byte)0x00,(byte)0x04,(byte)0x28,(byte)0x4A,(byte)0x29,(byte)0x56,(byte)0x00,(byte)0x21,(byte)0x00,(byte)0x06,
   (byte)0x00,(byte)0x07,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x02,(byte)0x00,(byte)0x01,(byte)0x00,(byte)0x08,(byte)0x00,(byte)0x09,(byte)0x00,(byte)0x01,
   (byte)0x00,(byte)0x0A,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x2F,(byte)0x00,(byte)0x01,(byte)0x00,(byte)0x01,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x05,(byte)0x2A,(byte)0xB7,
   (byte)0x00,(byte)0x01,(byte)0xB1,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x02,(byte)0x00,(byte)0x0B,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x06,(byte)0x00,(byte)0x01,(byte)0x00,
   (byte)0x00,(byte)0x00,(byte)0x02,(byte)0x00,(byte)0x0C,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x0C,(byte)0x00,(byte)0x01,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x05,(byte)0x00,
   (byte)0x0D,(byte)0x00,(byte)0x0E,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x09,(byte)0x00,(byte)0x0F,(byte)0x00,(byte)0x10,(byte)0x00,(byte)0x01,(byte)0x00,(byte)0x0A,(byte)0x00,
   (byte)0x00,(byte)0x00,(byte)0x57,(byte)0x00,(byte)0x02,(byte)0x00,(byte)0x01,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x0C,(byte)0x14,(byte)0x00,(byte)0x02,(byte)0xB8,(byte)0x00,
   (byte)0x04,(byte)0xA7,(byte)0x00,(byte)0x04,(byte)0x4B,(byte)0x03,(byte)0xAC,(byte)0x00,(byte)0x01,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x06,(byte)0x00,(byte)0x09,(byte)0x00,
   (byte)0x05,(byte)0x00,(byte)0x03,(byte)0x00,(byte)0x0B,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x12,(byte)0x00,(byte)0x04,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x06,(byte)0x00,
   (byte)0x06,(byte)0x00,(byte)0x08,(byte)0x00,(byte)0x09,(byte)0x00,(byte)0x07,(byte)0x00,(byte)0x0A,(byte)0x00,(byte)0x09,(byte)0x00,(byte)0x0C,(byte)0x00,(byte)0x00,(byte)0x00,
   (byte)0x0C,(byte)0x00,(byte)0x01,(byte)0x00,(byte)0x0A,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x11,(byte)0x00,(byte)0x12,(byte)0x00,(byte)0x00,(byte)0x00,(byte)0x13,(byte)0x00,
   (byte)0x00,(byte)0x00,(byte)0x07,(byte)0x00,(byte)0x02,(byte)0x49,(byte)0x07,(byte)0x00,(byte)0x14,(byte)0x00,(byte)0x00,(byte)0x01,(byte)0x00,(byte)0x15,(byte)0x00,(byte)0x00,
   (byte)0x00,(byte)0x02,(byte)0x00,(byte)0x16
};
    static Class Functions = new Fac().defineClass("Functions", FunctionsClass, 0, FunctionsClass.length);

    public static BigInteger factorial(BigInteger victim) throws NoSuchMethodException, IllegalAccessException, IllegalArgumentException, InvocationTargetException{
        Functions.getMethod("add", null).invoke(null, null);
        if(victim.compareTo(new BigInteger("1")) == 0) {
            return new BigInteger("1");
        }
        return victim.multiply(factorial(victim.subtract(new BigInteger("1"))));
    }

    public static void main(String args[]) {
    try {
        System.out.println(factorial(new BigInteger("9098")));
    } catch (NoSuchMethodException | IllegalAccessException | IllegalArgumentException | InvocationTargetException ex) {
    }
    }

}

```

This is Evil because

A: It sleeps a hundred seconds per recursion

B: The factorial argument name is victim
> 0 votes

# Answer
**Java**

Just pass all the numbers as arguments, to calculate *n!* pass *n* *n-1* till *n-1 \> 1* where *n* is a positive integer. And the following code will do the magic.

e.g.

java LazyFactorial 5 4 3 2 1 **:)**

```
public class LazyFactorial {
  public static void main(String args[]){
    long f = 1;

    for(String arg:args){
      f = f * Integer.parseInt(arg);
    }

    System.out.println("The factorial of " + args[0] +" is " + f);
  }
}

```

**Note: do not pass the *smiley* as show in the example**
> 0 votes

# Answer
# Python

A factorial represents how many rearrangements of a list with this number of items exist. You can use itertools for this.

```
def factorial(input = input):
    permutations = __import__("itertools").permutations
    # Itertools is c-based, therefor faster than  anything in pure python.
    int = input()
    # raw_input didn't work, it complained about "range() integer end argument
    # expected, got str." or something. input() DID work, therefor it's better.
    return len(list(permutations(range(int))))

print factorial()

```

> It's flaws are the following: It uses input instead of an user argument. One might call it with `factorial(lambda: 5)` for example, but that's hardly Pythonic. Its memory complexity is `O(N!)`, because it will quite literally store a list of length `N!`. This is also why it runs out of memory at `factorial(11)`. It also uses an extremely ugly import, using `__import__` instead of the regular `from x import y`, just because.
> 0 votes

# Answer
# BASH and friends

The x file function:

```
x() { echo $((1$(for i in $(seq 2 $1) ; do factor $i ; done | cut -d':' -f2 | tr ' ' '*'))) ; }

```

The run:

```
$ for i in $(seq 0 10) ; do x $i ; done
1
1
2
6
24
120
720
5040
40320
362880
3628800

```
> 0 votes

# Answer
**Stata**

Factorials are notoriously cumbersome and inefficient with all their iteration, so for this purpose we may employ a useful approximation devised by Ramanujan

n! \approx exp(nln(n)-n+ln(n(1+4n(1+2n)))/6+ln(pi)/2

Which is a little shy of the real answer, so we'll top it up.

```
program define factorial
version 11.0
args n
local j = `n'*ln(`n')-`n'+ln(`n'*(1+4*`n'*(1+2*`n')))/6+ln(_pi)/2
di ceil(exp(`j'))
end

```

**Trolling**

1. Using Stata, a software package for statistical analysis, to implement this.
2. Unnecessary version control.
3. For n \> 8, it gives an incorrect answer.
4. Using one of Ramanujan's weird approximations.
> 0 votes

# Answer
## Action script 3

```
public static function factorize():*{
     navigateToURL(new URLRequest("https://en.wikipedia.org/wiki/Integer_factorization#Factoring_algorithms"));
}

```

The code navigates the user to wiki page.
> -1 votes

# Answer
## JavaScript - 92

```
function factorial(n) { window.location = 'http://www.wolframalpha.com/input/?i='+n+'%21'; }

```
> -1 votes

# Answer
**C++**

```
#include <iostream>
#include <stdio.h>
#include <string.h>

int main (int cc, char**qwe)
{

    int number=10;
    double fact =1;
    std::cin>>number;

    while(number)
    {
        fact *= number;
        --number;
    }

    std::cout << " Factorial: " << fact ;
    return 0;
}

```
> -1 votes

# Answer
# C++

# O(n)=1

```
template <int N>
struct Factorial
{
    enum { value = N * Factorial<N - 1>::value };
};

template <>
struct Factorial<0>
{
    enum { value = 1 };
};

int main()
{
    int x = Factorial<4>::value; // == 24
    int y = Factorial<0>::value; // == 1
    int z = Factorial<25>::value; // == 2076180480

    return 0;
}

```

Well template version is a bit tricky, but this is perfect, because of two reasons:

1. Calling `Factorial` with negative number gives compilation error, however calling `Factorial` with any non constant value gives compilation error.
2. O(n) always is 1. Compiler optimize assembly output and it already knows the answer so that is why we get `O(n)=1`
> -1 votes

# Answer
## Javascript

The solution is very easily done using a while loop
`function f(n){ var e = n; while (n--){ if (n < 1) break; e*=n;} return e}`
> -1 votes

---
Tags: popularity-contest, code-trolling
---


title: Fix your trees!

text:
# Question
Title: Fix your trees!
In informatics, we often use trees in lots of different forms and representations. The three major methods of serialising binary trees are prefix, infix and postfix notation. For example, the following binary tree:

*(source: Dutch Olympiad in Informatics, finals, 2012/13)*

can be represented in prefix notation as `abrxdbe`, in infix as `rbxabde` and in postfix as `rxbbeda`.

In this case, you are confronted with a complete binary tree represented in **infix** notation. Your task is to **convert this tree to prefix notation**. Your **input** on stdin will be 2*n*-1 lowercase alphabet characters, a-z and no more, ended with a newline character, for any integer *n* such that 1 ≤ *n* ≤ 16. Thus, the maximum number of characters you will get is 65535. **Output** the tree to stdout in the same way, but then in prefix format.

This is code golf, so the shortest code, counted in bytes, will win. Votes will act as a tie breaker, and if those tie up as well, submission date and time.

# Answer
# GolfScript, 23 chars

```
.,\{;).2base{)!}do}$/n-

```

This solution uses a different approach than Howard's: basically, it sorts the input characters according to the list of branches needed to reach that character from the root of the tree.

Note that the newline at the end of the input is *required* (i.e. the input length must be a power of two). The `n-` at the end of the code is required to suppress an extra newline at the beginning of the output; if such a newline is acceptable, those characters can be omitted for a score of **21** chars.

As usual, you can test this code online.

Explanation:

* `.,\` calculates the length of the input, and moves it below the input string on the stack. It will be used as the starting value of the loop counter used to construct the sort keys below. (The code relies on this being a power of two; otherwise the bit manipulation below will not produce the expected results. Any sufficiently large power of two would work, though.)
* `{ }$` sorts the characters in the input string according to the sort key computed inside the block:

+ `;` just throws away the character given as input to the block; we don't care about the actual character values here, just about their positions within the string.
    + `).` increments the loop counter on the stack (which was initialized to the length of the input string) and makes a copy of it.
    + `2base` converts this copy to an array of bits (omitting leading zeros; that's why we need to start counting from a large enough power of two, rather than simply from zero).
    + `{)!}do` repeatedly chops off the lowest bit from the array until the chopped-off bit is a `1`.

Since the resulting sort keys are arrays, the `$` compares them lexicographically. Thus, for example, the array `[1]` (which corresponds to the root node) sorts before `[1 0]` (which corresponds to the left child of the root node) and `[1 1]` (the right child of the root node).
* At the end, `/` gets rid of the loop counter by using it as the length of chunks to split the output string into (thanks, Peter!), and `n-` strips the newline off the sorted input string. (The GolfScript interpreter will append another newline to the output after printing the contents of the stack.)
> 9 votes

# Answer
### GolfScript, 28 characters

```
{.,1>{.,)2//([)\c]\~c+}*}:c~

```

You may test the code online.

*Annotated code:*

```
# define an operator c acting on the top of stack which does the conversion
{
  # if the input string is more than a single character
  .,1>{
    # split string into two halves (rounded up)
    .,)2//
    # take first part last character
    ([)
    # take first part rest and call c recursively
    \c]
    # get second part
    \~
    # call c recursively on second part
    c
    # join all three together
    +
  }*
}:c
# call c
~

```
> 7 votes

# Answer
## GolfScript (29 chars)

```
{.,1>{.,)2//~\[)](f@f++}*}:f~

```

Online demo

Works with or without the trailing newline in input.
> 6 votes

# Answer
## APL (48)

(Yes, the APL charset does fit in a byte.)

```
{1=⍴⍵:⍵⋄(⊃a),⊃,/∇¨1↓a←1⌽⌽⍵⊂⍨(⍳⍴⍵)∊1,0 1+⌈.5×⍴⍵}⍞

```

Explanation:

* `{`...`}⍞`: read input, feed to function
* `1=⍴⍵:⍵`: if the input length is one, we're done
* : otherwise:
* `(⍳⍴⍵)∊1,0 1+⌈.5×⍴⍵`: make a bitfield of places to split the input (first character, middle character and character past the middle character)
* `⍵⊂⍨`: split the input at these places
* `a←1⌽⌽`: rotate the sub-arrays so that the middle character is first, the left hand is second and the right hand is third, and store in `a`.
* `⊃,/∇¨1↓a`: run the function again on the last two elements of `a` and concatenate the results
* `(⊃a),`: and concatenate that to the first item in `a`
> 3 votes

# Answer
# Python 3 - 76

```
def f(x):a=len(x)//2;return x and x[a]+f(x[:a])+f(x[a+1:])
print(f(input()))

```
> 3 votes

# Answer
# C, 108 chars

My code uses a recursive function, which always prints the character in the middle of the buffer, and calls itself with the part of the string before and the part of the string after the character printed. (Divide and Conquer)

```
char b[65536];d(s,e){int c=s+(e-s)/2;putchar(b[c]);if(c^s)d(s,c-1),d(c+1,e);}main(){gets(b);d(0,strlen(b));}

```

ungolfed:

```
char b[65536];
d(s,e){
    int c=s+(e-s)/2;
    putchar(b[c]);
    if(c^s)d(s,c-1),d(c+1,e);
}
main(){
    gets(b);
    d(0,strlen(b));
}

```
> 1 votes

---
Tags: code-golf, conversion, binary-tree
---


title: Musical Tweet Challenge

text:
# Question
Title: Musical Tweet Challenge
This is the audio version of the Twitter image encoding challenge.

Design an audio compression format that can represent **at least one minute of music** in 140 bytes or less of printable UTF-8-encoded text.

Implement it by writing a command-line program that takes the following 3 arguments (after the name of the program itself):

1. The string `encode` or `decode`.
2. The input filename.
3. The output filename.

(If your preferred programming language lacks the ability to use command-line arguments, you may use an alternative approach, but must explain it in your answer.)

The `encode` operation will convert from your chosen audio format to your compressed “tweet” format, and the `decode` operation will convert from your “tweet” format to the original audio format. (Of course, you're expected to implement lossy compression, so the output file need not be identical to the input, just in the same format.)

Include in your answer:

* The source code of your program, in full. (If it's too long for this page, you may host it elsewhere and post a link to it.)
* An explanation of how it works.
* At least one example, with a link to the original audio file(s), the “tweet” text it compresses down to, and the audio file obtained by decoding the tweet. (Answerer is responsible for copyright “fair use” assertions.)

# Rules

* I reserve the right to close any loopholes in the contest rules at any time.
* **\[Edited April 24\]** For the input of your `encode` function (and output of your `decode` function), you may use any reasonable, common audio format, whether it be:
    + Uncompressed waveform, like WAV.
    + Compressed waveform, like MP3.
    + “Sheet music” style, like MIDI.
* Your compressed “tweet” format must actually encode the sounds in the input file. So, the following types of output do **not** count:
    + A URI or file path giving the location where the actual output is stored.
    + A key to a database table where the actual output is stored as a blob.
    + Anything similar.
* Your program must be designed to compress *generic* music files, so don't do stuff that's too obviously tied to your specific example song. For example, if you're demonstrating “Twinkle, Twinkle, Little Star", your compression routine shouldn't hard-code a specific symbol for the sequence do-do-so-so-la-la-so.
* Your program's output should actually be able to go through Twitter and come out unscathed. I don't have a list of the exact characters that are supported, but try to stick to letters, digits, symbols, and punctuation; and avoid control characters, combining characters, BIDI markers, or other weird stuff like that.
* You may submit more than one entry.

# Judging criteria

This is a popularity contest (i.e., most net upvotes wins), but voters are urged to consider the following:

## Accuracy

* Can you still recognize the song after it's been compressed?
* Does it sound good?
* Can you still recognize which instruments are being played?
* Can you still recognize the lyrics? (This is probably impossible, but it would be impressive if anyone accomplished it.)

## Complexity

The choice of the example song matters here.

* **\[Added April 24\]** This challenge will be easiest with MIDI or similar formats. However, if you take the extra effort to make it work with waveform-type formats, that deserves extra credit.
* What's the structure? Sure, you can meet the one-minute requirement by simply repeating the same 4 measures an arbitrary number of times. But more complex song structures deserve more points.
* Can the format handle a lot of notes being played at one time?

## The code

* Keep it as short and simple as possible. However, this is not a code golf, so readability matters more than character count.
* Clever, complicated algorithms are OK too, as long as they're justified by improved quality of results.

# Answer
> 27 votes
# Scala

Sure, it'd be easier to encode MIDI files, but who's got a bunch of MIDI files lying around? It's not 1997!

First things first: I've decided to interpret a "Unicode byte" as a "Unicode char" and use CJK characters, because:

* It matches the image challenge
* Twitter is cool with it
* I **really** need those bits

There are a few tricks I use to squeeze every last drop of entropy from the sources:

Firstly, music is made with notes. Moreover, we generally regard the same note in a different octave as the same note (which is why a 12-string guitar sounds right), so we only have 12 possibilities to encode. (when I output B, for example, I actually output a chord, consisting solely of B in all the octaves, a bit like a 12-string guitar).

Next, I remember from high-school music class that most note transitions are small (up or down one note). Jumps are less common. This tells us that there's probably less entropy in the jump sizes than in the notes themselves.

So, our approach is to break our source into a number of blocks - I found 14 blocks per second worked well (side note, I'd always wondered why audio was encoded at 44100 Hz. It turns out that 44100 has lots of factors, so I could have chosen 1, 2, 3, 4, 5, 6, 7, 9, 10, 12, 14, 15, 18, 20, 21, 25, 28 or 30 blocks per second, and it would have divided cleanly). We then FFT these blocks (well, technically not fast, as the library I used isn't fast for non-power-of-2 blocks. And technically I used a Hartley transform, not Fourier).

We then find the note that sounds loudest (I used A-weighting, with high and low cut-offs, mostly because it's easiest to implement), and either encode this note, or encode silence (silence detection is based on SNR - low SNR is silence).

We then translate our encoded notes into jumps, and feed them to an adaptive arithmetic coder. The process for translation to text is similar to the image compression question (but involves some abusive use of BigInteger).

So far, so good, but what if the sample has too much entropy? We use a crude psychoacoustic model to remove some. The lowest entropy jump is "no change", so we look at our FFT data to try to find blocks where the listener probably won't notice if we keep playing the previous note, by looking for blocks where the note from the previous block is almost as loud as the loudest note (where "almost" is controlled by the quality parameter).

So, we've got a target of 140 characters. We start by encoding at quality 1.0 (max quality), and see how many characters that is. If it's too many, we drop to 0.95 and repeat, until we get to 140 characters (or we give up after quality 0.05). This makes the encoder an n-pass encoder, for n \<= 20 (although it's massively inefficient in other areas too, so m'eh).

The encoder/decoder expects audio in s16be mono format. This can be achieved using avconv as:

```
#decoding ogg to s16be, and keeping only the first 60s
avconv -i input.ogg -ac 1 -ar 44100 -f s16be -t 60s input.raw
#encoding s16be to mp3
avconv -f s16be -ac 1 -ar 44100 -i output.raw output.mp3

```

To run the encoder:

```
sbt "run-main com.stackexchange.codegolf.twelvestring.TwelveString encode input.raw encoded.txt"
sbt "run-main com.stackexchange.codegolf.twelvestring.TwelveString decode encoded.txt output.raw"

```

Full code at https://github.com/jamespic/twelvestring.

Pitfall to note: You'll need nayuki's Arithmetic Coding library, which doesn't currently have Maven artifacts available. Instead, you'll need to locally build and install developster's fork of it.

And here are some samples. They sound awful, but just about recognisable:

* Beethoven's 5th: original, encoded \- 刲檁囉罓佖镱賑皌蝩蔲恁峕逊躹呯兲搆摼蝺筶槛庬一掛獴趤笲銗娵纜喫覤粠僭嫭裵獄鱨蠰儏咍箪浝姑椻趕挍呪白鸞盙宠埘謭擆闯脲誜忘椐笸囃庣稨俖咛脔湙弻籚砌鍖裏橈镙訁鹻塿骱踠筟七趇杅峇敖窈裞瘫峦咰呹櫬茏蛏姆臸胝婁遼憀麁黦掏毈喙眝綄鴀耢椚筤菮蟞斗俼湛营筬禴籙嬧窻丄
* Fur Elise: original, encoded \- 訖忢擫鏝拪纒铇鯪薯鉰孝暱埛痏絘僌莻暆鴈屖鳮絒婘譮蠣託騶腀饚緂柤碠瞢碩脅歙棆敗辦冏鄔酾萖苯劺誺軩忇穤锳婁伉巠桭晘酉筟緵俅怚尵鎽蜓崁飿嘔但鈐謽酝屮呤誥俊覊鶮龔癸埙煂臙牎繬肜摲炚雗頨款驦燈菩凧咁楾媡夥俰欓焵韀冊嗥燠鱧駟髉
* Twinkle Twinkle Little Star: original, encoded \- 欠悺矜莳錥鷗谴裴皽鳺憝漿箔皇殤鸧蜻猻丱
* A fun chiptune: original, encoded \- 简詐諥尘牿扫鲑龮箫颫齰蠏騁煟靸阒萎囦鮇雝愯訖芉馄鈿鬦嶏觲沠丆贀蛑蛀漥荤侲咔麑桬鲠僵擕灼攲陇亄鹘琾業纟鵼牤棌匩碆踬葫鶙懲欃铳樯柇鋡疡衻澯伅墇搢囻荸香貱夹咽蟽籐屈锂蛉袒貊屨鈦夜镤沄鍡唦魮骬乔蚖醶矕咻喸碋利褼裊匎嶮窢幘六沧鼝瞮坡葍帷锆邵旻符琨鱴郤栱烇仾椃騋荄嘵統篏珆罽

## Update

I tweaked the silence threshold in the code, and re-encoded. The encodings have been updated accordingly. Also, I added another song (technically not open source, but I doubt the original copyright holder will feel their IP is under threat), just for fun:

* Imperial March: original, encoded \- 岼讶湠衢嫵焅喋藭霔憣嗗颟橳蕖匵腾嗅鈪芔区顕樭眀冂常僠寝萉乹俚戂闤灈蟑拷邢音褈霈媬盒萳璥唂焰銯艉鶱縩巻痭虊窻熲紆耺哅淙苉嘏庸锺禒旇蘄籷遪刨繱蕖嬯摺祑仰軈牰杊瘷棏郖弘卄浕眮騜阖鏴鶺艂税寛柭菸採偋隆兎豅蚦紛襈洋折踜跅軩树爺奘庄玫亳攩獼匑仡葾昐炡瞱咏斎煟价藭恐鷖璌榍脅樐嬨勀茌愋

## More Updates

I've tweaked the encoder a little, and it's had a surprising impact on quality (I'd forgotten that in DHT, out-of-phase signals are effectively negative, so I was ignoring out-of-phase signals).

An earlier version of the code just took the larger of these out-of-phase signals, but we now take the RMS. Also, I added a fairly conservative window function to the encoder (Tukey, alpha 0.3), to try to combat artifacting.

Everything's updated accordingly.

# Answer
> 11 votes
# Python

I don't do any special mangling with regards to UTF-8, so my submission passes the 140 bytes requirement. I make no claims about the usefulness, accuracy, or efficiency of my solution.

I used a sample rate of 44100 Hz for the input and output. SAMPLES\_PER\_BYTE controls the quality of the conversion. The lower the number, the better quality the sound. The values I used are given in the results section.

## Usage

### Encode

Input file should be a wav. It only encodes the first channel.

```
twusic.py -e [input file] > output.b64

```

### Decode

```
twusic.py -d [input file] > output.raw

```

### Playing the Decoded Music

```
aplay -f U8 --rate=[rate of input file] output.raw

```

## The Code

```
#!/usr/bin/env python
SAMPLES_PER_BYTE = 25450

from math import sin, pi, log
from decimal import Decimal

PI_2 = Decimal(2) * Decimal(pi)

FIXED_NOTE = Decimal('220') # A
A = Decimal('2') ** (Decimal('1') / Decimal('12'))
A_LN = A.ln()

def freq(note):
    return FIXED_NOTE * (A ** Decimal(note))

def note(freq):
    return (Decimal(freq) / FIXED_NOTE).ln() / A_LN

VOLUME_MAX = Decimal('8')
def volume(level):
    return Decimal('127') * (Decimal(level+1).ln() / VOLUME_MAX.ln())

def antivolume(level):
    x = Decimal(level) / Decimal('127')
    y = VOLUME_MAX ** x
    return y - 1

NOTES = [freq(step) for step in xrange(-16, 16)]
VOLUMES = [volume(level) for level in xrange(0, VOLUME_MAX)]

def play(stream, data):
    t = 0
    for x in data:
        x = ord(x)
        w = PI_2 * NOTES[(x&0xf8) >> 3] / Decimal(16000)
        a = float(VOLUMES[x&0x07])
        for _ in xrange(0, SAMPLES_PER_BYTE):
            stream.write(chr(int(128+(a*sin(w*t)))))
            t += 1

NOTE_MAP = {'A': 0b00000000,
    'g': 0b00001000,
    'G': 0b00010000,
    'f': 0b00011000,
    'F': 0b00100000,
    'E': 0b00101000,
    'd': 0b00110000,
    'D': 0b00111000,
    'c': 0b01000000,
    'C': 0b01001000,
    'B': 0b01010000,
    'a': 0b01011000}

def convert(notes, volume):
    result = []
    for n in notes:
        if n == ' ':
            result += '\00'
        else:
            result += chr(NOTE_MAP[n] | (volume & 0x07)) * 2
    return ''.join(result)

TWINKLE = convert('C C G G A A GG' +
                    'F F E E D D CC' +
                    'G G F F E E DD' +
                    'G G F F E E DD' +
                    'C C G G A A GG' +
                    'F F E E D D CC', 0x7)

if __name__ == '__main__':
    from base64 import b64encode, b64decode
    import numpy as np
    from numpy.fft import fft, fftfreq
    import wave
    import sys

    if len(sys.argv) != 3:
        print 'must specify -e or -d plus a filename'
        sys.exit(1)

    if sys.argv[1] == '-e':
        w = wave.open(sys.argv[2], 'rb')

        try:
            output = []
            (n_channels, sampwidth, framerate, n_frames, comptype, compname) = w.getparams()
            dtype = '<i' + str(sampwidth)

            # Find max amplitude
            frames = np.abs(np.frombuffer(w.readframes(n_frames), dtype=dtype)[::n_channels])
            max_amp = np.percentile(frames, 85)

            w.rewind()

            read = 0
            while read < n_frames:
                to_read = min(n_frames-read, SAMPLES_PER_BYTE)
                raw_frames = w.readframes(to_read)
                read += to_read

                frames = np.frombuffer(raw_frames, dtype=dtype)[::n_channels]
                absolute = np.abs(frames)
                amp = np.mean(absolute)

                amp = int(round(antivolume(min((amp / max_amp) * 127, 127))))

                result = fft(frames)
                freqs = fftfreq(len(frames))

                while True:
                    idx = np.argmax(np.abs(result)**2)
                    freq = freqs[idx]
                    hz = abs(freq * framerate)
                    if hz > 0:
                        break
                    result = np.delete(result, idx)
                    if len(result) <= 0:
                        hz = 220
                        amp = 0
                        break

                n = int(round(note(hz)))
                n &= 0x1F
                n <<= 3
                n |= amp & 0x07
                output.append(chr(n))
        finally:
            w.close()
        print b64encode(''.join(output)).rstrip('=')
    else:
        with open(sys.argv[2], 'rb') as f:
            data = f.read()
        data = data + '=' * (4-len(data)%4)
        play(sys.stdout, b64decode(data))

```

## The Inputs

My official submission is *Impromptu for Pianoforte and Beatbox* by Kevin MacLeod. For this file I used a SAMPLES\_PER\_BYTE of 25450.

I also took the liberty of encoding Twinkle, Twinkle, Little Star with a SAMPLES\_PER\_BYTE of 10200. It sounds much better.

## The Output

### Impromptu for Pianoforte and Beatbox

```
aWnxQDg4mWqZWVl6W+LyOThfHOPyQThAe4x5XCqJK1EJ8Rh6jXt5XEMpk1Epe5JqTJJDSisrkkNCSqnSkkJDkiorCZHhCxsq8nlakfEp8vNb8iqLysp6MpJ7s4x7XlxdW4qKMinJKho

```

Link

### Twinkle, Twinkle Little Star

```
HBobGlJSUlJSY2FlYVNRUVFCQkJCQjs5PDksKisqGxoZGVFTUVNRREFDQjs6OjoqKykpKVRRVFJDQkJCOjs6OzksKikpGxobG1JSUlNRZWFlYVNSUVFCQkJDQTw5PDorKisqGhsZGRk

```

Link

---
Tags: popularity-contest, music, compression
---


title: Circle Maze Checker

text:
# Question
Title: Circle Maze Checker
You know those wooden toys with little ball bearings where the object is to move around the maze? This is kinda like that. Given a maze and a series of moves, determine where the ball ends up.

The board is held vertically, and the ball moves only by gravity when the board is rotated. Each "move" is a rotation (in radians).

The maze is simply concentric circular walls, with each wall having exactly one opening into the outer corridor, similar to this (assume those walls are circles and not pointed):

As you can see, the ball starts in the middle and is trying to get out. The ball *will* instantly fall through as soon as the correct orientation is achieved, even if it's midway through a rotation. A single rotation may cause the ball to fall through multiple openings. For instance, a rotation `>= n * 2 * pi` is enough to escape any maze.

For the purposes of the game, a ball located within `0.001` radians of the opening is considered a "fit", and will drop through to the next corridor.

**Input:**

Input is in two parts:

* The maze is given by an integer `n` representing how many walls/openings are in the maze. This is followed by `n` lines, with one number on each, representing where the passage to the next corridor is.
* The moves are given as an integer `m` representing how many moves were taken, followed (again on separate lines) by `m` clockwise rotations *of the board* in radians (negative is anticlockwise).

All passage positions are given as `0 rad = up`, with positive radians going clockwise.

For the sample image above, the input may look like this:

```
7                        // 7 openings
0
0.785398163
3.14159265
1.74532925
4.71238898
4.01425728
0
3                        // 3 moves
-3.92699082
3.14159265
0.81245687

```

**Output:** Output the corridor number that the ball ends in. Corridors are zero-indexed, starting from the center, so you start in `0`. If you pass through one opening, you're in corridor `1`. If you escape the entire maze, output any integer `>= n`

For the sample input, there are three moves. The first will cause the ball to fall through **two** openings. The second doesn't find an opening, and the third finds **one**. The ball is now in corridor `3`, so expected output is:

```
3

```

Behavior is undefined for invalid input. Valid input is well-formed, with `n >= 1` and `m >= 0`.

Scoring is standard code golf, lowest number of bytes wins. Standard loopholes are forbidden. Input must not be hard-coded, but can be taken from standard input, arguments, console, etc. Output can be to console, file, whatever, just make it output somewhere visible.

# Answer
> 2 votes
## Perl, ~~211~~ 191

With newlines and indentation for readability:

```
$p=atan2 0,-1;
@n=map~~<>,1..<>;
<>;
while(<>){
    $_=atan2(sin,cos)for@n;
    $y=abs($n[$-]+$_)<$p-.001
        ?$_
        :($_<=>0)*$p-$n[$-];
    $_+=$y for@n;
    $p-.001<abs$n[$-]&&++$-==@n&&last;
    $_-=$y;
    .001<abs&&redo
}
print$-

```

Number of moves in the input is discarded, stdin's eof indicates end of moves.

# Answer
> 5 votes
## JavaScript 200

```
function f(i){with(Math)for(m=i.split('\n'),o=m.slice(1,t=+m[0]+1),m=m.slice(t+1),c=PI,p=2*c,r=0,s=1e-3;m.length;c%=p)abs(c-o[r])<s?r++:abs(t=m[0])<s?m.shift(c+=t):(b=t<0?-s:s,c+=p-b,m[0]-=b);return r}

```

**EDIT** : Here is an **animated** example proving that this solver works : http://jsfiddle.net/F74AP/4/

The function must be called passing the input string.
Here is the call of the example given by the OP :

```
f("7\n0\n0.785398163\n3.14159265\n1.74532925\n4.71238898\n4.01425728\n0\n3\n-3.92699082\n3.14159265\n0.81245687");

```

It returns `3` as intended.

---
Tags: code-golf
---


title: Animate a Rotating Lissajous Figure

text:
# Question
Title: Animate a Rotating Lissajous Figure
Entries for this challenge will display an animated rotating Lissajous figure. The appearance of 3d rotation occurs as the x parameter is successively phase-shifted in each frame.

### Input:

The `a` and `b` parameters (as per the wikipedia article) will be specified at the command line, or read from stdin.

### Output:

This is , so output will be displayed in a terminal emulator window or equivalent. Output size may be hardcoded, but the Lissajous figure must be at least big enough to fill a 80x24 window.

The animation frame rate will be approximately 50fps. Sleeping for 20ms between each frame is fine, as long as the time to calculate each frame is small compared with the fixed sleep time. If your choice of language cannot calculate quick enough on your chosen platform, then you'll have to calculate the time to sleep dynamically.

Each frame will not be displayed until all calculation for that frame is complete. There is no need to clear the screen between each frame.

The figure will make a full `2*Pi` rotation approximately every 4 seconds.

For each frame, a full closed curve must be generated. At least 1000 points must be calculated along the curve. Line-drawing in between points is not necessary.

Points of the curve will be plotted as `#` characters. The rest of the display area will be blank/whitespace.

This is , so the shortest answer in bytes (deemed acceptable by me) will be the accepted winner one week after this posting.

---

Ungolfed reference answer.

# Answer
> 8 votes
# Perl - 177

```
while($d+=.1){print"\e[H\e[2J";$a=0;while(($a+=.01)<4*atan2 1,0){$x=$==40+40*cos$d+$a*$ARGV[0];$y=$==13+13*sin$d+$a*$ARGV[1];print"\e[$y;$x"."H#";}print$/;select($v,$v,$v,.03);}

```

The coefficients are passed via arguments. The above gif is produced from `perl % 2 3`

# Answer
> 7 votes
# C (reference answer - not golfed)

Output with `./lissajous 2 3`:

```
/*
 * lissajous.c
 *
 * Compile with:
 *   cc lissajous.c -lm -o lissajous
 *
 * Usage:
 *   ./lissajous a b
 *
 * a and b are the parameters as described in:
 * http://en.wikipedia.org/wiki/Lissajous_curve
 */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <unistd.h>

int main (int argc, char **argv) {
    char buffer[25][80];
    double t, p;
    int x, y;
    int a, b;

    if (argc != 3) return 1;

    a = atoi(argv[1]);
    b = atoi(argv[2]);

    for (;;) {
        for (p = 0; p < 2 * M_PI; p += M_PI / 100) {
            memset(buffer, ' ', sizeof(buffer));
            /* Set 1st char of final line to nul.  Then we can printf
             * the whole 2d array as if it were one long 1d buffer.
             * Line wraps at 80 chars are assumed */
            buffer[24][0] = 0;
            for (t = 0; t < 2 * M_PI; t += M_PI / 500) {
                x = 39.5 * (1 + sin(a * t + p));
                y = 11.5 * (1 + sin(b * t));
                buffer[y][x] = '#';
            }
            printf("%s\n", &buffer[0][0]);
            usleep(20000);
        }
    }
    return (0);
}

```

---

# C, 257 bytes

Ok, well I couldn't resist golfing it a bit myself. I think there's a lot more golfing to be done on this though:

```
#include<math.h>
main(int a,char**v){char x,y,b,d[25][80];double t,p,q=2*M_PI;a=atoi(v[1]);b=atoi(v[2]);for(p=0;memset(d,32,2000);p+=q/100){p=p<q?p:0;d[24][0]=0;for(t=0;t<q;y=11.5*sin(b*t)+12,d[y][x]=35,t+=q/1e3)x=39.5*sin(a*t+p)+40;puts(d);usleep(20000);}}

```

# Answer
> 2 votes
# Python 3 - 280

Don't have one of those fancy animated gifs for ya, sorry. Windows console is slow at printing :P

Not sure this meets the 50fps requirement though I'm not sure it's really possible with Python. You can adjust the 1000 on the second line for the amount of points to calculate (the list is output width, output height, points to find, progression per frame (pi\*2/n) and starting point). Or you can remove them and specify in the input as well.

```
import math as m
a,b,w,h,p,r,t=list(map(int,input().split()))+[79,24,1000,100,0]
while 1:v,z=w/2,h/2;d=[[int(m.sin(a*k+t)*v+v),int(m.sin(b*k)*z+z)]for k in[m.pi*2/p*l for l in range(p)]];print('\n'.join(''.join([' ','#'][[i,j]in d]for i in range(w))for j in range(h)));t+=m.pi*2/r

```

MORE IMPORTANT EDIT: Input via stdin, space-separated, newline terminated. Will wait for your input.

EDIT: Screenshot. Changed height to 40 for this one.

# Answer
> 1 votes
# C# - 360 352 (cross platform - 332 for Windows only)

**Edited after micro-golfing and rounding bug fix + suggestion by Ypnypn**

Not exactly a contender at that length - and it's pretty much a verbatim copy of the reference - but oh well. :)

```
namespace System{class P{static int Main(string[]m){double p=Math.PI*2,a=int.Parse(m[0]),b=int.Parse(m[1]),q,t;for(;;)for(q=0;q<p;q+=p/200){var s=new string(' ',1920).ToCharArray();for(t=0;t<p;t+=p/1000)s[(int)(39.5*Math.Sin(a*t+q)+40)+(int)(11.5*Math.Sin(b*t)+12)*80]='#';Console.SetCursorPosition(0,0);Console.Write(s);Threading.Thread.Sleep(20);}}}}

```

Memory hog, creating a new array for every refresh - originally (re)used a StringBuilder, but sacrificed it for shortness. But at least the refresh takes less than 1 ms on my old Core2.

After removing some - now length-hurtful - old golfing, thereby reducing it by 8 characters, I tried to get it back to the "poetic" 360 by reverting to double rather than int parsing, and returning to 80\*24 instead of 1920. That's still only 359, though - and no other single character addition that I can think of really adds any value to the code. So we'll just stick with 352. :-)

Unrolled (lost the pre-golf code):

```
namespace System
{
    class P
    {
        static int Main(string[] m)
        {
            double p = Math.PI * 2,
                   a = int.Parse(m[0]),
                   b = int.Parse(m[1]),
                   q, t;

            for (;;)
            {
                for (q = 0; q < p; q += p/200)
                {
                    var s = new string(' ', 1920).ToCharArray();
                    // Alternative - Windows console only:
                    // var s = new char[1920];

                    for (t = 0; t < p; t += p/1000)
                    {
                        s[
                            (int) (39.5*Math.Sin(a * t + q) + 40)
                          + (int) (11.5*Math.Sin(b * t) + 12) * 80
                        ] = '#';
                    }
                    Console.SetCursorPosition(0, 0);
                    Console.Write(s);
                    Threading.Thread.Sleep(20);
                }
            }
        }
    }
}

```

The Windows console actually accepts outputting a lot of null chars resulting in output that's (graphically) identical to using an actual space character - which allows a few characters less to initialize the character array.

# Answer
> 1 votes
## Python 2.7 - 214

I think I'm going to have another look at this. I have a feeling this can be brought down even further, but it will be hard to hit the Perl byte count. The math seems to be my biggest limitation here.

Warning: may crash whatever terminal you are using. I tested this on the Windows command prompt with `lissajous.py 2 3`. Because of the quick writing to the command prompt, expect the frames to jump a little bit. This can be mostly resolved (at the cost of speed) by using a greater `s` in the `range(s)` and `t=2*pi*i`.

I don't use `\r` or `\b` here purposely because I'm running it on Windows and it would cost extra characters.

```
from math import*;import sys;a,b=sys.argv[1:];p=s=1920
while p:
 c = [" "]*s
 for i in range(s):
    t=2*pi*i/s;c[int(round((39.5*(1+sin(eval(a)*t+p))))+round(11.5*(1+sin(eval(b)*t)))*80)]="#"
 print ''.join(c)
 p+=.1

```

---
Tags: code-golf, math, ascii-art, animation
---


title: Turtle Graphics Version 2

text:
# Question
Title: Turtle Graphics Version 2
Most of you have probably heard of the famous Turtle Graphics program, initially made popular by Logo. This challenge is to implement a Turtle Graphics program in your language of choice.

Rules:

1. The floor must be a diagonal with dimensions input by the user through std-in in the form `x/y`, representing the `x` and `y` length, respectively. `x` may not be more than 20 and `y` may not be more than 45,
2. When the pen is in the down state, it must draw in both the square (the x/y coordinate) the turtle leaves and the square the turtle enters. This is what would happen in real life, so that is what your program should do.
3. Initial position and direction of the turtle must be input by the user in the form `x,y,d`, where `x` and `y` are the positions on the x- and y-axis, respectively, and `d` is the direction, entered as `U`, `D`, `R`, or `L` (up, down, right, and left, respectively).
4. You must stop the turtle and display an error message if the turtle hits the wall. In other words, the turtle cannot walk through the wall.
5. The turtle must include these commands:

> RESET - Resets board to blank - turtle goes back to initial position and direction.
>
> DRAW and ERASE - These commands set the turtle to drawing and erasing, respectively.
>
> UP and DOWN - These two commands set the active tool (pen or eraser) position to up and down, respectively.
>
> DIRECTION x - This command turns the turtle to any direction North, Northeast, East, Southeast, South, Southwest, West, or Northwest, represented as the digits 1-8, with North (up) being 1, Northeast being 2...
>
> FORWARD xx - Advances turtle xx squares; FORWARD 15 advances the turtle 15 squares. If the turtle is facing N, E, S, of W, it will draw in `x` squares in that direction only. If the turtle is facing NE, NW, SE, or SW, it will draw in `x` squares in both directions; i.e. in FORWARD 1 while facing NE, it will draw this:
>
> ```
>  X
> X
>
> ```
>
> DISPLAY - Displays board, using `X` for filled squares (x/y coordinates) and a blank space  for empty squares.
>
> POSITION - Prints turtle's x/y coordinate on the board.
>
> SETPOS x y d - Sets the turtle to the x/y coordinate facing direction `d`, using the same notation as the DIRECTION command.
>
> STOP - Displays the board, and terminates the program after the user enters the character `~`.

Example commands:

> DIRECTION 2 FORWARD 1 DIRECTION 4 FORWARD 1:
>
> ```
>  X
> X X
>
> ```
>
> DIRECTION 2 FORWARD 1 DIRECTION 4 FORWARD 4:
>
> ```
>  X
> X X
>    X
>     X
>
> ```
>
> DIRECTION 3 FORWARD 5:
>
> ```
> XXXXX
>
> ```

This program will use standard scoring rules to try to allow non-esoteric programming languages, such as Java and C++, to compete.

Version 1 is here. It did not require user input of board size and turtle start point, nor did it require diagonal movements.

# Answer
> 2 votes
### Python 3.3 (354?)

I noticed this as an unanswered question and decided to give it a go:

```
v=input().split('/')+input().split(',')+[input().split(' '),0,1,'X','U','D','L','R']
w,h,x,y,d,c,p,r,m,n,s,l,e=v
w,h,x,y=int(w),int(h),int(x),int(y)
g=[[' 'for x in range(int(h))]for y in range(int(w))]
while p<len(c):
 i=c[p]
 if r:
  g[y][x]=m
 if i=='RESET':
  w,h,x,y,d,c,p,r,m,n,s,l,e=v
 if i=='DRAW':
  m='X'
 if i=='ERASE':
  m=' '
 if i=='UP':
  r=0
 if i=='DOWN':
  r=1
 if i=='DIRECTION':
  p+=1
  i=int(c[p])
  d=''
  if i in[8,1,2]:
   d+=n
  if i in[4,5,6]:
   d+=s
  if i in[6,7,8]:
   d+=l
  if i in[2,3,4]:
   d+=e
 if i=='FORWARD':
  p+=1
  i=int(c[p])
  for _ in range(i):
   if d.find(n)+1:
    y-=1
   if d.find(s)+1:
    y+=1
   if d.find(l)+1:
    x-=1
   if d.find(e)+1:
    x+=1
   if r:
    g[y][x]=m
 if i=='DISPLAY':
  for z in g:
   print(''.join(z))
 if i=='POSITION':
  print(x,y)
 if i=='SETPOS':
  p+=3
  x,y=c[p-2:p]
  d=''
  if i in[8,1,2]:
   d+=n
  if i in[4,5,6]:
   d+=s
  if i in[6,7,8]:
   d+=w
  if i in[2,3,4]:
   d+=e
 if i=='STOP':
  while input()!='~':
   pass
  exit
 if x>w or x<0 or y>h or y<0:
  print('!')
  exit
 p+=1

```

> PS I am unsure about the scoring setup so my score may be incorrect!

---
Tags: atomic-code-golf
---