text:
Tips for golfing in CJam
CJam is a GolfScript-inspired stack-based golfing language, created by PPCG user aditsu.
So, in the vein of other language-specific tips questions:
What general tips do you have for golfing in CJam? Please post one tip per answer.

See also Tips for golfing in GolfScript; the languages are similar enough that many of the tricks can be adapted either way.

@IlmariKaronen After going through the answers in that question, I'd say only around half of them apply to CJam, due to syntactical or logical differences in the languages.

Correct modulo for negative numbers
It's often annoying that the result of the modulo operation gives the same sign as the first operand. E.g. -5 3% gives -2 instead of 1. More often than not you want the latter. The naive fix is to apply modulo, add the divisor once and apply modulo again:
3%3+3%

But that's long and ugly. Instead, we can use the fact that array indexing is always modular and does work correctly with negative indices. So we just turn the divisor into a range and access that:
3,=

Applied to -5, this gives 1 as expected. And it's only one byte longer than the built-in %!
If the modulus is a power of 2, you can save another byte using bitwise arihmetic (which is also a lot faster). Compare:
32,=
31&

For the special case of 65536 == 2^16 another byte can be saved by making use of the wrapping behaviour of the character type:
ci

Pushing concatenated character ranges

The string containing all digits "0123456789" can be written  as
A,s

The uppercase ASCII letters (A-Z) can be pushed as
'[,65>

which generates the string of all characters up to Z, then discards the first 65 (up to @).
All ASCII letters (A-Za-z) can be pushed as
'[,65>_el+

which works as above, then creates a copy, converts to lowercase and appends.
But there's a shorter way to do it!
Then often overlooked ^ operator (symmetric differences for lists) allows to create the same ranges while saving three bytes:
'[,_el^

'[, creates the range of all ASCII characters up to Z, _el creates a lowercase copy and ^ keeps only characters of both strings that appear in one but not both.
Since all letters in the first string are uppercase, all in the second are lowercase and all non-letter characters are in both strings, the result in the string of letters.
The RFC 1642 Base64 alphabet (A-Za-z0-9+/) can be pushed using the above technique and appending the non-letters:
'[,_el^A,s+"+/"+

An equally short way of pushing this string makes use solely of symmetric differences:
"+,/0:[a{A0":,:^

How can we find the string at the beginning?
All used character ranges (A-Z, a-z, 0-9, +, /) can be pushed as the symmetric difference of to range that start at the null byte, namely 'A,'[,^, 'a,'{,^, '0,':,^, '+,',,^ and '/,'0,^.
Therefore, executing :,:^ on "A[a{):+,/0" will push the desired characters, but not in the right order.
How do we find the right order? Brute force to the rescue! The program
'[,_el^A,s+"+/"+:T;"0:A[a{+,/0"e!{:,:^T=}=

iterates over all possible permutations of the string, applies :,:^ and compares the result to the desired output (permalink).
The radix-64 alphabet used, e.g, by crypt (.-9A-Za-z) can be generated using the above method:
".:A[a{":,:^

This is the shortest method I know.
Since all characters in the desired output are in ASCII order, iterating over permutations isn't needed.
Not all concatenated character ranges can be pushed in the desired order using :,:^.
For example, the range 0-9A-Za-z;-? cannot be pushed by executing :,:^ on any permutation of "0:A[a{;@".
However, we can find a rotated variation of the desired string that can, by using the code
A,'[,_el^'@,59>]s2*:T;"0:A[a{;@"e!{:,:^T\#:I)}=Ip

which will print (permalink) the following:
10
0:@[a{A;

This means that
"0:@[a{A;":,:^Am>

has the same effect as
A,'[,_el^'@,59>]s

which can only be used with an empty stack without prepending a [.

Avoid {…}{…}?
Assume you have an integer on the stack. If it is odd, you want to multiply it by 3 and add 1; otherwise you want to divide it by 2.
A "normal" if/else statement would look like this:
_2%{3*)}{2/}?

However, using blocks is usually not the way to go, since {}{} already adds four bytes. ? can also be used to select one of two items on the stack:
_2%1$3*)@2/?

This is one byte shorter.

Block-? with an empty if statement is always a no-go. For example,
{}{2/}?

is two bytes longer than
{2/}|

If instead you have
{2/}{}?

and the thing you are checking on is non-negative integer, you can do
g)/

The new {}& and {}| are handy, but sometimes problematic if you cannot clutter the stack.
Still, in the case of
_{…}{;}?

you can use a temporary variable instead:
:T{T…}&

!)/ and g)/ are shorter in the examples.

Golfing common array and string values
There are certain short arrays or strings that crop up every now and then, e.g. to initialise grids. Naively, these can cost 4 or more bytes, so it's worth looking for operations on built-in values which will give the same result. Especially base conversion is often useful.

