Question about performance

[Peter Hickman]

I have a little program I wrote in Ruby to find all the chains between any two four letter words where each intermediate word only differs by one letter. In Ruby this program runs in one hour or so from a list of 4919 words. The dictionary file contains things like '

aani arni bani dani mani pani rani' which means that 'aani' is only one letter different from arni, bani, dani, mani, pani and rani (yes they are all valid words). From the output you can see that it took a little over an hour to process all 4919 words. The program is somewhat inefficient and I could easily improve on it but as I was looking at Go I skipped that and went straight for a version of this program in Go.

First the Ruby version:

#!/usr/bin/env ruby

# I, [2014-05-31T11:56:12.982985 #5706]  INFO -- : Loading dictionary from dictionary.txt

# I, [2014-05-31T11:56:13.045781 #5706]  INFO -- : Loaded 4919 words

# I, [2014-05-31T11:56:13.045847 #5706]  INFO -- : Starting to build the pairs

# I, [2014-05-31T12:01:13.899227 #5706]  INFO -- : Created 12100740 pairs

# I, [2014-05-31T13:08:50.284022 #5706]  INFO -- : Writing chains to chains.txt

require 'logger'

MAX_DEPTH=17

def make_key(a, b)

  [a,b].sort.join(":")

end

def expand(depth)

  if depth % 2 == 0

    index_to_read = 0

    index_to_write = 1

  else

    index_to_read = 1

    index_to_write = 0

  end

  $tree[index_to_write].clear

  words = $tree[index_to_read].map do |word|

    $dictionary[word]

  end.flatten.uniq

  words.each do |word|

    key = make_key($root_word, word)

    if $pairs[key] > depth

      $pairs[key] = depth

    end

  end

  if depth < MAX_DEPTH

    $tree[index_to_write] = words

    expand(depth + 1)

  end

end

def load_dictionary(filename)

  $logger.info "Loading dictionary from #{filename}"

  f = File.open(filename,"r")

  f.each do |line|

    x = line.chomp.split(/\s+/)

    k = x.shift

    $dictionary[k] = x

  end

  f.close

  $logger.info "Loaded #{$dictionary.size} words"

end

def build_pairs()

  $logger.info "Starting to build the pairs"

  $dictionary.keys.each do |outer|

    $dictionary.keys.each do |inner|

      key = make_key(outer, inner)

      $pairs[key] = 999 unless $pairs.has_key?(key)

    end

  end

  $logger.info "Created #{$pairs.size} pairs"

end

def display_pairs(filename)

  $logger.info "Writing chains to #{filename}"

  f = File.open(filename,"w")

  $pairs.each do |k,v|

    f.puts "#{k} #{v}"

  end

  f.close

end

$logger = Logger.new(STDOUT)

$logger.formatter = Logger::Formatter.new

$dictionary = Hash.new

$pairs = Hash.new

load_dictionary("dictionary.txt")

build_pairs()

$tree = Array.new(2,Array.new)

$dictionary.keys.each do |word|

  $root_word = word

  $tree[0] = [$root_word]

  # $logger.info "Building tree from #{$root_word}" 

  expand(0)

end

display_pairs("chains.txt")

Now the Go version which is essentially the same code but with some improvements over the Ruby version. I realise that this may not be the best written program but I was expecting some improvement over the Ruby version. However whereas the Ruby version ran in little over an hour the Go version took 11 hours to process only 1303 words from the dictionary, it seems to be averaging around 30 seconds per word and the program would probably take around 40 hours to complete. As I've said I recognise that the Go version is not the best solution to this problem but I find it difficult to understand how it can be an order of magnitude worse.

I am going to take another approach to the Go version but I would like some pointers as to where the tar pit might be in this program.

package main

/*

2014/05/31 23:32:28 Loading dictionary from dictionary.txt

2014/05/31 23:32:28 Loaded 4919 words

2014/05/31 23:32:28 Starting to build the pairs

2014/05/31 23:32:41 Created 12100740 pairs

2014/05/31 23:32:41 Building tree from flux

... (1301 omitted lines)

2014/06/01 10:14:49 Building tree from twat

... (another 3616 lines to go)

*/

import ( 

  "os"

  "bufio"

  "strings"

  "container/list"

  "log"

  "fmt"

)

const maxSize = 17

var dictionary = make(map[string][]string)

var pairs = make(map[string]int)

var tree = make([]list.List, 2)

var root_word string

var logger = log.New(os.Stdout, "", log.Ldate|log.Ltime)

func loadDictionary(filename string) {

  f, err := os.Open(filename)

  if err != nil {

    logger.Fatal("error opening",filename,"=",err)

  }

  defer f.Close()

  logger.Println("Loading dictionary from",filename)

  scanner := bufio.NewScanner(f)

  for scanner.Scan() {

    p := strings.Split(scanner.Text()," ")

    dictionary[p[0]] = p[1:]

  }

  logger.Println("Loaded",len(dictionary),"words")

}

func makeKey(a,b string) string {

  if a < b {

    return a + ":" + b

  } else {

    return b + ":" + a

  }

}

func buildPairs() {

  logger.Println("Starting to build the pairs")

  for outer := range dictionary {

    for inner := range dictionary {

      key := makeKey(outer,inner)

      pairs[key] = 999

    }

  }

  logger.Println("Created",len(pairs),"pairs")

} 

func notFoundInTree(word string, index int) bool {

  for e := tree[index].Front(); e != nil; e=e.Next() {

    if e.Value.(string) == word {

      return false

    }

  }

  return true

}

func expand(depth int) {

  var index_to_read, index_to_write int

  if depth + 1 < maxSize {

    if depth % 2 == 0 {

      index_to_read = 0

      index_to_write = 1

    } else {

      index_to_read = 1

      index_to_write = 0

    }

    tree[index_to_write].Init()

    for e := tree[index_to_read].Front(); e != nil; e=e.Next() {

      word := e.Value.(string)

      for _,next_word := range dictionary[word] {

        if notFoundInTree(next_word,index_to_write) {

          tree[index_to_write].PushBack(next_word)

          key := makeKey(root_word,next_word)

          if depth < pairs[key] {

            pairs[key] = depth

          }

        }

      }

    }

    expand(depth+1)

  }

}

func initialiseTree(word string) {

  root_word = word

  tree[0].Init()

  tree[0].PushBack(root_word)

  logger.Println("Building tree from",root_word)

}

func displayPairs(filename string) {

  logger.Println("Writing chains to",filename)

  w, err := os.Create(filename)

  if err != nil {

    logger.Fatal("error creating",filename,"=",err)

  }

  defer w.Close()

  for key := range pairs {

    _, err := fmt.Fprintln(w,key,pairs[key])

    if err != nil {

      logger.Fatal("error writing to",filename,"=",err)

    }

  }

}

func main() {

  loadDictionary("dictionary.txt")

  buildPairs()

  for word := range dictionary {

    initialiseTree(word)

    expand(0)

  }

  displayPairs("chains.txt")

}

[Jérôme Champion]

Are you sure that a list that for tree, a []list.List is more efficient than [][]string ? I don't see the reason to use a list.List.

I don't think it's the part where you lose performance, but using a list.List where it's not needed is considered quite bad in go.

You should consider profiling your program.

[Fredrik Ehnbom]

I'm putting my money on makeKey: http://play.golang.org/p/I0GJL73Lsy

BenchmarkMakeKey    2000    876392 ns/op

BenchmarkMakeKey2   10000    133716 ns/op

BenchmarkMakeKey3  200000      8883 ns/op

Strings in Go are a bit special, read up at http://golang.org/ref/spec#String_types and http://blog.golang.org/strings.

/f

[Dan Kortschak]

Profile. But you are creating a lot of string garbage in makeKey calls and as has been said, slices are a better fit for this. Also, have you considered a MITM approach?

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Michael Jones]

Peter,

Have you read Donald Knuth's book, "The Stanford Graphbase"? He discusses word ladders (http://en.wikipedia.org/wiki/Word_ladder) at length. His program LADDERS uses Dijkstra's shortest path algorithm, which is excellent for your purpose. 

To be fast, you need to (a) build the graph of neighbors quickly, and, (b) use a priority queue in the Dijkstra implementation.

If you want to share your word list, I'll happily explore what would be good timings. These types of applications are a love of mine.

Michael

--

Michael T. Jones | Chief Technology Advocate  | m...@google.com |  +1 650-335-5765

[Peter Hickman]

Thanks for all the feedback I will look into it

Jérôme Champion: I assumed that as list had been implemented as a package it would be a superior solution to plain string slices, I mean why create a package that is inferior to the built in functionality. I will look at [][]string as an alternative solution. 

Fredrik Ehnbom: Given the vast improvement in timings that your versions of makeKey yields I will certainly look into incorporating these changes into the program, thank you for the suggestion

Dan Kortschak: I realise that this is causing lots of garbage to be collected, I even envisioned using a 19,676 byte string (4,919 4 character words) and indexing within that to avoid repeated memory allocation. But the issue for me is that Ruby has to do the same (ie repeated object creation and destruction) and Ruby is not a particularly fast language but still performs vastly better than Go

Michael Jones: For me the problem "what is the shortest chain between two words" has now been solved. The Ruby version has provided me with the answers. Implementing it in Go was as a non trivial exercise to get a handle on the language. I was rather surprised with how badly it went. I am tempted to try and do this is C++ to see if it is a problem common to compiled languages, perhaps also in Python to see how other dynamic languages will fare.

Thank you all for your help and suggestions.

[Kevin Gillette]

Instead of storing a concatenated string generated from makeKey, just have your map's key type be [2]string. This will prevent extra garbage from being generated, and it's semantically equivalent.

I agree with the note about use of the container/list package -- it looks like you're only using PushBack to mutate it, so []string will be much faster.

As a general note, languages like Ruby tend to have slow interpreted execution mixed with comparatively fast stdlib and garbage collection implementations; Go generally very fast execution, so the stdlib doesn't need to be leveraged as much to get good speed, and more emphasis is placed on reusing allocations and keeping things memory efficient. The result of this is that approaches you would take in interpreted languages to get efficiency may have pathological performance in Go (and vice versa, of course).

[Paul Hankin]

It looks like the function `notFoundInTree` has been introduced in your go version, and it causes your list construction to be O(n^2) rather than O(n) like the ruby version. Not sure if that's the difference because it's hard to tell how long the lists are, but it's the first place I'd check.

-- 

Paul

[Michael Jones]

Peter,

