text:
Tips for golfing in sed
What general tips do you have for golfing in sed? I'm looking for ideas which can be applied to code-golf problems and which are also at least somewhat specific to sed (e.g. "remove comments" is not an answer).
Please post one tip per answer.

Not really a golfing tip (but still a tip for golfing): linefeeds consume just as many bytes as semicolons, so you can keep your code short and readable.

Not a tip either, but a problem: I have GNU sed, yet the F command never worked. Does anyone know why?

@seshoumara F works on my GNU sed (Debian testing).  It just prints - if reading from stdin, of course, but that's expected.  What do you get from sed -e 'F;Q' /etc/hostname?

@TobySpeight That gives this error: char 1: unknown command: F. I have to update sed maybe; what version do you have? The L command also doesn't work, but it's useless anyway since -l n exists. Everything else mentioned on GNU sed's site works.

@seshoumara, my results are on sed (GNU sed) 4.2.2.  Just to check, you don't have POSIXLY_CORRECT set in your environment, do you?  That would turn off most GNU extensions.

@TobySpeight I have sed 4.2.1 so this could be why (updating). And no, I didn't had that set in my environment. Thanks for all the help today.

I opened the chat room bash, sed and dc for all who want to talk and ask about these languages. Let's make a community!

If you need to use labels then for sure you'll want your label names to be as short as possible.  In fact taken to the extreme, you may even use the empty string as a label name:
:    # define label ""
p    # print pattern space
b    # infinite loop! - branch to label ""

As of gnu sed 4.3, this behavior was removed. : now requires a label.

Indeed, here is also the actual git commit link. I guess for PPCG this won't change much, since we are allowed to post answers for GNU sed 4.2.x, but it's good to know, though regrettably, that this trick won't officially work anymore.

The GNU sed documentation describes the s command as "sed's Swiss Army Knife".  But if all you want to do is replace all instances of one character with another, then the y command is what you need:
y/a/b/

is one char shorter than:
s/a/b/g

its also way faster, and can swap chars in place: y/12/21/

When repeatedly replacing in a loop:
loop:
s/foo/bar/g
tloop

it's usually unnecessary to replace globally, as the loop will eventually replace all occurrences:
# GNU sed
:
s/foo/bar/
t

Note also the GNU extension above: a label can have an empty name, saving more precious bytes.  In other implementations, a label cannot be empty, and jumping without a label transfers flow to the end of script (i.e. same as n).

