Ruby Golf on Lazy T9 Words

ruby-talk
1

Assuming you are running Linux and have a list of valid English words in the file /usr/share/dict/words or someplace or something similar.

Assume you have a cellphone with T9 predictive text input.

For those that don't, cellphones have each key overloaded to mean several things. eg. On my Sharp GX-15
2 also means A,B,C
3 also means D,E,F
4 also means G,H,I
5 also means J,K,L
6 = M,N,O
7 = P,Q,R,S
8 = T,U,V
9 = W,X,Y,Z

In T9 mode I can type in 43556 and it only finds one word in its dictionary that can be made with combination {G,H,I}{D,E,F}{J,K,L}{J,K,L}{M,N,O} and that is
HELLO

Which is a lost faster than typing 4433555555666.

How ever, some words like "high", can be entered by just bouncing on one key ... 4444.

Your mission, should you choose to accept, is to write the shortest ruby program that will find the longest word in the dictionary that can be produced by...
  * repeatedly typing one key
  * Can be produced by just using only two keys.
  * Can be produced by just using only three keys.
  * Can be produced by just using only four keys.
  * ....

John Carter Phone : (64)(3) 358 6639
Tait Electronics Fax : (64)(3) 359 4632
PO Box 1645 Christchurch Email : john.carter@tait.co.nz
New Zealand

Carter's Clarification of Murphy's Law.

"Things only ever go right so that they may go more spectacularly wrong later."

From this principle, all of life and physics may be deduced.

2

If you wanted this to be a rubyquiz, you better could have send it to
James Edward Gray II. A similar quiz has allready been done in the
past. Check out http://rubyquiz.com and look around.

grtz,
wannes

···

On 06/10/05, John Carter <john.carter@tait.co.nz> wrote:

Assuming you are running Linux and have a list of valid English words in
the file /usr/share/dict/words or someplace or something similar.
Assume you have a cellphone with T9 predictive text input.
Your mission, should you choose to accept, is to write the shortest ruby
program that will find the longest word in the dictionary that can be
produced by...

3

John Carter wrote:

Assuming you are running Linux and have a list of valid English words in
the file /usr/share/dict/words or someplace or something similar.

Assume you have a cellphone with T9 predictive text input.

For those that don't, cellphones have each key overloaded to mean several
things. eg. On my Sharp GX-15
2 also means A,B,C
3 also means D,E,F
4 also means G,H,I
5 also means J,K,L
6 = M,N,O
7 = P,Q,R,S
8 = T,U,V
9 = W,X,Y,Z

In T9 mode I can type in 43556 and it only finds one word in its
dictionary that can be made with combination
{G,H,I}{D,E,F}{J,K,L}{J,K,L}{M,N,O} and that is
HELLO

Which is a lost faster than typing 4433555555666.

How ever, some words like "high", can be entered by just bouncing on one
key ... 4444.

Your mission, should you choose to accept, is to write the shortest ruby
program that will find the longest word in the dictionary that can be
produced by...
  * repeatedly typing one key
  * Can be produced by just using only two keys.
  * Can be produced by just using only three keys.
  * Can be produced by just using only four keys.
  * ....

Assumes that ambiguity is disallowed; rejects words with apostrophes.

h=Hash.new(0)
a=ARGF.grep(/^\w+$/).sort_by{|x|-x.size}.map{|w|w.chomp!.downcase!
c=w.split('').map{|c|2+"abc def ghi jkl mno pqrstuv wxyz".index(c)/4}
h[c]+=1;[w,c]}.reject{|w,c|h[c]>1}
(1..8).each{|n|p [n,a.find{|w,c|n==c.uniq.size}[0]]}

[1, "deeded"]
[2, "blackjack"]
[3, "openendedness"]
[4, "prepossessingness"]
[5, "contemporaneousness"]
[6, "microspectrophotometric"]
[7, "antidisestablishmentarianism"]
[8, "microspectrophotometrically"]