Before breakfast I implemented part 1 of the solution in Go. It reads a word list from a file and determines the pairs for each word. (These is not your solutions as that is the part I'm doing now.) I don't have your word list so I used the "worst case" SCRABBLE word lists. Here's "wc -l" for these:

     124 words2.txt

    1310 words3.txt

    5526 words4.txt

They are richer than a typical list would be so there is more work for the program to do in tabulating the links between words with single-character differences. My timings are as follows:

BenchmarkPairs_words2  500000    312062 ns/op

BenchmarkPairs_words3   50000   4478264 ns/op

BenchmarkPairs_words4    5000  23872168 ns/op

This is not too bad. For 3-letter words that produces the full graph in 4.4ms:

    0: aah  aal, aas, ach, ash, bah, dah, fah, hah, lah, nah, pah, rah, yah

    1: aal  aah, aas, ail, all, awl, bal, dal, gal, mal, pal, sal

    2: aas  aah, aal, abs, ads, ags, ahs, ais, als, ans, ars, ass, ats, ays, bas, das, eas, fas, gas, has, kas, las, mas, nas, pas, ras, tas, vas, was, zas

    3: aba  abb, abo, abs, aby, aga, aha, aia, aka, ala, ama, ana, aua, ava, awa, oba

    4: abb  aba, abo, abs, aby, alb, arb, ebb

    5: abo  aba, abb, abs, aby, ado, ago, apo, avo, azo, obo

    6: abs  aas, aba, abb, abo, aby, ads, ags, ahs, ais, als, ans, ars, ass, ats, ays, obs

    7: aby  aba, abb, abo, abs, any, ary

    8: ace  ach, act, age, ake, ale, ame, ane, ape, are, ate, aue, ave, awe, axe, aye, ice

    9: ach  aah, ace, act, ash, ech, ich, och

   10: act  ace, ach, aft, ait, alt, ant, apt, art, att

   11: add  ado, ads, adz, aid, and, ard, odd

   12: ado  abo, add, ads, adz, ago, apo, avo, azo, udo

   13: ads  aas, abs, add, ado, adz, ags, ahs, ais, als, ans, ars, ass, ats, ays, eds, ids, ods, uds

   14: adz  add, ado, ads

   15: aff  aft, alf, arf, auf, eff, iff, off

   16: aft  act, aff, ait, alt, ant, apt, art, att, eft, oft

   17: aga  aba, age, ago, ags, aha, aia, aka, ala, ama, ana, aua, ava, awa

   18: age  ace, aga, ago, ags, ake, ale, ame, ane, ape, are, ate, aue, ave, awe, axe, aye

   19: ago  abo, ado, aga, age, ags, apo, avo, azo, ego, ygo

   20: ags  aas, abs, ads, aga, age, ago, ahs, ais, als, ans, ars, ass, ats, ays, ugs

   21: aha  aba, aga, ahi, ahs, aia, aka, ala, ama, ana, aua, ava, awa, cha, sha, wha

   22: ahi  aha, ahs, ami, ani, chi, ghi, khi, phi

:

 1298: zho  mho, oho, pho, rho, tho, who, zoo

 1299: zig  big, cig, dig, fig, gig, jig, lig, mig, pig, rig, tig, vig, wig, zag, zin, zip, zit, ziz

 1300: zin  ain, bin, din, fin, gin, hin, jin, kin, lin, pin, qin, rin, sin, tin, vin, win, yin, zig, zip, zit, ziz

 1301: zip  dip, gip, hip, kip, lip, nip, pip, rip, sip, tip, yip, zap, zep, zig, zin, zit, ziz

 1302: zit  ait, bit, cit, dit, fit, git, hit, kit, lit, nit, pit, rit, sit, tit, wit, zig, zin, zip, ziz

 1303: ziz  biz, fiz, jiz, miz, riz, wiz, zig, zin, zip, zit, zuz, zzz

 1304: zoa  boa, goa, hoa, koa, moa, poa, zea, zol, zoo, zos

 1305: zol  col, dol, jol, mol, pol, sol, vol, zel, zoa, zoo, zos

 1306: zoo  boo, coo, doo, goo, hoo, loo, moo, noo, poo, roo, too, woo, zho, zoa, zol, zos

 1307: zos  bos, cos, dos, gos, hos, ios, kos, los, mos, nos, oos, pos, sos, wos, zas, zoa, zol, zoo

 1308: zuz  cuz, luz, ziz, zzz

 1309: zzz  ziz, zuz

Of course for a less open-minded word list the number of words and their linkages will be less as well. The four-letter set takes 24ms to compute a similar graph for its 5526 words, with linkages that look like this:

    0: aahs  aals, dahs, fahs, hahs, lahs, pahs, rahs, yahs

    1: aals  aahs, ails, alls, awls, bals, dals, gals, mals, pals, sals

    2: abac  abas

    3: abas  abac, abbs, abos, abys, agas, aias, akas, alas, amas, anas, auas, avas, obas

    4: abba  abbe, abbs, alba, arba

    5: abbe  abba, abbs, able, abye, albe

    6: abbs  abas, abba, abbe, abos, abys, albs, arbs, ebbs

    7: abed  abet, abid, aced, aged, ahed, aked, aped, ared, awed, axed

    8: abet  abed, abut, aret, ybet

    9: abid  abed, acid, amid, arid, avid

   10: able  abbe, ably, abye, arle, axle

   11: ably  able, agly, ally

   12: abos  abas, abbs, abys, ados, apos, avos, obos

   13: abri  

   14: abut  abet

   15: abye  abbe, able, abys

   16: abys  abas, abbs, abos, abye

   17: acai  

  :

 5509: zoic  

 5510: zols  cols, dols, hols, jols, mols, pols, sols, vols, zels, zoos

 5511: zona  bona, dona, mona, nona, zoea, zone, zonk

 5512: zone  bone, cone, done, fone, gone, hone, lone, none, pone, rone, sone, tone, zine, zona, zonk

 5513: zonk  bonk, conk, gonk, honk, konk, monk, ponk, tonk, wonk, zona, zone, zouk

 5514: zoom  boom, coom, doom, loom, room, soom, toom, zoon, zoos, zoot

 5515: zoon  boon, coon, doon, goon, hoon, loon, moon, noon, poon, roon, soon, toon, woon, zoom, zoos, zoot

 5516: zoos  boos, coos, doos, goos, loos, moos, poos, roos, woos, zhos, zols, zoom, zoon, zoot

 5517: zoot  boot, coot, foot, hoot, loot, moot, poot, root, soot, toot, woot, zoom, zoon, zoos

 5518: zori  gori, hori, nori, sori, tori, zari

 5519: zouk  bouk, douk, gouk, jouk, pouk, souk, touk, youk, zonk

 5520: zulu  lulu, pulu, sulu

 5521: zupa  oupa, pupa

 5522: zurf  curf, surf, turf, zarf

 5523: zyga  

 5524: zyme  cyme, lyme

 5525: zzzs  

Note the singletons abri, acai, zoic, zyga, and zzzs. In the Knuth Graphbase book, he termed them "aloof" since they are isolated and unlinked, and because 'aloof' itself is such a word. There are 60 of these in the 4-letter SCRABBLE word list:

abri, acai, adaw, adze, aesc, ahoy, ankh, asci, azym, djin, dzho, ecru, eevn, ekka, elhi, enuf, envy, epee, epha, erhu, euoi, evil, exam, expo, exul, gyny, huhu, hwyl, imam, isit, jehu, jeux, khor, kiwi, lwei, mwah, myxo, mzee, ngai, occy, odor, odso, ogam, ombu, omov, oppo, ossa, ovum, pfft, pruh, ughs, upta, vuln, waac, yebo, ygoe, yunx, zoic, zyga, zzzs

I'll do the solving part now, which is trivial given the above. Alas, as the number of pairs defining word ladders is large (30,531,150 for the four-letter case), and you want the count of all paths for each, the run time will not be in milliseconds. ;-)

Michael

P.S. If you want to see how to do this part quickly, here's a preview of the code. 

(http://play.golang.org/p/G6kHZEXpnY) My word lists came from (http://www.scrabble.org.au/words/)

 

--

You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Michael Jones]

Peter, your desire for ALL the solutions is an expensive one. With extensive word lists, it is possible to derive very long sequences. Here is an A-Z example...

aani ➤ arni ➤ arna ➤ anna ➤ anba ➤ abba ➤ abby ➤ abey ➤ abed ➤ abel ➤ abet ➤ adet ➤ adat ➤ adad ➤ adai ➤ adam ➤ adar ➤ adaw ➤ aday ➤ addy ➤ adda ➤ addu ➤ ardu ➤ ordu ➤ urdu ➤ urde ➤ unde ➤ ande ➤ aide ➤ aile ➤ able ➤ abie ➤ abir ➤ ahir ➤ amir ➤ amar ➤ afar ➤ agar ➤ agag ➤ agal ➤ agao ➤ agio ➤ agib ➤ adib ➤ adin ➤ adit ➤ alit ➤ alif ➤ alef ➤ alea ➤ alba ➤ albe ➤ alee ➤ agee ➤ aged ➤ agen ➤ ager ➤ acer ➤ acor ➤ amor ➤ amok ➤ amos ➤ amoy ➤ ahoy ➤ ahey ➤ ahem ➤ ahet ➤ chet ➤ chat ➤ bhat ➤ beat ➤ bead ➤ beak ➤ beal ➤ baal ➤ baar ➤ bear ➤ beam ➤ bean ➤ beau ➤ benu ➤ bena ➤ bana ➤ baba ➤ babe ➤ babi ➤ babs ➤ babu ➤ baby ➤ gaby ➤ gabe ➤ gabi ➤ gali ➤ bali ➤ bala ➤ baga ➤ bago ➤ baho ➤ baht ➤ baft ➤ baff ➤ biff ➤ buff ➤ bufo ➤ bubo ➤ bobo ➤ boba ➤ boga ➤ biga ➤ bigg ➤ bing ➤ bang ➤ banc ➤ band ➤ bald ➤ bale ➤ bade ➤ bake ➤ baka ➤ baku ➤ balu ➤ balk ➤ back ➤ bach ➤ bash ➤ base ➤ bane ➤ bani ➤ bank ➤ bant ➤ bait ➤ bail ➤ bain ➤ bais ➤ bass ➤ bask ➤ bark ➤ bara ➤ barb ➤ bard ➤ bare ➤ bari ➤ barm ➤ balm ➤ ball ➤ balt ➤ bart ➤ barn ➤ baru ➤ aaru ➤ maru ➤ maku ➤ haku ➤ habu ➤ habe ➤ hade ➤ cade ➤ cadi ➤ madi ➤ mabi ➤ maba ➤ caba ➤ caca ➤ cack ➤ calk ➤ calf ➤ call ➤ calm ➤ caam ➤ caum ➤ cauk ➤ cank ➤ cana ➤ cand ➤ caid ➤ cain ➤ cagn ➤ cage ➤ cake ➤ caky ➤ cany ➤ cane ➤ came ➤ camb ➤ camp ➤ calp ➤ calx ➤ falx ➤ fall ➤ fail ➤ dail ➤ dain ➤ dais ➤ dags ➤ dago ➤ dado ➤ dada ➤ dade ➤ dace ➤ dale ➤ dali ➤ dalk ➤ dalt ➤ daft ➤ daff ➤ doff ➤ coff ➤ coft ➤ coat ➤ boat ➤ blat ➤ blab ➤ blad ➤ blae ➤ blah ➤ blan ➤ alan ➤ akan ➤ akal ➤ anal ➤ anam ➤ anan ➤ anas ➤ abas ➤ aias ➤ alas ➤ alar ➤ ajar ➤ apar ➤ aper ➤ apex ➤ alex ➤ alec ➤ alem ➤ alen ➤ alin ➤ akin ➤ akia ➤ akha ➤ agha ➤ agla ➤ agra ➤ agre ➤ acre ➤ ache ➤ achy ➤ ashy ➤ asha ➤ asta ➤ acta ➤ acca ➤ alca ➤ alco ➤ also ➤ alto ➤ auto ➤ aute ➤ ante ➤ anne ➤ acne ➤ acle ➤ acme ➤ alme ➤ alle ➤ ally ➤ algy ➤ alga ➤ alfa ➤ alma ➤ alms ➤ arms ➤ army ➤ arry ➤ adry ➤ aery ➤ aero ➤ cero ➤ caro ➤ cara ➤ card ➤ care ➤ cape ➤ caph ➤ cafh ➤ cash ➤ case ➤ cask ➤ cark ➤ carl ➤ carp ➤ carr ➤ cart ➤ cant ➤ cast ➤ bast ➤ batt ➤ bate ➤ bath ➤ bats ➤ eats ➤ mats ➤ mans ➤ hans ➤ hals ➤ hala ➤ gala ➤ gaia ➤ gail ➤ gael ➤ gaen ➤ gaet ➤ gait ➤ gain ➤ fain ➤ fair ➤ gair ➤ gaur ➤ daur ➤ daer ➤ darr ➤ dard ➤ dand ➤ dana ➤ dama ➤ dame ➤ damn ➤ damp ➤ dump ➤ bump ➤ burp ➤ burd ➤ bird ➤ bind ➤ bend ➤ beid ➤ beld ➤ bela ➤ beja ➤ bema ➤ besa ➤ bess ➤ bees ➤ beef ➤ beek ➤ beck ➤ bick ➤ bice ➤ bide ➤ bike ➤ bikh ➤ binh ➤ bine ➤ bene ➤ beng ➤ beni ➤ benj ➤ benn ➤ been ➤ beer ➤ beet ➤ belt ➤ bell ➤ bely ➤ bevy ➤ levy ➤ levi ➤ hevi ➤ heii ➤ hein ➤ gein ➤ gean ➤ dean ➤ dead ➤ deaf ➤ deal ➤ dear ➤ deer ➤ deed ➤ deem ➤ deep ➤ jeep ➤ jeel ➤ feel ➤ feal ➤ feak ➤ fear ➤ feat ➤ felt ➤ celt ➤ cell ➤ ceil ➤ chil ➤ bhil ➤ boil ➤ boid ➤ boii ➤ bois ➤ boss ➤ bosc ➤ bose ➤ boce ➤ bock ➤ bolk ➤ bilk ➤ bile ➤ bill ➤ bilo ➤ bino ➤ beno ➤ bego ➤ bogo ➤ bodo ➤ bode ➤ body ➤ bogy ➤ bony ➤ bond ➤ bold ➤ bola ➤ bole ➤ boke ➤ bone ➤ bong ➤ boni ➤ bini ➤ bibi ➤ biri ➤ beri ➤ bere ➤ berg ➤ berm ➤ bern ➤ bert ➤ bent ➤ best ➤ bust ➤ bult ➤ bolt ➤ boll ➤ bolo ➤ boho ➤ bojo ➤ boro ➤ bora ➤ boma ➤ bomb ➤ boob ➤ blob ➤ bleb ➤ blee ➤ bleo ➤ blet ➤ blot ➤ bloc ➤ blow ➤ alow ➤ alod ➤ aloe ➤ alop ➤ asop ➤ atop ➤ atap ➤ atip ➤ atik ➤ atis ➤ acis ➤ acid ➤ amid ➤ amia ➤ amba ➤ ambo ➤ ammo ➤ amma ➤ amla ➤ amra ➤ aira ➤ aire ➤ airt ➤ aint ➤ aunt ➤ aune ➤ arne ➤ arse ➤ erse ➤ ease ➤ east ➤ fast ➤ fact ➤ face ➤ fack ➤ facy ➤ fady ➤ fade ➤ fage ➤ fake ➤ faky ➤ fany ➤ fana ➤ faba ➤ fama ➤ fame ➤ fare ➤ dare ➤ dane ➤ dang ➤ dani ➤ dank ➤ dark ➤ darg ➤ dari ➤ darn ➤ dart ➤ daut ➤ daub ➤ dabb ➤ dubb ➤ dubs ➤ dibs ➤ digs ➤ diss ➤ dess ➤ cess ➤ cass ➤ coss ➤ coos ➤ coof ➤ boof ➤ bood ➤ biod ➤ bion ➤ aion ➤ aeon ➤ agon ➤ anon ➤ anoa ➤ anda ➤ andi ➤ andy ➤ anay ➤ anat ➤ awat ➤ awag ➤ awan ➤ away ➤ awny ➤ awry ➤ airy ➤ miry ➤ mary ➤ cary ➤ cavy ➤ cava ➤ cave ➤ cate ➤ cete ➤ cede ➤ cepe ➤ cepa ➤ ceps ➤ reps ➤ rees ➤ kees ➤ keek ➤ geek ➤ geck ➤ deck ➤ desk ➤ desi ➤ dasi ➤ dash ➤ dish ➤ dich ➤ dice ➤ dick ➤ dink ➤ bink ➤ bint ➤ bitt ➤ bite ➤ biti ➤ jiti ➤ jati ➤ hati ➤ hagi ➤ hami ➤ hame ➤ game ➤ gade ➤ gage ➤ gale ➤ gall ➤ galp ➤ galt ➤ gant ➤ fant ➤ fand ➤ fang ➤ gang ➤ gane ➤ gape ➤ gapa ➤ gapo ➤ gapy ➤ gamy ➤ gamb ➤ gamp ➤ gasp ➤ gash ➤ fash ➤ fass ➤ fess ➤ feis ➤ feif ➤ feil ➤ fell ➤ dell ➤ dele ➤ delf ➤ pelf ➤ pele ➤ hele ➤ hale ➤ haje ➤ hake ➤ hako ➤ halo ➤ half ➤ haaf ➤ haab ➤ harb ➤ garb ➤ gara ➤ gare ➤ garn ➤ earn ➤ earl ➤ farl ➤ farm ➤ faro ➤ garo ➤ gary ➤ gazy ➤ dazy ➤ davy ➤ dave ➤ date ➤ data ➤ daza ➤ caza ➤ maza ➤ maga ➤ jaga ➤ jama ➤ jamb ➤ iamb ➤ lamb ➤ lama ➤ lame ➤ kame ➤ kale ➤ kala ➤ kafa ➤ kaha ➤ kahu ➤ kadu ➤ kagu ➤ kago ➤ kalo ➤ kali ➤ kaki ➤ kaka ➤ kana ➤ kang ➤ kans ➤ sans ➤ sand ➤ hand ➤ hank ➤ hack ➤ haik ➤ hail ➤ hain ➤ hair ➤ harr ➤ hard ➤ hare ➤ hark ➤ harl ➤ hall ➤ halt ➤ haet ➤ haec ➤ haem ➤ harm ➤ harn ➤ harp ➤ hart ➤ haft ➤ haff ➤ faff ➤ fuff ➤ cuff ➤ duff ➤ guff ➤ gaff ➤ goff ➤ goaf ➤ goad ➤ glad ➤ clad ➤ chad ➤ chaa ➤ chab ➤ chac ➤ chai ➤ chal ➤ cham ➤ chao ➤ chap ➤ char ➤ bhar ➤ boar ➤ boer ➤ bier ➤ bien ➤ birn ➤ birk ➤ birl ➤ birr ➤ burr ➤ buhr ➤ buhl ➤ bual ➤ bull ➤ bulb ➤ bulk ➤ buck ➤ bunk ➤ bonk ➤ book ➤ bool ➤ boom ➤ boon ➤ boor ➤ boot ➤ bort ➤ bord ➤ bore ➤ borg ➤ borh ➤ born ➤ bosn ➤ bosh ➤ bosk ➤ bouk ➤ boud ➤ baud ➤ baul ➤ baun ➤ bawn ➤ bawd ➤ bawl ➤ bowl ➤ bowk ➤ fowk ➤ folk ➤ colk ➤ coak ➤ coal ➤ coan ➤ clan ➤ clag ➤ clam ➤ clap ➤ clat ➤ claw ➤ blaw ➤ blas ➤ bias ➤ lias ➤ liar ➤ fiar ➤ fiat ➤ fiot ➤ fist ➤ cist ➤ cest ➤ cent ➤ dent ➤ debt ➤ debi ➤ demi ➤ deme ➤ demy ➤ defy ➤ deft ➤ heft ➤ heat ➤ geat ➤ geal ➤ gear ➤ glar ➤ glam ➤ flam ➤ flag ➤ flak ➤ flan ➤ flap ➤ flat ➤ flaw ➤ flax ➤ flay ➤ blay ➤ bray ➤ brab ➤ arab ➤ arad ➤ arar ➤ avar ➤ aval ➤ axal ➤ axel ➤ aiel ➤ kiel ➤ keel ➤ heel ➤ heal ➤ head ➤ heaf ➤ heap ➤ hear ➤ heer ➤ feer ➤ feed ➤ fend ➤ fent ➤ fest ➤ fust ➤ dust ➤ duct ➤ duck ➤ cuck ➤ cock ➤ coca ➤ coco ➤ codo ➤ coda ➤ code ➤ coke ➤ coky ➤ coly ➤ cola ➤ cold ➤ coed ➤ cled ➤ clee ➤ chee ➤ chef ➤ chen ➤ chew ➤ chaw ➤ chay ➤ clay ➤ cloy ➤ clod ➤ clog ➤ cleg ➤ clef ➤ clem ➤ clep ➤ clew ➤ clow ➤ chow ➤ chob ➤ chol ➤ chop ➤ chip ➤ chia ➤ chic ➤ chid ➤ chih ➤ chin ➤ chit ➤ chut ➤ bhut ➤ bout ➤ bott ➤ bota ➤ beta ➤ beth ➤ both ➤ bote ➤ bute ➤ bube ➤ aube ➤ auge ➤ augh ➤ hugh ➤ high ➤ hish ➤ fish ➤ fisc ➤ disc ➤ disa ➤ dika ➤ dike ➤ dime ➤ dine ➤ cine ➤ cise ➤ cite ➤ city ➤ mity ➤ maty ➤ katy ➤ kate ➤ fate ➤ faze ➤ baze ➤ daze ➤ doze ➤ coze ➤ cole ➤ coli ➤ coll ➤ coil ➤ coif ➤ coin ➤ coir ➤ coix ➤ coax ➤ crax ➤ crab ➤ crag ➤ brag ➤ brad ➤ brae ➤ bram ➤ bran ➤ brat ➤ braw ➤ brew ➤ bred ➤ ared ➤ area ➤ arba ➤ arca ➤ aria ➤ arid ➤ aril ➤ amil ➤ amic ➤ amin ➤ amen ➤ aten ➤ atef ➤ ates ➤ anes ➤ anew ➤ knew ➤ knee ➤ knet ➤ keet ➤ geet ➤ gelt ➤ geld ➤ gell ➤ gill ➤ dill ➤ dial ➤ dian ➤ dhan ➤ dhai ➤ dhak ➤ dhaw ➤ dhow ➤ drow ➤ arow ➤ brow ➤ brob ➤ brod ➤ brog ➤ brig ➤ brim ➤ brin ➤ brit ➤ bret ➤ bree ➤ brei ➤ brey ➤ grey ➤ gray ➤ dray ➤ drab ➤ doab ➤ doat ➤ doit ➤ dolt ➤ colt ➤ colp ➤ coop ➤ clop ➤ clip ➤ blip ➤ blup ➤ blub ➤ blue ➤ blur ➤ alur ➤ alum ➤ ahum ➤ ahom ➤ whom ➤ wham ➤ sham ➤ scam ➤ scab ➤ scad ➤ ecad ➤ egad ➤ sgad ➤ saad ➤ raad ➤ raid ➤ kaid ➤ kaik ➤ kail ➤ jail ➤ jain ➤ jann ➤ jane ➤ jade ➤ jady ➤ jawy ➤ jewy ➤ dewy ➤ deny ➤ dene ➤ dere ➤ cere ➤ cern ➤ corn ➤ conn ➤ cond ➤ cone ➤ come ➤ coma ➤ comb ➤ tomb ➤ toma ➤ goma ➤ gola ➤ dola ➤ dole ➤ dobe ➤ doby ➤ dogy ➤ doge ➤ dode ➤ dodd ➤ dodo ➤ dedo ➤ dido ➤ dilo ➤ filo ➤ fico ➤ fice ➤ fide ➤ fido ➤ fifo ➤ fife ➤ fike ➤ file ➤ fill ➤ film ➤ fils ➤ fels ➤ wels ➤ weld ➤ keld ➤ keid ➤ kend ➤ hend ➤ heed ➤ herd ➤ herb ➤ gerb ➤ germ ➤ derm ➤ dern ➤ dorn ➤ domn ➤ dome ➤ doke ➤ doko ➤ doto ➤ coto ➤ coho ➤ coyo ➤ moyo ➤ mayo ➤ kayo ➤ karo ➤ kari ➤ karl ➤ jarl ➤ jara ➤ java ➤ jiva ➤ diva ➤ deva ➤ depa ➤ dopa ➤ copa ➤ cope ➤ copr ➤ copt ➤ coot ➤ clot ➤ clit ➤ clio ➤ olio ➤ ohio ➤ ohia ➤ okia ➤ okie ➤ okee ➤ akee ➤ akey ➤ ikey ➤ skey ➤ skee ➤ shee ➤ ghee ➤ gheg ➤ gleg ➤ glee ➤ flee ➤ flea ➤ fled ➤ flem ➤ flet ➤ flew ➤ flex ➤ fley ➤ sley ➤ slay ➤ play ➤ plak ➤ peak ➤ leak ➤ lead ➤ leaf ➤ leah ➤ leal ➤ leam ➤ lean ➤ jean ➤ joan ➤ eoan ➤ evan ➤ even ➤ eben ➤ ebon ➤ elon ➤ elod ➤ plod ➤ pled ➤ peed ➤ leed ➤ leek ➤ leck ➤ feck ➤ ferk ➤ fern ➤ feru ➤ peru ➤ pelu ➤ pell ➤ hell ➤ helm ➤ help ➤ hemp ➤ heme ➤ feme ➤ fume ➤ fumy ➤ fury ➤ bury ➤ buoy ➤ busy ➤ bush ➤ budh ➤ buda ➤ buba ➤ buna ➤ bund ➤ bung ➤ bunt ➤ burt ➤ bure ➤ burg ➤ buri ➤ bugi ➤ sugi ➤ sufi ➤ safi ➤ safe ➤ rafe ➤ race ➤ lace ➤ lack ➤ jack ➤ jacu ➤ jocu ➤ joch ➤ jock ➤ dock ➤ dook ➤ cook ➤ conk ➤ cony ➤ copy ➤ cory ➤ cora ➤ cord ➤ core ➤ corf ➤ cork ➤ corm ➤ coom ➤ cool ➤ coon ➤ cion ➤ cuon ➤ curn ➤ burn ➤ burl ➤ buro ➤ duro ➤ dura ➤ aura ➤ akra ➤ akka ➤ atka ➤ atma ➤ atta ➤ anta ➤ ansa ➤ ansu ➤ ausu ➤ aulu ➤ aula ➤ auca ➤ yuca ➤ yuck ➤ huck ➤ heck ➤ hech ➤ lech ➤ lich ➤ lick ➤ hick ➤ hock ➤ honk ➤ hone ➤ done ➤ dong ➤ ding ➤ dint ➤ diet ➤ dieb ➤ diem ➤ dier ➤ doer ➤ doeg ➤ does ➤ dogs ➤ doss ➤ dosa ➤ dora ➤ dori ➤ doli ➤ doll ➤ dool ➤ diol ➤ dion ➤ doon ➤ donn ➤ dont ➤ dout ➤ douc ➤ doug ➤ doum ➤ doom ➤ doob ➤ door ➤ dour ➤ doup ➤ coup ➤ caup ➤ caul ➤ coul ➤ aoul ➤ foul ➤ foal ➤ foam ➤ form ➤ dorm ➤ dorp ➤ dory ➤ domy ➤ doty ➤ dote ➤ cote ➤ coth ➤ cosh ➤ cost ➤ cosy ➤ cowy ➤ cowl ➤ dowl ➤ dowd ➤ dowf ➤ down ➤ dawn ➤ fawn ➤ faon ➤ faun ➤ foun ➤ boun ➤ noun ➤ noon ➤ goon ➤ gaon ➤ gaol ➤ gaul ➤ gaub ➤ gaud ➤ daud ➤ laud ➤ laid ➤ laic ➤ lain ➤ lair ➤ laur ➤ laun ➤ gaun ➤ gaum ➤ gaup ➤ gaus ➤ gaut ➤ gast ➤ gest ➤ gent ➤ gena ➤ gene ➤ gens ➤ genu ➤ menu ➤ mend ➤ lend ➤ land ➤ lana ➤ lane ➤ lade ➤ lady ➤ lacy ➤ laky ➤ lake ➤ jake ➤ jako ➤ jato ➤ pato ➤ paco ➤ maco ➤ mace ➤ mack ➤ mank ➤ jank ➤ jauk ➤ jaun ➤ jaup ➤ paup ➤ paip ➤ paik ➤ naik ➤ nabk ➤ nabs ➤ nabu ➤ napu ➤ hapu ➤ hapi ➤ hopi ➤ hope ➤ dope ➤ dose ➤ dove ➤ cove ➤ cive ➤ dive ➤ dire ➤ dird ➤ dirk ➤ dirl ➤ dirt ➤ girt ➤ gift ➤ gilt ➤ gila ➤ gild ➤ gied ➤ gien ➤ girn ➤ firn ➤ finn ➤ find ➤ fine ➤ fink ➤ firk ➤ fire ➤ firm ➤ yirm ➤ yarm ➤ marm ➤ maam ➤ maim ➤ maia ➤ maha ➤ mahi ➤ magi ➤ mage ➤ made ➤ mado ➤ majo ➤ maja ➤ mala ➤ male ➤ make ➤ maki ➤ mako ➤ malo ➤ lalo ➤ lall ➤ lill ➤ hill ➤ hilt ➤ hint ➤ hant ➤ hano ➤ mano ➤ mamo ➤ mapo ➤ maro ➤ mara ➤ mana ➤ mand ➤ maid ➤ mail ➤ main ➤ mann ➤ mane ➤ mang ➤ mani ➤ mali ➤ mall ➤ malm ➤ malt ➤ mant ➤ lant ➤ laet ➤ last ➤ lasa ➤ kasa ➤ kapa ➤ kapp ➤ lapp ➤ lamp ➤ limp ➤ gimp ➤ gump ➤ cump ➤ cusp ➤ cush ➤ cusk ➤ busk ➤ buss ➤ cuss ➤ fuss ➤ fusc ➤ fuse ➤ fise ➤ five ➤ give ➤ gave ➤ eave ➤ have ➤ hate ➤ gate ➤ gata ➤ geta ➤ keta ➤ keto ➤ keno ➤ kenn ➤ keen ➤ keep ➤ kelp ➤ kele ➤ kelk ➤ keck ➤ kick ➤ kink ➤ gink ➤ ging ➤ gong ➤ gona ➤ gond ➤ gold ➤ fold ➤ fole ➤ fore ➤ fora ➤ forb ➤ ford ➤ food ➤ feod ➤ feud ➤ foud ➤ four ➤ hour ➤ hoar ➤ hoer ➤ goer ➤ goel ➤ goal ➤ goan ➤ ghan ➤ ghat ➤ gnat ➤ gnar ➤ gnaw ➤ snaw ➤ scaw ➤ scan ➤ saan ➤ sain ➤ nain ➤ naid ➤ naif ➤ naig ➤ nail ➤ nael ➤ noel ➤ joel ➤ joey ➤ joky ➤ joke ➤ jose ➤ hose ➤ hohe ➤ hehe ➤ here ➤ herl ➤ hern ➤ hero ➤ hiro ➤ giro ➤ gilo ➤ golo ➤ gobo ➤ gobi ➤ goby ➤ gony ➤ gone ➤ gode ➤ gore ➤ gora ➤ gorb ➤ gory ➤ hory ➤ holy ➤ hold ➤ hole ➤ holl ➤ goll ➤ golf ➤ goli ➤ koli ➤ kobi ➤ kobu ➤ koku ➤ kiku ➤ kike ➤ hike ➤ hide ➤ hipe ➤ hire ➤ hive ➤ hove ➤ gove ➤ gote ➤ goth ➤ gith ➤ gish ➤ gist ➤ gust ➤ gurt ➤ curt ➤ cult ➤ cull ➤ culm ➤ kulm ➤ kula ➤ gula ➤ gufa ➤ guha ➤ guhr ➤ duhr ➤ duer ➤ duel ➤ dual ➤ duad ➤ dyad ➤ dyak ➤ dyas ➤ eyas ➤ eyah ➤ ayah ➤ kyah ➤ kyar ➤ khar ➤ khan ➤ khat ➤ khet ➤ khot ➤ knot ➤ knit ➤ knut ➤ knub ➤ knab ➤ knag ➤ knap ➤ knar ➤ knur ➤ snur ➤ saur ➤ sadr ➤ sade ➤ sabe ➤ saba ➤ paba ➤ paca ➤ pace ➤ nace ➤ nach ➤ each ➤ etch ➤ itch ➤ inch ➤ inca ➤ inga ➤ inia ➤ ilia ➤ elia ➤ ella ➤ olla ➤ olea ➤ oxea ➤ oxen ➤ omen ➤ oman ➤ oban ➤ iban ➤ ibad ➤ ibid ➤ ibis ➤ iris ➤ cris ➤ crib ➤ cric ➤ crig ➤ crin ➤ cran ➤ cram ➤ crap ➤ craw ➤ crew ➤ crea ➤ cree ➤ crex ➤ crux ➤ crum ➤ arum ➤ drum ➤ dram ➤ drag ➤ drat ➤ draw ➤ drew ➤ dree ➤ dreg ➤ drug ➤ drub ➤ drib ➤ drip ➤ drop ➤ crop ➤ croc ➤ crom ➤ crow ➤ croy ➤ troy ➤ tray ➤ fray ➤ frab ➤ frae ➤ fram ➤ frap ➤ frat ➤ fret ➤ fred ➤ free ➤ froe ➤ floe ➤ flob ➤ floc ➤ flog ➤ flop ➤ flip ➤ flit ➤ flix ➤ flux ➤ flub ➤ club ➤ chub ➤ chud ➤ chug ➤ chum ➤ chun ➤ shun ➤ scun ➤ scud ➤ scug ➤ scog ➤ scob ➤ scot ➤ scat ➤ scap ➤ scar ➤ scur ➤ scum ➤ saum ➤ saim ➤ naim ➤ naam ➤ noam ➤ loam ➤ load ➤ loaf ➤ loan ➤ loin ➤ hoin ➤ hohn ➤ hoon ➤ hood ➤ good ➤ goof ➤ gook ➤ gool ➤ fool ➤ foil ➤ fowl ➤ gowl ➤ gowf ➤ gowk ➤ gawk ➤ cawk ➤ hawk ➤ hask ➤ hash ➤ hasp ➤ rasp ➤ ramp ➤ rama ➤ nama ➤ naga ➤ naja ➤ nana ➤ nane ➤ nake ➤ nako ➤ naio ➤ nair ➤ nais ➤ naos ➤ taos ➤ taps ➤ tapa ➤ napa ➤ nape ➤ jape ➤ jupe ➤ dupe ➤ dude ➤ duke ➤ cuke ➤ cube ➤ cuba ➤ cuna ➤ cuya ➤ puya ➤ puja ➤ puka ➤ pika ➤ pica ➤ mica ➤ mice ➤ mick ➤ mico ➤ miao ➤ mian ➤ mean ➤ mead ➤ meak ➤ meal ➤ meat ➤ leat ➤ leap ➤ lear ➤ leer ➤ jeer ➤ neer ➤ need ➤ meed ➤ meek ➤ meet ➤ leet ➤ leep ➤ lees ➤ lens ➤ lena ➤ leda ➤ lede ➤ lene ➤ leno ➤ lent ➤ hent ➤ hest ➤ hewt ➤ hewn ➤ sewn ➤ sawn ➤ gawn ➤ gown ➤ lown ➤ lawn ➤ lawk ➤ lank ➤ lanx ➤ lynx ➤ jynx ➤ jinx ➤ jina ➤ jing ➤ hing ➤ hind ➤ kind ➤ kina ➤ king ➤ kino ➤ kiho ➤ kilo ➤ kill ➤ jill ➤ jell ➤ jerl ➤ jerk ➤ jerm ➤ jert ➤ jest ➤ jess ➤ jass ➤ joss ➤ josh ➤ fosh ➤ gosh ➤ gush ➤ dush ➤ dusk ➤ disk ➤ lisk ➤ lask ➤ lark ➤ lard ➤ lari ➤ lars ➤ lass ➤ lash ➤ lasi ➤ nasi ➤ nash ➤ mash ➤ magh ➤ math ➤ hath ➤ hatt ➤ matt ➤ mart ➤ marc ➤ mare ➤ mari ➤ mark ➤ marl ➤ mars ➤ mass ➤ masa ➤ mask ➤ mast ➤ masu ➤ tasu ➤ tabu ➤ taku ➤ raku ➤ rake ➤ rage ➤ page ➤ paga ➤ paha ➤ pahi ➤ paho ➤ pavo ➤ pave ➤ lave ➤ late ➤ lata ➤ lath ➤ kath ➤ kith ➤ kish ➤ kiss ➤ hiss ➤ hisn ➤ hist ➤ host ➤ hoit ➤ holt ➤ hoot ➤ foot ➤ flot ➤ flow ➤ frow ➤ frog ➤ frig ➤ frib ➤ frim ➤ frit ➤ frot ➤ brot ➤ broo ➤ kroo ➤ proo ➤ phoo ➤ phoh ➤ phon ➤ paon ➤ pain ➤ pail ➤ paal ➤ paar ➤ pair ➤ pais ➤ pass ➤ pash ➤ pasi ➤ pali ➤ pala ➤ pale ➤ pall ➤ palm ➤ palp ➤ palt ➤ pact ➤ pack ➤ pank ➤ pand ➤ pane ➤ pang ➤ pani ➤ pant ➤ nant ➤ nast ➤ natt ➤ nate ➤ mate ➤ maze ➤ gaze ➤ gazi ➤ kazi ➤ kavi ➤ kava ➤ kiva ➤ riva ➤ rima ➤ hima ➤ himp ➤ hump ➤ huma ➤ duma ➤ dumb ➤ numb ➤ nimb ➤ limb ➤ lima ➤ lida ➤ lide ➤ life ➤ lifo ➤ lift ➤ left ➤ lest ➤ less ➤ liss ➤ lisa ➤ lija ➤ lila ➤ lile ➤ like ➤ lime ➤ limn ➤ lien ➤ lied ➤ lief ➤ lier ➤ kier ➤ pier ➤ peer ➤ pear ➤ peag ➤ peai ➤ peal ➤ neal ➤ neap ➤ neat ➤ neet ➤ neem ➤ neep ➤ peep ➤ peek ➤ peck ➤ neck ➤ nick ➤ nice ➤ nici ➤ nidi ➤ nide ➤ mide ➤ mede ➤ mele ➤ mela ➤ meld ➤ mell ➤ kell ➤ kelt ➤ kent ➤ kept ➤ kepi ➤ kopi ➤ komi ➤ kome ➤ home ➤ homo ➤ hobo ➤ jobo ➤ jodo ➤ judo ➤ jude ➤ gude ➤ gule ➤ gulf ➤ gull ➤ dull ➤ dult ➤ duet ➤ duit ➤ dunt ➤ dune ➤ dung ➤ dunk ➤ duns ➤ duny ➤ duly ➤ july ➤ judy ➤ jury ➤ jura ➤ hura ➤ hora ➤ hoga ➤ hova ➤ hoya ➤ haya ➤ baya ➤ maya ➤ raya ➤ rada ➤ raga ➤ raia ➤ raif ➤ raff ➤ raft ➤ rant ➤ rana ➤ raja ➤ rasa ➤ rase ➤ rame ➤ name ➤ nave ➤ navy ➤ nary ➤ nard ➤ nark ➤ narr ➤ parr ➤ para ➤ papa ➤ pape ➤ pare ➤ pard ➤ pari ➤ park ➤ part ➤ past ➤ oast ➤ oust ➤ just ➤ junt ➤ funt ➤ font ➤ fono ➤ fogo ➤ fogy ➤ foxy ➤ boxy ➤ coxy ➤ coxa ➤ doxa ➤ doxy ➤ dixy ➤ mixy ➤ miny ➤ liny ➤ lily ➤ lilt ➤ jilt ➤ jolt ➤ joll ➤ jowl ➤ howl ➤ howe ➤ howk ➤ hook ➤ hoof ➤ hoop ➤ goop ➤ glop ➤ glom ➤ glor ➤ glow ➤ gloy ➤ ploy ➤ plop ➤ klop ➤ klip ➤ slip ➤ saip ➤ saic ➤ said ➤ sail ➤ rail ➤ rain ➤ rais ➤ reis ➤ reid ➤ read ➤ reak ➤ real ➤ ream ➤ reap ➤ rear ➤ roar ➤ road ➤ roam ➤ roan ➤ moan ➤ moat ➤ goat ➤ gout ➤ glut ➤ glub ➤ glib ➤ glia ➤ glis ➤ gris ➤ grid ➤ grad ➤ grab ➤ gram ➤ grat ➤ grit ➤ grig ➤ greg ➤ gree ➤ grew ➤ grow ➤ grog ➤ gros ➤ eros ➤ enos ➤ enol ➤ enow ➤ know ➤ knob ➤ knop ➤ snop ➤ shop ➤ shap ➤ shab ➤ shad ➤ shag ➤ shah ➤ seah ➤ seak ➤ seal ➤ seam ➤ sean ➤ pean ➤ peat ➤ pelt ➤ melt ➤ ment ➤ meng ➤ meny ➤ many ➤ manx ➤ maux ➤ maud ➤ maul ➤ haul ➤ paul ➤ paut ➤ naut ➤ nawt ➤ newt ➤ nest ➤ nese ➤ mese ➤ mere ➤ merk ➤ merl ➤ mero ➤ meio ➤ mein ➤ rein ➤ reen ➤ peen ➤ peel ➤ reel ➤ reed ➤ redd ➤ rede ➤ reve ➤ neve ➤ nete ➤ jete ➤ jute ➤ cute ➤ cure ➤ curb ➤ curd ➤ curl ➤ curr ➤ cuir ➤ muir ➤ muid ➤ mudd ➤ mund ➤ fund ➤ funk ➤ fulk ➤ full ➤ fuel ➤ furl ➤ gurl ➤ girl ➤ gird ➤ girr ➤ gurr ➤ guar ➤ guan ➤ guao ➤ gulo ➤ gulp ➤ pulp ➤ pule ➤ jule ➤ jube ➤ jibe ➤ gibe ➤ kibe ➤ kipe ➤ kite ➤ dite ➤ dita ➤ pita ➤ pata ➤ pate ➤ path ➤ oath ➤ oaty ➤ oaky ➤ oary ➤ vary ➤ vady ➤ vade ➤ tade ➤ take ➤ sake ➤ sage ➤ saga ➤ sago ➤ saco ➤ sack ➤ rack ➤ rach ➤ rakh ➤ raki ➤ rabi ➤ rami ➤ rani ➤ rand ➤ rane ➤ rang ➤ rank ➤ rann ➤ raun ➤ maun ➤ taun ➤ taen ➤ tael ➤ taal ➤ taar ➤ tahr ➤ taha ➤ tala ➤ talc ➤ tald ➤ tale ➤ sale ➤ salm ➤ salp ➤ salt ➤ saft ➤ sant ➤ sane ➤ same ➤ samh ➤ sadh ➤ sado ➤ saho ➤ sahh ➤ sash ➤ rash ➤ rath ➤ rata ➤ rate ➤ rape ➤ rare ➤ rave ➤ raze ➤ haze ➤ hazy ➤ lazy ➤ laze ➤ naze ➤ nazi ➤ nozi ➤ nodi ➤ node ➤ lode ➤ lobe ➤ lobo ➤ loco ➤ loca ➤ loch ➤ koch ➤ koph ➤ moph ➤ mope ➤ lope ➤ loge ➤ logy ➤ lory ➤ kory ➤ kora ➤ koda ➤ kola ➤ kolo ➤ koko ➤ koso ➤ koto ➤ kota ➤ iota ➤ iowa ➤ lowa ➤ loka ➤ loke ➤ lone ➤ ione ➤ ioni ➤ joni ➤ jong ➤ hong ➤ hung ➤ hunh ➤ hunk ➤ gunk ➤ guna ➤ gunj ➤ munj ➤ mung ➤ kung ➤ kunk ➤ junk ➤ jink ➤ jinn ➤ linn ➤ liin ➤ lion ➤ leon ➤ geon ➤ neon ➤ peon ➤ pern ➤ kern ➤ kerf ➤ serf ➤ self ➤ sele ➤ sell ➤ nell ➤ neil ➤ neif ➤ leif ➤ reif ➤ reef ➤ reek ➤ reck ➤ rect ➤ reet ➤ reem ➤ reim ➤ reit ➤ reft ➤ rent ➤ pent ➤ pend ➤ penk ➤ perk ➤ peri ➤ neri ➤ neti ➤ neth ➤ nesh ➤ mesh ➤ mesa ➤ meso ➤ memo ➤ momo ➤ mogo ➤ gogo ➤ pogo ➤ poco ➤ pico ➤ pice ➤ pici ➤ pick ➤ pict ➤ piet ➤ pied ➤ pien ➤ mien ➤ miek ➤ milk ➤ mila ➤ mild ➤ mile ➤ mike ➤ miki ➤ kiki ➤ kiri ➤ jiri ➤ juri ➤ jure ➤ dure ➤ durn ➤ turn ➤ tarn ➤ tain ➤ tail ➤ tait ➤ tact ➤ tach ➤ tack ➤ talk ➤ tali ➤ tall ➤ tell ➤ teal ➤ tead ➤ teak ➤ team ➤ tean ➤ teap ➤ tear ➤ sear ➤ seat ➤ sect ➤ sech ➤ pech ➤ tech ➤ teca ➤ teck ➤ seck ➤ seek ➤ seed ➤ seel ➤ seem ➤ seen ➤ seep ➤ seer ➤ sher ➤ shea ➤ rhea ➤ thea ➤ theb ➤ thee ➤ them ➤ teem ➤ teel ➤ teen ➤ teer ➤ teet ➤ teat ➤ telt ➤ selt ➤ seit ➤ seid ➤ send ➤ rend ➤ renk ➤ renu ➤ zenu ➤ zend ➤ tend ➤ teng ➤ tang ➤ sang ➤ sank ➤ sark ➤ sara ➤ saka ➤ saki ➤ sari ➤ sard ➤ sare ➤ sart ➤ saut ➤ sauf ➤ saul ➤ raul ➤ waul ➤ wail ➤ vail ➤ vain ➤ vair ➤ sair ➤ stir ➤ star ➤ soar ➤ soak ➤ siak ➤ sial ➤ pial ➤ pian ➤ pirn ➤ kirn ➤ kiln ➤ kilp ➤ kilt ➤ kist ➤ list ➤ lint ➤ lina ➤ line ➤ ling ➤ link ➤ lino ➤ mino ➤ milo ➤ mill ➤ milt ➤ mint ➤ mina ➤ mima ➤ mime ➤ mimi ➤ mimp ➤ jimp ➤ jump ➤ lump ➤ mump ➤ pump ➤ pimp ➤ pima ➤ pina ➤ nina ➤ nine ➤ mine ➤ mind ➤ ming ➤ mink ➤ mirk ➤ kirk ➤ yirk ➤ yark ➤ wark ➤ wack ➤ wace ➤ wabe ➤ wabi ➤ wadi ➤ wade ➤ wage ➤ vage ➤ vale ➤ vali ➤ vall ➤ vell ➤ veal ➤ veil ➤ teil ➤ toil ➤ koil ➤ moil ➤ moio ➤ moho ➤ moha ➤ mohr ➤ moor ➤ mood ➤ lood ➤ loof ➤ look ➤ lock ➤ loci ➤ foci ➤ fuci ➤ fuji ➤ suji ➤ susi ➤ sisi ➤ sidi ➤ sida ➤ side ➤ ride ➤ ribe ➤ rice ➤ rich ➤ rick ➤ rikk ➤ rink ➤ pink ➤ pind ➤ pine ➤ pike ➤ piki ➤ piky ➤ pily ➤ oily ➤ only ➤ inly ➤ inby ➤ inbe ➤ inde ➤ indy ➤ ondy ➤ undy ➤ undo ➤ unco ➤ unca ➤ onca ➤ orca ➤ orna ➤ urna ➤ ulna ➤ ulla ➤ ulua ➤ ulva ➤ urva ➤ urea ➤ uria ➤ eria ➤ eric ➤ erie ➤ erne ➤ esne ➤ eyne ➤ dyne ➤ dyce ➤ dyke ➤ cyke ➤ cyme ➤ ryme ➤ rime ➤ oime ➤ sime ➤ seme ➤ semi ➤ remi ➤ reki ➤ weki ➤ weka ➤ waka ➤ wake ➤ wakf ➤ waff ➤ wafd ➤ waft ➤ taft ➤ takt ➤ taky ➤ tavy ➤ pavy ➤ paly ➤ paty ➤ patu ➤ tatu ➤ tapu ➤ tape ➤ tame ➤ tama ➤ tamp ➤ samp ➤ simp ➤ sima ➤ sika ➤ sike ➤ sice ➤ sick ➤ silk ➤ sile ➤ nile ➤ nife ➤ rife ➤ riff ➤ jiff ➤ jeff ➤ teff ➤ tiff ➤ miff ➤ moff ➤ koff ➤ koft ➤ loft ➤ loot ➤ loom ➤ joom ➤ joon ➤ loon ➤ loop ➤ loup ➤ goup ➤ moup ➤ moop ➤ mool ➤ moll ➤ loll ➤ lola ➤ lolo ➤ loro ➤ lora ➤ lira ➤ lipa ➤ lepa ➤ nepa ➤ nema ➤ noma ➤ loma ➤ lota ➤ jota ➤ jova ➤ jove ➤ jive ➤ live ➤ lire ➤ lise ➤ lish ➤ lisp ➤ risp ➤ resp ➤ repp ➤ ropp ➤ romp ➤ pomp ➤ pome ➤ mome ➤ mode ➤ moke ➤ moki ➤ moko ➤ mojo ➤ mono ➤ mona ➤ kona ➤ nona ➤ none ➤ mone ➤ mole ➤ mola ➤ mold ➤ moed ➤ moud ➤ loud ➤ leud ➤ leuk ➤ louk ➤ jouk ➤ joug ➤ toug ➤ thug ➤ shug ➤ shog ➤ shoa ➤ shod ➤ shed ➤ shel ➤ shen ➤ shan ➤ nhan ➤ than ➤ thad ➤ thai ➤ shai ➤ shat ➤ shaw ➤ shay ➤ spay ➤ spad ➤ slad ➤ slab ➤ slae ➤ slag ➤ skag ➤ skal ➤ skat ➤ skaw ➤ skew ➤ skef ➤ skeg ➤ skel ➤ sken ➤ skeo ➤ skep ➤ sker ➤ eker ➤ ever ➤ aver ➤ over ➤ ofer ➤ omer ➤ imer ➤ iter ➤ itea ➤ idea ➤ edea ➤ edda ➤ eddo ➤ eddy ➤ edgy ➤ edge ➤ euge ➤ huge ➤ hugo ➤ huso ➤ huse ➤ huke ➤ hume ➤ hure ➤ hurf ➤ huff ➤ luff ➤ muff ➤ puff ➤ ruff ➤ suff ➤ surf ➤ sura ➤ lura ➤ luba ➤ juba ➤ juga ➤ juha ➤ juza ➤ tuza ➤ tiza ➤ tina ➤ sina ➤ sind ➤ rind ➤ rine ➤ rile ➤ pile ➤ pili ➤ pill ➤ pirl ➤ piro ➤ miro ➤ mira ➤ mird ➤ mire ➤ mise ➤ miss ➤ mess ➤ moss ➤ loss ➤ lois ➤ loir ➤ lour ➤ lout ➤ lost ➤ lose ➤ lore ➤ kore ➤ kori ➤ kuri ➤ kuei ➤ kuki ➤ kuku ➤ kudu ➤ pudu ➤ puku ➤ puke ➤ juke ➤ june ➤ juno ➤ puno ➤ pino ➤ ping ➤ ning ➤ ring ➤ rong ➤ long ➤ lonk ➤ monk ➤ mock ➤ muck ➤ juck ➤ luck ➤ luce ➤ lube ➤ luge ➤ luke ➤ lune ➤ luna ➤ lula ➤ hula ➤ huia ➤ hupa ➤ pupa ➤ pipa ➤ nipa ➤ ripa ➤ ripe ➤ pipe ➤ pipi ➤ pipy ➤ piny ➤ pint ➤ oint ➤ oont ➤ mont ➤ moit ➤ molt ➤ moly ➤ moky ➤ poky ➤ pogy ➤ poly ➤ pole ➤ poke ➤ pone ➤ pond ➤ pong ➤ mong ➤ morg ➤ mora ➤ more ➤ morn ➤ horn ➤ lorn ➤ lord ➤ lori ➤ lors ➤ lots ➤ lote ➤ lete ➤ leto ➤ lett ➤ sett ➤ sent ➤ sept ➤ seps ➤ sess ➤ ness ➤ pess ➤ pesa ➤ peba ➤ peda ➤ pega ➤ vega ➤ veda ➤ teda ➤ tema ➤ temp ➤ terp ➤ tarp ➤ tara ➤ tana ➤ tane ➤ tanh ➤ tank ➤ tano ➤ taro ➤ tare ➤ tari ➤ tarr ➤ tars ➤ tart ➤ taut ➤ taum ➤ taur ➤ tour ➤ pour ➤ poor ➤ pooa ➤ poof ➤ pooh ➤ pook ➤ nook ➤ nock ➤ pock ➤ polk ➤ poll ➤ noll ➤ noil ➤ poil ➤ phil ➤ phit ➤ phiz ➤ whiz ➤ whid ➤ whig ➤ thig ➤ thin ➤ shin ➤ shih ➤ shik ➤ shim ➤ ship ➤ shiv ➤ skiv ➤ skid ➤ skil ➤ skim ➤ skin ➤ skip ➤ skit ➤ slit ➤ slat ➤ plat ➤ plan ➤ klan ➤ klam ➤ olam ➤ olaf ➤ olax ➤ odax ➤ odal ➤ opal ➤ oral ➤ eral ➤ kral ➤ krag ➤ kran ➤ iran ➤ iron ➤ tron ➤ thon ➤ then ➤ theo ➤ thew ➤ phew ➤ plew ➤ llew ➤ lleu ➤ lieu ➤ limu ➤ limy ➤ rimy ➤ rixy ➤ pixy ➤ pity ➤ pith ➤ lith ➤ lite ➤ lute ➤ fute ➤ fuye ➤ fuze ➤ fuzz ➤ buzz ➤ bizz ➤ fizz ➤ gizz ➤ hizz ➤ sizz ➤ size ➤ pize ➤ pise ➤ pish ➤ pisk ➤ piso ➤ peso ➤ peho ➤ pepo ➤ peto ➤ pete ➤ mete ➤ meta ➤ muta ➤ muga ➤ mura ➤ mure ➤ lure ➤ lupe ➤ nupe ➤ nope ➤ nome ➤ nose ➤ mose ➤ most ➤ mist ➤ mitt ➤ mite ➤ mote ➤ moth ➤ mott ➤ moot ➤ moon ➤ mown ➤ mowt ➤ mort ➤ fort ➤ fork ➤ pork ➤ pore ➤ pope ➤ pose ➤ posh ➤ losh ➤ lush ➤ hush ➤ husk ➤ hulk ➤ hull ➤ hulu ➤ lulu ➤ lull ➤ mull ➤ mule ➤ mulk ➤ mult ➤ munt ➤ hunt ➤ hurt ➤ hurl ➤ hurr ➤ huer ➤ hued ➤ huey ➤ quey ➤ quay ➤ quab ➤ quad ➤ quag ➤ quan ➤ juan ➤ kuan ➤ kuar ➤ quar ➤ quat ➤ quet ➤ quit ➤ quib ➤ quid ➤ quin ➤ ruin ➤ ruen ➤ ruer ➤ rier ➤ roer ➤ roed ➤ rodd ➤ rode ➤ robe ➤ roke ➤ roka ➤ roky ➤ roey ➤ ropy ➤ rope ➤ role ➤ rolf ➤ roll ➤ rill ➤ rial ➤ vial ➤ vill ➤ sill ➤ silo ➤ silt ➤ sift ➤ rift ➤ riot ➤ rist ➤ pist ➤ pest ➤ pert ➤ perm ➤ term ➤ tera ➤ sera ➤ seba ➤ seta ➤ seth ➤ sith ➤ sigh ➤ nigh ➤ yigh ➤ yogh ➤ yoga ➤ soga ➤ soda ➤ sody ➤ sidy ➤ tidy ➤ tide ➤ tice ➤ tick ➤ tink ➤ sink ➤ sine ➤ sife ➤ sipe ➤ sire ➤ sere ➤ qere ➤ qeri ➤ seri ➤ serb ➤ sero ➤ sert ➤ sext ➤ next ➤ text ➤ tent ➤ test ➤ rest ➤ resh ➤ rush ➤ mush ➤ much ➤ muth ➤ mute ➤ muse ➤ musa ➤ kusa ➤ kuba ➤ nuba ➤ nuda ➤ nudd ➤ nude ➤ nuke ➤ tuke ➤ toke ➤ soke ➤ soce ➤ sock ➤ rock ➤ rook ➤ rood ➤ roid ➤ ooid ➤ olid ➤ slid ➤ sled ➤ sleb ➤ pleb ➤ plea ➤ plex ➤ ilex ➤ ibex ➤ obex ➤ obey ➤ ovey ➤ oven ➤ open ➤ owen ➤ ower ➤ ewer ➤ eyer ➤ eyed ➤ syed ➤ sned ➤ sneb ➤ snab ➤ snag ➤ snap ➤ slap ➤ plap ➤ plup ➤ plud ➤ plug ➤ glug ➤ glue ➤ clue ➤ coue ➤ roue ➤ rome ➤ rone ➤ rond ➤ roud ➤ roub ➤ roun ➤ roon ➤ poon ➤ pool ➤ poop ➤ noop ➤ noup ➤ nous ➤ nobs ➤ pobs ➤ poss ➤ piss ➤ puss ➤ guss ➤ huss ➤ muss ➤ musk ➤ lusk ➤ lurk ➤ gurk ➤ guru ➤ puru ➤ pulu ➤ puli ➤ pulk ➤ puck ➤ puce ➤ pume ➤ puma ➤ numa ➤ yuma ➤ yuga ➤ ruga ➤ rupa ➤ rusa ➤ rosa ➤ rose ➤ rise ➤ risk ➤ riss ➤ ross ➤ rosy ➤ nosy ➤ nowy ➤ lowy ➤ rowy ➤ rory ➤ pory ➤ pony ➤ pont ➤ poet ➤ polt ➤ polo ➤ nolo ➤ novo ➤ nova ➤ nora ➤ nori ➤ norm ➤ norn ➤ sorn ➤ soon ➤ sion ➤ siol ➤ sool ➤ rool ➤ roil ➤ roit ➤ root ➤ poot ➤ phot ➤ phos ➤ thos ➤ this ➤ thio ➤ thir ➤ khir ➤ whir ➤ weir ➤ wear ➤ waar ➤ waac ➤ waag ➤ waeg ➤ waer ➤ waur ➤ wauf ➤ waif ➤ waik ➤ wain ➤ wait ➤ walt ➤ wale ➤ wali ➤ walk ➤ wall ➤ warl ➤ ward ➤ wand ➤ wane ➤ vane ➤ vang ➤ uang ➤ wang ➤ want ➤ wany ➤ waky ➤ wary ➤ ware ➤ vare ➤ vara ➤ vari ➤ veri ➤ teri ➤ teli ➤ tele ➤ tete ➤ tate ➤ sate ➤ save ➤ tave ➤ wave ➤ wame ➤ wamp ➤ vamp ➤ yamp ➤ yapp ➤ wapp ➤ warp ➤ warf ➤ warm ➤ warn ➤ wart ➤ wast ➤ vast ➤ vasa ➤ sasa ➤ sapa ➤ saya ➤ soya ➤ sofa ➤ soft ➤ soot ➤ shot ➤ shoe ➤ shoo ➤ shoq ➤ shor ➤ shou ➤ chou ➤ thou ➤ thob ➤ thof ➤ thoo ➤ thow ➤ jhow ➤ show ➤ scow ➤ slow ➤ plow ➤ plot ➤ ilot ➤ slot ➤ slob ➤ slod ➤ sloe ➤ slee ➤ slew ➤ slaw ➤ slam ➤ siam ➤ sium ➤ slum ➤ glum ➤ geum ➤ grum ➤ grim ➤ grin ➤ grip ➤ trip ➤ trap ➤ trag ➤ toag ➤ toad ➤ toat ➤ that ➤ thar ➤ tiar ➤ tiam ➤ tiao ➤ timo ➤ time ➤ tige ➤ tile ➤ till ➤ tilt ➤ tift ➤ tint ➤ tind ➤ tied ➤ tien ➤ tier ➤ sier ➤ suer ➤ suet ➤ spet ➤ spat ➤ spae ➤ spak ➤ span ➤ spar ➤ spor ➤ spot ➤ snot ➤ snob ➤ snib ➤ snig ➤ snip ➤ snup ➤ scup ➤ scut ➤ shut ➤ phut ➤ pout ➤ mout ➤ moul ➤ soul ➤ soil ➤ sowl ➤ sown ➤ sowt ➤ nowt ➤ wowt ➤ woft ➤ toft ➤ toff ➤ tofu ➤ tolu ➤ told ➤ sold ➤ sola ➤ soja ➤ soka ➤ soma ➤ some ➤ sole ➤ soli ➤ solo ➤ soco ➤ soho ➤ soso ➤ sosh ➤ sish ➤ sikh ➤ sinh ➤ sing ➤ song ➤ sond ➤ sonk ➤ sons ➤ soss ➤ siss ➤ sise ➤ sist ➤ wist ➤ west ➤ vest ➤ vent ➤ vend ➤ verd ➤ vera ➤ vela ➤ velo ➤ veto ➤ veta ➤ vita ➤ rita ➤ rite ➤ rive ➤ rove ➤ love ➤ move ➤ wove ➤ weve ➤ wede ➤ wene ➤ wend ➤ weed ➤ week ➤ weak ➤ weal ➤ weam ➤ wean ➤ ween ➤ veen ➤ veep ➤ weep ➤ weel ➤ weet ➤ weft ➤ welt ➤ welf ➤ welk ➤ well ➤ will ➤ wild ➤ wile ➤ vile ➤ vice ➤ vick ➤ wick ➤ wice ➤ wide ➤ wife ➤ wime ➤ wine ➤ tine ➤ ting ➤ tino ➤ tiny ➤ tony ➤ toby ➤ toba ➤ tobe ➤ tode ➤ toda ➤ todd ➤ tody ➤ tory ➤ sory ➤ sora ➤ sorb ➤ sore ➤ sope ➤ soph ➤ qoph ➤ toph ➤ tope ➤ tipe ➤ tire ➤ tirl ➤ tirr ➤ pirr ➤ porr ➤ port ➤ post ➤ posy ➤ poxy ➤ puxy ➤ puky ➤ puly ➤ pull ➤ null ➤ rull ➤ rule ➤ rube ➤ ruby ➤ rudy ➤ rudd ➤ rude ➤ rune ➤ rung ➤ lung ➤ lunn ➤ lunt ➤ lust ➤ must ➤ mutt ➤ butt ➤ gutt ➤ putt ➤ pott ➤ pote ➤ note ➤ rote ➤ rota ➤ roto ➤ toto ➤ toco ➤ tock ➤ tonk ➤ tone ➤ tole ➤ toll ➤ tolt ➤ togt ➤ toga ➤ togs ➤ tops ➤ topi ➤ topo ➤ toho ➤ toko ➤ toro ➤ moro ➤ moxo ➤ moxa ➤ myxa ➤ myna ➤ myra ➤ eyra ➤ eyre ➤ byre ➤ byee ➤ tyee ➤ tree ➤ tref ➤ trek ➤ tret ➤ trey ➤ prey ➤ pray ➤ prad ➤ pram ➤ prat ➤ prut ➤ prue ➤ grue ➤ grub ➤ grun ➤ trun ➤ tran ➤ trah ➤ tram ➤ trim ➤ prim ➤ plim ➤ slim ➤ stim ➤ stam ➤ soam ➤ soap ➤ soup ➤ roup ➤ rout ➤ tout ➤ toit ➤ toot ➤ took ➤ sook ➤ yook ➤ yock ➤ yolk ➤ yelk ➤ yeld ➤ yell ➤ yelm ➤ yelp ➤ yelt ➤ yeat ➤ yeah ➤ yean ➤ yern ➤ tern ➤ torn ➤ toon ➤ tool ➤ toom ➤ room ➤ roof ➤ woof ➤ wolf ➤ wold ➤ woad ➤ woak ➤ woan ➤ whan ➤ whap ➤ whar ➤ what ➤ whet ➤ whee ➤ when ➤ whin ➤ whim ➤ whip ➤ whit ➤ writ ➤ wrig ➤ prig ➤ pria ➤ proa ➤ prob ➤ prod ➤ prof ➤ prog ➤ prop ➤ prow ➤ trow ➤ trod ➤ trog ➤ trig ➤ trin ➤ twin ➤ twig ➤ swig ➤ spig ➤ spin ➤ spit ➤ smit ➤ smut ➤ slut ➤ slub ➤ slud ➤ slue ➤ slug ➤ slog ➤ slon ➤ sloo ➤ slop ➤ stop ➤ stap ➤ stab ➤ stag ➤ stan ➤ staw ➤ stay ➤ stey ➤ steg ➤ stem ➤ item ➤ iten ➤ sten ➤ step ➤ stet ➤ stew ➤ smew ➤ smee ➤ snee ➤ snew ➤ snow ➤ snod ➤ snog ➤ smog ➤ smug ➤ smur ➤ slur ➤ sour ➤ soud ➤ soum ➤ snum ➤ snub ➤ snug ➤ spug ➤ spud ➤ spun ➤ skun ➤ stun ➤ stub ➤ stib ➤ stid ➤ stod ➤ stoa ➤ stob ➤ stof ➤ stog ➤ stot ➤ stow ➤ swow ➤ swob ➤ swab ➤ swad ➤ swag ➤ swam ➤ swan ➤ swap ➤ swat ➤ swot ➤ swom ➤ swim ➤ swum ➤ stum ➤ stud ➤ stue ➤ stre ➤ sure ➤ pure ➤ purl ➤ purr ➤ turr ➤ turb ➤ turd ➤ kurd ➤ kurt ➤ yurt ➤ yuft ➤ tuft ➤ tufa ➤ tuba ➤ tube ➤ tule ➤ tula ➤ sula ➤ suld ➤ sudd ➤ suid ➤ suit ➤ sunt ➤ punt ➤ puna ➤ pung ➤ punk ➤ puny ➤ tuny ➤ tuna ➤ tund ➤ tune ➤ sune ➤ sung ➤ qung ➤ tung ➤ tong ➤ wong ➤ wing ➤ wind ➤ wink ➤ wilk ➤ wilt ➤ wily ➤ winy ➤ viny ➤ vina ➤ viga ➤ vila ➤ vili ➤ viti ➤ titi ➤ tite ➤ site ➤ sita ➤ siva ➤ viva ➤ vira ➤ vire ➤ vine ➤ vino ➤ vint ➤ wint ➤ went ➤ wept ➤ wert ➤ vert ➤ verb ➤ yerb ➤ yarb ➤ yalb ➤ yale ➤ yade ➤ yaje ➤ yare ➤ yard ➤ yarl ➤ yarn ➤ yarr ➤ yirr ➤ wirr ➤ wird ➤ wire ➤ were ➤ wese ➤ wase ➤ vase ➤ vise ➤ vive ➤ wive ➤ wipe ➤ wips ➤ wiss ➤ wise ➤ wish ➤ wash ➤ tash ➤ task ➤ tass ➤ taws ➤ tawa ➤ tawn ➤ pawn ➤ pawk ➤ mawk ➤ mawp ➤ yawp ➤ yawl ➤ yowl ➤ youl ➤ youd ➤ yond ➤ yont ➤ wont ➤ wone ➤ wode ➤ woke ➤ wore ➤ tore ➤ tome ➤ tote ➤ toty ➤ tosy ➤ tosh ➤ tosk ➤ toss ➤ tost ➤ tort ➤ sort ➤ syrt ➤ syre ➤ gyre ➤ gyle ➤ gyne ➤ gype ➤ gyte ➤ gyve ➤ wyve ➤ wyde ➤ wyke ➤ fyke ➤ hyke ➤ hyle ➤ hyne ➤ syne ➤ wyne ➤ wyle ➤ wype ➤ rype ➤ type ➤ tyke ➤ pyke ➤ pyre ➤ lyre ➤ tyre ➤ tyro ➤ typo ➤ typp ➤ tymp ➤ tump ➤ rump ➤ sump ➤ sumo ➤ suto ➤ sutu ➤ suku ➤ sulu ➤ sulk ➤ suck ➤ such ➤ ouch ➤ ough ➤ sugh ➤ pugh ➤ push ➤ tush ➤ wush ➤ wusp ➤ wuss ➤ wust ➤ rust ➤ ruse ➤ russ ➤ rusk ➤ ruck ➤ tuck ➤ tuik ➤ turk ➤ tusk ➤ tunk ➤ tuno ➤ tunu ➤ tulu ➤ tutu ➤ tute ➤ tuts ➤ tuth ➤ teth ➤ tath ➤ wath ➤ with ➤ wite ➤ wote ➤ vote ➤ yote ➤ yoke ➤ yore ➤ yere ➤ yerd ➤ yerk ➤ york ➤ work ➤ word ➤ wood ➤ wool ➤ woon ➤ worn ➤ wort ➤ worm ➤ woom ➤ zoom ➤ zoon ➤ zion

No wonder you find it to be an expensive computation. 

[Benjamin Measures]

On Sunday, 1 June 2014 15:57:47 UTC+1, Peter Hickman wrote:

I assumed that as list had been implemented as a package it would be a superior solution to plain string slices, I mean why create a package that is inferior to the built in functionality.

Ruby doesn't have linked lists so you wouldn't understand. I mean why should rock star rubists concern themselves with theory and understanding?

[chris dollin]

On 2 June 2014 09:00, Benjamin Measures <saint....@gmail.com> wrote:

Ruby doesn't have linked lists so you wouldn't understand. I mean why should rock star rubists concern themselves with theory and understanding?

Snide and unhelpful all in one lump. If you can't be polite, be quiet.

Chris

--
Chris "allusive" Dollin

[Benjamin Measures]

On Monday, 2 June 2014 10:04:48 UTC+1, chris dollin wrote:

On 2 June 2014 09:00, Benjamin Measures <saint....@gmail.com> wrote:

Ruby doesn't have linked lists so you wouldn't understand. I mean why should rock star rubists concern themselves with theory and understanding?

Snide and unhelpful all in one lump.

There are two main outcomes:

1. It gets ignored; Life goes on. (p~0.7)

2. Offence is taken; (p~0.3)

 a. I get proven wrong. The OP now understands. (p~0.25)

 b. Nothing happens. Somebody is hurt. (p~0.05)

Had I provided an answer to the [rhetorical] question, "I mean why create a package that is inferior":

1. It gets ignored; Life goes on. (p~0.95)

2. The OP takes an interest; The OP now understands. (p~0.05)

Was it worth the chance of somebody new learning the performance characteristics of linked lists? I don't know.

If you can't be polite, be quiet.

As you wish, I respect your posts.

[Paul Hankin]

<font face="arial narrow, sans-s

...

I think Peter's ruby program finds all _shortest_ paths between each pair of words. That is, (shortest) paths between every pair of words, not every path between every pair of words. The latter has exponential blowup and for example there's at least 16! paths from BAT to CAT, since you can take any path through the set of words: EAT FAT GAT HAT KAT LAT MAT NAT OAT PAT QAT RAT SAT TAT VAT WAT. 16! ~= 2e13, which is too big to be feasible.

Anyhow, as an exercise since I've never done any benchmarking/profiling/etc. in go before, I wrote some code to find, for each N, the pair of words of length N that have the longest distance between them. I suppose there's a cleverer way to find a graph diameter than to do a full depth-first search on the graph for every node, but that's what I did, and the slowest N (ie: N=5) took 118sec, which is quite a lot better than 11 hours. It's a curiosity that N=5 is slower than N=6 and N=7, because there's more words 6 and 7 letter words than 5 letter words. I think it's because there's lots of 6 and 7 letter words with common suffixes, and so the graph has relatively fewer edges.

Here's the benchmark results, which include a log line for the longest paths found:

BenchmarkLongest3-2        1 1080988066 ns/op

--- BENCH: BenchmarkLongest3-2

wordladder_test.go:243: [IGG EGG ERG ERN EEN BEN BIN BIZ ZIZ ZZZ]

BenchmarkLongest4-2        1 17632977434 ns/op

--- BENCH: BenchmarkLongest4-2

wordladder_test.go:243: [AMOK ATOK ATOP ATAP ALAP ALAS ALTS ANTS ANTE ANCE UNCE UNCO UNDO UPDO UPGO]

BenchmarkLongest5-2        1 71806645487 ns/op

--- BENCH: BenchmarkLongest5-2

wordladder_test.go:243: [APPEL APPAL APPAY APPLY AMPLY AMPLE AMOLE ANOLE ANILE ANILS ARILS VRILS VEILS DEILS DELLS DELLY DELAY DENAY DENAR DEBAR KEBAR KABAR KABAB KABOB CABOB CAROB CAROL PAROL]

BenchmarkLongest6-2        1 117603093116 ns/op

--- BENCH: BenchmarkLongest6-2

wordladder_test.go:243: [EMBOIL EMBAIL EMBALL EMBALE EMPALE EMPARE EMPARL IMPARL IMPARK IMBARK EMBARK EMBARS EMBERS EMMERS EMMEWS ENMEWS ENDEWS ENDERS ENTERS EATERS PATERS PARERS PAREOS PARVOS PARVIS PARKIS PARKAS PARRAS PARRAL PARIAL PARIAH PARISH BARISH BANISH DANISH DAWISH RAWISH RADISH RUDISH DUDISH DUDISM NUDISM NUDIST NUDEST RUDEST]

BenchmarkLongest7-2        1 74958368760 ns/op

--- BENCH: BenchmarkLongest7-2

wordladder_test.go:243: [GAINEST FAINEST FAIREST SAIREST SAIDEST SADDEST MADDEST MIDDEST MILDEST WILDEST WILIEST WALIEST WANIEST CANIEST CANTEST CONTEST CONFEST CONFESS CONFERS CONNERS CANNERS PANNERS PAWNERS PAWNEES PAWNCES PAUNCES POUNCES POUNCED POUNDED POINDED POINTED PRINTED PRENTED PRESTED PRESSED PREASED PREASES UREASES UNEASES UNCASES UNCASED UNBASED UNBATED UNMATED UNMETED UNMEWED ENMEWED ENDEWED INDEWED INDEXED INDEXES INDENES INDENTS INCENTS INCESTS INFESTS INFECTS INJECTS]

BenchmarkLongest9-2       10  122306602 ns/op

--- BENCH: BenchmarkLongest9-2

wordladder_test.go:243: [BRUSHINGS BLUSHINGS FLUSHINGS FLASHINGS CLASHINGS CLASPINGS CLAPPINGS CLIPPINGS CHIPPINGS CHOPPINGS CROPPINGS DROPPINGS DRIPPINGS TRIPPINGS TRIPLINGS TRILLINGS TWILLINGS SWILLINGS STILLINGS STALLINGS STALKINGS STACKINGS STICKINGS SLICKINGS CLICKINGS CLOCKINGS BLOCKINGS BLACKINGS BLANKINGS PLANKINGS PLANTINGS PLATTINGS SLATTINGS SWATTINGS SWOTTINGS SPOTTINGS SPOUTINGS SHOUTINGS SHOOTINGS]

BenchmarkLongest10-2       50   66829422 ns/op

--- BENCH: BenchmarkLongest10-2

wordladder_test.go:243: [BLISTERING BLUSTERING CLUSTERING CLUTTERING CLATTERING SLATTERING SCATTERING SCUTTERING STUTTERING STOTTERING STOITERING]

BenchmarkLongest11-2       50   56975603 ns/op

--- BENCH: BenchmarkLongest11-2

wordladder_test.go:243: [DINGINESSES MINGINESSES MANGINESSES RANGINESSES RANDINESSES HANDINESSES HARDINESSES TARDINESSES TARTINESSES TATTINESSES RATTINESSES RUTTINESSES RUSTINESSES MUSTINESSES MUSKINESSES MURKINESSES MIRKINESSES MILKINESSES SILKINESSES SULKINESSES BULKINESSES BULGINESSES BUGGINESSES PUGGINESSES PUDGINESSES PODGINESSES]

BenchmarkLongest12-2       50   35458411 ns/op

--- BENCH: BenchmarkLongest12-2

wordladder_test.go:243: [MATERIALIZED MATERIALISED MATERIALISES MATERIALISMS MATERNALISMS PATERNALISMS PATERNALISTS]

BenchmarkLongest13-2      100   23323809 ns/op

--- BENCH: BenchmarkLongest13-2

wordladder_test.go:243: [BEARISHNESSES BOARISHNESSES BOORISHNESSES BOOKISHNESSES BLOKISHNESSES]

BenchmarkLongest14-2      100   15643089 ns/op

--- BENCH: BenchmarkLongest14-2

wordladder_test.go:243: [ROOFLESSNESSES ROOTLESSNESSES FOOTLESSNESSES FOODLESSNESSES WOODLESSNESSES WORDLESSNESSES WORKLESSNESSES]

BenchmarkLongest15-2      100   14157335 ns/op

--- BENCH: BenchmarkLongest15-2

wordladder_test.go:243: [EXPANDABILITIES EXPENDABILITIES EXTENDABILITIES EXTENDIBILITIES EXTENSIBILITIES]

I've not done any profiling yet since it looks like it's not ready yet on MacOS/Mavericks, but I was impressed how convenient it was to write benchmarks.

-- 

Paul

 

[Peter Hickman]

--
You received this message because you are subscribed to a topic in the Google Groups "golang-nuts" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/golang-nuts/Hkav3BpgWsk/unsubscribe.
To unsubscribe from this group and all its topics, send an email to golang-nuts...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

I admire your optimism but you overlooked other outcomes:

1) I learn to ignore anything that Benjamin Measures says (p~1.0)

