22
\$\begingroup\$

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
\$\endgroup\$
8
  • \$\begingroup\$ Is it fine if we return all correct answers? \$\endgroup\$
    – Razetime
    Dec 31 '20 at 16:49
  • \$\begingroup\$ @Razetime Yep, see the 3rd point under "Notes". \$\endgroup\$
    – Jonah
    Dec 31 '20 at 16:54
  • 1
    \$\begingroup\$ I'm saving this for the "Trickiest Challenge" category for best-of 2020. \$\endgroup\$
    – Razetime
    Dec 31 '20 at 17:22
  • 1
    \$\begingroup\$ aa is not a valid output for aa ab bcc bcc, right? \$\endgroup\$
    – att
    Dec 31 '20 at 19:53
  • \$\begingroup\$ @att Correct. ab is the only correct answer. \$\endgroup\$
    – Jonah
    Dec 31 '20 at 20:13

12 Answers 12

5
\$\begingroup\$

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
\$\endgroup\$
8
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ set(x) -> {*x} save 2 bytes \$\endgroup\$
    – Danis
    Jan 2 at 9:55
  • 2
    \$\begingroup\$ @a25bedc5-3d09-41b8-82fb-ea6c353d75ae that doesn't work in Python 2 \$\endgroup\$
    – pxeger
    Jan 2 at 20:35
6
\$\begingroup\$

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!

\$\endgroup\$
8
  • \$\begingroup\$ 13 bytes Try it online! \$\endgroup\$
    – pxeger
    Dec 31 '20 at 19:55
  • \$\begingroup\$ Do you have to take in input space seperated? \$\endgroup\$ Dec 31 '20 at 20:05
  • \$\begingroup\$ nvm I see that you use the unarrayed input \$\endgroup\$ Dec 31 '20 at 20:06
  • 1
    \$\begingroup\$ In the legacy edition .m returned all least frequent elements, which can be used for 10 bytes (For some reason Σ didn't sort without the (, not sure what is happening there) \$\endgroup\$
    – ovs
    Jan 1 at 12:27
  • \$\begingroup\$ But I think both your current version and my suggestion fail if the space is the single least frequent character in the input, so you need something like IðK to fix this. \$\endgroup\$
    – ovs
    Jan 1 at 12:30
5
\$\begingroup\$

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)
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Well done. You win the coveted "First posted answer is in J" badge. \$\endgroup\$
    – Jonah
    Dec 31 '20 at 17:07
  • 4
    \$\begingroup\$ @Jonah whenever I see a challenge from you I'm sure it can be solved quickly in J. :-) \$\endgroup\$
    – xash
    Dec 31 '20 at 17:16
5
\$\begingroup\$

K (ngn/k), 35 33 28 bytes

-2 bytes from shuffling things around

-5 bytes from @Traws' improvement

{x@*>+//'+x=/:&c=&/c:#'=,/x}

Try it online!

Modeled after @xash's J answer.

  • c:#'=,/x build a dictionary mapping characters to the number of times they appear across the entire input, storing in c
  • &c=&/c filter down to only the most infrequent character(s)
  • +//'+x=/: sum up the number of times the most infrequent characters appear in each word of the input
  • x@*> filter the input down to the first word with the most infrequent character(s)
\$\endgroup\$
1
  • 1
    \$\begingroup\$ You may save a few bytes by outputting just one solution when there are multiple: {x@*>+//'+x=/:&s=&/s:#'=,/x} \$\endgroup\$
    – Traws
    Jan 11 at 18:58
3
\$\begingroup\$

Charcoal, 38 bytes

WS⊞υι≔Eβ№⪫υωιη≔EυLΦ⌕Aη⌊Φηλ№ι§βλζ§υ⌕ζ⌈ζ

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

WS⊞υι

Input the words.

≔Eβ№⪫υωιη

Get frequencies for all of the letters.

≔EυLΦ⌕Aη⌊Φηλ№ι§βλζ

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:

WS⊞υι≔υθ≔Eβ№⪫υωιη≔Eυ⁰ζW⌈η«≔⌕AηιεFε§≔ηκ⁰UMε§βκ≔EθΦκ¬№εμδUMζ⁺κ⎇§δλLεLΦε№§θλμ≔δ軧υ⌕ζ⌈ζ

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

WS⊞υι

Input the words.

≔υθ

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

≔Eβ№⪫υωιη

Get frequencies for all of the letters.

≔Eυ⁰ζ

Start off with 0 guesses for all of the words.

W⌈η«

Repeat while there are still letters to guess.

≔⌕Aηιε

Find the positions of the most frequent letters.

Fε§≔ηκ⁰

Remove them from the list of frequencies.

UMε§βκ

Get the letter characters at those positions.

≔EθΦκ¬№εμδ

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

UMζ⁺κ⎇§δλLεLΦε№§θλμ

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ 110 bytes. not much left to golf here, apart from thinking of another approach. I did try gregexpr along with lengths, but constructing the regex of least frequent characters is longer. \$\endgroup\$
    – Giuseppe
    Dec 31 '20 at 18:06
  • \$\begingroup\$ @Giuseppe Thanks! \$\endgroup\$ Dec 31 '20 at 19:27
2
\$\begingroup\$

Wolfram Language (Mathematica), 60 56 bytes

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

Try it online!

Input a list of character lists.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ tally is nice addition to Enumerable \$\endgroup\$
    – Jonah
    Dec 31 '20 at 22:32
  • \$\begingroup\$ @Jonah - Unfortunately, tally adds load to the code, so I receded back to Ruby, and now I have a TIO link :-) \$\endgroup\$
    – vrintle
    Jan 1 at 4:04
  • 1
    \$\begingroup\$ I like that trick to make the sorting work how we need, though ofc now i can't run the program with billion character words :) \$\endgroup\$
    – Jonah
    Jan 1 at 18:16
  • \$\begingroup\$ Yeah, lol xD. I could also push w.size, but that's 3 bytes longer.. \$\endgroup\$
    – vrintle
    Jan 2 at 9:22
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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
}

\$\endgroup\$
1
\$\begingroup\$

Pyth, 15 bytes

.Mms/L.m/sQbsQZ

Try it online!

\$\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.