[0 1] can be written as 2,.
[1 0] can be written as YYb (i.e. 2 in binary).
[1 1] can be written as ZYb (i.e. 3 in binary).
The matrix [[0 1] [1 0]] can be written as 2e!.
[LL]  can be written as SS/ (splitting a single space by spaces).
"\"\"" can be written as L`.
"{}" can be written as {}s.

The latter can be extended to cases where you want all bracket types to save another byte:

"[{<()>}]" can be written as {<()>}a`.
"()<>[]{}" can be written as {<()>}a`$.

Especially the base conversion trick can be useful to keep in mind for some obscurer cases that pop up every now and then. E.g. [3 2] would be E4b (14 in base 4).
In even rarer cases you might even find the factorisation operator mf useful. E.g. [2 7] is Emf.
Please feel free to extend this list if you come across any other examples.

Switch statements
CJam doesn't have switch statements. Nested if statements work just as well, but {{}{}?}{}? is already 12 bytes long...
If we can transform the condition into a small, non-negative integer, we can transform all case statements in a delimited string and evaluate the corresponding result.
For example, if we want to execute code0 if the integer of the stack is 0, code1 if it is 1, and code2 if it is 2, we can either use
_{({code2}{code1}?}{;code0}?

or
[{code0}{code1}{code2}]=~

or
"code0 code1 code2"S/=~

S/ splits the string into ["code0" "code1" "code2"], = extracts the corresponding chunk, and ~ evaluates the code.
Click here to see switch statements in action.
Finally, as suggested by suggested by @jimmy23013 and @RetoKoradi, we can shorten the switch even more in some cases. Say code0, code1 and code2 have lengths L0, L1 and L2, respectively.
If L0 = L1 ≥ L2
"code0code1code2"L/=~

can be used instead, where L is L0. Instead of splitting at a delimiter, / splits the string into chunks of equal length here.
If L0 ≥ L1 ≥ L2 ≥ L0 - 1,
"cccooodddeee012">3%~

can be used instead. > removes 0, 1 or 2 elements from the beginning of the string, and 3% extracts every third element (starting with the first).

For the last example, does that have any advantage over  "code0code1code2"5/=~? Seems much more straightforward to me, and it's the same length.

@RetoKoradi If all snippets have the same length, there's no advantage. For different length, your method can be both shorter and longer than the modulus method.

Clearing the stack
If you just want to clear the entire stack, wrap it in an array and pop it:
];

What's a bit more tricky is, if you've done a lot of computations, but only want to keep the top stack element and discard everything beneath. The naive approach would be to store the top element in a variable, clear the stack, push the variable. But there's a much shorter alternative: wrap the stack in an array and extract the last element:
]W=

(Thanks to Optimizer who showed this to me the other day.)
Of course, if there's only two elements on the stack, \; is shorter.

\; would only pop the element below the TOS. Did you mean ;;?

@CalculatorFeline the second half of the answer is about clearing everything but the TOS.

Euclidean norms
The straightforward way of calculating the Euclidean norm of a vector, i.e., the square root of the sum of the squares of its elements, is
2f#:+mq

However, there's a much shorter way.
mh, the hypotenuse operator, pops two integers a and b from the stack and pushes sqrt(a2 + b2).
If we have a vector x := [x1 … xn], n > 1 on the stack, :mh (reduce by hypotenuse) will achieve the following:

First x1 and x2 are pushed and mh is executed, leaving sqrt(x12 + x22), on the stack.
Then, x3 is pushed and mh is executed again, leaving
sqrt(sqrt(x12 + x22)2 + x32) = sqrt(x12 + x22 + x32) on the stack.
After xn has been processed, we're left with sqrt(x12 + … xn2), the Euclidean norm of x.

If n = 1 and x1 < 0, the above code will produce an incorrect result. :mhz works unconditionally. (Thanks to @MartinBüttner for pointing that out.)
I've used this trick for the first time in this answer.

Of course, this has implications for numerical analysis of your program...

e and powers of ten
As in oh-so-many other languages, you can write 1e3 instead of 1000 in CJam.
This works for non-integer bases and even for non-integer exponents as well. For example, 1.23e2 pushes 123.0 and 1e.5 pushes 3.1622776601683795 (square root of 10).
What's not immediately obvious is that 1e3 is actually two tokens:

1 pushes the integer 1 on the stack.
e3 multiplies it by 1000.

Why is that important?

You can call e<numeric literal> on something that's already on the stack.
2 3 + e3 e# Pushes 5000.

You can map e<numeric literal> over an array.
5 , :e3  e# Pushes [0 1000 2000 3000 4000].

Convert from base n with a list of numbers greater than n
CJam converts a list to a number with this formula: A0*nl + A1*nl-1 + A2*nl-2 + Al*n0 (with nonnegative n). n is the base and l is the list length. This means Ai can be any integer, which doesn't have to be in the range of [0,n).
Some examples:

0b extracts the last item and cast it to integer. Works like W=i and saves a byte if it wasn't integer. But everything else in the list must also be able to cast into integer.
1b returns the sum. Works like :i:+ and saves two bytes if they weren't integers. It also works with empty lists while :+ doesn't.
[i{_1&9 32?_@\m2/}16*;]W%:c converts a character to a string of line endings and tabs, which can be converted back with 2bc. The encoding function isn't easy to be golfed in a code-golf program, though. But you don't usually need that.
You can use the following code to convert a string to Unicode characters not in 16 bit, which can be converted back with 2A#b128b:c. (Explanations will be added later. Or perhaps I'll write a new version later.)
128b2A#b         " Convert to base 1024. ";
W%2/)W%\:+       " Convert to two base 1024 digit groups. ";
[0X@
{
  _54+
  @I+_Am>@\-
  _Am<@+ 0@-@1^
}fI
]);)
@\+[~+]2A#b_2G#<!{2A#b}*
\W%+:c

The similar method works with any set of n integers which have different values mod n, if you can find some way to get rid of the most significant digit.

Using $ as ternary if
When you don't mind leaking memory, i.e., leaving unused elements on the stack that you'll later clear with ];, the copy operator $ can be a handy substitute for the ternary operator ?.
? works well if you manage to compute the condition before pushing the two items to choose from, but more often than not, the condition actually depends on those items, and having it on top of them results much more natural.
If you have A B C on the stack, you can execute
!$

instead of
\@?

to copy B if C is truthy and A otherwise.
If C is an actual Boolean (0 or 1), you can execute
$

instead of
@@?

to copy A if C is truthy and B otherwise.

In hindsight, this is a rather obvious trick, but I had never thought of it before. I've used it for the first time in this answer.

Map for Nested Lists
Say you've got a nested list, like a matrix:
[[0 1 2][3 4 5][6 7 8]]

Or an array of strings:
["foo""bar"]

And you want to map a block onto the nested level (i.e. apply it to each number or each character). The naive solution is a nested %:
{{...}%}%

However, you can actually push the inner block onto the stack and then use f%. f is "map with additional parameter", so it will map % onto the outer list, using the block as the second parameter:
{...}f%

Saves two bytes.
Another neat trick to do something like for (i=0; i<5; ++i) for (j=0; j<5; ++j) {...} is
5,_f{f{...}}

The outer f will map onto the first range, supplying the second range as an additional parameter. But now, if you use f again, only the top stack element is an array, so you f maps the inner block onto that, supplying the outer "iteration variable" as an additional parameter. This means the inner block is runs with i and j on the stack.
This has the same number of characters as just mapping a block onto a Cartesian product (although the latter gets shorter if you need the pairs as arrays):
5,_m*{~...}%

The difference is that this version yields a single array of results for all pairs, whereas the double-f yields a nested list, which can be useful if you want to store the results in a grid, with the iterator variables being the coordinates.
Thanks to Dennis for showing me this trick.
0.6.4 Update
f and : have now been immensely improved by taking any other operator including themselves. This means you can save even more bytes now. Mapping an operator onto a nested list got even shorter now:
{:x}%
{x}f%
::x

This doesn't really help with mapping blocks onto nested lists though.
As for the applying blocks or operators to the Cartesian product, this also got shorter now, for blocks as well as operators:
5,_f{f{...}}
5,_ff{...}

5,_f{fx}
5,_ffx

What's nice is that you can now nest these. So you can apply an operator just as easily to the third level down a list:
:::x

Or a block with some trickery:
{...}ff%

Great update. But there is still no f~...

@user23013 f expects a binary operator, ~ is unary; did you perhaps want :~? Also, we can discuss this in chat

Am I missing something about this 0.6.4 update? I still get error messages doing those tricks, like Unhandled char after ':': : (link)

@Runer112 Works for me. Make sure you reload properly (i.e. not from cache). Depending on your browser Ctrl+F5 should work.

@MartinBüttner It was indeed caused by silly caching. Thanks.

Vectorized operators for ASCII art
For many ASCII art challenges, it is useful to generate two different patterns to superpose them later. Vectorized operators can be very helpful to achieve different types of superpositions.
One useful property of operator vectorization is that the operator is only executed once for each element of the shorter string/array, while the elements of the larger one that do not have counterparts remain untouched.

.e<
The minimum operator e< work for pairs of strings, characters, arrays and integers; it pops two items from the stack and pushes the lower on e back.
Since a space has a lower code point than all other printable ASCII characters, .e< can be used to "erase" parts of a generated pattern:
"\/\/\/\/\/" "    " .e<

e# This pushes "    \/\/\/".

For a full example, see my answer to Me Want Honeycomb.
.e>
The maximum operator e> works as the minimum operator, with the opposite result.
Again, because of the low code point of the space, .e> can be used to insert a pattern of printable characters in a block of spaces:
[[" " " " " " " "] [" " " " " " " "]][["+" "" "-" ""]["" "*" "" "/"]] ..e>

e# This pushes [["+" " " "-" " "] [" " "*" " " "/"]].

For a full example, see my answer to Seven Slash Display.
.e&
The logical AND operator e& pushes its left argument if it is falsy and its right argument otherwise.
If neither pattern contains falsy elements, this can be used to inconditionally impose one pattern over another one:
"################" " * * * *" .e&

e# This pushes " * * * *########".

For a full example, see my answer to Print the American Flag!.
.e|
The logical OR operator e| can be used as above, with reversed argument
order:
" * * * *" "################" .e|

e# This pushes " * * * *########".

Use & to check if an item is in a list
For
1 [1 2 3] #W>
1 [1 2 3] #)

You can use
1 [1 2 3] &,
1 [1 2 3] &

instead, which returns 0/1 and truthy/falsey respectively.

z and non-rectangular arrays
The zip operator z transposes the rows and columns of a two-dimensional1 array A, whose elements can also be iterables.
For non-rectangular arrays – unlike the built-in zip functions in, e.g., Python (truncates the rows to the same length) or Ruby (pads the rows with nil) – CJam simply converts the columns of the array into rows, ignoring their lengths and gaps.
For example, zipping the array
[
  [1]
  [2 4]
  [3 5 6]
]

is equivalent to zipping the array
[
  [1 4 6]
  [2 5]
  [3]
]

or the array
[
  [1]
  [2 4 6]
  [3 5]
]

as all three actions push
[
  [1 2 3]
  [4 5]
  [6]
]

on the stack.
While this means that z is not an involution (which would be useful on occasions), it has a few applications.
For example:

We can align the columns of an array to the top (i.e., turn the first array into the second) by zipping twice:
zz

Minor modifications of the above method can be used for similar problems.
For instance, to align the columns of an array to the bottom (i.e., to turn the second array into the first), we can zip twice with reversed row order:
W%zzW%

Given an array of strings, we can compute the length of the longest string like this:
:,:e>

However, by zipping and calculating the number of rows of the result, we can save three bytes:
z,

1 If any of the "rows" of A is not iterable, z treats them as singletons, so zipping works for arbitrary arrays.

Just a different way of visualizing the same thing, but for me the behavior is much more logical if I picture z converting columns into rows, while empty values are skipped. In the example, the first column in the input is 1, 2, 3, the second column is 4, 5 (empty position is skipped), and the third column is 6. These are then the rows of the result.

@RetoKoradi That's a much better way to describe it.

Exceptions
All exceptions are fatal in CJam. Since output to STDERR is ignored by default, we can use this to our advantage.
All operator in CJam work by popping zero or more elements from the stack, perform some task and push zero or more elements on the stack. Exceptions occur while the task is performed, so this still pops the elements, but nothing is pushed in return.
Here are a few use cases:

Clearing a small stack
To clear a stack that contains two elements, @ can be used. @ tries to pop three stack elements, but fails after popping the second.
Any other operator that pops three elements would serve the same purpose.
See it in action here.
Removing two or three elements from the stack
Any operator that is not implemented for these particular elements can be used to pop two or three elements from the stack right before exiting.
To pop two elements, b works if one of them is a character or none of them is an integer.
To pop three elements, t works if none of the bottom-most two is an iterable, the bottom-most iterable is empty or none of them is an integer.
Exiting from a loop
On occasions, we need to exit from a loop when an integer becomes zero or a string becomes too short. Rather than testing for these conditions, if the involved operations fail for zero, the empty string or singletons, we can simply let the program take its natural course.
For an example involving arithmetic, see here.
For an example involving strings, see here.
Conditional execution
If the source code should not be executed for certain types of input, we sometimes can use an operator that fails that kind of input.
For example, i will fail for strings that do not evaluate to an integer and ew will fail for strings of length 0 or 1.
See it in action here.

Max/Min from an array
Here is one for starters!
When you need to find the maximum or minimum number from an array, the easiest and smallest way is to sort the array and then take out the first or last element.
So if the array is in variable A
A$W=

is the maximum and
A$0=

is the minimum.
Get both at the same time is also possible
A$)\0=

This might seem obvious after reading, but anyone's first attempt tends to go towards the usage of e< or e> via iterating through the array, which goes like
A{e<}*

which is 2 bytes longer, and even longer if you want both max and min.

Of course, if you don't mind the rest of the array remaining on the stack, you can actually use ( and ) instead of 0= and W=.

Now there is :e< and :e>

@aditsu Though, they are not shorter than the tip above.

Use a timestamp for large numbers
If you need a very large, but arbitrary number, you'll usually either use scientific notation like 9e9 or raise one of the large built-in variables to a similar power, like KK#. However, if you don't care what the actual number is, and it doesn't need to be consistently the same (e.g. as the upper bound for a random number), you can do it in two bytes using
es

instead. This gives the current timestamp in milliseconds, and is on the order of 1012

Also note that if you want a large arbitrary number, and want to discard a positive number together, you can use e9.

Checking that two strings/arrays are not equal
Sometimes you want a truthy value when two strings or arrays are not equal, and a falsy value if they are. The obvious solution is two bytes:
=!

Check for equality, and invert the result. However, under some conditions you can use
#

When # is applied to two arrays it actually searches for the second array as a subarray of the first (and gives you the index where the subarray starts). So if the two arrays are the same, the subarray will be found right at the start and give 0, which is falsy. But if the second array cannot be found, it will give -1 which is truthy.
The reason we need some additional condition on the two arrays is that this also yields a falsy value if the second array is a non-trivial prefix of the first, e.g.:
"abc""ab"#

gives 0 although the strings are not the same. The simplest condition which rules out this case is if you know that both arrays will be the same length - in that case if one is a prefix of the other, you know that they are equal. But in specific circumstances there may be weaker conditions that are also sufficient. For instance, if you know that the strings are sorted, a prefix would always be the first string, not the second.

c and 16-bit integers
To add (or subtract) unsigned 16-bit integers with proper wrapping, you can use +65536% or +2G#%.
However,
+ci

is a lot shorter. Characters wrap arround at 65536, so casting to Character (c) then to Long (i) has a similar effect to 65536%, with the added benefit that the result will not be negative.
The same trick can be used to push 65535:
Wci

Power sets
Say you have an array and you want an array with all possible subsets of that array. The trick is to start with an empty array, and then, for each element, duplicate the subsets you already have, and add the new element to them (keeping previous result where the element wasn't added). Note that you need to initialise the stack with the base case, i.e. an array containing only an empty array: That could look like this:
[1 2 3 4 5]La\{1$f++}/

The nice thing about this is, you can immediately run some computation on the subset, potentially without added characters. Say you want the products of all subsets. In that case, the base case is an array containing 1, and at each step, you take the previous list of possible products, duplicate it, and multiply everything in the duplicate by the new element:
[1 2 3 4 5]1a\{1$f*+}/

Check if items in a list are all the same
I think this also worth mentioning. Use:
)-

Returns truthy if not all the same, or empty list if all the same. Errors if the list is empty.
In case the item extracted might be an array (or string) itself:
)a-

Use ! or !! to get boolean values. In case the item extracted might be an array, and there are at most two kind of different items, and you want it to be 1 if not all the same, this is shorter:
_|,(

0= for strings
To retrieve the first element of an array, you have to use 0= (or (, if you don't mind leaving the rest of the array on the stack).
However, if that array is a string, casting to character is sufficient.
Example
"xyz"c e# Pushes 'x.

I don't see why CJam doesn't just let c extract the first element of any array, which would be more useful and consistent.

Rotating an array (or the stack) one unit to the left
CJam has the rotate left operator m<, which is normally what you should use to rotate an array an arbitrary number of units to the left.
In some cases, you can also use (+ to shift and append:
[1 2 3]       (+ e# Pushes [2 3 1].
[[1] [2] [3]] (+ e# Pushes [[2] [3] 1].

The second example did not work because the arrays first element is also an iterable, so + concatenated instead of appending.
Also, if you want to dump the rotated array on the stack, you can use :\ (reduce by swapping) unconditionally:
[1 2 3]       :\ e# Pushes 2 3 1.
[[1] [2] [3]] :\ e# Pushes [2] [3] [1].

As long as you don't have an open [, this trick can also be used to rotate the entire stack, i.e., to bring the bottom-most stack item to the top:
]:\

Printing a list and clearing the stack
Lets say your stack has a list of strings/numbers/etc. on top and some other extra items below it. i.e.
123 "waste" ["a" "b" "rty" "print" "me" "please"]

Now you are interested in printing the last list only, so you do
S*]W=

which outputs
a b rty print me please

Which seems really smart as we use the clearing the stack trick and only print the list joined with spaces (which might not be the desired way of printing a list at times).
This can be golfed further!
p];

That's 2 bytes shorter!
and if you have only 1 item on stack other than the list, its even shorter!
p;

The beauty of p is that it removes the top most item from stack, stringifies it (also adds a newline at the end) and prints to STDOUT instantly, without waiting for completion of the code.
So the above code will output
["a" "b" "rty" "print" "me" "please"]

which is the exact representation of a list when it was in stack!

Cartesian products or all possible combinations of two or more sets
CJam has an inbuilt Cartesian product calculator m* which takes the top two arraylists/strings on stack and create all possible pairs from it. For example
[1 2 3 4]"abc"m*

leaves
[[1 'a] [1 'b] [1 'c] [2 'a] [2 'b] [2 'c] [3 'a] [3 'b] [3 'c] [4 'a] [4 'b] [4 'c]]

as the stack
But what if you want all possible combinations from more than 2 lists/strings. You use m* that many times ? For example
[1 2 3 4][5 6]"abc"m*m*

will leave the following on stack
[[1 [5 'a]] [1 [5 'b]] [1 [5 'c]] [1 [6 'a]] [1 [6 'b]] [1 [6 'c]] [2 [5 'a]] [2 [5 'b]] [2 [5 'c]] [2 [6 'a]] [2 [6 'b]] [2 [6 'c]] [3 [5 'a]] [3 [5 'b]] [3 [5 'c]] [3 [6 'a]] [3 [6 'b]] [3 [6 'c]] [4 [5 'a]] [4 [5 'b]] [4 [5 'c]] [4 [6 'a]] [4 [6 'b]] [4 [6 'c]]]

Notice that the products are still pairs, where one of the item is a pair itself. This is not expected and we want flattened combinations.
There is an easy way to do that. Just wrap every list that you want for your cartesian product in an array, pairwise create Cartesian products and flatten it each time:
[1 2 3 4][5 6]"abc"]{m*{(+}%}*

This leaves
[['a 5 1] ['b 5 1] ['c 5 1] ['a 6 1] ['b 6 1] ['c 6 1] ['a 5 2] ['b 5 2] ['c 5 2] ['a 6 2] ['b 6 2] ['c 6 2] ['a 5 3] ['b 5 3] ['c 5 3] ['a 6 3] ['b 6 3] ['c 6 3] ['a 5 4] ['b 5 4] ['c 5 4] ['a 6 4] ['b 6 4] ['c 6 4]]

on stack.
Want the order maintained ?, simply swap the before adding the popped item back to the array. i.e.
{m*{(\+}%}*

Want only permutations ?
{m*{(+$}%_&}*

Want only unique elements in the combinations ?
{m*{(+_&}%}*

That's all folks. for now.

Now you can also do ]:m*:e_, with any number of arrays

Operating on strings
Sometimes if you are working with a complex data structure, while the items in it are simple, converting to strings may help.
For example, if you want to get the first or last few items in a 2D array of bits, and don't care about the returned type, sA< saves a byte from 0=A< or :+A<.
Or if you want to modify some bits in the input, you can modify the string before evaluating it.
Or if you got this structure and want to convert it to a simple list:
[[[[[[[[[1]2]3]4]5]6]7]8]9]

You can do it with many characters in other ways:
[a{~)\}h;]W%

But it can be much shorter with strings:
s:~

It's shorter even if it may have numbers with more than one digit:
[`La`-~]

Or:
`']-~]