2) There is no other outcome

Combined with your condescending and elitist attitude (re "why should rock star rubists concern themselves with theory and understanding") I can confidently say that the only thing I have learned from Benjamin Measures is that Benjamin Measures has nothing to say worth listening to.

I am going to press on with the C++ version of the program to see if it exhibits the same performance characteristics and look into applying the suggestions I have received here.

However nothing that you have said was in the least bit useful. You brought nothing to the party.

[Michael Jones]

On Mon, Jun 2, 2014 at 4:41 AM, Paul Hankin <paul....@gmail.com> wrote:

:

I think Peter's ruby program finds all _shortest_ paths between each pair of words. That is, (shortest) paths between every pair of words, not every path between every pair of words. The latter has exponential blowup and for example there's at least 16! paths from BAT to CAT, since you can take any path through the set of words: EAT FAT GAT HAT KAT LAT MAT NAT OAT PAT QAT RAT SAT TAT VAT WAT. 16! ~= 2e13, which is too big to be feasible.

Yes, all shortest paths would be much more reasonable. But I can only go by what people say, and he wrote specifically, "I have a little program I wrote in Ruby to find all the chains between any two four letter words where each intermediate word only differs by one letter." [emphasis mine.] Another support for 'all' meaning 'all' rather than 'each solution of shortest length' is the reported long run times. Anyway, if the problem is as you state it is much more interesting!

 

