Kilordle String Problem

Revision en1, by ComboGirl, 2022-04-09 00:15:58

Here's an interesting string problem I have been thinking about related to the game of Kilordle, a variant of Wordle.

Kilordle is a word game played like Wordle, but instead of having one game, you play several games of wordle simultaneously, and each guess is applied to each individual game. You win after correctly solving every game of wordle. In kilordle, you don't have to guess the exact word for any of the individual games. As long as you guess words that have letters in the correct places that will suffice. You can guess as many times as you want. For example, if the word for one of the individual games is "CARTS", then if you guess "CAtch" and then "foRTS" that individual game will be solved, as you have guessed a word that contains C as the first letter, you've guessed a word that contains A as the second letter, you've guessed a word that contains R as the third letter, etc.

One simple strategy for kilordle is just to type in a sequence of words that covers all possible words in the dictionary.

Formally, suppose the dictionary contains a set $$$S$$$ of $$$n$$$ strings, each of length $$$k,$$$ and there are $$$m$$$ distinct letters in the language. Give an efficient algorithm to find the size of the smallest subset $$$S' \subset S$$$ such that for all $$$s \in S,$$$ and all $$$1 \leq i \leq k,$$$ there exists some $$$s' \in S'$$$ such that $$$s[i] = s'[i].$$$

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English ComboGirl 2022-04-09 00:16:29 48 (published)
en1 English ComboGirl 2022-04-09 00:15:58 1387 Initial revision (saved to drafts)