Optimizing the telephone keypad There seems to be this ongoing craze about people tediously learning new keyboard layouts like Dvorak or Neo because it supposedly makes them more productive. I argue that switching keyboard layouts is a bad idea, because it can take you months to get up to speed, and when you're finially 5% faster than the rest, you're screwed if you need to type on a computer that isn't your own.

Also, all these people forget where the real bottleneck in modern communication lies - the telephone keypad.

This is how your average telephone keypad looks like:



Letter 'r' is the third letter on button 7; so if you were to type the letter 'r' on a mobile phone, you would press button 7 three times, for 's' you'd press it 4 times, and for 'a' you'd press button 2 once.

Considering this, putting 'e' after 'd' was probably a bad decision - 'e' is the most commonly used letter in the english alphabet, so, if you were to label button 3 "EDF" instead of "DEF", you would save quite a lot of keystrokes.

Moreover, you've probably experienced yourselves that typing 2 letters that share the same button is a nuisance - if you want to write "TU", you can't just hit 8 three times, because that would result in 'V'. So usually you'd write 'T', then hit space, then hit backspace, and then write 'U', which equals 5 button presses instead of 3.



TL;DR

Given these two rules:


A letter is typed by pressing a button n times, where n is the position of where the letter is at on the button's label
Writing two letters that are typed using the same button requires an additional 2 button presses


What's the telephone keyboard layout that requires the least amount of button presses, given a specific text?
You should only use the buttons 2-9, 1 and 0 are reserved for special symbols.

Input

The text which you should find the optimal layout for is supplied via stdin. You don't need to handle anything other than the lowercase alphabet and can assume that the input consists of only that.
You can also assume that the input text is reasonably large and every letter is in there at least once, if that helps.

Output

I don't want to put too many constraints on the output, since that sometimes gives some languages advantages over others; so however your language shows arrays is fine, alternatively you can seperate each label with a newline.

There may be multiple possible optimal layouts, you can print any one of them.
Here's a simple example:

&gt;&gt; echo "jackdawslovemybigsphinxofquartz" | foo.sh
ojpt
avhz
cen
skm
dyf
wbq
ixu
lgr


Bonus Points

-35 if your algorithm is not brute-forcing all possible layouts (I'm looking at Haskell's `permutations' here)

-3 if your code fits inside a text message (140 chars) and you post a pic of you sending your code to a friend.

This is my first challenge on StackExchange. I'd be happy to hear whether you like it, or have any other feedback about it!
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.