If you don't need another array containing many of such arrays.

There is e_ now

@aditsu See this answer and comment. Sometimes s still works better.

Sure, when you can work with a string directly, it's shorter.

Using N instead of La
In many cases you need something initialized to an array containing an empty array as its only element, which is La, seemingly unnecessarily 1 byte longer.
In many cases you also need to add a newline after each element before printing, which would be something like No or N*.
But if both are true, sometimes you may find out that you can just initialize the array with N, which has the newline character as its only element. Make sure you only prepend things to the elements in the rest of your code, and the first thing to prepend is always a character or an array. Or only append, if a leading newline is acceptable and that makes it shorter.
Sometimes S also works if you need to separate the output with spaces.
In rarer cases, the initial element has to be a string. But you still can use Na which might be shorter than appending the newline afterwards.

Splitting on one or more occurrences
Say you have a string "abbcdbbfghbdbb" and you want to split it on b
"abbcdbbfghbdbb"'b/

This leaves on stack:
["a" "" "cd" "" "fgh" "d" "" ""]

Notice the empty strings ? Those are there because two b were together and nothing was in between them. At times, you want to avoid this. You can do this by
"abbcdbbfghbdbb"'b/La-

or filtering out empty strings
"abbcdbbfghbdbb"'b/{},

but that is 3 extra bytes.
A little less known operator for this particular use case is %. Apart from doing mod and map and splitting based on number ("abcd"2% = "ac"), % can also split on strings/arrays. So for the above use case:
"abbcdbbfghbdbb"'b%

will leave
["a" "cd" "fgh" "d"]

on stack.
Thanks for @user23013 for pointing this out in one of my answers today.

I think this should be named "also learn GolfScript", which has better examples in the documentation.

@user23013 but we are never sure what all is similar to GS and what is not.

Use fold/reduce as infix foreach
We have :x as a shorthand for {x}% and or {x}* (depending on whether x is unary or binary). Unfortunately, there is no equivalent infix operator to shorten {x}/. However, very often when we do {x}/, x is actually a binary operator which repeatedly modifies the item lying underneath on the stack. If that's the case, and said item is not an array, we can save a byte by abusing fold/reduce as foreach:
5 [1 2 3 4]{-}/  e# Gives -5
5 [1 2 3 4]+:-

This works because fold always leaves the first element untouched. Unfortunately, it doesn't save a byte, when the modified element is an array, because adding it would unwrap it. However, sometimes you're lucky enough that your array already contains that element at the front, in which case reduce should be kept in mind (instead of manually removing the element before using {}/ on the remainder).

print and println
CJam has print operator: o. It works but stack is printing immediately after all the code has executed. You can stop it if you clear the stack at the end of program. Simply put this at the end:
];