4

William James wrote:

John Carter wrote:
> Assuming you are running Linux and have a list of valid English words in
> the file /usr/share/dict/words or someplace or something similar.
>
> Assume you have a cellphone with T9 predictive text input.
>
> For those that don't, cellphones have each key overloaded to mean several
> things. eg. On my Sharp GX-15
> 2 also means A,B,C
> 3 also means D,E,F
> 4 also means G,H,I
> 5 also means J,K,L
> 6 = M,N,O
> 7 = P,Q,R,S
> 8 = T,U,V
> 9 = W,X,Y,Z
>
> In T9 mode I can type in 43556 and it only finds one word in its
> dictionary that can be made with combination
> {G,H,I}{D,E,F}{J,K,L}{J,K,L}{M,N,O} and that is
> HELLO
>
> Which is a lost faster than typing 4433555555666.
>
> How ever, some words like "high", can be entered by just bouncing on one
> key ... 4444.
>
> Your mission, should you choose to accept, is to write the shortest ruby
> program that will find the longest word in the dictionary that can be
> produced by...
> * repeatedly typing one key
> * Can be produced by just using only two keys.
> * Can be produced by just using only three keys.
> * Can be produced by just using only four keys.
> * ....

Assumes that ambiguity is disallowed; rejects words with apostrophes.

h=Hash.new(0)
a=ARGF.grep(/^\w+$/).sort_by{|x|-x.size}.map{|w|w.chomp!.downcase!
c=w.split('').map{|c|2+"abc def ghi jkl mno pqrstuv wxyz".index(c)/4}
h[c]+=1;[w,c]}.reject{|w,c|h[c]>1}
(1..8).each{|n|p [n,a.find{|w,c|n==c.uniq.size}[0]]}

[1, "deeded"]
[2, "blackjack"]
[3, "openendedness"]
[4, "prepossessingness"]
[5, "contemporaneousness"]
[6, "microspectrophotometric"]
[7, "antidisestablishmentarianism"]
[8, "microspectrophotometrically"]

Shorter:

h=Hash.new(0)
a=ARGF.grep(/^\w+$/).sort_by{|x|-x.size}.map{|w|w.chomp!.downcase!
c=w.split('').map{|c|2+"abc def ghi jkl mno pqrstuv wxyz".index(c)/4}
h[c]+=1;[w,c]}
(1..8).each{|n|p [n,a.find{|w,c|1==h[c]&&n==c.uniq.size}[0]]}

5

If you wanted this to be a rubyquiz, you better could have send it to
James Edward Gray II.

Didn't even occur to me. Just thought it was a nice simple problem to which I personally wanted the answer. Since I thought it would be fun, I wondered if anyone else would have fun with it. RubyQuiz must have been somewhere in my subconscious since I borrowed his "wish to accept" tag line.

A similar quiz has allready been done in the
past. Check out http://rubyquiz.com and look around.

There was a quiz to design a "better than multitap" algorithm, not given T9, what is the longest word with shortest taps.

I started crafting a solution to my problem when I got lost with wheels in wheels in wheels and stopped.

I then went for a walk to buy milk and had the notion that regexes would be good....

···

On Thu, 6 Oct 2005, wannes wrote:

On 06/10/05, John Carter <john.carter@tait.co.nz> wrote:

=========================================================
a=Hash.new('')
IO.read('/usr/share/dict/words').scan(/[a-z]+/i){|m|
    x={}

    m.upcase.tr( 'ABCDEFGHIJKLMNOPQRSTUVWXYZ',
                 '22233344455566677778889999').each_byte{|c|
      x[c]=c
    }
    z=x.keys.size
    i=a[z]
    a[z]=m if i.size < m.size
}
p a

But than gave just the one example, so I extended it to give me all words of the maximum length..

# I love the flexibility of the Ruby hash constructor. I use that # feature all the time.
a=Hash.new([''])

