10
\$\begingroup\$

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.

Task

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – HyperNeutrino Nov 13 at 15:33
  • 1
  • 1
    \$\begingroup\$ @AlexeyBurdin Your code can load it from wherever is convenient. \$\endgroup\$ – Anush Nov 14 at 11:11
  • 1
    \$\begingroup\$ @ 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. \$\endgroup\$ – Kevin Cruijssen Nov 14 at 15:23
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Matsyir Nov 20 at 16:07
5
+50
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ The TIO doesn't seem to work. \$\endgroup\$ – Anush Nov 14 at 13:50
  • \$\begingroup\$ I do with y=[i for i in y if len(set(i)&set(wd))==m] \$\endgroup\$ – Alexey Burdin Nov 14 at 15:12
  • \$\begingroup\$ Your output suggests 12 but I am not sure what orates 12 1 means \$\endgroup\$ – Anush Nov 14 at 20:52
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Alexey Burdin Nov 14 at 21:03
4
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.