To println you can use oNo or p (works as `oNo)

There's a larger difference between o and p. p starts by converting the item to be printed to an unambiguous string representation. p is equvalent to executing `oNo.

Modify an element instead of deleting it
If you need the sum of a list except for the last element, increased by T, instead of:
W<:+T+

You can use:
WTt:+

Or if you just need the sum of a list except for element K, which isn't the first or last element, you can use:
K0t:+

Except for the case there are only 3 elements and K=1, where this is shorter:
2%:+

Understand How Array Literals Work
The [ and ] characters in CJam are not part of any special syntax; they are operators.
What [ does is puts a "flag" on the stack. Attempting to pop from the stack will pop from below it, but pushing to the stack will push above it.
This means that this:
1 2 [+]

Will result in the stack looking like this:
[3]

This can be used for golfing. For example, if I wanted to duplicate the final element in an array (i.e. turn ["foo" "bar" "baz"] into ["foo" "bar" "baz" "baz"]), I could do this:
_W=a+

But I can shorten this by 1 byte:
[~_]

If I wanted to put the top two stack elements into an array, I'd do:
a\a\+

But again, I can shorten this:
[\\]

If I was doing some computation earlier that pushed the two values onto the stack, I could wrap part of it in []. This means I don't need the \\, which saves even more bytes.
You can manipulate this in even crazier ways. For example, you can accumulate an array ([1 2 3] -> [1 3 6]) using:
[{1$+}*]

(I still wish CJam had a builtin for that, though, as I find myself needing it oftentimes.)
In general, this technique allows us to treat stack elements as array elements and vice versa.

Check if array contains sub-array
Note: If you're only looking for a single element use jimmy's method.
If you want to see if an array contains a specific sub-array, use #). # is "index of" and ) increases it by 1. If the sub-array is not in the array # returns -1. When you increment it by 1, you get 0 which is falsey. If the sub-array is in the array # returns a number that is at least 0, which when incremented by 1 returns a truthy value.
& and e= don't work for sub-arrays.

Index into an array, use a default value or run code if not in range
This could be done using a single character: j.
For example, this code would output GolfScript, CJam, Pyth for 0, 1, 2, and Seriously for all other cases:
ri"GolfScript CJam Pyth"S/{;"Seriously"}j

Compared to:
ri3,#"GolfScript CJam Pyth Seriously"S/=

Actually used more characters. But it might be considerable if the type is not string or you have to run code in a block anyway.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Swipe Type Converter
The next revolution in typing on laptops was released on the first of April, 2014 by SwiftKey. However, I want to be the first person to write a swiping nano clone, but, as I can't find a good swipe-text to real-text library, and I can't wait for them, I'm asking here.
Task
Write a program that takes in swipe-text and outputs the real-text equivalent. Example:
Input: hgrerhjklo
Output: hello

When the user does:

Other examples:
Input: wertyuioiuytrtjklkjhgfd
Output: world

Input: poiuytrtyuioiugrewsasdfgbhnmkijnbg
Output: programming

Input: poiuygfdzxcvhjklkjhgres
Output: puzzles

Input: cvhjioiugfde
Output: code

Input: ghiolkjhgf
Output: golf

Rules

The program will take one swiped 'word' in on stdin or argv
The first and last letter of the swiped input will equate to the first and last letter of the real word
You can assume the user will make reasonably straight lines, but you can use the sample data to verify this (I made the sample data, and I will make the final test data)
For ambiguous input, you can make select either output, but I will try to eradicate all ambiguousness from the test data
This word will be in this word list (but swiped). The word list will be in the current directory, and can be read (newline separated, will be named wordlist, no extension).
The swipe will only contain lowercase alphabetic characters
The swipe may contain duplicated characters, if the user pauses on a key
The program must output on stdout (case does not matter)
The program must return 0 as the return code
You must provide the run command, compile command (if needed), name and which input path to use
Standard loopholes apply (they might not help, though)
No non-builtin libraries allowed
Deterministic, non golfed / obfuscated solutions preferred
No file writing, networking, etc.
Your code must run in one second or less (your code is run once per word)
The scoring runs are run on a Intel i7 Haswell processor, with 4 virtual code (2 real ones), so you can use threads if you have to
Maximum code length of 5000 bytes
The language you use must have a free (non trial) version available for Linux (Arch Linux, if that matters)

Winning Criterion

The winner is the most accurate solution (scored by the control program, using the provided test list)
Popularity is the tie breaker
The scoring table will be updated every few days
Time-outs and crashes count as fails
This challenge will run for two weeks or more, depending on popularity
The final scoring will use a different, randomly selected list of words (same length, from same word list)

Other

You can use the control program to test your program
If you are impatient, and want your program updated / added quickly, start an issue or pull request at https://github.com/matsjoyce/codegolf-swipe-type/blob/master
Entries are maintained at https://github.com/matsjoyce/codegolf-swipe-type/blob/master/entries
Logs of each program run are maintained at https://github.com/matsjoyce/codegolf-swipe-type/blob/master/logs
Main log at https://github.com/matsjoyce/codegolf-swipe-type/blob/master/log.log
The position of each key will be provided as a csv file in the current directory called keypos.csv, with the x and y values given as relative to Q (see https://github.com/matsjoyce/codegolf-swipe-type/blob/master/keypos.csv)
Each key is 1.5 x 1.5 cm (same unit as in keypos.csv)

Current Score Boards
testlist (logs):
Three Pass Optimizer:Errors: 0/250       Fails: 7/250        Passes: 243/250     Timeouts: 0/250
Corner Sim:         Errors: 0/250       Fails: 9/250        Passes: 241/250     Timeouts: 0/250
Discrete Fréchet Distance:Errors: 0/250       Fails: 17/250       Passes: 233/250     Timeouts: 0/250
Turnaround:         Errors: 0/250       Fails: 18/250       Passes: 232/250     Timeouts: 0/250
Direction Checker:  Errors: 0/250       Fails: 19/250       Passes: 231/250     Timeouts: 0/250
Regex Solver:       Errors: 0/250       Fails: 63/250       Passes: 187/250     Timeouts: 0/250

testlist2 (logs):
Corner Sim:         Errors: 0/250       Fails: 10/250       Passes: 240/250     Timeouts: 0/250
Three Pass Optimizer:Errors: 2/250       Fails: 14/250       Passes: 234/250     Timeouts: 0/250
Turnaround:         Errors: 0/250       Fails: 16/250       Passes: 234/250     Timeouts: 0/250
Direction Checker:  Errors: 0/250       Fails: 17/250       Passes: 233/250     Timeouts: 0/250
Discrete Fréchet Distance:Errors: 0/250       Fails: 18/250       Passes: 232/250     Timeouts: 0/250
Regex Solver:       Errors: 0/250       Fails: 67/250       Passes: 183/250     Timeouts: 0/250

Final Run
testlist (logs):
Corner Sim:         Errors: 0/250       Fails: 14/250       Passes: 236/250     Timeouts: 0/250
Three Pass Optimizer:Errors: 0/250       Fails: 18/250       Passes: 232/250     Timeouts: 0/250
Direction Checker:  Errors: 0/250       Fails: 20/250       Passes: 230/250     Timeouts: 0/250
Turnaround:         Errors: 0/250       Fails: 23/250       Passes: 227/250     Timeouts: 0/250
Discrete Fréchet Distance:Errors: 0/250       Fails: 30/250       Passes: 220/250     Timeouts: 0/250
Regex Solver:       Errors: 0/250       Fails: 55/250       Passes: 195/250     Timeouts: 0/250

Well done to everybody and hgfdsasdertyuiopoiuy swertyuiopoijnhg!

What is "A Solution"? Where is its code?

Let us continue this discussion in chat.

Somewhat related.

@Optimizer Not sure about the other cases, but "poiuytresaseresasdfghuioiugfdxcguiugcxsasdfghjklkuy" contains every letter of "paradoxically", in order, except for the l, which is not doubled.

Sorry, my bad. I missed the first "d" there.

I am pretty sure that the Error and Timeout section will always remain 0. You can remove that. Also, feel free to add mine too ...

If I'm not mistaken there are two spelling mistakes in the test cases ('cvbjkloiuhgfcvhjkjhgfds', expecting 'cloaks' and 'ijnjuyfdsasrtre', expecting 'inundate') and at least a dozen genuine ambiguities (like brats vs. breasts or aped vs. adopted). You could of cause say that any realistic test scenario should include such cases. ;)

I'm getting a syntax error when trying the control program. It is pointing to def print(.... I think it is this problem: http://stackoverflow.com/questions/937491/invalid-syntax-when-using-print but I can't fix it because I don't know python.

@Mhmd Make sure you are using python 3. It will not work with python 2.

@Optimizer The Error category hasn't remained zero... :)

That's a bug. I will fix it.

@Optimizer I'll run the final round as soon as you've fixed your bug. The test set is ready.

Give me a day :)

@Optimizer Shall I go ahead with the final scoring then?

Sorry, I wasn't able to fix the errors in time. Please proceed as it will not be fair to others

You are not going to choose your own submission as answer, right ? (Dunno if its possible)

@Optimiser Well, I thought your submission would beat it, but it was just below (a little tweaking would have changed that, I'm sure). It seems I can accept it, so... should I (I don't appear to get rep from accepting it)? I'd like to accept someone else's, but that's not following the rules (unless you've got a good idea).

JavaScript, ES6, Three Pass Optimizer, 112 187 235 240 241 243 and 231 234 passes
A three pass filter which first figures out critical keys in the keystroke sequence and then passes the sequence through the three filters:

A loosely formed RegEx out of the critical keys and helping keys. This gives correct result for majority of the keys (around 150)
A strict RegEx made out of just critical keys. This gives correct result for an extra 85 sequences
A third filter to figure out ambiguity amongst close answers. This works for 40% ambiguous cases.

Code
keyboard = {
  x: {},
  y: ['  q      w      e      r      t      y      u      i      o      p',
      '    a      s      d      f      g      h      j      k      l',
      '        z      x      c      v      b      n      m'],
};
for (var i in keyboard.y)
  for (var y of keyboard.y[i])
    keyboard.x[y] = +i*7;
p = C => (x=keyboard.x[C],{x, y: keyboard.y[x/7].indexOf(C)})
angle = (L, C, R) => (
  p0 = p(L), p1 = p(C), p2 = p(R),
  a = Math.pow(p1.x-p0.x,2) + Math.pow(p1.y-p0.y,2),
  b = Math.pow(p1.x-p2.x,2) + Math.pow(p1.y-p2.y,2),
  c = Math.pow(p2.x-p0.x,2) + Math.pow(p2.y-p0.y,2),
  Math.acos((a+b-c) / Math.sqrt(4*a*b))/Math.PI*180
)
corner = (L, C, R, N, W) => {
  if (skip) {
    skip = false;
    return [];
  }
  ngl = angle(L, C, R);
  if (ngl < 80) return [C + "{1,3}"]
  if (ngl < 115 && p(L).x != p(R).x && p(L).x != p(C) && p(R).x != p(C).x && Math.abs(p(L).y - p(R).y) < 5) return [C + "{0,3}"]
  if (ngl < 138) {
    if (N && Math.abs(ngl - angle(C, R, N)) < 6) {
      skip = true;
      return [L + "{0,3}", "([" + C + "]{0,3}|[" + R + "]{0,3})?", N + "{0,3}"]
    }
    return [C + "{0,3}"]
  }
  return ["([" + L + "]{0,3}|[" + C + "]{0,3}|[" + R + "]{0,3})?"]
}
f = S => {
  for (W = [S[0] + "{1,2}"],i = 1; i < S.length - 1; i++)
    W.push(...corner(S[i - 1], S[i], S[i + 1], S[i + 2], W))
  return [
    new RegExp("^" + W.join("") + S[S.length - 1] + "{1,3}$"),
    new RegExp("^" + W.filter(C=>!~C.indexOf("[")).join("") + S[S.length - 1] + "{1,3}$")
  ]
}
thirdPass = (F, C) => {
  if (!F[0]) return null
  F = F.filter((s,i)=>!F[i - 1] || F[i - 1] != s)
  FF = F.map(T=>[...T].filter((c,i)=>!T[i - 1] || T[i - 1] != c).join(""))
  if (FF.length == 1) return F[0];
  if (FF.length < 6 && FF[0][2] && FF[1][2] && FF[0][0] == FF[1][0] && FF[0][1] == FF[1][1])
    if (Math.abs(F[0].length - F[1].length) < 1)
      for (i=0;i<Math.min(F[0].length, FF[1].length);i++) {
        if (C.indexOf(FF[0][i]) < C.indexOf(FF[1][i])) return F[0]
        else if (C.indexOf(FF[0][i]) > C.indexOf(FF[1][i])) return F[1]
      }
  return F[0]
}
var skip = false;
SwiftKey = C => (
  C = [...C].filter((c,i)=>!C[i - 1] || C[i - 1] != c).join(""),
  skip = false, matched = [], secondPass = [], L = C.length, reg = f(C),
  words.forEach(W=>W.match(reg[0])&&matched.push(W)),
  words.forEach(W=>W.match(reg[1])&&secondPass.push(W)),
  matched = matched.sort((a,b)=>Math.abs(L-a.length)>Math.abs(L-b.length)),
  secondPass = secondPass.sort((a,b)=>Math.abs(L-a.length)>Math.abs(L-b.length)),
  first = matched[0], second = secondPass[0], third = thirdPass(secondPass.length? secondPass: matched, C),
  second && second.length >= first.length - 1? first != third ? third: second: third.length >= first.length ? third: first
)

// For use by js shell of latest firefox
print(SwiftKey(readline()));

The code assumes a variable called words is present which is an array of all the words from this page
See the code in action here
See the test cases in action here
Both the above link work only on a latest Firefox (33 and above) (due to ES6).

Yup! I'm shelling out with shells. You can also use the proper keypos.csv file now. The IO functions avalible are listed at https://developer.mozilla.org/en-US/docs/Mozilla/Projects/SpiderMonkey/Introduction_to_the_JavaScript_shell

It's fine, but the swipes are made with my keyboard angles, so it's your choice (doesn't seem to have affected your score, though!)

Sure done. https://github.com/matsjoyce/codegolf-swipe-type/blob/master/logs/Three%20Pass%20Optimizer.log

240 passes is outstanding! I would have thought that ambiguities would prevent such good results. I'll be curious how this will perform on the final test set.

@Emil - Yeah, I am waiting to see that too.

@Emil I'll probably run the final set in ten days or so (unless the question becomes wildly popular, and I'll leave it longer). In the meantime, would making a second test set be useful?

@matsjoyce yeah.

@Emil Done. Interesting how solid camelNeck's solution is (identical score) (actually most of the solutions got the same score, so my test-case validation method must work)

This just means that I've got more data to improve my algorithm on an overall set.

Ruby, Regex Solver - 30 140 176 180 182 187 and 179 183 passes
I'll figure out the score later. Here is very naive solution that doesn't take the keyboard layout into account:
words = File.readlines('wordlist').map(&:chomp)

swipe = ARGV.shift
puts words.select {|word| word[0] == swipe[0] &&
                          word[-1] == swipe[-1]}
          .select {|word|
              chars = [word[0]]
              (1..word.size-1).each {|i| chars << word[i] if word[i] != word[i-1]}
              swipe[Regexp.new('^'+chars.join('.*')+'$')]
          }.sort_by {|word| word.size}[-1]

It takes input from ARGV and prints the result. I'm just filtering the word list by first and last letter, and them I'm trying all of the remaining words against the input (eliminating duplicate letters and using a regex like ^g.*u.*e.*s$ for "guess") and return the first of those if there are multiple solutions.
Run it like
ruby regex-solver.rb cvhjioiugfde

Anyone else, feel free to reuse this step as a first filter - I believe it won't throw out any correct words, so this preliminary check can greatly reduce the search space for better algorithms.
Edit: Following the OPs suggestion, I'm now selecting the longest of the candidates, which seems to be a decent heuristic.
Also thanks to es1024 for reminding me about duplicate letters.

Done. Your log's at https://github.com/matsjoyce/codegolf-swipe-type/blob/master/logs/Regex%20Solver.log I think the problem is that it selects from the possible solutions randomly, which could be improved by selecting the longest, or something else.

I think this might throw out all correct words with two identical letters next to each other, such as paradoxically, as the l would only appear once in the input, rather than twice as demanded by the regex.

@es1024, ah thanks, when I first proposed this algorithm back in the sandbox, I was actually aware of that, but forgot about it yesterday. Will fix later.

C++, Discrete Fréchet Distance - 201 220 222 232 and 232 passes
To me, the problem very much called for the Fréchet Distance which unfortunately is very hard to compute.
Just for fun, I've tried to approach the problem by implementing a discrete approximation described by Thomas Eiter and Heikki Mannila in Computing Discrete Fréchet Distance (1994).
At first, I'm using the same approach as the others for filtering all words in the list which are subsequences of the input (also accounting for multiple sequential occurances of the same character).
Then, I'm filling the polygon curve from letter to letter of every word with intermediate points and match it against the input curve.
Finally, I divide every distance by the length of the word and take the minimum score.
So far, the method doesn't work as well as I had hoped (It recognizes the code example as "chide"), but this could just be the result of bugs I haven't found yet. Else, another idea would be to use other variations of the fréchet distance ("average" instead of "maximum dog leash length").
Edit: Now, I'm using an approximation to the "average dog leash length". This means that I'm finding an ordered mapping between both paths which minimizes the sum of all distances and later divide it by the number of distances.
If the same character appears twice or more often in the dictionary word, I only put one node in the path.
#include<iostream>
#include<fstream>
#include<vector>
#include<map>
#include<algorithm>
#include<utility>
#include<cmath>

using namespace std;

const double RESOLUTION = 3.2;

double dist(const pair<double, double>& a, const pair<double, double>& b) {
    return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}

double helper(const vector<pair<double, double> >& a,
        const vector<pair<double, double> >& b,
        vector<vector<double> >& dp,
        int i,
        int j) {
    if (dp[i][j] > -1)
        return dp[i][j];
    else if (i == 0 && j == 0)
        dp[i][j] = dist(a[0], b[0]);
    else if (i > 0 && j == 0)
        dp[i][j] = helper(a, b, dp, i - 1, 0) +
                   dist(a[i], b[0]);
    else if (i == 0 && j > 0)
        dp[i][j] = helper(a, b, dp, 0, j - 1) +
                   dist(a[0], b[j]);
    else if (i > 0 && j > 0)
        dp[i][j] = min(min(helper(a, b, dp, i - 1, j),
                           helper(a, b, dp, i - 1, j - 1)),
                       helper(a, b, dp, i, j - 1)) +
                   dist(a[i], b[j]);
    return dp[i][j];
}

double discretefrechet(const vector<pair<double, double> >& a, const vector<pair<double, double> >& b) {
    vector<vector<double> > dp = vector<vector<double> >(a.size(), vector<double>(b.size(), -1.));
    return helper(a, b, dp, a.size() - 1, b.size() - 1);
}

bool issubsequence(string& a, string& b) {
    // Accounts for repetitions of the same character: hallo subsequence of halo
    int i = 0, j = 0;
    while (i != a.size() && j != b.size()) {
        while (a[i] == b[j])
            ++i;
        ++j;
    }
    return (i == a.size());
}

int main() {
    string swipedword;
    cin >> swipedword;

    ifstream fin;
    fin.open("wordlist");
    map<string, double> candidatedistance = map<string, double>();
    string readword;
    while (fin >> readword) {
        if (issubsequence(readword, swipedword) && readword[0] == swipedword[0] && readword[readword.size() - 1] == swipedword[swipedword.size() - 1]) {
            candidatedistance[readword] = -1.;
        }
    }
    fin.close();

    ifstream fin2;
    fin2.open("keypos.csv");
    map<char, pair<double, double> > keypositions = map<char, pair<double, double> >();
    char rc, comma;
    double rx, ry;
    while (fin2 >> rc >> comma >> rx >> comma >> ry) {
        keypositions[rc] = pair<double, double>(rx, ry);
    }
    fin2.close();

    vector<pair<double, double> > swipedpath = vector<pair<double, double> >();
    for (int i = 0; i != swipedword.size(); ++i) {
        swipedpath.push_back(keypositions[swipedword[i]]);
    }

    for (map<string, double>::iterator thispair = candidatedistance.begin(); thispair != candidatedistance.end(); ++thispair) {
        string thisword = thispair->first;
        vector<pair<double, double> > thispath = vector<pair<double, double> >();
        for (int i = 0; i != thisword.size() - 1; ++i) {
            pair<double, double> linestart = keypositions[thisword[i]];
            pair<double, double> lineend = keypositions[thisword[i + 1]];
            double linelength = dist(linestart, lineend);
            if (thispath.empty() || linestart.first != thispath[thispath.size() - 1].first || linestart.second != thispath[thispath.size() - 1].second)
                thispath.push_back(linestart);
            int segmentnumber = linelength / RESOLUTION;
            for (int j = 1; j < segmentnumber; ++j) {
                thispath.push_back(pair<double, double>(linestart.first + (lineend.first - linestart.first) * ((double)j) / ((double)segmentnumber),
                                    linestart.second + (lineend.second - lineend.second) * ((double)j) / ((double)segmentnumber)));
            }
        }
        pair<double, double> lastpoint = keypositions[thisword[thisword.size() - 1]];
        if (thispath.empty() || lastpoint.first != thispath[thispath.size() - 1].first || lastpoint.second != thispath[thispath.size() - 1].second)
        thispath.push_back(lastpoint);

        thispair->second = discretefrechet(thispath, swipedpath) / (double)(thispath.size());
    }

    double bestscore = 1e9;
    string bestword = "";
    for (map<string, double>::iterator thispair = candidatedistance.begin(); thispair != candidatedistance.end(); ++thispair) {
        double score = thispair->second;
        if (score < bestscore) {
            bestscore = score;
            bestword = thispair->first;
        }
        // cout << thispair->first << ": " << score << endl;
    }
    cout << bestword << endl;

    return 0;
}

I've compiled the code with clang, but g++ ./thiscode.cpp -o ./thiscode should also work fine.

Yes! Somebody has finally added a solution with a big fat algorithm name! Your log is at https://github.com/matsjoyce/codegolf-swipe-type/blob/master/logs/Discrete%20Fr%C3%A9chet%20Distance.log

Let's rather call it a simple dynamic programming algorithm for a big fat computer science problem.

For some reason, this seems to fail for the input of programmijng -- it gives me pang.

That's strange. I'm getting programming like it should. Could you please uncomment the line // cout << thispair->first << ": " << score << endl; and paste the resulting scores?

Python 2, Turnarounds, 224 226 230 232 and 230 234 passes
This is quite a straight forward approach:

Find the points where the flow of letters changes direction (plus start and end).
Output the longest word that includes all these turning points.

import sys, csv, re

wordlistfile = open('wordlist', 'r')
wordlist = wordlistfile.read().split('\n')

layout = 'qwertyuiop asdfghjkl  zxcvbnm'
keypos = dict((l, (2*(i%11)+i/11, i/11)) for i,l in enumerate(layout))

#read input from command line argument
input = sys.argv[1]

#remove repeated letters
input = ''.join(x for i,x in enumerate(input) if i==0 or x!=input[i-1])

#find positions of letters on keyboard
xpos = map(lambda l: keypos[l][0], input)
ypos = map(lambda l: keypos[l][1], input)

#check where the direction changes (neglect slight changes in x, e.g. 'edx')
xpivot = [(t-p)*(n-t)<-1.1 for p,t,n in zip(xpos[:-2], xpos[1:-1], xpos[2:])]
ypivot = [(t-p)*(n-t)<0 for p,t,n in zip(ypos[:-2], ypos[1:-1], ypos[2:])]
pivot = [xp or yp for xp,yp in zip(xpivot, ypivot)]

#the first and last letters are always pivots
pivot = [True] + pivot + [True]

#build regex
regex = ''.join(x + ('+' if p else '*') for x,p in zip(input, pivot))
regexobj = re.compile(regex + '$')

#find all words that match the regex and output the longest one
words = [w for w in wordlist if regexobj.match(w)]
output = max(words, key=len) if words else input
print output

Run as
python turnarounds.py tyuytrghn

The solution is not very robust. A single wrong keystroke would make it fail. However, since the set of test cases has very little no misspellings it performs quite well, only getting confused in some cases where it picks too long words.
Edit: I changed it a bit to not use the provided key position file but a simplified layout. This makes it easier for my algorithm because in the file the keys are not evenly spaced. I can achieve even slightly better results by including some ad-hoc tiebreakers for ambiguous cases, but that would be over-optimizing for this particular test set. Some fails remain that are not actually ambiguous but that I don't catch with my simple algorithm because it only considers direction changes of more than 90 degrees.

Well done! Current leader! If you want to see the log, goto https://github.com/matsjoyce/codegolf-swipe-type/blob/master/logs/Turnaround.log

@matsjoyce: I've added a comment to the question pointing out the two spelling mistakes I think I've found. :)