Anyhow, as an exercise since I've never done any benchmarking/profiling/etc. in go before, I wrote some code to find, for each N, the pair of words of length N that have the longest distance between them. I suppose there's a cleverer way to find a graph diameter than to do a full depth-first search on the graph for every node, but that's what I did, and the slowest N (ie: N=5) took 118sec, which is quite a lot better than 11 hours. It's a curiosity that N=5 is slower than N=6 and N=7, because there's more words 6 and 7 letter words than 5 letter words. I think it's because there's lots of 6 and 7 letter words with common suffixes, and so the graph has relatively fewer edges.

Your program seems nicely performant. As you say, the key issue is not the number of words (nodes) but the number of possible transitions between them (edges in the graph theory sense, or pairs in the terminology of the original post.) 

This consideration is why the exact list of chosen words makes such a difference. I've been experimenting with a variety of word lists and see great variation based on the source.

Michael

 

--

You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Peter Hickman]

On 2 June 2014 14:39, 'Michael Jones' via golang-nuts <golan...@googlegroups.com> wrote:

On Mon, Jun 2, 2014 at 4:41 AM, Paul Hankin <paul....@gmail.com> wrote:

:

I think Peter's ruby program finds all _shortest_ paths between each pair of words. That is, (shortest) paths between every pair of words, not every path between every pair of words. The latter has exponential blowup and for example there's at least 16! paths from BAT to CAT, since you can take any path through the set of words: EAT FAT GAT HAT KAT LAT MAT NAT OAT PAT QAT RAT SAT TAT VAT WAT. 16! ~= 2e13, which is too big to be feasible.

