Optimizing the telephone keypad
Perl, 333

$_=&lt;&gt;;$c{$&amp;}++while/./g;@c=sort{$c{$b}&lt;=&gt;$c{$a}}keys%c;$d{$&amp;.$1}++while/.(?=(.))/g;sub f{my$x=shift;if(my$c=pop@$x){for(grep!$_[$_],0..7){my@y = @_;$y[$_]=$c;f([@$x],@y)}}else{for(0..7){$z=$_[$_];$c+=$d{$z.$_}+$d{$_.$z}for@{$a[$_]}}$c&lt;$m?($m=$c,@n=@_):1}}while(@c){$m= ~0;f[splice@c,0,8];push@{$a[$_]},$n[$_]for 0..7}print@$_,$/for@a


Here's an attempt to optimize for rule #2. After my comment, above, and in lieu of answers taking that rule into account (cf. high question rating), I thought that I owe some effort here...

Solutions that don't optimize for rule #2 can produce output very far from optimal. I checked long natural English text ("Alice in Wonderland", actually), pre-processed (lower case letters only), and e.g. Perl script from OJW's answer, result being

2: ermx
3: tdfz
4: alp
5: oub
6: ick
7: nwv
8: hgj
9: syq


er alone ruins it, plus some other pairs should never have ended on the same key...

Btw, zxqjvkbpfmygwculdrshnioate are letters sorted, frequency ascending, from that text.

If we try to solve it easy way (hoping for -35 bonus, maybe) and place letters one by one, choosing available key by minimal pair-wise count, we can end with e.g.:

slbx
hdmz
nrf
iuj
ogv
awk
tcp
eyq


I don't post code for this (wrong) solution here. E.g., note, c is more frequent than w and is placed first. tc (ct) pairs are obviously less frequent than ac (ca) - 43+235 against 202+355. But then w ends up with a -- 598+88. We end with pairs aw and tc (964 total), though it would be better ac and tw (635 total). Etc..

So, next algorithm tries to check each 8 remaining (or 2, if last) most frequent letters against letters already on the keypad, and to place them so that pair-wise count is minimal.

$_=&lt;&gt;;                          # Read STDIN.
$c{$&amp;}++while/./g;              # Count letters (%c hash).
@c=sort{$c{$b}&lt;=&gt;$c{$a}}keys%c; # Sort them by frequency, ascending
$d{$&amp;.$1}++while/.(?=(.))/g;    # (@c array), and count pairs (%d hash).

                                # Next is recursive sub that does the job.
                                # Some CPAN module for permutations
                                # would probably do better...
                                # Arguments are reference to array of what's 
                                # left un-placed of current 8-pack of letters,
sub f{                          # and 8 element list of placed letters
    my$x=shift;                 # (or undefs).
    if(my$c=pop@$x){            # Pop a letter from 8-pack (if anything left),
        for(grep!$_[$_],0..7){  # try placing it on each available key, and 
            my@y = @_;          # call sub again passing updated arguments.
            $y[$_]=$c;
            f([@$x],@y)
        }
    }else{                      # If, OTOH, 8-pack is exhausted, find sum of
        for(0..7){              # pairs count of current permutation (@_) and 
            $z=$_[$_];          # letters placed in previous rounds (8-packs).
                                # @a is "array of arrays" - note, we didn't 
                                # have to initialize it. First "8-pack" will
                                # be placed on empty keypad "automatically".
                                # We re-use undefined (i.e. 0) $c.

            $c+=$d{$z.$_}+$d{$_.$z}for@{$a[$_]}
        }
        $c&lt;$m                   # Is sum for current placement minimal?
            ?($m=$c,@n=@_)      # Then remember this minimum and placement.
            :1
    }
}

while(@c){
    $m= ~0;                         # Initialize "minimum" with large enough 
    f[splice@c,0,8];                # number, then call sub with each 8-pack
                                    # (and empty list of placed letters 
                                    # from current round). On return,
                                    # @n will have optimal arrangement.
    push@{$a[$_]},$n[$_]for 0..7    # Then place it permanently on keypad.
}
print@$_,$/for@a                    # Show us what you've done.


Result is:

sdfz
hlmx
nrv
iyp
ogk
acq
twb
euj


I don't like the ac pair (The Cat being one of the characters, after all), but, still that's optimal letter placement for English, if my code is not wrong. Not exactly 'golfing' effort, just some working solution, ugly or not.