Yes, thanks, I'm just giving it another check. I'm not quite sure what to do with ambiguous cases, though.

@matsjoyce: Some ambiguities could be resolved by choosing a another of the possible paths across the keyboard. E.g. brats could be 'bgrdsasdrtrds'which cannot be confused with breasts. However, I also wouldn't mind if you left it as it is.

True, that would work. I'm just worried that if this set is made too 'optimal', and the final scoring set is not put up to much scrutiny, some solutions may not perform as well

PHP, Direction Checker, 203 213 216 229 231 and 229 233 passes
This begins with a simple pass through the dictionary to obtain a list of words whose letters are all present in the input (what Martin did here), and also only checking for l.* instead of l.*l.* when l is duplicated.
The longest word here is then saved in a variable.
Another check is then done, based on the keys at the points where the swipe changes direction (+/0 to - or -/0 to +, in either x or y). The list of possible words is checked against this list of characters, and words that do not match are eliminated. This approach relies on sharp turns in swiping to be accurate.
The longest remaining word is outputted, or if no words are left, the longest word from earlier is outputted instead.
Edit: Added all characters in a horizontal line leading up to a change in direction as possible values to check for.
PHP 5.4 is required (or replace all [..] with array(..)).
<?php
function get_dir($a, $b){
    $c = [0, 0];
    if($a[0] - $b[0] < -1.4) $c[0] = 1;
    else if($a[0] - $b[0] > 1.4) $c[0] = -1;
    if($a[1] < $b[1]) $c[1] = 1;
    else if($a[1] > $b[1]) $c[1] = -1;
    return $c;
}
function load_dict(){
    return explode(PHP_EOL, file_get_contents('wordlist'));
}