Yes, all shortest paths would be much more reasonable. But I can only go by what people say, and he wrote specifically, "I have a little program I wrote in Ruby to find all the chains between any two four letter words where each intermediate word only differs by one letter." [emphasis mine.] Another support for 'all' meaning 'all' rather than 'each solution of shortest length' is the reported long run times. Anyway, if the problem is as you state it is much more interesting!

My apologies for not being clearer, I was indeed looking for the shortest chains between two words.

Having said that "the longest chain between two words" has an appeal of it's own :)

[Michael Jones]

Oh! Glad to hear that. Now we're in the realm of interesting programming tasks.

In my post yesterday morning I addressed part one: reading the word list and finding all the pairs between words where a transition from one to the other can be done by changing a single letter. This data, collected for each word, defines the underlying problem: "word 17 can become word 3, 31, 406, and 993." The time for this in Go is quite brief, just 24 milliseconds for the exhaustive SCRABBLE 4-letter word list. This was a fun exercise and a good use for Go's built-in map type.

Finding and counting each shortest-length word chains between every pair of words is part two of the task. Here are some initial results using n-letter words from the Webster's ("web2") wordlist in UNIX-style OS's /usr/dict/words (or /usr/share/dict/words):

139 words in "words/webster-2"

46 links

xi -> ai -> aa -> ya

