Bedevil your hangman opponent

Question

Task

You are playing Hangman, and your opponent uses a simple but effective strategy: Each turn, from the remaining letters, they guess the letter that appears most frequently across all possible words. When multiple letters appear with the same maximum frequency, your opponent selects randomly among them.

That is, your opponent knows which dictionary (list of words) you've chosen your word from, and has computed a table showing how many times each letter of the alphabet appears in this dictionary. Your opponent always chooses letters with higher frequency counts before letters with lower frequency counts.

Your goal is to write a program that will select a word that maximizes their average number of guesses.

This is code golf.

Input / Output

The input will be a list of words in any convenient format, per standard site IO rules (comma delimited string, array, lines of a file, etc).

The output will be a single word from that list that maximizes your opponent's average number of guesses. If there is more than one such word, you may return any one of them.

Worked Example

If the input word list is:

one
wont
tee

The letter frequency table will be:

┌─┬─┬─┬─┬─┐
│e│t│o│n│w│
├─┼─┼─┼─┼─┤
│3│2│2│2│1│
└─┴─┴─┴─┴─┘

Your opponent will always guess e first, since it occurs most frequently. Their second, third, and fourth guesses will be split randomly among the letters t, o, and n, and w will always be guessed last.

Thus the word wont will always be completed last, on the 5th guess, and is the sole correct answer for this word list.

Notes

• Words will contain only the 26 letters a through z.
• If you want, you can use the uppercase alphabet instead.
• When there is more than one correct answer, you may return any of them. If you want, you can return all of them, but this is not required.

Test Cases

Each test case consists of two lines:

1. An input word list of space-separated words.
2. The expected output. This will be a single word when there is only one correct answer, and a space-separated list when there is more than one. Note that your program only needs to return one correct answer when there are multiple correct answers.

one wont tee
wont

aaa bbb ccc
aaa bbb ccc

oneword
oneword

thee lee
thee

tee lee
tee lee

three eon one holt
three holt

xeon threes eon one holt
threes

xeon threes eon one holt apple mango george any fine
fine

Answer 1

Python 2, 60 bytes

lambda l:min(l,key=lambda x:sorted(map(`l`.count,set(x)))+l)

Try it online!

Explanation

The idea is much like every other answer. In every word, we compute the frequency of each character. Then we take the word whose least frequent character occurs most often.

In the code, we sort the array as opposed to finding the minimum. Here is an example to show how this works: Input: thee lee baa. For each word, we compute a frequency table (duplicates are ignored): [(1, 1, 4), (1, 4), (1, 2)]. After sorting, the lexiocgraphically smallest list is (1, 1, 4), therefore the answer is thee.

There is also an edge case to consider: Input: a bc, which gives the following frequency table: [(1), (1, 1)]. The lexicographically smallest list would be (1), which is incorrect since the second list contains more 1s. I'll leave out the specifics of how the code resolves this issue

Answer 2

05AB1E, 25 16 13 11 13 12 bytes

-3 thanks to @pxeger

-2 thanks to @ovs

+2 for bug fix (for input acb abc cb and aa ab bcc bcc)

-1 for another bug fix, noticed by @ovs

ΣISТWQÏ¢O}θ

Try it online!

Legacy version, 10 bytes, thanks to @ovs

ΣIS.m¢O(}н

Try it online!

Answer 3

K (ngn/k), 35 33 28 27 20 bytes

-2 bytes from shuffling things around

-5 bytes from @Traws' improvement

-1 byte from @bstrat's improvement

-7 bytes from new approach

{*>+/'x#=/&/\#'=,/x}

Try it online!

Modeled after @xash's J answer.

• #'=,/x build a dictionary mapping characters to the number of times they appear across the entire input
• =/&/\ identify the least frequent character(s)
• +/'x# sum up the number of times the most infrequent characters appear in each word of the input
• *> filter the input down to the first word with the most infrequent character(s)

Answer 4

Stax, ^{20 18 10} 9 bytes

·╦Eà3ΩQù»

Run and debug it

Explanation coming next year™. Happy new Year!

-8 bytes from recursive using the surprisingly fitting multi-anti-mode builtin.

-1 more byte from recursive with an insane compression hack.

Replacing H from this version with E(a lower codepoint), results in -1 byte due to packing magic.

Explanation

