Return to Answer

A joint submission from user PragTob and myself.

A joint submission from user PragTob and myself.

As it stands, this is not a valid answer, as it accesses the word list. I'm currently working on a version that doesn't do so, but it might take a while.

A joint submission from user PragTob and myself.

MAX_TURNS = 6

words_by_length = File.read('wordlist.txt').split.group_by &:length

while !(input=gets.chomp)['END']
  current_turns = MAX_TURNS
  won = false
  fitting_words = words_by_length[input.length]
  characters_used = '_'
  while (current_turns > 0) && !won
    pattern_regex = Regexp.new(input.gsub('_', "[^#{characters_used}]"))
    fitting_words = fitting_words.select do |word|
      pattern_regex.match word
    end

    char_count = Hash.new 0
    fitting_words.each do |word|
      word.chars.uniq.each {|c|
        char_count[c] += 1
      }
    end

    chars = char_count.keys.reject {|c|
      /[#{characters_used}]/.match c
    }.sort_by {|c|-char_count[c]}

    characters_used << chars[0]
    puts chars[0]
    $stdout.flush
    old_input     = input
    input         = gets.chomp

    current_turns -= 1 if input == old_input
    won = !input[?_]
  end

  if won
    words_by_length[input.length].delete input
  end
end

Currently this takes about 13 seconds on my machine, but there is certainly room for some speed optimisation.

It averages a score of about 3940 and total error of 6050.

I say "averages", because the algorithm depends on the order of the words used.

This is roughly how it works:

• for each guess, we figure out all possible words from the given list, count in how many of them each character occurs and guess the most common one

• here is how we determine "all possible words":

  • we start with all words on word list
  • every time we guess a word correctly, we delete it
  • at each turn we also remove all words that do not fit the input pattern
  • finally we remove all words where "blanks" in the input pattern correspond to characters we already guessed

It's getting late over here and that's currently the best method we can think of. We might be able to make minor improvements by including logic to throw out missed words as well (say we missed three words that all read _o_ at the end, and there are three words like this left in our list, we could throw those out as well). But it seems that this might take at least as much code as we already have, and the improvements may or may not be negligible.

A joint submission from user PragTob and myself.

MAX_TURNS = 6

frequencies = {?t=>[3,48,145,214,252,266,249,223,191,142,63,44,16,1,0,1],?h=>[2,14,81,125,85,91,60,42,30,14,11,6,1,1],?e=>[5,49,260,316,456,408,328,279,202,125,50,32,12,0,0,1],?a=>[4,60,211,259,249,266,253,192,152,111,51,42,15,1,0,1],?n=>[4,30,120,136,214,252,238,214,189,128,59,45,16,0,0,1],?d=>[1,25,100,104,131,123,131,81,63,36,14,15,7,1],?f=>[2,13,51,58,64,67,41,40,28,18,11,9,3,1],?o=>[9,44,150,165,195,220,214,168,155,104,46,37,14,1,0,1],?r=>[1,25,140,246,312,310,263,206,150,95,45,32,11,1],?y=>[3,29,41,58,86,94,83,63,52,31,21,12,2],?u=>[2,23,67,117,126,154,107,97,85,48,27,16,2,0,0,1],?b=>[2,22,53,60,72,59,41,30,36,16,7,6,1],?i=>[3,38,143,179,223,299,270,241,205,134,64,44,16,1,0,1],?s=>[3,23,129,176,195,208,177,136,117,71,44,23,13,1],?c=>[0,12,68,122,146,194,180,163,130,85,49,25,7,0,0,1],?l=>[0,18,153,172,190,196,164,131,125,67,35,20,5,0,0,1],?g=>[1,19,42,75,82,104,78,60,39,30,12,10,0,1],?w=>[1,21,56,56,40,41,18,16,6,2,1,0,0,1],?m=>[2,10,77,68,119,94,104,76,68,45,15,17,8,0,0,1],?p=>[1,24,82,84,94,129,105,88,99,56,24,11,7],?k=>[1,6,65,37,28,24,6,10,3,4],?j=>[0,5,5,6,7,6,5,6,2,0,1,1],?x=>[0,6,4,7,15,22,13,16,9,9,2,2],?v=>[0,3,21,39,47,58,63,42,40,23,10,9,2],?z=>[0,0,3,3,3,5,2,3,0,0,1],?q=>[0,0,1,9,5,13,8,3,5,4,3,2]}

while !(input=gets.chomp)['END']
  current_turns = MAX_TURNS
  won = false
  chars = frequencies.keys.sort_by {|c|
    -(frequencies[c][input.length-2] || 0)
  }
  i=0
  while (current_turns > 0) && !won
    c=chars[i]
    i += 1
    puts c
    $stdout.flush
    old_input     = input
    input         = gets.chomp

    if input == old_input
      current_turns -= 1
    # else
    #   frequencies[c][input.length-2] -= 1 
    end
    won = !input[?_]
  end
end

Result:

score is 625, totalerr is 23196

This has 1672 characters and isn't golfed yet so we have ample room for algorithmic improvement.

First we store a hash of character frequencies (computed from the word list) grouped by word length.

Then in each round we simply sort all characters by the frequencies for the current length and try them from most common to least common one. Using this approach we obviously fail every single word that has even just a medium common character.

Ruby

A joint submission from user PragTob and myself.

MAX_TURNS = 6

words_by_length = File.read('wordlist.txt').split.group_by &:length

while !(input=gets.chomp)['END']
  current_turns = MAX_TURNS
  won = false
  fitting_words = words_by_length[input.length]
  characters_used = '_'
  while (current_turns > 0) && !won
    pattern_regex = Regexp.new(input.gsub('_', "[^#{characters_used}]"))
    fitting_words = fitting_words.select do |word|
      pattern_regex.match word
    end

    char_count = Hash.new 0
    fitting_words.each do |word|
      word.chars.uniq.each {|c|
        char_count[c] += 1
      }
    end

    chars = char_count.keys.reject {|c|
      /[#{characters_used}]/.match c
    }.sort_by {|c|-char_count[c]}

    characters_used << chars[0]
    puts chars[0]
    $stdout.flush
    old_input     = input
    input         = gets.chomp

    current_turns -= 1 if input == old_input
    won = !input[?_]
  end

  if won
    words_by_length[input.length].delete input
  end
end

Currently this takes about 13 seconds on my machine, but there is certainly room for some speed optimisation.

It averages a score of about 3940 and total error of 6050.

I say "averages", because the algorithm depends on the order of the words used.

This is roughly how it works:

• for each guess, we figure out all possible words from the given list, count in how many of them each character occurs and guess the most common one

• here is how we determine "all possible words":

  • we start with all words on word list
  • every time we guess a word correctly, we delete it
  • at each turn we also remove all words that do not fit the input pattern
  • finally we remove all words where "blanks" in the input pattern correspond to characters we already guessed

It's getting late over here and that's currently the best method we can think of. We might be able to make minor improvements by including logic to throw out missed words as well (say we missed three words that all read _o_ at the end, and there are three words like this left in our list, we could throw those out as well). But it seems that this might take at least as much code as we already have, and the improvements may or may not be negligible.

Ruby

As it stands, this is not a valid answer, as it accesses the word list. I'm currently working on a version that doesn't do so, but it might take a while.

A joint submission from user PragTob and myself.

MAX_TURNS = 6

words_by_length = File.read('wordlist.txt').split.group_by &:length

while !(input=gets.chomp)['END']
  current_turns = MAX_TURNS
  won = false
  fitting_words = words_by_length[input.length]
  characters_used = '_'
  while (current_turns > 0) && !won
    pattern_regex = Regexp.new(input.gsub('_', "[^#{characters_used}]"))
    fitting_words = fitting_words.select do |word|
      pattern_regex.match word
    end

    char_count = Hash.new 0
    fitting_words.each do |word|
      word.chars.uniq.each {|c|
        char_count[c] += 1
      }
    end

    chars = char_count.keys.reject {|c|
      /[#{characters_used}]/.match c
    }.sort_by {|c|-char_count[c]}

    characters_used << chars[0]
    puts chars[0]
    $stdout.flush
    old_input     = input
    input         = gets.chomp

    current_turns -= 1 if input == old_input
    won = !input[?_]
  end

  if won
    words_by_length[input.length].delete input
  end
end

Currently this takes about 13 seconds on my machine, but there is certainly room for some speed optimisation.

It averages a score of about 3940 and total error of 6050.

I say "averages", because the algorithm depends on the order of the words used.

This is roughly how it works:

• for each guess, we figure out all possible words from the given list, count in how many of them each character occurs and guess the most common one

• here is how we determine "all possible words":

  • we start with all words on word list
  • every time we guess a word correctly, we delete it
  • at each turn we also remove all words that do not fit the input pattern
  • finally we remove all words where "blanks" in the input pattern correspond to characters we already guessed

It's getting late over here and that's currently the best method we can think of. We might be able to make minor improvements by including logic to throw out missed words as well (say we missed three words that all read _o_ at the end, and there are three words like this left in our list, we could throw those out as well). But it seems that this might take at least as much code as we already have, and the improvements may or may not be negligible.