10
$\begingroup$

Your friend will pick a 4-letter word and you will make guesses in order to find it.

-A word can contain only the letters A, B, C, and D, and they can be used more than once. (AAAA-DDDD).

-In your guess if at least three letters are in their correct places you will win a prize.

What is the minimum number of guesses in order to guarantee to win the prize?

Edit: The question is compared to other question by many: Mastermind But I assure you that they are not the same! Mine is harder. Only feedback you will have is whether your guess is true(at least 3 letters in the right places) or not. Have fun!

$\endgroup$
  • 4
    $\begingroup$ Possible duplicate of Clever ways to solve Mastermind? $\endgroup$ – Oray Feb 24 '16 at 11:41
  • $\begingroup$ This question has been discussed before. $\endgroup$ – Oray Feb 24 '16 at 11:41
  • 3
    $\begingroup$ @Oray: Feedback was not part of the question. This is not a duplicate. $\endgroup$ – Deusovi Feb 24 '16 at 12:13
  • 1
    $\begingroup$ I could not see the connection :/ You can ask the questioner if your guess is acceptable(at least three letters in right place) or not. Nothing else, there is no other feedback. This is a probabilty question. They are similar but not the same. $\endgroup$ – Alper91 Feb 24 '16 at 13:25
  • 1
    $\begingroup$ I enjoyed a lot while solving this question Thanks @Alper91. $\endgroup$ – Oray Feb 25 '16 at 21:11
4
$\begingroup$

I have my own algorithm. It generates immediately an answer.

24

A minimum set

AAAA AABB ABDC ACBA ACAB ADCD
BAAB BABA BBDC BCAA BCBB BDCD
CACC CBAD CBBD CCCC CDDA CDDB
DADD DBCA DBCB DCDD DDAC DDBC

2-letter word

If the game is pick 2-letter word. The rules like https://www.chess.com/blog/kurtgodden/8-lonely-rooks
enter image description here
Select 1 piece will match 7 positions.

enter image description here
2-letter word. 4 steps:
Step 1: Guess any.
Step 2,3,4: Guess any but not the same row or column as in picture.

The 3-letter(8 steps) and 4-letter(24 steps) like Lonely Rooks puzzle in 3D and 4D.

Continue: 3-letter

From 4x4 square above we create 4 squares 4x4 by add A,B,C,D at the end. So now we have a cube 4x4x4 like this

enter image description here enter image description here
Select 1 pieces will match 10 position.
enter image description here 3-letter word. 8 steps:
Step 1,2: Choose any 2 pieces (but not same row or column) from A,B,C,D => I random choose from A then select AAA and CCA.
Step 3,4: Choose any 2 pieces from 3 other boards (B,C,D left) => random choose B then select CAB and ACB (not same row or column, but same row & column with previous board, board A).
Step 5,6: Choose any from other 2 boards (C,D left) => choose from C 2 pieces BBC & DDC (not same row or column)
Step 7,8: Choose 2 other pieces left from D => BDD & DBD
2 other sets: enter image description here enter image description here
4-letter game have very same method like this to get a minimum set (24 steps) A 4-D Cube 4x4x4x4 : D
https://www.youtube.com/watch?v=Aonf34s0Bqg
https://www.youtube.com/watch?v=VOUw4V1bKQQ

4-letter word

From 4 squares 4x4 above we create 16 squares 4x4 by add A,B,C,D at the end. So now we have a cube 4x4x4 like this enter image description here Select 1 piece will match 13 positions. enter image description here Use same method as 3-letter will get result:
AAAA BBAA ABBA BABA DCCA CDDA
BAAB ABAB AABB BBBB DCCB CDDB
CCAC CCBC ADCC BDCC DADC DBDC
DDAD DDBD CACD CBCD ACDD BCDD

$\endgroup$
  • $\begingroup$ very well done! $\endgroup$ – Oray Feb 29 '16 at 18:50
  • $\begingroup$ so we can tell that if it was 5 digits, the answer would be 96 :) $\endgroup$ – Oray Feb 29 '16 at 22:05
  • 1
    $\begingroup$ Welcome to Puzzling! This is a great first answer - what do the rounded corners mean though? $\endgroup$ – Deusovi Mar 1 '16 at 3:25
  • 2
    $\begingroup$ It means nothing :P sorry for my bad drawing skill. $\endgroup$ – Tim007 Mar 1 '16 at 3:30
  • $\begingroup$ This is the answer I am looking for. Well done! $\endgroup$ – Alper91 Mar 1 '16 at 8:05
6
$\begingroup$

Edit: I think I can back up Oray's solution with a proof and confirm that the answer is indeed

$24$

His algorithm suffices to give the upper bound so it only remains to show that it is also a lower bound.

Lower bound

Call a pair of words 'neighbours' if they differ by one letter e.g, $ABCD$ and $ABAD$ are neighbours.

Let us consider the map $A \rightarrow 0, B \rightarrow 1, C \rightarrow 2, D \rightarrow 3$ so that each word maps to a point in 4-dimensional space, e.g, $BACD \rightarrow (1, 0, 2, 3)$. Then the set of words is a finite hypercube lattice (of side length 3) and the set of neighbours of a given word, $W$, is the set of points which lie on some axis-parallel line passing through the point corresponding to $W$.