# Hah! I didn't even know about ARGF. Ah well, I learn something
# new every day!

# I should of used \w instead of [a-z], that would have been shorter.
IO.read('/usr/share/dict/words').scan(/[a-z]+/i){|m|
   x={}

   # I chose upcase instead of downcase, saved me 2 chars. :wink:
   # Hmm, perhaps I should have done the tr before the scan.
   m.upcase.tr( 'ABCDEFGHIJKLMNOPQRSTUVWXYZ',
                '22233344455566677778889999').each_byte{|c|
     x[c]=c
   }

   # Somehow I sure if I was smarter there would be a shorter way of
   # finding the number of uniq chars in a string. Especially
   # as I could make those chars whatever I like.

   z=x.keys.size

   i=a[z]
   if i[0].size < m.size
     a[z]=[m]
   elsif i[0].size == m.size
     # Now this is actually quite subtle.
     # Who says ruby doesn't have pointers?
     # I have another fun problem in my head that relates to that.
     i << m
   end
}
a.keys.sort.each{|k| puts "#{k}\n\t#{a[k].sort.uniq.join("\n\t")}\n"}

The result is...

1
   deeded
2
   blackball
   blackjack
   depressed
   depresses
   preferred
   redressed
   redresses
   repressed
   represses
3
   shepherdesses
4
   presumptuousness
5
   transubstantiation
6
   contradistinctions
   disenfranchisement
   disproportionating
   hypersensitivities
   misinterpretations
   misrepresentations
7
   counterrevolutionaries
   electroencephalographs
8
   counterrevolutionary
   uncharacteristically

It is interesting that the 8 key words are shorter than the 7.

John Carter

The Cybernetic Entomologist - cyent@xtra.co.nz

http://geocities.yahoo.com/cy_ent

I'm becoming less and less convinced of humans as rational beings.
I suspect we are merely meme collectors, and the reason meme is only
kept on to help count our change.

John Carter Phone : (64)(3) 358 6639
Tait Electronics Fax : (64)(3) 359 4632
PO Box 1645 Christchurch Email : john.carter@tait.co.nz
New Zealand

Carter's Clarification of Murphy's Law.

"Things only ever go right so that they may go more spectacularly wrong later."

From this principle, all of life and physics may be deduced.

6

So having learnt from the other posts I get down to...

a=Hash.new([''])
ARGF.read.upcase.scan(/\w+/){|m|

   z = m.tr( 'A-Z',
             '22233344455566677778889999').split('').sort.uniq.size

   i=a[z]
   if (j=i[0].size) < n = m.size
     a[z]=[m]
   elsif j == n
     i << m
   end
}
a.keys.sort.each{|k| puts "#{k}\n\t#{a[k].sort.uniq.join("\n\t")}\n"}

1
   DEEDED
2
   BLACKBALL
   BLACKJACK
   DEPRESSED
   DEPRESSES
   PREFERRED
   REDRESSED
   REDRESSES
   REPRESSED
   REPRESSES
3
   SHEPHERDESSES
4
   PRESUMPTUOUSNESS
5
   TRANSUBSTANTIATION
6
   CONTRADISTINCTIONS
   DISENFRANCHISEMENT
   DISPROPORTIONATING
   HYPERSENSITIVITIES
   MISINTERPRETATIONS
   MISREPRESENTATIONS
7
   COUNTERREVOLUTIONARIES
   ELECTROENCEPHALOGRAPHS
8
   COUNTERREVOLUTIONARY
   UNCHARACTERISTICALLY

John Carter Phone : (64)(3) 358 6639
Tait Electronics Fax : (64)(3) 359 4632
PO Box 1645 Christchurch Email : john.carter@tait.co.nz
New Zealand

Carter's Clarification of Murphy's Law.

"Things only ever go right so that they may go more spectacularly wrong later."

From this principle, all of life and physics may be deduced.