word pairs =       276

   ladders =      2592

user 0m0.001s

1294 words in "words/webster-3"

969 links

own -> awn -> arn -> urn

word pairs =      2586

   ladders =     26656

user 0m0.005s

4994 words in "words/webster-4"

9118 links

zuza -> juza -> juba -> cuba -> cube -> cuke -> cyke -> cyme -> zyme

word pairs =      9986

   ladders =     62096

user 0m0.723s

The word ladder/chain printed in each case is the first example of the longest length required to connect every pair of connectable pairs in that word set. In the case of webster-4, this means that there are 4994 4-letter words in my Mac's /usr/share/dict/words, that these have 9118 link classes (commonalities where a single ambiguous letter allows a transition with the other letters remaining fixed), that 9,986 pairs of words out of the 4994*4993 = 24,935,042 total possible pairs do indeed have letter chains between them, that there are 62,096 such chains, and that this whole process, including the reading and pair discovery, requires 0.723 seconds of compute time in Go in single-threaded mode. Let's compare to your original post:

Now the Go version which is essentially the same code but with some improvements over the Ruby version. I realise that this may not be the best written program but I was expecting some improvement over the Ruby version. However whereas the Ruby version ran in little over an hour the Go version took 11 hours to process only 1303 words from the dictionary, it seems to be averaging around 30 seconds per word and the program would probably take around 40 hours to complete. As I've said I recognise that the Go version is not the best solution to this problem but I find it difficult to understand how it can be an order of magnitude worse.

