hangman

a-hangman.md

http://ruby-china.org/topics/16256

get https://github.com/mvj3/hangman/blob/master/data/words.txt

and compile the decision tree.json

ruby compile.rb

then run the test

ruby test.rb

result

tested 8000 samples, correct rate: 99.3125%

---

example keys in tree.json:

• "c1,3" when "c" matches in position 1 and 3
• "" when a char doesn't match (the char can be extracted from the first char of keys of the same wrapping hash)

leaf values in tree.json:

• 1 guess succeed. no repeat chars in the word
• 0 guess succeed. there is repeat chars in the word

compile.rb

require_relative "word"

def compile_tree chars, words
  if words.empty?
    return 0
  elsif chars.empty?
    return 1
  end

  c = chars.max_by do |c|
    words.count do |word|
      word.indices c
    end
  end
  chars -= [c]

  r = words.group_by do |word|
    word.indices c
  end
  if r.size == 1 and r.keys.first.nil?
    # edge case: no other chars fit
    return 0
  end
  r.keys.each do |k|
    r[k] = compile_tree(chars, r[k])
  end
  r
end

words = File.read(__dir__ + '/words.txt').downcase.strip.split
words = words.group_by(&:size)

tree = {}
words.each do |sz, list|
  puts "#{sz}: #{list.size}"
  list.map! {|w| Word.new w }
  tree[sz] = compile_tree ('a'..'z').to_a, list
end

require "json"
File.open __dir__ + '/tree.json', 'w' do |f|
  f << tree.to_json
end

test.rb

require "json"
require_relative "word"

TREE = JSON.parse File.read __dir__ + '/tree.json'
WORDS = File.read(__dir__ + '/words.txt').strip.split

def guess_word word, fail
  print word, ': '

  tree = TREE[word.size.to_s]
  word = Word.new word
  while fail > 0
    c = tree.find{|k,v|k.size > 0}.first[0]
    k = word.indices(c)
    if k
      print k[0]
    else
      fail -= 1
      print "#{c}!"
    end
    tree = tree[k.to_s]
    if tree == 1 or tree == 0
      puts
      return true
    end
  end
  puts ' -- FAIL'
  false
end

all_correct = 0
100.times do
  correct = WORDS.sample(80).count do |word|
    guess_word word, 10
  end
  puts '-' * 70
  puts "correct: #{correct}/80"
  all_correct += correct
end

puts
puts '-' * 70
puts "tested 8000 samples, correct rate: #{all_correct.to_f / 80}%"

word.rb

class Word
  def initialize w
    @r = {}
    w.chars.each_with_index do |c, i|
      if @r[c]
        @r[c] << ",#{i}"
      else
        @r[c] = "#{c}#{i}"
      end
    end
  end

  def indices c
    @r[c]
  end
end