The set of words beginning with a given letter is a finite cubic lattice in this space.
Key Observation: Each guess eliminates $10$ possible answers from the cube containing the guess and $1$ possible answer from each of the other cubes.

Now, suppose that the number of guesses we make is less than $24$. Then there is at least one cube which contains at most $5$ guesses.

We may ask the following question: what is the maximum number of words we can eliminate from a single cube with $5$ guesses?

I propose that the answer is $45$.
To show this, notice that each cube further subdivides into four planes corresponding to fixing the second letter of the word. With $5$ guesses, there is at least one of these planes which contains at least two guesses. This pair of guesses will share at least two neighbours (call them intersections of the guesses). Alternatively, we can subdivide the cube lattice into planes in the other two directions (defined by fixing the third or fourth letter) and use the same logic to show that there exists a plane, in each of these directions, which contains at least two guesses with at least a pair of intersections. On face value this seems to constitute six intersections but really there are three possible scenarios to consider.

(i) These intersections may be distinct, in which case there are a total of six intersections.
(ii) One or more of these intersections may appear twice, in which case any double intersection counts twice (as it prevents two guesses from eliminating an additional possible answer). So again there are essentially a total of six intersections.
(iii) One intersection may appear three times. This is a special case as the triple intersection may only count twice (it prevents two guesses from eliminating a possible answer but if these two guesses also intersect here it is to neither one's detriment). Hence, in this case there are essentially five intersections.

The point is that the maximum number of words in a given cube that can be eliminated as possible answers by $5$ guesses in that cube is $5 \times 10 - 5 = 45$. The maximum number of words in a given cube that can be covered by $18$ guesses in other cubes is $18$. Hence, if we are limited to at most $23$ guesses, then there is some cube with at most $45 + 18 = 63$ out of $64$ words eliminated as possible answers. Hence, the number of guesses we must make is at least $24$.

Note 1: If the above logic does not convince you, it does not take very much computing power to show that, in a given cube of words with $5$ guesses, we can eliminate at most $45$ possible answers since ${{64}\choose{5}} = 7,624,512$ which is not terribly big.

Note 2: It should be fairly clear that it's not worth having less than five guesses in a given cube if we are limited to $23$ overall since we make up only one guess by guessing in a different cube and lose at least that by not guessing in the given cube.

Note 3: One thing that falls out from this analysis is that it may be possible, with $23$ guesses, to guarantee that either you win the prize or you definitely know your friend's word. I don't know if this is achievable but would be very interesting to see if so.

$\endgroup$
  • $\begingroup$ I think your upper bound is the answer (assuming it's the smallest such S). Since our only feedback after each guess is if you won or not, and we only care about the worst case, we can pretend that the opponent cheats and uses a strategy where after every guess, they try to pick a new word that hasn't been covered by any of the guesses so far. If they find such a word, they say "wrong". If not, they say "correct". $\endgroup$ – Mark Peters Feb 24 '16 at 17:48
4
$\begingroup$

I have a set of size

30

The set:

BACB, CABC, ABDA, ACDA, BBCA, CADD, CBBA, DAAA, 
CCDA, ABAD, ADAB, BDBD, CDAB, ADCC, CCCD, BDBA,
ABCB, DCBB, DDDC, AACB, BBDB, CCCA, BADD, DADD,
BCAC, ACDD, DBAD, CBBC, AABC, DDCC

I found this using the weighted A* algorithm with an epsilon of 5...meaning it is not guaranteed to be finding the optimal solution. I'm trying to balance runtime demands with optimality; I'll gradually reduce the epsilon to 0 and see if anything beats the above solution.

$\endgroup$
4
$\begingroup$

I have found the minimum set of

24

which are

AAAA AAAB ABBC ACCD
ACDD ADBC BABD BBCA
BBDB BCAC BDCB BDDA
CACC CADC CBAD CCBA
CCBB CDAD DABD DBCB
DBDA DCAC DDCA DDDB

This is the optimal solution (actually there are 4 solutions but they are mirrors so I share with AAAA version with you: BBBB CCCC and DDDD versions are possible too), found by using computer programming with my own algorithm that I had mentioned on my deleted post:

  • Take a word (from the table all possible 256 words), find the maximum number of matches with 13 possible words by changing one letter from A to D from each digit.
  • Try to find matches in the Word Pool and count how many matches there are with all words,
  • Choose a word randomly which has the highest amount of matches,
  • Remove those matched words from the word pool with the word you chose randomly,
  • Go back to the beginning and go on until you do not have any word left in your word pool and count your tries.

I wish I wanted to share the code, but it is too messy, but the algorithm is something like this.

As a result, I got

24

which is found after 8 hours of running my coding... I wanted to explain the result but this is purely found by computer.

$\endgroup$
  • $\begingroup$ Kudos on finding a small set, but maybe you could explain your assertion that "this is the optimal solution", given that you apparently didn't do an exhaustive search. 256 choose 26 is 274153227480348207935266705643775360, which is a heck of a lot more than 1000000. $\endgroup$ – Mark Peters Feb 26 '16 at 1:41
  • $\begingroup$ @MarkPeters after a couple of words, the rest becomes like filling the blanks, the first chooses are the most important part. $\endgroup$ – Oray Feb 26 '16 at 6:24

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.