Everyone would prefer 0.723 seconds to an hour, 11 hours, or 40 hours. The problem here is not Go, but a combination of two factors:

a. The intrinsic efficiency of algorithms and data structures matters. (strategy)

b. The implementation environment shapes the approach. (tactics)

Admittedly I did not look at the Ruby program to see what it is doing, not actually at the Go program because Go trying to be Ruby is not the place to be. I wanted to explore the problem itself to see what it needed and then consider how to do that efficiently in Go.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Kevin D]

This project may be of interest:

https://github.com/neocortical/go-doublet

[Michael Jones]

Yes, nice to see it done carefully with A*. I worked on my version a little bit more before I left home this morning to see what ladders could be made from Lincoln's Gettysburg Address and Martin Luther King, Jr's "I have a Dream" speech. Also explored using Go's UTF/rune mechanisms to search for similar chains in Greek and Japanese.

ワード ➤ 

コード ➤ 

コース ➤ 

アース ➤ 

アリス ➤ 

アリー ➤ 

フリー ➤ 

ファー ➤ 

ファン ➤ 

ヴァン

I like that this one starts with "word" and "code" -- it seems auspicious!

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Michael Jones]

Oh, and with four characters:

ブロック ➤ ブラック ➤ ブラッド ➤ ブランド ➤ グランド ➤ グラント ➤ プラント