$coord = [];
$f = fopen('keypos.csv', 'r');
while(fscanf($f, "%c, %f, %f", $c, $x, $y)){
    $coord[$c] = [$x, $y];
}
fclose($f);

$dict = load_dict();
$in = $argv[1];
$possib = [];

foreach($dict as $c){
    if($c[0] == $in[0]){
        $q = strlen($c);
        $r = strlen($in);
        $last = '';
        $fail = false;
        $i = $j = 0;
        for($i = 0; $i < $q; ++$i){
            if($last == $c[$i]) continue;
            if($j >= $r){
                $fail = true;
                break;
            }
            while($c[$i] != $in[$j++])
                if($j >= $r){
                    $fail = true;
                    break;
                }
            if($fail) break;
            $last = $c[$i];
        }
        if(!$fail)
            $possib[] = $c;
    }
}

$longest = '';
foreach($possib as $p){
    if(strlen($p) > strlen($longest))
        $longest = $p;
}

$dir = [[0, 0]];
$cdir = [0, 0];
$check = '/^' . $in[0] . '.*?';
$olst = []; $p = 1;

$len = strlen($in);
for($i = 1; $i < $len; ++$i){
    $dir[$i] = get_dir($coord[$in[$i - 1]], $coord[$in[$i]]);
    $olddir = $cdir;
    $newdir = $dir[$i];
    $xc = $olddir[0] && $newdir[0] && $newdir[0] != $olddir[0];
    $yc = $olddir[1] && $newdir[1] && $newdir[1] != $olddir[1];
    if($xc || $yc){ // separate dir from current dir
        if($yc && !$xc && $dir[$i - 1][1] == 0){
            $tmp = '';
            for($j = $i - 1; $j >= 0 && $dir[$j][1] == 0; --$j){
                $tmp = '(' . $in[$j-1] . '.*?)?' . $tmp;
            }
            $olst[] = range($p, $p + (($i - 1) - $j));
            $p += ($i - 1) - $j + 1;
            $check .= $tmp . '(' . $in[$i - 1] . '.*?)?';
        }else{
            $check .= $in[$i - 1] . '.*?';
        }
        $cdir = $dir[$i];
    }else{
        if(!$cdir[0]) $cdir[0] = $dir[$i][0];
        if(!$cdir[1]) $cdir[1] = $dir[$i][1];
    }
}
$check .= substr($in, -1) . '$/';
$olstc = count($olst);
$res = [];
foreach($possib as $p){
    if(preg_match($check, $p, $match)){
        if($olstc){
            $chk = array_fill(0, $olstc, 0);
            for($i = 0; $i < $olstc; ++$i){
                foreach($olst[$i] as $j){
                    if(isset($match[$j]) && $match[$j]){
                        ++$chk[$i];
                    }
                }
                // give extra weight to the last element of a horizontal run
                if(@$match[$olst[$i][count($olst[$i])-1]])
                    $chk[$i] += 0.5;
            }
            if(!in_array(0, $chk)){
                $res[$p] = array_sum($chk);
            }
        }else{
            $res[$p] = 1;
        }
    }
}
$possib = array_keys($res, @max($res));
$newlong = '';
foreach($possib as $p){
    if(strlen($p) > strlen($newlong))
        $newlong = $p;
}
if(strlen($newlong) == 0) echo $longest;
else echo $newlong;

@matsjoyce Missed that bullet point while reading through the question. Code now uses the positions from keypos.csv