$|!x{n|&%oE
$           join the input together
 |!         get the rarest characters(anti-mode)
   x        push the input again
    {    o  and order by the following:
     n|&    intersect with the anti-mode 
        %   and take the length
          E push all the elements onto stack
            implicitly print the last element

Answer 5

J, 32 bytes

{.@\:(~.(#~<./=])#/.~)@;+/@e."1>

Try it online!

• ; words razed to letters
• #/.~ number of occurrences of each letter
• ~. the letters deduplicated
• (#~<./=]) take only the most infrequent letters
• +/@e."1> how many of these letters occur in each word?
• {.@\: sort the words based on the amount and return the first one (the one with most infrequent letters)

Answer 6

Charcoal, 38 bytes

ＷＳ⊞υι≔Ｅβ№⪫υωιη≔ＥυＬΦ⌕Ａη⌊Φηλ№ι§βλζ§υ⌕ζ⌈ζ

Try it online! Link is to verbose version of code. Explanation:

ＷＳ⊞υι

Input the words.

≔Ｅβ№⪫υωιη

Get frequencies for all of the letters.

≔ＥυＬΦ⌕Ａη⌊Φηλ№ι§βλζ

Find the letters with the lowest positive frequencies, then for each word count how many of those letters are contained.

§υ⌕ζ⌈ζ

Output the word with the highest count.

Previous 84-byte longhand solution:

ＷＳ⊞υι≔υθ≔Ｅβ№⪫υωιη≔Ｅυ⁰ζＷ⌈η«≔⌕ＡηιεＦε§≔ηκ⁰ＵＭε§βκ≔ＥθΦκ¬№εμδＵＭζ⁺κ⎇§δλＬεＬΦε№§θλμ≔δ軧υ⌕ζ⌈ζ

Try it online! Link is to verbose version of code. Explanation:

ＷＳ⊞υι

Input the words.

≔υθ

Make a copy of the list. The letters will be removed from these words as they are guessed.

≔Ｅβ№⪫υωιη

Get frequencies for all of the letters.

≔Ｅυ⁰ζ

Start off with 0 guesses for all of the words.

Ｗ⌈η«

Repeat while there are still letters to guess.

≔⌕Ａηιε

Find the positions of the most frequent letters.

Ｆε§≔ηκ⁰

Remove them from the list of frequencies.

ＵＭε§βκ

Get the letter characters at those positions.

≔ＥθΦκ¬№εμδ

Make a temporary copy of the words with all of those letters removed.

ＵＭζ⁺κ⎇§δλＬεＬΦε№§θλμ

For words which still have some letters left, count all of the letters as guesses, otherwise just count the number of matching letters. This is the minimum number of guesses rather than the average but the sort order is the same.

≔δθ

Update the list of words with the removed letters.

»§υ⌕ζ⌈ζ

Print the word that took the most guesses.

Answer 7

R, 111 110 bytes

-1 byte thanks to Giuseppe

function(s)s[which.max(colSums(outer(names(x<-table(unlist(strsplit(s,""))))[x==min(x)],s,Vectorize(grepl))))]

Try it online!

Computes the table of number of occurrences of each letter, then the vector of letter(s) which occur the least often. These rare letters will be tried last (in random order), so we pick the word which maximises the number of distinct rare letters.

If there are several optimal words, this returns the first one. We can return all of them at a cost of 1 byte.

Answer 8

Wolfram Language (Mathematica), 60 56 bytes

#~MaximalBy~Union/*Map[c=Counts[Join@@#]]/*Count[Min@c]&

Try it online!

Input a list of character lists.

Answer 9

Ruby 2.7, 61 bytes

->w{w.min_by{_1.chars.uniq.map{|c|(w*"").count c}.sort<<1e9}}

Try it online!

Expects an array of words. Outputs the one with most rarest chars. TIO uses an older version of Ruby, whereas in Ruby 2.7, we've numbered parameters, which saves two bytes.

Answer 10

Japt -m, 29 bytes

ˬx@¬Ê/U¬èX p
VíU nÏÎ-XgÃÎg1

Try it

Not a great answer but a bit different approach.

ˬx@¬Ê/U¬èX p \$\to\$ map each word by summing the weight of each letter.

• Weight is number of all letters divided by occurrences of letter raised to a power (\$2\$) we can increase the power to get a more precise output at the cost of one byte.

VíU nÏÎ-XgÃÎg1 \$\to\$ sorts the input based on weights

Answer 11

R, 100 bytes

function(s,S=colSums)s[order(S(t(a<-matrix(sapply(letters,grepl,s),,26))*(b=S(a))!=min(b[b>0])))][1]

Try it online!

How? - ungolfed version:

f=function(s){
a<-sapply(letters,grepl,s)  # a = matrix indicating which letters (columns) are present in which words (rows)
a<-matrix(a,,26)            # (force 'a' as a matrix in case there was only one word in the input)
b<-colSums(a)               # b = for each letter, the count of the words that it is in
c<-t(a)*b                   # c = replace 'TRUE' elements of 'a' with the word counts from 'b'
d<-colSums(c==min(b[b>0]))  # d = the number of different letters in each word with the lowest overall nonzero word count
s[which.max(d)]             # output the (first) word that maximises d
}

Answer 12

Pyth, 15 bytes

.Mms/L.m/sQbsQZ

Try it online!