A guess the word game

The agreed dictionary. All words are 6 letters long with all letters distinct

Rules: This is a game of two players and the task will be to implement Player 2.

Player 1 chooses a word from the agreed dictionary

Player 2 repeatedly guesses a word from the agreed dictionary.

At each turn, Player 1 tells Player 2 how many letters the guess has in common with the secret word. For example, youths and devout have three letters in common.

Goal

Player 2's goal is to guess the word in as few turns as possible.

The task is to implement player 2 to minimize the maximum number of guesses they ever have to make. Your score is the maximum number of guesses made when considered over all the words in the agreed dictionary. A lower score is better.

You should test your code by choosing each word from the agreed dictionary in turn and see how many guesses your implementation of Player 2 needs. You should then output the maximum.

Objective winning criteria

Answers will first be compared by the score they get using the rules above. Two answers with the same score will then be compared using rules. That is by the number of bytes in the code.

• I feel like this challenge is just going to end up being a regular code-golf once someone figures out the best word path :P Not a necessarily bad thing, and I didn't downvote. – HyperNeutrino Nov 13 '19 at 15:33
• Using bytecount as a tiebreaker is a thing to avoid when writing challenges – pppery Nov 14 '19 at 4:27
• @AlexeyBurdin Your code can load it from wherever is convenient. – Anush Nov 14 '19 at 11:11
• @ everyone: you can use ./.input.tio as file-path in TIO and it will use the content of the STDIN as file content. I did something similar in this challenge. It probably won't be able to fit the entire wordlist because it's too large, but a smaller test sample is possible to verify your code a bit. @GB Here your Ruby TIO like this. – Kevin Cruijssen Nov 14 '19 at 15:23
• Ah man, I've just done it thinking P2 tells P1 which characters the words had in common, not just the count. And the worst score was 64 (very straightforward implementation). No idea how the current answers are able to get it so efficient with those rules. Good challenge, much harder than I expected. – Matsyir Nov 20 '19 at 16:07

Ruby, 418 bytes, score 12 (on 'palest')

$dict = File.readlines('agreeddict.txt').map(&:chomp) def search(wrd) words = 0 fdic =$dict.clone
guess = ''
starters = ['earths','blowup','coding']

chs = wrd.chars

while guess!=wrd do
guess = starters.pop || fdic.pop
words += 1
ghs = guess.chars
chars = (chs|ghs).size
fdic.select!{|w|(w.chars|ghs).size == chars}
end

words
end

upp = 0;