The empty label name is GNU-specific, POSIX requires branches with no argument to jump to the end of the script (seems to be the behavior in the BSDs and Busybox, also in GNU sed if you don't add an empty :)

The nameless label was always a bug in GNU sed, not an extension, and in version 4.3 and higher this bug was, regrettably, fixed. See here.

Consider using extended regex syntax (in GNU sed).  The -r option costs one byte in scoring, but using it just once to eliminate the backslashes from a pair of \(...\) has already paid for itself.

With the additional note that -r seems to be GNU sed specific.

@manat - added (but it's a Community Wiki answer, so you could have edited yourself).

Of course. I just didn't considered it part of the tip, only an additional note.

And it keeps paying for itself when using +, ?, {} and | in regex matches, since no backslashes are needed either.

-E works as an alias to -r in many sed implementations if I remember correctly.

-E also works in older versions of GNU sed though it has been documented only since newer versions. For the new versions GNU wrongly claims that -E is a POSIX option. POSIX does not specify extended regex for sed.

As mentioned in man sed (GNU), you can use any character as a delimiter for regular expressions by using the syntax
\%regexp%

where % is a placeholder for any character.
This is useful for commands like
/^http:\/\//

which are shorter as
\%^http://%

What is mentioned in the GNU sed manual but not in man sed is that you can change the delimiters of s/// and y/// as well.
For example, the command
ss/ssg

removes all slashes from the pattern space.

Read the whole input at once with -z
Often you need to operate on the whole input at once instead of one line at a time. The N command is useful for that:
:
$!{N;b}

...but usually you can skip it and use the -z flag instead.
The -z flag makes sed use NUL (\0) as its input line separator instead of \n, so if you know your input won’t contain \0, it will read all of the input at once as a single “line”:
$ echo 'foo
> bar
> baz' | sed -z '1y/ao/eu/'
fuu
ber
bez

Try it online!

There's no built-in arithmetic, but calculations can be done in unary or in unary-coded decimal.  The following code converts decimal to UCD, with x as the unit and 0 as the digits separator:
s/[1-9]/0&/g
s/[5-9]/4&/g
y/8/4/
s/9/4&/g
s/4/22/g
s/[37]/2x/g
s/[26]/xx/g
s/[1-9]/x/g

and here's the conversion back to decimal:
s/0x/-x/g
s/xx/2/g
y/x/1/
s/22/4/g
s/44/8/g
s/81/9/g
s/42/6/g
s/21/3/g
s/61/7/g
s/41/5/g
s/-//g

These are both taken from an answer to "Multiply two numbers without using any numbers".
Plain old unary can be converted using this pair of loops from this answer to "{Curly Numbers};", where the unit is ;.  I've used v and x to match Roman for 5 and 10; b comes from "bis".
# unary to decimal
:d
/;/{
s/;;;;;/v/g
s/vv/x/g
/[;v]/!s/x\+/&0/
s/;;/b/g
s/bb/4/
s/b;/3/
s/v;/6/
s/vb/7/
s/v3/8/
s/v4/9/
y/;bvx/125;/
td
}

# Decimal to unary
:u
s/\b9/;8/
s/\b8/;7/
s/\b7/;6/
s/\b6/;5/
s/\b5/;4/
s/\b4/;3/
s/\b3/;2/
s/\b2/;1/
s/\b1/;0/
s/\b0//
/[^;]/s/;/&&&&&&&&&&/g
tu

...and if you have to use either of these, you've almost certainly already lost the code golf, though you might still be competitive with Java answers ;-)  Still fun to use though.

The conversion from plain unary to decimal gives wrong answers for unary input equivalent of decimal form X0X, for example 108. The line responsible for this is /[;v]/!s/\b/0/2, which needs to be changed to /[;v]/!s:x\+:&0: for it to work. See here.

@seshoumara, your link seems to be an empty page.  But it's entirely plausible that I made an error when extracting that code from the referenced answer, so I'll just apply your fix.

The link loads correctly, but I was expecting something other than a grey page with "TIO" and something that looks like the Ubuntu logo - is that what's intended?  And I was referring to the second of the answers I referenced (58007), as that's where the plain-unary sample originated.

The TIO link should have contained the corrected code, plus an example input, 108 in unary. On running the code you should have seen the correct result 108, and not 180, as previously generated by that now fixed line of code. Updating the referenced answer is entirely up to you. This is a community wiki.

Append a newline in one byte
The G command appends a newline and the contents of the hold space to the pattern space, so if your hold space is empty, instead of this:
s/$/\n/

You can do this:
G

Prepend a newline in three bytes
The H command appends a newline and the contents of the pattern space to the hold space, and x swaps the two, so if your hold space is empty, instead of this:
s/^/\n/

You can do this:
H;x

This will pollute your hold space, so it only works once. For two more bytes, though, you could clear your pattern space before swapping, which is still a savings of two bytes:
H;z;x

If not explicitly banned by the question, the consensus for this meta question is that numerical input may be in unary.  This saves you the 86 bytes of decimal to unary as per this answer.

Isn't that meta consensus for sed referring to plain old unary format? I have several answers where an input in UCD would help me, in case it's either way.

@seshoumara I meant unary, not UCD

Then the conversion from decimal to plain old unary saves you 126 bytes as per that answer you linked. The 86 bytes is for the conversion to UCD.

I know this is an old thread, but I just found those clumsy decimal to UCD converters, with almost a hundred bytes, some even messing the hold space or requiring special faulty sed versions.
For decimal to UCD I use (68 bytes; former best posted here 87 bytes)
s/$/\n9876543210/
:a
s/\([1-9]\)\(.*\n.*\)\1\(.\)/\3x\2\1\3/
ta
P;d

UCD to decimal is (also 66 bytes; former best posted here 96)
s/$/\n0123456789/
:a
s/\([0-8]\)x\(.*\n.*\)\1\(.\)/\3\2\1\3/
ta
P;d

\n in the replacement is not portable. You can use a different character instead and save two bytes, but you'll need more bytes to remove the appendix instead of P;d; see next remark. Or, if your hold space is empty, do G;s/$/9876543210/ without byte penalty.
If you need further processing, you'll need some more bytes for s/\n.*// instead of P;d.
You could save two bytes each for those buggy old GNU sed versions
No, you can't save those six backslashes as extended regular expressions don't do backreferences

There are no decimal to UCD and back converters posted in this thread that mess the hold space or require faulty sed versions.

Your own answer from April 6th uses the gold space and will only run with old sed versions that violate the POSIX standard.

I'm not doing decimal to UCD conversions! Read the thread again carefully. UCD means that 12 is converted to 0x0xx (what your answer calculates), while plain unary (what my answer calculates) means that 12 is converted to xxxxxxxxxxxx. I chosed @ as symbol, but you get the idea. And further, on PPCG one doesn't need to adhere to the POSIX standard.

If it pleases you, sheriff

Empty regexes are equivalent to the previously encountered regex
(thanks to Riley for discovering this from an anagol submission)
Here is an example where we are tasked with creating 100 @s in an empty buffer.
s/$/@@@@@@@@@@/;s/.*/&&&&&&&&&&/ # 31 bytes
s/.*/@@@@@@@@@@/;s//&&&&&&&&&&/  # 30 bytes

The second solution is 1 byte shorter and uses the fact that empty regexes are filled in with the last encountered regex. Here, for the second substitution, the last regex was .*, so the empty regex here will be filled with .*. This also works with regexes in /conditionals/.
Note that it is the previously encountered regex, so the following would also work.
s/.*/@@@@@@@@@@/;/@*/!s/$/@/;s//&&&&&&&&&&/

The empty regex gets filled with @* instead of $ because s/$/@/ is never reached.

Yes, good answer.  I've even made regexes longer so that they can be re-matched like this (thus making the program shorter).

Unary-UCD-Decimal conversions
The programs below are adapted from solutions in anarchy golf. The solutions below work on GNU sed 4.2.2, where empty labels are allowed. It is possible I've missed better solutions on anarchy golf.
Unary to Decimal, sed -r at 47 bytes
From solutions by %20 and tails. Works only for integers greater than 0. The chosen unary digit (- in the below program) occurs 3 times in the program.
:
s/-/<<123456789-01>/
s/(.)<.*\1(-*.).*>/\2/
t

Try it online! and (bash wrapper for easier testing)
Decimal to UCD, sed at 39 bytes
From a solution by %20. Works on all integers, including negative ones.
:
s/[1-9]/&;/g
y/123456789/012345678/
t

Try it online!
Decimal to Unary (via UCD), sed 55 bytes
From a solution by tails. Works on all integers, including negative ones.
:
s/[1-9]/&;/g
y/123456789/012345678/
s/;0/9;/
t
s/0//g

Try it online! and (bash wrapper)

Instead of clearing the pattern space with s/.*//, use the z command (lowercase) if you go with GNU sed. Besides the lower bytes count, it has the advantage that it won't start the next cycle as the command d does, which can be useful in certain situations.

May also be of benefit if you have invalid multi-byte sequences (which aren't matched by .).

Let's talk about the t and T commands, that although they are explained in the man page, it's easy to forget about it and introduce bugs accidently, especially when the code gets complicated.
Man page statement for t:

If  a s/// has done a successful substitution since the last input line was read and since the last t or T command, then branch to label.

Example showing what I mean: Let's say you have a list of numbers and you want to count how many negatives there are. Partial code below:
1{x;s/.*/0/;x}                   # initialize the counter to 0 in hold space
s/-/&/                           # check if number is negative
t increment_counter              # if so, jump to 'increment_counter' code block
b                                # else, do nothing (start a next cycle)

:increment_counter
#function code here

Looks ok, but it's not. If the first number is positive, that code will still think it was negative, because the jump done via t for the first line of input is performed regardless, since there was a successful s substitution when we initialized the counter! Correct is: /-/b increment_counter.
If this seemed easy, you could still be fooled when doing multiple jumps back and forth to simulate functions. In our example the increment_counter block of code for sure would use a lot of s commands. Returning back with b main might cause another check in "main" to fall in the same trap. That is why I usually return from code blocks with s/.*/&/;t label. It's ugly, but useful.

Expanding upon this tip answer, regarding the conversions between decimal and plain unary number formats, I present the following alternative methods, with their advantages and disadvantages.
Decimal to plain unary: 102 + 1(r flag) = 103 bytes. I counted \t as a literal tab, as 1 byte.
h
:
s:\w::2g
y:9876543210:87654321\t :
/ /!s:$:@:
/\s/!t
x;s:-?.::;x
G;s:\s::g
/\w/{s:@:&&&&&&&&&&:g;t}

Try it online!
Advantage: it is 22 bytes shorter and as extra, it works with negative integers as input
Disadvantage: it overwrites the hold space. However, since it's more likely that you'd need to convert the input integer right at the start of the program, this limitation is rarely felt.
Plain unary to decimal:  102 + 1(r flag) = 103 bytes
s:-?:&0:
/@/{:
s:\b9+:0&:
s:.9*@:/&:
h;s:.*/::
y:0123456789:1234567890:
x;s:/.*::
G;s:\n::
s:@::
/@/t}

Try it online!
Advantage: it is 14 bytes shorter. This time both tip versions work for negative integers as input.
Disadvantage: it overwrites the hold space
For a complicated challenge, you'll have to adapt these snippets to work with other information that may exist in the pattern space or hold space, besides the number to convert. The code can be golfed more, if you know you only work with positive numbers or that zero alone is not going to be a valid input / output.
An example of such challenge answer, where I created and used these snippets, is the Reciprocal of a number (1/x).

For unary-to-decimal you can save two bytes by combining the last two substitutions: s:\n|@$::g. https://tio.run/##K05N@f@/2ErX3krNwIpL30G/2oqr2ComyVLbykANxNSz1HKw0gcyM6yBHC19KyuuSisDQyNjE1MzcwtLKzgLqL0CqERfTwuoxB3IismrcVCxskoHmVpS@/@/Awj8yy8oyczPK/6vWwQA

I had my own try at the decimal to unary converter. Here's 97 bytes :) Try it online! (also doesn't require -r, but with new consensus, flags do not count towards the bytecount anyways, and it doesn't mess up the hold space)

Actually if you change the last line from /\n/ta to /\n/t, you save 1 byte to get 96

@Cowsquack Thanks, 96 is great! Don't have time now, will look on it this weekend.

Sure, do send me a ping on chat then :)

Make use of sed's line-handling ability
With flexible challenge I/O, it can pay to have input/output separated by newlines instead of any other character by taking advantage of sed's commands for handling lines (like D, N, n, G, H, P, s's m flag) instead of only being limited to s substitutions.
This can also open the opportunity for using D for looping instead of labels and goto, especially in sed versions that don't permit empty labels.

The L command in old GNU sed versions
Used, for example, in the second solution in https://codegolf.stackexchange.com/a/220633/. Older versions of GNU sed like GNU sed 4.2.2 have the L command, which was later removed in newer versions. From the archived docs,

L n
This GNU sed extension fills and joins lines in pattern space to produce output lines of (at most) n characters, like fmt does; if n is omitted, the default as specified on the command line is used. This command is considered a failed experiment and unless there is enough request (which seems unlikely) will be removed in future versions.

#n at first to imply -n

The "#" and the remainder of the line are ignored (treated as a comment), with the single exception that if the first two characters in the file are #n, the default output is suppressed; this is the equivalent of specifying -n on the command line.

Source: sed (from SUSv2)
This is useful if you prefer NOT to output something by default.
...But is it really useful? -n adds either 1 or 2 bytes but #n and LF adds 3.

This would be useful in anagol where you can't specify flags.

i, a, and c
(The answer focuses on GNU sed because GNU sed's invocation of these commands is slightly shorter than that of POSIX, but otherwise I think the functionality should be the same).
These insert to, append to, and change the pattern space respectively. The lines they add are printed and so are not edited into the pattern space, meaning that the program will not be able to manipulate these lines. But they are shorter than s, if you want to insert some unchanging lines. Compare the following two lines:
s/^/text\n/ # 11 bytes
itext       #  5 bytes

Now I want to focus on c. c text replaces the pattern space with text. This text will be printed immediately, since the c makes sed move on to the next line. This means that the commands follows a call to c are effectively ignored. This behaviour of c can be useful in challenges where there are only few possible outputs, particularly when combined with the conditional /.../.
An example is the 'Hello, World!' challenge, where c is shorter than s:
s/^/Hello, World!/ # 18 bytes
cHello, World!     # 14 bytes

Another example is this challenge (sed answer) to swap the strings Good and Bad. The outputs are restricted to being Good (when the input is Bad) or Bad (when the input is Good).
s gives 21 bytes:
s/Goo/Ba/;t;s/Ba/Goo/

Using c (in combination with /.../) gives 13 instead:
/B/cGood
cBad

If the input matches /B/, i.e. it the input is Bad, Good is printed and the program skips processing this input line. So the program only ever reaches the second line if the input doesn't match B, i.e. if the input is Good. Then in this case the output is set to Bad.

Mostly useless step:
y|A-y|B-z|

This will only translate A to B and y to z (... and - to - ;), but nothing else,
so
sed -e 'y|A-y|B-z|' <<<'Hello world!'

will just return:
Hello world!

You could ensure this will be useless, for sample by using this on lower-case hexadecimal values (containing only 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e or f.)
A little worst:
sed '; ;/s/b;y|A-y|B-z|;s ;s/ //; ; ;' <<<'Hello world'
Hello world

Why did this not suppress the space?

Is this something you found out the hard way?!  ;-)

In sed, the closest thing to a function that you can have is a label. A function is useful because you can execute its code multiple times, thus saving a lot of bytes. In sed however you would need to specify the return label and as such you can't simply call this "function" multiple times throughout your code the way you would do it in other languages.
The workaround I use is to add in one of the two memories a flag, which is used to select the return label. This works best when the function code only needs a single memory space (the other one).
Example showing what I mean: taken from a project of mine to write a small game in sed
# after applying the player's move, I overwrite the pattern space with the flag "P"
s/.*/P/
b check_game_status
:continue_turn_from_player
#code

b calculate_bot_move
:return_bot_move
# here I call the same function 'check_game_status', but with a different flag: "B"
s/.*/B/
b check_game_status
:continue_turn_from_bot
#code (like say 'b update_screen')

:check_game_status   # this needs just the hold space to run
#code
/^P$/b continue_turn_from_player
/^B$/b continue_turn_from_bot

The labels should be golfed of course to just one letter, I used full names for a better explanation.

Combine s substitutions
The s command takes many bytes (4 + 1 for the statement separator), so combining them can save bytes.
An example: the following is at 17 bytes
s/\S+ //
s/\S+$//

while combining the two substitutions gives 15 bytes
s/^\S+ |\S+$//g

Okay, here's a weird functioning of (GNU) sed's regex. For example, if the pattern space is only qqq, then the extended regex s/^|q|$/<&>/g gives <q><q><q>. Try it online!
I'm not sure, but I think it is because if a character matches, then do the empty strings surrounding it. So because the terminal q matches, the match also includes the end of the pattern space, so $ by itself doesn't get matched because otherwise it would overlap with the previous match (and likewise for ^ and even I think for word boundaries and the like).
An example where this is useful is in the following (rather contrived) task:

an input of a should give ab,
and inputs matching /a(c+)/ should give ab\1b, for example, an input of accc should give abcccb

Without the trick I can get 11 bytes (with the -E flag)
s/a|c+/&b/g

but using it gives 10 bytes
s/a|$/&b/g

Try it online!
(Do let me know if there is a better example that uses this behaviour).

Use back references
Most people know that you can mark some parts of your regex with \(\) and later refer to it as \1 (or \2 for the second and so on) in your substitution.
But you hardly ever see back references, using \1 in the regex itself. For extended regular expressions (option -E to sed), this has been removed from the standard, but GNU sed supports it anyhow, so it works at tio.run, for example.
For example, this ERE (.)\1 matches a double character or this one (.).*\1 appearing twice in the pattern space. See here for an example, how this makes things easier (and much shorter!).
Complicated task like this one looking for matches in a file or this one or this one would almost be impossible without this feature.
Math with back references
And it's great for teaching sed to count. I know you can solve some of those problems using y, but as soon as you have more than one thing to increment or decrement, this is the way to go. See examples here or here or try the 151-byte decimal add online to examine how it works.


text:
Count the crossing words
Consider the following standard 15×15 crossword puzzle grid.

We can represent this in ASCII art by using # for blocks and  (space) for white squares.
     #    #
     #    #
          #
   #   #
###     ##   ##

     ##   #
   #       #
    #   ##

##   ##     ###
       #   #
    #
    #    #
    #    #

Given a crossword grid in the ASCII art format above, determine how many words it holds. (The above grid has 78 words. It happens to be last Monday's New York Times puzzle.)
A word is a group of two or more consecutive spaces running vertically or horizontally. A word starts and ends with either a block or the edge of the grid and always runs top to bottom or left to right, never diagonally or backwards. Note that words can span the whole width of the puzzle, as in the sixth row of the puzzle above. A word does not have to be connected to another word.
Details

Input will always be a rectangle containing the characters # or  (space), with rows separated by a newline (\n). You can assume the grid is made of any 2 distinct printable ASCII characters instead of # and .
You may assume there is an optional trailing newline. Trailing space characters DO count, as they affect the number of words.
The grid will not always be symmetrical, and it may be all spaces or all blocks.
Your program should theoretically be able to work on a grid of any size, but for this challenge it will never be larger than 21×21.
You may take the grid itself as input or the name of a file containing the grid.
Take input from stdin or command line arguments and output to stdout.
If you prefer, you may use a named function instead of a program, taking the grid as a string argument and outputting an integer or string via stdout or function return.

Test cases

Input:
    #
    #
    #

Output: 7 (There are four spaces before each #. The result would be the same if each number sign were removed, but Markdown strips spaces from otherwise empty lines.)
Input:
##
 #
##

Output: 0 (One-letter words don't count.)
Input:
######
#    #
  ####
# ## #
# ## #
#### #

Output: 4
Input: (May 10's Sunday NY Times puzzle)
   #    ##   #
   #    #    #
   #         #
       #     ###   ##
    #       #
##   #   #
        #       ##
      #   ##
   #        ##      #
         #   ###   ##
#   ##         ##   #
##   ###   #
#      ##        #
         ##   #
   ##       #
           #   #   ##
        #       #
##   ###     #
       #         #
       #    #    #
       #   ##    #

Output: 140

Scoring
Shortest code in bytes wins. Tiebreaker is oldest post.

CJam, 18 17 13 11 bytes
2 bytes saved by Dennis.
Uses spaces for filled cells and 1 for empty cells:
qN/_z+:~1-,

Test it here.
Explanation
q    e# Read the entire input.
N/   e# Split into lines.
_z   e# Make a copy and transpose it.
+    e# Add the lines of the two grids together.
:~   e# Evaluate each line which will push a rep-digit number for each empty-cell chunk.
1-   e# Remove all the 1s as these correspond to individual empty cells.
,    e# Get the length of the array.

Slip, 18 + 3 = 21 bytes
>? ( +(X|$^)<<){2}

Run with the flags no (hence the +3), and uses space/X instead of space/#. Annoyingly this is longer than CJam/Pyth, but I guess Slip wasn't designed to be particular golfy...
Try it online. Note that the first example is missing spaces on a few lines.
Explanation
>?           Optionally turn right, hence matching either horizontally or vertically
[space]      Match a space
(    ){2}    Group, twice:
[space]+       Match 1+ spaces
(X|$^)         Either an X or the boundary of the grid
<<             Reverse the match pointer by turning left twice

The n flag makes output print the number of matches, and the o flag enables overlapping matches starting from the same square. The reason for the back-and-forth is because Slip tries matches starting from every square, and we want to make sure we only match a full row rather than a partial one. Slip only returns unique matches, even if they started from different positions.
Note: Originally I had >?(  +(X|$^)<<){2}, with the first space on the inside. This would miss some cases with 2 space long words at the edge, since the pointer would go like this:
XXX       XXX       XXX       XXX
X>        X >       X<        <
XXX       XXX       XXX       XXX

[sp]    [sp]+$^    <<[sp]    [sp]+   (uh oh match fails)

Why are the two flags three bytes?

@ThomasKwa I think the current policy with command line flags is this meta post, which counts the number of bytes as the difference from the usual invocation of the code. So here the difference is between py -3 slip.py regex.txt input.txt and py -3 slip.py regex.txt input.txt no, which is three bytes (including the space before n)

That makes sense. I was thinking about it from an entropy perspective; sometimes I forget that it's characters we count.

Haskell, 81 bytes
import Data.List
m x=sum[1|(_:_:_)<-words x]
f x=m x+m(unlines$transpose$lines x)

Uses spaces  as block characters and any other (non whitespace) character as an empty cell.
How it works: split input into list of words at spaces. Take a 1 for every word with at lease 2 characters and sum those 1s. Apply the same procedure to the transposition (split at \n) of the input. Add both results.

Pyth, 15 14 13 bytes
lftTcjd+.zC.z

I'm using  as seperator and # as fill characters instead of their opposite meaning from the OP. Try it online: Demonstration
Instead of # as fill character this accepts also letters. So you could actually take the solved crossword puzzle, and it would print the number of words. And if you remove the l command, it even prints all words. Test it here: May 10's Sunday NY Times puzzle
Explanation
        .z      all input rows
          C.z   all input columns (C transposes)
       +        add them (all rows and columns)
     jd         join by spaces
    c           split by spaces
 f              filter for pieces T, which satisfy:
  tT              len(T) > 1
l               length, implicitly printed

JavaScript (ES6) 87 121 147
Build the transposition of input string and append it to input, then count the strings of 2 or more spaces.
Run the snippet in Firefox to test.
Credits @IsmaelMiguel, a solution for ES5 (122 bytes):
function F(z){for(r=z.split(/\n/),i=0;i<r[j=0][L='length'];i++)for(z+='#';j<r[L];)z+=r[j++][i];return~-z.split(/  +/)[L]};

F=z=>
(
  r=z.split(/\n/),
  [r.map(r=>z+=r[i],z+='#')for(i in r[0])],
  ~-z.split(/  +/).length
)

// TEST
out=x=>O.innerHTML += x + '\n';

[
'     #    #    \n     #    #    \n          #    \n   #   #       \n###     ##   ##\n               \n     ##   #    \n   #       #   \n    #   ##     \n               \n##   ##     ###\n       #   #   \n    #          \n    #    #     \n    #    #     ', '##\n #\n##', '    #\n    #\n    #',
 '######\n#    #\n  ####\n# ## #\n# ## #\n#### #',
 '   #    ##   #       \n   #    #    #       \n   #         #       \n       #     ###   ##\n    #       #        \n##   #   #           \n        #       ##   \n      #   ##         \n   #        ##      #\n         #   ###   ##\n#   ##         ##   #\n##   ###   #         \n#      ##        #   \n         ##   #      \n   ##       #        \n           #   #   ##\n        #       #    \n##   ###     #       \n       #         #   \n       #    #    #   \n       #   ##    #   '
].forEach(x=>out(x.replace(/ /g,'.')+'\n'+F(x)+'\n'))

What about F=z=>{for(r=z.split(/\n/),i=0;i<r[j=0][L='length'];i++)for(z+='#';j<r[L];)z+=r[j++][i];return~-z.split(/  +/)[L]}? It is 113 bytes long. Your regex was replaced with /  +/ (2 spaces), The j=0 was added in the 'parent' for loop and instead of using the syntax obj.length, I changed to use L='length'; ... obj[L], which is repeated 3 times.

I got it to work on http://www.es6fiddle.net/iakdcpdh/ (instead of F=z=>, I had to use var F=(z,i,L,j,r)=>). I tested it on IE11 and it works!

@IsmaelMiguel well done! and best fit for ES5. Looking at it again, I found something more ES6ish and shorter. Maybe you could publish your solution for ES5.

No, it's alright. It was your solution, I just reduced it. I don't find it fair to answer as if it was my own.

Now that I think about it, you can replace /\n/ with a template string with a real newline between. That saves 1 byte since you don't have to write the escape sequence.

@IsmaelMiguel right, thx. It's a pity that it compromise (even more!) the readability of code, having a significant newline that must be counted and some other newlines just for pretty printing. And 87 or 86 does not matter when competition is at 11..20

You get more functionality. /\n/ can only handle 1 newline style, while the template string can handle the browser's default.

J, 38 bytes
1#.1<[:#;._1 1:,@,.[:(,!.1|:)'#'&=;._2

Try it online!

source: Stack Exchange

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

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

sort: votes


text:
Boggle Board Compression
When working on Non-Palindromic Polyglot Boggle, I found it quite tedious to pack the codes as efficiently as possible onto the Boggle board, even with only two strings. But we're programmers, right? We know how to automate things.
Given a list of strings, you're to generate a Boggle board on which each of those strings can be found (independently of the others). The challenge is to make the Boggle board as small as possible. As this is (hopefully) a rather difficult task, this is a code-challenge: there is no requirement for optimality - the challenge is to do it as well as you can.
Rules

The Boggle board will be rectangular and contain only upper case letters. Therefore, the input strings will also contain only upper case letters.
The usual Boggle rules apply: a string is part of the board if, starting anywhere, you can find the string by repeatedly moving to adjacent characters (horizontally, vertically, or diagonally). To form a single string, you cannot use any cell of the board more than once. However, characters may be reused between different strings.
You've got 30 minutes to process the test data, and your code must not use more than 4 GB of memory. I will give a little bit of leeway on the memory limit, but if your program consistently uses more than 4 GB or spikes significantly above it, I will (temporarily) disqualify it.
I will test all submissions on my own machine, which is running Windows 8. I do have a Ubuntu VM, but if I have to test on that you won't be able to make as much use of the 30 minutes as otherwise. Please include a link to a free interpreter/compiler for your chosen language, as well as instructions on how to compile/run your code.
Your score will be the size of the Boggle board for the test data below (not counting the newlines). In the case of a tie (e.g. because multiple people managed to produce an optimal solution), the winner will be the submission that produces this optimal solution faster.
You must not optimise your code specifically towards the test data. If I suspect anyone of doing so, I reserve the right to generate new test data.

Example
Given the strings
FOO
BAR
BOOM

Once could trivially put them in a 4x3 Boggle board:
FOOX
BARX
BOOM

By making use of the fact that strings don't have to be straight, we can compress it to 5x2:
BORFO
OMABO

But we can make it even smaller by reusing characters between different strings, and fit the strings in 4x2:
FOOM
BARX

Now the B is used for both BOOM and BAR, and the OO is used for both BOOM and FOO.
Test Data
Your submission will be tested on the following 50 strings. For testing purposes you can simply use smaller subsets of this data which should then run more quickly. I believe that the absolute lower bound for this test data is a board with 120 characters, although this is not necessarily achievable.
T
WP
GVI
CIHM
EGWIV
QUTYFZ
LWJVPNG
XJMJQWSW
JLPNHFDUW
SWMHBBZWUG
XVDBMDQWDEV
TIUGAVZVUECC
IWDICFWBPSPQR
MMNWFBGMEXMSPY
YIHYXGJXKOUOIZA
BZSANEJNJWWNUJLJ
XTRMGOVPHVZYLLKKG
FLXFVVHNTWLMRRQYFQ
VZKJRAFQIYSBSXORTSH
FNQDIGCPALCHVLHDNZAV
GEAZYFSBSWCETXFKMSWLG
KWIZCEHVBDHEBGDGCJHOID
SKMQPHJAPDQKKHGTIPJCLMH
ZSFQDNYHALSUVWESQVVEUIQC
HXHBESUFCCECHNSTQGDUZPQRB
DSLXVHMOMLUXVHCNOJCBBRPVYB
DVTXKAOYYYRBVAVPSUAOYHIPPWN
PJAIYAWHMTNHTQDZDERPZYQEMLBZ
SYNSHJNOIWESMKWTBIANYUAUNRZOS
WADGUKIHUUFVRVUIBFUXQIOLAWIXAU
LGLXUFIXBEPSOFCKIAHXSHVKZPCXVPI
LIUYFHITTUYKDVQOZPNGZLWOZSRJTCTZ
IZDFTFFPNEBIYGVNTZHINICBXBXLBNBAL
BSKQNTPVUAVBXZGHVZCOUCRGCYISGFGYAS
DPGYYCIKDGCETXQOZGEQQLFQWACMVDTRYAT
RQDNIPGUHRYDRVHIPJLOWKBXMIBFAWCJGFMC
PFKOAGEQLXCMISSVEARWAPVYMRDCLSLPJOMQQ
EQPCNHQPTWABPFBVBXHQTFYELPNMNCWVKDDKGR
RAHTJMGIQJOJVWJBIHVRLJYVCSQJCKMEZRGRJMU
SZBJBPQYVYKDHAJHZMHBEWQEAQQKIEYCFACNLJBC
ANVDUCVXBPIZVRAXEBFEJOHSYKEKBIJELPIWEYXKH
DJUNPRLTISBFMGBEQNXSNUSOGDJNKESVKGAAMTIVXK
TZPUHDSHZFEURBNZTFBKXCDPYRELIAFMUWDIQTYWXGU
FJIKJROQSFSZUCGOOFJIEHBZREEUUSZWOLYFPCYHUSMR
TPMHJEAWVAJOCSDOPMQMHKRESBQSTRBXESYGCDVKLFOVS
ABJCCDJYMYDCYPZSGPGIAIKZQBYTZFDWYUZQBOESDSDGOY
IIHKTVPJNJDBCBOHCIYOPBKOVVKGNAKBDKEEKYIPRPHZOMF
IABGEPCSPNSMLVJBSGLRYNFSSYIALHWWAINTAVZAGJRVMDPW
GFMFVEFYJQJASVRIBLULUEHPMZPEXJMHIEMGJRMBLQLBDGTWT
YPWHLCVHQAVKVGHMLSOMPRERNHVYBECGCUUWTXNQBBTCMVTOVA

Verifier
You can use the following Stack Snippet to verify whether a Boggle board contains all strings in a given list. I ported the Boggle search code from edc65's answer over here. Let me know if anything seems buggy.

function verify() {
  var strings = document.getElementById("strings").value;
  var board = document.getElementById("board").value;
  strings = strings.match(/[A-Z]+/g) || [];
  board = board.split('\n');
  var valid = true;
  var len = board[0].length;
  var result = 'Valid';
  for (var i = 0; i < board.length; ++i)
  {
    if (board[i].length != len)
    {
      valid = false;
      result = 'Invalid: Board not rectangular.';
    }
    if (/[^A-Z]/.test(board[i]))
    {
      valid = false;
      result = 'Invalid: Board contains invalid character on line '+i+'.';
    }
    if (!valid) break;
  }
  if (valid)
    for (i = 0; i < strings.length; ++i) {
      if (!findInBoard(board, strings[i]))
      {
        valid = false;
        result = 'Invalid: String "'+strings[i]+'"not found in board.';
        break;
      }
    }
  document.getElementById("output").innerHTML = result;
}

function findInBoard(b, w) {
  var l = b[0].length;
  var r = 0;
  var Q = function(p, n) {
    return (r |= !w[n]) ||
    (
      b[p] = 0,
      [1,l,l+1,l+2,-1,-l,-l-1,-l-2].map( function(q) { return b[q+=p]==w[n] && Q(q,n+1) }),
      b[p] = w[n-1]
    );
  }
  b = (b+'').split('');
  b.map(function(e, p) { return e==w[0] && Q(p,1) });
  return r;
}
Strings that should be part of the Boggle board:

<textarea id="strings" cols="60" rows="10"></textarea>

Boggle board:

<textarea id="board" cols="60" rows="10"></textarea>

<input type="button" value="Verify" onclick="verify()" />

C++11, score = 992 1024
The algorithm is really stupid, but so far no one else made a serious one either, so I'll post it. It more or less randomly sticks words on a square board, and then starts over if it doesn't manage to make them fit. It kind of tries to maximize overlap with the existing words, but in a really inefficient way.
Edit: Improved score by adding 1 to a side length and trying a rectangle after failing 50 times. Also sorted input strings by size instead of randomizing the order.
#include <iostream>
#include <cstring>
#include <string>
#include <random>
#include <algorithm>
using namespace std;

struct grid {
    char *g;
    int h,w;
    grid(int h, int w):h(h),w(w) {
        g = new char[h*w];
        memset(g,0,h*w*sizeof(*g));
    }
    grid(const grid &o) {
        h=o.h, w=o.w;
        g = new char[h*w];
        memcpy(g,o.g,h*w*sizeof(*g));
    }
    grid(grid &&o) {
        h=o.h, w=o.w;
        g = o.g;
        o.g = 0;
    }
    grid& operator=(const grid &o) {
        h=o.h, w=o.w;
        memcpy(g,o.g,h*w*sizeof(*g));
        return*this;
    }
    grid& operator=(grid &&o) {
        h=o.h, w=o.w;
        g = o.g;
        o.g = 0;
        return*this;
    }
    char& operator()(int i, int j) {
        return g[i*w+j];
    }
    ~grid() { delete []g; }
};
typedef struct { int n, i, j; grid g; } ng;

const int qmax = 140;
const bool sizesort = true;
const int maxtries = 50;

inline int sq(int x){return x*x;}
bool operator<(const ng &a, const ng& b) {return a.n < b.n;}
void search(vector<string>& s) {
    int tl = 0;
    for(auto&x: s) tl += x.size();
    int l = 0;
    while(l*l < tl) l++;
    vector<string*> v;
    for(size_t i = 0; i < s.size(); i++) v.push_back(&s[i]);
    struct{bool operator()(string*a,string*b){return a->size()>b->size();}} scmp;
    if(sizesort) sort(v.begin(), v.end(), scmp);
    mt19937 rng;
    for(;;l--) {
        int tries = 0;
        int side2 = l;
        retry:
        tries++;
        if(!sizesort) shuffle(v.begin(), v.end(), rng);

        if(tries == maxtries) cout<<"rectangle",side2++;
        grid g(l,side2);

        for(string* x: v) {
            string& z = *x;
            vector<ng> p;
            for(int i = 0; i < g.h; i++)
            for(int j = 0; j < g.w; j++) {
                if(g(i,j) && g(i,j) != z[0]) continue;
                p.push_back({!g(i,j), i,j, g});
                p.back().g(i,j) = z[0]|32;
            }
            for(size_t zi = 1; zi < z.size(); zi++) {
                vector<ng> p2;
                for(ng &gg: p) {
                    for(int i = max(gg.i-1,0); i <= min(gg.i+1,g.h-1); i++)
                    for(int j = max(gg.j-1,0); j <= min(gg.j+1,g.w-1); j++) {
                        if(!gg.g(i,j) || gg.g(i,j) == z[zi]) {
                            p2.push_back({gg.n+!g(i,j),i,j,gg.g});
                            p2.back().g(i,j) = z[zi]|32;
                        }
                    }
                }
                shuffle(p2.begin(), p2.end(), rng);
                sort(p2.begin(), p2.end());
                if(p2.size() > qmax) p2.erase(p2.begin() + qmax, p2.end());
                p = move(p2);
            }
            if(p.empty()) goto retry;
            g = p[0].g;
            for(int i = 0; i < g.h; i++)
            for(int j = 0; j < g.w; j++)
                g(i,j) &= ~32;
        }
        cout<<g.w*g.h;
        for(int i = 0; i < g.h; i++) {
            cout<<'\n';
            for(int j = 0; j < g.w; j++)
                cout<<(g(i,j)?g(i,j):'X');
        }
        cout<<endl;
    }
}

int main()
{
    vector<string> v = {"T","WP","GVI","CIHM","EGWIV","QUTYFZ","LWJVPNG","XJMJQWSW","JLPNHFDUW","SWMHBBZWUG","XVDBMDQWDEV","TIUGAVZVUECC","IWDICFWBPSPQR","MMNWFBGMEXMSPY","YIHYXGJXKOUOIZA","BZSANEJNJWWNUJLJ","XTRMGOVPHVZYLLKKG","FLXFVVHNTWLMRRQYFQ","VZKJRAFQIYSBSXORTSH","FNQDIGCPALCHVLHDNZAV","GEAZYFSBSWCETXFKMSWLG","KWIZCEHVBDHEBGDGCJHOID","SKMQPHJAPDQKKHGTIPJCLMH","ZSFQDNYHALSUVWESQVVEUIQC","HXHBESUFCCECHNSTQGDUZPQRB","DSLXVHMOMLUXVHCNOJCBBRPVYB","DVTXKAOYYYRBVAVPSUAOYHIPPWN","PJAIYAWHMTNHTQDZDERPZYQEMLBZ","SYNSHJNOIWESMKWTBIANYUAUNRZOS","WADGUKIHUUFVRVUIBFUXQIOLAWIXAU","LGLXUFIXBEPSOFCKIAHXSHVKZPCXVPI","LIUYFHITTUYKDVQOZPNGZLWOZSRJTCTZ","IZDFTFFPNEBIYGVNTZHINICBXBXLBNBAL","BSKQNTPVUAVBXZGHVZCOUCRGCYISGFGYAS","DPGYYCIKDGCETXQOZGEQQLFQWACMVDTRYAT","RQDNIPGUHRYDRVHIPJLOWKBXMIBFAWCJGFMC","PFKOAGEQLXCMISSVEARWAPVYMRDCLSLPJOMQQ","EQPCNHQPTWABPFBVBXHQTFYELPNMNCWVKDDKGR","RAHTJMGIQJOJVWJBIHVRLJYVCSQJCKMEZRGRJMU","SZBJBPQYVYKDHAJHZMHBEWQEAQQKIEYCFACNLJBC","ANVDUCVXBPIZVRAXEBFEJOHSYKEKBIJELPIWEYXKH","DJUNPRLTISBFMGBEQNXSNUSOGDJNKESVKGAAMTIVXK","TZPUHDSHZFEURBNZTFBKXCDPYRELIAFMUWDIQTYWXGU","FJIKJROQSFSZUCGOOFJIEHBZREEUUSZWOLYFPCYHUSMR","TPMHJEAWVAJOCSDOPMQMHKRESBQSTRBXESYGCDVKLFOVS","ABJCCDJYMYDCYPZSGPGIAIKZQBYTZFDWYUZQBOESDSDGOY","IIHKTVPJNJDBCBOHCIYOPBKOVVKGNAKBDKEEKYIPRPHZOMF","IABGEPCSPNSMLVJBSGLRYNFSSYIALHWWAINTAVZAGJRVMDPW","GFMFVEFYJQJASVRIBLULUEHPMZPEXJMHIEMGJRMBLQLBDGTWT","YPWHLCVHQAVKVGHMLSOMPRERNHVYBECGCUUWTXNQBBTCMVTOVA"};
    search(v);
    return 0;
}

The board:
TGBHXEXMPYTECWBSFYOXKXKXFSQJXKXX
UZBWMLJKSXXPIXSVYYXATVDLVOCVCXMT
WWPSJGBUFWPOUHPAKRZMXIPCHHXJYEAX
SQPBNXFQNMLAYSQVBGAESYGWQJOVXJZY
RJXWJJDWMNSGFUQXSEAWXBMIJAYWLRTR
XMXFEIWIHTIHIGMOJTKVARJNPSVFJVDG
XJHNCGCCQXTYLSJHVNOJXHTSCKERBHMR
XVCLACEDGTCCDGLPMCJXXMQMQPVGIAJC
DLZSFPURZYUGRKENTWSDPVLSHBFFHBMA
HNBUQYZPDOKNMYDDVBBOGJBQGKSMLUWQ
XXZRSEBQNCQDPVFNKSSQNCDLXERPMSLF
XKVAIHMHTGZVUXPTQUSXXGEBRXEZHOUQ
XRJUXYNLQFJLHAVQPNNXTCXYMRJPKEQH
FAPIHATDBSWXWGBHCQHPBWUVNMJGKGVP
XQVVWMLJRZZOVRZXESFQTAUFHIMLLYZV
XIWXUSOQTXTLSEABVBIPXGXSYEAEMGOX
WEYQCBIUXCNSJKGRFZXTBXXSMFLIRYPQ
XGSBIPFLPAMIBEEMVEJLXDWDUBHTYXDX
XQSUXIZQGFOCPLKSUOAREVYQDWDVXCTA
XXVEBKXLEKCIOFYYHCBJPCTKIAWKIMZE
ORVEUGVIXYEWFPCCDJCNUDANHIBODFCI
XTOFPUSHKQXAZYDYIYOBJZVZBFMXLGOU
SZNSCXHLWQQSGCTQMBPDGAXXTRACJJXO
HRUAUKIAXEUOPGUIKWRJMNKKDGUWPBGK
ZVEYNGDNBUEOJIAZQORVGBDSEEOYIYXX
VMHCCAIBHRHFAESSBXVJKQOSKYFZHVPB
ALEVJPTWLMZJHXXFJYXIZUEFLIGUSRRB
GZCBDHPKMXXBXDSBTZJDUYVXNQPPHDYC
UIPJQKEQSBNICKYPNEFHWVHFDFRUZOJX
KWTGKXGBEOIJHNVQFBTLNTNMYXLTXNMX
DIOHJCXDGWHZTSGYIFJPMRRQOMXVHCFX

C, score 1154
AVOTVMCTBBQNXTWUUCGCEBYVHNRERPMOSLMHGVKVAQHVCLHWPYGOSUNSXNQEBGMFBSITLRPNUJDXJMHIEMGJRMBLQLBDGTWTWVJOJQIGMJTHARYPDCXKBFTZNBRUEFZHSDHUPZTCUZSFSQORJKIJFYNDQFSZOWLZGNPZOQVDKYUTTIHFYUILHWWAINTAVZAGJRVMDPWPQRBEAWVAJOCSDOPMQMHKRESBQSTRBXESYGCDVKLFOVSOYNUAUYNAIBTWKMSEWIONJHSNYSKYVYQPBJBZSOHCIYOPBKOVVKGNAKBDKEEKYIPRPHZOMFGJCWAFBIMXBKWOLJPIHVRDYRHUGPINDQRQPSPBWFCIDWIVPAWRAEVSSIMCXLQEGAOKFPFFTFDZIWLMRRQYFQSXORTSHLUXVHCNOJCBBRPVYBMKSNTPVUAVBXZGHVZCOUCRGCYISGFGYASOZGEQQLFQWACMVDTRYATIAJPVUECCYFSBSWCETXFKMSWLGFUUHIKUGDAWIYXCPZKVHSXHAIKCFOSPEBXIFUXLGLJNHFDUWSWQJMJXWSMXEMGBFWNMMGOVPHVZY
NDUCVXBPIZVRAEBFEJOHSYKEKBIJLPIWEYXKKXITMAGKSEKNJDFMFVEFYJQJASVRILULUEHMZPEUMRGRZKCJQSCVYJRVHIBJUGXWYTDWUFAILERMSUHYCPYLOWZSUERBEIJFOOGQIEVVQEWVUSLAHZTCTJRIABGEPCSNSMLJBSGLRYNFSSYAXHBESUFCCECHNSTQGUZTMHJABJCCDYMYDCYZSGPGIAIKZBYZFDWYUZQBOESDSDGZRCBJLNCAFCYEIQQAQEBHMZJAHDIIHKTVJNDCBNWPPHAUSPVABRYYYOAKXTVDWQDMBDVXCRGKDDKVWCNNPLEYFTQHXBBFPBAWTPQHCPEQMOJLSLCDRMYLABNBLXBXBCNIHZTNVYIBENLXVVHNTVZKJAFISBDLVHMOMCJPITGHKKQDPAJHPQBSQKWIZCEHDHEBDGCJHIDDPYYCKDCETXQZBLMYZPREDZDQTHNMHWYUGVZIWGAZUAXIWALOIQUBIUVRVAZIOUOXJXYHPVAZNDHLCLAPCGDQNBZANJNJWWNUJLPGPVJWLGUZBBHMYPHICQUTYZXTRVIXGKKLL

Use two lines so newly added words can reuse the letters from the top line.
char l[2][2000];
char s[2][2000];
char w[100][200];
int d[200];
void pri() {
    puts(l[0]);
    puts(l[1]);
}
void sav() { memcpy(s,l,sizeof(l)); }
void res() { memcpy(l,s,sizeof(l)); }
int fit(char *t, int l0, int l1) {
    if (!*t) return 0;
    if (l[0][l0] == *t && (l0 <= l1 || l[1][l1])) return 1+fit(t+1,l0+1,l1+(l1<l0));
    if (l[1][l1] == *t && (l1 <= l0 || l[0][l0])) return 1+fit(t+1,l0+(l0<l1),l1+1);
    if (!l[0][l0]) {
    strcpy(l[0]+l0,t);
    return 0;
    }
    if (!l[0][l1]) {
    strcpy(l[0]+l1,t);
    return 0;
    }
    if (!l[1][l1]) {
    l[1][l1] = *t;
    return fit(t+1,l0+(l0<l1),l1+1);
    }
    return 1000;
}
int main(){
    int j,i,n,best,besti,bestk,c,tot = 0;
    for (i = 0; scanf("%s ",w[i])>0; i+=2) {
    int j = strlen(w[i]);
    for (c = 0; c < j; c++) w[i+1][c] = w[i][j-c-1];
    }
    n = i;
    pri();
    for (j = 0; j < n/2; j++) {
    int k = -1;
    best = -1;
    for (k = 0; k <= strlen(l[1]); k++) {
    for (i = 0; i<n; i++) if (!d[i/2]) {
    sav();
    c = fit(w[i],k,k);
    if (c < 1000 && c >= best) best = c, besti = i, bestk = k;
    res();
    }
    }
    fit(w[besti],bestk,bestk);
    d[besti/2] = 1; tot += best;
    }
    pri();
    printf("%d - %d\n",tot, strlen(l[0])+strlen(l[1]));
    return 0;
}

Python 3, score = 1225
In this solution we use only 1 row. Starting from the empty string in every step we add the word which guarantees the largest possible overlap. (The words are checked in all 4 possible orientations.)
This gives a score of 1225 which is 50 lower than the score of 1275 for concatenating all the words together with no overlapping.
The result:
CBJLNCAFCYEIKQQAEQWEBHMZHJAHDKYVYQPBJBZSFQDNYHALSUVWESQVVEUIQCMFGJCWAFBIMXBKWOLJPIHVRDYRHUGPINDQRQPSPBWFCIDWIPVXCPZKVHSXHAIKCFOSPEBXIFUXLGLWSMKFXTECWSBSFYZAEGWIVGNPVJWLIUYFHITTUYKDVQOZPNGZLWOZSRJTCTZPUHDSHZFEURBNZTFBKXCDPYRELIAFMUWDIQTYWXGUWZBBHMWSKMQPHJAPDQKKHGTIPJCLMHICCEUVZVAGUITAYRTDVMCAWQFLQQEGZOQXTECGDKICYYGPDIOHJCGDGBEHDBVHECZIWKXVITMAAGKVSEKNJDGOSUNSXNQEBGMFBSITLRPNUJDSLXVHMOMLUXVHCNOJCBBRPVYBZSANEJNJWWNUJLJLPNHFDUWPDMVRJGAZVATNIAWWHLAIYSSFNYRLGSBJVLMSNPSCPEGBAIZDFTFFPNEBIYGVNTZHINICBXBXLBNBALQUTYFZBLMEQYZPREDZDQTHNTMHWAYIAJPFKOAGEQLXCMISSVEARWAPVYMRDCLSLPJOMQQFYQRRMLWTNHVVFXLFNQDIGCPALCHVLHDNZAVOTVMCTBBQNXTWUUCGCEBYVHNRERPMOSLMHGVKVAQHVCLHWPYPSMXEMGBFWNMMXJMJQWSWADGUKIHUUFVRVUIBFUXQIOLAWIXAUMJRGRZEMKCJQSCVYJLRVHIBJWVJOJQIGMJTHARGKDDKVWCNMNPLEYFTQHXBVBFPBAWTPQHNCPQEXVDBMDQWDEVZKJRAFQIYSBSXORTSHXHBESUFCCECHNSTQGDUZPQRBSKQNTPVUAVBXZGHVZCOUCRGCYISGFGYASYNSHJNOIWESMKWTBIANYUAUNRZOSVOFLKVDCGYSEXBRTSQBSERKHMQMPODSCOJAVWAEJHMPTWTGDBLQLBMRJGMEIHMJXEPZMPHEULULBIRVSAJQJYFEVFMFGKKLLYZVHPVOGMRTXYIHYXGJXKOUOIZANVDUCVXBPIZVRAXEBFEJOHSYKEKBIJELPIWEYXKHDVTXKAOYYYRBVAVPSUAOYHIPPWNFJIKJROQSFSZUCGOOFJIEHBZREEUUSZWOLYFPCYHUSMRABJCCDJYMYDCYPZSGPGIAIKZQBYTZFDWYUZQBOESDSDGOYIIHKTVPJNJDBCBOHCIYOPBKOVVKGNAKBDKEEKYIPRPHZOMF

The code:
import sys

def com_len(a,b):
    for i in range(min(len(a),len(b)),-1,-1):
        if (a[-i:] if i else '')==b[:i]:
            return i

def try_s(a,b,sn,mv):
    v=com_len(a,b)
    if v>mv:
        return a+b[v:],v
    return sn,mv

ws=[w.rstrip() for w in sys.stdin.readlines()]
s=''
while ws:
    mv=-1
    sn=None
    mi=None
    for i in range(len(ws)):
        mvo=mv
        for a in [s,s[::-1]]:
            for b in [ws[i],ws[i][::-1]]:
                sn,mv=try_s(a,b,sn,mv)
        if mvo<mv:
            mi=i
    s=sn
    del ws[mi]
print(s)

CJam, 1122 1089 letters
qN%{,}$__W%Wf%+:A;s[,mQ)__2#_S*:B;+2/:P;:DX1$W*W]:M;1:L;{BQCelt:B;}:T;
{A,,{B:G;P:H;D:I;L:J;A=:Z{:C;PL+D-:QB=C=
{T}{QD+:QB=C={T}{BPCelt:B;PD+:PL+B=' ={MD#)M=:D;ML#)M=:L;}&}?}?}/BS-,Z,-G:B;H:P;I:D;J:L;}$
0=:KA={:C;PL+D-:QB=C={T}{QD+:QB=C=
{T}{BPCelt:B;PD+:PL+B=' ={MD#)M=:D;ML#)M=:L;}&}?}?}/Beu:B;AKWtK~WtW-:A}g
{PL+B=' -PD-L+B=' -e&}{BP'Zt:B;PD+:P;}w
BM0=/Sf-Oa-N*

The program constructs the rectangle from its center, spiraling outwards. This is a rather simple approach so far. There's still room for improvement.
The code is a big mess right now. I'll clean it up when I'm satisfied with my score.
Try it online in the CJam interpreter.
Board
GXVDBDQDEVGPVJWLWSWQJMJMHCFNQDIGC
UIWESMKWBIANYUANRZOLGLXUFIXBEPSOP
WOPZUDGQTSHCCCUSEBHSKMQHJADKKHGFA
ZNQDKVWCMNPLEYFTQHXBVBPBATPQHNTCL
BJRDOWLZNPZQVDKYUTTIHFYILWADGCIKH
BHBKZXZGHZCOUCGCIGFGYSUGXYQIUPJAV
MSNGSBSMLVJSGLRYNSSIALHWWNTDKQCHL
WYWPRVNDSEBQZUYWFZTYBQZIAIAWIELXD
GSPAJAPSDIOHJDGHDBECZIWKSGVUHQMSN
VTHITUCGAWUUCGEBYVHNERPMZPZMUQHVZ
EIOYCVPONTFOOCUZSSQORJKOBGAFUMDKA
WGUAZTEYVXJYGDVKLFOSFMISJSJIVOPZV
IASWRNGTDNISBCBDJJPVTOJLBZRLRJGCS
IVPHDQBWUQHEOGOSUNNQKZFMPYVEVPYXF
WZVMNKATCBBXHDTROXSEHHTHQCMRULYVQ
DUATISIGVTZBCJSVZFBGIPMGYDPYISCPD
IEVNPBSDXCERINHKTYSMIRHVYMWDBLIYN
FCBHGRXLBMETYKDJQUIFKPJKDJGCFCKHA
WCRTUAVQPVUSOEURAFQBXIEVHDFXUDGYL
BQYQHTHLITUQPSNPLTISVYAQACMKQRCXS
PFYDRJMBZOZSBVKGAAMTIKWHJCFBIMEGU
SQYZYGOMRVWEKOVNKBDKEEVCHJVFOYTJV
PROEDILJXAORHMQMPOSCOJALZBETLVXKW
QRAPRQUGECLYFPCYHUMRYPWHMAFZAPQOE
WMKZVJXMFBJNCAFEIKQQAEQEBHYNWROUS
ULXYHOVIEJOHSYKKBJELPIWYXKJBIAZIQ
DWTQIJCHMXEPZMPHEULUBRVSAJQRXEGAV
FNVEPVNOJCBBRPVYBTZPHDSHZFEUAVQGV
PHDMJWJBIHVRLJYCSQJCKMEZRGRJMSQKE
LVMBLOKXMBFAWCGFMCPFOAGQLXCMISLKU
JVNZGEAZYFSBSETXKSWLGTYRTDVAWQFLI
WFWFBMXMSPYZANJNJWNUJLJXMGOPHVZYQ
PXLLANBLXBXBCIIHZTVGYIBENPFFTFDIC

Python 3, score = 1014
Starting from a null sized area we add words letter by letter to the area in a way that the area will always be a rectangular spiral:
  .
32.
41.
567

We keep 10 boards candidates throughout the computation. At every step to every candidate we try to add every word that board has left in every possible legal way keeping the spiral layout. We score each of the resulting new boards based on the total used word length / total area used fraction. We keep the best 10 boards and repeat the step until there are no words left.
To minimize unused space at the end of the spiral we try taking some steps ahead before spiraling to create non-square spirals. E.g.:
98765
.1234
..

The word list is given in stdin. The (quite ugly) code takes about 30 minutes on my slow laptop. (If you want to wait less, you can choose nonspiral_length=13 rather than looping through the possible values.)
The resulting board:
JFOOGCUZSFSQORKIJFYGDSDSEOQZUYWDFZTYBQZ
ISDHUZTIIHKTJNJDBCBOHIYOPBKVVGNAKBDKEEK
EHOJPSLCDRMYVPAWESSIMCLQEGAOKFPJLCAFCKI
BZMFYLPNMNKDKGRAVMCTBBXTWUUCGCBYHNREYPA
RFQTXESYGCDVKLFOVSSFQNYHALSVWESQVEQRIRI
EELQBZNGZLWOZSRJTCTZWDGUIHUUFVRVUICPKPG
UUAHROPSCPGBAVXCPZVHXAIKCOSPBXIFUBTMQHG
SRBXTQNSXYEIPLJIBKKYSHOJEFBEXRIPXFAOQZS
WZNBSVMAHKWZCEHVDHEGDGHIDTIGAVZBLQYSAOZ
OTLVQDLYXMTIVXKBYVRBCJONHVXULMVXGIRLEMP
LFXFBKVGHAFBGEXMSPSPBWFCIDWIMOUCLOTMQFY
YKBPSYJFBAWNTMRRQYNQDIGPALCHXLEDTADHWTC
FDXBEUBGEGMHJWLSMKFXTECBSFYVDSCVXWVGEWD
HPCARTLSSKMVVGUWZBBHMWSGEAZLBJCNKIMKBTY
UYIWKTRIUVZFPNQTYFXJJQWIVNDHMLPAOXCVHGM
SRNTHINYFSKXLFYIHXGKOUOZAEWQDJNIYAWAMDY
MEIPMHFGCEJRASBSXORTSHBSJNJWNUHTYUQHZBJ
XLZHQYSRCKNDGOUNNQEBGMFITLRPUDFGYXFVJLD
XITNMNSUECHSTQGDUZPSKQPHJAPDQKKHRTLCAQC
XAVCPHYOCZVGZXBVAVTNQNWPYOUSPVAVBMQHDLC
XFGQOJIALHWWAINTAGJRVMDGKKLLYZHPOGQWKBJ
XMYEDNOWESMKTBAYUUNZOSYYCIDGCETXQZEPYMA
XUICSCJAVJHPJAIWHMTHTQDZDERPZYQEMLBYVRA
XWBMFGWFBIMXBKWOLJPIVRYRHUGINDRSZBJPQJH
XDENPFTDZGFFVEFYJQASIBLULPMZPEXJMHIEMGT
XIQTYWXGUMJRGRZEMKCJQSCVYJLRVHIBWVJOJQI

The generating code:
import sys

class b:
    def __init__(s,l,ws):
        s.d=[' ']*(l*l)
        s.x,s.y=l//2,l//2
        s.l=l
        s.dir=1j
        s.ws=ws[:]
        # last char pos, remaining word part, used positions
        s.wx,s.wy,s.wp,s.wu=None,None,None,None

    def copy(s):
        #print('copy',s.x,s.y,s.wp)
        c=b(s.l,s.ws)
        c.d=s.d[:]
        c.x,c.y=s.x,s.y
        c.dir=s.dir*1
        c.wx,c.wy=s.wx,s.wy
        c.wp=s.wp[:] if s.wp!=None else None
        c.wu=s.wu[:] if s.wu!=None else None
        return c#copy.deepcopy(s) is very slow

    def score(s):
        placed_chars=allwlen-sum([len(w) for w in s.ws])
        used_cells=0
        for i in range(s.l):
            for j in range(s.l):
                if s.d[i*s.l+j]!=' ':
                    used_cells+=1
        return placed_chars/used_cells

    def get_next_bs(s):
        bl=[]
        for wi in range(len(s.ws)):
            bl+=s.get_b_for_w(wi)
        return bl

    def get_b_for_w(s,wi):
        w=s.ws[wi]
        bl=[]
        for i in range(1,s.l-1,3):
            for j in range(1,s.l-1,3):
                for reversed in True,False:
                    if abs(i-s.x)+abs(j-s.y)>5:
                        continue
                    bn=s.copy()
                    bn.wx,bn.wy=i,j
                    bn.wp=w if not reversed else w[::-1]
                    del bn.ws[wi]
                    bn.wu=[]
                    bnr=bn.get_bs_for_wp()
                    bl+=bnr
        # only use the best for a given word
        best_b=max(bl,key=lambda b:b.score())
        return [best_b]

    def get_bs_for_wp(s):
        if len(s.wp)==0:
            return [s]
        bl=[]
        for ir in -1,0,1:
            for jr in -1,0,1:
                i=s.wx+ir
                j=s.wy+jr
                if (i,j) not in s.wu and (s.d[i*s.l+j]==s.wp[0] or (i==s.x and j==s.y)):
                    bn=s.copy()
                    assert bn.d[i*bn.l+j] in (bn.wp[0],' ')
                    #add/owerwrite char
                    bn.d[i*bn.l+j]=bn.wp[0]
                    bn.wp=bn.wp[1:]
                    bn.wu+=[(i,j)]
                    bn.wx,bn.wy=i,j
                    if (i==bn.x and j==bn.y):
                        spiraling=not (bn.x==bn.l//2 and bn.l//2+nonspiral_length>bn.y>=bn.l//2 )
                        #turn
                        nd=bn.dir*1j
                        if bn.d[int(bn.x+nd.real)*bn.l+int(bn.y+nd.imag)]==' ' and spiraling:
                            bn.dir=nd
                        #move
                        bn.x+=bn.dir.real
                        bn.y+=bn.dir.imag

                    #add bs from new state
                    bl+=bn.get_bs_for_wp()
        return bl

    def __repr__(s):
        #borders
        x1,x2,y1,y2=s.l,0,s.l,0
        for i in range(s.l):
            for j in range(s.l):
                if s.d[i*s.l+j]!=' ':
                    x1=min(i,x1)
                    x2=max(i,x2)
                    y1=min(j,y1)
                    y2=max(j,y2)
        r=''
        for i in range(x1,x2+1):
            for j in range(y1,y2+1):
                r+=s.d[i*s.l+j] if s.d[i*s.l+j]!=' ' else 'X'
            r+='\n'
        return r

progress_info=False # toggle to print progress info

allws=[w.rstrip() for w in sys.stdin.readlines()]
allws=allws[:]
allwlen=sum([len(w) for w in allws])
max_nonspiral_length=16
best_score=allwlen*2+1 # maxint
best_b=None

for nonspiral_length in range(1,max_nonspiral_length+1,3):

    length=int(allwlen**0.5)+nonspiral_length*2+5 #size with generous padding

    bl=[b(length,allws)]

    for wc in range(len(allws)):
        bln=[]
        for be in bl:
            bln+=be.get_next_bs()

        bln.sort(key=lambda b:b.score(),reverse=True)
        bl=bln[:10]
        if progress_info:
            print(wc,end=' ')
            sys.stdout.flush()
        #print(bl[0].score(),wc)

    real_score=len(repr(bl[0]))-repr(bl[0]).count('\n')
    #print(bl[0])
    if progress_info:
        print()
        print(nonspiral_length,'score =',real_score)

    if real_score<best_score:
        best_b=bl[0]
        best_score=real_score

if progress_info:
    print()
print(best_b)
if progress_info:
    print('score =',best_score)

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


text:
King of the Hill - Liar's Dice
Liar's Dice is a fairly simple dice game. I've seen a few different variations of the rules, but here is the version I'm most familiar with:

Each player starts with 5d6
Except when tallying the dice at the end of a round, each player may see their own dice, but not those of any opponent
At the start of any given round, all players roll whatever dice they currently have
Then, one player (usually, this is either the winner of the previous round OR the player to the left of the player who started last time; we'll be using the former for this KotH; with a random player starting the first round) makes a guess about how many of a particular number are on the table (ONES ARE WILD)
Bidding continues to the right, going higher each time (for instance; 3 fives, 3 sixes and 4 twos are all higher than 3 fours, but 3 threes is not; 4 ones is also higher but bidding on ones will probably put you at a disadvantage); until any player calls the player preceding them a liar
At this point, all players reveal their dice and count the number of the last number bid on on the table altogether
If the total is lower than the bid, the player who made the bid must give a die to the player who called them a liar, otherwise, the player who called the bidder a liar must give a die to the bidder (so the bidder wins if their are at least as many of that number as he had bid, there don't have to be the exact number)
When you run out of dice, you lose
The last player standing wins

For example:

Player one has 1,1,2,4,6
Player two has 1,2,2,3,5
Player three has 1,3,3,4,6
Player one: three sixes.
Player two: four twos.
Player three: four threes.
Player one: five twos.
Player two: six twos.
Player three: six threes.
Player one: six fours.
Player two: Liar!
They reveal their dice and count up the ones (because ones are wild) and the fours.
It turns out that there are, in fact, exactly six fours.
So player two gives player one a die.
They reroll and player one starts the next round.

You must write a bot to play this game. It must implement the following abstract java class:
public abstract class Player {
    public Player() {}
    public String toString() {
        return this.getClass().getSimpleName();
    }
    public abstract String bid(int yourId, int[] diceEachPlayerHas, int[] yourDice, String[] bids);
}

You must implement the bid method

The first argument is your bot's current position in the turn order, the second is an array showing how many dice each player (including yourself) currently has, the third is an array showing the values currently shown on your own dice, and the fourth is an array of all bids made since the start of the current round - will have length 0 if you are making the first bid of the round
The output should be either a string of the form "number face", or the string "Liar!" to call the previous bidder a liar.
If your output is formatted illegally, you will be eliminated.

You may override the toString method, but are not required to. However, you may not edit it in any way that interferes with the readability of the controller's output.
You are permitted to call any other public methods of the controller, but not its main method.
You may read and edit only files in the running directory prefixed with your bot's own name
You are not permitted to take input from any other source
Instance variables are reset at the start of each new game, but static variables are not.

Scoring

One set of 1,000 games, with 3-5 players in each, will be simulated each time a bot is added (as soon as three or more bots have been submitted), scored as shown in the controller source (in any given game, you get 1 at the start of each of your turns, 10 each time you capture a die, and 1,000 bonus if you win); enforcing a limit of 5,000 TURNS (not rounds) each game.
Your bot will be scored by its score from the latest set of games; plus ten times its vote score, if nonnegative. (The latter is unlikely to have a significant effect on the score)

The controller source can be found here.
Scores as of 2015-06-19:
Badnomial: 434,924 + 6x10 = 424,984
Nobody: 282,329 + 6x10 = 282,389
StraightShooter: 265,205 + 5x10 = 265,255
MostlyHonestAbe: 158,958 + 4x10 = 158,998
The Pirate: 157,005 + 1x10 = 157,015
Statistician: 144,012 + 2x10 = 144,032
Fidelio: 49,973 + 2x10 = 49,993
Absurd Bot: 6,831
DrHouse: 2,638 + 3x10 = 2,668

You should clarify that the output should be "2 3" and not "two threes" like your example shows. Also, is there a way in the controller to watch a single match?

Not in the official version, but I'll post an alternate version that lets you do that.

@Geobits: If you want to. It will put you at a bit of a disadvantage if someone calls you though.

@Cain: http://pastebin.com/raw.php?i=GvVKG1QY

I assume the indices of the arrays are the "ids" of the players, so that diceEachPlayerHas[yourId] = your dice count, and bids[yourId] is your first bid (or null if it's your first turn).  Is that correct?

The first is true, the second may not be as the current controller setup adjusts the player ids (and therefore the indices of the arrays) automatically as players are removed. Also, if its your first turn, bids[yourId] will throw an IndexOutOfBoundsException.

I've seen games where some submissions play more games than others (Nobody: 414 games, Straight Shooter: 409 games). This isn't fair, can you please fix this?

That's not actually a huge disparity, and something on roughly that scale should be expected when selecting 1,000 rounds at random.

Nobody
Tries to guess the dice from other players. Calls other bots liars if it doesn't know what to do.
Edit: Fixed a problem where Nobody would bid forever, never calling Liar.
public class Nobody extends Player{

    @Override
    public String bid(int myId, int[] diceEachPlayerHas, int[] myDice,
            String[] bids) {
        if (bids.length == 0)
            return "1 2";
        int wilds = 0;
        int players = Controller.numPlayers();
        double myKnowledge = (double)diceEachPlayerHas[myId]/Controller.diceInPlay();
        double previousKnowledge = (double)diceEachPlayerHas[(myId-1+players)%players] / Controller.diceInPlay();
        int[] dice = new int[5];
        for (int i = 0; i < myDice.length; i++) {
            if (myDice[i] == 1) {
                wilds++;
            } else {
                dice[myDice[i]-2]++;
            }
        }
        wilds = (int) (1/myKnowledge+wilds-1)+1;
        for (int i = 2; i <= 6; i++) {
            dice[i-2] += wilds;
        }
        String best = "0 0";
        for (int i = 2; i <= 6; i++) {
            if (Controller.isGreaterThan(dice[i-2] + " " + i, best)) {
                best = dice[i-2] + " " + i;
            }
        }
        if (Controller.isGreaterThan(best, bids[bids.length - 1])) {
            return best;
        }
        if (previousKnowledge > 0.4) {
            int prev = Integer.valueOf(bids[bids.length - 1].split(" ")[0]);
            int prevFace = Integer.valueOf(bids[bids.length - 1].split(" ")[1]);
            if (dice[prevFace - 2] +2 >= prev)
                return (prev+1) + " " + bids[bids.length - 1].split(" ")[1];
        }
        return "Liar!";
    }
}

Your last set of updates really seem to have helped.

Badnomial, the bot that makes bad decisions based on binomial distributions: Edit: Fixed a stupid mistake in the probability calculations, now accounts for next Bidder as well as previous.
    public class Badnomial extends Player{
    public String toString() {return "Badnomial";}

  public String bid(int myId, int[] diceEachPlayerHas, int[] myDice, String[] bids) {
  int[] dieCounts = new int[7];
  for(int i:myDice)
   dieCounts[i]++;
  for(int i=2; i<7; i++)
   dieCounts[i] += dieCounts[1];

  if(bids.length > 0)
  {
   String[] lastBid = bids[bids.length - 1].split(" ");
   int bidCount = Integer.valueOf(lastBid[0]);
   int bidDie = Integer.valueOf(lastBid[1]);
   // Check if I hold a better bid
   boolean betterBid = false;
   int myBidDie;
   int myBidCount;
   int myHighestCount = 0;
   int myHighDie = bidDie +1;

   for(int i = 2; i < 7; i++) {
    if(dieCounts[i] >= myHighestCount) {
     myHighestCount = dieCounts[i];
     myHighDie = i;
    }
   }
    if((myHighestCount > bidCount) || ((myHighestCount == bidCount) && (myHighDie > bidDie))) {
     betterBid = true;
     myBidDie = myHighDie;
     myBidCount = myHighestCount;
     }

   if(betterBid == false) {
    int unknownDice = Controller.diceInPlay() - myDice.length;
    int myDiceNeeded = bidCount - myHighestCount;
 if(myHighDie <= bidDie)
  myDiceNeeded++;
    int previousBidder = myId - 1;
    if(previousBidder < 0)
     previousBidder = Controller.numPlayers() -1;
    int bidderDiceNeeded = bidCount - dieCounts[bidDie] - (int)(diceEachPlayerHas[previousBidder]/3 +1);
    int bidderUnknown = Controller.diceInPlay() - diceEachPlayerHas[previousBidder] -myDice.length;
 int nextBidder = myId + 1;
 if(nextBidder == Controller.numPlayers())
  nextBidder = 0;
 int nbDiceNeeded = myDiceNeeded - (int)(diceEachPlayerHas[nextBidder]/3 +1);
    int nbUnknown = Controller.diceInPlay() - diceEachPlayerHas[nextBidder];
    //float myChances = (unknownDice/3 - myDiceNeeded)/((float)unknownDice/9);
    //float bidderChances = (bidderUnknown/3 - bidderDiceNeeded)/((float)bidderUnknown/9);
    double myChances = 1 - cumBinomialProbability(unknownDice, myDiceNeeded -1);
    double bidderChances;
    if(bidderDiceNeeded > 0)
     bidderChances = 1- cumBinomialProbability(bidderUnknown, bidderDiceNeeded -1);
    else bidderChances = 1.0;
    double nbChances;
    if(nbDiceNeeded > 0)
      nbChances = 1- cumBinomialProbability(nbUnknown, nbDiceNeeded -1 );
    else nbChances = 1.0;
    if(((myChances < .5) && (nbChances <.5)) || (bidderChances < .2))
     return "Liar!";
   }

   return (bidCount+1) + " " + myHighDie;
  }

  return 2 + " " + 2;
 }

 private double cumBinomialProbability(int n, int k) {
   double sum = 0;
   for(int i = 0; i <=k; i++)
     sum += binomialProbability(n, i);
   return sum;
 }

 private double binomialProbability(int n, int k) {
   double nfact = 1;
   double dfact = 1;
   int greater;
   int lesser;
   if((n-k) > k) {
     greater = n - k;
     lesser = k;
   }
   else {
     greater = k;
     lesser = n-k;
   }
   for(int i = greater+1; i <= n; i++)
     nfact = nfact * i;
   for(int i = 2; i <= lesser; i++)
     dfact = dfact * i;
   return (nfact/dfact)*(Math.pow((1.0/3), k))*Math.pow(2.0/3, (n-k));
 }

}

It tries to determine whether it should bluff or call Liar based on estimated cumulative binomial distributions for itself and the previous and next bidders' chances of having their needed dice present.
Basically, it calls Liar if the previous Bidder is very likely to be a Liar or if it feels it that both it and the next Bidder are more likely lying than not.

With these changes, Badnomial actually seems remotely competent vs the other bots.

Straight Shooter
He plays it straight and doesn't bluff. He's also naive enough to think that others do, too, so he never calls liar unless the bid goes over the total number of dice in play (minus his own dice that don't match the bid).
To be a bit more conservative than the exact expected number for each die, he doesn't count his own wilds, but assumes others have a uniform distribution. With the current four players, either he or MostlyHonestAbe came up first each time, with fairly close scores.
I'm assuming the minimum bid is 2 2. If a bid of one die (or bidding ones) is allowed, let me know so I can make that change.
public class StraightShooter extends Player{
    public String toString(){return "Straight Shooter";}
    public String bid(int me, int[] numDices, int[] dice, String[] bids){
        int[] counts = new int[7];
        double[] expected = new double[7];
        int unknown = Controller.diceInPlay() - dice.length;
        for(int i:dice)
            counts[i]++;
        for(int i=2;i<7;i++)
            expected[i] = counts[i] + unknown / 3d;
        int bidCount = 2;
        int bidDie = 2;
        if(bids.length > 0){
            String[] lastBid = bids[bids.length-1].split(" ");
            bidCount = Integer.valueOf(lastBid[0]);
            bidDie = Integer.valueOf(lastBid[1])+1;
            int possible = Controller.diceInPlay();
            for(int i=2;i<7;i++)
                if(i != bidDie)
                    possible -= counts[i];
            if(bidCount > possible)
                return "Liar!";

            if(bidDie > 6){
                bidDie = 2;
                bidCount++;
            }
        }
        double best = Double.MAX_VALUE;
        int bestCount = bidCount;
        int bestDie = bidDie;
        for(int count=bidCount;count<=Controller.diceInPlay();count++){
            for(int die=bidDie;die<7;die++){
                double score = Math.abs(expected[die]-bidCount);
                if(score < best){
                    best = score;
                    bestCount = count;
                    bestDie = die;
                }
            }
            bidDie = 2;
        }
        return bestCount + " " + bestDie;
    }
}

This and MostlyHonestAbe are both so hesitant to lie or call liar, there's some games going to 2000 turns when I test haha. :P

Same in mine. That's okay, though, because every turn is an extra point toward the final score. If I last 2000 turns and don't win, that's better than winning after 100 in my book ;)

I just had to go look at the scoring rules again. Whole new game XD

Yea, with this scoring it seems like the optimum strategy might be to be as conservative as you can, and just rack up points. Maybe there's something better, but I can't see it.

On the officially scored set of games, I only noticed one that went beyond 1,500. Do you think I should increase the bonus for winning?

@SuperJedi224 I noticed over 1000 was common, 1500 was uncommon, and 2000 was rare. I ran 20k rounds, though.

I'm not sure it would make much difference. Being conservative would still be an advantage, just because you have a lower chance of losing a die. The reason more people don't play that way in real life is because it's just boring, but what is boredom to a bot?

I just adjusted the scoring rules (most notably, I increased the bonus for winning by a factor of ten) and reduced the turn limit to 5,000. That should reduce that problem.

If anything, it seems to have widened the gap between the more and less conservative entries ;)

MostlyHonestAbe
Abe makes conservative guesses about the rest of opponents die, and then then stays honest until he doesn't think there are enough dice to beat the current bid. At this point he bluffs once, then calls liar the next time.
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintStream;

public class MostlyHonestAbe extends Player{

    final boolean debug = false;
    boolean bluffedOnce = false;
    PrintStream out;
    @Override
    public String bid(int myId, int[] diceEachPlayerHas, int[] myDice, String[] bids) {
        try {
            File f = new File("abe.log.txt");
            out = new PrintStream(f);
        } catch (FileNotFoundException e) {
            // TODO Auto-generated catch block
            //e.printStackTrace();
        }
        if(debug){
            out = System.out;
        }

        //reset bluff counter on the first round
        if(bids.length < diceEachPlayerHas.length){
            bluffedOnce = false;
        }

        //Is it the first bid?
        if(bids.length == 0){
            out.println("I go first");
            return lowestViableBid(1,1, myDice, diceEachPlayerHas, true);
        }

        out.println("Last bid = " + bids[bids.length - 1]);
        out.print("My Dice = ");
        for(int d : myDice){
            out.print(d + ", ");
        }
        out.println();

        //What was the last bid?
        String[] lastBid = bids[bids.length -1].split(" ");
        return lowestViableBid(Integer.parseInt(lastBid[1]), Integer.parseInt(lastBid[0]), myDice, diceEachPlayerHas, false);

    }

    //Lowest honest bid, or liar
    private String lowestViableBid(int highestVal, int highestCount, int[] myDice, int[] otherDice, boolean firstTurn){

        //Make a better array for the dice
        //Include what the other players probably have
        int wilds = numDie(1, myDice);
        int[] diceCount = new int[6];
        diceCount[0] = wilds;
        int otherPlayerExpectedValue = 0;
        for(int d : otherDice){
            otherPlayerExpectedValue += d;
        }
        otherPlayerExpectedValue -= myDice.length;
        out.println("Number of other dice = " + otherPlayerExpectedValue);
        otherPlayerExpectedValue = otherPlayerExpectedValue / 4;
        //Note: Other player expected value is biased low, counting wilds the number should be divided by 3.

        out.println("playerExpectedVal = " + otherPlayerExpectedValue);
        for(int i = 1; i < 6; i++){
            diceCount[i] = numDie(i + 1, myDice) + wilds + otherPlayerExpectedValue;
        }

        //What's my array look like?
        for(int i = 0; i < diceCount.length; i++){
            out.println("diceVal = " + (i + 1) + ", diceCount = " + diceCount[i]);
        }

        //Can I bid the same number, but higher dice val?
        for(int diceVal = highestVal + 1; diceVal <= 6; diceVal++){
            if(diceCount[diceVal - 1] >= highestCount){
                out.println("1.Returning " + highestCount + " " + diceVal);
                return highestCount + " " + diceVal; }
        }

        //What about more dice?
        for(int diceNum = highestCount + 1; diceNum <= myDice.length; diceNum++){
            for(int diceVal = highestVal + 1; diceVal <= 6; diceVal++){
                if(diceCount[diceVal - 1] == diceNum){
                    out.println("2.Returning " + (diceNum) + " " + diceVal);
                    return (diceNum) + " " + diceVal; }
            }
        }

        if(firstTurn){ return "1 2"; }
        //If this is the first time I'm out of my league, bluff a round before calling liar.
        if(!bluffedOnce){
            out.println("bluffing " + (highestCount + 1) + " " + highestVal);
            bluffedOnce = true;
            return (highestCount + 1) + " " + highestVal;
        }
        out.println("Returning Liar!");
        //Well, wouldn't want to lie
        return "Liar!";
    }

    private int numDie(int i, int[] myDice){
        int result = 0;
        for(int j : myDice){
            if(i == j){ result++; }
        }
        return result;
    }
}

Are you kidding me? I was less than five minutes from posting HonestAbe. Now I have to think up a new name :P

Can't have a game with Liar in the name without an Abraham Lincoln reference somewhere.

Dr. House
Everybody Lies!
public class DrHouse extends Player
{
  public String bid(int yourId, int[] diceEachPlayerHas, int[] yourDice, String[] bids)
  {
    return "Liar!";
  }
}

I suggest adding special logic for when you have the first bid of the round.

@SuperJedi224 I imagine that the bot then considers the controller telling him that it is his turn to be a liar

Made my day lol

Statistician
You have 1/3 chance of having any number other than aces. One guy once tell me that not checking your dices and juste knowing the odds can make you win this game.
EDIT : It was bidding too high. But it doesn't improve the score a lot.
public class Statistician extends Player{
    public String toString(){return "Statistician";}
    public String bid(int me, int[] numDices, int[] dice, String[] bids){
        int totalDices = 0;
        int currentBid, max;
        for (int i : numDices)
            totalDices += i;
        max = totalDices/3;
        if(bids.length>0){
            currentBid = Integer.valueOf(bids[bids.length-1].split(" ")[0]);
            if(currentBid>max)
                return "Liar!";
        }
        return max+" 6";
    }
}

Fidelio
This bot know that only his most recurrent value will lead him to victory, so he stick with it. He assume there's a portion of everyone's dice that is the same as his, if anyone bid more than that portion, he assume he's a liar.
public class Fidelio extends Player
{
    final String LIAR ="Liar!";
    @Override
    public String bid(int yourId,
            int[] diceEachPlayerHas,
            int[] yourDice,
            String[] bids)
    {
        int[] myDices = new int[6];
        int valueToBid=1;
        for(int i : yourDice)
            myDices[i-1]++;
        for(int i=2;i<myDices.length;i++)
            if(myDices[i]>=myDices[valueToBid])
                valueToBid=i;
        if(bids.length==0)
            return 2+" "+valueToBid;
        int sum=0;
        String[] lastBidString=bids[bids.length-1].split(" ");
        int[] lastBid = new int[2];
        lastBid[0] = Integer.parseInt(lastBidString[0]);
        lastBid[1] = Integer.parseInt(lastBidString[1])-1;
        for(int i : diceEachPlayerHas)
            sum+=i;
        sum-=yourDice.length;
        if(lastBid[0]>sum/3+myDices[lastBid[1]]+myDices[0])
            return LIAR;
        if(lastBid[1]>= valueToBid)
        {
            if(lastBid[0]>=myDices[0]+myDices[valueToBid]+sum*2/5)
                return LIAR;
            return (lastBid[0]+1)+" "+myDices[valueToBid];
        }
        return lastBid[0]+" "+valueToBid;
    }
}

I hope he will do some good work :).

I'm getting an IndexOutOfBoundsException on line 13. Remember that arrays are 0-indexed in java.

Now I'm getting one on the other end on line 19, for an index of -1. It would appear that it was trying to read the last element from an empty array, you should include a check for that.

Fixed, the check if(bids.length==0) was done after I used bids...

Oh, I had just proposed another possible solution, but this will probably work as well.

Ah, so this suggested edit is no longer needed?

Ho, yeah, forgot to reject it, sorry ^^'. Anyway, @SuperJedi224 did a run with my bot, and it works well :). It even took the third place, which is great !

@Katenkyo: It's third to last actually, though I'm really not sure why.

Haha, did a wrong assumption because a bot for an other KotH just score 3rd xD. I can't get why he's so bad too, but no problem, it means it wasn't a good idea :p

The Pirate
I made a few simple bots while testing the controller, and this is the only one that's really any good.
Will likely be improved upon later.
import java.util.Arrays;
import java.util.Scanner;

public class Pirate extends Player{
    public Pirate() {
    }
    public String toString(){
        return "The Pirate";
    }
    private String bid(int[] t,int tol){
        int[]z=t.clone();
        Arrays.sort(z);
        int j=0;
        for(int i=0;i<6;i++){
            if(t[i]==z[5]){j=i;break ;}
        }
        return (tol+t[j])+" "+(j+1);
    }
    @Override
    public String bid(int yourId, int[] diceEachPlayerHas, int[] yourDice,
            String[] bids) {
        int[] t=new int[6];
        for(int i=0;i<yourDice.length;i++){
            t[yourDice[i]-1]++;
        }
        for(int i=1;i<t.length;i++)t[i]+=t[0];
        int tol=(Controller.diceInPlay()-yourDice.length)/4;
        if(bids.length==0)return bid(t,1);
        Scanner i=new Scanner(bids[bids.length-1]);
        int x=i.nextInt(),y=i.nextInt();
        i.close();
        if(t[y-1]>x)return (t[y-1]+2)+" "+y;
        int nd=Controller.diceInPlay();
        if(x>nd+t[y-1]-yourDice.length)return "Liar!";
        if(Controller.isGreaterThan(bid(t,tol), bids[bids.length-1])){
            int z=Controller.valueOf(bids[bids.length-1]);
            for(int j=1;j<=tol;j++)if(Controller.valueOf(bid(t,j))>z)return bid(t,j);
        }
        return "Liar!";
    }
}

Absurd Bot
Makes the claim that all of the dice are 6's unless it can't. If the bot can't do that, it means that this is an impossible situation or nearly impossible situation. Because of this, it calls liar. I am curious as to how effective this bot will be.
public class AbsurdBot extends Player {
    @Override
    public String bid(int yourId, int[] diceEachPlayerHas,int[] yourDice,String[] bids)
    {
        String[] lastbid;
        int a, b, d;
        d = 0;
        for (int dice : diceEachPlayerHas)
            d += dice;
        if (bids.length != 0)
            {
                lastbid = bids[bids.length-1].split(" ");
                a = Integer.parseInt(lastbid[0]);
                b = Integer.parseInt(lastbid[1]);
                if (a > d || a == d && b == 6)
                    return "Liar!";
            }
        return d + " 6";
    }
}

As for how effective: Its main function seems to be handing dice to whichever player follows it :P

@Geobits I fixed the code. This is what happens when you try to jump into a programming language you haven't programmed in before...

@Geobits Thanks for all the help. I think that this finally works properly now. Does it? (Java is confusing)

Yea, it runs now. The strategy is insanely suicidal, though. It scores only ~2% of the next-lowest player.

@Geobits I never tried running it against the other players. Did you run it against the others?

Against the current entries, yes. Here's a fairly representative result: http://pastebin.com/3nwVEubq


text:
All about basic binary
Please excuse the punny title.
This is a question is inspired by A Curious Property of 82000.  In it, the author points out that the number 82000 is binary in base 2, 3, 4, and 5.  The post then poses the question "is there a number that is binary in bases 2, 3, 4, 5, and 6"?  (For those curious, I've checked values up to 10^1,000,000 and so far the answer is no.)
This got me thinking: given a number, what bases is it binary in?
Our curious number, 82000, is actually binary in six bases:
Base 2 = 10100000001010000
Base 3 = 11011111001
Base 4 = 110001100
Base 5 = 10111000
Base 81999 = 11
Base 82000 = 10

Not all numbers will have binary bases that are sequential.  Consider the number 83521.  It's binary in bases 2, 17, 289, 83520, and 83521.
Your challenge is to determine and display which bases a number is binary in.
Rules

A number is considered "binary" in a given base if its representation in that base consists of only zeroes and ones.  110110 is a binary value, while 12345 is not, A380F is definitely not.
Your number will be provided on standard input.  It will be an integer value between 2 and 2^32-1 inclusive and will be provided in base-10 format.
In ascending order, display each base greater than one that the number is binary in.  Each base should be on its own line.  If you include the binary value in that base (see the bonus scoring below), separate the base and the binary value with a space.  Only output to standard out will be judged, standard error and other sources will be ignored.

Scoring
Your score is your program's size in bytes.  The lower the score, the better.
Bonus:
If your program also outputs the binary values in the found bases, multiply your score by 0.75
Your displayed binary value should have no extra punctuation, no extraneous zeroes, no decimal point, just zeroes and ones.
Examples
Input:
82000

Output (receives bonus):
2 10100000001010000
3 11011111001
4 110001100
5 10111000
81999 11
82000 10

Input:
1234321

Output (no bonus):
2
1111
1234320
1234321

Can the input end with a newline?

@LegionMammal978 - Uhhh... sure?  My intent was that you should be able to get the input number with a simple fgets, readline, or something similar.

In general, n is always at least binary in bases 1 (not counted), 2, n-1, and n.

When you say, "your number will be provided on standard input," do you mean STDIN only, or can we alternatively accept the number as a function argument as is standard for the site?

Should the binary representation (in the bonus part) have a certain format? Particularly would [1, 0, 1, 1, 0] be o.k., or does the numbers have to be joined like 10110?

I've clarified the rules regarding bonus point criteria and warnings.

@Mr.Llama What about input?

I am curiuos. Did you really tried all numbers up to 1 million digits?

@edc65 - Not every single one.  There's some major optimizations you can make to skip large ranges of values.

How many bases do we need to output?

@FireCubez - "In ascending order, display each base greater than one that the number is binary in."  The number of bases a number is binary in will differ.

Pyth, 14 13
jbf!-jQTU2tSQ

Thanks to Jakube for pointing out the new S function.
Try it here.
The online version is too slow to do 1234321. This simply converts the input to each base from 2 to itself and discards the results that contain values other than 0 and 1.
Explanation:
                           : Q=eval(input) (implicit)
jb                         : join on newlines the list...
  f!                       : filter away nonempty values (impliticly named T)
    -jQTU2                 : sewtise difference of number converted to base and range(2)
     jQT                   : convert Q to base T
        U2                 : range(2)
          tSQ              : over the range [2 Q+1)

In addition, this is a (not well golfed now well golfed, again thanks to Jakube) bonus version (20 * .75 = 15):
VQI!-JjQK+2NU2pdKjkJ

Try it here

Pyth just got updated. So you can link to actual solutions.

And here's a 20 * 0.75 = 15 solution: VQI!-JjQK+2NU2pdKjkJ Sometimes functional programming is not the best approach.

Julia, 72 70 bytes
It's actually longer with the bonus, so no bonus here.
n=int(readline());for j=2:n all(i->i∈0:1,digits(n,j))&&println(j)end

This reads a line from STDIN, converts it to an integer, and prints the result. Despite being a brute force method, the input 1234321 took less than 1 second for me.
Ungolfed + explanation:
# Read n from STDIN and convert to integer
n = int(readline())

# For every potential base from 2 to n
for j = 2:n
    # If all digits of n in base j are 0 or 1
    if all(i -> i ∈ 0:1, digits(n, j))
        # Print the base on its own line
        println(j)
    end
end

Examples:
julia> n=int(readline());for j=2:n all(i->i∈0:1,digits(n,j))&&println(j)end
1234321
2
1111
1234320
1234321

julia> n=int(readline());for j=2:n all(i->i∈0:1,digits(n,j))&&println(j)end
82000
2
3
4
5
81999
82000

NOTE: If input can be taken as a function argument rather than from STDIN (awaiting confirmation from the OP), the solution is 55 bytes.

CJam, 20 bytes (or 27 bytes * 0.75 = 20.25)
Here is the no bonus version, 20 bytes:
ri:X,2f+{X\b2,-!},N*

Try this here.
Just for fun, here is the bonus version, 27 bytes:
ri:X{X\)b2,-!},1>{)SX2$bN}/

Try it online here

Sure. Once I am done a bit of golfing.

ri_,f{2+S@2$bN}4/{2=2,-!}, (19.5 bytes)

Python 2, 88 86 80
Fairly straightforward, no bonus. Python is nice and lenient with global variables.
N=input();g=lambda n:n<1or(n%b<2)*g(n/b)
for b in range(2,N+1):
 if g(N):print b

Best I've managed to get for the bonus is 118*.75 = 87.75:
N=input();g=lambda n:0**n*" "or" "*(n%b<2)and(g(n/b)+`n%b`)*(g(n/b)>'')
for b in range(2,N+1):
 if g(N):print`b`+g(N)

Nice solution, beat me to it with much shorter code.

It would be shorter to just do g(N) instead of n=N.

@feersum Oh yeah (it used to be g(N,b) so the comma made the two equal), but what do you mean I wouldn't need a variable for N?

@KSab I deleted that second part; never mind it.

I may be wrong but couldn't you get the bonus by just changing g(n/b) to (g(n/b)+'n%b') where ' represents a backtick?

@feersum The n<1or will make it sometimes return a bool but I think it should be doable with some tweaking.

@KSab 1**n is a numerical synonym for n<1 on non-negative ints.

@xnor Did you mean 0**n?

@Sp3000 Yup, derp.

Mathematica, 59 bytes
Print/@Select[1+Range[n=Input[]],Max@IntegerDigits[n,#]<2&]

Ugh... IntegerDigits D:
There isn't really much to explain about the code... 12 bytes are wasted by the requirement for using STDIN and STDOUT.
I don't think I can claim the bonus. The best I've got is 84 bytes (which yields a score over 60):
Print@@@Select[{b=#+1," ",##&@@n~IntegerDigits~b}&/@Range[n=Input[]],Max@##3<2&@@#&]

Python 2, 90 * 0.75 = 67.5
n=input();b=1
while b<n:
 b+=1;s="";c=k=n
 while k:s=`k%b`+s;c*=k%b<2;k/=b
 if c:print b,s

Pretty straightforward iterative approach.
Without the bonus, this is 73 bytes:
n=input();b=1
while b<n:
 b+=1;c=k=n
 while k:c*=k%b<2;k/=b
 if c:print b

SQL (PostgreSQL), 247.5 255 230.25 (307 * .75)
Since SQL is known to be wonderful at these sorts of challenges, I thought I better put one together :) The bonus was really worthwhile for this one.It should comply with spec, but I have no easy way to test the COPY I FROM STDIN.
Edit Fixed order. Changed the way column R is handled to use an array.
CREATE TABLE IF NOT EXISTS I(I INT);TRUNCATE TABLE I;COPY I FROM STDIN;WITH RECURSIVE R AS(SELECT n,I/n I,ARRAY[I%n] R FROM generate_series(2,(SELECT I FROM I))g(n),(SELECT I FROM I)I(I)UNION ALL SELECT n,I/n,I%n||R FROM R WHERE I>0)SELECT n||' '||array_to_string(R,'')FROM R WHERE 2>ALL(R)and i=0ORDER BY n

As a test I just used straight inserts into the I table.
Test run expanded and commented.
-- Create the table to accept the input from the copy command
CREATE TABLE IF NOT EXISTS I(I INT);
-- Make sure that it is empty
TRUNCATE TABLE I;
-- Popoulate it with a value from STDIN
--COPY I FROM STDIN;
INSERT INTO I VALUES(82000); -- Testing
--Using a recursive CTE query
WITH RECURSIVE R AS (
    -- Recursive anchor
    SELECT n,                -- base for the row
       I/n I,                -- integer division
       ARRAY[I%n] R   -- put mod value in an array
    FROM generate_series(2,(SELECT I FROM I))g(n), -- series for the bases
         (SELECT I FROM I)I(I) -- Cross joined with I,  saves a few characters
    UNION ALL
    -- for each row from r recursively repeat the division and mod until i is 0
    SELECT n,
        I/n,
        I%n||R -- Append mod to beginning of the array
    FROM R WHERE I>0
    )
-- return from r where i=0 and r has 1's and 0's only
SELECT n||' '||array_to_string(R,'')
FROM R
WHERE 2 > ALL(R)and i=0
ORDER BY n -- Ensure correct order

2 10100000001010000
3 11011111001
4 110001100
5 10111000
81999 11
82000 10

So close!  The output bases needs to be in ascending order.  +1 for using an unconventional language though.

@Mr.Llama fixed it with an order by.  Now to see if I can get those characters back

Haskell 109*0.75 = 81.75 bytes
0#x=[]
n#x=n`mod`x:div n x#x
f n=[show x++' ':(n#x>>=show)|x<-[2..n+1],all(<2)$n#x]
p=interact$unlines.f.read

Usage example (note: binary values are lsb first):
p 82000

2 00001010000000101
3 10011111011
4 001100011
5 00011101
81999 11
82000 01

Without input/output restrictions, i.e input via function argument, output in native format via REPL):
Haskell, 67*0.75 = 50.25 bytes
0#x=[]
n#x=n`mod`x:div n x#x
f n=[(x,n#x)|x<-[2..n+1],all(<2)$n#x]

Returns a list of (base,value) pairs. The values are lsb first, e.g. (newlines/spaces added for better display):
 f 82000
 [ (2,[0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,1]),
   (3,[1,0,0,1,1,1,1,1,0,1,1]),
   (4,[0,0,1,1,0,0,0,1,1]),
   (5,[0,0,0,1,1,1,0,1]),
   (81999,[1,1]),
   (82000,[0,1]) ]

Java, 181 155.25(207 * .75) 151.5(202 * .75) bytes
class I{public static void main(String[]a){a:for(long b=new java.util.Scanner(System.in).nextLong(),c,d=1;d++<b;){String e="";for(c=b;c>0;e=c%d+e,c/=d)if(c%d>1)continue a;System.out.println(d+" "+e);}}}

Expanded with explanation:
class I {
    public static void main(String[]a){
        a:for(long b=new java.util.Scanner(System.in).nextLong(),c,d=1; //b = input(), d = base
              d++<b;) {                                           //For all bases in range(2,b+1)
            String e="";
            for(c = b;c > 0; e = c % d + e,c /= d)                //Test all digits of base-d of b
                           //e = c % d + e                        //Append digits to string
                if (c % d > 1)                                    //Reject base if the digit is greater than 1
                    continue a;
            System.out.println(d+" "+e);                          //Print base and digits.
        }
    }
}

Original (without bonus):
class I{public static void main(String[]a){long b=new java.util.Scanner(System.in).nextLong(),c,d=1;a:for(;d++<b;){c=b;while(c>0){if(c%d>1)continue a;c/=d;}System.out.println(d);}}}

3.75 bytes thanks to Ypnypn :)

R, 111
Probably a lot of room to improve this at the moment
i=scan();b=2:i;R=i%%b;I=rep(i,i-1);while(any(I<-I%/%b))R=cbind(I%%b,R);for(x in b)if(all(R[x-1,]<2))cat(x,'\n')

Runs with warnings
> i=scan();b=2:i;R=i%%b;I=rep(i,i-1);while(any(I<-I%/%b))R=cbind(I%%b,R);for(x in b)if(all(R[x-1,]<2))cat(x,'\n')
1: 82000
2:
Read 1 item
There were 17 warnings (use warnings() to see them)
2
3
4
5
81999
82000
>

@AlexA.  Warnings caused by coercing the I%/%b to a logical in the any() clause.  `

R, 94 83 79
n=scan();cat((2:n)[!sapply(2:n,function(x){while(n&n%%x<2)n=n%/%x;n})],sep="\n")

Usage:
> n=scan();cat((2:n)[!sapply(2:n,function(x){while(n&n%%x<2)n=n%/%x;n})],sep="\n")
1: 82000
2:
Read 1 item
2
3
4
5
81999
82000
> n=scan();cat((2:n)[!sapply(2:n,function(x){while(n&n%%x<2)n=n%/%x;n})],sep="\n")
1: 1234321
2:
Read 1 item
2
1111
1234320
1234321

The core of the function is !sapply(2:n,function(x){while(n&n%%x<2)n=n%/%x;n}) which, for each base x from 2 to n, keep the quotient n/x as long as the remainder is either 0 and 1. It then outputs the result (which is 0 if all remainders were either 1 or 0) and negates it (0 negates to TRUE, everything else negates to FALSE). Thanks to function scope, there is no need to make a dummy variable for n. The resulting vector of booleans is then used to index 2:n and therefore outputs only the bases for which it worked.

Jelly, 9 bytes
³bṀỊµÐfḊY

Try it online!
Done alongside caird coinheringaahing in chat.
How it works

³bṀỊµÐfḊY    Full program.

     Ðf      Filter the implicitly generated range [1, input].
    µ        Starts a new monadic chain.
³b           Convert the input to the base of the current number, as a list.
  Ṁ          Maximum.
   Ị         Insignificant. Checks if abs(Z) ≤ 1.
       Ḋ     Dequeue; Removes the first element of the list (to drop base 1).
        Y    Join by newlines.

APL (Dyalog Extended), 28 bytes, 28 * 0.75 = 21
{{⍵⌿⍨∧/2>↑2⌷⍉⍵}(⍪,⊤∘⍵¨)1↓⍳⍵}

1↓⍳⍵ all numbers from 2 to ⍵
(⍪,⊤∘⍵¨) each number with the representation of ⍵ in that base
{⍵⌿⍨∧/2>↑2⌷⍉⍵} dfn to filter
↑2⌷⍉⍵ 2nd column as a matrix
2> is 2 greater than?
∧/ boolean and
⍵⌿⍨ replicate
Try it online!

TI-BASIC, 31 29
For(B,2,Ans
If 2>round(Bmax(fPart(Ans/B^randIntNoRep(1,32
Disp B
End

This is probably optimal for TI-BASIC.
Explanation:
randIntNoRep(1,32) returns a random permutation of the numbers from 1 to 32 (All we need is those numbers in some order; TI-BASIC doesn't have anything like APL's iota command). 32 elements is enough because the smallest possible base is 2 and the largest number is 2^32-1. B^randIntNoRep(1,31) raises that list to the Bth power, which results in the list containing all of B^1,B^2,...,B^32 (in some order).
Then the input (in the Answer variable, which is input to in the form [number]:[program name]) is divided by that number. If your input is 42 and the base is 2, the result will be the list 21,10.5,5.25,...,42/32,42/64,[lots of numbers less than 1/2], again in some order.
Taking the fractional part and multiplying the number by your base gives the digit at that position in the base-b representation. If all digits are less than 2, then the greatest digit will be less than 2.
As Ypnypn stated, a closing parenthesis on the For statement speeds this up due to a parser bug.
31->31: Saved a byte but fixed rounding errors which added the byte again.
31->29: Saved two bytes by using RandIntNoRep() instead of cumSum(binomcdf()).

Does TI-BASIC have a sequence function?

Yes, the command is seq(expression, variable, start, end[, step]). If no step is given, it defaults to 1. However, cumSum(binomcdf(31,0 is 8 bytes whereas seq(X,X,1,32 is 9 bytes.

Ah, that explains it.  I'm not familiar with scoring works in TI-Basic.

TI-Basic, 45 bytes
Input N
For(B,2,N
If prod(seq(BfPart(iPart(N/B^X)/B),X,0,log(N)/log(B))<2
Disp B
End

Explanation

Input N
For every B from 2 to N

If N is just 0 and 1 in base B

Display B

End loop

The complicated part
The second line works as follows:

For every X from 0 to logB N
B × fPart(iPart(N / BX) / B) is the Nth digit in base B, counting backwards
Consider this as a list
For each element, if the digit is less than 2, yield 1 (true), else 0 (false)
Take the product: 1 iff all elements are 1

Note
The program runs significantly faster if a closing parenthesis ) is placed at the end of the second line. See here for more about this.

Javascript, ES6, 118*.75 = 88.5 110*.75 = 82.5
f=x=>{res={};for(b=2;b<=x;++b)if(!+(res[b]=(c=x=>x%b<2?x?c(x/b|0)+""+x%b:"":"*")(x)))delete res[b];return res}

Previous version:
f=x=>{res={};for(q=2;q<=x;++q)if(!+(res[q]=(c=(x,b)=>x%b<2?x?c(x/b|0,b)+""+x%b:"":"*")(x,q)))delete res[q];return res}

Check:
f(82000)
Object { 2: "10100000001010000", 3: "11011111001", 4: "110001100", 5: "10111000", 81999: "11", 82000: "10" }

Here you have no input and no output.

JavaScript (ES6) 65
68 bytes for a function with a parameter and console output.
f=n=>{s=n=>n%b>1||b<n&&s(n/b|0);for(b=1;b++<n;)s(n)||console.log(b)}

65 bytes with I/O via popup
n=prompt(s=n=>n%b>1||b<n&&s(n/b|0));for(b=1;b++<n;)s(n)||alert(b)

Claiming the bonus: 88*0.75 => 66
n=prompt(s=n=>n%b>1?9:(b<=n?s(n/b|0):'')+n%b);for(b=1;b++<n;)s(n)<'9'&&alert(b+' '+s(n))

Mathematica, 76 * 0.75 = 57
n=Input[];G=#~IntegerDigits~b&;If[Max@G@n<2,Print[b," ",Row@G@n]]~Do~{b,2,n}

Initially forgot about the input requirements... Fortunately, those didn't add too much extra.

Ruby, 44 bytes
->n{(2..n).select{|i|n.digits(i)-[0,1]==[]}}

Try it online!

Perl 5, 63 bytes
map{$t=$n;1while($f=$t%$_<2)&&($t=int$t/$_);say if$f}2..($n=<>)

Try it online!
No bonus on this because it scores very slightly better than my version with the bonus:
Perl 5, 85 bytes * 0.75 = 63.75
map{my$r;$t=$n;$r=$/.$r while($/=$t%$_)<2&&($t=int$t/$_);say"$_ 1$r"if$/<2}2..($n=<>)

Try it online!

Husk, 11 10 bytes
¶tfoΛε`B¹ḣ

Try it online!
-1 byte from Zgarb.
Explanation
¶tfoΛ<2`B¹ḣ
          ḣ list from 1..n
  f         filter based on the result of the following
   o        composition of 2 functions
       `B¹  the input in base n as digits
    Λ<2     are all digits < 2?
 t          remove first element
¶           join with newlines

<2 can be ε here

@Zgarb May I ask, what was the idea behind adding that?

You'd be surprised how often it saves a byte. Jelly has it too, as Ị.

Japt -R, 11 bytes
õ2 f@ìX e§1

Try it
õ2 f@ìX e§1     :Implicit input of integer U
õ2              :Range [2,U]
   f            :Filter by
    @           :Passing each X through the following fuction
     ìX         :  Convert U to base X digit array
        e       :  All
         §1     :    <=1
                :Implicit output, joined with newlines