Golfscript -- 12 chars
{,1\{)*}/}:f
Getting started with Golfscript -- Factorial in step by step
Here's something for the people who are trying to learn golfscript. The prerequisite is a basic understanding of golfscript, and the ability to read golfscript documentation.
So we want to try out our new tool golfscript. It's always good to start with something simple, so we're beginning with factorial. Here's an initial attempt, based on a simple imperative pseudocode:
# pseudocode: f(n){c=1;while(n>1){c*=n;n--};return c}
{:n;1:c;{n 1>}{n c*:c;n 1-:n;}while c}:f
Whitespace is very rarely used in golfscript. The easiest trick to get rid of whitespace is to use different variable names. Every token can be used as a variable (see the syntax page). Useful tokens to use as variables are special characters like |, &, ? -- generally anything not used elsewhere in the code. These are always parsed as single character tokens. In contrast, variables like n will require a space to push a number to the stack after. Numbers are essentially preinitialized variables.
As always, there are going to be statements which we can change, without affecting the end result. In golfscript, everything evaluates to true except 0, [], "", and {} (see this). Here, we can change the loop exit condition to simply {n} (we loop an additional time, and terminate when n=0).
As with golfing any language, it helps to know the available functions. Luckily the list is very short for golfscript. We can change 1- to ( to save another character. At present the code looks like this: (we could be using 1 instead of | here if we wanted, which would drop the initialization.)
{:n;1:|;{n}{n|*:|;n(:n;}while|}:f
It is important to use the stack well to get the shortest solutions (practice practice practice). Generally, if values are only used in a small segment of code, it may not be necessary to store them into variables. By removing the running product variable and simply using the stack, we can save quite a lot of characters.
{:n;1{n}{n*n(:n;}while}:f
Here's something else to think about. We're removing the variable n from the stack at the end of the loop body, but then pushing it immediately after. In fact, before the loop begins we also remove it from the stack. We should instead leave it on the stack, and we can keep the loop condition blank.
{1\:n{}{n*n(:n}while}:f
Maybe we can even eliminate the variable completely. To do this, we will need to keep the variable on the stack at all times. This means that we need two copies of the variable on the stack at the end of the condition check so we don't lose it after the check. Which means that we'll have a redundant 0 on the stack after the loop ends, but that is easy to fix.
This leads us to our optimal while loop solution!
{1\{.}{.@*\(}while;}:f
Now we still want to make this shorter. The obvious target should be the word while. Looking at the documentation, there are two viable alternatives -- unfold and do. When you have a choice of different routes to take, try and weigh the benefits of both. Unfold is 'pretty much a while loop', so as an estimate we'll cut down the 5 character while by 4 into /. As for do, we cut while by 3 characters, and get to merge the two blocks, which might save another character or two.
There's actually a big drawback to using a do loop. Since the condition check is done after the body is executed once, the value of 0 will be wrong, so we may need an if statement. I'll tell you now that unfold is shorter (some solutions with do are provided at the end). Go ahead and try it, the code we already have requires minimal changes.
{1\{}{.@*\(}/;}:f
Great! Our solution is now super-short and we're done here, right? Nope. This is 17 characters, and J has 12 characters. Never admit defeat!
Now you're thinking with... recursion
Using recursion means we must use a branching structure. Unfortunate, but as factorial can be expressed so succinctly recursively, this seems like a viable alternative to iteration.
# pseudocode: f(n){return n==0?n*f(n-1):1}
{:n{n.(f*}1if}:f # taking advantage of the tokeniser
Well that was easy -- had we tried recursion earlier we may not have even looked at using a while loop! Still, we're only at 16 characters.
Arrays
Arrays are generally created in two ways -- using the [ and ] characters, or with the , function. If executed with an integer at the top of the stack, , returns an array of that length with arr[i]=i.
For iterating over arrays, we have three options:
{block}/: push, block, push, block, ...{block}%: [ push, block, push, block, ... ] (this has some nuances, e.g. intermediate values are removed from the stack before each push){block}*: push, push, block, push, block, ...
The golfscript documentation has an example of using {+}* to sum the contents of an array. This suggests we can use {*}* to get the product of an array.
{,{*}*}:f
Unfortunately, it isn't quite that simple. All the elements are off by one ([0 1 2] instead of [1 2 3]). We can use {)}% to rectify this issue.
{,{)}%{*}*}:f
Well not quite. This doesn't handle zero correctly. We can calculate (n+1)!/(n+1) to rectify this, although this costs far too much.
{).,{)}%{*}*\/}:f
We can also try to handle n=0 in the same bucket as n=1. This is actual extremely short to do, try and work out the shortest you can.
Not so good is sorting, at 7 characters: [1\]$1=.
Note that this sorting technique does has useful purposes, such as imposing boundaries on a number (e.g. `[0\100]$1=)
Here's the winner, with only 3 characters: .!+
If we want to have the increment and multiplication in the same block, we should iterate over every element in the array. Since we aren't building an array, this means we should be using {)*}/, which brings us to the shortest golfscript implementation of factorial! At 12 characters long, this is tied with J!
{,1\{)*}/}:f
Bonus solutions
Starting with a straightforward if solution for a do loop:
{.{1\{.@*\(.}do;}{)}if}:f
We can squeeze a couple extra out of this. A little complicated, so you'll have to convince yourself these ones work. Make sure you understand all of these.
{1\.!!{{.@*\(.}do}*+}:f
{.!{1\{.@*\(.}do}or+}:f
{.{1\{.@*\(.}do}1if+}:f
A better alternative is to calculate (n+1)!/(n+1), which eliminates the need for an if structure.
{).1\{.@*\(.}do;\/}:f
But the shortest do solution here takes a few characters to map 0 to 1, and everything else to itself -- so we don't need any branching. This sort of optimization is extremely easy to miss.
{.!+1\{.@*\(.}do;}:f
For anyone interested, a few alternative recursive solutions with the same length as above are provided here:
{.!{.)f*0}or+}:f
{.{.)f*0}1if+}:f
{.{.(f*}{)}if}:f
*note: I haven't actually tested many of the pieces of code in this post, so feel free to inform if there are errors.