@es1024 While not part of the 250 test cases, the word list does contain 238 words with three consecutive letters (so far, all I've checked are words ending in sss) - I don't think your duplicate elimination would catch those.

If you need it, your logs at https://github.com/matsjoyce/codegolf-swipe-type/blob/master/logs/Direction%20Checker.log

Python 3, Corner Simulator, 241 and 240 passes
Algorithm:

Deduplicate (remove consecutive runs of the same character) the input and all the words in the word list (using a dictionary to get the original words back)
Remove all words that do not start and end with the start and end of the swipe (first pass)
Make a regex out of all the corners greater than 80 degrees, then remove all words which do not match this (second pass)
Regex each word (like Regex Solver) against the swipe, then split the swipe into a series of theoretically straight lines, and check if they are straight and could have been produced by a finger moving along that line (significant_letter function) (third pass)
Sort the words by closeness to the straight lines
Then use length as a tie breaker (longer is better)
Then use Levenshtein distance as the final tie breaker
Output word!

Code:
# Corner Sim

from math import atan, degrees, pi, factorial, cos, radians
import csv
import re
import sys

keys = {}
key_size = 1.5
for line in open("keypos.csv"):
    k, x, y = map(str.strip, line.split(","))
    keys[k] = float(x), float(y)

def deduplicate(s):
    return s[0] + "".join(s[i + 1] for i in range(len(s) - 1) if s[i + 1] != s[i])

def angle(coord1, coord2):
    x1, y1, x2, y2 = coord1 + coord2
    dx, dy = x2 - x1, y1 - y2
    t = abs(atan(dx/dy)) if dy else pi / 2
    if dx >= 0 and dy >= 0: a = t
    elif dx >= 0 and dy < 0: a = pi - t
    elif dx < 0 and dy >= 0: a = 2 * pi - t
    else: a = t + pi
    return degrees(a)

def significant_letter(swipe):
    if len(swipe) <= 2: return 0
    x1, y1, x2, y2 = keys[swipe[0]] + keys[swipe[-1]]
    m = 0 if x2 == x1 else (y2 - y1) / (x2 - x1)
    y = lambda x: m * (x - x1) + y1
    def sim_fun(x2, y2):
        try: return (x2 / m + y2 - y1 + x1 * m) / (m + 1 / m)
        except ZeroDivisionError: return x2
    dists = []
    for i, key in enumerate(swipe[1:-1]):
        sx, bx = min(x1, x2), max(x1, x2)
        pos_x = max(min(sim_fun(*keys[key]), bx), sx)
        sy, by = min(y1, y2), max(y1, y2)
        pos_y = max(min(y(pos_x), by), sy)
        keyx, keyy = keys[key]
        dist = ((keyx - pos_x) ** 2 + (keyy - pos_y) ** 2) ** 0.5
        a = angle((keyx, keyy), (pos_x, pos_y))
        if 90 <= a <= 180: a = 180 - a
        elif 180 <= a <= 270: a = a - 180
        elif 270 <= a <= 360: a = 360 - a
        if a > 45: a = 90 - a
        h = key_size / 2 / cos(radians(a))
        dists.append((max(dist - h, 0), i + 1, key))
    return sorted(dists, reverse=True)[0][0]

def closeness2(s, t):
    # https://en.wikipedia.org/wiki/Levenshtein_distance
    if s == t: return 0
    if not len(s): return len(t)
    if not len(t): return len(s)
    v0 = list(range(len(t) + 1))
    v1 = list(range(len(t) + 1))
    for i in range(len(s)):
        v1[0] = i + 1
        for j in range(len(t)):
            cost = 0 if s[i] == t[j] else 1
            v1[j + 1] = min(v1[j] + 1, v0[j + 1] + 1, v0[j] + cost)
        for j in range(len(v0)):
            v0[j] = v1[j]
    return v1[len(t)] / len(t)

def possible(swipe, w, s=False):
    m = re.match("^" + "(.*)".join("({})".format(i) for i in w) + "$", swipe)
    if not m or s:
        return bool(m)
    return closeness1(swipe, w) < 0.8

def closeness1(swipe, w):
    m = re.match("^" + "(.*)".join("({})".format(i) for i in w) + "$", swipe)
    unsigpatches = []
    groups = m.groups()
    for i in range(1, len(groups), 2):
        unsigpatches.append(groups[i - 1] + groups[i] + groups[i + 1])
    if debug: print(unsigpatches)
    sig = max(map(significant_letter, unsigpatches))
    if debug: print(sig)
    return sig

def find_closest(swipes):
    level1, level2, level3, level4 = swipes
    if debug: print("Loading words...")
    words = {deduplicate(i.lower()): i.lower() for i in open("wordlist").read().split("\n") if i[0] == level1[0] and i[-1] == level1[-1]}
    if debug: print("Done first filter (start and end):", words)
    r = re.compile("^" + ".*".join(level4) + "$")
    pos_words2 = list(filter(lambda x: bool(r.match(x)), words))
    if debug: print("Done second filter (sharpest points):", pos_words2)
    pos_words = pos_words2 or words
    pos_words = list(filter(lambda x: possible(level1, x), pos_words)) or list(filter(lambda x: possible(level1, x, s=True), pos_words))
    if debug: print("Done third filter (word regex):", pos_words)
    sorted_pos_words = sorted((closeness1(level1, x), -len(x), closeness2(level1, x), x)
                              for x in pos_words)
    if debug: print("Closeness matching (to", level2 + "):", sorted_pos_words)
    return words[sorted_pos_words[0][3]]

def get_corners(swipe):
    corners = [[swipe[0]] for i in range(4)]
    last_dir = last_char = None
    for i in range(len(swipe) - 1):
        dir = angle(keys[swipe[i]], keys[swipe[i + 1]])
        if last_dir is not None:
            d = abs(last_dir - dir)
            a_diff = min(360 - d, d)
            corners[0].append(last_char)
            if debug: print(swipe[i], dir, last_dir, a_diff, end=" ")
            if a_diff >= 55:
                if debug: print("C", end=" ")
                corners[1].append(last_char)
            if a_diff >= 65:
                if debug: print("M", end=" ")
                corners[2].append(last_char)
            if a_diff >= 80:
                if debug: print("S", end=" ")
                corners[3].append(last_char)
            if debug: print()
        last_dir, last_char = dir, swipe[i + 1]
    tostr = lambda x: deduplicate("".join(x + [swipe[-1]]).lower())
    return list(map(tostr, corners))

if __name__ == "__main__":
    debug = "-d" in sys.argv
    if debug: sys.argv.remove("-d")
    swipe = deduplicate(sys.argv[1] if len(sys.argv) > 1 else input()).lower()
    corners = get_corners(swipe)
    if debug: print(corners)
    print(find_closest(corners))

Run with python3 entries/corner_sim.py

This was a valid answer. No need to make mine the answer.

@Optimizer Well, the meta discussion seems to favour accepting your answer, so its fine by me.

After reading that meta discussion only, I was okay with your decision, but this is also good (better) :)

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

authors: Googlë สรัน ชาหลวง

sort: votes


text:
9 Holes of Code Golf - Kickoff
There has already been a 9 Hole Challenge (and another one here), but that was soooo last year. And besides, I have only been around for 2 months (although it seems like forever). And it is considerably different.
Leader Board: (note that weighting for holes are not established yet)
+---------------+------------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+
|Competitor     | Language   | Hole 1 | Hole 2 | Hole 3 | Hole 4 | Hole 5 | Hole 6 | Hole 7 | Hole 8 | Hole 9 | Total  |
+----------------------------------------------------------------------------------------------------------------------+
|Dennis         |CJam        |        | 31     |        |        |        |        |        |        |        | 31     |
+----------------------------------------------------------------------------------------------------------------------+
|Optimizer      |CJam        |        | 35     |        |        |        |        |        |        |        | 35     |
+----------------------------------------------------------------------------------------------------------------------+
|Martin Büttner |Mathematica |        | 222    |        |        |        |        |        |        |        | 222    |
+----------------------------------------------------------------------------------------------------------------------+
|Cameron        |Python      | 878    |        |        |        |        |        |        |        |        | 878    |
+----------------------------------------------------------------------------------------------------------------------+
|bubalou        |Processing 2| 717    |        |        |        |        |        |        |        |        | 717    |
+----------------------------------------------------------------------------------------------------------------------+
|Doorknob       |Python 2    |        |        |0.079711|        |        |        |        |        |        |0.079711|
+----------------------------------------------------------------------------------------------------------------------+
|Vulcan         |Java        |        |        |0.6949  |        |        |        |        |        |        |0.6949  |
+----------------------------------------------------------------------------------------------------------------------+
|Eli            |C++         |        |        |1.42042 |        |        |        |        |        |        |1.42042 |
+---------------+------------+--------+--------+--------+--------+--------+--------+--------+--------+--------+--------+

Other Holes:

hole 2
hole 3

It's been slow around here lately, so I am here to kick off the next 9 hole golf course, involving a smattering of all that I have seen here in my (albeit limited) experience. This will entail:

Ascii Art
Graphical Output
Conway's Game of Life
King of the Hill
Kolmogorov complexity
Quines
Image processing
Math
Classic code golf.

I am really looking forward to seeing what you can do!
Competition Rules

You will choose 1 language for all of the holes (that you participate in...see point 4 for more info).
For all holes - standard loopholes are (still) not funny.
The next challenge will appear when I see that there are enough submissions given a reasonable amount of time. King of the hill, for example, will take longer.
You do not have to participate in all of the holes. If you find a hole particularly challenging, don't have the time to do it, etc, you will receive 2 times as many points as the lowest score. Please do not take advantage of this rule by leaving 1 golfscript answer with 12 characters and taking 24 as a score.

Scoring

Your score is based on the culmination of the scores from all of the holes
Lowest score wins (as per real golf)
The leaderboard will be placed at the top of this page

I will try my very best to make sure that no questions are duplicates, all questions have objective criteria, are well written, and that they all have (relatively) equal weight in the context of the whole contest.
However, Please be patient when I fail.
And, without further ado, the first challenge!
The Plasma Globe
A plasma globe is everyone's favorite toy:

Your job it to draw one.
You must draw a base:

a globe:

A tesla thingy (?)

And, of course, cool plasma shoots:

However, when you put your hand near a plasma globe (or a conductive object as Wikipedia tells me), it attracts the plasma.
Your globe should reflect that.
To put it quantitatively, your globe has a maximum of 16 shoots (see above picture). An "object" on the surface of the globe (given by an angle in radians) will contain "conductive power", that is, the amount of beams it attracts. So an object with a power of 5 will attract 5 beams (a single line with thickness 5) leaving 11 to spread evenly among the rest of the globe:

Note that
1. the black circle in the middle remains above the plasma
2. that in this example, the angle would be pi/2.
You may have more than one conductive object, and in that event, it is not required that the shoots are equally spaced apart. However, they be relatively spaced out. For example, this is ok for 2 objects, 1 at angle pi/4 power 5 and another at angle 5pi/3 power 3:

You should be able to see each of the end points of the shoots (of plasma).
However, given an object (or sum of objects) with power greater than 16, the globe will "break":

Notes

The globe's diameter is 1.5 times bigger than the length of the base, which is a square
When the globe breaks, the globe is on the right side. It is tangent to the right side of the base as well as the ground. There should be no plasma when the plasma globe is broken (why? safety features of course! No word on how it broke in the first place.)
The color of everything except the shoots must be black, and 1 pixel thick. The color of the plasma has hue 245 - 280, and saturation/value 100. Use this under "HSV" if you have no idea what I am talking about.

Input
Input can be through STDIN/command line args/whatever or through function arguments.
There should be 2 inputs - length of the base of the plasma globe (include an axis if using vector graphics), and an array of objects like this:
[[angle,power],[angle,power],[angle,power]]

So for no objects (see first picture with 16 lines) the input would be
100,[]