p $dict.map{|w| [search(w),w] }.max  Try it online! Runs in 15 seconds on my machine. TIO link for reference only - does not work if the file is not in the current directory. The trick Instead of brute-force elimination, try a list of initializers first. A lot of words differ by only 1 character and it's easy to get stuck in a single-letter elimination loop. The most difficult words to guess are those with 4-5 very common characters (a e r s t), 1-2 'outsiders' (c p x z...) and some anagrams in the dictionary. For example, when we reach a word containing the letters "a e r s t" and the answer is 5: if we just filter all the entries containing these 5 characters, we are left with a dictionary of 40 similar words, and then we have to try almost all of them, removing only a few words at each step. We need to remove these words first, and we filter on the least common character, so if we get to "earths", and Player 1 answers 5, we don't have a lot of words to check. The first 2 words we always check are "coding" and "blowup" (no pun intended). Now we can try with a word containing the 5 most common letters ("earths"). If the answer is 4 or 5 (which is likely), we don't have a lot of words to choose from, because we already filtered all the words containing only 1 or 2 uncommon letters (and we only used 3 guesses to get here). Finding the right initializers was a little tricky, I started with a list of 5 "quasi orthogonal" words (with as few letters as possible in common, a good start was "sporty fuzing hawked climax jumble", missing only the letter z) and got to 13, then started a test on automatically generated smaller lists. 'palest' seems to be a worst case, having 6 anagrams and 4 very common letters, but it's not the only word requiring 12 guesses, so I don't think I could get a better score with this approach. I don't want to golf this. Python 3.8, 730 bytes, score 13 p='https://gist.github.com/lesshaste/775f70d4da6778807ff9a8a42c293169/raw/c36b8d3b3d501106de781cb2c3b4c8f6e9d47b33/agreeddict.txt' from urllib.request import urlopen as o w=str(o(p).read(),encoding='utf-8').split('\n') from collections import* g=lambda x:lambda s:len(set(x)&set(s)) s=dict() for x in w: f=g(x) #the answer function from Player 1. Nothing else knows x y=w[:] #init the word set c=0 #tries counter wd='muting' while len(set(frozenset(i) for i in y))>1: #till we have only one set of letters c+=1 m=f(wd) y=[i for i in y if len(set(i)&set(wd))==m] #filter words #print('%2d'%c,wd,'answer:%d'%m,'variants left:%4d'%len(y)) d=dict() for i in y: r=Counter(len(set(i)&set(j)) for j in y) d[i]=max(r.items(),key=lambda x:x[1]) #-math.log(d[i]/len(y),2) is the info in worst case wd=min(d.items(),key=lambda x:x[1][1])[0] s[x]=(c,len(y)) assert set(y[0])==set(x) print(x,c,len(y),flush=True) print(max(sum(i) if i[1]!=1 else i[0] for i in s.values()))  Try it online! (doesn't seem to work, you can download it from there and run with python3 (likely 3-4 hours)) -- the result is here. The working version with 5 first words+['palest','extras','orates'] for shorter amount of time (with words-list lzma-compressed). At every step we choose such word from the list of words left, as even the worst answer form Player 1 gives us the most of information over all worst cases. We need ~11.77 bits of information. Output is word, number of tries to get set of letters, number of words with such set. The maximum:  1 muting answer:1 variants left:1149 2 charts answer:4 variants left: 133 3 alerts answer:5 variants left: 32 4 averts answer:5 variants left: 19 5 prates answer:5 variants left: 16 6 rawest answer:5 variants left: 13 7 skater answer:5 variants left: 10 8 stared answer:5 variants left: 7 9 barest answer:5 variants left: 5 10 faster answer:5 variants left: 3 11 ersatz answer:5 variants left: 2 12 extras answer:5 variants left: 1 orates 12 1  (compared with "palest")  1 muting answer:1 variants left:1149 2 charts answer:3 variants left: 344 3 dactyl answer:3 variants left: 102 4 adepts answer:5 variants left: 18 5 basted answer:4 variants left: 11 6 palest answer:6 variants left: 6  • The TIO doesn't seem to work. – Anush Nov 14 '19 at 13:50 • I do with y=[i for i in y if len(set(i)&set(wd))==m] – Alexey Burdin Nov 14 '19 at 15:12 • Your output suggests 12 but I am not sure what orates 12 1 means – Anush Nov 14 '19 at 20:52 • This means after 12th step Player 2 knows that the word is 'orates' (1 candidate) but he didn't hit 6 before, so need 1 more turn. – Alexey Burdin Nov 14 '19 at 21:03 Haskell, haven't bothered to golf, 14 If I can get down to 13, I'll try to golf this, but I don't have time right now: {-# LANGUAGE TemplateHaskell #-} module Main where import Control.Monad.State.Lazy import Control.Lens import Data.List (intersect) import System.Environment import Text.Printf data World = World { _wDictionary :: [String] , _wAnswer :: String , _wScore :: Int } makeLenses ''World main :: IO () main = do [answer] <- getArgs dictionary <- fmap lines getContents let score = evalState solve$ World dictionary answer 0
putStrLn $printf "Correctly guessed answer %s in %d attempts" answer score solve :: State World Int solve = do word <- uses wDictionary head result <- guess word if result == 6 then use wScore else do wDictionary %= filter ((== result) . length . intersect word) solve guess :: String -> State World Int guess word = do wScore += 1 uses wAnswer$ length . intersect word


Words scoring 14 are "streak", "skater", and "takers." I can't add TIO because it doesn't have the lens package.