...which according to Google Translate, is...

Block ➤ Black ➤ Blood ➤ Brand ➤ Ground ➤ Grant ➤ Plant

​The word list is from the open movie subtitle database​, so the vocabulary is rather restricted...

[Dan Kortschak]

On Mon, 2014-06-02 at 14:55 +0100, Peter Hickman wrote:
> My apologies for not being clearer, I was indeed looking for the
> shortest chains between two words.

For this case, performing a meet-in-the-middle will probably give you
the greatest performance increase.

[Peter Hickman]

Just to report on the progress I made. The first change I made was to pre allocate all my data structures up front, using slices, and stop using the List type.

There was pretty much no improvement, maybe averaging a 2-3 seconds faster per word on average. This suggests that Go is not really having much of a problem allocating and releasing objects and that the List type is not that inefficient.

The next step was to convert the words to numbers. When the dictionary is loaded it allocates a number to each new word it sees and the data structures now reference number and not strings. This allowed me to implement Fredrik Ehnbom's suggestion of the key being a struct of ints which showed the best performance improvement for makeKey.

The result is that each word is now being processed in around 5 seconds as opposed to 30 seconds. This gives an overall runtime of less that 7 hours, much improved on the 40+ but still short of the Ruby 1 hour.

I think that it means that the real bottleneck was assigning strings and / or comparing strings. Given how frequently the notFoundInTree function was being called I suspect that comparison was the most likely culprit.

In essence the Go and Ruby programs are both implementing the same brute force algorithm, just that Go is using integers rather than strings.

The next step is checking the output, if nothing both programs should have produced the same output. Then I need to check that the output is actually correct (I did some checks on the Ruby version but will have to be a bit more thorough).

I have some tweaks, which for the sake of fairness I will have to apply to both programs, which should reduce the number of comparisons.

[Michael Jones]

Peter,

Can you share your word list and computed sum of shortest paths? If so, we could better understand the performance of your chosen approach. (Feel free to email me directly with the file if that is easiest.)

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.