For the next (one object, power 5) it would be:
100,[[1.570796,5]]

For the last example:
100,[[0.785398,5],[5.23598,3]]

This is code-golf, so shortest code in bytes wins.

@MartinBüttner If the image does not get smaller when the base-length get smaller, include an axis

In your second example. What if the second object was at -3/8π? In that case it would overlap exactly with one of the other beams. Do we have to rotate all the beams in such a case? If so, I think you need to specify how far away the individual beams need to be from the object-induced beams.

You should rotate the rest of the beams in the event of an exact overlap, as you said. Each beam should be visually distinct from one another, so I should see the object induced beam as being separate from the beam it is close to. If you need more specification, you can use .1 as the minimum angle. However, I don't want to specify this too much, because a beam of power 15 will cover much more than a beam of power 3, therefore needing a much greater buffer distance.

er.... why the column "hole 2" of the board is already filled even if there are no answers?

How big should the square become? Is it required to have a line (or anything else that visually distinguishes it from the background)?

Does the globe have to be exactly centered at the top of the square?

A little help to better visualize this: http://inear.se/plasmaball/

@user2428118 The globe should be centered above (and tangent to) the square... Within a pixel or 2 is fine. The square should be visible - so yes, it should be distinguishable from the background.

@xem um, there are answers to hole 2, so why not post them? This doesn't necessarily have to go in order...

If only I could think of a reliable way to ensure that object-induced beams and leftover beams never overlap...

ah ok each hole has its own thread. nevermind ten ;)

@StretchManiac Acc. to your rules. If answers in first and second hole remain like what they are now, Cameron gets over 800 point advantage over the rest of the 3 participants. (Re: if you do not participate in a hole, you get double of worst score)

@Optimizer I was going to do update weights and no answers only periodically (rather than every time someone answers). Otherwise, it would require substantial changes whenever anyone answers. Think of it as a raw score table, not as the actual winning table (though I will throw one up eventually).

@StretchManiac You did not get my point. Your that rule is putting the other three contenders to a great disadvantage.

@Optimizer All of the scores will eventually become the same weight - so the hole 2 scores might be multiplied by 30 (as an example) to even the scores out. Then the double rule will take effect.

Processing 2 - 717 characters
As processing is a language made for artists, and I am a very novice programmer, I do not expect to do very well on many of these challenges. That being said, I really like how simple it is to draw things in processing, and I have been meaning to play around with it some more, so these challenges should be interesting.
int j,m,b,k,d,l;float w,c,h,x,y,z;float v[],p[],g[];void setup(){j=m=d=0;c=z=0;String i[]= loadStrings("f.txt");i[0]=i[0].replace("[","").replace("]","");String o[]=split(i[0],',');v=new float[o.length];p=new float[o.length-1];for(String s:o){if(!s.equals("")){v[j]=Float.parseFloat(s);}j++;}w=v[0];size((int)w*3,(int)w*3);h=w*.75;l=v.length;noLoop();}void draw(){translate(w/2,height);scale(1,-1);rect(0,0,w,w);if(l>2){while(m<j-1){m+=2;c+=v[m];}}if(c>16){ellipse(w+h,h,2*h,2*h);rect(w/2,w,1,h);}else{ellipse(w/2,w+h,2*h,2*h);rect(w/2,w,1,h);b=16;m=1;stroke(#1500ff);if(l>2){while(m<j){p[m-1]=cos(v[m])*h;p[m]=sin(v[m])*h;strokeWeight(v[m+1]);line(w/2,w+h,p[m-1]+w/2,p[m]+w+h);b-=v[m+1];m+=2;}}strokeWeight(1);c=(PI*2)/b;k=b;g=new float[b+b];while(b>0){g[d]=cos(z+c*b)*h;g[d+1]=sin(z+c*b)*h;m=0;if(l>2){while(m<j-1){if(abs(g[d]-p[m])<.1 && abs(g[d+1]-p[m+1])<.1){b=k+1;z=z+.1;d=-2;break;}m+=2;}}b--;d+=2;}d--;while(d>0){line(w/2,w+h,g[d]+w/2,g[d-1]+w+h);d-=2;}}stroke(#000000);fill(#000000);ellipse(w/2,w+h,w/9,w/9);}

I'm sure this can be golfed down considerably and I may try to do that when I have more time, but for now I am happy with it.
reads in a file (f.txt) located in the data folder of the sketch to get its input.  I used Camerons idea of shifting the free beams until they don't overlap.
int j,m,b,k,d,l;
float w,c,h,x,y,z;
float v[],p[],g[];
void setup(){
j=m=d=0;
c=z=0;
String i[]= loadStrings("f.txt");
i[0]=i[0].replace("[","").replace("]","");
String o[]=split(i[0],',');
v=new float[o.length];
p=new float[o.length-1];
for(String s:o){if(!s.equals("")){v[j]=Float.parseFloat(s);}j++;}
w=v[0];
size((int)w*3,(int)w*3);
h=w*.75;
l=v.length;
noLoop();
}

void draw()
{
  translate(w/2,height);
  scale(1,-1);
  rect(0,0,w,w);
  if(l>2)
  {
    while(m<j-1)
    {
      m+=2;
      c+=v[m];
    }
  }
  if(c>16)
  {
    ellipse(w+h,h,2*h,2*h);
    rect(w/2,w,1,h);
  }
  else
  {
    ellipse(w/2,w+h,2*h,2*h);
    rect(w/2,w,1,h);
    b=16;m=1;
    stroke(#1500ff);
    if(l>2)
    {
      while(m<j)
      {
        p[m-1] = cos(v[m]) * h;
        p[m] = sin(v[m]) * h;
        strokeWeight(v[m+1]);
        line(w/2,w+h,p[m-1]+w/2,p[m]+w+h);
        b-=v[m+1];
        m+=2;
      }
    }
    strokeWeight(1);
    c=(PI*2)/b;
    k=b;
    g=new float[b+b];
    while(b>0)
    {
      g[d] = cos(z+c*b) * h;
      g[d+1] = sin(z+c*b) * h;
      m=0;
      if(l>2)
      {
        while(m<j-1)
        {
          if(abs(g[d]-p[m])<.1 && abs(g[d+1]-p[m+1])<.1)
          {
            b=k+1;
            z=z+.1;
            d=-2;
            break;
          }
          m+=2;
        }
      }
      b--;
      d+=2;
    }
    d--;
    while(d>0)
    {
      line(w/2,w+h,g[d]+w/2,g[d-1]+w+h);
      d-=2;
    }
  }
    stroke(#000000);
    fill(#000000);
    ellipse(w/2,w+h,w/9,w/9);
}

Examples:
100,[[0.785398,3],[5.23598,5]]

100,[]

100,[[1.72398,12],[5.23598,5]]

get processing here

Python, 878 chars
By no means is this golfed well, but I wanted to see an answer for this hole.
import matplotlib.pyplot as P
from math import *
L=len
M=min
Y=P.plot
K=P.Circle
Z=P.gcf().gca().add_artist
f=sin
g=cos
k={'color':(0,0,0)}
j={'color':(.16,0,1)}
def Q(S,C):
    P.axis([-S,S*2.5,0,S*3.5],**k)
    Y([0,S,S,0,0],[0,0,S,S,0],**k)
    Y([S/2,S/2],[S,7*S/4],**k)
    Z(K([S/2,7*S/4],S/20,**k))

    k['fill']=False

    A,B=zip(*C)

    N=16-sum(B)
    if N<0:
        Z(K([7*S/4,3*S/4],3*S/4,**k))

    else:
        Z(K([S/2,7*S/4],3*S/4,**k))
        if L(C)==0:
            D(16,0,S)
        elif L(C)==1:
            D(N,A[0],S)
            Y([S/2,S/2+3*S*g(A[0])/4],[7*S/4,7*S/4+3*S*f(A[0])/4],linewidth=B[0],**j)
        else:
            for c in C:
                Y([S/2,S/2+3*S*g(c[0])/4],[7*S/4,7*S/4+3*S*f(c[0])/4],linewidth=c[1],**j)
            D(N,J(N,A),S)
    P.show()

def J(N,A):
    T=d=0
    t=2*pi/N
    while d<0.1:
        T+=0.1
        d=M(M(a-T-floor((a-T)/t)*t for a in A),\
            M(T+ceil((a-T)/t)*t-a for a in A))
    return T

def D(N,I,S):
    a=I
    for i in range(N):
        Y([S/2,S/2+3*S*g(a)/4],[7*S/4,7*S/4+3*S*f(a)/4],**j)
        a+=2*pi/N

And some sample outputs
Q(100,[[pi/4,6],[-4.2*pi/8,1]])

Q(100,[[0.785398,10],[5.23598,7]])

Q(100,[[pi/4,3],[pi/2,3],[3*pi/2,2],[5*pi/4,2]])

How does this ensure that object-induced and free beams never overlap?

I rotate the equally spaced beams by a small amount until I find an orientation that ensures the beams are at least 0.1 radians spaced apart

Ah, right, I expected something like that. Thanks for clarifying!

Np, I've been trying to solve how to maximize the minimal distance between any object-induced beam and any free beam, but its seems to be a difficult question

I think that's the inverse problem to this http://codegolf.stackexchange.com/q/37269/8478

A,B=zip(*C) should save a few bytes

Python 2.7, 378 375
from turtle import *;import sys
(s,P),A,B=eval(sys.argv[1]),90,180
n,S=sum([b for(a,b) in P]),.75*s;l=16-n
for i in 'abcd':fd(s);lt(A)
pu()
if l<0:goto(s+S,0)
else:goto(s/2,s)
pd();circle(S);pu();goto(s/2,s);lt(A);pd();fd(S)
def C():fd(S);fd(-S)
if n<16:
 color('blue')
 for i in range(l):rt(360/l);C()
 for a,p in P:pensize(p);rt(a*57.3);C()
color('black')
shape('circle')

It reads its parameters from commandline argument.
Sample images :
(parameters=100,[[0.785398,5],[5.23598,3]])

(parameters=100,[])

(parameters=100,[[1.72398,12],[5.23598,5]])

I wasn't able to test this, but it's golfed a bit here: https://repl.it/E52i

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/